RS符号（リード・ソロモン符号）の仕組み

はじめに

RS符号（リード・ソロモン符号）は、データの転送や記録時に発生するミスを検出し自動で修正するための誤り訂正符号の一種です。計算の仕組みを下記にまとめます。

1. 送信側の準備（符号化）

まず2つの根（例： $\alpha^1$ と $\alpha^2$ ）で割り切れる式を作ります。

生成多項式 $G(x)$ の作成:
$G(x) = (x + \alpha^1)(x + \alpha^2) = x^2 + \alpha^4x + \alpha^3$
割り算で余りを出す:
データ $M(x)$ を $G(x)$ で割り、余りをくっつけて送信データ $W(x)$ を作ります。
完成した $W(x)$ の特徴:
$W(\alpha^1) = 0$ かつ $W(\alpha^2) = 0$ になる。（これが検証時の合格基準）

1. 準備：スペースを空ける

送りたいデータ $M(x) = \alpha^1$ に検査列（余り）を入れるための2次分の空席を作ります。

計算： $M(x) \cdot x^2 = \alpha^1 x^2$
これを「中身がまだ空っぽの送信データ案」と呼びましょう。

2. 実行：生成多項式 $G(x)$ で割る

この案を $G(x) = (x + \alpha^1)(x + \alpha^2) = x^2 + \alpha^4x + \alpha^3$ で割ります。
目的は「あとどれだけ足りないか（余り）」を調べることです。

【筆算のプロセス】

商を立てる：先頭の $\alpha^1 x^2$ を消すために商に $\alpha^1$ を立てます。
引き算用の式を作る：商 $\alpha^1$ と $G(x)$ を掛けます。
- $\alpha^1 \cdot (x^2 + \alpha^4x + \alpha^3) = \mathbf{\alpha^1 x^2 + \alpha^5x + \alpha^4}$
余りを出す：元の案から今の式を引き（足し）ます。
- $(\alpha^1 x^2) + (\alpha^1 x^2 + \alpha^5x + \alpha^4) = \mathbf{\alpha^5x + \alpha^4}$
- これが余り $R(x)$ です。

3. 合体：完成した $W(x)$ の正体

元の案に今出した余りをくっつけます。

$W(x) = \alpha^1 x^2 + (\alpha^5x + \alpha^4)$

ここで数学的なマジックが起きています。この式をよく見るとステップ2で作った「引き算用の式」そのものになっていますよね？
つまり $W(x) = \alpha^1 \cdot G(x)$ という形になっているのです。

4. 特徴：なぜ $0$ になるのか？

完成した $W(x)$ は「 $G(x)$ の倍数」です。
中身を分解するとこうなっています：
$W(x) = \alpha^1 \cdot {(x + \alpha^1)(x + \alpha^2)}$

この式に $x = \alpha^1$ や $x = \alpha^2$ を代入するとどうなるでしょうか？

$x = \alpha^1$ を代入：
$W(\alpha^1) = \alpha^1 \cdot (\alpha^1 + \alpha^1) \cdot (\alpha^1 + \alpha^2) = \alpha^1 \cdot (\mathbf{0}) \cdot (\alpha^1 + \alpha^2) = \mathbf{0}$
$x = \alpha^2$ を代入：
$W(\alpha^2) = \alpha^1 \cdot (\alpha^2 + \alpha^1) \cdot (\alpha^2 + \alpha^2) = \alpha^1 \cdot (\alpha^2 + \alpha^1) \cdot (\mathbf{0}) = \mathbf{0}$

「 $G(x)$ で割って余りを出す」という作業は言い換えれば「データを $G(x)$ の倍数に無理やり整形する作業」です。

わざと割ることで足りないパーツ（余り）を特定する。
そのパーツをくっつけることで全体を $G(x)$ で割り切れる形にする。
$G(x)$ は最初から $(x + \alpha^1)$ と $(x + \alpha^2)$ を持っているのでそれら（根）を代入すれば必ず $0$ になる。

2. 受信側での異常検知（シンドローム計算）

受信したデータを $R(x)$ とします。もし途中でエラー $E(x)$ が混じると $R(x) = W(x) + E(x)$ となります。
受信側は2つの根を代入して、シンドローム（ $S_1, S_2$ ）を出します。

$S_1 = R(\alpha^1) = W(\alpha^1) + E(\alpha^1) = \mathbf{E(\alpha^1)}$
$S_2 = R(\alpha^2) = W(\alpha^2) + E(\alpha^2) = \mathbf{E(\alpha^2)}$

もし両方 $0$ なら: エラーなし（合格！）。
もし $0$ でなければ: その値（ $S_1, S_2$ ）の中にエラーの場所と大きさの情報が閉じ込められています。

3. エラーの特定（方程式を解く）

ここが一番のポイントです。
仮に「 $x^j$ という場所に $Y$ という大きさのエラー」が起きたとするとシンドロームは以下のようになります。

$S_1 = Y \cdot (\alpha^1)^j$
$S_2 = Y \cdot (\alpha^2)^j$

この2つの式はいわば「犯人が残した2つの足跡」です。これを連立方程式として解くことで未知数である $j$ （場所）と $Y$ （大きさ）を特定します。

具体例：
$S_2$ を $S_1$ で割ってみると…
$\frac{S_2}{S_1} = \frac{Y \cdot \alpha^{2j}}{Y \cdot \alpha^j} = \alpha^j$
この結果を見れば $\alpha$ が何乗されているか＝「どの場所（ $j$ ）が化けたか」が一発でわかります！場所がわかれば、大きさ $Y$ もすぐに逆算できます。

4. 修正（訂正）

場所 $j$ と大きさ $Y$ が判明したら最後に修理をします。

修正: 受信データ $R(x)$ の該当箇所に算出したエラー $Y$ を足します。
結果: 化けていたビットが反転し、元の正しい $W(x)$ に戻ります。

具体的な計算

生成多項式の根： $x = \alpha^1$ と $x = \alpha^2$
正しい送信データ $W(x)$ ： $\alpha^1 x^2 + \alpha^5x + \alpha^4$
ルール： $\alpha^7 = 1$ 、また足し算は「同じものを足すと $0$ 」になる世界です。

1. エラー発生！

通信中に $x^1$ の項（ $\alpha^5x$ ）がノイズで $\alpha^2x$ に化けて届いたとします。

受信データ $R(x) = \alpha^1 x^2 + \mathbf{\alpha^2 x} + \alpha^4$

受信側はどこが化けたかまだ知りません。

2. シンドローム（足跡）を計算する

受信した $R(x)$ に根を代入して計算します。

① $S_1$ の計算 ( $x = \alpha^1$ を代入)
$S_1 = \alpha^1(\alpha^1)^2 + \alpha^2(\alpha^1) + \alpha^4$
$= \alpha^3 + \alpha^3 + \alpha^4$
$= 0 + \alpha^4 = \mathbf{\alpha^4}$

② $S_2$ の計算 ( $x = \alpha^2$ を代入)
$S_2 = \alpha^1(\alpha^2)^2 + \alpha^2(\alpha^2) + \alpha^4$
$= \alpha^5 + \alpha^4 + \alpha^4$
$= \alpha^5 + 0 = \mathbf{\alpha^5}$

3. 犯人（場所と大きさ）を特定する

出揃ったシンドローム $S_1 = \alpha^4, S_2 = \alpha^5$ を使って分析します。

【ステップA：場所 $j$ を出す】
比率を計算します。
$\frac{S_2}{S_1} = \frac{\alpha^5}{\alpha^4} = \alpha^1$
公式 $\frac{S_2}{S_1} = \alpha^j$ に当てはめると、 $\alpha^j = \alpha^1$ なので、場所は $j=1$ ( $x^1$ の項) だと判明しました！

【ステップB：大きさ $Y$ を出す】
$S_1 = Y \cdot (\alpha^1)^j$ に、いま分かった $j=1$ を入れます。
$\alpha^4 = Y \cdot \alpha^1$
$Y = \frac{\alpha^4}{\alpha^1} = \mathbf{\alpha^3}$
これで「 $x^1$ の場所に $\alpha^3$ というエラーが足された」ことが特定できました。

4. データを修正する

受信したデータの $x^1$ の項（ $\alpha^2$ ）に、特定したエラー（ $\alpha^3$ ）を足して打ち消します。

修正計算： $\alpha^2 + \alpha^3$
（ビットで見ると $100 + 011 = 111$ ）
$\alpha^2 + \alpha^3$ の結果は $\alpha^5$ になります。
復活したデータ： $\alpha^1 x^2 + \mathbf{\alpha^5 x} + \alpha^4$

見送信側が送った元のデータに戻りました。

$S_2 \div S_1$ で「場所」を特定
逆算で「大きさ」を特定
足し算で「エラーを消去」

まとめ

送信側: 2つの根で割り切れるように「余り」を仕込む。
受信側: 2つの根を代入して「2つのシンドローム」を出す。
特定: 2つのシンドロームを比較して「場所」と「大きさ」を割り出す。
修正: 特定したエラーを上書きして消去する。

根が2つあるおかげで、「どこが」「どう」間違ったのかを計算できます。