バーレカンプ・マッシィ法　具体例

前回のnoteの表記法に基づく。

原始多項式$${x^4+x+1}$$に基づく$${GF(2^4)}$$上のシンボルを持つ(15, 11)RS符号。

シンドロームまで以下のように計算されているとする。

$${S_0 = 15, S_1 = 3, S_2 = 4, S_3 = 12}$$

初期値： $${K = 1, L = 0, \sigma(x) = 1, C(x) = x. }$$

Step1

1. 誤り値$${e = S_0 = 15}$$

2. $${\sigma(x)^* = \sigma(x) + e \times C(x) = 1 + 15 \times x = 1+15x}$$

3. $${L = K - L = 1}$$, $${C(x) = \sigma(x)/e = \sigma(x) / \alpha^{12} = \sigma(x) \alpha^{3} = 8\sigma(x) = 8}$$

4. $${C(x) = C(x)x = 8x}$$, $${\sigma(x) =\sigma(x)^* = 1 + 15x}$$, $${K = K+1 = 2 }$$

Step2

1. 誤り値$${e = S_1 + \sigma_1 S_0  = 3 + 15 \times 15 = 9}$$

2. $${\sigma(x)^* = \sigma(x) + e \times C(x) = 1 + 15x + 9 \times 8x = 1+11x}$$

3. $${L = 2K}$$なので、このステップはスキップ

4. $${C(x) = C(x)x = 8x^2}$$, $${\sigma(x) =\sigma(x)^* = 1 + 11x}$$, $${K = K+1 = 3 }$$

Step3

1. 誤り値$${e = S_2 + \sigma_1 S_1  = 4 + 11 \times 3 = 10}$$

2. $${\sigma(x)^* = \sigma(x) + e \times C(x) = 1 + 11x + 10 \times 8x^2 = 1+11x+15x^2}$$

3. $${L = K - L = 2}$$, $${C(x) = \sigma(x)/e = 12\sigma(x) = 12 + 13x}$$

4. $${C(x) = C(x)x = 12x + 13x^2}$$, $${\sigma(x) =\sigma(x)^* = 1 + 11x + 15x^2}$$, $${K = K+1 = 4 }$$

Step4

1. 誤り値$${e = S_3 + \sigma_1 S_2 + \sigma_2 S_1 = 12 + 11 \times 4 + 15\times 3 = 4}$$

2. $${\sigma(x)^* = \sigma(x) + e \times C(x) = 1 + 11x + 15x^2 + 4 \times (12x+13x^2) = 1 + 11x + 15x^2 + 5x+x^2 = 1 + 14x + 14x^2}$$

3. $${2L = K}$$なのでスキップ

4. $${C(x) = C(x)x = 12x^2}$$, $${\sigma(x) =\sigma(x)^* = 1 + 14x + 14x^2}$$, $${K = K+1 = 5 }$$

したがって誤り位置多項式$${\sigma(x) = 1 + 14x + 14x^2}$$を得る。