クロード・シャノンによるフィードバックチャネルの分析：離散無記憶チャネルにおける容量不変性とその理論的意義
はじめに：通信路フィードバックの概念とシャノンの問い
通信システムにおいて、受信側が得られた情報の一部または全部を送信側に送り返す仕組みは「フィードバック」と呼ばれ、古くから広く用いられてきました。例えば、自動再送要求（ARQ）プロトコルは、エラー検出信号をフィードバックとして利用する代表的な例です。このようなフィードバックが、情報理論的な意味での通信路容量にどのような影響を与えるのかは、クロード・シャノンが『A Mathematical Theory of Communication』をはじめとする初期の研究で探求した重要な問いの一つでした。
本稿では、シャノンが通信路フィードバックについてどのように分析したのか、特に離散無記憶チャネル（Discrete Memoryless Channel, DMC）における容量に関するその主要な結果である「容量不変性」、すなわちフィードバックが存在してもDMCのチャネル容量は変化しないという定理に焦点を当てて深く掘り下げます。この結果が持つ理論的な意義、そして容量は増加しないとしてもフィードバックが符号化・復号の設計に与える影響について考察します。
フィードバックチャネルのモデル化
情報理論においてフィードバックチャネルを扱う際、通信路は通常のチャネルモデルに加えて、受信機からのフィードバック信号を生成する機能を持つと見なされます。時点 $i$ における入力シンボルを $X_i$、出力シンボルを $Y_i$ とします。通常の無記憶チャネルでは、時点 $i$ における出力 $Y_i$ の確率分布は、入力 $X_i$ のみに依存し、過去の入出力系列 $(X_1, \dots, X_{i-1}, Y_1, \dots, Y_{i-1})$ には依存しません。
フィードバックがある場合、時点 $i$ における送信機の入力 $X_i$ を決定する際に、過去の受信出力系列 $(Y_1, \dots, Y_{i-1})$ を利用できると考えます。より一般的には、過去の入力系列 $(X_1, \dots, X_{i-1})$ も利用可能ですが、これはフィードバックがなくとも送信機自身が記憶しておける情報であるため、フィードバックの本質は受信結果 $Y_1, \dots, Y_{i-1}$ を送信機が知りうる点にあります。
したがって、時点 $i$ における入力 $X_i$ は、符号器によって、送りたいメッセージ $M$（これは $N$ 個の可能なメッセージから一つ選ばれるとします）と、過去の受信出力系列 $(Y_1, \dots, Y_{i-1})$ の関数として決定されます。 $$ X_i = f_i(M, Y_1, \dots, Y_{i-1}) $$ ただし、$Y_0$ は存在しないため、$X_1 = f_1(M)$ となります。チャネルは無記憶であるため、時点 $i$ における条件付き確率分布 $P(Y_i | X_i, Y_1, \dots, Y_{i-1}, X_1, \dots, X_{i-1})$ は $P(Y_i | X_i)$ に等しくなります。
離散無記憶チャネル (DMC) における容量不変性
シャノンは、離散無記憶チャネル（DMC）において、フィードバックが存在してもチャネル容量は変化しないことを示しました。つまり、フィードバック付きDMCの容量 $C_{FB}$ は、フィードバックなしのDMCの容量 $C$ に等しいということです。 $$ C_{FB} = C = \max_{P(x)} I(X;Y) $$ ここで、$I(X;Y)$ は入力 $X$ と出力 $Y$ の間の相互情報量であり、容量は入力シンボルの確率分布 $P(x)$ について最大化することで得られます。
この結果は、直感に反するように感じられるかもしれません。送信機が受信結果を知ることができるならば、それを活用してより効率的な符号化が可能になり、容量が増加するのではないか、と考えることもできます。しかし、DMCにおいては、これは成り立ちません。
容量不変性の証明の核心
シャノンがDMCにおける容量不変性を示す際に用いた主な考え方は、フィードバックが存在しても、任意の入力系列 $X^n = (X_1, \dots, X_n)$ と対応する出力系列 $Y^n = (Y_1, \dots, Y_n)$ の間の相互情報量 $I(X^n; Y^n)$ が、フィードバックがない場合の相互情報量の合計を超えることがない、という点にあります。
フィードバック付きチャネルにおける $n$ タイムスロット間の相互情報量は、以下のように展開できます。 $$ I(X^n; Y^n) = H(Y^n) - H(Y^n | X^n) $$ チャネルが無記憶であることから、$H(Y^n | X^n) = \sum_{i=1}^n H(Y_i | X_i)$ が成り立ちます。 また、相互情報量は連鎖律を用いて次のように書くことができます。 $$ I(X^n; Y^n) = \sum_{i=1}^n I(X^n; Y_i | Y^{i-1}) = \sum_{i=1}^n I(X_i, X^{i-1}; Y_i | Y^{i-1}) $$ ここで、$Y^{i-1} = (Y_1, \dots, Y_{i-1})$, $X^{i-1} = (X_1, \dots, X_{i-1})$ です。 $X_i$ は $M$ と $Y^{i-1}$ の関数として決定されるため、$Y^{i-1}$ が与えられた条件下では、$X_i$ は $M$ にのみ依存すると考えることができます（あるいは、$M$ が既知であれば $X_i$ は $Y^{i-1}$ にのみ依存）。より正確には、$(X_i, X^{i-1})$ と $Y_i$ の間の条件付き相互情報量を考えます。 DMCにおいては、$Y_i$ は過去の入出力系列に条件付けられても、現在の入力 $X_i$ にのみ統計的に依存します。つまり、$P(Y_i | X_i, X^{i-1}, Y^{i-1}) = P(Y_i | X_i)$ です。 これを用いると、相互情報量の連鎖律は次のように変形できます。 $$ I(X^n; Y^n) = \sum_{i=1}^n I(X^n; Y_i | Y^{i-1}) = \sum_{i=1}^n [H(Y_i | Y^{i-1}) - H(Y_i | X^n, Y^{i-1})] $$ また、$H(Y_i | X^n, Y^{i-1}) = H(Y_i | X_i, X^{i-1}, Y^{i-1}) = H(Y_i | X_i)$ です。 $$ I(X^n; Y^n) = \sum_{i=1}^n [H(Y_i | Y^{i-1}) - H(Y_i | X_i)] $$ ここで、$H(Y_i | Y^{i-1}) \le H(Y_i)$ であり、さらにフィードバックによって $X_i$ が $Y^{i-1}$ に依存するとしても、$I(X_i; Y_i | Y^{i-1}) = H(Y_i | Y^{i-1}) - H(Y_i | X_i, Y^{i-1}) = H(Y_i | Y^{i-1}) - H(Y_i | X_i)$ となりますが、これは $I(X_i; Y_i)$ とは一般に異なります。 しかし、より直接的なアプローチとして、送信機の持つ情報 $M$ と受信機の持つ情報 $Y^n$ の間の相互情報量 $I(M; Y^n)$ を考えます。フィードバック付き符号化では、送信機は $M$ と $Y^{i-1}$ を基に $X_i$ を生成します。このとき、データ処理の不等式（Data Processing Inequality）を用いると、メッセージ $M$ は送信機の入力 $X^n$ を通してのみチャネル出力 $Y^n$ に影響を与え、かつフィードバック $Y^{i-1}$ は過去の出力であるため、以下の関係が成り立ちます。 $$ I(M; Y^n) \le I(X^n; Y^n) $$ また、 $$ I(X^n; Y^n) = \sum_{i=1}^n I(X^n; Y_i | Y^{i-1}) $$ フィードバックにより $X_i$ は $Y^{i-1}$ に依存しますが、チャネルは無記憶であるため $Y_i$ は $X_i$ にのみ直接依存します。条件付き相互情報量 $I(X^n; Y_i | Y^{i-1})$ を展開すると、$I(X_i, X^{i-1}; Y_i | Y^{i-1}) = I(X_i; Y_i | Y^{i-1}) + I(X^{i-1}; Y_i | X_i, Y^{i-1})$ となります。無記憶性より $I(X^{i-1}; Y_i | X_i, Y^{i-1}) = 0$ です。 したがって、$I(X^n; Y^n) = \sum_{i=1}^n I(X_i; Y_i | Y^{i-1})$ となります。 さらに、$I(X_i; Y_i | Y^{i-1}) \le I(X_i; Y_i)$ が成り立ちます。これは条件付けは相互情報量を減少させないという性質に基づいているわけですが、ここでは $Y^{i-1}$ が $X_i$ を決定する情報として送信機で使われる点が重要です。より厳密な証明では、情報メトリックの凸性や連鎖律を慎重に適用し、フィードバックによって $X_i$ の選択が $Y^{i-1}$ に依存するとしても、情報伝送レートの上限である相互情報量の和は無フィードバックの場合のチャネル容量の和を超えることはない、という結論を導きます。特に、 $$ I(X^n; Y^n) = \sum_{i=1}^n I(X_i; Y_i | Y^{i-1}) $$ であり、ここで $I(X_i; Y_i | Y^{i-1}) = H(Y_i | Y^{i-1}) - H(Y_i | X_i, Y^{i-1}) = H(Y_i | Y^{i-1}) - H(Y_i | X_i)$. また、$I(X_i; Y_i) = H(Y_i) - H(Y_i | X_i)$ です。 $I(X_i; Y_i | Y^{i-1}) \le I(X_i; Y_i)$ は一般には成り立ちませんが、フィードバックが $X_i$ の選択に影響を与えるとしても、適切に定義されたマルコフ連鎖関係 $M \to (X_1, \dots, X_i, Y_1, \dots, Y_{i-1}) \to Y_i$ を利用することで、漸化式的に容量の上限を評価することが可能です。シャノンはこのような議論を経て、最終的に $\frac{1}{n} I(M; Y^n)$ の上限が $C$ であることを示しました。
この定理の数学的詳細については、シャノンの原論文 [1] や情報理論の標準的な教科書（例：Cover & Thomas [2]）に詳細な証明が記述されています。核となるのは、フィードバック情報 $Y^{i-1}$ を知っていることは、現在の入力 $X_i$ と出力 $Y_i$ の間の相互情報量 $I(X_i; Y_i)$ を、適切な入力分布を選んだとしても、無フィードバック時の容量を超えるほどには増加させない、という事実です。
容量不変性の意義：理論と実践
DMCにおける容量不変性の結果は、理論的に非常に重要です。これは、理想的な条件下（無限長の符号、計算能力の制約なし）においては、単方向の情報伝送能力を決定する上で、受信結果を送信機に知らせることは究極的には無意味であることを示唆しています。通信路の「広さ」そのものは、過去の情報を知ることで変えることはできないのです。
しかし、これはフィードバックが通信システムにおいて役に立たないということを意味しません。シャノン自身も、フィードバックは符号化や復号の「複雑性」を軽減する可能性があることを示唆しています。容量は同じでも、フィードバックを利用することで、より単純な符号構成で容量に近い伝送レートを達成したり、復号の計算量を削減したりすることが可能になるのです。
例えば、ARQシステムは、エラーが起きたブロックのみを再送することで、再送がない場合に比べて実効レートを向上させます（ただしこれは定義上、エラーレートが非常に小さい場合にチャネル容量に近づけるための手段であり、容量そのものを増やしているわけではありません）。また、逐次復号アルゴリズムのように、フィードバックのアイデア（これまでの復号結果を次の復号に利用する）は復号計算量の削減に有効であることが知られています。シャノンは、フィードバックを利用した符号化戦略の例として、送信機が過去の受信結果に基づいて次に送るシンボルを変えることで、事実上「状態」を持つかのように振る舞う符号構成の可能性に言及しています。
DMC以外のチャネルにおけるフィードバック
シャノンの容量不変性の結果はDMCに限定されることに注意が必要です。メモリのある離散チャネルや連続チャネル、特にガウスチャネルにおいては、フィードバックが容量を増加させる場合があります。例えば、加法的白色ガウスノイズ（AWGN）チャネルにメモリがある場合や、複数の送信アンテナと受信アンテナを持つMIMOチャネル（ここでチャネル状態情報がフィードバックされる場合）などでは、フィードバックを利用することで容量が増加することが知られています。
この違いは、チャネルの「状態」が過去の入力や出力に依存して変化するかどうかに起因します。DMCではチャネルの統計的性質は常に一定で、過去の出来事に影響されません。そのため、送信機が過去の受信結果を知ったとしても、将来のチャネルの振る舞いについて新たな情報を得ることはできません。一方、メモリのあるチャネルや状態が変化するチャネルでは、過去の入出力系列はチャネルの状態に関する情報を含みうるため、フィードバックによって送信機がその状態を知ることで、将来の伝送をより効率的に適応させることが可能となり、結果として容量が増加することがあります。
結論
クロード・シャノンによるフィードバックチャネルの分析は、情報理論の基礎において重要な位置を占めます。特に、離散無記憶チャネル（DMC）における容量不変性の定理は、フィードバックが理想的な情報伝送能力（容量）そのものを増加させるわけではない、という基本的な限界を示しました。この結果は、容量の概念が通信路の固有の性質（統計的特性）によってのみ定まることを改めて強調するものです。
しかし同時に、シャノンの研究は、フィードバックが符号化・復号プロセスの設計において極めて有効なツールとなりうることを示唆しています。容量不変性はあくまで理論上の上限に関するものであり、有限長の符号や計算能力の制約といった現実的な条件下では、フィードバックは性能向上や実装の容易化に貢献します。今日の多くの通信システムにおけるフィードバックの広範な利用は、シャノンがその理論的基盤を築いたこの洞察に基づいています。
シャノンのフィードバックに関する初期の考察は、その後の情報理論や符号化理論の研究において、フィードバックを用いた符号構成や、様々なチャネルモデルにおけるフィードバックの影響を詳細に分析する研究へと発展していきました。DMCにおける容量不変性という一見シンプルな結果の背後には、情報、不確実性、そして通信路の性質に関するシャノンならではの深い洞察が存在しています。
参考文献
[1] Shannon, C. E. (1948). A Mathematical Theory of Communication. Bell System Technical Journal, 27(3), 379–423, and 27(4), 623–656. [2] Cover, T. M., & Thomas, J. A. (2006). Elements of Information Theory (2nd ed.). Wiley-Interscience.
(注：この定理の証明の詳細は、参考文献[1]のSection 22や参考文献[2]のChapter 7などに詳細に記述されています。)