このページの目次
チャネル容量と符号化
シャノンの符号化定理は、情報論において最も直感に反する結論の一つである。伝送レートがチャネル容量 C = max I(X;Y) より下であれば、誤り率を任意の低い値に押し下げることが可能だ。信頼性を得るためにレートを犠牲にする必要はなく、その代償はより長く、より賢い符号化のみである。この定理は通信の物理的限界を定義しており、現代の LDPC/Turbo コードはすでにその限界に近づいている。
導入: 間違いを避けては通れない回線
前の章では「いかに情報を圧縮するか」を扱った。本章ではその逆、情報を誤りの生じる回線を通過させて相手に届ける際、ノイズによって情報が破壊されないようにするにはどうすればよいかを問う。
回線はビットを反転させ、ノイズを重畳させる。最も愚かな対策は冗長性を加えることだ。例えば、各ビットを3回再送し、受信側で多数決を取る方法がある。しかし、これでは伝送レートが 1/3 に低下し、さらにノイズが大きいと依然として誤りが生じる。
1948年、シャノンは学界を驚かせた答えを示した。あなたは、信頼性を得るために伝送レートを犠牲にする必要はない。伝送レートが何らかの閾値を下回っていれば、誤り率を任意の低い値に押し下げることができ、レートは1ビットも減らさなくてよい。この閾値こそがチャネル容量である。本章ではこれを明確にする。
チャネルモデル: ノイズのモデル化
まず、計算可能なノイズモデルが必要である。チャネル(channel) とは、入力 X をノイズ付きの出力 Y に写像するものであり、条件分布 p(y \mid x) によって記述される。直感を支える最も基本的なモデルが2つある。
- バイナリ対称チャネル (Binary Symmetric Channel, BSC): 入力は 0 / 1 で、確率 p で反転し（0 が 1 に、または 1 が 0 に）、確率 1-p で正しく通過する。ここで言う p が誤り率である。これはデジタル通信における最も単純な抽象化であり、各ビットが独立して一定の確率でノイズによって反転するモデルである。
- 加性ガウス白雑音チャネル (AWGN): 出力は Y = X + N で表され、ここで N は平均 0、分散 \sigma^2 のガウス雑音である。これはアナログ / ワイヤレスチャネルの標準モデルである。信号は伝送中にランダムなノイズの層を被り、信号対雑音比 \text{SNR} が高いほど、相対的なノイズは小さくなる。
チャネルの本質的な制約は、ノイズによって受信側が発信された内容が完全に特定できず、Y は X に関する部分的な情報しか持たない点にある。そして、その「部分」がどれほど多いかは、まさに相互情報量によって測られる。
相互情報量: チャネルは実際にどれだけの情報を伝えたか
チャネルを1回使用した際、出力 Y が入力 X について持つ情報量は、相互情報量である。
I(X;Y) = H(X) - H(X \mid Y)
分解して読むと非常に自然である。送信前の X に対する不確実性は H(X) であり、Y を受信した後の残存不確実性は H(X \mid Y) である（これがノイズによって導入された曖昧さである）。この2つの差こそが、チャネルを無事に通過した情報である。
3つの極端なケースで直感を養う。
- ノイズレスチャネル: H(X \mid Y)=0、I(X;Y)=H(X)。送ったものがそのまま届く。
- 純粋なノイズチャネル (Y と X が独立): I(X;Y)=0。受信した情報は入力の推測に全く役立たない。
- BSCにおける1ビットあたりの相互情報量: I = 1 - H(p)。ここで H(p) は 二元エントロピー関数 である。p=0.5 のとき、H(p)=1、I=0 となる。反転確率が半分であることは純粋なノイズと同等であり、チャネルは完全に機能停止する。
チャネル容量とシャノンの符号化定理
チャネル容量(channel capacity) は、すべての可能な入力分布にわたって、相互情報量が取り得る最大値として定義される。
C = \max_{p(x)} I(X;Y)
これは、このチャネルを1回使用したときに、信頼性を持って運べるビット数の最大値であり、単位は bit / チャネル使用である。
シャノンの符号化定理(1948) は、その直感に反する結論を示す。
いかなる伝送レート R < C に対しても、復号誤り率を任意に 0 に近づける符号化方式が存在する。逆に、R > C の場合、誤り率を 0 にすることはできず、信頼性の高い伝送は不可能である。
直感に反するのはどこか？人々は「誤り率を下げたいならば、レートを下げる必要がある（例えば、各ビットを3回再送すればレートは 1/3 になる）」と考えていた。しかしシャノンは必要ないと言う。C 以下であれば、レートを維持しつつ、誤り率を任意に低くできる。
では、その代償はどこで支払うのか？符号化の複雑さと符号語の長さである。方法は、多数のビットをパックして長い符号語とし、長いブロック上の統計的規則性を用いてノイズに抵抗することだ。符号語が長ければ長いほど、この限界に近づく。
この定理は2つの側面から成り立っている。一方は下界の到達可能性を保証し、他方は上界を封じる。到達可能性(achievability) は、R<C の場合にランダム符号を用いて良好な符号を構成できることを示す（これは存在性の証明であり、具体的な符号は与えない）。逆定理(converse) は、R>C の場合、いかなる符号でも非ゼロの誤りを免れないことを示す。この2つが上下から C という鋭い閾値を絞り込む。
BSC の容量を計算する
抽象的な議論が終わったので、数値を当てはめてみよう。BSC の容量には閉じた解が存在する: C = 1 - H(p)。ここで p は反転確率、H(p) は 二元エントロピー関数 である。
- p=0 (ノイズレス): H(0)=0、C=1 bit。1回の使用で最大 1 bit を満杯で伝送できる。
- p=0.11 (約 11\% の誤り): H(0.11)\approx 0.5、C\approx 0.5 bit。信頼性を持って伝送するには、情報 1 bit あたり約 2 ビットのチャネルビットを送る必要があり、帯域の半分がノイズ対策に費やされる。
- p=0.5 (純粋なノイズ): H(0.5)=1、C=0 bit。出力と入力は独立しており、情報は伝送できない。
- p=1 (必ず反転): C=1 bit。興味深いことに、確定的な反転はノイズではない。受信後に反転すれば、情報は損なわれない。
最後の例は、一般的な誤解を解くものである。チャネルを殺すのは反転そのものではなく、p=0.5 の「最大の不確実性」である。容量を達成する最適な入力分布は、ここでは一様分布（0 / 1 が等確率）である。これは、C の定義で \max を用いてすべての入力分布にわたって最大化する必要がある理由も説明している。チャネルがどれだけの情報を伝送できるかは、あなたが入力にどのように分布を与えるかにも依存するからである。
直感に反するが重要なポイント
- 信頼性の高い伝送のために、レートを犠牲にする必要はない。 直感的には「より信頼性を高めたいなら冗長性を増やし、レートを下げるべきだ」と思われるかもしれない。しかしシャノンは、R<C であれば、ゼロエラーのためにレートを犠牲にするのではなく、符号語の長さを犠牲にすればよいと言う。リピート符号（1 bit を3回送信するなど）は最も愚かなノイズ対策であり、レートが 1/3 に低下するだけでなく、良好な符号には遠く及ばない。
- 容量は硬い壁であり、緩い制約ではない。 R>C の場合、「誤り率が少し高くなる」のではなく、原理的に 0 にすることはできない。冗長性をどれだけ増やし、いかに賢い符号を使おうとも無駄である。この線は逆定理によって厳密に証明されている。
- シャノンは「存在」のみを証明し、「どのように構築するか」は示さなかった。 定理はランダム符号を用いて良好な符号が存在することを証明したが、効率的な符号化・復号の方法については一言も触れていない。この存在性と構成性との間の溝は、符号化理論の半世紀以上を支えてきた。
シャノンの限界の工学的意義
強調するが、シャノンの定理は存在性のものである。良好な符号が存在することを証明したが、どのように構築するかは教えてくれず、復号がどれほど速いかについても言及していない。その後の半世紀以上にわたる符号化理論は、この「シャノンの限界」に追いつくこと、すなわち C に近づきながら効率的な符号化・復号が可能な実用的な符号を作ることを目指してきた。
- 初期のハミング符号やリード・ソロモン符号は、限界から遠く離れていた。
- Turbo符号(1993) と LDPC符号(Gallager 1962, 1990年代に再発見) は、反復復号 / 信頼度伝播復号を用い、AWGN チャネルにおいてシャノンの限界から 1 dB 以内に到達した。これは通信工学における勝利であり、現在では 5G、Wi-Fi 6、深宇宙通信などで LDPC が使用されている。
- 具体的な誤り訂正符号の構成と反復復号の詳細についてはここで触れるにとどめる。覚えておくべき骨格は、理論的限界はシャノンの定理によって定められており、工学の数十年はすでにその限界に近づいているということである。
最後に、美しい双対性について言及しよう。チャネル符号化（ノイズに対抗するためにデータに慎重に冗長性を加えること）と ソース符号化 / 圧縮（冗長性を絞り尽くし、エントロピーに近づけること）は、鏡のような関係にある。一方は冗長性を加え、他方は冗長性を除去するが、両端とも情報論の限界定理によって支えられている。
参考文献
- 論文: "A Mathematical Theory of Communication" (Shannon, 1948 — チャネル容量と符号化定理の原典)
- 教科書: "Elements of Information Theory" (Cover & Thomas — 第7章 チャネル容量, BSC/AWGN および容量の導出)
- 論文: "Near Shannon Limit Error-Correcting Coding and Decoding: Turbo-Codes" (Berrou et al., 1993 — シャノンの限界に初めて近づいた実用的符号)
キーワード: チャネル容量 channel capacity, バイナリ対称チャネル BSC, 加性ガウス白雑音 AWGN, 相互情報量 mutual information, チャネル符号化定理 channel coding theorem, シャノンの限界 Shannon limit, LDPC, Turbo符号, 到達可能性と逆定理