Berlekamp–Massey algorithm 이해하기가 너무 힘들어요 ㅠㅠ
위키링크
The Berlekamp–Massey algorithm is an alternate iterative procedure for finding the error locator polynomial. During each iteration, it calculates a discrepancy based on a current instance of Λ(x) with an assumed number of errors e:
and then adjusts Λ(x) and e so that a recalculated Δ would be zero. Berlekamp–Massey algorithm has a detailed description of the procedure. In the following example, C(x) is used to represent Λ(x).
Consider the Reed–Solomon code defined in GF(929) with α = 3 and t = 4 (this is used in PDF417 barcodes). The generator polynomial is
- g(x) = (x − 3)(x − 32)(x − 33)(x − 34) = x4 + 809x3 + 723x2 + 568x + 522
If the message polynomial is p(x) = 3 x2 + 2 x + 1, then the codeword is calculated as follows.
Errors in transmission might cause this to be received instead.
- r(x) = s(x) + e(x) = 3x6 + 2x5 + 123x4 + 456x3 + 191x2 + 487x + 474
The syndromes are calculated by evaluating r at powers of α.
To correct the errors, first use the Berlekamp–Massey algorithm to calculate the error locator polynomial.
--------------------------------------------------------
여기 까지 이해해서 밑에 Sn+1의 신드롬은 생성 할 수 있습니다.
하지만 밑에 표와 같이 d,C,B,b,m의 생성과 그 밑에 식을 유도 하지 못하겠습니다. 아시면 알려주세요.
| n | Sn+1 | d | C | B | b | m |
|---|---|---|---|---|---|---|
| 0 | 732 | 732 | 197 x + 1 | 1 | 732 | 1 |
| 1 | 637 | 846 | 173 x + 1 | 1 | 732 | 2 |
| 2 | 762 | 412 | 634 x2 + 173 x + 1 | 173 x + 1 | 412 | 1 |
| 3 | 925 | 576 | 329 x2 + 821 x + 1 | 173 x + 1 | 412 | 2 |
The final value of C is the error locator polynomial, Λ(x). The zeros can be found by trial substitution. They are x1 = 757 = 3−3 and x2 = 562 = 3−4, corresponding to the error locations. To calculate the error values, apply the Forney algorithm.
Subtracting e1x3 and e2x4 from the received polynomial r reproduces the original codeword s.
댓글 달기