シャノン研究ノート

シャノンのチャネル符号化定理：ランダム符号化の限界と構成的符号の探求

Tags: 情報理論, チャネル符号化, ランダム符号化, 符号理論, シャノン

はじめに：シャノンのチャネル符号化定理とその革新性

クロード・シャノンが1948年に発表した画期的な論文『A Mathematical Theory of Communication』の中で提示されたチャネル符号化定理は、ノイズが存在する通信路においても、チャネル容量と呼ばれる特定のレート以下であれば、任意に小さな誤り確率で信頼性の高い通信が可能であることを理論的に証明しました。これは、それまでの通信工学が直面していた「ノイズとの闘い」に明確な理論的指針を与え、情報理論の最も重要な成果の一つと位置づけられています。

この定理は、通信可能な最大レートの存在を示しただけでなく、そのレートを達成するための符号化・復号化の「存在」を証明しました。しかし、その証明に用いられた主要な技術の一つである「ランダム符号化 (Random Coding)」は、定理の存在性を示す強力なツールであった一方で、実際に通信システムで利用可能な構成的な符号化・復号化アルゴリズムを直接提供するものではありませんでした。この記事では、シャノンのチャネル符号化定理の核心を再確認しつつ、特にランダム符号化が持つ意義と限界、そしてその後の情報理論と符号理論の研究において、いかにして理論的限界を達成する構成的な符号が探求されてきたのかについて掘り下げていきます。

シャノンのチャネル符号化定理の核心

ノイズのある離散無記憶通信路 (Discrete Memoryless Channel, DMC) を考えます。この通信路は、入力アルファベット $\mathcal{X}$、出力アルファベット $\mathcal{Y}$、そして遷移行列 $P(y|x)$ で特徴づけられます。チャネル容量 $C$ は、入力分布 $p(x)$ に関する相互情報量 $I(X;Y)$ の最大値として定義されます。

$$ C = \max_{p(x)} I(X;Y) = \max_{p(x)} \sum_{x \in \mathcal{X}, y \in \mathcal{Y}} p(x) P(y|x) \log_2 \frac{P(y|x)}{\sum_{x' \in \mathcal{X}} p(x') P(y|x')} $$

シャノンのチャネル符号化定理（またはノイズのあるチャネル符号化定理）は、次の二つの部分から構成されます。

  1. 達成可能性 (Achievability): 任意のレート $R < C$ と任意の $\epsilon > 0$ に対して、十分に大きな符号長 $n$ を持つ符号が存在し、最大誤り確率が $\epsilon$ 以下となるように設計できます。
  2. 逆定理 (Converse): もしレート $R > C$ で通信しようとするならば、符号長 $n$ をいくら大きくしても、誤り確率はゼロに収束しません。実際、どのような符号化・復号化を用いても、誤り確率はある正の値より小さくならないことが示されます。

この定理は、チャネル容量 $C$ が、信頼性の高い通信が可能なレートの上限であることを明確に示しました。特に達成可能性部分は、それまで経験的にレートを上げるほど誤り率が増加するという認識があった中で、「容量以下ならば原理的には誤りなく送れる」という強力なメッセージを発信するものでした。

ランダム符号化：存在証明のための強力なツール

シャノンがチャネル符号化定理の達成可能性を証明するために採用した主要な手法がランダム符号化です。その基本的な考え方は以下の通りです。

  1. 符号帳の生成: $M = 2^{nR}$ 個の符号語を、入力アルファベット $\mathcal{X}$ から独立かつ同一分布 (i.i.d.) に、ある確率分布 $p(x)$ に従ってランダムに生成します。これらの $M$ 個の符号語の集合が符号帳となります。
  2. 符号化: 送信したいメッセージに対応する符号語を、生成された符号帳から選び出します。
  3. 復号化: 受信した信号 $y^n$ に対して、符号帳の中の各符号語 $x^n$ を仮定し、事後確率 $P(x^n|y^n)$ が最も高くなる符号語を元のメッセージとして推定します（最大事後確率復号）。あるいは、共同典型性 (Joint Typicality) を用いる方法もあります。受信系列 $y^n$ が、送信された符号語 $x^n$ と「共同典型」である場合にのみ、その符号語を復号結果とします。共同典型集合の性質を用いることで、送信された符号語が正しく復号される確率が高いこと、および誤って他の符号語が共同典型と判断される確率が非常に小さいことが示せます。

ランダム符号化による証明の鍵は、符号帳を「平均的に」評価することにあります。つまり、ランダムに生成された「ほとんど全ての」符号帳が良い符号帳（高い確率で誤りが少ない符号帳）であることを示します。符号帳全体に対する平均誤り確率を計算し、それが符号長 $n \to \infty$ のときゼロに収束することを示せば、少なくとも一つは誤り確率がゼロに収束する符号帳が存在することが結論づけられます。

このアプローチは、特定の構造を持つ符号を構成することなく、統計的な性質を利用して良い符号の存在を示すという点で非常に巧妙です。漸近等分割性 (Asymptotic Equipartition Property, AEP) や共同典型集合といった概念と組み合わせることで、情報源や通信路の統計的性質と情報レートの限界を結びつける強力なフレームワークを提供しました。

ランダム符号化の限界と構成的符号化への課題

ランダム符号化は定理の存在証明には成功しましたが、実際の通信システムにそのまま適用することは困難です。その主な理由は以下の通りです。

  1. 非構成性: ランダム符号化は「良い符号帳が存在する」ことを保証するだけで、具体的な符号帳の構築方法を直接与えません。実際にランダムに生成された符号帳がどれほど「良い」かは保証されず、最悪の符号帳が生成される可能性もゼロではありません（ただし、その確率は非常に小さい）。
  2. 符号帳の巨大さ: レート $R$ で $M=2^{nR}$ 個のメッセージを符号化するためには、符号帳に $M$ 個の符号語を格納する必要があります。符号長 $n$ が大きくなると、 $M$ は指数関数的に増大するため、符号帳を記憶したり、復号化のために符号帳全体を探索したりすることが計算量的に非現実的になります。
  3. 復号化の計算量: 最大事後確率復号や共同典型性復号は、受信系列と符号帳内の全ての符号語との比較を必要とします。符号帳のサイズが指数関数的に増大するため、この復号化処理も計算量的に膨大になります。

これらの限界から、シャノンのチャネル符号化定理は「信頼性のある通信が可能である」という理論的な可能性を示しましたが、「では、具体的にどのように符号を設計すればその理論限界を達成できるのか？」という新たな、そして極めて困難な課題を提起しました。この課題こそが、シャノンの定理発表後の符号理論研究の主要なモチベーションとなりました。目標は、チャネル容量に近いレートで動作し、かつ実用的な計算量で符号化・復号化が可能な「構成的な」符号を見つけ出すことでした。

構成的符号の探求と現代符号理論

シャノンが提起した構成的符号の課題に対する探求は、符号理論の歴史を通じて精力的に続けられてきました。

初期には、代数的な構造を持つ符号、例えば線形ブロック符号、巡回符号、BCH符号、リード・ソロモン符号などが研究されました。これらの符号は、効率的な符号化・復号化アルゴリズムを持つという利点があり、特にリード・ソロモン符号はストレージシステムなどで広く利用されています。しかし、これらの符号は、二元対称通信路 (Binary Symmetric Channel, BSC) のような単純な通信路においても、容量に近いレートで動作させようとすると符号長が非常に大きくなり、復号化が困難になるという限界がありました。

1990年代に入ると、シャノンの理論限界に極めて近い性能を持つ革新的な符号が登場しました。代表的なものとして、ターボ符号 (Turbo Codes) と低密度パリティ検査 (LDPC: Low-Density Parity-Check) 符号が挙げられます。

これらの現代的な符号は、シャノンのチャネル符号化定理が示した理論的限界を、実用的なレベルで達成可能であることを示しました。これは、シャノンがランダム符号化という非構成的な手法で示した可能性を、その後の研究者たちが構成的な手法で実現するという、情報理論史における重要なマイルストーンと言えます。

結論：理論から実践へ繋がるシャノンの遺産

クロード・シャノンのチャネル符号化定理は、通信の究極的な限界を明確に定義し、ノイズ下での信頼性のある通信が理論的に可能であることを示しました。その証明に用いられたランダム符号化は、この存在性を示す上で不可欠なツールでしたが、同時に実用的な符号化・復号化の課題を浮き彫りにしました。

この「理論的な可能性」と「実用的な実現」のギャップを埋めるための探求が、その後の符号理論研究を大きく推進し、代数符号、畳み込み符号、そしてLDPC符号やターボ符号といった容量限界に近い性能を持つ構成的な符号の開発へと繋がりました。これらの現代的な符号は、今日のデジタル通信システムにおいて不可欠な要素となっています。

シャノンのチャネル符号化定理は単なる理論的な結果に留まらず、実用的な技術開発に対する強力な指針と動機付けを提供し、情報科学の発展に測り知れない影響を与え続けています。ランダム符号化という抽象的な概念が、その後の何十年にもわたる研究を経て、具体的な高性能符号として結実した過程は、理論研究と応用研究の美しい相互作用を示す好例と言えるでしょう。シャノンの仕事は、情報理論の基礎であると同時に、現代通信技術の基盤として、今なおその輝きを失っていません。