クロード・シャノンによるノイズのあるチャネル符号化定理：理論の核心と証明の概要
はじめに：シャノンの第二定理の意義
クロード・シャノンが1948年に発表した画期的な論文『A Mathematical Theory of Communication』は、情報科学、特に通信理論の礎を築きました。その中で最も重要な結果の一つが、「ノイズのあるチャネル符号化定理 (Noisy Channel Coding Theorem)」です。これは一般に「シャノンの第二定理」とも呼ばれています。この定理は、通信路（チャネル）にノイズが存在する場合であっても、情報伝送速度のある限界値（チャネル容量）以下であれば、誤り率を任意に小さく抑えることが可能であることを示しています。逆に、この限界値を超える速度での信頼性の高い通信は不可能であることも同時に示唆しており、通信システムの設計における根本的な指針を与えました。
本記事では、このシャノンのノイズのあるチャネル符号化定理に焦点を当て、その理論的な背景、定理の厳密なステートメント、そしてシャノンが提示した証明の核心部分について深く掘り下げていきます。情報理論の研究者にとって、この定理の正確な理解は、符号理論や通信原理の基礎を固める上で不可欠です。
理論的基礎：チャネルモデルと情報量
シャノンの第二定理を理解するためには、まずその基礎となる概念、特に離散無記憶チャネル（Discrete Memoryless Channel, DMC）のモデルと、情報量の測度について明確にする必要があります。
離散無記憶チャネル (DMC)
DMCは、入力アルファベット $\mathcal{X}$、出力アルファベット $\mathcal{Y}$、そして遷移確率 $p(y|x)$ によって定義されます。ここで $x \in \mathcal{X}$ は入力シンボル、$y \in \mathcal{Y}$ は出力シンボルです。無記憶性とは、ある時刻での入出力が、それ以前およびそれ以降の入出力から統計的に独立であることを意味します。つまり、チャネルの振る舞いは現在の入力のみに依存し、過去の入力や出力は影響しません。
エントロピーと相互情報量
シャノンは、情報の不確かさや量を測るための概念としてエントロピーを導入しました。確率変数 $X$ のエントロピー $H(X)$ は、その取りうる値の確率分布 $p(x)$ を用いて以下のように定義されます。
$$H(X) = -\sum_{x \in \mathcal{X}} p(x) \log_b p(x)$$
ここで $b$ は対数の底で、通常は2（ビット単位）が用いられます。条件付きエントロピー $H(Y|X)$ は、入力 $X$ が与えられたときの出力 $Y$ の不確かさを表します。
$$H(Y|X) = -\sum_{x \in \mathcal{X}} \sum_{y \in \mathcal{Y}} p(x,y) \log_b p(y|x)$$
相互情報量 $I(X;Y)$ は、入力 $X$ が出力 $Y$ に関して伝える情報量を測る尺度であり、以下のように定義されます。
$$I(X;Y) = H(X) - H(X|Y) = H(Y) - H(Y|X) = H(X) + H(Y) - H(X,Y)$$
これはまた、以下のようにも表現できます。
$$I(X;Y) = \sum_{x \in \mathcal{X}} \sum_{y \in \mathcal{Y}} p(x,y) \log_b \frac{p(x,y)}{p(x)p(y)} = \sum_{x \in \mathcal{X}} \sum_{y \in \mathcal{Y}} p(x) p(y|x) \log_b \frac{p(y|x)}{p(y)}$$
相互情報量は、入力分布 $p(x)$ に依存します。
チャネル容量の定義
DMCにおけるチャネル容量 $C$ は、入力シンボルの確率分布 $p(x)$ に関して相互情報量 $I(X;Y)$ を最大化することで定義されます。
$$C = \max_{p(x)} I(X;Y)$$
チャネル容量は、そのチャネルが単位時間あたりに誤りなく伝送できる情報の最大速度を示唆する値であり、単位はビット毎シンボル（bits per channel use）となります。
ノイズのあるチャネル符号化定理 (シャノンの第二定理)
定理は以下のように述べられます。
離散無記憶チャネル (DMC) のチャネル容量を $C$ とする。
- 達成可能性 (Achievability): 任意の符号化速度 $R < C$ に対し、長さ $n$ の符号語を用いた符号化方式で、ブロック誤り確率 $P_e^{(n)}$ を $n \to \infty$ の極限で任意に小さくできる符号系列が存在する。すなわち、$\lim_{n \to \infty} P_e^{(n)} = 0$ となる符号系列が存在する。
- 逆定理 (Converse): 任意の符号化方式において、ブロック誤り確率 $P_e^{(n)}$ を $n \to \infty$ の極限で任意に小さくできるならば、その符号化速度 $R$ は必ずチャネル容量 $C$ 以下でなければならない。すなわち、もし $\lim_{n \to \infty} P_e^{(n)} = 0$ ならば $R \le C$ である。
この定理は、容量 $C$ が通信の「限界」であることを数学的に厳密に証明しています。容量以下ならば原理的に信頼性の高い通信が可能であり、容量を超えると不可能になるということです。
証明の概要：シャノンの洞察
シャノンが提示した第二定理の証明は、その後の情報理論や符号理論の研究に大きな影響を与えました。特に、達成可能性の証明で用いられた手法は画期的でした。
達成可能性証明の概要
シャノンの達成可能性証明の中心的なアイデアは、「ランダム符号化 (Random Coding)」と「共同典型的性 (Joint Typicality)」の概念にあります。
- ランダム符号化: まず、送信機は $2^{nR}$ 個のメッセージに対応する長さ $n$ の符号語を、入力アルファベット $\mathcal{X}$ 上の確率分布 $p(x)$ に従ってランダムに、かつ独立に生成します。ここで $R$ は符号化速度であり、$2^{nR}$ は符号語の数です。この符号帳は、送信機と受信機の両方で共有されていると仮定します。
- 送信と受信: メッセージ $i$ を送信する場合、対応する符号語 $\mathbf{x}i = (x{i1}, \dots, x_{in})$ がチャネルを通して送信されます。受信機は、チャネルの出力系列 $\mathbf{y} = (y_1, \dots, y_n)$ を観測します。
- デコーディング: 受信機は、観測した出力系列 $\mathbf{y}$ と符号帳に登録されている各符号語 $\mathbf{x}_i$ を比較し、最も「らしい」符号語に対応するメッセージを推定します。シャノンの原証明やその後の多くの証明では、共同典型的性 (joint typicality) に基づくデコーディング規則が用いられます。系列 $(\mathbf{x}, \mathbf{y})$ が共同典型的であるとは、そのエントロピーや相互情報量に対応する統計的な性質を満たすことを指します。受信機は、観測した $\mathbf{y}$ に対して、チャネルの遷移確率 $p(\mathbf{y}|\mathbf{x}_i)$ が高い、あるいはより一般的には $(\mathbf{x}_i, \mathbf{y})$ が共同典型的であるような唯一の符号語 $\mathbf{x}_i$ を見つけたと推定します。そのような符号語が複数あるか、一つもない場合は誤りと判断します。
- 誤り確率の解析: 誤りが発生するのは、正しい符号語 $\mathbf{x}_i$ を送ったにも関わらず、受信した $\mathbf{y}$ が他の符号語 $\mathbf{x}_j$ (j $\ne$ i) とも共同典型的になってしまう場合などが考えられます。ランダム符号化を用いることで、符号帳全体の平均的な誤り確率を解析します。シャノンは、速度 $R < C$ であれば、ランダムに生成された符号帳の大部分において、平均誤り確率がブロック長 $n$ を大きくするにつれて指数関数的に小さくなることを示しました。したがって、少なくとも一つは誤り率が任意に小さくなる符号帳が存在することになります。
このランダム符号化のアイデアは、具体的な「良い符号」を構成するのではなく、「良い符号が存在する」ことを確率論的に証明するものでした。これは当時の符号理論における画期的なアプローチでした。
逆定理の証明の概要
逆定理の証明は、達成可能性の証明よりも比較的容易です。その核心は、ファノの不等式や情報処理の不等式（データ処理の不等式）といった情報理論的な限界を用いることにあります。
符号化速度 $R$ で通信を行うということは、$2^{nR}$ 個の可能なメッセージを区別する必要があるということです。これらのメッセージに対応する入力系列を $\mathbf{X}$、受信系列を $\mathbf{Y}$ とします。情報処理の不等式によれば、情報源からの情報 $M$ （メッセージのインデックス）と、受信機での推定結果 $\hat{M}$ の間の相互情報量 $I(M; \hat{M})$ は、チャネルを通して得られる情報 $I(\mathbf{X}; \mathbf{Y})$ を超えることはありません。
$$I(M; \hat{M}) \le I(\mathbf{X}; \mathbf{Y})$$
信頼できる通信（誤り率が小さい通信）では、送信されたメッセージ $M$ と推定結果 $\hat{M}$ の間の相互情報量 $I(M; \hat{M})$ は、メッセージのエントロピー $H(M) = nR$ に近い値になります。ファノの不等式などを用いて、誤り率が小さければ $I(M; \hat{M})$ が $H(M)$ に近いことを示せます。
一方、$I(\mathbf{X}; \mathbf{Y})$ は、DMCの場合、各シンボル使用における相互情報量の合計で上限が抑えられます。
$$I(\mathbf{X}; \mathbf{Y}) \le \sum_{k=1}^n I(X_k; Y_k) \le n \max_{p(x)} I(X;Y) = nC$$
これらの不等式を組み合わせると、誤り率が小さくなるためには $nR \approx I(M; \hat{M}) \le I(\mathbf{X}; \mathbf{Y}) \le nC$ が成り立ち、したがって $R \le C$ であることが導かれます。つまり、チャネル容量 $C$ を超える速度で誤り率を任意に小さくすることは不可能である、と結論づけられます。
歴史的背景と現代的意義
シャノンのノイズのあるチャネル符号化定理は、当時の通信工学の常識を覆すものでした。それまで、通信の信頼性を向上させるには、送信電力を増やすか、帯域幅を広げるしかないと考えられていました。しかしシャノンは、ノイズがある環境でも、適切な符号化を行うことで、特定の限界速度（容量）までは誤り率を任意に小さくできることを数学的に示したのです。これは、通信システムの設計思想を「信号対ノイズ比や帯域幅といった物理的制約」から「情報量とチャネル容量という情報論的制約」へと転換させる決定的な一歩となりました。
シャノンの定理は存在証明でしたが、具体的な符号構成法は提示していませんでした。その後数十年にわたり、シャノンの容量限界に迫る「良い符号」の探索と構成が、符号理論の中心的な研究課題となりました。ターボ符号やLDPC符号といった現代的な誤り訂正符号は、シャノンの容量限界に非常に近い性能を達成しており、デジタル通信システムの信頼性と効率性を劇的に向上させています。携帯電話、Wi-Fi、衛星通信、データストレージなど、現代のあらゆる情報技術は、シャノンの第二定理とその後の符号理論の発展に支えられています。
また、情報理論の枠を超えて、統計学、機械学習、生物学など、情報伝送や処理が関わる多くの分野で、シャノンの情報量や容量の概念、そしてこの定理に示される原理が重要な洞察を与えています。
まとめ
クロード・シャノンによるノイズのあるチャネル符号化定理は、情報理論における最も深遠で実践的な成果の一つです。この定理は、ノイズが存在する通信路においても、チャネル容量という明確な限界以下であれば信頼性の高い通信が可能であることを数学的に保証しました。シャノンが達成可能性証明で用いたランダム符号化や共同典型的性の考え方は、その後の情報理論研究に大きな影響を与えました。
現代においても、この定理は通信システムの理論的な限界を理解し、容量に迫る高性能な符号を設計するための基本的な指針であり続けています。シャノンの洞察は、単なる通信技術の進歩を超え、情報の普遍的な性質に関する深い理解をもたらしました。情報科学に携わる研究者にとって、シャノンの原論文に立ち返り、この定理の証明の細部やその哲学的意義を再検討することは、常に新たな発見をもたらす可能性を秘めています。
本記事が、シャノンのノイズのあるチャネル符号化定理とその意義について、読者の皆様の理解を深める一助となれば幸いです。