1683:
of the quadratic residue codes with the code length up to 113. However, decoding of long binary quadratic residue codes and non-binary quadratic residue codes continue to be a challenge. Currently, decoding quadratic residue codes is still an active research area in the theory of error-correcting
1637:
Since late 1980, there are many algebraic decoding algorithms were developed for correcting errors on quadratic residue codes. These algorithms can achieve the (true) error-correcting capacity
486:
1387:
960:
1681:
1159:
579:
1472:
1588:
1001:
850:
1627:
1514:
1748:
Y. Li, Y. Duan, H. C. Chang, H. Liu, T. K. Truong, Using the difference of syndromes to decode quadratic residue codes, IEEE Trans. Inf. Theory 64(7), 5179-5190 (2018)
1192:
783:
147:
1082:
803:
599:
214:
743:
651:
309:
249:
182:
115:
80:
1416:
1324:
1027:
1215:
1534:
1448:
1295:
1275:
1255:
1235:
1102:
1047:
890:
870:
823:
711:
691:
671:
619:
529:
509:
413:
389:
369:
349:
329:
277:
1730:
Reed, I.S., Truong, T.K., Chen, X., Yin, X., The algebraic decoding of the (41, 21, 9) quadratic residue code. IEEE Trans. Inf. Theory 38(3), 974–986 (1992)
1724:
M. Elia, Algebraic decoding of the (23,12,7) Golay code, IEEE Transactions on
Information Theory, Volume: 33, Issue: 1, pg. 150-151, January 1987.
1727:
Reed, I.S., Yin, X., Truong, T.K., Algebraic decoding of the (32, 16, 8) quadratic residue code. IEEE Trans. Inf. Theory 36(4), 876–880 (1990)
1742:
He, R., Reed, I.S., Truong, T.K., Chen, X., Decoding the (47, 24, 11) quadratic residue code. IEEE Trans. Inf. Theory 47(3), 1181–1186 (2001)
1736:
Chen, X., Reed, I.S., Truong, T.K., Decoding the (73, 37, 13) quadratic-residue code. IEE Proc., Comput. Digit. Tech. 141(5), 253–258 (1994)
1733:
Humphreys, J.F. Algebraic decoding of the ternary (13, 7, 5) quadratic-residue code. IEEE Trans. Inf. Theory 38(3), 1122–1125 (May 1992)
17:
1739:
Higgs, R.J., Humphreys, J.F.: Decoding the ternary (23, 12, 8) quadratic-residue code. IEE Proc., Comm. 142(3), 129–134 (June 1995)
421:
1329:
1536:) an extended quadratic residue code is self-dual; otherwise it is equivalent but not equal to its dual. By the
901:
1640:
1548:), the automorphism group of an extended quadratic residue code has a subgroup which is isomorphic to either
1107:
534:
1761:
1453:
1551:
968:
828:
1766:
1593:
1493:
1427:
1164:
748:
120:
1052:
788:
584:
187:
716:
624:
282:
222:
155:
88:
53:
1392:
1300:
8:
1006:
1197:
1519:
1433:
1280:
1260:
1240:
1220:
1087:
1032:
875:
855:
808:
696:
676:
656:
604:
514:
494:
398:
374:
354:
334:
314:
262:
216:
392:
149:
1713:
852:
either results in the same code or an equivalent code, according to whether or not
1541:
1755:
1545:
1701:
82:
1486:
Adding an overall parity-check digit to a quadratic residue code gives an
39:
1717:
1326:
also generates a quadratic residue code; more precisely the ideal of
28:
1697:, North-Holland Publishing Co., Amsterdam-New York-Oxford, 1977.
895:
An alternative construction avoids roots of unity. Define
415:. Its generator polynomial as a cyclic code is given by
1643:
1596:
1554:
1522:
1496:
1456:
1436:
1395:
1332:
1303:
1283:
1263:
1243:
1223:
1200:
1167:
1110:
1090:
1055:
1035:
1009:
971:
904:
878:
858:
831:
811:
791:
751:
719:
699:
679:
659:
627:
607:
587:
537:
517:
497:
424:
401:
377:
357:
337:
317:
285:
265:
225:
190:
158:
123:
91:
56:
621:th root of unity in some finite extension field of
1675:
1621:
1582:
1528:
1508:
1466:
1442:
1410:
1381:
1318:
1289:
1269:
1249:
1229:
1209:
1186:
1153:
1096:
1076:
1041:
1021:
995:
954:
884:
864:
844:
817:
797:
777:
737:
705:
685:
665:
645:
613:
593:
573:
523:
503:
481:{\displaystyle f(x)=\prod _{j\in Q}(x-\zeta ^{j})}
480:
407:
383:
363:
343:
323:
303:
271:
243:
208:
176:
141:
109:
74:
1712:(5), Piscataway, NJ, USA: IEEE Press: 1269–1273,
1753:
1704:(September 2006), "The Gleason-Prange theorem",
50:Examples of quadratic residue codes include the
1382:{\displaystyle F_{l}/\langle X^{p}-1\rangle }
1670:
1644:
1376:
1357:
568:
538:
259:There is a quadratic residue code of length
1418:corresponds to the quadratic residue code.
955:{\displaystyle g(x)=c+\sum _{j\in Q}x^{j}}
1693:F. J. MacWilliams and N. J. A. Sloane,
1676:{\displaystyle \lfloor (d-1)/2\rfloor }
1154:{\displaystyle c=(1+{\sqrt {p^{*}}})/2}
14:
1754:
1700:
1430:of a quadratic residue code of length
1695:The Theory of Error-Correcting Codes
511:is the set of quadratic residues of
574:{\displaystyle \{1,2,\ldots ,p-1\}}
24:
1632:
25:
1778:
693:ensures that the coefficients of
1481:
254:
1488:extended quadratic residue code
745:. The dimension of the code is
1659:
1647:
1616:
1610:
1577:
1571:
1405:
1399:
1349:
1343:
1313:
1307:
1140:
1117:
1065:
1059:
990:
984:
914:
908:
764:
752:
732:
726:
640:
634:
475:
456:
434:
428:
298:
292:
238:
232:
203:
191:
171:
165:
136:
124:
104:
98:
69:
57:
13:
1:
1687:
7:
1467:{\displaystyle {\sqrt {p}}}
45:
10:
1783:
1583:{\displaystyle PSL_{2}(p)}
996:{\displaystyle c\in GF(l)}
872:is a quadratic residue of
845:{\displaystyle \zeta ^{r}}
673:is a quadratic residue of
26:
1622:{\displaystyle SL_{2}(p)}
1509:{\displaystyle p\equiv 3}
1421:
27:Not to be confused with
1706:IEEE Trans. Inf. Theory
1187:{\displaystyle p^{*}=p}
778:{\displaystyle (p+1)/2}
142:{\displaystyle (23,12)}
1677:
1623:
1584:
1538:Gleason–Prange theorem
1530:
1510:
1468:
1444:
1412:
1383:
1320:
1291:
1271:
1251:
1231:
1211:
1188:
1155:
1098:
1078:
1077:{\displaystyle g(1)=1}
1043:
1023:
997:
956:
886:
866:
846:
819:
799:
798:{\displaystyle \zeta }
779:
739:
707:
687:
667:
647:
615:
595:
594:{\displaystyle \zeta }
575:
525:
505:
482:
409:
385:
365:
345:
325:
305:
279:over the finite field
273:
245:
210:
209:{\displaystyle (11,6)}
178:
143:
111:
76:
36:quadratic residue code
18:Gleason–Prange theorem
1678:
1624:
1585:
1531:
1511:
1469:
1445:
1413:
1384:
1321:
1292:
1272:
1252:
1232:
1217:according to whether
1212:
1189:
1156:
1099:
1079:
1044:
1024:
998:
957:
887:
867:
847:
820:
805:by another primitive
800:
780:
740:
738:{\displaystyle GF(l)}
708:
688:
668:
653:. The condition that
648:
646:{\displaystyle GF(l)}
616:
596:
576:
526:
506:
483:
410:
386:
366:
346:
326:
306:
304:{\displaystyle GF(l)}
274:
246:
244:{\displaystyle GF(3)}
211:
179:
177:{\displaystyle GF(2)}
144:
112:
110:{\displaystyle GF(2)}
77:
75:{\displaystyle (7,4)}
1641:
1594:
1552:
1520:
1494:
1454:
1434:
1411:{\displaystyle g(x)}
1393:
1330:
1319:{\displaystyle g(x)}
1301:
1281:
1261:
1241:
1221:
1198:
1165:
1108:
1088:
1053:
1033:
1007:
969:
902:
876:
856:
829:
809:
789:
749:
717:
697:
677:
657:
625:
605:
585:
535:
515:
495:
422:
399:
375:
355:
335:
315:
283:
263:
223:
188:
156:
121:
89:
54:
1022:{\displaystyle l=2}
1673:
1619:
1580:
1526:
1506:
1464:
1440:
1408:
1379:
1316:
1287:
1267:
1247:
1227:
1210:{\displaystyle -p}
1207:
1184:
1151:
1094:
1074:
1039:
1019:
993:
952:
941:
882:
862:
842:
825:-th root of unity
815:
795:
775:
735:
703:
683:
663:
643:
611:
591:
571:
521:
501:
478:
455:
405:
381:
361:
341:
321:
301:
269:
241:
217:ternary Golay code
206:
174:
139:
107:
72:
1762:Quadratic residue
1718:10.1109/18.133245
1529:{\displaystyle 4}
1476:square root bound
1462:
1443:{\displaystyle p}
1290:{\displaystyle 4}
1270:{\displaystyle 3}
1250:{\displaystyle 1}
1230:{\displaystyle p}
1138:
1097:{\displaystyle l}
1042:{\displaystyle c}
926:
885:{\displaystyle p}
865:{\displaystyle r}
818:{\displaystyle p}
706:{\displaystyle f}
686:{\displaystyle p}
666:{\displaystyle l}
614:{\displaystyle p}
524:{\displaystyle p}
504:{\displaystyle Q}
440:
408:{\displaystyle p}
393:quadratic residue
384:{\displaystyle l}
364:{\displaystyle p}
344:{\displaystyle l}
324:{\displaystyle p}
272:{\displaystyle p}
150:binary Golay code
16:(Redirected from
1774:
1720:
1682:
1680:
1679:
1674:
1666:
1628:
1626:
1625:
1620:
1609:
1608:
1589:
1587:
1586:
1581:
1570:
1569:
1535:
1533:
1532:
1527:
1515:
1513:
1512:
1507:
1473:
1471:
1470:
1465:
1463:
1458:
1450:is greater than
1449:
1447:
1446:
1441:
1417:
1415:
1414:
1409:
1388:
1386:
1385:
1380:
1369:
1368:
1356:
1342:
1341:
1325:
1323:
1322:
1317:
1296:
1294:
1293:
1288:
1276:
1274:
1273:
1268:
1256:
1254:
1253:
1248:
1237:is congruent to
1236:
1234:
1233:
1228:
1216:
1214:
1213:
1208:
1193:
1191:
1190:
1185:
1177:
1176:
1160:
1158:
1157:
1152:
1147:
1139:
1137:
1136:
1127:
1104:is odd, choose
1103:
1101:
1100:
1095:
1083:
1081:
1080:
1075:
1048:
1046:
1045:
1040:
1028:
1026:
1025:
1020:
1002:
1000:
999:
994:
961:
959:
958:
953:
951:
950:
940:
891:
889:
888:
883:
871:
869:
868:
863:
851:
849:
848:
843:
841:
840:
824:
822:
821:
816:
804:
802:
801:
796:
784:
782:
781:
776:
771:
744:
742:
741:
736:
712:
710:
709:
704:
692:
690:
689:
684:
672:
670:
669:
664:
652:
650:
649:
644:
620:
618:
617:
612:
600:
598:
597:
592:
580:
578:
577:
572:
530:
528:
527:
522:
510:
508:
507:
502:
487:
485:
484:
479:
474:
473:
454:
414:
412:
411:
406:
390:
388:
387:
382:
370:
368:
367:
362:
350:
348:
347:
342:
330:
328:
327:
322:
310:
308:
307:
302:
278:
276:
275:
270:
250:
248:
247:
242:
215:
213:
212:
207:
183:
181:
180:
175:
148:
146:
145:
140:
116:
114:
113:
108:
81:
79:
78:
73:
21:
1782:
1781:
1777:
1776:
1775:
1773:
1772:
1771:
1752:
1751:
1690:
1662:
1642:
1639:
1638:
1635:
1633:Decoding Method
1604:
1600:
1595:
1592:
1591:
1565:
1561:
1553:
1550:
1549:
1521:
1518:
1517:
1495:
1492:
1491:
1484:
1457:
1455:
1452:
1451:
1435:
1432:
1431:
1424:
1394:
1391:
1390:
1364:
1360:
1352:
1337:
1333:
1331:
1328:
1327:
1302:
1299:
1298:
1282:
1279:
1278:
1262:
1259:
1258:
1242:
1239:
1238:
1222:
1219:
1218:
1199:
1196:
1195:
1172:
1168:
1166:
1163:
1162:
1143:
1132:
1128:
1126:
1109:
1106:
1105:
1089:
1086:
1085:
1054:
1051:
1050:
1049:to ensure that
1034:
1031:
1030:
1008:
1005:
1004:
970:
967:
966:
965:for a suitable
946:
942:
930:
903:
900:
899:
877:
874:
873:
857:
854:
853:
836:
832:
830:
827:
826:
810:
807:
806:
790:
787:
786:
767:
750:
747:
746:
718:
715:
714:
698:
695:
694:
678:
675:
674:
658:
655:
654:
626:
623:
622:
606:
603:
602:
601:is a primitive
586:
583:
582:
536:
533:
532:
516:
513:
512:
496:
493:
492:
469:
465:
444:
423:
420:
419:
400:
397:
396:
376:
373:
372:
356:
353:
352:
336:
333:
332:
316:
313:
312:
284:
281:
280:
264:
261:
260:
257:
224:
221:
220:
189:
186:
185:
157:
154:
153:
122:
119:
118:
90:
87:
86:
55:
52:
51:
48:
32:
23:
22:
15:
12:
11:
5:
1780:
1770:
1769:
1764:
1750:
1749:
1746:
1743:
1740:
1737:
1734:
1731:
1728:
1725:
1722:
1698:
1689:
1686:
1672:
1669:
1665:
1661:
1658:
1655:
1652:
1649:
1646:
1634:
1631:
1618:
1615:
1612:
1607:
1603:
1599:
1579:
1576:
1573:
1568:
1564:
1560:
1557:
1542:Andrew Gleason
1525:
1505:
1502:
1499:
1483:
1480:
1474:; this is the
1461:
1439:
1428:minimum weight
1423:
1420:
1407:
1404:
1401:
1398:
1378:
1375:
1372:
1367:
1363:
1359:
1355:
1351:
1348:
1345:
1340:
1336:
1315:
1312:
1309:
1306:
1286:
1266:
1246:
1226:
1206:
1203:
1183:
1180:
1175:
1171:
1150:
1146:
1142:
1135:
1131:
1125:
1122:
1119:
1116:
1113:
1093:
1073:
1070:
1067:
1064:
1061:
1058:
1038:
1018:
1015:
1012:
992:
989:
986:
983:
980:
977:
974:
963:
962:
949:
945:
939:
936:
933:
929:
925:
922:
919:
916:
913:
910:
907:
881:
861:
839:
835:
814:
794:
774:
770:
766:
763:
760:
757:
754:
734:
731:
728:
725:
722:
702:
682:
662:
642:
639:
636:
633:
630:
610:
590:
570:
567:
564:
561:
558:
555:
552:
549:
546:
543:
540:
520:
500:
489:
488:
477:
472:
468:
464:
461:
458:
453:
450:
447:
443:
439:
436:
433:
430:
427:
404:
380:
360:
340:
320:
300:
297:
294:
291:
288:
268:
256:
253:
240:
237:
234:
231:
228:
205:
202:
199:
196:
193:
173:
170:
167:
164:
161:
138:
135:
132:
129:
126:
106:
103:
100:
97:
94:
71:
68:
65:
62:
59:
47:
44:
9:
6:
4:
3:
2:
1779:
1768:
1767:Coding theory
1765:
1763:
1760:
1759:
1757:
1747:
1744:
1741:
1738:
1735:
1732:
1729:
1726:
1723:
1719:
1715:
1711:
1707:
1703:
1702:Blahut, R. E.
1699:
1696:
1692:
1691:
1685:
1667:
1663:
1656:
1653:
1650:
1630:
1613:
1605:
1601:
1597:
1574:
1566:
1562:
1558:
1555:
1547:
1546:Eugene Prange
1543:
1539:
1523:
1503:
1500:
1497:
1489:
1482:Extended code
1479:
1477:
1459:
1437:
1429:
1419:
1402:
1396:
1389:generated by
1373:
1370:
1365:
1361:
1353:
1346:
1338:
1334:
1310:
1304:
1284:
1264:
1244:
1224:
1204:
1201:
1181:
1178:
1173:
1169:
1148:
1144:
1133:
1129:
1123:
1120:
1114:
1111:
1091:
1071:
1068:
1062:
1056:
1036:
1016:
1013:
1010:
987:
981:
978:
975:
972:
947:
943:
937:
934:
931:
927:
923:
920:
917:
911:
905:
898:
897:
896:
893:
879:
859:
837:
833:
812:
792:
772:
768:
761:
758:
755:
729:
723:
720:
700:
680:
660:
637:
631:
628:
608:
588:
565:
562:
559:
556:
553:
550:
547:
544:
541:
518:
498:
470:
466:
462:
459:
451:
448:
445:
441:
437:
431:
425:
418:
417:
416:
402:
394:
378:
371:is odd, and
358:
338:
318:
295:
289:
286:
266:
255:Constructions
252:
235:
229:
226:
218:
200:
197:
194:
168:
162:
159:
151:
133:
130:
127:
101:
95:
92:
84:
66:
63:
60:
43:
41:
38:is a type of
37:
30:
19:
1709:
1705:
1694:
1636:
1537:
1487:
1485:
1475:
1425:
964:
894:
785:. Replacing
490:
351:are primes,
258:
83:Hamming code
49:
35:
33:
1540:(named for
531:in the set
40:cyclic code
1756:Categories
1688:References
1671:⌋
1654:−
1645:⌊
1501:≡
1377:⟩
1371:−
1358:⟨
1202:−
1174:∗
1134:∗
976:∈
935:∈
928:∑
834:ζ
793:ζ
589:ζ
563:−
554:…
467:ζ
463:−
449:∈
442:∏
311:whenever
1684:code.
1161:, where
184:and the
46:Examples
1490:. When
1297:. Then
1277:modulo
1029:choose
1003:. When
713:lie in
395:modulo
29:QR Code
1422:Weight
491:where
117:, the
1516:(mod
1084:. If
391:is a
219:over
152:over
85:over
1544:and
1426:The
581:and
331:and
1714:doi
1590:or
1257:or
1194:or
1758::
1745:….
1710:37
1708:,
1629:.
1478:.
892:.
251:.
195:11
134:12
128:23
42:.
34:A
1721:.
1716::
1668:2
1664:/
1660:)
1657:1
1651:d
1648:(
1617:)
1614:p
1611:(
1606:2
1602:L
1598:S
1578:)
1575:p
1572:(
1567:2
1563:L
1559:S
1556:P
1524:4
1504:3
1498:p
1460:p
1438:p
1406:)
1403:x
1400:(
1397:g
1374:1
1366:p
1362:X
1354:/
1350:]
1347:X
1344:[
1339:l
1335:F
1314:)
1311:x
1308:(
1305:g
1285:4
1265:3
1245:1
1225:p
1205:p
1182:p
1179:=
1170:p
1149:2
1145:/
1141:)
1130:p
1124:+
1121:1
1118:(
1115:=
1112:c
1092:l
1072:1
1069:=
1066:)
1063:1
1060:(
1057:g
1037:c
1017:2
1014:=
1011:l
991:)
988:l
985:(
982:F
979:G
973:c
948:j
944:x
938:Q
932:j
924:+
921:c
918:=
915:)
912:x
909:(
906:g
880:p
860:r
838:r
813:p
773:2
769:/
765:)
762:1
759:+
756:p
753:(
733:)
730:l
727:(
724:F
721:G
701:f
681:p
661:l
641:)
638:l
635:(
632:F
629:G
609:p
569:}
566:1
560:p
557:,
551:,
548:2
545:,
542:1
539:{
519:p
499:Q
476:)
471:j
460:x
457:(
452:Q
446:j
438:=
435:)
432:x
429:(
426:f
403:p
379:l
359:p
339:l
319:p
299:)
296:l
293:(
290:F
287:G
267:p
239:)
236:3
233:(
230:F
227:G
204:)
201:6
198:,
192:(
172:)
169:2
166:(
163:F
160:G
137:)
131:,
125:(
105:)
102:2
99:(
96:F
93:G
70:)
67:4
64:,
61:7
58:(
31:.
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.