クロード・シャノンによるメモリ付き離散通信路の容量：定義、性質、そして情報理論的分析
クロード・シャノンによるメモリ付き離散通信路の容量：定義、性質、そして情報理論的分析
クロード・シャノンが1948年に発表した金字塔的な論文『A Mathematical Theory of Communication』は、情報理論の体系を確立しました。この論文では、離散無記憶通信路（Discrete Memoryless Channel; DMC）の容量が中心的に扱われていますが、シャノンは§24において、より一般的なメモリ付き離散通信路（Discrete Channel with Memory; DCM）についてもその定義と情報理論的な分析の端緒を示しています。本稿では、シャノンがどのようにメモリ付き通信路を捉え、その容量を定義し、分析したのかを掘り下げます。
メモリ付き離散通信路のモデル化
無記憶通信路が、ある時刻における出力がその時刻の入力のみに依存する（過去の入出力には依存しない）通信路であるのに対し、メモリ付き通信路では、現在の出力が過去の入出力、あるいは通信路の内部状態に依存します。シャノンはこのような通信路を、確率過程としてモデル化しました。
具体的には、時刻 $i$ における入力記号を $X_i$（入力アルファベット $\mathcal{X}$ から）、出力記号を $Y_i$（出力アルファベット $\mathcal{Y}$ から）とするとき、メモリ付き通信路は条件付き確率分布 $P(Y_i | X_i, X_{i-1}, Y_{i-1}, \dots)$ あるいはより一般に $P(Y_i | X_i, \text{channel state}_i)$ によって特徴づけられます。ここで「channel state」は過去の入出力履歴によって決定される、通信路の内部状態を表します。
シャノンは特に、出力確率が現在の入力と通信路の内部状態のみに依存し、その内部状態が過去の入力系列によってのみ遷移するような、一種の有限状態チャネル（Finite State Channel; FSC）やマルコフチャネルに相当するモデルを念頭に置いていました。つまり、時刻 $i$ の出力 $Y_i$ の分布は、入力 $X_i$ と、時刻 $i$ における通信路の状態 $S_i$ によって決まり、$S_i$ は $S_{i-1}$ と $X_{i-1}$ によって決まる、といった構造です。このようなモデルは、実際の通信路におけるエコー、干渉、フェージングなどの「メモリ」を持つ現象を捉えるために重要です。
メモリ付き通信路の容量の定義
離散無記憶通信路（DMC）の容量 $C$ は、単一のシンボル使用における入力 $X$ と出力 $Y$ の間の相互情報量 $I(X;Y)$ を、可能な全ての入力確率分布 $P(X)$ について最大化した値として定義されます。
$C = \max_{P(X)} I(X;Y)$ （DMCの場合）
しかし、メモリ付き通信路では、単一のシンボル使用における相互情報量は、過去の履歴によって変動するため、チャネルの性能を一意に定める指標としては適切ではありません。シャノンは、長い系列を考えることで、漸近的な性質に基づいて容量を定義しました。
長さ $n$ の入力系列 $X^n = (X_1, X_2, \dots, X_n)$ に対する出力系列を $Y^n = (Y_1, Y_2, \dots, Y_n)$ とします。メモリ付き通信路における容量は、このような長い系列に対する平均相互情報率の極限として定義されます。
まず、系列に対する相互情報量を $I(X^n; Y^n)$ と定義します。これは $H(X^n) + H(Y^n) - H(X^n, Y^n)$ あるいは $H(Y^n) - H(Y^n|X^n)$ 等として計算できます。
メモリ付き通信路の容量 $C$ は、次のように定義されます。
$C = \lim_{n \to \infty} \max_{P(X^n)} \frac{1}{n} I(X^n; Y^n)$
ここで、最大化は可能な全ての入力系列の確率分布 $P(X^n)$ について行われます。シャノンは論文中で、もし入力情報源が定常エルゴード的であれば、上記の定義は
$C = \sup_{\text{stationary ergodic sources } P(X^\infty)} \lim_{n \to \infty} \frac{1}{n} I(X^n; Y^n)$
としても等価であることを示唆しています。これは、容量が通信路自身の性質であり、特定の優れた入力情報源（あるいは符号化戦略）に依存しない値であることを意味します。
この定義は、無記憶通信路における容量の定義の自然な拡張となっています。無記憶通信路の場合、$I(X^n; Y^n) = \sum_{i=1}^n I(X_i; Y_i)$ となり、入力 $X_i$ を独立同分布（i.i.d.）に選ぶことで $P(X^n)$ を構成すれば、$\frac{1}{n} I(X^n; Y^n) \to I(X;Y)$ となり、上記の定義が無記憶通信路の容量定義に帰着することが理解できます。
シャノンによる分析の核心
シャノンがメモリ付き通信路の容量を分析する上で核となるのは、漸近等分割性（Asymptotic Equipartition Property; AEP）の概念が、特定の条件下ではメモリ付きの情報源やチャネルにも拡張できるという洞察です。無記憶情報源に対して成立するAEPは、「長い系列のほとんどは『典型集合』に属し、その確率はほぼ等しく、情報源のエントロピー率によってその集合のサイズが決まる」というものでした。シャノンは、定常エルゴード的な確率過程によって生成される系列にも、同様の漸近的な性質が成り立つことを示しました。
通信路の文脈では、これは「条件付きAEP」として現れます。特定の入力系列 $x^n$ が与えられたとき、それに対応する出力系列 $y^n$ のほとんどは、条件付きエントロピー率 $H(Y|X)$ に対応する確率で分布する「条件付き典型集合」に属します。
シャノンの容量定理（ノイズのあるチャネル符号化定理）は、「容量 $C$ 未満のレートであれば、誤り確率を任意に小さくできる符号が存在する」という存在定理です。この定理の証明は、ランダム符号化と呼ばれる構成法に依存しており、符号帳をランダムに生成し、AEPや共同典型性（Joint Typicality）を用いてデコーディングの成功確率を評価します。この証明のフレームワークは、メモリ付き通信路に対しても、適切な漸近性（例えば、定常エルゴード性）が仮定されれば、そのまま適用可能であることが示唆されます。つまり、メモリ付き通信路の容量もまた、情報伝送レートの根本的な限界を定める値となります。
容量の計算そのものは、無記憶チャネルの場合に比べて一般には遥かに困難です。無記憶チャネルでは、相互情報量 $I(X;Y)$ が入力分布 $P(X)$ に対して凸関数であり、凸最適化問題として容量を計算できます。しかし、メモリ付きチャネルでは、系列全体の確率分布 $P(X^n)$ を最適化する必要があり、これは次元が $n$ と共に指数関数的に増加するため、直接的な計算は非現実的です。
シャノン自身は、特定の単純なメモリ構造を持つ通信路（例: 過去の入力一つに依存するチャネル）について容量を計算したり、その bounds を与えたりしています。容量の正確な計算は、一般には状態空間が有限であるようなマルコフチャネルなど、構造化されたメモリを持つチャネルに対して、動的計画法や行列計算を用いた手法（例: ブラーハット・有本アルゴリズムの拡張など、シャノン以降の研究で発展したもの）によって行われます。
歴史的意義と現代における位置づけ
シャノンがメモリ付き通信路を情報理論の枠組みに含めたことは、理論の実応用における関連性を高める上で極めて重要でした。実際の通信環境は、電波伝搬の遅延、マルチパス、システム内部の回路特性などにより、ほとんどがメモリを持つチャネルとして振る舞います。シャノンの理論は、このような現実の通信路においても、情報伝送の基本的な限界が存在し、その限界がメモリ構造に依存して定まることを示しました。
シャノン以降の情報理論研究では、様々な種類のメモリ付きチャネル（マルコフチャネル、フェージングチャネル、チャネル状態情報を持つチャネルなど）が詳細に分析され、それぞれの容量が研究されてきました。また、メモリ付きチャネルに対する効率的な符号化・復号化技術（例: 畳み込み符号、ターボ符号、LDPC符号など、過去の入力や状態に依存する構造を持つ符号）の研究は、現代のデジタル通信システムの発展に不可欠な要素となっています。
シャノンのメモリ付き通信路に関する初期の記述は、これらの広範な研究の基盤を提供しました。彼の容量定義は、漸近的な性質に焦点を当てることで、複雑な時間依存性を本質的な情報伝送能力という一つの数値に集約するという、極めて強力な概念的枠組みを与えています。
結論
クロード・シャノンによるメモリ付き離散通信路の導入と容量の定式化は、『A Mathematical Theory of Communication』の重要な一側面であり、情報理論の普遍性を示すものです。無記憶通信路の容量定義を、長い系列に対する平均相互情報率の極限へと拡張することで、彼はより現実的な通信モデルに対しても情報伝送レートの理論的な限界を定めることに成功しました。容量の計算はメモリ構造に依存して複雑になりますが、シャノンが提示した概念的フレームワークと漸近的な分析手法は、その後のメモリ付きチャネルに関する研究、そして現代の高度な符号化技術の発展に不可欠な基礎を提供しています。シャノンの原論文を読むことは、これらの発展がどのように彼の根本的な洞察に基づいているのかを深く理解する上で、今なお非常に有益であると言えるでしょう。