2845:
1659:
2840:{\displaystyle {\begin{bmatrix}b_{1}&b_{1}a_{1}&-1&-a_{1}&-a_{1}^{2}&-a_{1}^{3}&-a_{1}^{4}\\b_{2}&b_{2}a_{2}&-1&-a_{2}&-a_{2}^{2}&-a_{2}^{3}&-a_{2}^{4}\\b_{3}&b_{3}a_{3}&-1&-a_{3}&-a_{3}^{2}&-a_{3}^{3}&-a_{3}^{4}\\b_{4}&b_{4}a_{4}&-1&-a_{4}&-a_{4}^{2}&-a_{4}^{3}&-a_{4}^{4}\\b_{5}&b_{5}a_{5}&-1&-a_{5}&-a_{5}^{2}&-a_{5}^{3}&-a_{5}^{4}\\b_{6}&b_{6}a_{6}&-1&-a_{6}&-a_{6}^{2}&-a_{6}^{3}&-a_{6}^{4}\\b_{7}&b_{7}a_{7}&-1&-a_{7}&-a_{7}^{2}&-a_{7}^{3}&-a_{7}^{4}\\\end{bmatrix}}{\begin{bmatrix}e_{0}\\e_{1}\\q0\\q1\\q2\\q3\\q4\\\end{bmatrix}}={\begin{bmatrix}-b_{1}a_{1}^{2}\\-b_{2}a_{2}^{2}\\-b_{3}a_{3}^{2}\\-b_{4}a_{4}^{2}\\-b_{5}a_{5}^{2}\\-b_{6}a_{6}^{2}\\-b_{7}a_{7}^{2}\\\end{bmatrix}}}
3741:
3293:
3304:
2856:
3736:{\displaystyle {\begin{bmatrix}1&0&0&0&0&0&0\\0&1&0&0&0&0&0\\0&0&1&0&0&0&0\\0&0&0&1&0&0&0\\0&0&0&0&1&0&0\\0&0&0&0&0&1&0\\0&0&0&0&0&0&1\\\end{bmatrix}}{\begin{bmatrix}e_{0}\\e_{1}\\q0\\q1\\q2\\q3\\q4\\\end{bmatrix}}={\begin{bmatrix}4\\2\\4\\3\\3\\1\\3\\\end{bmatrix}}}
3288:{\displaystyle {\begin{bmatrix}1&0&6&0&0&0&0\\5&5&6&6&6&6&6\\3&6&6&5&3&6&5\\6&4&6&4&5&1&3\\3&5&6&3&5&6&3\\2&3&6&2&3&1&5\\2&5&6&1&6&1&6\\\end{bmatrix}}{\begin{bmatrix}e_{0}\\e_{1}\\q0\\q1\\q2\\q3\\q4\\\end{bmatrix}}={\begin{bmatrix}0\\2\\2\\2\\1\\6\\5\\\end{bmatrix}}}
1493:
4125:
1193:
1223:
960:
4034:
3852:
666:
794:
954:
879:
305:
3920:
482:
436:
351:
217:
91:
560:
1532:
518:
390:
253:
167:
127:
1488:{\displaystyle b_{i}(e_{0}+e_{1}a_{i}+e_{2}a_{i}^{2}+\cdots +e_{e-1}a_{i}^{e-1})-(q_{0}+q_{1}a_{i}+q_{2}a_{i}^{2}+\cdots +q_{q}a_{i}^{q})=-b_{i}a_{i}^{e}}
4158:
4100:
1188:{\displaystyle b_{i}(e_{0}+e_{1}a_{i}+e_{2}a_{i}^{2}+\cdots +e_{e}a_{i}^{e})-(q_{0}+q_{1}a_{i}+q_{2}a_{i}^{2}+\cdots +q_{q}a_{i}^{q})=0}
4083:
36:
3926:
3758:
4153:
1571:) = 0 to recover the original code word. If the remainder ≠ 0, then an uncorrectable error has been detected.
584:
1557:
is reduced to 0, indicating no errors. If Q()/E() has remainder = 0, then F() = Q()/E() and the code word values F(
4123:, "Error Correction for Algebraic Block Codes", published September 27, 1983, issued December 30, 1986
1605:= i-1 : {0,1,2,3,4,5,6}. The message to be systematically encoded is {1,6,3}. Using Lagrange interpolation,
722:
885:
816:
258:
4148:
4143:
3858:
441:
395:
310:
176:
50:
4112:
130:
716:) . These equations can't be solved directly, but by defining Q() as the product of E() and F():
28:
523:
1498:
resulting in a set of equations which can be solved using linear algebra, with time complexity
1501:
487:
359:
222:
136:
96:
4120:
4105:
Algebraic Codes on Lines, Planes and Curves, An
Engineering Approach – Richard E. Blahut
810:= 1, the result will lead to a set of equations that can be solved with linear algebra.
4116:
32:
4137:
1553:
is reduced by 1 and the process repeated, until the equations can be solved or
4095:
356:
The goal of the decoder is to recover the original encoding polynomial
1635:= 6, results in the code word {1,6,3,6,1,2,2}. Assume errors occur at
799:
and adding the constraint that the most significant coefficient of E(a
4101:
University at
Buffalo Lecture Notes on Coding Theory – Dr. Atri Rudra
1649:
resulting in the received code word {1,5,3,6,3,2,2}. Start off with
35:. This is a decoder algorithm that efficiently corrects errors in
3746:
Starting from the bottom of the right matrix, and the constraint
47:), code based on the Reed Solomon original view where a message
4096:
MIT Lecture Notes on
Essential Coding Theory – Dr. Madhu Sudan
1549:)/2⌋. If the equations can not be solved (due to redundancy),
4108:
Welch
Berlekamp Decoding of Reed–Solomon Codes – L. R. Welch
1537:
The algorithm begins assuming the maximum number of errors
484:
with possible errors. It also computes an error polynomial
4074:= 4) = 1 to produce corrected code word {1,6,3,6,1,2,2}.
4130:– The patent by Lloyd R. Welch and Elewyn R. Berlekamp
4029:{\displaystyle F(a_{i})=Q(a_{i})/E(a_{i})=3x^{2}+2x+1}
3677:
3584:
3313:
3229:
3136:
2865:
2606:
2513:
1668:
3929:
3861:
3761:
3307:
2859:
1662:
1504:
1226:
963:
888:
819:
725:
587:
526:
490:
444:
398:
362:
313:
261:
225:
179:
139:
99:
53:
4028:
3914:
3847:{\displaystyle Q(a_{i})=3x^{4}+1x^{3}+3x^{2}+3x+4}
3846:
3735:
3287:
2839:
1526:
1487:
1187:
948:
873:
788:
660:
562:corresponding to errors in the received codeword.
554:
512:
476:
430:
384:
345:
299:
247:
211:
161:
121:
85:
1217:is constrained to be 1, the equations become:
661:{\displaystyle b_{i}E(a_{i})=E(a_{i})F(a_{i})}
8:
1564:) are calculated for the locations where E(
4005:
3986:
3971:
3962:
3940:
3928:
3891:
3872:
3860:
3823:
3807:
3791:
3772:
3760:
3672:
3605:
3591:
3579:
3308:
3306:
3224:
3157:
3143:
3131:
2860:
2858:
2823:
2818:
2808:
2791:
2786:
2776:
2759:
2754:
2744:
2727:
2722:
2712:
2695:
2690:
2680:
2663:
2658:
2648:
2631:
2626:
2616:
2601:
2534:
2520:
2508:
2494:
2489:
2474:
2469:
2454:
2449:
2434:
2411:
2401:
2389:
2375:
2370:
2355:
2350:
2335:
2330:
2315:
2292:
2282:
2270:
2256:
2251:
2236:
2231:
2216:
2211:
2196:
2173:
2163:
2151:
2137:
2132:
2117:
2112:
2097:
2092:
2077:
2054:
2044:
2032:
2018:
2013:
1998:
1993:
1978:
1973:
1958:
1935:
1925:
1913:
1899:
1894:
1879:
1874:
1859:
1854:
1839:
1816:
1806:
1794:
1780:
1775:
1760:
1755:
1740:
1735:
1720:
1697:
1687:
1675:
1663:
1661:
1515:
1503:
1479:
1474:
1464:
1445:
1440:
1430:
1411:
1406:
1396:
1383:
1373:
1360:
1335:
1330:
1314:
1295:
1290:
1280:
1267:
1257:
1244:
1231:
1225:
1170:
1165:
1155:
1136:
1131:
1121:
1108:
1098:
1085:
1066:
1061:
1051:
1032:
1027:
1017:
1004:
994:
981:
968:
962:
931:
909:
893:
887:
862:
840:
824:
818:
789:{\displaystyle Q(a_{i})=E(a_{i})F(a_{i})}
777:
758:
736:
724:
649:
630:
608:
592:
586:
537:
525:
501:
489:
468:
449:
443:
422:
403:
397:
373:
361:
337:
318:
312:
291:
266:
260:
236:
224:
203:
184:
178:
150:
138:
110:
98:
77:
58:
52:
949:{\displaystyle b_{i}E(a_{i})-Q(a_{i})=0}
93:is used as coefficients of a polynomial
874:{\displaystyle b_{i}E(a_{i})=Q(a_{i})}
300:{\displaystyle a_{k+1},\cdots ,a_{n}}
7:
3915:{\displaystyle E(a_{i})=1x^{2}+2x+4}
1653:= 2 and solve the linear equations:
574:= number of errors, the key set of
477:{\displaystyle b_{1},\cdots ,b_{n}}
431:{\displaystyle a_{1},\cdots ,a_{n}}
346:{\displaystyle c_{1},\cdots ,c_{n}}
212:{\displaystyle a_{1},\cdots ,a_{k}}
86:{\displaystyle m_{1},\cdots ,m_{k}}
14:
4159:Error detection and correction
3992:
3979:
3968:
3955:
3946:
3933:
3878:
3865:
3778:
3765:
1613:= 3 x + 2 x + 1, and applying
1521:
1508:
1451:
1353:
1347:
1237:
1176:
1078:
1072:
974:
937:
924:
915:
902:
868:
855:
846:
833:
783:
770:
764:
751:
742:
729:
655:
642:
636:
623:
614:
601:
543:
530:
507:
494:
379:
366:
307:to create an encoded codeword
242:
229:
156:
143:
116:
103:
1:
4084:Reed–Solomon error correction
133:to generate the polynomial
4175:
555:{\displaystyle E(a_{i})=0}
16:Error-correcting algorithm
392:, using the known inputs
25:Welch–Berlekamp algorithm
21:Berlekamp–Welch algorithm
1527:{\displaystyle O(n^{3})}
513:{\displaystyle E(a_{i})}
385:{\displaystyle F(a_{i})}
248:{\displaystyle F(a_{i})}
162:{\displaystyle F(a_{i})}
122:{\displaystyle F(a_{i})}
4030:
3916:
3848:
3737:
3289:
2841:
1598:= 3 and input values:
1528:
1489:
1189:
950:
875:
790:
702:non error cases where
662:
556:
514:
478:
438:and received codeword
432:
386:
347:
301:
249:
213:
163:
131:Lagrange interpolation
123:
87:
4031:
3917:
3849:
3738:
3290:
2842:
1529:
1490:
1190:
951:
876:
791:
663:
557:
515:
479:
433:
387:
348:
302:
250:
214:
164:
124:
88:
4036:with remainder = 0.
3927:
3859:
3759:
3305:
2857:
1660:
1502:
1224:
961:
886:
817:
723:
694:) ≠ 0 for the
585:
524:
488:
442:
396:
360:
311:
259:
223:
177:
137:
97:
51:
23:, also known as the
4121:Berlekamp, Elwyn R.
2828:
2796:
2764:
2732:
2700:
2668:
2636:
2499:
2479:
2459:
2380:
2360:
2340:
2261:
2241:
2221:
2142:
2122:
2102:
2023:
2003:
1983:
1904:
1884:
1864:
1785:
1765:
1745:
1484:
1450:
1416:
1346:
1300:
1175:
1141:
1071:
1037:
4154:Information theory
4026:
3912:
3844:
3733:
3727:
3663:
3573:
3285:
3279:
3215:
3125:
2837:
2831:
2814:
2782:
2750:
2718:
2686:
2654:
2622:
2592:
2502:
2485:
2465:
2445:
2366:
2346:
2326:
2247:
2227:
2207:
2128:
2108:
2088:
2009:
1989:
1969:
1890:
1870:
1850:
1771:
1751:
1731:
1579:Consider RS(7,3) (
1524:
1485:
1470:
1436:
1402:
1326:
1286:
1185:
1161:
1127:
1057:
1023:
946:
871:
786:
658:
552:
510:
474:
428:
382:
343:
297:
245:
209:
159:
119:
83:
37:Reed–Solomon codes
29:Elwyn R. Berlekamp
566:The key equations
4166:
4129:
4128:
4124:
4060:= 4 Calculate F(
4035:
4033:
4032:
4027:
4010:
4009:
3991:
3990:
3975:
3967:
3966:
3945:
3944:
3921:
3919:
3918:
3913:
3896:
3895:
3877:
3876:
3853:
3851:
3850:
3845:
3828:
3827:
3812:
3811:
3796:
3795:
3777:
3776:
3742:
3740:
3739:
3734:
3732:
3731:
3668:
3667:
3610:
3609:
3596:
3595:
3578:
3577:
3294:
3292:
3291:
3286:
3284:
3283:
3220:
3219:
3162:
3161:
3148:
3147:
3130:
3129:
2846:
2844:
2843:
2838:
2836:
2835:
2827:
2822:
2813:
2812:
2795:
2790:
2781:
2780:
2763:
2758:
2749:
2748:
2731:
2726:
2717:
2716:
2699:
2694:
2685:
2684:
2667:
2662:
2653:
2652:
2635:
2630:
2621:
2620:
2597:
2596:
2539:
2538:
2525:
2524:
2507:
2506:
2498:
2493:
2478:
2473:
2458:
2453:
2439:
2438:
2416:
2415:
2406:
2405:
2394:
2393:
2379:
2374:
2359:
2354:
2339:
2334:
2320:
2319:
2297:
2296:
2287:
2286:
2275:
2274:
2260:
2255:
2240:
2235:
2220:
2215:
2201:
2200:
2178:
2177:
2168:
2167:
2156:
2155:
2141:
2136:
2121:
2116:
2101:
2096:
2082:
2081:
2059:
2058:
2049:
2048:
2037:
2036:
2022:
2017:
2002:
1997:
1982:
1977:
1963:
1962:
1940:
1939:
1930:
1929:
1918:
1917:
1903:
1898:
1883:
1878:
1863:
1858:
1844:
1843:
1821:
1820:
1811:
1810:
1799:
1798:
1784:
1779:
1764:
1759:
1744:
1739:
1725:
1724:
1702:
1701:
1692:
1691:
1680:
1679:
1593:
1587:= 3) defined in
1533:
1531:
1530:
1525:
1520:
1519:
1494:
1492:
1491:
1486:
1483:
1478:
1469:
1468:
1449:
1444:
1435:
1434:
1415:
1410:
1401:
1400:
1388:
1387:
1378:
1377:
1365:
1364:
1345:
1334:
1325:
1324:
1299:
1294:
1285:
1284:
1272:
1271:
1262:
1261:
1249:
1248:
1236:
1235:
1194:
1192:
1191:
1186:
1174:
1169:
1160:
1159:
1140:
1135:
1126:
1125:
1113:
1112:
1103:
1102:
1090:
1089:
1070:
1065:
1056:
1055:
1036:
1031:
1022:
1021:
1009:
1008:
999:
998:
986:
985:
973:
972:
955:
953:
952:
947:
936:
935:
914:
913:
898:
897:
880:
878:
877:
872:
867:
866:
845:
844:
829:
828:
795:
793:
792:
787:
782:
781:
763:
762:
741:
740:
667:
665:
664:
659:
654:
653:
635:
634:
613:
612:
597:
596:
561:
559:
558:
553:
542:
541:
519:
517:
516:
511:
506:
505:
483:
481:
480:
475:
473:
472:
454:
453:
437:
435:
434:
429:
427:
426:
408:
407:
391:
389:
388:
383:
378:
377:
352:
350:
349:
344:
342:
341:
323:
322:
306:
304:
303:
298:
296:
295:
277:
276:
254:
252:
251:
246:
241:
240:
218:
216:
215:
210:
208:
207:
189:
188:
168:
166:
165:
160:
155:
154:
128:
126:
125:
120:
115:
114:
92:
90:
89:
84:
82:
81:
63:
62:
4174:
4173:
4169:
4168:
4167:
4165:
4164:
4163:
4134:
4133:
4126:
4119: &
4117:Welch, Lloyd R.
4111:
4092:
4080:
4072:
4067:= 1) = 6 and F(
4065:
4058:
4051:
4044:
4001:
3982:
3958:
3936:
3925:
3924:
3887:
3868:
3857:
3856:
3819:
3803:
3787:
3768:
3757:
3756:
3751:
3726:
3725:
3719:
3718:
3712:
3711:
3705:
3704:
3698:
3697:
3691:
3690:
3684:
3683:
3673:
3662:
3661:
3652:
3651:
3642:
3641:
3632:
3631:
3622:
3621:
3612:
3611:
3601:
3598:
3597:
3587:
3580:
3572:
3571:
3566:
3561:
3556:
3551:
3546:
3541:
3535:
3534:
3529:
3524:
3519:
3514:
3509:
3504:
3498:
3497:
3492:
3487:
3482:
3477:
3472:
3467:
3461:
3460:
3455:
3450:
3445:
3440:
3435:
3430:
3424:
3423:
3418:
3413:
3408:
3403:
3398:
3393:
3387:
3386:
3381:
3376:
3371:
3366:
3361:
3356:
3350:
3349:
3344:
3339:
3334:
3329:
3324:
3319:
3309:
3303:
3302:
3298:
3278:
3277:
3271:
3270:
3264:
3263:
3257:
3256:
3250:
3249:
3243:
3242:
3236:
3235:
3225:
3214:
3213:
3204:
3203:
3194:
3193:
3184:
3183:
3174:
3173:
3164:
3163:
3153:
3150:
3149:
3139:
3132:
3124:
3123:
3118:
3113:
3108:
3103:
3098:
3093:
3087:
3086:
3081:
3076:
3071:
3066:
3061:
3056:
3050:
3049:
3044:
3039:
3034:
3029:
3024:
3019:
3013:
3012:
3007:
3002:
2997:
2992:
2987:
2982:
2976:
2975:
2970:
2965:
2960:
2955:
2950:
2945:
2939:
2938:
2933:
2928:
2923:
2918:
2913:
2908:
2902:
2901:
2896:
2891:
2886:
2881:
2876:
2871:
2861:
2855:
2854:
2850:
2830:
2829:
2804:
2798:
2797:
2772:
2766:
2765:
2740:
2734:
2733:
2708:
2702:
2701:
2676:
2670:
2669:
2644:
2638:
2637:
2612:
2602:
2591:
2590:
2581:
2580:
2571:
2570:
2561:
2560:
2551:
2550:
2541:
2540:
2530:
2527:
2526:
2516:
2509:
2501:
2500:
2480:
2460:
2440:
2430:
2425:
2417:
2407:
2397:
2395:
2385:
2382:
2381:
2361:
2341:
2321:
2311:
2306:
2298:
2288:
2278:
2276:
2266:
2263:
2262:
2242:
2222:
2202:
2192:
2187:
2179:
2169:
2159:
2157:
2147:
2144:
2143:
2123:
2103:
2083:
2073:
2068:
2060:
2050:
2040:
2038:
2028:
2025:
2024:
2004:
1984:
1964:
1954:
1949:
1941:
1931:
1921:
1919:
1909:
1906:
1905:
1885:
1865:
1845:
1835:
1830:
1822:
1812:
1802:
1800:
1790:
1787:
1786:
1766:
1746:
1726:
1716:
1711:
1703:
1693:
1683:
1681:
1671:
1664:
1658:
1657:
1647:
1640:
1633:
1626:
1618:
1610:
1603:
1588:
1577:
1569:
1562:
1511:
1500:
1499:
1460:
1426:
1392:
1379:
1369:
1356:
1310:
1276:
1263:
1253:
1240:
1227:
1222:
1221:
1215:
1151:
1117:
1104:
1094:
1081:
1047:
1013:
1000:
990:
977:
964:
959:
958:
927:
905:
889:
884:
883:
858:
836:
820:
815:
814:
808:
802:
773:
754:
732:
721:
720:
714:
707:
693:
689:
685:
676:
645:
626:
604:
588:
583:
582:
568:
533:
522:
521:
497:
486:
485:
464:
445:
440:
439:
418:
399:
394:
393:
369:
358:
357:
333:
314:
309:
308:
287:
262:
257:
256:
232:
221:
220:
199:
180:
175:
174:
169:of degree <
146:
135:
134:
106:
95:
94:
73:
54:
49:
48:
27:, is named for
17:
12:
11:
5:
4172:
4170:
4162:
4161:
4156:
4151:
4146:
4136:
4135:
4132:
4131:
4109:
4106:
4103:
4098:
4091:
4090:External links
4088:
4087:
4086:
4079:
4076:
4070:
4063:
4056:
4049:
4042:
4025:
4022:
4019:
4016:
4013:
4008:
4004:
4000:
3997:
3994:
3989:
3985:
3981:
3978:
3974:
3970:
3965:
3961:
3957:
3954:
3951:
3948:
3943:
3939:
3935:
3932:
3911:
3908:
3905:
3902:
3899:
3894:
3890:
3886:
3883:
3880:
3875:
3871:
3867:
3864:
3843:
3840:
3837:
3834:
3831:
3826:
3822:
3818:
3815:
3810:
3806:
3802:
3799:
3794:
3790:
3786:
3783:
3780:
3775:
3771:
3767:
3764:
3749:
3744:
3743:
3730:
3724:
3721:
3720:
3717:
3714:
3713:
3710:
3707:
3706:
3703:
3700:
3699:
3696:
3693:
3692:
3689:
3686:
3685:
3682:
3679:
3678:
3676:
3671:
3666:
3660:
3657:
3654:
3653:
3650:
3647:
3644:
3643:
3640:
3637:
3634:
3633:
3630:
3627:
3624:
3623:
3620:
3617:
3614:
3613:
3608:
3604:
3600:
3599:
3594:
3590:
3586:
3585:
3583:
3576:
3570:
3567:
3565:
3562:
3560:
3557:
3555:
3552:
3550:
3547:
3545:
3542:
3540:
3537:
3536:
3533:
3530:
3528:
3525:
3523:
3520:
3518:
3515:
3513:
3510:
3508:
3505:
3503:
3500:
3499:
3496:
3493:
3491:
3488:
3486:
3483:
3481:
3478:
3476:
3473:
3471:
3468:
3466:
3463:
3462:
3459:
3456:
3454:
3451:
3449:
3446:
3444:
3441:
3439:
3436:
3434:
3431:
3429:
3426:
3425:
3422:
3419:
3417:
3414:
3412:
3409:
3407:
3404:
3402:
3399:
3397:
3394:
3392:
3389:
3388:
3385:
3382:
3380:
3377:
3375:
3372:
3370:
3367:
3365:
3362:
3360:
3357:
3355:
3352:
3351:
3348:
3345:
3343:
3340:
3338:
3335:
3333:
3330:
3328:
3325:
3323:
3320:
3318:
3315:
3314:
3312:
3296:
3295:
3282:
3276:
3273:
3272:
3269:
3266:
3265:
3262:
3259:
3258:
3255:
3252:
3251:
3248:
3245:
3244:
3241:
3238:
3237:
3234:
3231:
3230:
3228:
3223:
3218:
3212:
3209:
3206:
3205:
3202:
3199:
3196:
3195:
3192:
3189:
3186:
3185:
3182:
3179:
3176:
3175:
3172:
3169:
3166:
3165:
3160:
3156:
3152:
3151:
3146:
3142:
3138:
3137:
3135:
3128:
3122:
3119:
3117:
3114:
3112:
3109:
3107:
3104:
3102:
3099:
3097:
3094:
3092:
3089:
3088:
3085:
3082:
3080:
3077:
3075:
3072:
3070:
3067:
3065:
3062:
3060:
3057:
3055:
3052:
3051:
3048:
3045:
3043:
3040:
3038:
3035:
3033:
3030:
3028:
3025:
3023:
3020:
3018:
3015:
3014:
3011:
3008:
3006:
3003:
3001:
2998:
2996:
2993:
2991:
2988:
2986:
2983:
2981:
2978:
2977:
2974:
2971:
2969:
2966:
2964:
2961:
2959:
2956:
2954:
2951:
2949:
2946:
2944:
2941:
2940:
2937:
2934:
2932:
2929:
2927:
2924:
2922:
2919:
2917:
2914:
2912:
2909:
2907:
2904:
2903:
2900:
2897:
2895:
2892:
2890:
2887:
2885:
2882:
2880:
2877:
2875:
2872:
2870:
2867:
2866:
2864:
2848:
2847:
2834:
2826:
2821:
2817:
2811:
2807:
2803:
2800:
2799:
2794:
2789:
2785:
2779:
2775:
2771:
2768:
2767:
2762:
2757:
2753:
2747:
2743:
2739:
2736:
2735:
2730:
2725:
2721:
2715:
2711:
2707:
2704:
2703:
2698:
2693:
2689:
2683:
2679:
2675:
2672:
2671:
2666:
2661:
2657:
2651:
2647:
2643:
2640:
2639:
2634:
2629:
2625:
2619:
2615:
2611:
2608:
2607:
2605:
2600:
2595:
2589:
2586:
2583:
2582:
2579:
2576:
2573:
2572:
2569:
2566:
2563:
2562:
2559:
2556:
2553:
2552:
2549:
2546:
2543:
2542:
2537:
2533:
2529:
2528:
2523:
2519:
2515:
2514:
2512:
2505:
2497:
2492:
2488:
2484:
2481:
2477:
2472:
2468:
2464:
2461:
2457:
2452:
2448:
2444:
2441:
2437:
2433:
2429:
2426:
2424:
2421:
2418:
2414:
2410:
2404:
2400:
2396:
2392:
2388:
2384:
2383:
2378:
2373:
2369:
2365:
2362:
2358:
2353:
2349:
2345:
2342:
2338:
2333:
2329:
2325:
2322:
2318:
2314:
2310:
2307:
2305:
2302:
2299:
2295:
2291:
2285:
2281:
2277:
2273:
2269:
2265:
2264:
2259:
2254:
2250:
2246:
2243:
2239:
2234:
2230:
2226:
2223:
2219:
2214:
2210:
2206:
2203:
2199:
2195:
2191:
2188:
2186:
2183:
2180:
2176:
2172:
2166:
2162:
2158:
2154:
2150:
2146:
2145:
2140:
2135:
2131:
2127:
2124:
2120:
2115:
2111:
2107:
2104:
2100:
2095:
2091:
2087:
2084:
2080:
2076:
2072:
2069:
2067:
2064:
2061:
2057:
2053:
2047:
2043:
2039:
2035:
2031:
2027:
2026:
2021:
2016:
2012:
2008:
2005:
2001:
1996:
1992:
1988:
1985:
1981:
1976:
1972:
1968:
1965:
1961:
1957:
1953:
1950:
1948:
1945:
1942:
1938:
1934:
1928:
1924:
1920:
1916:
1912:
1908:
1907:
1902:
1897:
1893:
1889:
1886:
1882:
1877:
1873:
1869:
1866:
1862:
1857:
1853:
1849:
1846:
1842:
1838:
1834:
1831:
1829:
1826:
1823:
1819:
1815:
1809:
1805:
1801:
1797:
1793:
1789:
1788:
1783:
1778:
1774:
1770:
1767:
1763:
1758:
1754:
1750:
1747:
1743:
1738:
1734:
1730:
1727:
1723:
1719:
1715:
1712:
1710:
1707:
1704:
1700:
1696:
1690:
1686:
1682:
1678:
1674:
1670:
1669:
1667:
1645:
1638:
1631:
1624:
1616:
1608:
1601:
1576:
1573:
1567:
1560:
1523:
1518:
1514:
1510:
1507:
1496:
1495:
1482:
1477:
1473:
1467:
1463:
1459:
1456:
1453:
1448:
1443:
1439:
1433:
1429:
1425:
1422:
1419:
1414:
1409:
1405:
1399:
1395:
1391:
1386:
1382:
1376:
1372:
1368:
1363:
1359:
1355:
1352:
1349:
1344:
1341:
1338:
1333:
1329:
1323:
1320:
1317:
1313:
1309:
1306:
1303:
1298:
1293:
1289:
1283:
1279:
1275:
1270:
1266:
1260:
1256:
1252:
1247:
1243:
1239:
1234:
1230:
1213:
1196:
1195:
1184:
1181:
1178:
1173:
1168:
1164:
1158:
1154:
1150:
1147:
1144:
1139:
1134:
1130:
1124:
1120:
1116:
1111:
1107:
1101:
1097:
1093:
1088:
1084:
1080:
1077:
1074:
1069:
1064:
1060:
1054:
1050:
1046:
1043:
1040:
1035:
1030:
1026:
1020:
1016:
1012:
1007:
1003:
997:
993:
989:
984:
980:
976:
971:
967:
956:
945:
942:
939:
934:
930:
926:
923:
920:
917:
912:
908:
904:
901:
896:
892:
881:
870:
865:
861:
857:
854:
851:
848:
843:
839:
835:
832:
827:
823:
806:
800:
797:
796:
785:
780:
776:
772:
769:
766:
761:
757:
753:
750:
747:
744:
739:
735:
731:
728:
712:
705:
691:
687:
683:
678:) = 0 for the
674:
669:
668:
657:
652:
648:
644:
641:
638:
633:
629:
625:
622:
619:
616:
611:
607:
603:
600:
595:
591:
567:
564:
551:
548:
545:
540:
536:
532:
529:
509:
504:
500:
496:
493:
471:
467:
463:
460:
457:
452:
448:
425:
421:
417:
414:
411:
406:
402:
381:
376:
372:
368:
365:
340:
336:
332:
329:
326:
321:
317:
294:
290:
286:
283:
280:
275:
272:
269:
265:
255:is applied to
244:
239:
235:
231:
228:
206:
202:
198:
195:
192:
187:
183:
158:
153:
149:
145:
142:
118:
113:
109:
105:
102:
80:
76:
72:
69:
66:
61:
57:
33:Lloyd R. Welch
15:
13:
10:
9:
6:
4:
3:
2:
4171:
4160:
4157:
4155:
4152:
4150:
4149:Coding theory
4147:
4145:
4144:Finite fields
4142:
4141:
4139:
4122:
4118:
4114:
4110:
4107:
4104:
4102:
4099:
4097:
4094:
4093:
4089:
4085:
4082:
4081:
4077:
4075:
4073:
4066:
4059:
4052:
4045:
4037:
4023:
4020:
4017:
4014:
4011:
4006:
4002:
3998:
3995:
3987:
3983:
3976:
3972:
3963:
3959:
3952:
3949:
3941:
3937:
3930:
3922:
3909:
3906:
3903:
3900:
3897:
3892:
3888:
3884:
3881:
3873:
3869:
3862:
3854:
3841:
3838:
3835:
3832:
3829:
3824:
3820:
3816:
3813:
3808:
3804:
3800:
3797:
3792:
3788:
3784:
3781:
3773:
3769:
3762:
3754:
3752:
3728:
3722:
3715:
3708:
3701:
3694:
3687:
3680:
3674:
3669:
3664:
3658:
3655:
3648:
3645:
3638:
3635:
3628:
3625:
3618:
3615:
3606:
3602:
3592:
3588:
3581:
3574:
3568:
3563:
3558:
3553:
3548:
3543:
3538:
3531:
3526:
3521:
3516:
3511:
3506:
3501:
3494:
3489:
3484:
3479:
3474:
3469:
3464:
3457:
3452:
3447:
3442:
3437:
3432:
3427:
3420:
3415:
3410:
3405:
3400:
3395:
3390:
3383:
3378:
3373:
3368:
3363:
3358:
3353:
3346:
3341:
3336:
3331:
3326:
3321:
3316:
3310:
3301:
3300:
3299:
3280:
3274:
3267:
3260:
3253:
3246:
3239:
3232:
3226:
3221:
3216:
3210:
3207:
3200:
3197:
3190:
3187:
3180:
3177:
3170:
3167:
3158:
3154:
3144:
3140:
3133:
3126:
3120:
3115:
3110:
3105:
3100:
3095:
3090:
3083:
3078:
3073:
3068:
3063:
3058:
3053:
3046:
3041:
3036:
3031:
3026:
3021:
3016:
3009:
3004:
2999:
2994:
2989:
2984:
2979:
2972:
2967:
2962:
2957:
2952:
2947:
2942:
2935:
2930:
2925:
2920:
2915:
2910:
2905:
2898:
2893:
2888:
2883:
2878:
2873:
2868:
2862:
2853:
2852:
2851:
2832:
2824:
2819:
2815:
2809:
2805:
2801:
2792:
2787:
2783:
2777:
2773:
2769:
2760:
2755:
2751:
2745:
2741:
2737:
2728:
2723:
2719:
2713:
2709:
2705:
2696:
2691:
2687:
2681:
2677:
2673:
2664:
2659:
2655:
2649:
2645:
2641:
2632:
2627:
2623:
2617:
2613:
2609:
2603:
2598:
2593:
2587:
2584:
2577:
2574:
2567:
2564:
2557:
2554:
2547:
2544:
2535:
2531:
2521:
2517:
2510:
2503:
2495:
2490:
2486:
2482:
2475:
2470:
2466:
2462:
2455:
2450:
2446:
2442:
2435:
2431:
2427:
2422:
2419:
2412:
2408:
2402:
2398:
2390:
2386:
2376:
2371:
2367:
2363:
2356:
2351:
2347:
2343:
2336:
2331:
2327:
2323:
2316:
2312:
2308:
2303:
2300:
2293:
2289:
2283:
2279:
2271:
2267:
2257:
2252:
2248:
2244:
2237:
2232:
2228:
2224:
2217:
2212:
2208:
2204:
2197:
2193:
2189:
2184:
2181:
2174:
2170:
2164:
2160:
2152:
2148:
2138:
2133:
2129:
2125:
2118:
2113:
2109:
2105:
2098:
2093:
2089:
2085:
2078:
2074:
2070:
2065:
2062:
2055:
2051:
2045:
2041:
2033:
2029:
2019:
2014:
2010:
2006:
1999:
1994:
1990:
1986:
1979:
1974:
1970:
1966:
1959:
1955:
1951:
1946:
1943:
1936:
1932:
1926:
1922:
1914:
1910:
1900:
1895:
1891:
1887:
1880:
1875:
1871:
1867:
1860:
1855:
1851:
1847:
1840:
1836:
1832:
1827:
1824:
1817:
1813:
1807:
1803:
1795:
1791:
1781:
1776:
1772:
1768:
1761:
1756:
1752:
1748:
1741:
1736:
1732:
1728:
1721:
1717:
1713:
1708:
1705:
1698:
1694:
1688:
1684:
1676:
1672:
1665:
1656:
1655:
1654:
1652:
1648:
1641:
1634:
1627:
1620:
1612:
1604:
1597:
1591:
1586:
1582:
1574:
1572:
1570:
1563:
1556:
1552:
1548:
1544:
1540:
1535:
1516:
1512:
1505:
1480:
1475:
1471:
1465:
1461:
1457:
1454:
1446:
1441:
1437:
1431:
1427:
1423:
1420:
1417:
1412:
1407:
1403:
1397:
1393:
1389:
1384:
1380:
1374:
1370:
1366:
1361:
1357:
1350:
1342:
1339:
1336:
1331:
1327:
1321:
1318:
1315:
1311:
1307:
1304:
1301:
1296:
1291:
1287:
1281:
1277:
1273:
1268:
1264:
1258:
1254:
1250:
1245:
1241:
1232:
1228:
1220:
1219:
1218:
1216:
1209:
1205:
1201:
1182:
1179:
1171:
1166:
1162:
1156:
1152:
1148:
1145:
1142:
1137:
1132:
1128:
1122:
1118:
1114:
1109:
1105:
1099:
1095:
1091:
1086:
1082:
1075:
1067:
1062:
1058:
1052:
1048:
1044:
1041:
1038:
1033:
1028:
1024:
1018:
1014:
1010:
1005:
1001:
995:
991:
987:
982:
978:
969:
965:
957:
943:
940:
932:
928:
921:
918:
910:
906:
899:
894:
890:
882:
863:
859:
852:
849:
841:
837:
830:
825:
821:
813:
812:
811:
809:
778:
774:
767:
759:
755:
748:
745:
737:
733:
726:
719:
718:
717:
715:
708:
701:
697:
681:
677:
650:
646:
639:
631:
627:
620:
617:
609:
605:
598:
593:
589:
581:
580:
579:
578:equations is
577:
573:
565:
563:
549:
546:
538:
534:
527:
502:
498:
491:
469:
465:
461:
458:
455:
450:
446:
423:
419:
415:
412:
409:
404:
400:
374:
370:
363:
354:
338:
334:
330:
327:
324:
319:
315:
292:
288:
284:
281:
278:
273:
270:
267:
263:
237:
233:
226:
204:
200:
196:
193:
190:
185:
181:
172:
151:
147:
140:
132:
129:or used with
111:
107:
100:
78:
74:
70:
67:
64:
59:
55:
46:
42:
38:
34:
30:
26:
22:
4113:US 4,633,470
4068:
4061:
4054:
4047:
4040:
4038:
3923:
3855:
3755:
3747:
3745:
3297:
2849:
1650:
1643:
1636:
1629:
1622:
1614:
1606:
1599:
1595:
1589:
1584:
1580:
1578:
1565:
1558:
1554:
1550:
1546:
1542:
1538:
1536:
1497:
1211:
1207:
1203:
1199:
1197:
804:
798:
710:
703:
699:
695:
682:cases when b
679:
672:
670:
575:
571:
569:
355:
170:
44:
40:
24:
20:
18:
1210:- 1. Since
686:≠ F(a
173:for inputs
4138:Categories
690:), and E(a
39:for an RS(
4046:) = 0 at
2802:−
2770:−
2738:−
2706:−
2674:−
2642:−
2610:−
2483:−
2463:−
2443:−
2428:−
2420:−
2364:−
2344:−
2324:−
2309:−
2301:−
2245:−
2225:−
2205:−
2190:−
2182:−
2126:−
2106:−
2086:−
2071:−
2063:−
2007:−
1987:−
1967:−
1952:−
1944:−
1888:−
1868:−
1848:−
1833:−
1825:−
1769:−
1749:−
1729:−
1714:−
1706:−
1458:−
1421:⋯
1351:−
1340:−
1319:−
1305:⋯
1146:⋯
1076:−
1042:⋯
919:−
570:Defining
459:⋯
413:⋯
328:⋯
282:⋯
219:and then
194:⋯
68:⋯
4078:See also
4053:= 1 and
671:Where E(
1628:= 3 to
1575:Example
4127:
4115:,
1198:where
520:where
3753:= 1:
1594:with
1583:= 7,
1642:and
1621:for
1541:= ⌊(
803:) =
709:= F(
31:and
19:The
1615:F(a
1607:F(a
1592:(7)
4140::
4039:E(
1590:GF
1534:.
1206:-
1202:=
698:-
353:.
43:,
4071:5
4069:a
4064:2
4062:a
4057:5
4055:a
4050:2
4048:a
4043:i
4041:a
4024:1
4021:+
4018:x
4015:2
4012:+
4007:2
4003:x
3999:3
3996:=
3993:)
3988:i
3984:a
3980:(
3977:E
3973:/
3969:)
3964:i
3960:a
3956:(
3953:Q
3950:=
3947:)
3942:i
3938:a
3934:(
3931:F
3910:4
3907:+
3904:x
3901:2
3898:+
3893:2
3889:x
3885:1
3882:=
3879:)
3874:i
3870:a
3866:(
3863:E
3842:4
3839:+
3836:x
3833:3
3830:+
3825:2
3821:x
3817:3
3814:+
3809:3
3805:x
3801:1
3798:+
3793:4
3789:x
3785:3
3782:=
3779:)
3774:i
3770:a
3766:(
3763:Q
3750:2
3748:e
3729:]
3723:3
3716:1
3709:3
3702:3
3695:4
3688:2
3681:4
3675:[
3670:=
3665:]
3659:4
3656:q
3649:3
3646:q
3639:2
3636:q
3629:1
3626:q
3619:0
3616:q
3607:1
3603:e
3593:0
3589:e
3582:[
3575:]
3569:1
3564:0
3559:0
3554:0
3549:0
3544:0
3539:0
3532:0
3527:1
3522:0
3517:0
3512:0
3507:0
3502:0
3495:0
3490:0
3485:1
3480:0
3475:0
3470:0
3465:0
3458:0
3453:0
3448:0
3443:1
3438:0
3433:0
3428:0
3421:0
3416:0
3411:0
3406:0
3401:1
3396:0
3391:0
3384:0
3379:0
3374:0
3369:0
3364:0
3359:1
3354:0
3347:0
3342:0
3337:0
3332:0
3327:0
3322:0
3317:1
3311:[
3281:]
3275:5
3268:6
3261:1
3254:2
3247:2
3240:2
3233:0
3227:[
3222:=
3217:]
3211:4
3208:q
3201:3
3198:q
3191:2
3188:q
3181:1
3178:q
3171:0
3168:q
3159:1
3155:e
3145:0
3141:e
3134:[
3127:]
3121:6
3116:1
3111:6
3106:1
3101:6
3096:5
3091:2
3084:5
3079:1
3074:3
3069:2
3064:6
3059:3
3054:2
3047:3
3042:6
3037:5
3032:3
3027:6
3022:5
3017:3
3010:3
3005:1
3000:5
2995:4
2990:6
2985:4
2980:6
2973:5
2968:6
2963:3
2958:5
2953:6
2948:6
2943:3
2936:6
2931:6
2926:6
2921:6
2916:6
2911:5
2906:5
2899:0
2894:0
2889:0
2884:0
2879:6
2874:0
2869:1
2863:[
2833:]
2825:2
2820:7
2816:a
2810:7
2806:b
2793:2
2788:6
2784:a
2778:6
2774:b
2761:2
2756:5
2752:a
2746:5
2742:b
2729:2
2724:4
2720:a
2714:4
2710:b
2697:2
2692:3
2688:a
2682:3
2678:b
2665:2
2660:2
2656:a
2650:2
2646:b
2633:2
2628:1
2624:a
2618:1
2614:b
2604:[
2599:=
2594:]
2588:4
2585:q
2578:3
2575:q
2568:2
2565:q
2558:1
2555:q
2548:0
2545:q
2536:1
2532:e
2522:0
2518:e
2511:[
2504:]
2496:4
2491:7
2487:a
2476:3
2471:7
2467:a
2456:2
2451:7
2447:a
2436:7
2432:a
2423:1
2413:7
2409:a
2403:7
2399:b
2391:7
2387:b
2377:4
2372:6
2368:a
2357:3
2352:6
2348:a
2337:2
2332:6
2328:a
2317:6
2313:a
2304:1
2294:6
2290:a
2284:6
2280:b
2272:6
2268:b
2258:4
2253:5
2249:a
2238:3
2233:5
2229:a
2218:2
2213:5
2209:a
2198:5
2194:a
2185:1
2175:5
2171:a
2165:5
2161:b
2153:5
2149:b
2139:4
2134:4
2130:a
2119:3
2114:4
2110:a
2099:2
2094:4
2090:a
2079:4
2075:a
2066:1
2056:4
2052:a
2046:4
2042:b
2034:4
2030:b
2020:4
2015:3
2011:a
2000:3
1995:3
1991:a
1980:2
1975:3
1971:a
1960:3
1956:a
1947:1
1937:3
1933:a
1927:3
1923:b
1915:3
1911:b
1901:4
1896:2
1892:a
1881:3
1876:2
1872:a
1861:2
1856:2
1852:a
1841:2
1837:a
1828:1
1818:2
1814:a
1808:2
1804:b
1796:2
1792:b
1782:4
1777:1
1773:a
1762:3
1757:1
1753:a
1742:2
1737:1
1733:a
1722:1
1718:a
1709:1
1699:1
1695:a
1689:1
1685:b
1677:1
1673:b
1666:[
1651:e
1646:5
1644:c
1639:2
1637:c
1632:7
1630:a
1625:4
1623:a
1619:)
1617:i
1611:)
1609:i
1602:i
1600:a
1596:α
1585:k
1581:n
1568:i
1566:a
1561:i
1559:a
1555:e
1551:e
1547:k
1545:-
1543:n
1539:e
1522:)
1517:3
1513:n
1509:(
1506:O
1481:e
1476:i
1472:a
1466:i
1462:b
1455:=
1452:)
1447:q
1442:i
1438:a
1432:q
1428:q
1424:+
1418:+
1413:2
1408:i
1404:a
1398:2
1394:q
1390:+
1385:i
1381:a
1375:1
1371:q
1367:+
1362:0
1358:q
1354:(
1348:)
1343:1
1337:e
1332:i
1328:a
1322:1
1316:e
1312:e
1308:+
1302:+
1297:2
1292:i
1288:a
1282:2
1278:e
1274:+
1269:i
1265:a
1259:1
1255:e
1251:+
1246:0
1242:e
1238:(
1233:i
1229:b
1214:e
1212:e
1208:e
1204:n
1200:q
1183:0
1180:=
1177:)
1172:q
1167:i
1163:a
1157:q
1153:q
1149:+
1143:+
1138:2
1133:i
1129:a
1123:2
1119:q
1115:+
1110:i
1106:a
1100:1
1096:q
1092:+
1087:0
1083:q
1079:(
1073:)
1068:e
1063:i
1059:a
1053:e
1049:e
1045:+
1039:+
1034:2
1029:i
1025:a
1019:2
1015:e
1011:+
1006:i
1002:a
996:1
992:e
988:+
983:0
979:e
975:(
970:i
966:b
944:0
941:=
938:)
933:i
929:a
925:(
922:Q
916:)
911:i
907:a
903:(
900:E
895:i
891:b
869:)
864:i
860:a
856:(
853:Q
850:=
847:)
842:i
838:a
834:(
831:E
826:i
822:b
807:e
805:e
801:i
784:)
779:i
775:a
771:(
768:F
765:)
760:i
756:a
752:(
749:E
746:=
743:)
738:i
734:a
730:(
727:Q
713:i
711:a
706:i
704:b
700:e
696:n
692:i
688:i
684:i
680:e
675:i
673:a
656:)
651:i
647:a
643:(
640:F
637:)
632:i
628:a
624:(
621:E
618:=
615:)
610:i
606:a
602:(
599:E
594:i
590:b
576:n
572:e
550:0
547:=
544:)
539:i
535:a
531:(
528:E
508:)
503:i
499:a
495:(
492:E
470:n
466:b
462:,
456:,
451:1
447:b
424:n
420:a
416:,
410:,
405:1
401:a
380:)
375:i
371:a
367:(
364:F
339:n
335:c
331:,
325:,
320:1
316:c
293:n
289:a
285:,
279:,
274:1
271:+
268:k
264:a
243:)
238:i
234:a
230:(
227:F
205:k
201:a
197:,
191:,
186:1
182:a
171:k
157:)
152:i
148:a
144:(
141:F
117:)
112:i
108:a
104:(
101:F
79:k
75:m
71:,
65:,
60:1
56:m
45:k
41:n
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.