Featured image of post 誤り訂正符号の仕組み：傷だらけのCDからQRコードまで
数学 コンピュータサイエンス

誤り訂正符号の仕組み：傷だらけのCDからQRコードまで

ハミング符号やリード・ソロモン符号など、デジタルデータを守る誤り訂正符号の数学的原理と情報理論について深く解説します。

誤り訂正符号とは何か？

デジタル社会において、データは常にノイズの脅威に晒されています。CDについた傷、宇宙空間から送信される探査機のデータ、あるいは私たちが日常的にスキャンしているQRコード。これらのデータが少しの欠損やノイズによって完全に壊れてしまわないのは、「誤り訂正符号 (Error-Correcting Codes, ECC)」という強力な数学的メカニズムが存在するからです。

この記事では、情報理論の父クロード・シャノンが提唱した概念から始まり、パリティチェックの基礎、ハミング符号の行列表現、そしてガロア体を駆使したリード・ソロモン符号まで、その仕組みを詳細に解き明かします。

1. シャノンの情報理論と通信路符号化定理

1948年、クロード・シャノンは論文 “A Mathematical Theory of Communication” を発表し、情報理論という全く新しい分野を打ち立てました。シャノンが証明した最も驚くべき定理の一つが「通信路符号化定理 (Noisy-channel coding theorem)」です。

シャノンは、どのようなノイズのある通信路であっても、その通信路の「通信路容量 (Channel Capacity)」$C$を下回る通信速度であれば、情報を実質的にエラーなしで送ることができると数学的に証明しました。これは、エラーを減らすために単に送信電力を上げたり、何度も同じデータを送る（繰り返し符号）必要はなく、「賢い符号化」を行えばよいということを意味します。

  graph TD
    A["送信者 (Source)"] -- "メッセージ (Message)" --> B["エンコーダ (Encoder)"]
    B -- "符号語 (Codeword)" --> C["ノイズのある通信路 (Noisy Channel)"]
    C -- "受信語 (Received word)" --> D["デコーダ (Decoder)"]
    D -- "復元されたメッセージ (Recovered Message)" --> E["受信者 (Destination)"]

2. 最もシンプルなエラー検出：パリティチェック

誤りを見つける最も単純な方法は「パリティチェック」です。データビットの最後に1ビットの「パリティビット」を追加し、全体の「1」の数が常に偶数（偶数パリティ）または奇数（奇数パリティ）になるように調整します。

例えば、データ 1011 を送る場合、1の数は3つです。偶数パリティを使用する場合、パリティビットとして 1 を追加し、送信データは 10111 となります。受信側で1の数が奇数になっていれば、通信中にエラーが起きたことがわかります。

しかし、パリティチェックには致命的な弱点があります。

  1. エラーを検出できるだけで、訂正はできない（どのビットが反転したかわからない）。
  2. 2ビットのエラーが同時に起こると検出できない（偶奇が元に戻ってしまうため）。

この限界を突破したのが、リチャード・ハミングが考案した「ハミング符号」です。

3. ハミング符号：エラーの場所を特定する

ハミング符号は、複数のパリティビットを巧みに組み合わせることで、1ビットのエラーを検出し、かつ自動的に訂正することができる画期的な符号です。代表的なものに、4ビットのデータに3ビットのパリティを付加する「ハミング(7,4)符号」があります。

ハミング(7,4)符号の行列表現

ハミング符号は、線形代数の強力なツールである「生成行列 (Generator Matrix) $G$」と「パリティ検査行列 (Parity-Check Matrix) $H$」を用いて定義されます。

データベクトルを $d = (d_1, d_2, d_3, d_4)$ とします。 生成行列 $G$ は次のように定義されます（標準形）。

$$ G = egin{pmatrix} 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 \end{pmatrix} $$

符号語 $c$ は、$c = d \cdot G \pmod 2$ で計算されます。

受信側では、受信したベクトル $r$ に対して、パリティ検査行列 $H$ を掛けて「シンドローム (Syndrome) $S$」を計算します。

$$ S = r \cdot H^T \pmod 2 $$

もし $S = (0, 0, 0)$ ならばエラーなし。それ以外の場合は、シンドロームの値がエラーの発生したビット位置を示します！

Pythonによるハミング符号の実装例

以下は、Pythonを用いたシンプルなハミング(7,4)符号のシミュレーションです。

 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

import numpy as np

# 生成行列 G (4x7)
G = np.array([
    [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 (3x7)
H = np.array([
    [1, 1, 0, 1, 1, 0, 0],
    [1, 0, 1, 1, 0, 1, 0],
    [0, 1, 1, 1, 0, 0, 1]
])

# 元データ
d = np.array([1, 0, 1, 1])

# エンコード (モジュロ 2)
c = np.dot(d, G) % 2
print(f"送信符号語: {c}")

# ノイズの付加（3番目のビットを反転）
r = c.copy()
r[2] ^= 1
print(f"受信データ: {r}")

# シンドロームの計算
S = np.dot(r, H.T) % 2
print(f"シンドローム: {S}")

4. リード・ソロモン符号：バーストエラーに立ち向かう

ハミング符号は1ビットのランダムエラーには強いですが、CDの傷のように「連続してビットが壊れる」現象（バーストエラー）には対応できません。これを解決するのが「リード・ソロモン符号 (Reed-Solomon Codes, RS符号)」です。

QRコード、CD、DVD、ブルーレイ、宇宙通信など、現代のほぼすべてのデータストレージと通信でRS符号が使われています。

ガロア体（有限体）の魔法

RS符号の核心は、「ガロア体 (Galois Field, GF)」という特殊な数学の世界（有限体）で計算を行うことです。通常の数とは異なり、ガロア体では四則演算を行った結果が必ずその体の要素に収まります（オーバーフローや小数が存在しません）。

通常、コンピュータは8ビット（1バイト）単位でデータを扱います。そのため、$GF(2^8)$ という256個の要素を持つガロア体がよく使われます。

RS符号の仕組み

RS符号は、データを $GF(2^8)$ 上の多項式の係数とみなします。 $k$ 個のデータシンボルを係数とする $k-1$ 次の多項式 $P(x)$ を作成します。 この多項式に、様々な $x$ の値（評価点）を代入して $n$ 個の点を計算します。これが送信されるデータ（符号語）です。

受信側では、ノイズによっていくつかの点がずれて（エラーになって）届きます。しかし、残った正しい点が十分に多ければ、「ラグランジュ補間」などの数学的手法を用いて、元の多項式 $P(x)$ を完全に復元できるのです！

比喩的な説明 2点あれば直線を引けます。3点あれば放物線（2次曲線）を描けます。 もし元のデータが「直線」であり、3つの点を送ったとします。受信側で1つの点がずれていても、残り2つの点が正しければ、元の直線を正しく引き直すことができる、という原理です。

まとめ：数学が支える私たちのデジタルライフ

私たちが何気なくスマートフォンでQRコードを読み取ったり、音楽をストリーミング再生したりできるのは、シャノン、ハミング、リード、ソロモンといった天才たちが築き上げた「誤り訂正符号」という強固な数学的基盤があるからです。

ノイズだらけの現実世界で、完璧なデジタルデータを維持し続ける。それはまさに、数学が現実世界にかけた魔法と言えるでしょう。

comments powered by Disqus