RS 符号（複数エラー）

ここでは、一般的な Reed–Solomon（RS）符号について、複数エラー訂正まで含めた一連の流れを説明します。

流れは以下の通りです。

• ヴァンデルモンド行列（符号化）

• エラー多項式モデル

• シンドローム

• Berlekamp–Massey アルゴリズム

• エラーロケータ多項式 $\Lambda(x)$Λ(x)

• エラー評価多項式 $\Omega(x)$Ω(x)

• チェン探索（Chien Search）

• Forney 公式

---

0. 設定（複数エラー対応 RS 符号）

有限体

• $GF(2^3)$GF(23)

• 原始元（primitive element）：$\alpha$α

• $\alpha^7 = 1$α7=1

符号パラメータ

• 符号長：$n=7$n=7

• 情報長：$k=3$k=3

• 訂正能力：$t=2$t=2

つまり最大 2 エラーまで訂正可能です。

評価点

RS 符号では多項式を以下の点で評価します。

$$\alpha^0,\alpha^1,\alpha^2,\alpha^3,\alpha^4,\alpha^5,\alpha^6$$α0,α1,α2,α3,α4,α5,α6

---

1. 符号化（ヴァンデルモンド行列）

メッセージ多項式

$$M(x)=\alpha^2+\alpha^4x+\alpha x^2$$M(x)=α2+α4x+αx2

---

ヴァンデルモンド行列

RS 符号の符号化は、多項式評価として表現できます。

$$\begin{bmatrix} 1 & \alpha^0 & (\alpha^0)^2 \ 1 & \alpha^1 & (\alpha^1)^2 \ 1 & \alpha^2 & (\alpha^2)^2 \ \vdots & \vdots & \vdots \end{bmatrix} \begin{bmatrix} \alpha^2 \ \alpha^4 \ \alpha \end{bmatrix}$$[1​α0​(α0)2 1​α1​(α1)2 1​α2​(α2)2 ⋮​⋮​⋮​][α2 α4 α​]

---

符号語

評価結果として符号語を得ます。

$$W=(w_0,w_1,\dots,w_6)$$W=(w0​,w1​,…,w6​)

---

2. 誤りモデル

ここが複数エラー訂正の核心です。

エラー多項式

$$E(x)=Y_1x^{j_1}+Y_2x^{j_2}$$E(x)=Y1​xj1​+Y2​xj2​

---

具体例

2 箇所でエラーが発生したとします。

• 位置：

  • $j_1=1$j1​=1

  • $j_2=4$j2​=4

• エラー値：

  • $Y_1=\alpha^3$Y1​=α3

  • $Y_2=\alpha^5$Y2​=α5

---

3. 受信データ

受信側には符号語にエラーが加わったデータが届きます。

$$R(x)=W(x)+E(x)$$R(x)=W(x)+E(x)

---

4. シンドローム

RS 符号では、受信データを評価してシンドロームを作ります。

$$S_i = R(\alpha^i)$$Si​=R(αi)

---

重要な式

エラーだけが残るため、

$$S_i = Y_1\alpha^{ij_1} + Y_2\alpha^{ij_2}$$Si​=Y1​αij1​+Y2​αij2​

となります。

---

シンドローム列

訂正能力 $t=2$t=2のため、通常は以下を使用します。

$$S_1,S_2,S_3,S_4$$S1​,S2​,S3​,S4​

---

5. Berlekamp–Massey アルゴリズム

ここが複数エラー訂正の本体です。

---

何をしているのか

シンドローム列

$$S_1,S_2,S_3,\dots$$S1​,S2​,S3​,…

からエラーロケータ多項式を復元します。

---

エラーロケータ多項式

$$\Lambda(x)=1+\lambda_1x+\lambda_2x^2$$Λ(x)=1+λ1​x+λ2​x2

---

直感的な意味

Berlekamp–Massey（BM）アルゴリズムは、

「このシンドローム列を生成する最短の線形フィードバック回路（LFSR）を求める」

アルゴリズムです。

---

出力例

例えば次のような結果になります。

$$\Lambda(x)=1+\alpha^2x+\alpha^5x^2$$Λ(x)=1+α2x+α5x2

---

6. チェン探索（Chien Search）

やること

以下を満たす点を総当たり探索します。

$$\Lambda(x)=0$$Λ(x)=0

つまり

$$x=\alpha^{-i}$$x=α−i

を順番に代入して調べます。

---

発見結果

例えば以下が見つかります。

• $x=\alpha^{-1}\Rightarrow j_1=1$x=α−1⇒j1​=1

• $x=\alpha^{-4}\Rightarrow j_2=4$x=α−4⇒j2​=4

これでエラー位置が分かります。

---

7. エラー評価多項式 $\Omega(x)$Ω(x)

定義

$$\Omega(x)=S(x)\Lambda(x)\bmod x^{2t}$$Ω(x)=S(x)Λ(x)modx2t

---

役割

エラー値に関する情報を圧縮した多項式です。

---

今回の構造

$$\Omega(x)=\omega_0+\omega_1x$$Ω(x)=ω0​+ω1​x

---

8. Forney 公式

ここでエラー値を求めます。

公式

$$Y_i= -\frac{\Omega(\alpha^{-j_i})} {\Lambda'(\alpha^{-j_i})}$$Yi​=−Λ′(α−ji​)Ω(α−ji​)​

---

9. 実際の計算イメージ

エラー 1

位置：

$$j_1=1$$j1​=1

計算結果：

$$Y_1=\alpha^3$$Y1​=α3

---

エラー 2

位置：

$$j_2=4$$j2​=4

計算結果：

$$Y_2=\alpha^5$$Y2​=α5

---

10. 修正

受信語：

$$R=W+E$$R=W+E

---

各位置を修正

• index 1 に $-\alpha^3$−α3を加える

• index 4 に $-\alpha^5$−α5を加える

---

復元結果

$$W(x)$$W(x)

を完全復元できます。

---

11. RS 復号の全体構造

RS 復号は次の 6 層構造になっています。

---

① 符号化

ヴァンデルモンド行列による多項式評価。

---

② 誤りモデル

$$E(x)=\sum Y_i x^{j_i}$$E(x)=∑Yi​xji​

---

③ シンドローム

観測データの圧縮。

---

④ Berlekamp–Massey

エラーロケータ多項式 $\Lambda(x)$Λ(x)を生成。

---

⑤ チェン探索

$$\Lambda(x)=0$$Λ(x)=0

の根を探してエラー位置を特定。

---

⑥ Forney 公式

エラー値を直接計算。

---

12. 本質（重要）

RS 符号の本質は

「2 段階分解」

にあります。

---

① 構造（位置）

• Berlekamp–Massey

• $\Lambda(x)$Λ(x)

---

② 数値（値）

• Forney 公式

• $\Omega(x)$Ω(x)

---

13. 直感的な理解

• BM：犯人の「癖（構造）」を見抜く

• Chien：犯人の「位置」を探す

• Forney：犯人の「ダメージ量」を計算する

---

一言まとめ

RS 符号は

ヴァンデルモンド行列でデータを空間へ埋め込み、
シンドロームで歪みを観測し、
Berlekamp–Massey で構造（$\Lambda$Λ）を復元し、
チェン探索で位置を特定し、
Forney 公式で値を復元する体系

です。

---