クロード・シャノンによるランダム符号化：ノイズありチャネル符号化定理の証明技術
はじめに：ノイズありチャネル符号化定理とその証明の課題
クロード・シャノンが1948年の金字塔的な論文「A Mathematical Theory of Communication」で示したノイズのあるチャネル符号化定理、いわゆる第二定理は、情報理論における最も重要な結果の一つです。この定理は、通信路容量 $C$ という単一の量が存在し、それより低い任意の伝送レート $R < C$ では、符号長を十分に長くすることで誤り確率をいくらでも小さくできること、そして容量 $C$ より高いレートではそれが不可能であることを示しています。
この定理の強力さは、特定の通信路や符号化方式に依存せず、あらゆる通信路と符号化方式に対して普遍的な限界を与える点にあります。しかし、その証明は容易ではありませんでした。特に、容量以下であれば「良い符号」が存在することをいかに示すかが課題でした。特定の構造を持つ符号（例えば線形符号など）を構成してその性能を示すアプローチでは、全ての通信路に対して最適な符号の存在を示すことは困難です。シャノンがこの課題に対して導入した革新的な手法が、「ランダム符号化 (Random Coding)」でした。
本稿では、シャノンがノイズありチャネル符号化定理の証明で用いたランダム符号化の概念に焦点を当て、その技術的な詳細、証明における役割、そして情報理論における意義を深く掘り下げていきます。
ランダム符号化の概念とその目的
ランダム符号化とは、具体的にどのような符号帳（メッセージと符号語の対応リスト）を用いるかを示すのではなく、「確率的に符号帳を生成する」という発想に基づいた手法です。符号帳 $mathcal{C} = {mathbf{c}1, mathbf{c}_2, ..., mathbf{c}_M}$ （ここで $M$ はメッセージ数、$mathbf{c}_i$ は符号長 $n$ の符号語）を構成する各符号語 $mathbf{c}_i = (c{i1}, c_{i2}, ..., c_{in})$ の各要素 $c_{ij}$ を、入力アルファベット $mathcal{X}$ 上で定義されたある確率分布 $p(x)$ に従って、独立かつランダムに選ぶという手順をとります。これを $M$ 個の符号語全てに対して独立に行います。
このようにして生成された符号帳は、特定の構造を持たないという意味で「ランダム」です。シャノンの証明の核心は、このようにランダムに生成された符号帳の「平均的な性能」を評価することにありました。もし、ランダムに生成された符号帳の集合において、平均的な誤り確率が十分に小さいことが示せれば、少なくとも一つは誤り確率が小さい符号帳が存在することになります。これがランダム符号化を用いる最大の目的、すなわち存在証明です。
具体的な証明では、まず符号帳をランダムに生成し、次に受信信号からどのようにメッセージを復号するかという復号規則を定義します。典型的なのは、受信信号 $mathbf{y}$ に対して、最も尤もらしい（すなわち、チャネルの遷移確率 $p(mathbf{y}|mathbf{x})$ が最大となる）符号語 $mathbf{x}$ を持つメッセージを選択する最尤復号です。あるいは、送信された符号語と受信信号が「共同典型 (jointly typical)」であるかどうかを判定基準とする、漸近等分割性 (AEP) に基づく復号規則も用いられます。
証明の核心：平均誤り確率の上界評価
ランダム符号化による存在証明の鍵は、ランダムに選ばれた符号帳 $mathcal{C}$ に対する誤り確率 $P_e(mathcal{C})$ の、全ての可能な符号帳に対する平均値 $mathbb{E}[P_e(mathcal{C})]$ を評価することです。証明は、この平均誤り確率が、レート $R < C$ で符号長 $n$ を無限大に近づけるにつれてゼロに収束することを示します。
具体的には、まず任意の特定のメッセージ $i$ が送信された場合に、受信側で誤ってメッセージ $j$ と復号してしまう確率 $P_e(j|i,mathcal{C})$ を考えます。ランダム符号化を用いると、符号帳 $mathcal{C}$ はランダム変数とみなせるため、この条件付き確率もランダム変数です。シャノンは、特定の符号帳 $mathcal{C}$ に対する平均誤り確率 $P_e(mathcal{C})$ を、送信されたメッセージについて平均し、さらに符号帳のランダムな生成について平均した、全平均誤り確率 $mathbb{E}[P_e]$ を評価しました。
$mathbb{E}[P_e] = \mathbb{E}{mathcal{C}} \left[ \frac{1}{M} \sum{i=1}^M P_e(i,mathcal{C}) \right]$
ここで、$P_e(i,mathcal{C})$ はメッセージ $i$ が送信された時の誤り確率です。 この平均誤り確率を評価する際、シャノンは復号において誤りが起こる主要なケース、すなわち「送信した符号語 $mathbf{c}_i$ と受信信号 $mathbf{y}$ が典型的ではない」または「送信した符号語 $mathbf{c}_i$ ではない他の符号語 $mathbf{c}_j$ （$j \ne i$）と受信信号 $mathbf{y}$ が誤って典型的になってしまう」確率を解析しました。特に後者の確率は、ランダムに選ばれた符号語 $mathbf{c}_j$ が、送信された符号語 $mathbf{c}_i$ から生成された受信信号 $mathbf{y}$ に対して、あたかも $mathbf{c}_j$ から生成されたかのように見える確率であり、これは符号語 $mathbf{c}_j$ がランダムであることから独立性の性質を利用して評価できます。
ここで重要な数学的道具が使用されます。例えば、メッセージ $i$ が送られ符号語 $mathbf{c}_i$ が送信された際に、受信信号が $mathbf{y}$ となったとします。復号器は、他のどの符号語 $mathbf{c}_j$ ($j \ne i$) よりも $mathbf{c}_i$ の方が $mathbf{y}$ に対して尤もらしいと判断すれば正しく復号できます。誤りが発生するのは、ある $j \ne i$ に対して $mathbf{c}_j$ が $mathbf{y}$ に対して $mathbf{c}_i$ と同等かそれ以上に尤もらしく見える場合です。ランダム符号化では、$mathbf{c}_i$ と $mathbf{c}_j$ は確率的に独立に生成されます。この独立性が、誤り確率の上界を評価する上で非常に有効に働きます。
具体的な上界評価では、ユニオンバウンドやマルコフの不等式、チェルノフ限界のような確率論的なツールが活用されます。特に、相互情報量 $I(X;Y)$ やエントロピー $H(X)$ の概念が中心的な役割を果たします。平均誤り確率が $exp(-n E(R))$ のような形で指数関数的に減衰することを示し、レート $R$ が容量 $C$ 以下であれば、指数 $E(R)$ が正となり、誤り確率が符号長 $n$ とともにゼロに収束することを示します。この指数関数的な誤り確率の減少率は、ランダム符号化エラー指数（Random Coding Error Exponent）として知られ、シャノン自身やその後の研究者によって詳しく解析されました。
ランダム符号化による存在証明の論法
平均誤り確率 $mathbb{E}[P_e]$ が、レート $R < C$ で符号長 $n \to \infty$ のときにゼロに収束することが示されれば、証明の目標はほぼ達成です。なぜなら、$mathbb{E}[P_e] \to 0$ ということは、ランダムに生成された符号帳の「集合」の中で、誤り確率が非常に小さい符号帳が「存在しない」という事態の確率がゼロになることを意味するからです。したがって、少なくとも一つは、全平均誤り確率が $mathbb{E}[P_e]$ 以下となる（そして $mathbb{E}[P_e]$ がゼロに収束する）符号帳が存在することになります。
この論法は非常に強力です。具体的な「良い符号」を構成する必要がなく、その存在のみを保証するからです。これは数学における非構成的な存在証明の典型例であり、その後の情報理論や符号理論の研究において、様々な限界や存在を示すための標準的な手法の一つとなりました。
さらに、この存在証明から一歩進んで、平均誤り確率が $mathbb{E}[P_e]$ 以下である符号帳が存在することを示した後、そのような良い符号帳の中から、特定のメッセージに対する最大誤り確率も小さくなるような符号帳を選び出す追加的な手順が用いられることもあります。例えば、平均誤り確率が $\epsilon$ である符号帳が存在するならば、メッセージの半分以上に対する誤り確率が $2\epsilon$ を超えない符号帳が存在する、といった議論です。
歴史的背景と意義
シャノンのランダム符号化による証明は、当時の通信工学や符号理論研究者にとって、非常に斬新なものでした。それまで、誤りを訂正するための符号は、代数的な構造（例えば巡回符号や BCH 符号の初期の研究）を用いて構成されるのが一般的でした。これらの構成的な手法は具体的な符号の設計には役立ちますが、特定のチャネル容量を達成できるかどうかを示すには不十分でした。
シャノンは、符号語に特定の代数的な構造を与えるのではなく、確率的な構造（独立同一分布によるランダム生成）を与えることで、すべての可能な符号帳の集合の性質を論じ、存在証明へと持ち込みました。この手法は、具体的な符号構成法を示すものではありませんが、情報伝送レートの究極的な限界が容量 $C$ であることを揺るぎなく示しました。これは、それ以降の符号理論研究の方向性を決定づける上で極めて重要な意味を持ちました。研究者たちは、容量に近づく「良い符号」が確かに存在することを知り、そのような符号をいかに具体的に構成するか、あるいは容量に近づくような符号の性能をいかに効率的に復号するか、という問題に注力するようになりました。
ランダム符号化の考え方は、その後の多くの情報理論における存在証明や限界解析に応用されました。特に、多端子情報理論や分散情報源符号化など、より複雑な通信シナリオにおける容量の特性を明らかにする上で、確率論的な手法は不可欠となっています。
現代の情報科学における位置づけと関連研究
ランダム符号化そのものが具体的な符号構成法として実用されるわけではありませんが、その考え方は現代の情報科学においても多岐にわたって影響を与えています。
- 符号理論の理論解析: 近代的な高性能符号（例えば低密度パリティ検査符号 (LDPC) やターボ符号）の理論的な性能解析において、ランダム符号化の考え方、特に符号語集合全体に対する平均化というアプローチが引き続き強力なツールとして利用されています。ランダムに構成された符号族の性能を解析することで、その族の中に容量に近づく良い符号が存在することを示したり、特定の復号アルゴリズム（例えばメッセージパッシングアルゴリズム）の性能を平均的に評価したりします。
- 情報理論の拡張: 多端子情報理論（複数の送信機、受信機、中継器が存在するネットワーク）や情報源・チャネル符号化の共同設計など、シャノンのオリジナルのフレームワークを拡張する研究分野では、確率論的な手法が容量領域や限界を導出する上で不可欠です。ここでも、ランダム構成とその平均性能解析が基本的なアプローチとなります。
- 計算機科学との関連: ランダム化アルゴリズムの設計や解析といった計算機科学の分野においても、ランダム化によって問題が扱いやすくなるという発想は共通しており、ランダム符号化はその先駆けの一つと見なすことができます。
結論
クロード・シャノンがノイズのあるチャネル符号化定理の証明で導入したランダム符号化は、情報理論の歴史において極めて重要な概念です。これは、具体的な構成を示すことなく、情報伝送レートの究極的な限界である通信路容量が達成可能であることを証明するための、非構成的かつ確率論的な強力な手法でした。符号帳をランダムに生成し、その平均的な性能を評価するというアプローチは、その後の情報理論や符号理論の研究において、様々な存在証明や性能限界の導出における標準的なツールとなりました。
ランダム符号化そのものが直接的な符号設計に繋がるわけではありませんが、その背後にある確率論的な考え方と、集合の平均性能から個体の存在を導く論法は、情報科学における理論的な解析の基盤を築き、現代の研究においてもその影響は色濃く残っています。シャノンのこの洞察は、情報理論がいかに数学、特に確率論と深く結びついているかを示す顕著な例と言えるでしょう。