はじめに：情報理論の「その先」へ

こんにちは、TechBulkです。 後期の講義で**「符号理論（Coding Theory）」**が始まりました。

以前受講した「情報理論」の講義でも、ハミング符号などの誤り訂正符号は扱いました。しかし、そこでは「この行列$G$を使えば符号化できます」「この行列$H$を使えば誤りが見つかります」という、あくまでツールの使い方を学ぶにとどまっていました。

今回の「符号理論」の第1回講義を受けて、一番の衝撃だったのは、「なぜその行列が、そんな値（0と1の配置）になっているのか？」 というブラックボックスだった部分に、数学的なメスが入ったことです。

この記事では、第1回の講義で学んだ「符号理論と線形代数の密接な関係」についてまとめます。

本日の講義まとめ

1. 符号理論は「線形代数」そのものである: ベクトル空間や行列の知識がフル活用される。
2. 生成行列$G$と検査行列$H$: これらは適当に決まっているのではなく、「直交補空間」などの数学的性質に基づいて設計されている。
3. 有限体（GF(2)）: コンピュータの世界では、$1+1=0$ になる不思議な演算ルールが適用される。

1. 情報理論の復習：通信システムのモデル

まず、通信の基本的な流れをおさらいします。

1. 情報源: 送りたいデータ（メッセージ $w$）
2. 符号化: 生成行列 $G$ を掛けて、誤りに強い「符号語 $x$」に変換する
3. 通信路（ノイズ）: 送信中にビットが反転してしまう（誤り $e$ が乗る）
4. 復号: 受信したデータ $y$ から、元のメッセージを推定する

情報理論では、この流れを確率論（エントロピーなど）で扱いましたが、符号理論ではこれを**「ベクトルと行列の演算」**として扱います。

2. ハミング符号の「不思議」を解明する

講義では、(7,4,3)ハミング符号を例に解説がありました。 これは、4ビットのデータに3ビットの検査ビットを足して、7ビットにして送る方式です。

符号化の式

メッセージベクトルを $w$、生成行列を $G$ とすると、符号語 $x$ は以下の式で作られます。

$$x = w G$$

ここで登場する生成行列 $G$ はこんな形をしています。

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

情報理論の時は「ふーん、こういう行列があるんだ」程度に思っていましたが、よく見ると左側4列は単位行列になっています。これは、元のメッセージ $w$ をそのまま残しつつ（組織符号）、後ろにパリティ（検査用ビット）を付加していることを意味します。

復号の鍵：パリティ検査行列 $H$

受信側では、パリティ検査行列 $H$ を使って誤りをチェックします。 $H$ は以下のような行列です。

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

ここで重要な性質が一つあります。 「正しい符号語 $x$ は、必ず $H$ と直交する（積がゼロになる）」 というルールです。

$$H x^T = \mathbf{0}$$

なぜこの行列なのか？（今回のハイライト）

ここが今回一番面白かった点です。 なぜ $G$ と $H$ がこの値なのか？ それは、線形代数における**「ランク（階数）」「部分空間」「直交補空間」**という概念で説明がつきます。

• 符号語の集合は、あるベクトル空間の**「部分空間」**を形成している。
• 行列 $H$ は、その部分空間に対して**「直交補空間」**を張るように設計されている。

つまり、「正しいデータがあるべき空間（$G$が作る空間）」と「それ以外のゴミ空間」を、$H$ というフィルターを使って数学的にバッサリ切り分けているわけです。 なんとなく決まっていたように見えた0と1の羅列には、明確な数学的必然性があったのです。

3. シンドローム復号法：誤りの犯人探し

受信したデータ $y$ に誤りがあるかどうかは、以下の計算（シンドローム $s$）で一発で分かります。

$$s = H y^T$$

• もし $s = \mathbf{0}$ なら、誤りなし。
• もし $s \neq \mathbf{0}$ なら、$s$ の値が $H$ の何列目と同じかを見ることで、何ビット目が誤っているか特定できる。

例えば、計算結果が $s = \begin{pmatrix} 1 \\ 1 \\ 0 \end{pmatrix}$ だったとします。 行列 $H$ を見ると、このベクトルは**「2列目」**と同じです。

これにより、「あ、2ビット目が反転してるな」と即座に分かり、訂正ができるのです。まるで手品ですが、これも全て線形代数のロジック通りです。

4. 今後の課題：有限体（Galois Field）

ただし、これらの計算には一つだけ独特なルールがあります。それが**有限体（GF(2)）**です。 ここでは $1 + 1 = 0$ になります。

$$\begin{aligned} 0 + 0 &= 0 \\ 0 + 1 &= 1 \\ 1 + 0 &= 1 \\ 1 + 1 &= 0 \end{aligned}$$

実数の世界とは違うこの演算ルール（mod 2）の上で、いかに方程式を解き、システムを構築するかを考えます。

おわりに

「行列計算なんて社会に出て使うのか？」と学部1年の頃は思っていましたが、スマホの通信もHDDの読み書きも、裏側ではこの行列計算（線形代数）が膨大な速度で行われていることで成立しているんですね。 次回は線形空間の復習になると思います！