1. 導入：2つの日常的かつ驚異的な「情報復元の奇跡」

私たちの身の回りや科学技術の最前線には、直感に反するほど強靭な「情報の不死鳥」とも呼ぶべき現象が2つ存在します。

奇跡①：数十億キロメートル彼方から届くボイジャー探査機の鮮明な惑星画像

1977年に打ち上げられた深宇宙探査機ボイジャー1号・2号（Voyager 1 & 2）は、木星・土星・天王星・海王星を次々とフライバイし、現在では太陽圏（ヘリオスフィア）を脱出して地球から240億キロメートル以上離れた星間空間を航行しています。

ここで驚くべき物理的事実があります。ボイジャーに搭載された無線送信機の出力は、わずか$23\text{ W}$（ワット）——家庭の冷蔵庫の中にある小さな豆電球や、一般的なLED電球1〜2個分程度の電力しかありません。この微弱な電波が数十億キロメートルの宇宙空間を球面状に拡散しながら伝播し、地球上のNASA深宇宙通信網（DSN：直径70メートルの巨大パラボラアンテナ）に到達する頃には、受信電力は実に$10^{-16}\text{ W}$（$0.1\text{ aW}$：アトワット）以下にまで減衰しています。

これは、スマートフォンの一般的な受信感度よりもさらに何桁も小さく、宇宙背景放射や受信機内部の電子が熱運動によって生み出す熱雑音（Thermal Noise）の嵐の中に完全に埋もれてしまうレベルの極微弱エネルギーです。そのまま生のビット列としてデジタル画像を送れば、何千・何万ものビットがノイズによって無作為に反転（$0 \leftrightarrow 1$）し、地球に届く写真は砂嵐のような意味不明のノイズ画像になってしまうはずです。それにもかかわらず、ボイジャーは木星の「大赤斑」の渦や、海王星の鮮やかなコバルトブルーの大気、トリトンの氷の火山を、1ピクセルの破綻もない鮮明なカラー画像として地球へ送り届けました。

奇跡②：30%がコーヒーで汚れたりロゴで潰れても10ミリ秒で読めるQRコード

もうひとつの奇跡は、私たちが毎日スマートフォンで読み取っているQRコード（Quick Response Code）です。 カフェのテーブルに置かれたメニュー用QRコードの角にコーヒーのシミが付いていたり、屋外の看板のQRコードが雨風で一部剥がれていたり、あるいは企業のブランドロゴやイラストがQRコードの中央面積の最大30%近くを完全に塗りつぶしているデザインを見かけたことがあるでしょう。

常識的に考えれば、デジタルデータの3割が物理的に欠損・汚損していれば、ファイルは破損して開けないはずです。しかし、スマートフォンのカメラをかざした瞬間、わずか$10\text{ ms}$（ミリ秒）足らずのうちに、1ビットの誤りもなく（Zero Bit Errors）元のURLや決済情報が一瞬で復元されます。

  flowchart TD
    subgraph Voyager["深宇宙通信（ボイジャー探査機）"]
        V1["惑星画像データ k ビット"] --> V2["連接符号化（RS符号 + 畳み込み/LDPC符号）"]
        V2 --> V3["23W送信 → 数十億km伝播（受信電力 10⁻¹⁶ W）"]
        V3 --> V4["熱雑音による大量のビット反転エラー"]
        V4 --> V5["軟判定ビタビ / 確率伝播 + RS復号"]
        V5 --> V6["誤りゼロの鮮明な惑星ポートレート復元"]
    end
    subgraph QR["日常のQRコード読み取り"]
        Q1["URL・テキストデータ k バイト"] --> Q2["GF(2⁸) リード＝ソロモン符号化（n バイト）"]
        Q2 --> Q3["コーヒーのシミ・企業ロゴで最大30%が物理欠損"]
        Q3 --> Q4["シンドローム計算 + バーレカンプ＝マッシー法"]
        Q4 --> Q5["誤り位置・誤り値の代数特定（10ミリ秒）"]
        Q5 --> Q6["1ビットの狂いもない完全なデータ復元"]
    end

なぜ、熱雑音に呑み込まれた宇宙からの電波や、3割が物理的に削り取られた2次元バーコードから、元の情報を数学的に100%の精度で再構築できるのでしょうか？

その答えこそが、20世紀最大の知の金字塔であるクロード・シャノンの情報理論（Information Theory）と、幾何学・抽象代数学（ガロア体理論）・グラフ理論の粋を集めて構築された誤り訂正符号（Error-Correcting Codes: ECC）の科学です。本稿では、その根底にある数学的構造を基礎から最先端のシャノン限界達成符号まで徹底的に解き明かします。

2. クロード・シャノンの1948年革命と「通信路符号化定理」

2.1 1948年以前の絶望と「素朴な反復符号」の罠

1948年以前、通信工学の世界ではひとつの「常識（そして絶望）」が支配していました。それは、「ノイズのある通信路で誤り確率を限りなくゼロに近づけようとすれば、情報の伝送速度（レート）もまたゼロに近づかざるを得ない」という思い込みです。

なぜそう考えられていたのか、最も直感的な反復符号（Repetition Code）で計算してみましょう。 送信したい1ビットの情報（$0$ または $1$）が、確率 $p$（ただし $0 < p < 0.5$）で反転してしまう2元対称通信路（BSC: Binary Symmetric Channel）を通るとします。エラーを防ぐ最も素朴な方法は、「同じビットを奇数回 $n$ 回繰り返して送り、受信側で多数決（Majority Voting）をとる」ことです。

つまり、「信頼性（$P_e \to 0$）」と「伝送効率（$R > 0$）」は決して両立しないトレードオフであり、ノイズを完全に克服したければ通信速度を限りなくゼロに落とすか、あるいは莫大な送信電力を投入して物理的なノイズ比（S/N比）そのものを改善するしかない——1940年代のすべての通信技術者がそう信じて疑いませんでした。

2.2 シャノンの衝撃：通信路容量 $C$ と通信路符号化定理

1948年、ベル研究所の数学者クロード・シャノン（Claude E. Shannon）は、不朽の論文『通信の数学的理論（A Mathematical Theory of Communication）』を発表し、この常識を根底から覆しました。

シャノンが証明した通信路符号化定理（Noisy-Channel Coding Theorem / シャノンの第2基本定理）の主張は、当時の科学界に雷鳴のような衝撃を与えました。

【定理：シャノンの通信路符号化定理】 いかなる無記憶通信路にも、その統計的雑音特性のみによって決まる固有の正の定数「通信路容量（Channel Capacity） $C$」が存在する。 情報源の伝送レート（符号化率） $R$ がこの通信路容量 $C$ より厳密に小さい限り（$R < C$）、どれほど $R$ が $C$ に近くとも、符号長 $n$ を十分に大きくとることで、復号誤り確率 $P_e$ を任意に小さく（$P_e \to 0$）できるブロック符号 $\mathcal{C}$ と復号規則が必ず存在する。逆に $R > C$ のとき、誤り確率をゼロに漸近させることはいかなる符号を用いても不可能である。

つまり、誤り確率 $P_e$ をゼロに近づけるために伝送レート $R$ をゼロに落とす必要などまったくなかったのです！通信路の限界速度 $C$ を超えない限り、一定の高速なレート $R$ を保ったまま、エラー率だけを限りなくゼロにできることをシャノンは数学的に証明しました。

2.3 2元対称通信路（BSC）の容量 $C_{\text{BSC}}(p)$ の導出

となり、送信ビットの約 $53.1\%$ を純粋な情報ビットに割り当てながら、復号エラー率を $10^{-15}$ でも $10^{-50}$ でも好きなだけゼロに近づけられるのです。素朴な反復符号ではなく、「複数の情報ビットを長大なブロックとして絡み合わせて符号化する」ことで、ノイズの統計的ゆらぎ（典型集合：Typical Set）を大数の法則によって完全に吸収できるというのがシャノンのランダム符号化証明の核心でした。

2.4 AWGN通信路と究極の物理限界「シャノン限界 $-1.59\,\text{dB}$」

この $E_b / N_0 = -1.59\,\text{dB}$ という数値は、1情報ビットあたりの信号エネルギー $E_b$ が雑音電力密度 $N_0$ の約 $0.693$ 倍（信号がノイズより小さい状態！）であっても、それ以上のエネルギーさえあれば理論上はエラーゼロで宇宙の果てから通信できることを意味し、逆に $-1.59\,\text{dB}$ を下回れば、いかなる文明のいかなる超技術をもってしてもエラーのない通信は絶対に不可能であるという、熱力学第二法則にも匹敵する宇宙の絶対限界なのです。

3. リチャード・ハミングの1950年の幾何学的突破：ハミング距離と $[7, 4, 3]$ 完全符号

3.1 シャノンの「存在証明」からハミングの「構成的幾何学」へ

シャノンの1948年の定理は「そのような理想的な符号が存在する（ランダムに選んだ符号の平均をとれば条件を満たす）」という非構成的な存在証明であり、「では具体的にどうやってその符号を作り、実用的な計算時間で復号するのか？」というアルゴリズムは示していませんでした。

同じベル研究所でシャノンと部屋を並べていた数学者リチャード・ハミング（Richard W. Hamming）は、週末にリレー式計算機（Bell Model V）にパンチカードでジョブを投入するたび、たった1ビットの読み取りエラーで計算全体が強制停止して週末の計算が丸ごと無駄になることに激しい苛立ちを覚えていました。 「機械が自分で『ここにエラーがある』と検知できるなら、なぜ『どのビットが間違っているか』を特定して自分で直せないのか？」——この問いから1950年に誕生したのが、ハミング距離（Hamming Distance）という幾何学的概念と、人類初の実用的な誤り訂正符号であるハミング $(7,4)$ 符号でした。

3.2 $n$ 次元超立方体 $\mathbb{F}_2^n$ 上のハミング距離と最小距離 $d_{\min}$

長さ $n$ のすべての2進ビット列の集合を、2元体 $\mathbb{F}_2 = \{0, 1\}$ 上の $n$ 次元ベクトル空間（幾何学的には $2^n$ 個の頂点を持つ $n$ 次元超立方体 Hypercube） $\mathbb{F}_2^n$ とみなします。

ここで $w_H(\mathbf{x}) = |\{i \mid x_i \neq 0\}|$ は非ゼロ成分の個数を与えるハミング重み（Hamming Weight）です。ハミング距離は非負性・対称性・三角不等式 $d_H(\mathbf{u}, \mathbf{w}) \le d_H(\mathbf{u}, \mathbf{v}) + d_H(\mathbf{v}, \mathbf{w})$ をすべて満たす厳密な距離空間（Metric Space）をなします。

3.3 ハミング球のパッキングによる誤り検出・消失訂正・誤り訂正能力の証明

なぜ最小距離 $d_{\min}$ が大きいほど強い誤り訂正ができるのでしょうか？超立方体 $\mathbb{F}_2^n$ 内に、各符号語 $\mathbf{c} \in \mathcal{C}$ を中心とする半径 $t$ のハミング球（Hamming Sphere） $B_t(\mathbf{c}) = \{\mathbf{y} \in \mathbb{F}_2^n \mid d_H(\mathbf{c}, \mathbf{y}) \le t\}$ を描くことで、3つの基本能力が幾何学的に証明されます。

1. 誤り検出能力（Error Detection）：$d_{\min} - 1$ 個まで検出可能 符号語間の最小距離が $d_{\min}$ であるとき、ある符号語 $\mathbf{c}$ から $1$ 個以上 $d_{\min} - 1$ 個以下のビットが反転しても、受信語 $\mathbf{y}$ は決して別の符号語 $\mathbf{c}'$ に一致することはありません（一致するには最低 $d_{\min}$ 個の反転が必要）。したがって、受信語 $\mathbf{y} \notin \mathcal{C}$ であることをチェックするだけで、高々 $d_{\min} - 1$ 個のあらゆるビット誤りを100%確実に検出できます。
2. 消失訂正能力（Erasure Correction）：$e = d_{\min} - 1$ 個まで復元可能 「どの座標が欠損したか（位置）」は分かっているが、その値（$0$ か $1$ か）だけが不明である状態を消失（Erasure：たとえばパケットロスや破損セクタ）と呼びます。異なる2つの符号語は少なくとも $d_{\min}$ 箇所の座標で異なる値を持つため、たとえ $e \le d_{\min} - 1$ 箇所の座標が消え去っても、残りの $n - e$ 箇所の既知座標だけで一致する符号語はただ1つに絞られます。よって最大 $d_{\min} - 1$ 個の消失を完全に復元できます。
3. 任意誤り訂正能力（Error Correction）：$t = \lfloor(d_{\min}-1)/2\rfloor$ 個まで訂正可能 どのビットが反転したか位置すら分からない場合、受信語 $\mathbf{y}$ を「最もハミング距離が近い符号語 $\hat{\mathbf{c}} = \arg\min_{\mathbf{c}\in\mathcal{C}} d_H(\mathbf{y}, \mathbf{c})$」へと復号（最近傍復号）します。このとき、任意の2つの異なる符号語 $\mathbf{c}_1, \mathbf{c}_2$ を中心とする半径 $t$ のハミング球 $B_t(\mathbf{c}_1)$ と $B_t(\mathbf{c}_2)$ が互いに重ならない（Disjoint：$B_t(\mathbf{c}_1) \cap B_t(\mathbf{c}_2) = \emptyset$）ための必要十分条件は、三角不等式より： $$2t + 1 \le d_{\min} \iff t = \left\lfloor \frac{d_{\min} - 1}{2} \right\rfloor$$ です。一般に、位置未知の誤り $t$ 個と位置既知の消失 $e$ 個が同時に発生する場合、1個の誤りは2個の消失に相当する自由度を消費するため、完全復元の必要十分条件は次の統一不等式で与えられます： $$\mathbf{d_{\min} \ge 2t + e + 1}$$

この不等式で等号が成立する符号（つまり半径 $t$ のハミング球が $n$ 次元空間 $\mathbb{F}_q^n$ を1点の隙間も重なりもなく完全に埋め尽くす符号）を完全符号（Perfect Code）と呼びます。代数的符号理論の驚くべき定理（Tietäväinen-van Lintの定理）により、非自明な完全符号は全数学空間の中に「ハミング符号」と「ゴレイ符号（Golay Code：ボイジャーが木星・土星探査で実際に使用した $[23,12,7]_2$ 符号および $[11,6,5]_3$ 符号）」の2種類しか存在しないことが証明されています。

3.4 ハミング $(7,4)$ 符号の生成行列 $\mathbf{G}$・検査行列 $\mathbf{H}$・シンドローム復号

となり、見事に等号が成立する$t=1$ 誤り訂正の完全符号となっています。

（列ベクトルが左から順に $1=(001)^T, 2=(010)^T, 3=(011)^T, 4=(100)^T, 5=(101)^T, 6=(110)^T, 7=(111)^T$ に対応しています。）

この式が持つ威力に注目してください！シンドローム $\mathbf{s}$ は、送信されたメッセージ $\mathbf{c}$ が何であったかに一切依存せず、純粋にエラー $\mathbf{e}$ のみに依存します。 もし第 $j$ ビット目ただ1つだけが反転していた場合（すなわち $\mathbf{e} = (0, \dots, 0, \underset{j\text{番目}}{1}, 0, \dots, 0)$ の単位ベクトル）、行列とベクトルの積 $\mathbf{H}\mathbf{e}^T$ は、行列 $\mathbf{H}$ の第 $j$ 列ベクトルそのものを取り出します！

先ほどの2進数順の検査行列 $\mathbf{H}_{\text{binary}}$ を使っていれば、計算された3ビットのシンドローム $\mathbf{s} = (s_2, s_1, s_0)^T$ をそのまま2進数の数値として読むだけで、

• $\mathbf{s} = (0,0,0)^T \implies$ エラーなし（0番目）
• $\mathbf{s} = (1,0,1)^T \implies 101_2 = 5 \implies$ 第5ビット目が反転している！

と、探索すら行うことなく $O(1)$ のビット演算だけで瞬時にエラー箇所を特定・反転修復できるのです。このハミング符号の仕組み（に全体の偶数パリティ1ビットを追加して2ビット誤り検出も可能にした SECDED: Single Error Correction, Double Error Detection 拡張ハミング符号）は、現在もデータセンターのサーバーに搭載されている ECCメモリ（ECC DRAM） のハードウェア回路の中で毎秒何十億回も実行され、宇宙線中性子によるメモリビット反転（ソフトエラー）から世界中のクラウド基盤を守り続けています。

4. リードとソロモンの1960年の最高傑作：ガロア体 $\mathbb{F}_{2^m}$ 上のリード＝ソロモン（RS）符号

4.1 なぜハミング符号では「傷」や「汚れ（バースト誤り）」に勝てないのか？

ハミング符号は「7ビット中にたまたま1ビットだけランダムに反転する誤り」には無敵ですが、現実世界のストレージやQRコードでは致命的な弱点があります。 CDやDVDの表面についた1ミリの引っかき傷、QRコードの上に落ちたコーヒーの雫、あるいはフェージングによる無線通信の瞬断は、1ビットだけではなく連続する数十〜数百ビットを一気に破壊する「バースト誤り（Burst Errors）」を引き起こします。ハミング $(7,4)$ 符号で2ビット以上が同時に壊れると、シンドロームはまったく別の正常なビット位置を指し示し、訂正するどころか誤りをさらに増やしてしまいます。

この壁を打ち破るため、1960年にMITリンカーン研究所のアーヴィング・リード（Irving S. Reed）とギュスターヴ・ソロモン（Gustave Solomon）が発表したのが、現代デジタル文明の守護神とも呼べるリード＝ソロモン符号（Reed-Solomon Codes: RS符号）です。

4.2 ガロア体（有限体） $\mathbb{F}_{2^m}$ による「ビットの束（シンボル）」の代数化

リードとソロモンの第一の着眼点は、「0と1の単一ビット（$\mathbb{F}_2$）単位で考えるのをやめ、連続する $m$ ビット（たとえば $m=8$ ビット＝1バイト）をひとまとめにした『1つの数値（シンボル）』として扱い、加減乗除が自由にできる有限体（ガロア体 $\mathbb{F}_{2^m}$）の上で符号を組めばよいではないか！」というものでした。

なぜ通常の整数 $\bmod 256$ ではいけないのでしょうか？$\mathbb{Z}/256\mathbb{Z}$ では、たとえば $2 \times 128 \equiv 0 \pmod{256}$ となってしまい（零因子の存在）、割り算（逆元）が定義できないため、連立一次方程式や多項式補間が一意に解けなくなってしまいます。 エヴァリスト・ガロアが発見した定理により、要素数 $q$ の有限体（四則演算が完全に閉じており、0以外のすべての要素が乗法逆元を持つ代数系）が存在するための必要十分条件は、$q = p^m$（素数 $p$ のべき乗）であることです。

このガロア体 $\mathbb{F}_{2^8}$ の中では、1バイト（8ビット：$b_7 b_6 \dots b_1 b_0$）のデータが7次以下の多項式 $b_7 x^7 + \dots + b_1 x + b_0$ に対応し、驚くほど美しい性質を持ちます：

1. 足し算と引き算は単なるビットごとの XOR（排他的論理和）：係数が $\mathbb{F}_2$ なので $1 + 1 = 0$ となり、繰り上がりも一切発生せず、加法と減法は完全に同一の a ^ b（XOR演算）になります。
2. 掛け算と割り算は原始元 $\alpha$ の指数（対数）テーブルで $O(1)$：非ゼロの255個の要素 $\mathbb{F}_{2^8}^\times$ は巡回群をなすため、ある原始元（Primitive Element） $\alpha$（通常は多項式 $x$ すなわち数値 0x02）のべき乗 $\alpha^0, \alpha^1, \alpha^2, \dots, \alpha^{254}$ によって255個すべての非ゼロ要素が重複なく生成されます（$\alpha^{255} = 1$）。したがって、256バイトの指数表 EXP_TABLE と対数表 LOG_TABLE をメモリに置いておけば、任意の2要素 $A = \alpha^i, B = \alpha^j$ の積と商は、指数の足し算・引き算だけで一瞬で求まります： $$A \cdot B = \alpha^{(i + j) \bmod 255}, \qquad \frac{A}{B} = \alpha^{(i - j) \bmod 255}$$

これにより、たとえば1バイト（8ビット）の中に連続して何ビットもの破損が起きても、ガロア体 $\mathbb{F}_{2^8}$ の視点からは「たった1個のシンボル（1変数）が汚れただけ」に過ぎなくなります！これがRS符号がバースト誤りに圧倒的に強い第一の理由です。

4.3 代数学の奇跡：有限体上の多項式補間とシングルトン限界の達成（MDS性）

リードとソロモンの第二の（そして最大の）着眼点は、高校数学でも馴染み深い「多項式の一意性」を有限体 $\mathbb{F}_q$ 上に持ち込んだことです。

• 1次関数（直線） $P(x) = m_0 + m_1 x$ は、平面上の任意の2点を通ればただ1本に決まります。もしその直線上の5つの点の座標を送れば、途中でどの3点が消滅しても、残った2点から元の直線を100%復元できます。
• 2次関数（放物線） $P(x) = m_0 + m_1 x + m_2 x^2$ は、任意の3点でただ1つに決まります。

ここで代数学の基本定理から導かれる決定的な事実があります：

【定理：有限体上の多項式の根の個数とRS符号の最小距離】 体 $\mathbb{F}_q$ 上の次数が高々 $k-1$ の非ゼロ多項式は、$\mathbb{F}_q$ 内に高々 $k-1$ 個の根（ゼロ点）しか持つことができない。 したがって、異なる2つの情報多項式 $P(x) \neq Q(x)$（ともに次数 $\le k-1$）に対し、その差 $D(x) = P(x) - Q(x)$ も次数 $\le k-1$ の非ゼロ多項式であるため、$P(\alpha_i) = Q(\alpha_i)$ となって値が一致する評価点 $\alpha_i$ は最大でも $k-1$ 個しか存在しない。 ゆえに、$n$ 個の評価点のうち少なくとも $n - (k - 1) = n - k + 1$ 個の座標で必ず値が異なる！

符号理論において、いかなる $[n, k, d_{\min}]$ 符号であっても、最初の $d_{\min}-1$ 個の座標を削ぎ落とした長さ $n - (d_{\min} - 1)$ のベクトルがすべて相異ならなければならないことから、必ず $d_{\min} \le n - k + 1$ が成り立ちます。これをシングルトン限界（Singleton Bound）と呼びます。 リード＝ソロモン符号は、この理論上の上限 $d_{\min} = n - k + 1$ を等号で達成する究極の符号——最大距離分離符号（MDS: Maximum Distance Separable Code）なのです！

MDS符号である $[n, k]$ リード＝ソロモン符号に、冗長パリティシンボルを $n - k = 2t$ 個付加したとき、先ほどの統一不等式 $2t + e \le d_{\min} - 1 = n - k$ から、次の驚異的な能力が直ちに導かれます：

• 位置が既知の消失（Erasures）なら：追加したパリティの個数とまったく同じ $e = n - k$ シンボルまで100%復元可能！（任意の $k$ 個の生存シンボル $(x_{i_1}, y_{i_1}), \dots, (x_{i_k}, y_{i_k})$ からラグランジュ補間公式 $$P(x) = \sum_{j=1}^{k} y_{i_j} \prod_{\substack{m=1 \\ m \neq j}}^{k} \frac{x - x_{i_m}}{x_{i_j} - x_{i_m}}$$ によって元の多項式 $P(x)$ が一意に再構成されるため。）
• 位置が未知の任意誤り（Errors）なら：各エラーにつき「どの座標が壊れたか（位置）」と「いくらズレたか（誤り値）」の2つの未知数を特定する必要があるため、パリティ数のちょうど半分である $t = \lfloor (n - k) / 2 \rfloor$ シンボルまで100%訂正可能！

4.4 巡回符号としての生成多項式 $g(x)$ とバーレカンプ＝マッシー復号法

受信多項式を $y(x) = c(x) + e(x)$ としたとき、QRコードリーダーの内部では以下の4ステップの代数的復号アルゴリズムがわずか数ミリ秒で実行されています：

  flowchart TD
    R["受信語多項式 y(x) = c(x) + e(x)"] --> S1["Step 1: シンドローム計算<br/>S_j = y(α^j) = e(α^j) (j=1..2t)"]
    S1 --> Check{"すべての S_j = 0 か？"}
    Check -- "Yes" --> Done["エラーなし！先頭 k シンボルを出力"]
    Check -- "No" --> S2["Step 2: 誤り位置多項式 Λ(x) の決定<br/>（バーレカンプ＝マッシー法 / ユークリッド互除法）"]
    S2 --> S3["Step 3: チェン探索（Chien Search）<br/>Λ(α⁻ⁱ) = 0 となる根から誤り位置 i を特定"]
    S3 --> S4["Step 4: フォーニー（Forney）のアルゴリズム<br/>誤り評価多項式 Ω(x) から誤り値 e_i を算出"]
    S4 --> Fix["y(x) から e(x) を減算（XOR）して完全復元！"]

1. シンドローム計算（Syndrome Calculation）： 受信多項式 $y(x)$ に $\alpha^1, \dots, \alpha^{2t}$ を代入します。$c(\alpha^j) = 0$ なので、シンドローム $S_j$ は誤り多項式 $e(x) = \sum_{l=1}^\nu e_{i_l} x^{i_l}$（$\nu \le t$ 個の座標 $i_l$ で誤り値 $e_{i_l}$ が発生）の成分だけを抽出します： $$S_j = y(\alpha^j) = e(\alpha^j) = \sum_{l=1}^{\nu} Y_l X_l^j \quad (j = 1, 2, \dots, 2t)$$ ここで $X_l = \alpha^{i_l}$ は「誤り位置ナンバー」、$Y_l = e_{i_l}$ は「誤りの大きさ」です。この非線形連立方程式から未知の $X_l$ と $Y_l$ を直接解くのは困難に見えます。
2. 誤り位置多項式 $\Lambda(x)$ とバーレカンプ＝マッシー法（Berlekamp-Massey Algorithm）： ここでピーターソン（1960年）とバーレカンプ・マッシーが導入した天才的な仕掛けが、$X_l^{-1}$ を根に持つ誤り位置多項式（Error-Locator Polynomial） $\Lambda(x)$ です： $$\Lambda(x) \triangleq \prod_{l=1}^{\nu} (1 - X_l x) = 1 + \Lambda_1 x + \Lambda_2 x^2 + \dots + \Lambda_\nu x^\nu$$ $x = X_l^{-1}$ を代入すると $\Lambda(X_l^{-1}) = 0$ となる性質を使ってシンドロームと掛け合わせると、未知の係数 $\Lambda_1, \dots, \Lambda_\nu$ に関する完全な線形漸化式（ニュートンの恒等式 / 鍵方程式 Key Equation）に変換されます： $$S_{j + \nu} + \Lambda_1 S_{j + \nu - 1} + \dots + \Lambda_\nu S_j = 0 \quad (1 \le j \le 2t - \nu)$$ バーレカンプ＝マッシー法（または拡張ユークリッド互除法）は、このシンドローム数列を生成する最短の線形帰還シフトレジスタ（LFSR）を $O(t^2)$ 回のガロア体演算で求め、多項式 $\Lambda(x)$ を一瞬で決定します。
3. チェン探索（Chien Search）： 求まった $\Lambda(x)$ に、$\mathbb{F}_{2^8}$ の全要素 $\alpha^{-0}, \alpha^{-1}, \dots, \alpha^{-(n-1)}$ を順番に代入し、$\Lambda(\alpha^{-i}) = 0$ となるインデックス $i$ を探します。体要素は高々255個しかないため、全探索しても一瞬でどのバイト位置 $i_l$ が壊れているかが100%判明します。
4. フォーニーのアルゴリズム（Forney’s Algorithm）： 誤り位置が特定されれば、誤り評価多項式 $\Omega(x) \equiv S(x)\Lambda(x) \pmod{x^{2t}}$ と $\Lambda(x)$ の形式微分 $\Lambda'(x)$ を用いたフォーニーの公式： $$Y_l = -\frac{X_l \Omega(X_l^{-1})}{\Lambda'(X_l^{-1})}$$ によって「各破損バイトがどれだけズレたか（誤りビットパターン $Y_l$）」が算出され、受信バイトと XOR をとるだけで元のデータが1ビットの狂いもなく蘇ります。

4.5 QRコード・RAID-6・ボイジャーにおけるRS符号の実装

• QRコードの4段階の誤り訂正レベル： QRコードはデータを8ビット単位の $\text{GF}(2^8)$ シンボル（コード語）に分割し、用途に応じて以下の4段階のリード＝ソロモン符号化率を選択できます：
  • レベル L（Low）：全体の約 7% のコード語が汚損しても復元（パリティ比 約15%）
  • レベル M（Medium）：全体の約 15% のコード語が汚損しても復元（パリティ比 約30%）
  • レベル Q（Quartile）：全体の約 25% のコード語が汚損しても復元（パリティ比 約50%）
  • レベル H（High）：全体の約 30% のコード語が汚損しても復元（パリティ比 約60%） レベルHでは、ブロック全体の約60%をリード＝ソロモンのパリティシンボル（$n-k$）に割り当てるため、位置未知の汚れであってもその半分の $t = (n-k)/2 \approx 30\%$ の面積を企業ロゴやイラストで完全に潰してしまってなお、残りの70%から多項式を無傷で再構築できるのです！
• RAID-6 とクラウド分散ストレージ（Erasure Coding）： ハードディスクやSSDが故障する場合、どのドライブが応答しなくなったかはコントローラにとって位置が既知の「消失（Erasure）」です。したがって $2t$ ではなく $e = n - k$ がそのまま適用され、データ $k$ 台に対してわずか $2$ 台のパリティドライブ（$P$ と $Q$）を追加した RAID-6 は、任意の2台のドライブが同時に完全焼損しても100%データを復旧できます。さらに Google Cloud、AWS S3、Azure などの現代の巨大クラウドストレージでは、3重レプリケーション（容量300%消費）の代わりに、たとえば $[n=14, k=10]$ リード＝ソロモン消失訂正符号（容量わずか140%消費で、任意の4台のサーバーが同時ダウンしても無傷）が標準採用されています。
• ボイジャー探査機の「連接符号（Concatenated Codes）」： ボイジャー2号が天王星（1986年）や海王星（1989年）に到達した際、NASAはデイヴィッド・フォーニーが考案した連接符号化（Concatenated Coding）を採用しました。内符号（Inner Code）として熱雑音のランダムな1ビット誤りを軟判定ビタビ復号でかき集める畳み込み符号（Convolutional Code: $K=7, R=1/2$）を配置し、もしビタビ復号が限界を超えて連続的な復号ミス（バースト誤り）を吐き出しても、外符号（Outer Code）として待ち構える $[255, 223]$ リード＝ソロモン符号（情報223バイト＋パリティ32バイト、最大 $t=16$ バイト＝連続128ビットの塊まで完全訂正）がそれを一網打尽に消し去るという2段構えのアーキテクチャによって、数十億キロ彼方からの鮮明な画像伝送を成し遂げたのです。

5. シャノン限界への肉薄：LDPC符号・ターボ符号・Polar符号

5.1 45年間破られなかった「シャノン限界の壁」と確率伝播の革命

ハミング符号やリード＝ソロモン符号は代数的・幾何学的に極めて美しい符号ですが、実はシャノンが予言した究極の通信路容量 $C$（シャノン限界 $-1.59\,\text{dB}$）には、まだ数 $\text{dB}$（電力にして数倍）もの隔たりがありました。 シャノンの定理が要求する「数千〜数万ビットという巨大なブロック長 $n$」に対して、従来の代数的符号で厳密な最尤復号（Maximum Likelihood Decoding）を行おうとすると、計算量が $O(2^k)$ や高次の多項式時間で爆発してしまい、1990年代に入るまで「シャノン限界は実用的な計算量では絶対に到達できない理論上の蜃気楼だ」とすら言われていました。

この45年間の停滞を打ち破り、ついに人類をシャノン限界のすぐ目の前（わずか $0.0045\,\text{dB}$ 差！）へと到達させたのが、「疎なグラフ上の反復確率伝播（Iterative Belief Propagation）」と「通信路分極（Channel Polarization）」という2つのパラダイムシフトでした。

5.2 ロバート・ギャラガーのLDPC符号（1962年）とタナーグラフ上の確率伝播

実はシャノン限界を達成する鍵は、すでに1962年にMITのロバート・ギャラガー（Robert G. Gallager）の博士論文の中で発明されていました。それが低密度パリティ検査符号（LDPC: Low-Density Parity-Check Code）です。しかし、1962年当時のコンピュータの計算能力ではその真価を発揮できず、1993年にクロード・ベロウらがターボ符号（Turbo Codes）で反復復号の威力を実証したことをきっかけに、1990年代後半にデイヴィッド・マッカイ（David MacKay）らによって30年ぶりに「再発見」されるという劇的な歴史を辿りました。

LDPC符号の定義は驚くほどシンプルです。ブロック長 $n$ が数千〜数万ビットと非常に大きい一方で、パリティ検査行列 $\mathbf{H}_{m \times n}$ の中の $1$ の割合が極めて少ない（疎行列 Sparse Matrix：ほとんどが $0$）であるような線形符号です。

この疎な検査行列 $\mathbf{H}$ を、2種類の頂点を持つ2部グラフ——タナーグラフ（Tanner Graph）として表現します：

• 変数ノード（Variable Nodes $v_1, \dots, v_n$）：符号語の各ビット $c_j$ に対応（列に対応）。
• 検査ノード（Check Nodes $f_1, \dots, f_m$）：各パリティ検査式 $\sum_j H_{ij} c_j = 0 \pmod 2$ に対応（行に対応）。
• 行列の成分 $H_{ij} = 1$ のときに限り、変数ノード $v_j$ と検査ノード $f_i$ の間に枝（Edge）を結びます。

  flowchart TD
    subgraph Tanner["LDPCタナーグラフと確率伝播（Belief Propagation）"]
        direction TB
        V1["変数ノード v₁ (LLR L₁)"] --- C1["検査ノード f₁ (c₁⊕c₂⊕c₄=0)"]
        V2["変数ノード v₂ (LLR L₂)"] --- C1
        V2 --- C2["検査ノード f₂ (c₂⊕c₃⊕c₅=0)"]
        V3["変数ノード v₃ (LLR L₃)"] --- C2
        V4["変数ノード v₄ (LLR L₄)"] --- C1
        V4 --- C3["検査ノード f₃ (c₃⊕c₄⊕c₆=0)"]
        V5["変数ノード v₅ (LLR L₅)"] --- C2
        V6["変数ノード v₆ (LLR L₆)"] --- C3
        V3 --- C3
    end

（$L(c_i) = +10$ なら「ほぼ確実に $0$」、$L(c_i) = -0.1$ なら「ほんのわずかに $1$ っぽいが極めて曖昧」という確信度を表します。）

そして、タナーグラフの枝に沿って、変数ノードと検査ノードが互いの確信度メッセージをキャッチボールのように反復交換する確率伝播法（Belief Propagation / Sum-Product Algorithm）を実行します：

1. 検査ノードから変数ノードへのメッセージ $\mu_{f_a \to v_i}$：「あなた以外の隣接ビットたちの確信度から計算すると、パリティを偶数にするためにあなたが $0$ であるべき対数尤度比はこれだけです」というメッセージを、双曲線正接関数（$\tanh$ 則）によって伝えます： $$\mu_{f_a \to v_i} = 2 \operatorname{artanh}\!\left( \prod_{v_j \in N(f_a) \setminus \{v_i\}} \tanh\!\left(\frac{\mu_{v_j \to f_a}}{2}\right) \right)$$
2. 変数ノードから検査ノードへのメッセージ $\mu_{v_i \to f_a}$：「通信路から直接受け取った自分の初期LLR $L_{\text{ch}}(v_i)$ に、他のすべての検査ノードから届いた助言を足し合わせると、私の最新の確信度はこれです」と返答します： $$\mu_{v_i \to f_a} = L_{\text{ch}}(v_i) + \sum_{f_b \in N(v_i) \setminus \{f_a\}} \mu_{f_b \to v_i}$$

グラフが疎（Low-Density）であるため、短いループ（サイクル）が少なく、各ノードは1回の反復がわずか数回の足し算・掛け算（全体の計算量 $O(n)$！）で完結します。数十回の反復（イテレーション）を回すうちに、確信度の高いビットが曖昧なビットを助け起こし、ドミノ倒しのように全数万ビットの誤りが一斉に解消されます。2001年、Chung, Forney, Richardson, Urbanke らは、非正則LDPC符号の次数分布を密度進化法（Density Evolution）で最適化することで、シャノン限界からわずか $0.0045\,\text{dB}$ 以内で動作する符号を実際に構築してみせました。

5.3 エルダル・アリカンのPolar符号（2009年）：通信路分極によるシャノン容量の厳密達成

LDPC符号が実験的・漸近的にシャノン限界に迫ったのに対し、2009年、トルコ・ビルケント大学のエルダル・アリカン（Erdal Arıkan）教授は、1948年のシャノンの問題提起から実に61年を経て、「数学的に証明可能な形で、かつ $O(N \log N)$ の低計算量で厳密にシャノン容量 $C$ を達成する史上初の構成的符号」——Polar符号（Polar Codes：分極符号）を発表し、符号理論の歴史を塗り替えました。

受信側で出力 $(y_1, y_2)$ を受け取ったとき、次の2つの仮想的な合成通信路を考えます：

• 劣化した通信路 $W^-$：出力 $(y_1, y_2)$ だけから $u_1$ を推定する通信路。$u_1 = x_1 \oplus x_2$ には両方の通信路のノイズが重なるため、元の通信路 $W$ よりも必ず悪化（ノイズが増大）します。
• 向上した通信路 $W^+$：すでに $u_1$ が正しく分かったという条件のもとで、$(y_1, y_2, u_1)$ から $u_2$ を推定する通信路。$x_1 \oplus u_1 = u_2$ と $x_2 = u_2$ の2つの独立な観測から $u_2$ を推定できるため、元の通信路 $W$ よりも必ず良化（ノイズが減少）します。

この $2\times 2$ の分極操作を、クロネッカー積 $\mathbf{G}_N = \mathbf{B}_N \begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix}^{\otimes m}$ によって $N = 2^m$ 個の通信路へと再帰的に繰り返していくと（バタフライ構造）、$N \to \infty$ の極限において驚くべき現象——分極（Polarization）が起こります：

• 全体のちょうど $C = I(W)$ の割合（約 $N \cdot C$ 個）の仮想通信路は、容量が $1$（一切エラーが起きない完全無雑音通信路！）へと収束し、
• 残りの $1 - C$ の割合（約 $N(1-C)$ 個）の仮想通信路は、容量が $0$（まったく情報が通らない完全雑音通信路！）へと収束し、中間の曖昧な通信路が消滅するのです！

  flowchart TD
    subgraph Polar["Polar符号の通信路分極（Channel Polarization）"]
        W["N 個の同一な雑音通信路 W（各容量 C = 0.6）"] --> Kron["バタフライ変換 G_N = B_N F^{⊗m}<br/>（再帰的な悪化 W⁻ と良化 W⁺ の分裂）"]
        Kron --> Good["上位 N·C 個の分極通信路<br/>容量 I(W_i) → 1.0（完全無雑音！）"]
        Kron --> Bad["下位 N(1-C) 個の分極通信路<br/>容量 I(W_i) → 0.0（完全雑音）"]
        Good --> Info["情報ビット u_i をそのまま配置（Unfrozen Bits）"]
        Bad --> Frozen["既知の固定値 0 に凍結（Frozen Bits）"]
    end

通信路が $1$ か $0$ に二極化してしまえば、符号化は拍子抜けするほど簡単です。容量が $1$ に近づいた上位 $K \approx N \cdot C$ 個の良質な通信路（Unfrozen Bits）にだけ生の情報ビットを流し込み、容量が $0$ に落ちた下位 $N - K$ 個の劣悪な通信路には、送受信機があらかじめ合意した固定値 $0$（凍結ビット Frozen Bits）をセットしておくだけです。受信側は逐次除去復号（SC: Successive Cancellation Decoding）またはリスト復号（SCL: Successive Cancellation List Decoding + CRC）を $O(N \log N)$ で実行するだけで、シャノン容量 $C$ を理論通り達成できます。

5.4 主要な誤り訂正符号の体系的比較

これまで解説してきた誤り訂正符号の数学的基盤、復号アルゴリズム、および現代社会での主な応用先を一覧表にまとめます。

6. Pythonによる実装検証：ハミング $(7,4)$ 符号とガロア体リード＝ソロモン符号

理論の美しさを実際に手で触れて確かめるため、Python（標準ライブラリのみ）で以下の2つを完全実装して検証しましょう。

1. ハミング $(7,4)$ 符号の生成行列符号化とシンドローム復号（全ビット位置の反転エラーがシンドロームから一発で特定・修復される様子）
2. 有限体 $\mathbb{F}_q$ 上のリード＝ソロモン符号（多項式評価と連立方程式／バーレカンプ＝マッシー原理によるエラー位置・エラー値の完全特定）：メッセージ全体の30%近くが未知のノイズで破壊されても、1ビットの狂いもなく元の文字列が復元される様子を確認します。

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170

from typing import List, Tuple

# =====================================================================
# Part 1: ハミング (7, 4) 符号の符号化とシンドローム復号
# =====================================================================
def hamming74_demo() -> None:
    print("=== [1] Hamming (7,4) Code Verification ===")
    # 組織符号形式の生成行列 G (4x7) と パリティ検査行列 H (3x7)
    # G = [I_4 | P], H = [P^T | I_3] over GF(2)
    G = [
        [1, 0, 0, 0, 1, 1, 0],
        [0, 1, 0, 0, 1, 0, 1],
        [0, 0, 1, 0, 0, 1, 1],
        [0, 0, 0, 1, 1, 1, 1],
    ]
    H = [
        [1, 1, 0, 1, 1, 0, 0],
        [1, 0, 1, 1, 0, 1, 0],
        [0, 1, 1, 1, 0, 0, 1],
    ]

    msg = [1, 0, 1, 1]  # 送信したい4ビット情報
    # 符号化: c = m * G mod 2
    codeword = [sum(msg[i] * G[i][j] for i in range(4)) % 2 for j in range(7)]
    print(f"Original 4-bit Message : {msg}")
    print(f"Encoded 7-bit Codeword : {codeword}")

    # 第2ビット（0-indexedで index=2）をノイズで反転させる
    received = codeword.copy()
    error_idx = 2
    received[error_idx] ^= 1
    print(f"Received (bit {error_idx} flipped): {received}")

    # シンドローム計算: s = H * y^T mod 2
    syndrome = [sum(H[r][c] * received[c] for c in range(7)) % 2 for r in range(3)]
    # H のどの列ベクトルが syndrome と一致するか照合
    detected_col = -1
    for c in range(7):
        if [H[r][c] for r in range(3)] == syndrome:
            detected_col = c
            break

    corrected = received.copy()
    if detected_col != -1:
        corrected[detected_col] ^= 1
    decoded_msg = corrected[:4]
    print(f"Syndrome Vector s      : {syndrome} -> Matches Column {detected_col}")
    print(f"Corrected Codeword     : {corrected}")
    print(f"Decoded 4-bit Message  : {decoded_msg} (Success: {decoded_msg == msg})\n")


# =====================================================================
# Part 2: 有限体 GF(p) 上のリード＝ソロモン符号 (多項式評価と未知誤り訂正)
# =====================================================================
PRIME = 257  # 1バイト(0..255)をすべて表現できる最小の素数体 GF(257)

def gf_add(a: int, b: int) -> int:
    return (a + b) % PRIME

def gf_sub(a: int, b: int) -> int:
    return (a - b) % PRIME

def gf_mul(a: int, b: int) -> int:
    return (a * b) % PRIME

def gf_inv(a: int) -> int:
    if a == 0:
        raise ZeroDivisionError("Inverse of 0 in GF(257)")
    return pow(a, PRIME - 2, PRIME)  # フェルマーの小定理 a^(p-2) ≡ a^(-1) mod p

def poly_eval(coeffs: List[int], x: int) -> int:
    # P(x) = coeffs[0] + coeffs[1]*x + ... をホーナー法で評価
    res = 0
    for c in reversed(coeffs):
        res = gf_add(gf_mul(res, x), c)
    return res

def gf_gaussian_solve(A: List[List[int]], b: List[int]) -> List[int]:
    # GF(257) 上の連立一次方程式 A * x = b をガウス消去法で解く
    n = len(b)
    M = [row[:] + [b[i]] for i, row in enumerate(A)]
    for col in range(n):
        pivot = col
        while pivot < n and M[pivot][col] == 0:
            pivot += 1
        M[col], M[pivot] = M[pivot], M[col]
        inv_p = gf_inv(M[col][col])
        for j in range(col, n + 1):
            M[col][j] = gf_mul(M[col][j], inv_p)
        for row in range(n):
            if row != col and M[row][col] != 0:
                factor = M[row][col]
                for j in range(col, n + 1):
                    M[row][j] = gf_sub(M[row][j], gf_mul(factor, M[col][j]))
    return [M[i][n] for i in range(n)]

def lagrange_interpolate(points: List[Tuple[int, int]], k: int) -> List[int]:
    # k 個の正しい評価点 (x_i, y_i) から次数 < k の多項式係数を復元
    V = [[pow(x, deg, PRIME) for deg in range(k)] for x, _ in points[:k]]
    y_vals = [y for _, y in points[:k]]
    return gf_gaussian_solve(V, y_vals)

def reed_solomon_berlekamp_welch_decode(
    eval_points: List[int], received: List[int], k: int, t: int
) -> List[int]:
    # Welch-Berlekamp アルゴリズムによる [n, k] RS符号の未知誤り訂正:
    # 次数 t のモニック誤り位置多項式 E(x) = e_0 + e_1 x + ... + x^t と
    # 次数 < k + t の多項式 Q(x) に対し、すべての i で Q(alpha_i) = y_i * E(alpha_i)
    # を満たす線形方程式を解き、P(x) = Q(x) / E(x) として元の情報多項式を完全復元する。
    n = len(eval_points)
    # 未知数: Q(x) の係数 (k + t 個) と E(x) の下位係数 e_0..e_{t-1} (t 個) の計 k + 2t = n 個
    A_mat = []
    b_vec = []
    for i in range(n):
        x = eval_points[i]
        y = received[i]
        # Q(x) - y * (e_0 + e_1*x + ... + e_{t-1}*x^{t-1}) = y * x^t
        row = [pow(x, deg, PRIME) for deg in range(k + t)]
        for deg in range(t):
            row.append(gf_sub(0, gf_mul(y, pow(x, deg, PRIME))))
        A_mat.append(row)
        b_vec.append(gf_mul(y, pow(x, t, PRIME)))

    sol = gf_gaussian_solve(A_mat, b_vec)
    Q_coeffs = sol[: k + t]
    E_coeffs = sol[k + t :] + [1]  # 最高次係数 x^t は 1

    # E(alpha_i) == 0 となる根（破損した座標）を特定して除外し、正常な k 点で補間
    valid_points = []
    error_positions = []
    for i, x in enumerate(eval_points):
        if poly_eval(E_coeffs, x) == 0:
            error_positions.append(i)
        else:
            valid_points.append((x, received[i]))

    print(f"Detected Corrupted Symbol Indices (E(x_i) = 0): {error_positions}")
    return lagrange_interpolate(valid_points, k)

def reed_solomon_demo() -> None:
    print("=== [2] Reed-Solomon [n=15, k=9, d_min=7] Code Verification ===")
    text = "VOYAGER-1"  # k = 9 シンボル (バイト)
    k = len(text)
    t = 3  # 最大 t = 3 シンボル（位置未知）の誤りを訂正可能
    n = k + 2 * t  # n = 15 シンボル

    msg_coeffs = [ord(ch) for ch in text]
    eval_points = list(range(1, n + 1))  # 評価点 alpha_1..alpha_15 = 1..15

    # 符号化: 多項式 P(x) を 15 個の点で評価
    codeword = [poly_eval(msg_coeffs, x) for x in eval_points]
    print(f"Original Message (k={k}) : '{text}' -> {msg_coeffs}")
    print(f"RS Encoded (n={n} syms) : {codeword}")

    # 15シンボル中3シンボル（20%の領域）を完全にデタラメな値に破壊（バースト誤り模擬）
    corrupted = codeword.copy()
    corrupted[2] = 250
    corrupted[7] = 13
    corrupted[12] = 99
    print(f"Corrupted Received     : {corrupted} (Errors at idx 2, 7, 12)")

    # Welch-Berlekamp アルゴリズムによる復号
    recovered_coeffs = reed_solomon_berlekamp_welch_decode(eval_points, corrupted, k, t)
    recovered_text = "".join(chr(c) for c in recovered_coeffs)
    print(f"Recovered Coefficients : {recovered_coeffs}")
    print(f"Recovered Text         : '{recovered_text}' (Exact Match: {recovered_text == text})")

if __name__ == "__main__":
    hamming74_demo()
    reed_solomon_demo()

このコードを実行すると、以下のような出力が得られ、ハミング $(7,4)$ 符号による単一ビット反転の即時特定と、リード＝ソロモン $[15, 9, 7]$ 符号において全15シンボル中3シンボル（インデックス 2, 7, 12）が跡形もなく破壊されても、誤り位置多項式 $E(x)$ の根として破損箇所が自動特定され、元の文字列 'VOYAGER-1' が1ビットの狂いもなく完全復元されることが確認できます：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

=== [1] Hamming (7,4) Code Verification ===
Original 4-bit Message : [1, 0, 1, 1]
Encoded 7-bit Codeword : [1, 0, 1, 1, 0, 1, 0]
Received (bit 2 flipped): [1, 0, 0, 1, 0, 1, 0]
Syndrome Vector s      : [0, 1, 1] -> Matches Column 2
Corrected Codeword     : [1, 0, 1, 1, 0, 1, 0]
Decoded 4-bit Message  : [1, 0, 1, 1] (Success: True)

=== [2] Reed-Solomon [n=15, k=9, d_min=7] Code Verification ===
Original Message (k=9) : 'VOYAGER-1' -> [86, 79, 89, 65, 71, 69, 82, 45, 49]
RS Encoded (n=15 syms) : [121, 90, 219, 107, 16, 179, 102, 232, 92, 211, 213, 181, 144, 15, 68]
Corrupted Received     : [121, 90, 250, 107, 16, 179, 102, 13, 92, 211, 213, 181, 99, 15, 68] (Errors at idx 2, 7, 12)
Detected Corrupted Symbol Indices (E(x_i) = 0): [2, 7, 12]
Recovered Coefficients : [86, 79, 89, 65, 71, 69, 82, 45, 49]
Recovered Text         : 'VOYAGER-1' (Exact Match: True)

7. 深掘り考察：なぜ現代の5GやSSDは「RS符号」から「LDPC・Polar符号」へ移行したのか？

ここで1つの重要な疑問が浮かびます。「リード＝ソロモン符号がシングルトン限界 $d_{\min} = n - k + 1$ を達成する究極のMDS符号であるならば、なぜ現代の 5G 通信や Wi-Fi 6/7、最新の NVMe SSD はリード＝ソロモン符号ではなく LDPC 符号や Polar 符号を使っているのか？」という点です。

ここには、「代数的最小距離（ハード判定限界）」と「シャノンの軟判定情報量（確率的典型集合）」の間の深いギャップが存在します。

1. アルファベットサイズ $q$ とブロック長 $n$ の制約： リード＝ソロモン符号は評価点 $\alpha_1, \dots, \alpha_n$ を体 $\mathbb{F}_q$ の異なる要素から選ぶため、符号長 $n$ が体の要素数 $q = 2^m$ を超えられない（$n \le 2^m$）という宿命的な制約があります。$\text{GF}(2^8)$ ならばブロック長は最大 $255$ バイト（$2040$ ビット）止まりです。一方、シャノンの通信路符号化定理において大数の法則を極限まで効かせてシャノン限界に漸近するためには、数千〜数万ビットの巨大なブロック長と、ビット単位のきめ細かな確率連携が不可欠です。
2. 硬判定（Hard-Decision）による情報損失 $2\,\text{dB}$ のペナルティ： 従来のリード＝ソロモン復号器は、アナログ受信電圧を最初に「このバイトは 0x4A である」と0/1に量子化（硬判定）してから代数演算に入ります。しかし、連続的なガウス雑音通信路（AWGN）において、アナログの確信度（軟判定値 LLR）を捨てて硬判定を行った瞬間に、通信路容量が理論上約 $2\,\text{dB}$ も目減りしてしまうことが情報理論から証明されています。LDPC符号やPolar符号は、最初から最後まで連続値の対数尤度比（LLR）のままタナーグラフやバタフライ回路の上で確率計算を行うため、この $2\,\text{dB}$ の軟判定利得（Soft-Decision Gain）を丸ごと回収できるのです。
3. SSD（3D NANDフラッシュメモリ）における微細化と多値化（TLC/QLC）： かつてのSLC/MLC世代のSSDでは、BCH符号やRS符号の硬判定復号で十分でした。しかし、1つのメモリセルに3ビット（8段階の電圧閾値：TLC）や4ビット（16段階の電圧閾値：QLC）を詰め込む現代の3D NANDフラッシュメモリでは、隣のセルからの電荷干渉や経年劣化によって電圧分布が重なり合い、生ビット誤り率（RBER）が $10^{-2}$ 近くにまで悪化します。そのため現代のSSDコントローラは、まず硬判定LDPC復号を試し、それでも解けない場合はセルの読み出し電圧をわずかにずらして複数回読み出すことで各ビットの軟判定LLRを生成し、確率伝播法（Belief Propagation）を回すことで $10^{-16}$ 以下の訂正不能ビット誤り率（UBER）を実現しています。

一方で、パケット単位の欠損（消失）や2次元画像上の局所的な汚れ（QRコード）、HDD/SSD単位の丸ごと故障（RAID-6・クラウドオブジェクトストレージ）のように、「シンボル（バイトやチャンク）単位でバースト状の破壊・消失が起きる場面」では、今なおMDS性を持つリード＝ソロモン符号が人類最強・理論上限の地位に君臨しています。すなわち、物理層の熱雑音には LDPC / Polar 符号、上位層や空間層のバースト欠損・消失にはリード＝ソロモン符号という「適材適所の階層的共存」こそが、現代の情報インフラを支える真の姿なのです。

8. まとめ：ノイズに満ちた物理宇宙で「完全な情報」を紡ぐ数学の力

熱力学第二法則が支配する私たちの物理世界では、いかなる通信路も、いかなる記憶媒体も、熱雑音・量子ゆらぎ・宇宙線・経年劣化というエントロピー増大の嵐から逃れることはできません。

しかし、人類は過去75年間にわたり、以下の4つの数学的マイルストーンを築き上げることで、不完全な物理現象の上に「完全無欠なデジタル情報空間」を打ち立てました：

1. クロード・シャノン（1948年）は、通信路容量 $C$（BSCでは $1 - H_2(p)$、AWGNでは $B\log_2(1+S/N)$）と究極のシャノン限界 $E_b/N_0 = -1.59\,\text{dB}$ を導出し、「速度を犠牲にすることなくエラー率をゼロにできる」という希望の道標を打ち立てました。
2. リチャード・ハミング（1950年）は、$n$ 次元超立方体 $\mathbb{F}_2^n$ 上のハミング距離 $d_{\min} \ge 2t + e + 1$ とシンドローム $\mathbf{s} = \mathbf{H}\mathbf{y}^T$ を導入し、機械が自ら誤りを検出し修復する幾何学的アルゴリズムを創始しました。
3. リードとソロモン（1960年）は、ガロア体 $\mathbb{F}_{2^m}$ 上の次数 $< k$ の多項式が任意の $k$ 点で一意に定まるという代数学の奇跡を応用し、シングルトン限界 $d_{\min} = n - k + 1$ を達成するMDS符号によって、QRコードの汚れから深宇宙探査・クラウドストレージの障害までを克服しました。
4. ギャラガー（1962年）とアリカン（2009年）は、タナーグラフ上の確率伝播（LDPC符号）と通信路分極（Polar符号）によって、ついに人類をシャノン限界そのものへと到達させ、現代の5G通信やWi-Fi、SSDの超高密度記録を実現しました。

あなたが次に街角で一部が欠けたQRコードをスマートフォンで読み取るとき、あるいははるか星間空間を旅するボイジャーの信号に思いを馳せるとき、その背後ではガロア体上の多項式と超立方体上のタナーグラフが、ミリ秒以下の静寂の中でノイズを消し去り、情報を完全な姿へと蘇らせているのです。