RS 符号(複数エラー)
ここでは、一般的な Reed–Solomon(RS)符号について、複数エラー訂正まで含めた一連の流れを説明します。
流れは以下の通りです。
0. 設定(複数エラー対応 RS 符号)
有限体
符号パラメータ
-
符号長:n=7
-
情報長:k=3
-
訂正能力:t=2
つまり最大 2 エラーまで訂正可能です。
評価点
RS 符号では多項式を以下の点で評価します。
α0,α1,α2,α3,α4,α5,α6
1. 符号化(ヴァンデルモンド行列)
メッセージ多項式
M(x)=α2+α4x+αx2
ヴァンデルモンド行列
RS 符号の符号化は、多項式評価として表現できます。
[1α0(α0)2 1α1(α1)2 1α2(α2)2 ⋮⋮⋮][α2 α4 α]
符号語
評価結果として符号語を得ます。
W=(w0,w1,…,w6)
2. 誤りモデル
ここが複数エラー訂正の核心です。
エラー多項式
E(x)=Y1xj1+Y2xj2
具体例
2 箇所でエラーが発生したとします。
-
位置:
-
j1=1
-
j2=4
-
エラー値:
-
Y1=α3
-
Y2=α5
3. 受信データ
受信側には符号語にエラーが加わったデータが届きます。
R(x)=W(x)+E(x)
4. シンドローム
RS 符号では、受信データを評価してシンドロームを作ります。
Si=R(αi)
重要な式
エラーだけが残るため、
Si=Y1αij1+Y2αij2
となります。
シンドローム列
訂正能力 t=2のため、通常は以下を使用します。
S1,S2,S3,S4
5. Berlekamp–Massey アルゴリズム
ここが複数エラー訂正の本体です。
何をしているのか
シンドローム列
S1,S2,S3,…
からエラーロケータ多項式を復元します。
エラーロケータ多項式
Λ(x)=1+λ1x+λ2x2
直感的な意味
Berlekamp–Massey(BM)アルゴリズムは、
「このシンドローム列を生成する最短の線形フィードバック回路(LFSR)を求める」
アルゴリズムです。
出力例
例えば次のような結果になります。
Λ(x)=1+α2x+α5x2
6. チェン探索(Chien Search)
やること
以下を満たす点を総当たり探索します。
Λ(x)=0
つまり
x=α−i
を順番に代入して調べます。
発見結果
例えば以下が見つかります。
これでエラー位置が分かります。
7. エラー評価多項式 Ω(x)
定義
Ω(x)=S(x)Λ(x)modx2t
役割
エラー値に関する情報を圧縮した多項式です。
今回の構造
Ω(x)=ω0+ω1x
8. Forney 公式
ここでエラー値を求めます。
公式
Yi=−Λ′(α−ji)Ω(α−ji)
9. 実際の計算イメージ
エラー 1
位置:
j1=1
計算結果:
Y1=α3
エラー 2
位置:
j2=4
計算結果:
Y2=α5
10. 修正
受信語:
R=W+E
各位置を修正
復元結果
W(x)
を完全復元できます。
11. RS 復号の全体構造
RS 復号は次の 6 層構造になっています。
① 符号化
ヴァンデルモンド行列による多項式評価。
② 誤りモデル
E(x)=∑Yixji
③ シンドローム
観測データの圧縮。
④ Berlekamp–Massey
エラーロケータ多項式 Λ(x)を生成。
⑤ チェン探索
Λ(x)=0
の根を探してエラー位置を特定。
⑥ Forney 公式
エラー値を直接計算。
12. 本質(重要)
RS 符号の本質は
「2 段階分解」
にあります。
① 構造(位置)
-
Berlekamp–Massey
-
Λ(x)
② 数値(値)
-
Forney 公式
-
Ω(x)
13. 直感的な理解
-
BM:犯人の「癖(構造)」を見抜く
-
Chien:犯人の「位置」を探す
-
Forney:犯人の「ダメージ量」を計算する
一言まとめ
RS 符号は
ヴァンデルモンド行列でデータを空間へ埋め込み、
シンドロームで歪みを観測し、
Berlekamp–Massey で構造(Λ)を復元し、
チェン探索で位置を特定し、
Forney 公式で値を復元する体系
です。