シンドローム復号と標準配列 — 線形符号はどう誤りを特定するか

7ビットのデータが届きました。そのうち1ビットが、通信路のノイズでひっくり返っています。どのビットが化けたのか、受信側は送信データを知らないのに、どうやって突き止めればよいのでしょうか。

素朴に考えれば「あり得る送信データを全部試して、いちばん近いものを選ぶ」という手が浮かびます。しかしこの方法は、情報ビットが $k$ 個あれば $2^k$ 通りの候補と照合することになります。$k = 4$ なら16回で済みますが、実用的な符号の $k = 1000$ では $2^{1000}$ 回。宇宙の年齢を使っても終わりません。

ところが線形符号には、この探索を劇的に短縮する仕掛けがあります。受信語 $\bm{r}$ に検査行列 $\bm{H}$ を掛けて得られる シンドローム（syndrome）という短いベクトルが、送信された符号語には一切依存せず、混入した誤りパターンだけを反映する のです。$k = 1000$ の符号でも、シンドロームは $n – k$ ビットしかありません。誤りの「指紋」だけを取り出せる、というのがこの仕組みの核心です。

シンドローム復号は、地味に見えて現代の情報インフラの至るところで動いています。

• メモリのECC: サーバー用DIMMのSEC-DED（1ビット訂正・2ビット検出）は、まさにシンドロームからビット位置を直読する回路です。宇宙線由来のソフトエラーを、CPUが気づかないうちに毎日訂正しています
• 深宇宙通信・衛星通信: 送信電力が限られる探査機からのテレメトリでは、誤り訂正なしでは画像1枚まともに届きません。BCH符号やリード・ソロモン符号の復号も、出発点はシンドロームの計算です
• QRコード・光ディスク: 汚れや傷で読めなくなった記号を、シンドロームから割り出した誤り位置多項式で復元しています

そして、シンドロームがなぜ誤りだけを写し取るのか、なぜ「同じシンドロームの受信語をひとまとめにする」ことが最尤復号と一致するのか——この2つを説明する枠組みが、本記事の主役である 標準配列（standard array）です。標準配列は $2^n$ 個の全受信語を $2^{n-k}$ 行 $\times$ $2^k$ 列の表に並べ替えたもので、「復号とは何をしているのか」を一枚の表で完全に可視化してくれます。

まず、これから扱う仕組みの全体像を一枚の絵にしておきます。

左から右へ、情報4ビットが符号語7ビットになり、通信路で1ビットが化け、受信側は7ビットをたった3ビットのシンドロームに圧縮してから表を1回引くだけで誤り位置を突き止めています。図の下段の赤枠が全体の心臓部で、$\bm{s} = (\bm{c}+\bm{e})\bm{H}^{\mathsf{T}}$ を展開すると符号語の項 $\bm{c}\bm{H}^{\mathsf{T}}$ が消え、シンドロームが誤り $\bm{e}$ だけの関数になることを示しています。この1行が成り立つおかげで、「16通りの符号語のどれが送られたか」を当てる問題が「どんな誤りが起きたか」を当てる問題に置き換わるのです。

本記事の内容

• シンドローム $\bm{s} = \bm{r}\bm{H}^{\mathsf{T}} = \bm{e}\bm{H}^{\mathsf{T}}$ の導出と、送信語に依存しないことの証明
• 同じシンドロームを持つ受信語の集合が コセット（剰余類）になることの証明
• 標準配列の構成手順と、コセット代表（コセットリーダー）の選び方
• BSC上で「最小重みの誤りパターンを選ぶこと」＝「最尤復号」であることの導出
• ハミング(7,4)符号の完全なシンドローム表と、全8行の標準配列の掲載
• 非零シンドローム7通りが $\bm{H}$ の列と1対1対応するため、誤り位置が直読できることの検証
• Pythonによる標準配列の全数構成、シンドローム表の自動生成、BSC上での1万回試行によるBER測定

前提知識

この記事を読む前に、以下の記事を読んでおくと理解が深まります。

• 誤り訂正符号とは？仕組みと種類をわかりやすく解説 — 冗長性による誤り訂正の基本的な考え方
• 線形ブロック符号とは？生成行列と検査行列から理解する — 生成行列 $\bm{G}$、検査行列 $\bm{H}$、最小距離の定義
• ハミング符号の理論と誤り訂正能力 — 本記事で題材にする(7,4)符号の構成原理

誤りを「探す」のではなく「絞り込む」

まず、シンドロームという道具がどういう発想から生まれたのかを掴んでおきましょう。

健康診断を思い浮かべてください。医師は患者の全身をくまなく調べるわけではありません。血液検査でいくつかの数値を測り、その数値パターンから病気を絞り込みます。数値がすべて基準内なら「異常なし」。特定の数値だけが跳ね上がっていれば「この臓器が怪しい」と分かる。少数の測定値に、体全体の異常が凝縮されて現れる わけです。

シンドロームはまさにこれです。実際、syndrome という語は医学用語の「症候群」そのもので、符号理論の文献でこの言葉が使われるのは偶然ではありません。受信した $n$ ビットをそのまま眺めても、どこが化けたのかは分かりません。しかし $n – k$ 個の「検査値」を計算すると、そのパターンが誤りの所在を語り出す——これがシンドローム復号の発想です。

この「絞り込み」がどれだけ効くのかを、素朴な総当りと比べておきましょう。

赤い棒は「全符号語と照合する」場合の候補数 $2^k$ の対数、緑の棒はシンドローム表の行数 $2^{n-k}$ の対数です。$[1024, 1013]$ 符号では赤が $2^{1013}$ と天文学的な高さになる一方、緑はわずか2048行に収まっています。符号長を伸ばして効率を上げても検査ビット数 $n-k$ はほとんど増えないため、シンドロームという「検査値」を見る限り作業量は現実的な範囲に留まる、という構図が読み取れます。

ここで決定的に重要な性質が一つあります。健康診断の比喩で言えば、検査値は「その人が誰であるか」には依存せず、「どんな異常があるか」だけで決まる という性質です。符号の言葉に直せば、シンドロームは送信された符号語 $\bm{c}$ に依存せず、混入した誤りパターン $\bm{e}$ だけで決まります。この性質があるからこそ、「シンドロームを見る→誤りパターンを推定する→受信語から取り除く」という一直線の手続きが成立します。

もしシンドロームが送信語にも依存していたら、この手続きは崩壊します。「検査値が高いのは病気のせいか、それとももともとの体質か」が区別できなければ、診断は成り立ちません。次のセクションでは、この「送信語に依存しない」という性質が線形符号の定義からどう自動的に出てくるのかを、丁寧に導きます。

線形符号の記号を整理する

導出に入る前に、使う記号を確定させておきます。

体は $\mathbb{F}_2 = \{0, 1\}$、つまり足し算がXOR（$1 + 1 = 0$）の2元体です。$[n, k]$ 線形符号 $\mathcal{C}$ とは、$\mathbb{F}_2^n$ の $k$ 次元部分空間のことでした。要素の個数は $|\mathcal{C}| = 2^k$ 個です。

生成行列 $\bm{G}$（$k \times n$）は、情報ベクトル $\bm{m} \in \mathbb{F}_2^k$ を符号語に写す行列です。

$$ \begin{equation} \bm{c} = \bm{m}\bm{G} \end{equation} $$

本記事では行ベクトル規約を採ります。つまりベクトルは横に寝ていて、行列は右から掛かります。教科書によっては列ベクトル規約（$\bm{c} = \bm{G}^{\mathsf{T}}\bm{m}$）を使いますが、シンドローム復号の議論では行ベクトル規約のほうが式が短くなるので、こちらを使います。

検査行列 $\bm{H}$（$(n-k) \times n$）は、符号語であることの判定条件を与える行列です。

$$ \begin{equation} \bm{c} \in \mathcal{C} \iff \bm{c}\bm{H}^{\mathsf{T}} = \bm{0} \end{equation} $$

$\bm{H}$ の各行が1本のパリティ検査式に対応します。$\bm{H}$ の $i$ 行 $j$ 列成分が1なら「第 $i$ 番目の検査式に第 $j$ ビットが参加する」という意味です。$\bm{G}$ と $\bm{H}$ の間には直交関係

$$ \begin{equation} \bm{G}\bm{H}^{\mathsf{T}} = \bm{O} \end{equation} $$

が成り立ちます。実際、任意の $\bm{m}$ に対して $\bm{c} = \bm{m}\bm{G}$ が符号語であるためには $\bm{m}\bm{G}\bm{H}^{\mathsf{T}} = \bm{0}$ がすべての $\bm{m}$ で成り立つ必要があり、これは $\bm{G}\bm{H}^{\mathsf{T}} = \bm{O}$ と同値だからです。

通信路モデル は二元対称通信路（BSC: Binary Symmetric Channel）とします。各ビットが独立に確率 $p$ で反転し、$p < 1/2$ を仮定します。送信符号語 $\bm{c}$ に対し、誤りパターン $\bm{e} \in \mathbb{F}_2^n$（反転した位置に1が立つベクトル）が加わって

$$ \begin{equation} \bm{r} = \bm{c} + \bm{e} \end{equation} $$

が受信されます。$\mathbb{F}_2$ では加算と減算が同じなので、$\bm{e} = \bm{r} – \bm{c} = \bm{r} + \bm{c}$ と書き直せる点にも注意しておきましょう。この「引き算＝足し算」という性質は、以降の変形をとても軽くしてくれます。

重み $\mathrm{wt}(\bm{x})$ はベクトル $\bm{x}$ に含まれる1の個数（ハミング重み）、距離 $d(\bm{x}, \bm{y}) = \mathrm{wt}(\bm{x} + \bm{y})$ はハミング距離です。誤りパターンの重み $\mathrm{wt}(\bm{e})$ は「何ビット化けたか」を表します。BSCで $p$ が小さければ、重みの小さい誤りほど起こりやすい——この当たり前の事実が、あとで最尤復号の正体を暴く鍵になります。

記号が揃いました。いよいよ、シンドロームが誤りパターンだけの関数になることを示します。

シンドロームの定義と「送信語に依存しない」ことの証明

受信語 $\bm{r}$ に対し、シンドローム を次で定義します。

$$ \begin{equation} \bm{s} = \bm{r}\bm{H}^{\mathsf{T}} \in \mathbb{F}_2^{n-k} \end{equation} $$

長さは $n – k$ ビット。$n$ ビットの受信語を $n – k$ ビットに圧縮した「検査値」です。$[7, 4]$ 符号なら、7ビットを3ビットに圧縮していることになります。

さて、$\bm{r} = \bm{c} + \bm{e}$ を代入します。行列積は分配法則を満たすので、

$$ \begin{equation} \bm{s} = (\bm{c} + \bm{e})\bm{H}^{\mathsf{T}} = \bm{c}\bm{H}^{\mathsf{T}} + \bm{e}\bm{H}^{\mathsf{T}} \end{equation} $$

と2項に分かれます。ここで第1項に注目してください。$\bm{c}$ は符号語ですから、検査行列の定義 $(2)$ より $\bm{c}\bm{H}^{\mathsf{T}} = \bm{0}$ です。この第1項が消えることが、すべての出発点です。したがって

$$ \begin{equation} \bm{s} = \bm{0} + \bm{e}\bm{H}^{\mathsf{T}} = \bm{e}\bm{H}^{\mathsf{T}} \end{equation} $$

を得ます。式 $(7)$ の右辺には $\bm{c}$ がどこにも現れていません。つまり シンドロームは、何が送られたかとは無関係に、何が起きたかだけで決まる のです。

この主張は数値でも直接確かめられます。16通りの符号語すべてについて、同じ誤りを混ぜたときのシンドロームを並べてみましょう。

横軸は送信された符号語16通り、縦軸はシンドロームの10進値です。第3ビットを反転させた場合（赤）はどの符号語を送っても $s = 111$、第5ビットなら（青）どれでも $s = 100$、誤りなしなら（緑）どれでも $s = 000$ と、3本とも定規で引いたように水平です。もしシンドロームが送信語にも依存していれば、この線は符号語ごとに上下に暴れるはずでした。式 $(7)$ が主張する「送信語非依存性」が、視覚的にそのまま現れています。

この一行の帰結は驚くほど強力です。$2^k$ 個ある符号語のうちどれが送られたかを推定する問題が、$\bm{e}$ だけを推定する問題にすり替わりました。しかも $\bm{e}$ が分かれば、送信語は $\hat{\bm{c}} = \bm{r} + \hat{\bm{e}}$ で即座に復元できます（$\mathbb{F}_2$ では引き算＝足し算なので、足すだけで取り除ける）。

もう一つ、定義から直ちに分かる基本性質を確認しておきます。

$$ \begin{equation} \bm{s} = \bm{0} \iff \bm{r} \in \mathcal{C} \end{equation} $$

シンドロームがゼロなら、受信語はそのまま符号語です。ただしこれは「誤りが無かった」ことを意味しません。誤りパターン $\bm{e}$ 自身が符号語だった場合（$\bm{e} \in \mathcal{C}$、$\bm{e} \neq \bm{0}$）にも $\bm{s} = \bm{0}$ になります。このとき復号器は「異常なし」と判断し、誤った符号語をそのまま出力してしまいます。これが 検出不能誤り（undetectable error）です。誤り訂正符号が万能でない理由の一つがここにあります。

さらに、シンドロームには線形符号らしい性質があります。$\bm{e}$ が単位ベクトル $\bm{e}_i$（第 $i$ 成分だけ1）のとき、$\bm{e}_i\bm{H}^{\mathsf{T}}$ は $\bm{H}^{\mathsf{T}}$ の第 $i$ 行、すなわち $\bm{H}$ の第 $i$ 列 に等しくなります。

$$ \begin{equation} \bm{e}_i \bm{H}^{\mathsf{T}} = \bm{h}_i^{\mathsf{T}}, \quad \bm{h}_i = \bm{H} \text{ の第 } i \text{ 列} \end{equation} $$

したがって1ビット誤りのシンドロームは $\bm{H}$ の列そのもの。$\bm{H}$ の列がすべて相異なるように設計しておけば、1ビット誤りのシンドロームからその位置が一意に決まります。この事実が、後で見るハミング符号の「シンドロームから位置が直読できる」性質の正体です。より一般に、$i$ と $j$ の2ビットが誤ったなら $\bm{s} = \bm{h}_i^{\mathsf{T}} + \bm{h}_j^{\mathsf{T}}$ という具合に、誤り位置に対応する列の和がシンドロームになります。

この対応を、本記事で使う具体的な検査行列で見ておきます。

左は検査行列 $\bm{H}$ を画像として並べたもので、7つの列 $\bm{h}_1, \dots, \bm{h}_7$ がすべて異なるパターンになっていることが一目で分かります。右の棒グラフは、第 $i$ ビットだけが誤ったときのシンドロームを10進値で示したもので、高さは 6, 3, 7, 5, 4, 2, 1 と並び、同じ高さの棒が1本もありません。式 $(9)$ の $\bm{e}_i\bm{H}^{\mathsf{T}} = \bm{h}_i^{\mathsf{T}}$ が、そのまま「誤り位置とシンドロームの1対1対応」になっていることの視覚的な証拠です。

ここまでで「シンドロームは誤りの指紋である」ことは分かりました。しかし指紋から犯人が一意に決まるとは限りません。$\bm{s} = \bm{e}\bm{H}^{\mathsf{T}}$ という方程式は $\bm{e}$ について未知数 $n$ 個・式 $n-k$ 個の劣決定系であり、解は $2^k$ 個もあるからです。この $2^k$ 個の候補がどんな構造をしているのか——次にそれを調べます。

同じシンドロームを持つ受信語はコセットをなす

$2^n$ 個ある全受信語を、シンドロームの値でグループ分けしてみましょう。シンドロームは $n – k$ ビットなので、グループは最大 $2^{n-k}$ 個です。このグループ分けが、実はとても綺麗な代数構造を持ちます。

定理: 2つのベクトル $\bm{r}_1, \bm{r}_2 \in \mathbb{F}_2^n$ が同じシンドロームを持つのは、両者の差が符号語であるとき、かつそのときに限る。

証明: 同値変形を追いかけます。まずシンドロームが等しいという条件を、差がゼロという形に書き換えます。

$$ \bm{r}_1\bm{H}^{\mathsf{T}} = \bm{r}_2\bm{H}^{\mathsf{T}} \iff \bm{r}_1\bm{H}^{\mathsf{T}} + \bm{r}_2\bm{H}^{\mathsf{T}} = \bm{0} $$

$\mathbb{F}_2$ では移項が足し算になるのでこう書けます。次に、行列積の分配法則で $\bm{H}^{\mathsf{T}}$ をくくり出すと、

$$ (\bm{r}_1 + \bm{r}_2)\bm{H}^{\mathsf{T}} = \bm{0} $$

となります。最後に、この式は「$\bm{r}_1 + \bm{r}_2$ が検査条件を満たす」という主張そのものですから、検査行列の定義 $(2)$ により

$$ \bm{r}_1 + \bm{r}_2 \in \mathcal{C} $$

と同値です。（証明終わり）

つまり、あるベクトル $\bm{a}$ と同じシンドロームを持つ受信語の全体は

$$ \begin{equation} \bm{a} + \mathcal{C} = \{\bm{a} + \bm{c} : \bm{c} \in \mathcal{C}\} \end{equation} $$

という集合になります。これを $\mathcal{C}$ の コセット（coset、剰余類）と呼びます。線形代数の言葉で言えば、部分空間 $\mathcal{C}$ を平行移動したアフィン部分空間です。$\mathcal{C}$ 自身も $\bm{a} = \bm{0}$ としたコセット（$\bm{0} + \mathcal{C} = \mathcal{C}$）で、これだけが唯一「ゼロを含むコセット」になります。

この平行移動のイメージを、地層のように積み上げた図で掴んでおきましょう。

いちばん下の層が符号語の集合 $\mathcal{C}$ で、これだけが原点（全ゼロ）を含みます。その上の7層は、まだ使われていない重み最小のベクトル（ここでは重み1の $1000000$ や $0100000$ など）を足して平行移動したもので、右端にそれぞれのシンドローム値を添えてあります。16点 $\times$ 8層 $= 128$ 点でちょうど $\mathbb{F}_2^7$ 全体を覆い、しかも層どうしは決して交わりません。この「層に分かれている」という描像が、次に示す性質1〜3の内容そのものです。

コセットの重要な性質を3つ挙げます。

性質1: どのコセットも要素数は $2^k$ 個。 写像 $\bm{c} \mapsto \bm{a} + \bm{c}$ は $\mathcal{C}$ から $\bm{a} + \mathcal{C}$ への全単射です（逆写像は $\bm{x} \mapsto \bm{a} + \bm{x}$ で、これは同じ形をしています）。全単射があるので個数は等しく、$|\bm{a} + \mathcal{C}| = |\mathcal{C}| = 2^k$ です。

性質2: 異なるコセットは交わらない。 もし $\bm{x}$ が2つのコセット $\bm{a} + \mathcal{C}$ と $\bm{b} + \mathcal{C}$ の両方に属するなら、上の定理より $\bm{x}$ と $\bm{a}$ のシンドロームは等しく、$\bm{x}$ と $\bm{b}$ のシンドロームも等しいので、$\bm{a}$ と $\bm{b}$ のシンドロームも等しい。すると再び定理より $\bm{a} + \bm{b} \in \mathcal{C}$ であり、$\bm{a} + \mathcal{C} = \bm{b} + \mathcal{C}$（同じコセット）となります。「交わるなら一致する」ので、異なるコセットは互いに素です。

性質3: コセットの個数はちょうど $2^{n-k}$ 個。 性質1と2から、$\mathbb{F}_2^n$ は互いに素なコセットで完全に覆われます。したがってコセットの個数は

$$ \begin{equation} \frac{|\mathbb{F}_2^n|}{|\mathcal{C}|} = \frac{2^n}{2^k} = 2^{n-k} \end{equation} $$

です。一方でシンドロームの取りうる値も $2^{n-k}$ 通り。しかも異なるコセットは異なるシンドロームを持つ（定理の対偶）。個数が一致して単射なので、コセットとシンドロームの値は1対1に対応します（$\bm{H}$ がフルランクの場合）。

この対応関係が、シンドローム復号を実装可能にする決定的な事実です。$2^n$ 個の受信語を全部覚える必要はなく、$2^{n-k}$ 個のシンドローム値ごとに「代表的な誤りパターン」を1つずつ記憶しておけばよい。$[7,4]$ 符号なら128個ではなく8個です。$[255, 247]$ 符号（実用的なSEC符号）なら $2^{255}$ 個ではなく256個。指数的な圧縮が起きています。

ではその「代表的な誤りパターン」として何を選べばよいのでしょうか。ここに標準配列という表が登場します。

標準配列 — 全受信語を一枚の表に並べる

標準配列は、$2^n$ 個の全受信語を $2^{n-k}$ 行 $\times$ $2^k$ 列の長方形に並べた表です。1行が1つのコセットに対応します。作り方は次のとおりです。

手順1（第1行）: 表の1行目に、符号語をすべて並べます。左端には必ずゼロ符号語 $\bm{0}$ を置きます。

$$ \bm{0}, \; \bm{c}_2, \; \bm{c}_3, \; \dots, \; \bm{c}_{2^k} $$

これはコセット $\bm{0} + \mathcal{C} = \mathcal{C}$、つまりシンドロームがゼロのグループです。

手順2（第2行以降）: まだ表に現れていないベクトルのうち、重みが最小のもの を1つ選びます。これを $\bm{e}_{(2)}$ とし、表の2行目の左端に置きます。そして2行目の各列には、1行目の同じ列の符号語に $\bm{e}_{(2)}$ を足したものを書きます。

$$ \bm{e}_{(2)} + \bm{0}, \; \bm{e}_{(2)} + \bm{c}_2, \; \dots, \; \bm{e}_{(2)} + \bm{c}_{2^k} $$

これが2つ目のコセットです。

手順3（繰り返し）: 表がすべて埋まるまで、手順2を繰り返します。毎回「まだ表に現れていないベクトルのうち重み最小のもの」を左端に置き、その行を埋めていきます。

手順4（終了）: $2^{n-k}$ 行が埋まった時点で、$2^{n-k} \times 2^k = 2^n$ 個のマスがすべて相異なるベクトルで埋まり、$\mathbb{F}_2^n$ の全要素がちょうど1回ずつ現れます。

各行の左端に置いた $\bm{e}_{(i)}$ を、その行の コセットリーダー（coset leader）または コセット代表 と呼びます。手順の作り方から、コセットリーダーはそのコセットの中で最小重みを持つ元です。

出来上がった表がどんな見た目になるのか、各マスのハミング重みを色で表して眺めてみます。

縦8行がコセット（＝シンドロームの値）、横16列が各コセットの元で、マスの数字と色はその元のハミング重みです。赤枠で囲った左端の列を縦に見ると 0, 1, 1, 1, 1, 1, 1, 1 と並び、他のマスが軒並み2〜7であるのに対して際立って軽いことが分かります。この「左端だけが暗い」パターンこそ、各行で迷わず最小重み元を選べる——つまりコセットリーダーが素直に決まる——ことの視覚的な表現です。

標準配列を使った復号は、驚くほど単純な手続きになります。

標準配列復号: 受信語 $\bm{r}$ を表の中から探す。$\bm{r}$ が見つかった 列の一番上にある符号語 を、復号結果 $\hat{\bm{c}}$ として出力する。

なぜこれで正しいのでしょうか。$\bm{r}$ が第 $i$ 行・第 $j$ 列にあるなら、表の作り方から $\bm{r} = \bm{e}_{(i)} + \bm{c}_j$ です。つまり「誤りパターンは $\bm{e}_{(i)}$、送信語は $\bm{c}_j$」と解釈していることになります。列の先頭は $\bm{c}_j$ ですから、列の先頭を出力するのは「誤りパターンがその行のコセットリーダーだった」と推定することに他なりません。同じことを式で書けば

$$ \begin{equation} \hat{\bm{c}} = \bm{r} + \bm{e}_{(i)}, \quad i = \bm{r} \text{ の属する行} \end{equation} $$

です。そして「$\bm{r}$ の属する行」はシンドロームを計算するだけで分かる（コセットとシンドロームは1対1）ので、表を全部持ち歩く必要はありません。シンドローム → コセットリーダー の対応表（$2^{n-k}$ 行の小さな表）さえあれば十分です。これが シンドローム復号 です。

$$ \begin{equation} \bm{s} = \bm{r}\bm{H}^{\mathsf{T}} \; \longrightarrow \; \hat{\bm{e}} = \text{(表引き)} \; \longrightarrow \; \hat{\bm{c}} = \bm{r} + \hat{\bm{e}} \end{equation} $$

標準配列は「復号器の頭の中」を可視化した設計図であり、シンドローム表はそれを実装用に圧縮したものだ、と捉えると見通しがよくなります。

ここで当然の疑問が湧きます。手順2で「重みが最小のもの」を選んだのは、なぜでしょうか。直感的には「誤りは少ないほうがありそうだから」ですが、これは本当に最適な選択なのでしょうか。次のセクションで、この直感が最尤復号と厳密に一致することを示します。

最小重みを選ぶことが最尤復号である

最尤復号（Maximum Likelihood Decoding, MLD）とは、受信語 $\bm{r}$ が与えられたときに、それを最も生じさせやすい符号語を選ぶ復号法です。

$$ \begin{equation} \hat{\bm{c}}_{\mathrm{ML}} = \arg\max_{\bm{c} \in \mathcal{C}} P(\bm{r} \mid \bm{c}) \end{equation} $$

すべての符号語が等確率で送られるなら、これは事後確率 $P(\bm{c} \mid \bm{r})$ を最大化する最大事後確率（MAP）復号と一致し、ブロック誤り率を最小化する意味で最適です。

BSCの尤度を具体的に書き下しましょう。$\bm{c}$ が送られて $\bm{r}$ が受信されたなら、$d(\bm{r}, \bm{c})$ 個のビットが反転し、残り $n – d(\bm{r}, \bm{c})$ 個は無事だった、ということです。各ビットは独立なので

$$ \begin{equation} P(\bm{r} \mid \bm{c}) = p^{\,d(\bm{r},\bm{c})} (1-p)^{\,n – d(\bm{r},\bm{c})} \end{equation} $$

となります。この式を距離 $d$ の関数として見やすくするため、$(1-p)^n$ をくくり出します。指数を $n – d = n$ から $d$ を引いたものと見て、$(1-p)^{n-d} = (1-p)^n (1-p)^{-d}$ と分解すると、

$$ \begin{equation} P(\bm{r} \mid \bm{c}) = (1-p)^n \left(\frac{p}{1-p}\right)^{d(\bm{r},\bm{c})} \end{equation} $$

を得ます。ここで $(1-p)^n$ は $\bm{c}$ に依らない定数なので、最大化には無関係です。残る因子 $\left(\frac{p}{1-p}\right)^{d}$ の底に注目します。仮定 $p < 1/2$ より $p < 1 - p$ すなわち

$$ \begin{equation} 0 < \frac{p}{1-p} < 1 \end{equation} $$

が成り立ちます。底が1より小さい指数関数は指数について 単調減少 ですから、$\left(\frac{p}{1-p}\right)^{d}$ は $d$ が小さいほど大きくなります。よって

$$ \begin{equation} \arg\max_{\bm{c} \in \mathcal{C}} P(\bm{r} \mid \bm{c}) = \arg\min_{\bm{c} \in \mathcal{C}} d(\bm{r}, \bm{c}) \end{equation} $$

が示されました。BSC（$p < 1/2$）における最尤復号は、最小距離復号と完全に一致します。

この「底が1未満だから単調減少」という一点が効いている様子を、2枚の図で確認しておきます。

左図は尤度の $\bm{c}$ 依存部分 $\left(\frac{p}{1-p}\right)^{d}$ を距離 $d$ の関数として片対数で描いたもので、$p$ が小さいほど傾きが急ですが、いずれの $p$ でも右下がりで一度も上向きに転じません。右図は底 $\frac{p}{1-p}$ 自身を $p$ の関数として描いたもので、$p = 1/2$ でちょうど1を横切ります。左側の緑の領域（$p < 1/2$）では底が1を下回るため「距離が小さいほど尤度が大きい」が保証され、右側では逆転する——最尤復号の向きを決めているのが、この一本の交点だけであることが読み取れます。

さらに一歩進めます。距離の定義 $d(\bm{r}, \bm{c}) = \mathrm{wt}(\bm{r} + \bm{c})$ を思い出すと、$\bm{c}$ を動かしたときの $\bm{r} + \bm{c}$ の動き方が問題になります。$\bm{c}$ が $\mathcal{C}$ 全体を走るとき、$\bm{r} + \bm{c}$ は $\bm{r} + \mathcal{C}$ すなわち $\bm{r}$ が属するコセット全体 を走ります。したがって

$$ \begin{equation} \min_{\bm{c} \in \mathcal{C}} d(\bm{r}, \bm{c}) = \min_{\bm{x} \in \bm{r} + \mathcal{C}} \mathrm{wt}(\bm{x}) \end{equation} $$

となり、右辺の最小値を達成する $\bm{x}$ こそが、そのコセットの最小重み元——つまり コセットリーダー です。

以上をまとめると、次の結論が得られます。

BSC（$p < 1/2$）において、各コセットの最小重み元をコセットリーダーに選んだ標準配列復号は、最尤復号と等価である。

標準配列の手順2で「重み最小のものを選ぶ」としたのは、単なる経験則ではなく、最適性の要請だったわけです。裏を返せば、$p > 1/2$ のBSC（ビットが半分以上ひっくり返る奇妙な通信路）では最大重み元を選ぶのが最尤になります。実務上は受信ビットを全反転すれば $p < 1/2$ の通信路に帰着できるので、この場合を考える必要はありません。

なお、コセットリーダーは一意とは限りません。最小重みを持つ元が複数あるコセットでは、どれを選んでも尤度は同じで、選び方は任意です（タイブレーク）。この「引き分け」がどれくらい起きるかが符号の完全性と密接に関係することを、次に見ていきます。

ハミング(7,4)符号で標準配列を全部書く

理論が揃ったので、具体的な符号で全部書き下してみましょう。題材は最も有名な誤り訂正符号、ハミング(7,4)符号です。$n = 7$、$k = 4$、$n – k = 3$、最小距離 $d_{\min} = 3$、訂正能力 $t = \lfloor (d_{\min}-1)/2 \rfloor = 1$ ビットです。

生成行列と検査行列

組織符号形式（情報ビットがそのまま先頭に現れる形）を採ります。$\bm{G} = [\bm{I}_4 \mid \bm{P}]$、$\bm{H} = [\bm{P}^{\mathsf{T}} \mid \bm{I}_3]$ とすると、$\bm{G}\bm{H}^{\mathsf{T}} = \bm{P} + \bm{P} = \bm{O}$ が自動的に成り立ちます（$\mathbb{F}_2$ では $\bm{P} + \bm{P} = \bm{O}$）。ここで

$$ \bm{P} = \begin{pmatrix} 1 & 1 & 0 \\ 0 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 0 & 1 \end{pmatrix} $$

と選びます。すると

$$ \bm{G} = \begin{pmatrix} 1 & 0 & 0 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 0 & 1 \end{pmatrix}, \qquad \bm{H} = \begin{pmatrix} 1 & 0 & 1 & 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 1 & 0 \\ 0 & 1 & 1 & 1 & 0 & 0 & 1 \end{pmatrix} $$

です。$\bm{H}$ の7つの列を書き出すと

$$ \bm{h}_1 = \begin{pmatrix}1\\1\\0\end{pmatrix},\; \bm{h}_2 = \begin{pmatrix}0\\1\\1\end{pmatrix},\; \bm{h}_3 = \begin{pmatrix}1\\1\\1\end{pmatrix},\; \bm{h}_4 = \begin{pmatrix}1\\0\\1\end{pmatrix},\; \bm{h}_5 = \begin{pmatrix}1\\0\\0\end{pmatrix},\; \bm{h}_6 = \begin{pmatrix}0\\1\\0\end{pmatrix},\; \bm{h}_7 = \begin{pmatrix}0\\0\\1\end{pmatrix} $$

となり、3ビットの非零ベクトル7通りがちょうど1回ずつ現れています。これがハミング符号の定義的な特徴です。列がすべて異なるので $d_{\min} \geq 3$、かつ $\bm{h}_1 + \bm{h}_2 + \bm{h}_3 = \bm{0}$（$110 + 011 + 111 = 000$）のように3列が線形従属になる組があるので $d_{\min} = 3$ です。

16個の符号語

$\bm{c} = \bm{m}\bm{G}$ で全符号語を求めます。情報ビット $m_1 m_2 m_3 m_4$ と符号語 $c_1 \cdots c_7$ の対応は次のとおりです（重み $\mathrm{wt}$ も併記）。

重み分布を数えると、重み0が1個、重み3が7個、重み4が7個、重み7が1個です。重み1と重み2の符号語が存在しないことが、$d_{\min} = 3$ を直接裏づけています。また重み分布が $w$ と $7 – w$ で対称になっている（全1ベクトルが符号語なので、$\bm{c} \mapsto \bm{c} + \bm{1}$ が符号を保つ）のも綺麗な性質です。

棒グラフにすると、重み1と2の位置（赤く塗った帯）に棒が1本も立っていないことが即座に分かります。最小距離とは「非零符号語の最小重み」ですから、この空白がそのまま $d_{\min} = 3$ を意味します。また左右の棒の高さが $w$ と $7-w$ で鏡写しになっており、$1111111$ が符号語であることによる対称性も目で確かめられます。

標準配列の全8行

コセットは $2^{n-k} = 2^3 = 8$ 個、各コセットは $2^k = 16$ 個の元を持ちます。合計 $8 \times 16 = 128 = 2^7$ で、7ビットベクトル全体をちょうど覆います。

以下が完全な標準配列です。左端の列がコセットリーダー、その隣がシンドローム、右側の16列が各コセットの元です。第1行が符号語そのもの（$\bm{s} = 000$）で、以降の7行が1ビット誤りに対応します。

リーダー  s   | コセットの16元（左端から順に、第1行の同じ列の符号語 + リーダー）
0000000  000 | 0000000 0001101 0010111 0011010 0100011 0101110 0110100 0111001 1000110 1001011 1010001 1011100 1100101 1101000 1110010 1111111
1000000  110 | 1000000 1001101 1010111 1011010 1100011 1101110 1110100 1111001 0000110 0001011 0010001 0011100 0100101 0101000 0110010 0111111
0100000  011 | 0100000 0101101 0110111 0111010 0000011 0001110 0010100 0011001 1100110 1101011 1110001 1111100 1000101 1001000 1010010 1011111
0010000  111 | 0010000 0011101 0000111 0001010 0110011 0111110 0100100 0101001 1010110 1011011 1000001 1001100 1110101 1111000 1100010 1101111
0001000  101 | 0001000 0000101 0011111 0010010 0101011 0100110 0111100 0110001 1001110 1000011 1011001 1010100 1101101 1100000 1111010 1110111
0000100  100 | 0000100 0001001 0010011 0011110 0100111 0101010 0110000 0111101 1000010 1001111 1010101 1011000 1100001 1101100 1110110 1111011
0000010  010 | 0000010 0001111 0010101 0011000 0100001 0101100 0110110 0111011 1000100 1001001 1010011 1011110 1100111 1101010 1110000 1111101
0000001  001 | 0000001 0001100 0010110 0011011 0100010 0101111 0110101 0111000 1000111 1001010 1010000 1011101 1100100 1101001 1110011 1111110

この表から読み取れることが3つあります。

第一に、128個のマスに7ビットベクトルがちょうど1回ずつ現れています。目視で確認するのは大変ですが、後のPython実装で全数チェックします。表が漏れなく重複なく空間を覆っている——これがコセット分解の意味です。

第二に、コセットリーダーが8個ともきれいに「重み0が1個、重み1が7個」で尽きています。重み2以上のリーダーは一つも現れません。つまりコセットの数（8個）と、重み1以下の誤りパターンの数（$1 + 7 = 8$ 個）がぴったり一致しているのです。

第三に、各コセットのリーダーは一意です（同じコセットに重み1のベクトルが2つ入ることはない）。これは前節で触れた「引き分け」がまったく起きないことを意味し、復号器に選択の迷いがありません。

3つ目の「引き分けが起きない」は、コセットごとの重みの内訳を数えると一目瞭然です。

行が8つのコセット、列が元のハミング重み、マスの数字が「その重みを持つ元がそのコセットに何個あるか」です。赤枠で囲ったのは各行の最小重みの位置で、どの行を見てもそこの個数がちょうど 1 になっています。第1行（$s=000$、符号語の集合）は重み0が1個、残り7行は重み1が1個ずつ。最小値を取る元が2個以上ある行が一つもないため、コセットリーダーの選び方に任意性が生じないのです。

この3つの性質は偶然ではなく、ハミング符号が 完全符号（perfect code）であることの現れです。次にその意味を確かめましょう。

シンドローム表 — 実装が持つべき8行

標準配列128マスをそのまま実装に持つ必要はありません。必要なのは次の8行だけです。

右端の2列を見比べてください。非零シンドローム7通りは、$\bm{H}$ の7つの列と完全に1対1で対応しています。これは式 $(9)$ で示した $\bm{e}_i\bm{H}^{\mathsf{T}} = \bm{h}_i^{\mathsf{T}}$ の直接の帰結です。$\bm{H}$ の列に3ビット非零ベクトルが漏れなく1回ずつ並んでいるので、逆向きの対応（シンドローム → 列番号 → 誤り位置）も一意に定まります。

だから、ハミング符号の復号器は表引きすら要りません。シンドロームを計算し、それが $\bm{H}$ の何番目の列と一致するかを探し、そのビットを反転する。それだけです。$\bm{H}$ の列を「1から7の2進表現」の順に並べ替えておけば（本記事の $\bm{H}$ は組織符号形式なので順序が異なりますが）、シンドロームを10進数に読むだけで誤り位置が出てくる、というさらに極端な形にもできます。この配置はハミング符号の理論と誤り訂正能力で扱っています。

具体例を一つ追ってみましょう。情報 $\bm{m} = 1011$ を送るとします。符号語は $\bm{c} = 1011100$。通信路で第3ビットが反転し、$\bm{r} = 1001100$ が受信されたとします。シンドロームを計算すると

$$ \bm{s} = \bm{r}\bm{H}^{\mathsf{T}} = (1,0,0,1,1,0,0)\bm{H}^{\mathsf{T}} = (1,1,1) $$

です。実際に第1成分を計算してみると、$\bm{H}$ の第1行 $(1,0,1,1,1,0,0)$ と $\bm{r}$ の内積は $1\cdot1 + 0\cdot0 + 1\cdot0 + 1\cdot1 + 1\cdot1 + 0 + 0 = 1 + 1 + 1 = 1$（mod 2）。同様に第2成分、第3成分も1になります。表を引くと $\bm{s} = 111$ はコセットリーダー $0010000$、すなわち第3ビットの誤り。よって

$$ \hat{\bm{c}} = \bm{r} + \hat{\bm{e}} = 1001100 + 0010000 = 1011100 = \bm{c} $$

と正しく復元できました。情報ビットは先頭4ビットを取って $\hat{\bm{m}} = 1011$。組織符号なので抽出も一瞬です。

シンドロームが誤り位置を直読させる仕組みが見えました。しかしこの美しさには代償があります。次に、それが何かを見ます。

完全符号であることと、2重誤りで起きる悲劇

なぜ8個のコセットが重み1以下で尽きるのか

ハミング(7,4)符号のコセットが、重み0が1個・重み1が7個のリーダーでちょうど尽きた理由を、数え上げで確認しましょう。

半径 $t$ のハミング球（ある符号語からハミング距離 $t$ 以内のベクトル全体）の要素数は

$$ \begin{equation} V(n, t) = \sum_{i=0}^{t} \binom{n}{i} \end{equation} $$

です。$t$ ビット誤り訂正符号では、$2^k$ 個の符号語を中心とする半径 $t$ の球が互いに交わらないので、球の総体積は空間全体を超えられません。

$$ \begin{equation} 2^k \cdot V(n, t) \leq 2^n \end{equation} $$

これが ハミング限界（球充填限界）です。等号が成り立つ符号を 完全符号 と呼びます。

$[7, 4]$ ハミング符号では $t = 1$ なので $V(7, 1) = \binom{7}{0} + \binom{7}{1} = 1 + 7 = 8$、左辺は $2^4 \times 8 = 128$、右辺は $2^7 = 128$。ぴったり等号 です。つまり16個の符号語を中心とする半径1の球が、7ビット空間128点を隙間なく、重なりなく敷き詰めています。

赤い中心点が16個の符号語、その周りの7点が「その符号語から1ビットだけ違う受信語」です。1つの球に $1 + 7 = 8$ 点、球が16個で $16 \times 8 = 128$ 点。7ビット空間の全点数とぴったり一致します。重要なのは、この図に球の外側の余白がまったくないことです。次に見るように、この余白の無さが2重誤りへの脆さに直結します。

この事実をコセットの言葉に翻訳すると、まさに先ほど観察した性質になります。コセットの個数は $2^{n-k} = 8$ 個、重み1以下の誤りパターンも8個。そして重み1以下の異なる誤りパターンは必ず異なるコセットに属します（もし $\bm{e}_i$ と $\bm{e}_j$（$i \neq j$）が同じコセットなら $\bm{e}_i + \bm{e}_j \in \mathcal{C}$ ですが、これは重み2のベクトルであり $d_{\min} = 3$ に矛盾）。数が一致し、かつ単射なので全射——つまり 8個のコセットそれぞれに、重み1以下の誤りパターンがちょうど1個ずつ入る のです。

完全符号であることの実用的な意味は「無駄がない」ことです。シンドロームの3ビット、8通りの値が、1ビットも遊ばずに「誤りなし」＋「7つの誤り位置」に割り当てられています。逆に言えば、余裕がまったくない ということでもあります。

2重誤りは必ず誤訂正される

余裕がないことの代償が、2ビット以上の誤りに対する振る舞いに現れます。

第 $i$、第 $j$ ビットが誤ったとします（$\bm{e} = \bm{e}_i + \bm{e}_j$、重み2）。シンドロームは

$$ \bm{s} = (\bm{e}_i + \bm{e}_j)\bm{H}^{\mathsf{T}} = \bm{h}_i^{\mathsf{T}} + \bm{h}_j^{\mathsf{T}} $$

です。$\bm{h}_i \neq \bm{h}_j$ なので $\bm{s} \neq \bm{0}$。そして $\bm{s}$ は3ビットの非零ベクトルですから、$\bm{H}$ の列のどれか（$\bm{h}_l$ とします）と必ず一致します。$\bm{H}$ の列は非零ベクトルを全部尽くしているからです。

すると復号器は「第 $l$ ビットが誤った」と判断し、そのビットを反転します。結果として、実際に空間に加わった誤りは

$$ \bm{e} + \bm{e}_l = \bm{e}_i + \bm{e}_j + \bm{e}_l $$

重み3のベクトルになります。しかも $(\bm{e}_i + \bm{e}_j + \bm{e}_l)\bm{H}^{\mathsf{T}} = \bm{h}_i^{\mathsf{T}} + \bm{h}_j^{\mathsf{T}} + \bm{h}_l^{\mathsf{T}} = \bm{s} + \bm{s} = \bm{0}$ なので、この重み3のベクトルは符号語 です。つまり復号器は、誤り2ビットを訂正するどころか 3ビット違いの別の符号語を、自信満々で出力する のです。誤りを検出することすらできません（シンドロームは有効な1ビット誤りのそれと区別がつかない）。

左のフローは、いま追った論理を上から順に並べたものです。2ビット誤る → シンドロームが非零 → $\bm{H}$ の列を尽くしているので必ずどれかの列と一致 → 復号器が別のビットを反転 → 残る誤りが重み3の符号語、という一本道で、途中に「検出だけして訂正しない」という分岐がどこにもありません。右の棒グラフは、21通りの2重誤りが7個の重み3符号語のどれに落ちるかを数えたもので、7本すべてが高さ3。$7 \times 3 = 21$ で漏れも重複もなく対応していることが実測で確かめられます。

数え上げでも確認できます。重み2の誤りパターンは $\binom{7}{2} = 21$ 通り。一方、重み3の符号語は7個。各重み3符号語 $\bm{c}$（サポートを $\{i, j, l\}$ とする）は、「$\{i,j\}$ が誤って $l$ を誤訂正」「$\{j,l\}$ が誤って $i$ を誤訂正」「$\{i,l\}$ が誤って $j$ を誤訂正」の3通りの経路で生じます。$7 \times 3 = 21$ で、21通りの2重誤りが漏れなく対応します。この計算は後のPythonで実測確認します。

この現象は、完全符号だからこそ起きます。球が空間を隙間なく埋めているので「どの球にも属さない中間地帯」が存在せず、復号器が「訂正不能」と匙を投げる余地がありません。逆に、拡大ハミング符号（全体パリティを1ビット足した $[8,4]$ 符号、$d_{\min} = 4$）では中間地帯が生まれ、2ビット誤りを「検出はできるが訂正はしない」と正しく報告できるようになります。SEC-DED（Single Error Correction, Double Error Detection）と呼ばれるメモリECCがこの構成を使うのは、誤訂正が最悪の結果を招くからです。訂正を諦めて上位に報告するほうが、静かにデータを壊すより遥かにましなのです。

理論の予測が出揃いました。ここからはPythonで、標準配列を実際に構成し、シンドローム表を自動生成し、BSC上で1万回のシミュレーションを回して数値を確かめます。

Pythonでの実装

符号の構成と全符号語の列挙

まず生成行列・検査行列を作り、$\bm{G}\bm{H}^{\mathsf{T}} = \bm{O}$ を確認したうえで、16個の符号語と重み分布を求めます。

import numpy as np
import itertools

# 組織符号形式のハミング(7,4)符号
P = np.array([[1, 1, 0],
              [0, 1, 1],
              [1, 1, 1],
              [1, 0, 1]])                       # 4x3 のパリティ部
G = np.hstack([np.eye(4, dtype=int), P])        # G = [I4 | P]  (4x7)
H = np.hstack([P.T, np.eye(3, dtype=int)])      # H = [P^T | I3] (3x7)

print("G =\n", G)
print("H =\n", H)
print("G H^T (mod 2) =\n", (G @ H.T) % 2)       # 零行列になるはず

# 全16通りの情報ベクトルから符号語を作る
msgs = np.array(list(itertools.product([0, 1], repeat=4)))
C = (msgs @ G) % 2
weights = C.sum(axis=1)

print("\n情報 -> 符号語 (重み)")
for m, c, w in zip(msgs, C, weights):
    print(f"  {''.join(map(str, m))} -> {''.join(map(str, c))}  (wt={w})")

print("\n重み分布 A_w =", np.bincount(weights, minlength=8))
print("最小距離 d_min =", weights[weights > 0].min())

出力を確認すると、$\bm{G}\bm{H}^{\mathsf{T}}$ は $4 \times 3$ の零行列になり、直交関係が成立しています。重み分布は $A_0 = 1, A_3 = 7, A_4 = 7, A_7 = 1$ で、重み1と2の符号語が存在しないため最小距離は3。理論どおり1ビット訂正符号であることが数値的に裏づけられました。重み分布が $w$ と $7-w$ について対称なのは、全1ベクトル $1111111$ が符号語であるためです。

標準配列の全数構成

次に、$2^7 = 128$ 個の全ベクトルをシンドロームでグループ分けし、各グループ（コセット）の最小重み元をリーダーに選んで標準配列を組み立てます。

n, k = 7, 4
all_vectors = np.array(list(itertools.product([0, 1], repeat=n)))  # 128 x 7
S = (all_vectors @ H.T) % 2                      # 各ベクトルのシンドローム
s_int = S @ np.array([4, 2, 1])                  # 3ビットを10進に

leaders, leader_counts = {}, {}
for sv in range(2 ** (n - k)):
    coset = all_vectors[s_int == sv]             # 同じシンドロームの元 = コセット
    w = coset.sum(axis=1)
    mins = coset[w == w.min()]                   # 最小重みの元（複数あり得る）
    leaders[sv] = mins[0]
    leader_counts[sv] = (len(coset), int(w.min()), len(mins))

print("s(2進) コセット要素数 最小重み リーダー候補数 リーダー")
for sv in range(8):
    size, wmin, ncand = leader_counts[sv]
    print(f"  {sv:03b}      {size:3d}        {wmin}          {ncand}      "
          f"{''.join(map(str, leaders[sv]))}")

# 標準配列が 128 マスを重複なく覆うことを確認
array_rows = [ (C + leaders[sv]) % 2 for sv in range(8) ]
flat = np.vstack(array_rows)
print("\n総マス数 =", flat.shape[0], " ユニークな行数 =",
      len(np.unique(flat, axis=0)))

結果は、8つのコセットすべてが要素数16、最小重みは第1コセットが0で残り7つが1、そして リーダー候補数はどのコセットでも1 です。引き分けが一切起きていない——これがハミング符号が完全符号であることの直接の証拠です。また標準配列を平坦化すると128行あり、ユニークな行数も128。$\mathbb{F}_2^7$ の全要素をちょうど1回ずつ覆っていることが確認できました。

シンドローム表の自動生成と復号器

上で作った leaders がそのままシンドローム表です。これを使って復号器を書き、シンドロームと $\bm{H}$ の列の対応も検証します。

def syndrome_decode(R, H, leaders):
    """受信語の行列 R (m x n) をシンドローム復号する"""
    s = (R @ H.T) % 2
    sv = s @ np.array([4, 2, 1])
    E_hat = np.array([leaders[int(v)] for v in sv])   # 表引き
    return (R + E_hat) % 2, E_hat                     # F_2 では加算で除去

# 1ビット誤りのシンドローム = H の対応する列 であることの検証
print("誤り位置  シンドローム  H の列")
for i in range(n):
    e = np.zeros(n, dtype=int); e[i] = 1
    s = (e @ H.T) % 2
    match = "OK" if np.array_equal(s, H[:, i]) else "NG"
    print(f"  第{i+1}ビット    {''.join(map(str, s))}       "
          f"{''.join(map(str, H[:, i]))}  {match}")

# 具体例: m=1011 を送り、第3ビットが反転
m = np.array([1, 0, 1, 1])
c = (m @ G) % 2
r = c.copy(); r[2] ^= 1
c_hat, e_hat = syndrome_decode(r.reshape(1, -1), H, leaders)
print(f"\n送信 c = {''.join(map(str, c))}")
print(f"受信 r = {''.join(map(str, r))}  s = {''.join(map(str, (r @ H.T) % 2))}")
print(f"推定誤り e = {''.join(map(str, e_hat[0]))}")
print(f"復号 c_hat = {''.join(map(str, c_hat[0]))}  -> m_hat = "
      f"{''.join(map(str, c_hat[0][:4]))}")

7つの1ビット誤りすべてで、シンドロームが $\bm{H}$ の対応する列と完全に一致（すべて OK）しました。式 $(9)$ の主張が実測で確認できたわけです。具体例では受信語 $1001100$ からシンドローム $111$ が得られ、第3ビットの誤りと判定して $1011100$ を復元、情報ビット $1011$ を正しく取り出せています。手計算でたどった手順とまったく同じ経路を、コードが自動でたどっています。

誤り重みごとの復号成否を全数チェック

次に、重み0〜3のすべての誤りパターンを網羅して、復号が成功するか失敗するかを数え上げます。理論では「重み1まで成功、重み2以上は必ず失敗」のはずです。

c0 = np.zeros(n, dtype=int)     # 線形符号なので全零符号語で一般性を失わない
print("誤り重み  正しく復号  総パターン数")
for wt in range(0, 4):
    ok = tot = 0
    for pos in itertools.combinations(range(n), wt):
        e = np.zeros(n, dtype=int); e[list(pos)] = 1
        c_hat, _ = syndrome_decode(((c0 + e) % 2).reshape(1, -1), H, leaders)
        tot += 1
        ok += int(np.array_equal(c_hat[0], c0))
    print(f"    {wt}       {ok:3d}/{tot:3d}")

# 2重誤りの「出力側の誤り」の重みを集計
from collections import Counter
cnt = Counter()
for pos in itertools.combinations(range(n), 2):
    e = np.zeros(n, dtype=int); e[list(pos)] = 1
    c_hat, _ = syndrome_decode(((c0 + e) % 2).reshape(1, -1), H, leaders)
    cnt[int(c_hat[0].sum())] += 1
print("\n2重誤り時の復号結果の重み分布:", dict(cnt))

結果は、重み0が1/1、重み1が7/7で成功、重み2は0/21、重み3は0/35で全滅です。そして2重誤り21通りの復号結果は すべて重み3 でした。前節で導いたとおり、復号器は必ず重み3の符号語（$\bm{c} + \bm{e}_i + \bm{e}_j + \bm{e}_l$）を出力しており、誤りビット数は2から3へ増えています。誤訂正が「訂正しないより悪い」ことが数値で見えました。

左の図では、重み0と1では緑（成功）だけが立ち、重み2と3では赤（失敗）だけが立っています。破線が訂正能力 $t = 1$ の壁で、そこを一歩越えた瞬間に成功率が100%から0%へ断崖のように落ちることが分かります。右の図は2重誤り21通りの復号後に残る誤りの重みで、棒は重み3の位置に1本だけ、高さ21。入力の誤りが2ビットだったのに出力では3ビットに増えており、「訂正した結果かえって悪化した」という状況が21通りすべてで起きています。

BSC上で1万回試行してBERを測る

いよいよ性能測定です。反転確率 $p$ を変えながら、1万フレーム（1フレーム＝7ビット）を送受信し、情報ビットのビット誤り率（BER）とフレーム誤り率（FER）を測ります。比較対象は「符号化せずに4ビットをそのまま送る」場合で、この場合のBERは $p$、FERは $1 – (1-p)^4$ です。

rng = np.random.default_rng(0)
N = 10000
ps = [0.001, 0.005, 0.01, 0.02, 0.05, 0.1, 0.15, 0.2]

ber_coded, ber_unc, fer_coded, fer_unc, fer_theory = [], [], [], [], []
for p in ps:
    m = rng.integers(0, 2, size=(N, 4))
    c = (m @ G) % 2
    err = (rng.random((N, n)) < p).astype(int)   # BSC
    r = (c + err) % 2
    c_hat, _ = syndrome_decode(r, H, leaders)

    ber_coded.append((c_hat[:, :4] != m).mean())          # 情報ビットBER
    fer_coded.append((c_hat != c).any(axis=1).mean())     # フレーム誤り率
    ber_unc.append(p)
    fer_unc.append(1 - (1 - p) ** 4)
    fer_theory.append(1 - ((1 - p) ** 7 + 7 * p * (1 - p) ** 6))

print(" p      未符号化BER  符号化BER   FER(実測)  FER(理論)  未符号化FER")
for i, p in enumerate(ps):
    print(f"{p:.3f}   {ber_unc[i]:.6f}   {ber_coded[i]:.6f}  "
          f"{fer_coded[i]:.6f}  {fer_theory[i]:.6f}  {fer_unc[i]:.6f}")

測定結果は次のとおりです。

読み取れることが3つあります。第一に、実測FERは理論値 $1 – [(1-p)^7 + 7p(1-p)^6]$ とよく一致しています（$p = 0.05$ で 0.0426 対 0.0444、1万フレームの統計誤差の範囲）。理論式は「誤りが0ビットか1ビットなら成功、それ以外は失敗」という前節の全数チェック結果をそのまま確率に翻訳したものです。第二に、$p = 0.01$ では符号化BERが $9.75 \times 10^{-4}$ と、未符号化の $10^{-2}$ から約10分の1に改善しています。第三に、$p$ が大きくなるにつれて改善幅が縮み、$p = 0.2$ ではほとんど差がなくなっています。

この最後の点は重要なので、解析的に押さえておきましょう。$p$ が小さい領域では、復号後の誤りはほぼ2重誤りだけから生じます。2重誤りは21通りあり、各々が重み3の符号語ぶんの誤りを生みます。7個の重み3符号語の情報部（先頭4ビット）の重みを合計すると12なので、2重誤り21通りで生じる情報ビット誤りの総数は $3 \times 12 = 36$。したがって情報ビットあたりの誤り確率は

$$ \begin{equation} \mathrm{BER} \approx \frac{1}{4} \binom{7}{2} p^2 \cdot \frac{36}{21} = \frac{36 p^2}{4} = 9p^2 \end{equation} $$

と近似できます。$p = 0.001$ なら $9 \times 10^{-6}$、厳密計算では $8.97 \times 10^{-6}$ で見事に一致します。$p = 0.01$ なら $9 \times 10^{-4}$、厳密値 $8.74 \times 10^{-4}$。$\mathrm{BER} \propto p^2$ という2次の依存性が、$t = 1$ ビット訂正符号の符号化利得の正体です。

そして $9p^2 < p$ となるのは $p < 1/9 \approx 0.111$ のとき。ただしこれは低誤り率での近似式なので、厳密に $\mathrm{BER}(p) = p$ となる交点を数値的に求めると $p^* \approx 0.2113$ です。$p$ がこれを超えると、符号化したほうが誤りが増えます。誤り訂正符号は万能の魔法ではなく、通信路が十分良質であることを前提とした道具なのです。深宇宙通信のように $p$ が大きい環境では、ハミング符号のような弱い符号ではなく、LDPC符号やターボ符号のような強力な符号が必要になります。

左図では、未符号化の黒い破線が傾き1の直線であるのに対し、ハミング(7,4)の実測（赤）は傾き2で急速に下がり、低 $p$ 側で近似式 $9p^2$ の点線とほぼ重なっています。右端では2本が接近しており、灰色の一点鎖線で示した $p \approx 0.211$ より右は符号化が害になる領域です。右図の実測FER（赤）は理論曲線（緑）にぴったり乗っており、「誤りが0ビットか1ビットのときだけ成功する」というモデルが正しいことを裏づけています。

可視化 — BER曲線とコセット構造

上に掲げた図は、次のコードで生成しています。BER/FER曲線と、標準配列のコセット構造を可視化する部分です。

import matplotlib, matplotlib.pyplot as plt
for cand in ["Hiragino Sans", "Yu Gothic", "Noto Sans CJK JP", "IPAexGothic", "Meiryo"]:
    if any(cand == f.name for f in matplotlib.font_manager.fontManager.ttflist):
        plt.rcParams["font.family"] = cand
        break
plt.rcParams["axes.unicode_minus"] = False

fig, ax = plt.subplots(1, 2, figsize=(13, 5))

# 左: BER曲線
ax[0].loglog(ps, ber_unc, "k--o", label="未符号化（BER = p）")
ax[0].loglog(ps, np.maximum(ber_coded, 1e-7), "r-s", label="ハミング(7,4) 実測")
pp = np.logspace(-3.2, -0.7, 100)
ax[0].loglog(pp, 9 * pp ** 2, "b:", label=r"近似 $9p^2$")
ax[0].axvline(0.2113, color="gray", ls="-.", lw=1)
ax[0].text(0.215, 3e-5, "交点\n$p\\approx0.211$", fontsize=9, color="gray")
ax[0].set_xlabel("BSC反転確率 $p$"); ax[0].set_ylabel("情報ビットの誤り率 BER")
ax[0].set_title("符号化利得は $p^2$ の傾きとして現れる")
ax[0].legend(); ax[0].grid(True, which="both", alpha=0.3)

# 右: フレーム誤り率
ax[1].loglog(ps, fer_unc, "k--o", label="未符号化 4ビット")
ax[1].loglog(ps, np.maximum(fer_coded, 1e-7), "r-s", label="ハミング(7,4) 実測")
ax[1].loglog(ps, fer_theory, "g:^", label=r"理論 $1-[(1-p)^7+7p(1-p)^6]$")
ax[1].set_xlabel("BSC反転確率 $p$"); ax[1].set_ylabel("フレーム誤り率 FER")
ax[1].set_title("実測FERは理論式とよく一致する")
ax[1].legend(); ax[1].grid(True, which="both", alpha=0.3)

plt.tight_layout(); plt.show()

このコードが描くのが直前に掲げたBER/FER曲線です。np.maximum(ber_coded, 1e-7) としているのは、$p = 0.001$ では1万フレーム中に誤りが1件も出ず実測値が厳密に0になり、両対数プロットで点が消えてしまうためのフロア処理です。実測点が消えるほど誤りが少ないこと自体が、$t = 1$ 訂正の効きを物語っています。

続いて、標準配列そのものを画像として眺めるコードです。

import numpy as np
import matplotlib.pyplot as plt

# 標準配列 8x16 の各マスの「重み」をヒートマップにする
mat = np.zeros((8, 16), dtype=int)
row_labels = []
order = [0, 6, 3, 7, 5, 4, 2, 1]   # s=000,110,011,111,101,100,010,001 の順
for row, sv in enumerate(order):
    coset = (C + leaders[sv]) % 2
    mat[row, :] = coset.sum(axis=1)
    row_labels.append(f"s={sv:03b}  e={''.join(map(str, leaders[sv]))}")

fig, ax = plt.subplots(figsize=(12, 5))
im = ax.imshow(mat, cmap="viridis", aspect="auto")
ax.set_yticks(range(8)); ax.set_yticklabels(row_labels, fontsize=9)
ax.set_xticks(range(16)); ax.set_xticklabels([f"$c_{{{j+1}}}$" for j in range(16)],
                                             fontsize=8)
for i in range(8):
    for j in range(16):
        ax.text(j, i, mat[i, j], ha="center", va="center",
                color="w" if mat[i, j] < 4 else "k", fontsize=8)
ax.set_xlabel("列（対応する符号語）"); ax.set_ylabel("行（コセット）")
ax.set_title("標準配列の各マスのハミング重み — 左端の列がコセットリーダー")
plt.colorbar(im, ax=ax, label="ハミング重み")
plt.tight_layout(); plt.show()

これが「標準配列 — 全受信語を一枚の表に並べる」の節で示したヒートマップの生成コードです。左端の列（$c_1 = 0000000$ に対応）を縦に見ると、上から 0, 1, 1, 1, 1, 1, 1, 1 と並んでいます。これがコセットリーダーの重みで、第1行だけが0、残りはすべて1です。各行の他のマスは重み3〜7の値を取っており、リーダーが行内で唯一の最小値であることが色の濃淡からも読み取れます。この「左端だけが暗い」というパターンこそ、復号器が迷わずリーダーを選べる根拠です。

最後に、シンドロームと $\bm{H}$ の列の1対1対応を図示します。

import numpy as np
import matplotlib.pyplot as plt

fig, ax = plt.subplots(1, 2, figsize=(12, 4.5))

# 左: H を画像として表示（列がシンドロームそのもの）
ax[0].imshow(H, cmap="Greys", vmin=0, vmax=1)
for i in range(3):
    for j in range(7):
        ax[0].text(j, i, H[i, j], ha="center", va="center",
                   color="r" if H[i, j] else "b", fontsize=13)
ax[0].set_xticks(range(7))
ax[0].set_xticklabels([f"$h_{{{j+1}}}$" for j in range(7)])
ax[0].set_yticks(range(3)); ax[0].set_yticklabels(["検査1", "検査2", "検査3"])
ax[0].set_title("検査行列 $H$ の列 = 各ビットの「誤り指紋」")

# 右: 誤り位置 -> シンドローム10進値
sv_of_pos = []
for i in range(7):
    e = np.zeros(7, dtype=int); e[i] = 1
    sv_of_pos.append(int(((e @ H.T) % 2) @ np.array([4, 2, 1])))
ax[1].bar(range(1, 8), sv_of_pos, color="steelblue")
for i, v in enumerate(sv_of_pos):
    ax[1].text(i + 1, v + 0.15, f"{v:03b}", ha="center", fontsize=10)
ax[1].set_xlabel("誤ったビットの位置"); ax[1].set_ylabel("シンドロームの10進値")
ax[1].set_title("非零シンドローム7通りが位置と1対1に対応")
ax[1].set_ylim(0, 8.5); ax[1].grid(axis="y", alpha=0.3)

plt.tight_layout(); plt.show()

こちらは「シンドロームの定義と『送信語に依存しない』ことの証明」の節で示した図の生成コードです。左の図は検査行列を白黒画像にしたもので、各列が「そのビットが誤ったときに立つシンドローム」を表しています。7つの列がすべて異なるパターンになっていることが一目で分かります。右の棒グラフでは、誤り位置1〜7に対してシンドロームの10進値が 6, 3, 7, 5, 4, 2, 1 と並び、1から7の値が重複なく現れています。同じ高さの棒が2本無い——これが「シンドロームから誤り位置が一意に決まる」ことの視覚的な証拠です。

実装と測定が理論の予測を裏づけました。最後に、標準配列という考え方が一般の符号でどこまで通用するのかを整理しておきます。

標準配列の限界と、その先の復号法

標準配列は「線形符号の最尤復号とは何か」を完璧に説明する概念装置ですが、実装手段としてはすぐに破綻します。理由は表のサイズです。

シンドローム表の行数は $2^{n-k}$。$[7,4]$ なら8行で済みますが、$[255, 223]$ のリード・ソロモン符号相当のパラメータでは $2^{32} \approx 43$ 億行、$[1024, 512]$ のLDPC符号では $2^{512}$ 行。宇宙に存在する原子の数を軽く超えます。シンドローム表による復号は、$n – k$ が小さい符号でしか使えません。

縦軸は対数目盛で、目盛1つが約19桁分に相当します。ハミング$[7,4]$ の8行は図の左下の隅に埋もれ、$[255,223]$ 相当の約43億行でようやく緑の破線（実装可能な表サイズの目安 $10^{10}$ 行）に届きます。しかし $n-k = 512$ では赤の破線（宇宙の原子数の見積り $10^{80}$）を遥かに超え、$10^{154}$ 行に達します。表引きという発想が $n-k$ の増加に対してまったく耐えられないことが、この一直線の傾きに現れています。

この壁を越えるために、実用符号は「表引きの代わりに、シンドロームから誤りパターンを計算で求める」方向に進化しました。

代数的復号（BCH符号・リード・ソロモン符号）: シンドロームを有限体上の多項式の係数とみなし、誤り位置多項式を Berlekamp–Massey アルゴリズムや Euclid の互除法で求めます。表を持たず、$O(t^2)$ 程度の演算で誤り位置を算出できます。詳しくはBCH符号の理論やリード・ソロモン符号の理論と実装で扱っています。

反復復号（LDPC符号・ターボ符号）: そもそも最尤復号を諦め、確率伝搬法で近似的に事後確率を求めます。検査行列がスパースであることを利用し、計算量は符号長に対してほぼ線形です。LDPC符号の理論を参照してください。ここで「パリティ検査が満たされているか」を判定する終了条件は、まさにシンドロームが零ベクトルかどうかのチェックです。標準配列の考え方は消えたわけではなく、判定条件として生き残っています。

もう一つ、標準配列が教えてくれる重要な概念があります。コセットリーダーが一意でない場合の扱いです。

ハミング符号では引き分けが起きませんでしたが、一般の符号では頻繁に起きます。たとえば $[6, 3]$ の符号では、最小重み2の元が複数入るコセットが現れます。このとき復号器には2つの選択肢があります。

• 完全復号（complete decoding）: 引き分けの中から適当に1つ選び、常に何らかの符号語を出力する。ブロック誤り率は最小になるが、明らかに怪しいケースでも「訂正しました」と答えてしまう
• 不完全復号 / 有界距離復号（bounded distance decoding）: リーダーの重みが $t = \lfloor (d_{\min}-1)/2 \rfloor$ を超えるコセットに落ちたら「復号失敗」と宣言し、上位層に再送を要求する。誤訂正を避けられるが、訂正できたはずのケースも諦めることになる

どちらが良いかは応用次第です。ストレージやメモリのように「静かにデータが壊れる」ことが許されない場面では不完全復号（＋検出）が選ばれ、リアルタイム音声のように「多少間違ってもいいから何か出す」場面では完全復号が選ばれます。標準配列は、この選択が「どのコセットまでを訂正対象とみなすか」という表の切り分けの問題であることを、明快に示してくれます。

まとめ

本記事では、線形符号がどうやって誤りを特定するのか——シンドローム復号と標準配列——について解説しました。

• シンドロームは誤りだけを写す: $\bm{r} = \bm{c} + \bm{e}$ に対し $\bm{s} = \bm{r}\bm{H}^{\mathsf{T}} = \bm{c}\bm{H}^{\mathsf{T}} + \bm{e}\bm{H}^{\mathsf{T}} = \bm{e}\bm{H}^{\mathsf{T}}$。符号語の項が検査行列の定義で消えるため、シンドロームは送信語に一切依存しません。$2^k$ 個の符号語を探索する問題が、$n-k$ ビットの指紋を読む問題に置き換わります
• 同じシンドローム＝コセット: $\bm{r}_1, \bm{r}_2$ のシンドロームが等しいことと $\bm{r}_1 + \bm{r}_2 \in \mathcal{C}$ は同値です。$\mathbb{F}_2^n$ は $2^{n-k}$ 個のコセットに分割され、コセットとシンドローム値は1対1に対応します
• 標準配列とコセットリーダー: 全 $2^n$ 個の受信語を $2^{n-k} \times 2^k$ の表に並べ、各行の最小重み元をリーダーに選ぶ。復号は「列の先頭を出力する」という操作に帰着します
• 最小重み＝最尤: BSC（$p<1/2$）では $P(\bm{r}\mid\bm{c}) = (1-p)^n\left(\frac{p}{1-p}\right)^{d}$ で底が1未満のため、尤度最大は距離最小と同値。コセットリーダーを選ぶことが最尤復号そのものです
• ハミング(7,4)の完全なシンドローム表: 8つのコセットのリーダーは重み0が1個・重み1が7個で尽き、非零シンドローム7通りが $\bm{H}$ の7列と1対1対応します。$2^4 \cdot (1 + 7) = 2^7$ の等号（完全符号）がこの無駄のなさの正体です
• 完全性の代償: 隙間がないため2重誤りは必ず誤訂正され、実測でも21通りすべてが重み3の別符号語に化けました。SEC-DEDが拡大ハミング符号を使うのはこれを避けるためです
• 性能の実測: 1万フレームのBSCシミュレーションで、$p = 0.01$ のBERが $10^{-2} \to 9.75\times10^{-4}$ に改善。低 $p$ での挙動は $\mathrm{BER} \approx 9p^2$ でよく説明でき、$p \approx 0.211$ を超えると符号化が逆効果になることも確認しました

シンドローム復号は、誤り訂正符号のあらゆる復号法の出発点です。BCH符号もリード・ソロモン符号も、まずシンドロームを計算するところから始まります。LDPC符号の反復復号でさえ、収束判定はシンドロームが零かどうかのチェックです。標準配列という表は実装には使えませんが、「復号器は何を最適化しているのか」を一枚の絵で説明してくれる、他に代えがたい道具です。

次のステップとして、以下の記事も参考にしてください。

• ハミング符号の理論と誤り訂正能力 — 完全符号としての最適性の証明と拡大ハミング符号
• 線形ブロック符号とは？生成行列と検査行列から理解する — 生成行列・検査行列・最小距離の体系的な整理
• BCH符号の理論 — 巡回符号による多重誤り訂正 — シンドロームから誤り位置多項式を代数的に解く手法
• リード・ソロモン符号の理論と実装 — シンボル単位の誤り訂正とバースト誤りへの強さ
• LDPC符号の理論 — スパースグラフ符号の原理と復号アルゴリズム — 表引きを捨て、確率伝搬で近似最尤に迫る現代的アプローチ