192:
942:
532:
405:
1181:
1059:
813:
267:
Once the error locations are known, the next step is to determine the error values at those locations. The error values are then used to correct the received values at those locations to recover the original codeword.
1269:
1196:
would be an element of the finite field. The operator ⋅ represents ordinary multiplication (repeated addition in the finite field) which is the same as the finite field's multiplication operator, i.e.
648:
1406:
1479:
262:
1307:
67:
554:
824:
411:
284:
1093:
670:
1640:
1569:
964:
1203:
1598:
1495:
33:
569:
1343:
55:
Code words look like polynomials. By design, the generator polynomial has consecutive roots α, α, ..., α.
1427:
220:
1645:
1321:
1277:
28:) calculates the error values at known error locations. It is used as one of the steps in decoding
560:
187:{\displaystyle \Lambda (x)=\prod _{i=1}^{\nu }(1-x\,X_{i})=1+\sum _{i=1}^{\nu }\lambda _{i}\,x^{i}}
1624:
538:
1586:
1080:
1070:
1578:
559:
However, there is a more efficient method known as the Forney algorithm, which is based on
1607:
937:{\displaystyle e_{j}=-{\frac {X_{j}^{1-c}\,\Omega (X_{j}^{-1})}{\Lambda '(X_{j}^{-1})}}\,}
527:{\displaystyle s_{1}=e_{1}\alpha ^{(c+1)\,i_{1}}+e_{2}\alpha ^{(c+1)\,i_{2}}+\cdots \,}
400:{\displaystyle s_{0}=e_{1}\alpha ^{(c+0)\,i_{1}}+e_{2}\alpha ^{(c+0)\,i_{2}}+\cdots \,}
1421:
If both errors and erasures are present, use the error-and-erasure locator polynomial
1634:
17:
1564:
37:
1176:{\displaystyle \Lambda '(x)=\sum _{i=1}^{\nu }i\,\cdot \,\lambda _{i}\,x^{i-1}}
808:{\displaystyle S(x)=s_{0}x^{0}+s_{1}x^{1}+s_{2}x^{2}+\cdots +s_{2t-1}x^{2t-1}.}
1590:
1582:
1054:{\displaystyle e_{j}=-{\frac {\Omega (X_{j}^{-1})}{\Lambda '(X_{j}^{-1})}}}
1264:{\displaystyle i\lambda =(1+\ldots +1)\lambda =\lambda +\ldots +\lambda .}
1490:
951:
is often called the "first consecutive root" or "fcr". Some codes select
29:
1418:. Apply the procedure described above, substituting Γ for Λ.
1329:, pp. 52–54) gives a derivation of the Forney algorithm.
643:{\displaystyle \Omega (x)=S(x)\,\Lambda (x){\pmod {x^{2t}}}\,}
1401:{\displaystyle \Gamma (x)=\prod (1-x\,\alpha ^{j_{i}})}
217:. The zeros are the reciprocals of the error locations
1606:, Stanford University, pp. 42–45, archived from
1430:
1346:
1280:
1206:
1096:
967:
827:
673:
572:
541:
414:
287:
223:
70:
1473:
1400:
1301:
1263:
1175:
1053:
936:
807:
642:
548:
526:
399:
256:
186:
563:. First calculate the error evaluator polynomial
1474:{\displaystyle \Psi (x)=\Lambda (x)\,\Gamma (x)}
278:can be determined by solving the linear system
50:Need to introduce terminology and the setup...
1537:
1535:
1533:
8:
271:In the more general case, the error weights
1567:(October 1965), "On Decoding BCH Codes",
1458:
1429:
1411:Where the erasure locations are given by
1387:
1382:
1377:
1345:
1279:
1205:
1161:
1156:
1150:
1145:
1141:
1132:
1121:
1095:
1036:
1031:
1002:
997:
984:
972:
966:
933:
918:
913:
884:
879:
868:
856:
851:
844:
832:
826:
787:
768:
749:
739:
726:
716:
703:
693:
672:
639:
626:
613:
600:
571:
545:
540:
523:
509:
504:
488:
478:
463:
458:
442:
432:
419:
413:
396:
382:
377:
361:
351:
336:
331:
315:
305:
292:
286:
246:
241:
228:
222:
178:
173:
167:
157:
146:
124:
119:
101:
90:
69:
1570:IEEE Transactions on Information Theory
1506:
1083:of the error locator polynomial Λ(
1513:
1337:Define the erasure locator polynomial
257:{\displaystyle X_{j}=\alpha ^{i_{j}}}
7:
1553:
1541:
1524:
1326:
1302:{\displaystyle i\lambda =0,\lambda }
664:is the partial syndrome polynomial:
1496:Reed–Solomon error correction
1274:For instance, in characteristic 2,
1186:In the above expression, note that
958:, so the expression simplifies to:
621:
1459:
1446:
1431:
1347:
1098:
1017:
987:
899:
869:
601:
573:
71:
14:
818:Then evaluate the error values:
614:
1641:Error detection and correction
1468:
1462:
1455:
1449:
1440:
1434:
1395:
1365:
1356:
1350:
1234:
1216:
1111:
1105:
1045:
1024:
1011:
990:
927:
906:
893:
872:
683:
677:
635:
615:
610:
604:
597:
591:
582:
576:
501:
489:
455:
443:
374:
362:
328:
316:
130:
107:
80:
74:
1:
36:(a subclass of BCH codes).
1600:EE387 Notes #7, Handout #28
1662:
1068:
61:Error location polynomial
1190:is an integer, and λ
549:{\displaystyle \cdots \,}
40:developed the algorithm.
1583:10.1109/TIT.1965.1053825
34:Reed–Solomon codes
38:George David Forney Jr.
1475:
1402:
1322:Lagrange interpolation
1303:
1265:
1177:
1137:
1055:
938:
809:
644:
561:Lagrange interpolation
550:
528:
401:
258:
188:
162:
106:
1476:
1403:
1304:
1266:
1178:
1117:
1056:
939:
810:
645:
551:
529:
402:
259:
189:
142:
86:
1428:
1344:
1278:
1204:
1094:
965:
825:
671:
570:
539:
412:
285:
221:
197:The zeros of Λ(
68:
1597:Gill, John (n.d.),
1044:
1010:
926:
892:
867:
1625:W. Wesley Peterson
1471:
1398:
1299:
1261:
1173:
1051:
1027:
993:
934:
909:
875:
847:
805:
640:
546:
524:
397:
254:
184:
26:Forney's algorithm
1081:formal derivative
1071:Formal derivative
1065:Formal derivative
1049:
931:
1653:
1621:
1620:
1618:
1613:on June 30, 2014
1612:
1605:
1593:
1557:
1551:
1545:
1539:
1528:
1522:
1516:
1511:
1480:
1478:
1477:
1472:
1407:
1405:
1404:
1399:
1394:
1393:
1392:
1391:
1313:is even or odd.
1308:
1306:
1305:
1300:
1270:
1268:
1267:
1262:
1182:
1180:
1179:
1174:
1172:
1171:
1155:
1154:
1136:
1131:
1104:
1060:
1058:
1057:
1052:
1050:
1048:
1043:
1035:
1023:
1014:
1009:
1001:
985:
977:
976:
957:
950:
943:
941:
940:
935:
932:
930:
925:
917:
905:
896:
891:
883:
866:
855:
845:
837:
836:
814:
812:
811:
806:
801:
800:
782:
781:
754:
753:
744:
743:
731:
730:
721:
720:
708:
707:
698:
697:
663:
649:
647:
646:
641:
638:
634:
633:
555:
553:
552:
547:
533:
531:
530:
525:
516:
515:
514:
513:
483:
482:
470:
469:
468:
467:
437:
436:
424:
423:
406:
404:
403:
398:
389:
388:
387:
386:
356:
355:
343:
342:
341:
340:
310:
309:
297:
296:
277:
263:
261:
260:
255:
253:
252:
251:
250:
233:
232:
193:
191:
190:
185:
183:
182:
172:
171:
161:
156:
129:
128:
105:
100:
22:Forney algorithm
1661:
1660:
1656:
1655:
1654:
1652:
1651:
1650:
1631:
1630:
1616:
1614:
1610:
1603:
1596:
1563:
1560:
1552:
1548:
1540:
1531:
1523:
1519:
1512:
1508:
1504:
1487:
1426:
1425:
1416:
1383:
1378:
1342:
1341:
1335:
1319:
1276:
1275:
1202:
1201:
1195:
1157:
1146:
1097:
1092:
1091:
1073:
1067:
1016:
1015:
986:
968:
963:
962:
952:
948:
898:
897:
846:
828:
823:
822:
783:
764:
745:
735:
722:
712:
699:
689:
669:
668:
654:
622:
568:
567:
537:
536:
505:
484:
474:
459:
438:
428:
415:
410:
409:
378:
357:
347:
332:
311:
301:
288:
283:
282:
276:
272:
242:
237:
224:
219:
218:
216:
207:
174:
163:
120:
66:
65:
46:
12:
11:
5:
1659:
1657:
1649:
1648:
1643:
1633:
1632:
1629:
1628:
1622:
1594:
1577:(4): 549–557,
1559:
1558:
1546:
1529:
1517:
1505:
1503:
1500:
1499:
1498:
1493:
1486:
1483:
1482:
1481:
1470:
1467:
1464:
1461:
1457:
1454:
1451:
1448:
1445:
1442:
1439:
1436:
1433:
1414:
1409:
1408:
1397:
1390:
1386:
1381:
1376:
1373:
1370:
1367:
1364:
1361:
1358:
1355:
1352:
1349:
1334:
1331:
1318:
1315:
1298:
1295:
1292:
1289:
1286:
1283:
1272:
1271:
1260:
1257:
1254:
1251:
1248:
1245:
1242:
1239:
1236:
1233:
1230:
1227:
1224:
1221:
1218:
1215:
1212:
1209:
1191:
1184:
1183:
1170:
1167:
1164:
1160:
1153:
1149:
1144:
1140:
1135:
1130:
1127:
1124:
1120:
1116:
1113:
1110:
1107:
1103:
1100:
1069:Main article:
1066:
1063:
1062:
1061:
1047:
1042:
1039:
1034:
1030:
1026:
1022:
1019:
1013:
1008:
1005:
1000:
996:
992:
989:
983:
980:
975:
971:
945:
944:
929:
924:
921:
916:
912:
908:
904:
901:
895:
890:
887:
882:
878:
874:
871:
865:
862:
859:
854:
850:
843:
840:
835:
831:
816:
815:
804:
799:
796:
793:
790:
786:
780:
777:
774:
771:
767:
763:
760:
757:
752:
748:
742:
738:
734:
729:
725:
719:
715:
711:
706:
702:
696:
692:
688:
685:
682:
679:
676:
651:
650:
637:
632:
629:
625:
620:
617:
612:
609:
606:
603:
599:
596:
593:
590:
587:
584:
581:
578:
575:
557:
556:
544:
534:
522:
519:
512:
508:
503:
500:
497:
494:
491:
487:
481:
477:
473:
466:
462:
457:
454:
451:
448:
445:
441:
435:
431:
427:
422:
418:
407:
395:
392:
385:
381:
376:
373:
370:
367:
364:
360:
354:
350:
346:
339:
335:
330:
327:
324:
321:
318:
314:
308:
304:
300:
295:
291:
274:
249:
245:
240:
236:
231:
227:
212:
205:
195:
194:
181:
177:
170:
166:
160:
155:
152:
149:
145:
141:
138:
135:
132:
127:
123:
118:
115:
112:
109:
104:
99:
96:
93:
89:
85:
82:
79:
76:
73:
53:
52:
45:
42:
13:
10:
9:
6:
4:
3:
2:
1658:
1647:
1646:Coding theory
1644:
1642:
1639:
1638:
1636:
1626:
1623:
1609:
1602:
1601:
1595:
1592:
1588:
1584:
1580:
1576:
1572:
1571:
1566:
1562:
1561:
1556:, p. 48)
1555:
1550:
1547:
1543:
1538:
1536:
1534:
1530:
1526:
1521:
1518:
1515:
1510:
1507:
1501:
1497:
1494:
1492:
1489:
1488:
1484:
1465:
1452:
1443:
1437:
1424:
1423:
1422:
1419:
1417:
1388:
1384:
1379:
1374:
1371:
1368:
1362:
1359:
1353:
1340:
1339:
1338:
1332:
1330:
1328:
1324:
1323:
1316:
1314:
1312:
1309:according as
1296:
1293:
1290:
1287:
1284:
1281:
1258:
1255:
1252:
1249:
1246:
1243:
1240:
1237:
1231:
1228:
1225:
1222:
1219:
1213:
1210:
1207:
1200:
1199:
1198:
1194:
1189:
1168:
1165:
1162:
1158:
1151:
1147:
1142:
1138:
1133:
1128:
1125:
1122:
1118:
1114:
1108:
1101:
1090:
1089:
1088:
1086:
1082:
1078:
1072:
1064:
1040:
1037:
1032:
1028:
1020:
1006:
1003:
998:
994:
981:
978:
973:
969:
961:
960:
959:
955:
922:
919:
914:
910:
902:
888:
885:
880:
876:
863:
860:
857:
852:
848:
841:
838:
833:
829:
821:
820:
819:
802:
797:
794:
791:
788:
784:
778:
775:
772:
769:
765:
761:
758:
755:
750:
746:
740:
736:
732:
727:
723:
717:
713:
709:
704:
700:
694:
690:
686:
680:
674:
667:
666:
665:
661:
657:
630:
627:
623:
618:
607:
594:
588:
585:
579:
566:
565:
564:
562:
542:
535:
520:
517:
510:
506:
498:
495:
492:
485:
479:
475:
471:
464:
460:
452:
449:
446:
439:
433:
429:
425:
420:
416:
408:
393:
390:
383:
379:
371:
368:
365:
358:
352:
348:
344:
337:
333:
325:
322:
319:
312:
306:
302:
298:
293:
289:
281:
280:
279:
269:
265:
247:
243:
238:
234:
229:
225:
215:
211:
204:
200:
179:
175:
168:
164:
158:
153:
150:
147:
143:
139:
136:
133:
125:
121:
116:
113:
110:
102:
97:
94:
91:
87:
83:
77:
64:
63:
62:
59:
56:
51:
48:
47:
43:
41:
39:
35:
31:
27:
23:
19:
18:coding theory
1615:, retrieved
1608:the original
1599:
1574:
1568:
1549:
1544:, p. 47
1527:, p. 24
1520:
1509:
1420:
1412:
1410:
1336:
1325:
1320:
1310:
1273:
1192:
1187:
1185:
1084:
1076:
1074:
953:
946:
817:
659:
655:
652:
558:
270:
266:
213:
209:
202:
198:
196:
60:
57:
54:
49:
25:
21:
15:
1514:Forney 1965
1635:Categories
1565:Forney, G.
1554:Gill (n.d.
1502:References
1327:Gill (n.d.
1317:Derivation
947:The value
58:Syndromes
1617:April 21,
1591:0018-9448
1542:Gill n.d.
1525:Gill n.d.
1460:Γ
1447:Λ
1432:Ψ
1380:α
1372:−
1363:∏
1348:Γ
1297:λ
1285:λ
1256:λ
1250:…
1244:λ
1238:λ
1226:…
1211:λ
1166:−
1148:λ
1143:⋅
1134:ν
1119:∑
1099:Λ
1079:) is the
1038:−
1018:Λ
1004:−
988:Ω
982:−
920:−
900:Λ
886:−
870:Ω
861:−
842:−
795:−
776:−
759:⋯
602:Λ
574:Ω
543:⋯
521:⋯
486:α
440:α
394:⋯
359:α
313:α
239:α
165:λ
159:ν
144:∑
114:−
103:ν
88:∏
72:Λ
44:Procedure
30:BCH codes
1491:BCH code
1485:See also
1333:Erasures
1102:′
1075:Λ'(
1021:′
903:′
1627:'s book
208:, ...,
1589:
653:Where
214:ν
201:) are
20:, the
1611:(PDF)
1604:(PDF)
1619:2010
1587:ISSN
32:and
24:(or
1579:doi
1087:):
956:= 1
619:mod
16:In
1637::
1585:,
1575:11
1573:,
1532:^
264:.
1581::
1469:)
1466:x
1463:(
1456:)
1453:x
1450:(
1444:=
1441:)
1438:x
1435:(
1415:i
1413:j
1396:)
1389:i
1385:j
1375:x
1369:1
1366:(
1360:=
1357:)
1354:x
1351:(
1311:i
1294:,
1291:0
1288:=
1282:i
1259:.
1253:+
1247:+
1241:=
1235:)
1232:1
1229:+
1223:+
1220:1
1217:(
1214:=
1208:i
1193:i
1188:i
1169:1
1163:i
1159:x
1152:i
1139:i
1129:1
1126:=
1123:i
1115:=
1112:)
1109:x
1106:(
1085:x
1077:x
1046:)
1041:1
1033:j
1029:X
1025:(
1012:)
1007:1
999:j
995:X
991:(
979:=
974:j
970:e
954:c
949:c
928:)
923:1
915:j
911:X
907:(
894:)
889:1
881:j
877:X
873:(
864:c
858:1
853:j
849:X
839:=
834:j
830:e
803:.
798:1
792:t
789:2
785:x
779:1
773:t
770:2
766:s
762:+
756:+
751:2
747:x
741:2
737:s
733:+
728:1
724:x
718:1
714:s
710:+
705:0
701:x
695:0
691:s
687:=
684:)
681:x
678:(
675:S
662:)
660:x
658:(
656:S
636:)
631:t
628:2
624:x
616:(
611:)
608:x
605:(
598:)
595:x
592:(
589:S
586:=
583:)
580:x
577:(
518:+
511:2
507:i
502:)
499:1
496:+
493:c
490:(
480:2
476:e
472:+
465:1
461:i
456:)
453:1
450:+
447:c
444:(
434:1
430:e
426:=
421:1
417:s
391:+
384:2
380:i
375:)
372:0
369:+
366:c
363:(
353:2
349:e
345:+
338:1
334:i
329:)
326:0
323:+
320:c
317:(
307:1
303:e
299:=
294:0
290:s
275:j
273:e
248:j
244:i
235:=
230:j
226:X
210:X
206:1
203:X
199:x
180:i
176:x
169:i
154:1
151:=
148:i
140:+
137:1
134:=
131:)
126:i
122:X
117:x
111:1
108:(
98:1
95:=
92:i
84:=
81:)
78:x
75:(
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.