シャノン研究ノート

シャノンのフィードバックチャネル研究：離散無記憶チャネルにおける容量増加の可能性とその否定

Tags: 情報理論, クロード・シャノン, チャネル容量, フィードバック, 離散無記憶チャネル

はじめに：フィードバックチャネル研究の重要性

通信システムにおいて、受信側が得た情報を送信側に戻す仕組みをフィードバックと呼びます。直感的には、フィードバックを利用することで、送信側がチャネルの状態や過去の送信の結果を知ることができるため、より効率的で信頼性の高い通信が可能になると考えられます。情報理論の創始者であるクロード・シャノンは、『A Mathematical Theory of Communication』において、このフィードバックが通信路容量に与える影響についても理論的な考察を行いました。本稿では、特に離散無記憶チャネル（Discrete Memoryless Channel, DMC）におけるフィードバックの効果に関するシャノンの主要な結果と、その理論的意義、そしてその後の研究への影響について深く掘り下げます。

離散無記憶チャネル（DMC）とフィードバックの導入

まず、離散無記憶チャネル（DMC）の基本的なモデルを再確認します。DMCは、入力アルファベット $\mathcal{X}$、出力アルファベット $\mathcal{Y}$、そして遷移確率行列 $P(y|x)$ で定義される確率チャネルです。ここで、任意の入力記号列 $x_1, x_2, \dots, x_n$ に対して、対応する出力記号列 $y_1, y_2, \dots, y_n$ が得られる確率は、過去の入出力に依存せず、各時刻の遷移確率の積として与えられます。すなわち、$P(y_1, \dots, y_n | x_1, \dots, x_n) = \prod_{i=1}^n P(y_i | x_i)$ となります。

フィードバックのあるチャネルでは、時刻 $i$ における送信記号 $x_i$ を決定する際に、過去のすべての入出力記号 $x_1, \dots, x_{i-1}$ および $y_1, \dots, y_{i-1}$ を利用することができます。フィードバックがない場合、送信記号 $x_i$ は過去の入力のみ $x_1, \dots, x_{i-1}$ に依存する（あるいはまったく独立に選択される）のが一般的です。フィードバックは、送信機がチャネルの過去の挙動や受信機が何を受け取ったかを知る手段を提供します。

シャノンの主要定理：フィードバックのあるDMC容量

シャノンの情報理論における最も驚くべき結果の一つは、離散無記憶チャネルにおいて、フィードバックが存在しても通信路容量は増加しないという定理です。より正確には、フィードバックがある場合の通信路容量は、フィードバックがない場合の容量と完全に等しいことを示しました。フィードバックがない場合のDMC容量 $C$ は、入力確率分布 $P(x)$ について相互情報量 $I(X;Y)$ を最大化することで得られることは周知の事実です。

定理（シャノン, 1958年論文より）：離散無記憶チャネルにおいて、フィードバックが存在する場合の通信路容量は、フィードバックが存在しない場合の通信路容量に等しい。

この定理は、フィードバックが通信性能を向上させるという直感に反するように見えます。しかし、この結果はDMCという特定のモデルに対するものであり、チャネルが記憶を持っていたり、連続値であったり、送信機がチャネル状態情報を事前に知っていたりする場合には、フィードバックが容量を増加させる可能性があります。

証明の核心

シャノンがこの定理を証明した基本的な考え方は、『A Mathematical Theory of Communication, Part II: Discrete Channels with Noise』に記述されており、より詳細な議論は彼の後年の論文にも見られます（例えば、"The Zero Error Capacity of a Noisy Channel" に関連する議論）。証明の鍵は、フィードバックが送信側に追加の情報を提供するものの、それが容量の定義に本質的な影響を与えないことを情報理論的な量（相互情報量）を用いて示す点にあります。

フィードバックがある場合、時刻 $i$ の入力 $X_i$ は、過去の入出力 $(X^{i-1}, Y^{i-1}) = (X_1, \dots, X_{i-1}, Y_1, \dots, Y_{i-1})$ に依存して決定される符号化戦略を取ることができます。長さ $n$ の符号語全体 $X^n = (X_1, \dots, X_n)$ と出力語 $Y^n = (Y_1, \dots, Y_n)$ の間の相互情報量 $I(X^n; Y^n)$ を考える際に、連鎖律（chain rule）を用いると、

$I(X^n; Y^n) = \sum_{i=1}^n I(X_i, X^{i-1}; Y^n | Y^{i-1})$

となります。DMCの無記憶性より、$P(Y_i | X^n, Y^{i-1}) = P(Y_i | X_i)$ であること、そしてフィードバックがある場合 $X_i$ が $X^{i-1}$ と $Y^{i-1}$ の関数であることから、いくつかの情報理論的な等式を用いると、最終的に $I(X^n; Y^n) \le \sum_{i=1}^n I(X_i; Y_i | Y^{i-1})$ のような関係が得られます。さらに、フィードバックにより $X_i$ は $Y^{i-1}$ に依存しますが、この依存性は $I(X_i; Y_i | Y^{i-1})$ を増加させません。厳密な証明は、条件付き相互情報量の性質や凸性などを利用して、結局フィードバックがない場合の容量 $C = \max_{P(x)} I(X;Y)$ を超えるレートでの信頼性のある通信が不可能であることを示します。

シャノンの証明の核心は、フィードバックが提供する情報が、通信路自体の統計的特性（遷移確率）を変えるわけではないため、単位時間あたりに伝送できる情報量の上限を定める相互情報量の最大値を変えない、という点にあります。フィードバックは符号化・復号化の複雑性を減らす可能性はありますが、理論的な情報レートの限界（容量）には影響を与えません。

理論的意義と歴史的背景

この定理は、情報理論の基礎においてフィードバックの役割を明確に定義した点で非常に重要です。1940年代後半から1950年代にかけて、通信システム設計者はフィードバックを利用することでノイズの影響を完全に除去できる、あるいは容量を無限にできるといった誤解を持っていることがありました。シャノンの結果は、DMCにおいてはフィードバックが容量という観点からは無価値であることを明確に示し、フィードバックの真の価値（例：実装の容易さ、遅延の削減、単方向通信では困難な特定のタスクの実現など）に対する理解を深めるきっかけとなりました。

また、この定理は、シャノンのチャネル符号化定理（ノイズのあるチャネル符号化定理）の証明においても、フィードバックがない場合のみならず、フィードバックがある場合にも同じ容量が達成可能であることを示すために利用されました。これは、フィードバックがない場合の容量が通信路の究極的な限界であることを裏付ける結果となりました。

現代における位置づけと発展

シャノンによるDMCにおけるフィードバックの容量不変性という結果は、情報理論における古典的な定理として確固たる地位を築いています。しかし、現代の情報理論研究では、シャノンの基本モデルを拡張した様々なチャネルモデルにおいて、フィードバックがどのような影響を与えるかが活発に研究されています。

例えば、以下のようなケースではフィードバックが容量を増加させることが知られています。

さらに、フィードバックは容量増加に寄与しない場合でも、符号化・復号化の複雑性の低減、最小遅延の実現、または特定のタスク（例：逐次的な決定、制御）における性能向上に役立ちます。実際、現代の多くの通信システム（例：TCP/IPにおけるACK/NACK、ARQプロトコル）では、容量の最大化というよりは、信頼性や遅延の要求を満たすためにフィードバックが効果的に利用されています。

シャノンによるDMCフィードバック容量の定理は、これらの発展的研究の出発点となりました。フィードバックの価値がチャネルの特性（無記憶性、離散性、連続性、状態情報など）にどのように依存するのかという深い問いは、この定理によって初めて明確に提起されたと言えるでしょう。

結論

クロード・シャノンによる離散無記憶チャネルにおけるフィードバックの容量不変性に関する研究は、情報理論の基礎を築く上で重要な貢献でした。この結果は、フィードバックが通信路容量という理論的な限界に影響を与えないことを示し、フィードバックの実際の価値が容量増加以外の側面にあることを示唆しました。シャノンのこの洞察は、その後の情報理論や通信工学におけるフィードバックに関する研究の方向性を定め、記憶チャネル、連続チャネル、チャネル状態情報のあるチャネルなど、より複雑なモデルにおけるフィードバックの役割に関する活発な研究を促しました。シャノンの原論文を紐解くことで、この古典的ながらも奥深い結果の厳密な導出過程と、その情報理論体系における位置づけを再確認することは、現代の研究者にとっても依然として大きな意義を持つと言えるでしょう。