ハミング符号とゴレイ符号 — 誤り訂正符号の原点にある美しい線形代数

この回で学ぶこと

これまでの回では、畳み込み符号とビタビ復号、リード・ソロモン(RS)符号、そして(先の回で扱う)LDPC符号といった、実際の深宇宙ミッションの主力を張ってきた強力な誤り訂正符号を見てきました。RS符号では有限体 $GF(2^m)$ の上でシンボル単位の符号を組み立て、多項式の評価やシンドロームから誤り位置多項式を代数的に求める、という手の込んだ機械を動かしていました。

この回では少し時計の針を戻します。扱うのは ハミング符号(Hamming code) と ゴレイ符号(Golay code) という、1940年代末から1950年代前半に生まれた、符号理論そのものの出発点にあたる符号です。RS符号がシンボル($GF(2^m)$ の元)を単位とする代数的な構成だったのに対し、ハミング符号・ゴレイ符号は ビットそのものを直接扱う、最もシンプルな線形ブロック符号 です。この「シンプルさ」は決して見劣りするという意味ではありません。むしろハミング符号は、パリティ検査行列という道具立てだけで「受信語に行列を掛けるだけで誤り位置がそのまま指し示される」という、符号理論全体を通じて最も美しい仕組みの一つを持っています。そしてハミング符号もゴレイ符号も、後述する「完全符号(perfect code)」という、理論限界にぴったり到達する稀有な存在です。この回では、この原点にある美しさと、なぜ今なお現役であり続けているのかを見ていきます。

直感的な導入: パリティビット1個では足りない

誤り検出の最も原始的な方法は、パリティビットです。$k$ 個の情報ビットに、その総和(mod 2)を1ビット付け加えれば、1ビットの誤りが起きたかどうかは検出できます。しかし、これでは どのビットが誤ったのか は分かりません。「誤りがあったらしい」ということしか分からないパリティビット1個では、訂正のしようがないのです。

では、誤り位置を特定するには何が必要でしょうか。$n$ ビットの符号語の中で誤りが起こりうる位置は、「誤りなし」を含めて $n+1$ 通りあります($n$ 箇所のどこか1つが誤るか、どこも誤らないか)。この $n+1$ 通りの状態を区別するには、少なくとも $\lceil \log_2(n+1) \rceil$ ビットの検査情報が必要です。逆に言えば、$r$ 個の検査ビットがあれば、うまく設計すれば最大 $2^r - 1$ 通りの「1ビット誤りの位置」を区別できるはずです。

リチャード・ハミングが1940年代末にベル研究所で考えたのは、まさにこの発想でした。検査ビットが指し示す2進数の値を、そのまま誤りビットの位置番号として使えるように、検査ビットの配置を設計する ——これがハミング符号の核心です。$r=3$ 個の検査ビットなら $2^3-1=7$ 通りの位置を指し示せるので、符号語長は $n=7$、そのうち検査ビットが3個、残り $k=n-r=4$ ビットが情報ビットになります。これが最も有名な ハミング$(7,4)$符号 です。

パリティ検査行列 $H$ の設計

「各列が異なる非ゼロベクトル」という設計原理

ハミング$(7,4)$符号を、パリティ検査行列 $H$ から構成してみましょう。$H$ は $r \times n = 3 \times 7$ の行列で、符号語 $c \in \{0,1\}^7$ が正しい符号語であるための条件は

$$H c^{\top} = \mathbf{0} \pmod 2$$

です。ここで設計上の核心的なアイデアが登場します。$H$ の各列を、$1$ から $2^r-1$ までの整数を2進数で表したベクトルとして並べる のです。$r=3$ の場合、列は $1,2,\dots,7$ の2進表現、つまり

$$H = \begin{pmatrix} 0&0&0&1&1&1&1\\ 0&1&1&0&0&1&1\\ 1&0&1&0&1&0&1 \end{pmatrix}$$

のように、$7$本の列すべてが相異なる非ゼロの3ビットベクトルになるように配置します(列の並べ方自体は任意ですが、後述のシンドローム復号の見通しをよくするため、列 $j$ を整数 $j$ の2進表現にするのが標準的です)。

なぜこの配置が誤り訂正を可能にするのか、次節で見る通り、これは単なる思いつきではなく、$H$ の列の「相異なる非ゼロ性」そのものが訂正能力の根拠になっています。

生成行列との関係、そして系統的な形

実装上便利なのは、$H$ を列の並べ替えによって

$$H = \big[\, A \mid I_r \,\big]$$

の形(右側 $r$ 列が単位行列)に整理しておくことです。上の例では列 $\{4,2,1\}$(2進で $100,010,001$)がちょうど単位行列を作るので、それらの位置(1,2,4番目)を検査ビット、残り(3,5,6,7番目)を情報ビットに割り当てれば、系統符号(情報ビットがそのまま符号語に現れる符号)として素直に構成できます。対応する生成行列 $G$ は $H G^{\top} = \mathbf{0}$ を満たすように

$$G = \big[\, I_k \mid A^{\top} \,\big]$$

の形で作れ、符号語は $c = mG$($m$ は $k$ ビットの情報ベクトル、行ベクトルとして)で得られます。RS符号のところで見た「組織符号」と同じ発想が、ここでは二元(バイナリ)の世界でそのまま成り立っています。

シンドローム復号: $Hr^{\top}$ が誤り位置を直接指し示す

ハミング符号の最も美しい性質が、ここに現れます。送信符号語 $c$ が通信路を通り、$1$ ビットの誤りを含む受信語 $r = c + e$ になったとしましょう。ここで $e$ は誤りベクトルで、誤りが起きた位置 $j$ だけが $1$、他はすべて $0$ です($e = (0,\dots,0,\underbrace{1}_{j},0,\dots,0)$)。

このとき、受信語に $H$ を掛けた シンドローム $s$ を計算します。

$$s = H r^{\top} = H(c+e)^{\top} = Hc^{\top} + He^{\top} = \mathbf{0} + He^{\top} = He^{\top}$$

($Hc^{\top}=\mathbf{0}$ は $c$ が正しい符号語である定義そのものです。)ここで $He^{\top}$ を具体的に計算すると、$e$ は $j$ 番目だけが $1$ のベクトルなので、行列とベクトルの積の定義から

$$He^{\top} = (\text{$H$ の第 $j$ 列})$$

がそのまま出てきます。つまり、シンドローム $s$ は、$H$ の列のうち「誤りが起きた位置に対応する列」に一致します。そして先ほどの設計により、$H$ の列 $j$ は整数 $j$ の2進表現そのものでした。したがって

$$s = H r^{\top} = (j \text{ の2進表現})$$

つまり シンドロームを2進数として読むだけで、誤りビットの位置番号 $j$ がそのまま分かる のです。誤りが1ビットもなければ $s=\mathbf{0}$、1ビット誤りがあれば $s$ は非ゼロで、その値がそのまま誤り位置を教えてくれます。復号は「$s$ が指し示す位置のビットを反転させる」だけで完了します。探索も反復計算もいらない、驚くほど直接的な復号法です。RS符号のシンドローム復号がBerlekamp-Massey法やChien探索という反復的な代数計算を必要としたのに比べると、ハミング符号のこの単純さは際立っています。それはひとえに「1ビットしか誤りが起きない」という前提と、$H$ の列を1から $2^r-1$ まで漏れなく割り当てたという設計の直接的な帰結です。

最小距離 $d_{\min}=3$ と1ビット誤り訂正能力

なぜ「1ビット誤りしか訂正できない」のか、そしてそれがなぜ十分なのかを、最小距離の観点から確認しておきましょう。

線形符号の最小距離 $d_{\min}$ は、パリティ検査行列 $H$ の列たちの線形従属関係から決まる、という一般的な事実があります。具体的には、

$$d_{\min} = \min \{\, w : H \text{ の列のうち、ある } w \text{ 本を選ぶと和が } \mathbf{0} \text{ になる} \,\}$$

です(これは符号語 $c \ne \mathbf{0}$ が $Hc^{\top}=\mathbf{0}$ を満たすとき、$c$ の非ゼロ成分に対応する $H$ の列を足し合わせるとちょうど $\mathbf{0}$ になる、という関係から従います)。

ハミング$(7,4)$符号の $H$ を見ると、

• どの1本の列も非ゼロなので、1本だけで和が $\mathbf{0}$ になることはない($d_{\min}\ge 2$)。
• どの2本の列も互いに異なるように設計したので、2本の列を足しても $\mathbf{0}$ にはならない($d_{\min}\ge 3$)。
• 一方、3本の列をうまく選べば和が $\mathbf{0}$ になる組み合わせが必ず存在する(例えば上の $H$ で列1・列2・列3は $(0,0,1),(0,1,0),(0,1,1)$ であり、これらを足すと $(0,0,1)+(0,1,0)+(0,1,1)=(0,0,0)$ となります。7本の非ゼロ3ビットベクトルの中には、このような従属関係が必ず生じます)。

したがって $d_{\min}=3$ が成り立ちます。一般の線形符号では、最小距離 $d_{\min}$ の符号が確実に訂正できる誤り数 $t$ は

$$t = \left\lfloor \frac{d_{\min}-1}{2} \right\rfloor$$

でした(RS符号の回で見たのと同じ関係式です)。$d_{\min}=3$ を代入すると $t = \lfloor 2/2 \rfloor = 1$、すなわち ハミング$(7,4)$符号は1ビットの誤りを確実に訂正できる ことが導かれます。これは先ほどシンドローム復号で直接確認した性質と、最小距離という一般理論の両方から矛盾なく裏付けられているわけです。

また $d_{\min}=3$ であることから、2ビット誤りは(訂正はできないものの)検出はできます。2ビット誤りが起きるとシンドロームは非ゼロになりますが、その値は「本当は存在しない1ビット誤りの位置」を指すため、誤って別の1ビットを訂正してしまい、結果的に3ビット分食い違った符号語になってしまいます。したがって基本のハミング符号は「1ビット訂正・2ビット検出まで」というのが正確な性能です(検査ビットをもう1個追加した拡張ハミング符号 $(8,4)$ を使うと、2ビット誤り検出まで確実にできるようになりますが、これは次回以降の話題に譲ります)。

ハミング限界と「完全符号」としての美しさ

ここまでで「なぜうまくいくか」は分かりましたが、もう一つ、理論的に非常に美しい事実があります。それは、ハミング符号が、与えられたパラメータのもとで理論上可能な最良の効率を、誤差なくぴったり達成しているということです。

一般に、$n$ ビットの符号語で $t$ ビットまでの誤りを確実に訂正するには、球充填限界(sphere-packing bound、ハミング限界) と呼ばれる次の不等式を満たす必要があります。

$$2^k \sum_{i=0}^{t} \binom{n}{i} \le 2^n$$

この式の意味は次の通りです。符号語空間 $\{0,1\}^n$ の中に、$2^k$ 個の符号語が離れて配置されています。各符号語 $c$ を中心に、「ハミング距離 $t$ 以内にある全ての語」からなる球(誤り訂正の”守備範囲”)を描くと、その球の中に含まれる語の数はちょうど $\sum_{i=0}^{t}\binom{n}{i}$ 個です($i$ ビットだけ異なる語が $\binom{n}{i}$ 通りあるので)。$t$ ビットまでの誤りを確実に訂正するには、異なる符号語を中心とするこれらの球が互いに重なってはいけません。したがって、$2^k$ 個の球の体積の総和が、空間全体の大きさ $2^n$ を超えることはできない、というのがこの不等式です。

ハミング$(7,4)$符号にこの式を当てはめてみましょう。$n=7,\ k=4,\ t=1$ です。

$$2^4 \sum_{i=0}^{1}\binom{7}{i} = 2^4 \left(\binom{7}{0}+\binom{7}{1}\right) = 16 \times (1+7) = 16 \times 8 = 128 = 2^7$$

なんと、左辺と右辺が 完全に一致 します。不等号ではなく等号が成り立つのです。これは、ハミング$(7,4)$符号が作る $2^4=16$ 個の球が、空間 $\{0,1\}^7$($2^7=128$ 個の語)を、隙間なく、重なりなく、ぴったり敷き詰めることを意味します。空間上のどんな語(受信語)を持ってきても、それは必ずどれか1つの符号語からハミング距離1以内にある、つまり必ずどこかの球に属しているのです。

この、球充填限界を等号で達成する符号を 完全符号(perfect code) と呼びます。完全符号は非常に稀な存在で、既知の完全な線形符号は本質的に、ハミング符号の族、次節で見るゴレイ符号(の2つ)、そして自明な符号(反復符号や全ビット符号)しかない、ということが数学的に証明されています。無数にある線形符号のほとんどは、球充填限界に対してわずかに(あるいは大きく)余裕を残しており、「捨てているスペース」があるのに対し、ハミング符号は無駄が一切ない、理論限界にぴったり張り付いた稀有な設計だという点に、この符号の美しさがあります。

より一般に、検査ビット数 $r$ を大きくすると、符号長 $n=2^r-1$、情報ビット数 $k=n-r=2^r-1-r$ の ハミング$(n,k)$符号族 が同様に構成でき、そのすべてが1ビット誤り訂正の完全符号になります。$(7,4)$はこの族の $r=3$ の場合にすぎません。

ゴレイ符号 $(23,12)$: もう一つの完全符号

ハミング符号が $t=1$(1ビット誤り訂正)の完全符号だったのに対し、1949年にマルセル・ゴレイが発見した ゴレイ符号(Golay code) は、$t=3$(3ビット誤り訂正)を実現する完全符号です。パラメータは

$$(n,k,d_{\min}) = (23,12,7)$$

検査ビット数は $n-k=11$、最小距離 $d_{\min}=7$ なので $t=\lfloor(7-1)/2\rfloor=3$ ビットまで確実に訂正できます。ここでもハミング限界を確認してみましょう。

$$2^{12}\sum_{i=0}^{3}\binom{23}{i} = 2^{12}\left(\binom{23}{0}+\binom{23}{1}+\binom{23}{2}+\binom{23}{3}\right)$$ $$= 4096 \times (1+23+253+1771) = 4096 \times 2048 = 2^{12}\times 2^{11} = 2^{23}$$

ここでもぴったり $2^{23}$ に一致し、等号が成立します。つまりゴレイ$(23,12)$符号も、$\{0,1\}^{23}$ の空間を、半径3の球で隙間なく敷き詰める完全符号です。ハミング符号と自明な符号を除くと、2元の完全な線形符号はこのゴレイ符号ただ1つしか存在しない(3元版のゴレイ$(11,6)$符号を含めても、完全符号の族は本質的にこれで尽きる)ということが知られており、$t\ge2$ を訂正する完全符号としてはまさに孤高の存在です。

ゴレイ符号の具体的な生成行列や検査行列の構成(2次剰余符号としての構成、あるいは巡回符号としての構成)は本格的な代数的議論が必要になり、この回の範囲を超えますが、押さえておくべきは次の点です。ハミング符号のパリティ検査行列が「$1$ から $2^r-1$ までの整数を並べる」という直接的な設計原理から生まれたのに対し、ゴレイ符号は数論的にずっと深い構造(2次剰余、あるいは特定の巡回多項式)を利用しないと構成できません。$t=1$ を超える完全符号を実現するには、それだけの数学的な仕掛けが必要になる、ということでもあります。

歴史: ボイジャー計画とゴレイ符号

ゴレイ$(23,12)$符号は、深宇宙通信史において実際に使われた実績を持ちます。ボイジャー1号・2号は、1979年の木星接近、1980〜1981年の土星接近というミッション初期において、この拡張ゴレイ符号(パリティビットを1つ追加した$(24,12,8)$符号、$t=3$を保ったまま全ての誤りパターンで偶数距離を保証する形)を画像データの誤り訂正に使用していました。当時のリンク容量と処理能力の制約の中で、比較的シンプルな回路で実装できる完全符号としてのゴレイ符号は理にかなった選択でした。

(RS符号の回で見た通り、ボイジャー2号は後により遠い天王星(1986年)・海王星(1989年)へと向かう過程で、RS$(255,223)$符号を外符号とする連接符号へと符号化方式を更新しています。これはゴレイ符号のようなシンプルな完全符号だけでは、木星・土星よりもさらに遠い天王星・海王星からの微弱な信号に対応しきれなくなったためで、この回とRS符号の回は、ボイジャー計画という1つのミッションの中で符号技術がどう進化していったかを繋ぐ2つの章だと言えます。)

実務での使われ方

ここまで見てきたように、ハミング符号・ゴレイ符号は数学的には非常に美しく、完全符号という稀有な地位を占めています。しかし現代の深宇宙通信の主力回線では、これらは主役の座をRS符号・畳み込み符号・LDPC符号・ターボ符号などに譲っています。理由は単純で、訂正能力(符号化率あたりでどれだけ強い雑音に耐えられるか)という観点では、ハミング符号やゴレイ符号は現代の高度な符号に大きく見劣りするからです。ハミング$(7,4)$符号は1ビットしか訂正できず、ゴレイ符号でも3ビットです。一方RS$(255,223)$符号は16シンボル(最大128ビット相当)の誤りを訂正でき、LDPC符号やターボ符号はシャノン限界のごく近くまで迫る符号化利得を達成します。深宇宙リンクのようにビット誤り率(BER)を極限まで下げたい用途では、ハミング符号やゴレイ符号だけでは力不足なのです。

それでもなお、ハミング符号は今日も現役で使われ続けています。その理由は「訂正能力の強さ」とは別の軸、すなわち 低遅延・低複雑度 にあります。

• ECCメモリ(Error-Correcting Code Memory): C&DHサブシステムの回で触れた通り、探査機の搭載メモリは深宇宙の放射線環境によるビット反転(シングルイベントアップセットなど)に常にさらされています。メモリの各ワード(たとえば64ビット)に対して、ハミング符号を拡張した SEC-DED(Single Error Correction, Double Error Detection、単一誤り訂正・2重誤り検出)符号を付加するのが業界標準的な設計です。これは基本の $(n,k)$ ハミング符号にもう1ビットの全体パリティを追加した拡張ハミング符号そのもので、1ビット誤りは訂正、2ビット誤りは(訂正はできないものの)確実に検出できます。地上のサーバーやPCのメインメモリでも、同じ原理のECCメモリが広く使われています。
• 低遅延性: シンドローム復号の節で見た通り、ハミング符号の復号は「行列とベクトルの積を計算し、その値をそのまま誤り位置として使う」だけで完結します。反復計算も探索も不要なため、ハードウェア回路として実装したときのレイテンシが極めて小さく、メモリアクセスのたびに毎回発生する誤り訂正処理としては理想的な軽さです。RS符号のBerlekamp-Massey法やLDPC符号の反復的なメッセージパッシング復号のような計算コストは一切かかりません。
• 低複雑度・低消費電力: 検査行列 $H$ が固定された単純なXOR演算の組み合わせで実装できるため、回路規模が小さく、消費電力も小さく済みます。探査機搭載コンピュータのように、消費電力・実装面積・処理速度のすべてに厳しい制約がある環境では、この軽さは大きな価値を持ちます。

つまり、通信路の誤り訂正のように「多少の遅延と複雑さを許容してでも、できる限り強い符号化利得が欲しい」場面ではRS符号やLDPC符号が選ばれる一方、メモリアクセスのように「毎クロックサイクル発生しうる処理を、遅延ゼロに近い形で確実にこなしたい」場面では、ハミング符号のシンプルさと直接性がむしろ最適解になる、という住み分けができているわけです。

演習問題

1. 本文中のハミング$(7,4)$符号の検査行列 $H$(列を1〜7の2進表現とした形)を使い、情報ビット列 $m=(1,0,1,1)$ から系統符号語 $c$ を1つ構成してください(検査ビットの位置と計算方法は本文の議論を参考にしてよい)。その符号語の5番目のビットが反転して受信されたとして、シンドローム $s=Hr^{\top}$ を計算し、確かに誤り位置5を指し示すことを確認してください。
2. ハミング限界の式 $2^k\sum_{i=0}^{t}\binom{n}{i}\le 2^n$ を使い、$n=15,\ k=11$(検査ビット数 $r=4$ のハミング符号)が $t=1$ の完全符号であることを、等号が成立することを示すことで確認してください。
3. なぜ最小距離 $d_{\min}=3$ の符号は「1ビット訂正・2ビット検出」までしかできず、「2ビット訂正」はできないのか、球充填(あるいはハミング距離の三角不等式)の観点から自分の言葉で説明してください。
4. ハミング符号やゴレイ符号のような完全符号は理論的に「無駄がない」符号ですが、現代の深宇宙通信路の誤り訂正ではRS符号やLDPC符号のような、ハミング限界に対して余裕(無駄)を残す符号の方が好まれます。本文の議論をもとに、この一見矛盾するように見える状況がなぜ成り立つのか(「無駄のなさ」と「訂正能力の強さ」は別の軸である、という点を踏まえて)説明してください。

まとめと次回予告

この回では、RS符号やLDPC符号のような高度な符号の源流にある、最もシンプルな線形ブロック符号としてハミング符号とゴレイ符号を見てきました。ハミング$(7,4)$符号は、パリティ検査行列 $H$ の列に $1$ から $2^r-1$ までの整数を漏れなく割り当てるという設計により、シンドローム $Hr^{\top}$ を計算するだけで誤り位置がそのまま分かるという、極めて直接的な復号法を実現していました。最小距離 $d_{\min}=3$ から1ビット誤り訂正能力が導かれ、さらにハミング限界(球充填限界)にちょうど等号で到達する「完全符号」であることも確認しました。ゴレイ$(23,12)$符号は3ビット誤り訂正を実現するもう1つの数少ない完全符号で、ボイジャー計画の木星・土星接近時に実際に使われた歴史を持ちます。実務面では、通信路の誤り訂正の主役はRS符号やLDPC符号に移った一方、ECCメモリのような低遅延・低複雑度が求められる場面では、ハミング符号の直接的なシンドローム復号が今も選ばれ続けていることを見ました。

次回は、ハミング符号を一般化する方向に話を進めます。ハミング符号は $t=1$ しか訂正できませんでしたが、この構成を巡回符号・有限体上の多項式という枠組みへと拡張し、任意の訂正能力 $t$ を設計上自由に選べるようにした符号族が BCH符号(Bose-Chaudhuri-Hocquenghem符号) です。実はRS符号もBCH符号の特別な場合(非2元版)として位置づけられることになり、この回で見た「シンドローム」という考え方が、より一般的な代数的枠組みの中でどう洗練されていくのかを見ていきます。

参考文献

• R. W. Hamming, “Error Detecting and Error Correcting Codes,” Bell System Technical Journal, vol. 29, 1950
• M. J. E. Golay, “Notes on Digital Coding,” Proceedings of the IRE, vol. 37, 1949
• S. Lin, D. J. Costello, Error Control Coding, 2nd ed., Prentice Hall
• R. E. Blahut, Theory and Practice of Error Control Codes, Addison-Wesley
• J. H. Yuen (ed.), Deep Space Telecommunications Systems Engineering, JPL Publication 82-76