シャノン情報理論における固定長ブロック符号化：定義、構成、そして漸近解析
はじめに
クロード・シャノンが1948年の画期的な論文『A Mathematical Theory of Communication』で確立した情報理論において、情報源符号化定理と通信路符号化定理は双璧をなす基本的な結果です。これらの定理の証明とその理論的限界の定式化において、中心的な役割を果たす概念が「固定長ブロック符号化（Fixed-Length Block Coding）」です。
本稿では、シャノン情報理論における固定長ブロック符号化の基本的な枠組み、すなわち情報源符号化および通信路符号化におけるその定義、構成要素、そして特にブロック長を無限大に漸近させる解析手法の意義について深く掘り下げていきます。情報科学分野の専門家の皆様にとって、シャノンの原論文の理解を深め、自身の研究における情報理論的アプローチの厳密性を高める一助となれば幸いです。
固定長ブロック符号化の基本的な考え方
固定長ブロック符号化は、ある固定された長さ（ブロック長）のシンボル列（ブロック）を一つの単位として扱い、これを別の固定された長さのシンボル列に変換するプロセスです。情報源符号化においては、情報源からの $N$ 個のシンボルブロックを、$KN$ 個（ただし $K < 1$）のシンボルブロックに圧縮します。一方、通信路符号化においては、$KN$ 個のシンボルブロックを送信に適した形で（通常、冗長性を加えて）$N$ 個のシンボルブロックに変換し、通信路を介して送信された後、再び元の $KN$ 個のシンボルブロックを復元することを試みます。
ここで重要なのは、符号化と復号がブロック単位で行われること、そしてブロック長 $N$ がシステム設計時に固定されることです。シャノンの主要な定理は、このブロック長 $N$ を無限大に漸近させた極限性能に関するものです。
情報源符号化における固定長ブロック符号化
離散無記憶情報源 (Discrete Memoryless Source, DMS) $X$ から出力されるシンボル列 ${X_i}_{i=1}^\infty$ を考えます。各 $X_i$ はアルファベット $\mathcal{X}$ から独立かつ同一の確率分布 $P(x)$ に従って生成されます。
固定長 $N$ の情報源ブロック符号は、以下の要素から構成されます。
- エンコーダ (Encoder): 入力された $N$ 個のシンボル列 $x^N = (x_1, \dots, x_N) \in \mathcal{X}^N$ を、ある有限集合 $\mathcal{M} = {1, 2, \dots, M}$ の要素（メッセージ、インデックスとも呼ばれます）に写像する関数 $e: \mathcal{X}^N \to \mathcal{M}$ です。ここで $M$ は符号語の総数を表します。
- デコーダ (Decoder): 受信したメッセージ $m \in \mathcal{M}$ を、推定された元のシンボル列 $\hat{x}^N \in \mathcal{X}^N$ に写像する関数 $d: \mathcal{M} \to \mathcal{X}^N$ です。
この符号のレート $R$ は、$\frac{1}{N} \log_2 M$ [bits/symbol] で定義されます。これは、平均して1つの情報源シンボルあたりに割り当てられる符号語のビット数を示します。情報源符号化の目的は、情報源のエントロピー $H(X)$ よりも小さいレートで、デコード時の歪み（または誤り確率）を許容可能なレベルに抑えることです。
歪みを評価するために、シンボル単位の歪み関数 $d_s(x, \hat{x})$ が定義される場合があります。ブロックに対する歪みは、例えば $d(x^N, \hat{x}^N) = \frac{1}{N} \sum_{i=1}^N d_s(x_i, \hat{x}_i)$ のように定義されます。情報源符号化定理は、平均確率歪み $E[d(X^N, \hat{X}^N)]$ があるしきい値以下になるような最小のレート（レート歪み関数 $R(D)$）に関する主張を含みます。損失なし符号化（$d_s(x,x)=0, d_s(x,\hat{x})=1$ for $x \neq \hat{x}$ の場合）では、誤り確率 $P(X^N \neq \hat{X}^N)$ が評価指標となり、情報源エントロピー $H(X)$ が達成可能な最小レートとなります。
シャノンの情報源符号化定理（ソース符号化定理）の証明では、ブロック長 $N$ を大きくするにつれて、レートが情報源エントロピー $H(X)$ に近い値でも、誤り確率をいくらでも小さくできることが示されます。これは、大数の法則や漸近等分割性（AEP）といった確率論的な性質が、$N$ が大きいブロックの挙動を支配することを利用しています。例えば、高い確率で出現するブロックは「典型的集合（Typical Set）」に含まれ、そのサイズは約 $2^{NH(X)}$ であることがAEPからわかります。したがって、典型的集合に属するブロックだけを区別できる $M \approx 2^{NH(X)}$ 個の符号語を用意すれば、レートは約 $H(X)$ となり、ほとんどのブロックを正しくデコードできることになります。
通信路符号化における固定長ブロック符号化
離散無記憶通信路 (Discrete Memoryless Channel, DMC) を考えます。入力アルファベット $\mathcal{X}$、出力アルファベット $\mathcal{Y}$、そして通信路遷移確率 $P(y|x)$ で特徴づけられます。通信路を介して $N$ 個の入力シンボル列 $x^N = (x_1, \dots, x_N)$ を送信すると、独立に作用するノイズにより $N$ 個の出力シンボル列 $y^N = (y_1, \dots, y_N)$ が得られます。通信路のモデルは $P(y^N|x^N) = \prod_{i=1}^N P(y_i|x_i)$ で与えられます。
固定長 $N$ の通信路ブロック符号は、以下の要素から構成されます。
- メッセージ集合 (Message Set): 送信したいメッセージの有限集合 $\mathcal{M} = {1, 2, \dots, M}$ です。
- エンコーダ (Encoder): 各メッセージ $m \in \mathcal{M}$ を、通信路入力アルファベットの $N$ 個のシンボル列である符号語 $c_m \in \mathcal{X}^N$ に一意に写像する関数 $e: \mathcal{M} \to \mathcal{X}^N$ です。符号語の集合 $\mathcal{C} = {c_1, \dots, c_M}$ を符号帳 (codebook) と呼びます。
- デコーダ (Decoder): 受信した $N$ 個のシンボル列 $y^N \in \mathcal{Y}^N$ を、推定された元のメッセージ $\hat{m} \in \mathcal{M} \cup {\text{error}}$ に写像する関数 $d: \mathcal{Y}^N \to \mathcal{M} \cup {\text{error}}$ です。
この符号のレート $R$ は、$\frac{1}{N} \log_2 M$ [bits/channel use] で定義されます。通信路符号化の目的は、通信路の容量 $C$ よりも小さいレートで、デコード時の誤り確率をいくらでも小さく抑えることです。
デコード時の誤り確率は、送信されたメッセージ $m$ がデコードによって別のメッセージ $\hat{m} \neq m$ と判断されるか、あるいは誤りとして検出される確率です。ブロック誤り確率 $P_e$ は、メッセージの選び方に対する平均誤り確率、または最悪誤り確率として定義されます。
シャノンの通信路符号化定理（チャネル符号化定理）は、ブロック長 $N$ を大きくするにつれて、レートが通信路容量 $C$ に近い値でも、ブロック誤り確率をいくらでも小さくできることを示します。これは、通信路のノイズが $N$ が大きいブロックの統計的な性質にどう影響するかを分析することで証明されます。ここでもAEPや共同典型的集合（Jointly Typical Set）の概念が重要な役割を果たします。
具体的には、ある符号語 $x^N$ が送信されたときに、高い確率で受信される出力 $y^N$ は、$(x^N, y^N)$ が共同典型的集合に属するものに限られるという性質を利用します。デコーダは、受信した $y^N$ に対して、それがどの符号語 $c_m$ と共同典型的であるかを調べ、共同典型的である符号語が一つだけ存在すればそれをデコード結果とします。もし複数存在するか、あるいは全く共同典型的でない場合は誤りと判断します（典型集合デコーディング）。ランダム符号化の手法を用いることで、ランダムに選ばれた符号帳に対して平均的な誤り確率が、十分大きな $N$ では非常に小さくなることが示され、誤り確率をいくらでも小さくできる符号の存在が証明されます。
漸近解析の意義
シャノンの情報源符号化定理および通信路符号化定理は、いずれもブロック長 $N$ を無限大に近づけたときの性能限界を主張しています。なぜ漸近解析が必要なのでしょうか？
- 理論的な限界の明確化: 有限のブロック長では、誤り確率ゼロを達成しつつ最大のレート（あるいは最小のレートで誤り確率ゼロ）を達成することは一般に不可能です。ノイズのないチャネルにおける自明な場合を除き、レートと誤り確率はトレードオフの関係にあります。ブロック長を無限大にすることで、このトレードオフの極限における基本的な限界、すなわち情報源エントロピーと通信路容量という普遍的な定数を明らかにすることができます。
- 数学的な扱いやすさ: ブロック長 $N$ が大きくなると、シンボルの頻度分布が確率分布に収束するといった大数の法則的な性質が顕著になります。これにより、確率的な現象を情報源エントロピーや相互情報量といった平均的な量で特徴づけることが可能となり、解析が劇的に容易になります。AEPや典型集合といった概念は、この漸近的な挙動を捉えるための強力なツールです。
- システム設計への指針: 漸近的な限界を知ることは、実際の通信システムやデータ圧縮システムを設計する上での究極的な目標値を提供します。実際のシステムでは有限のブロック長で動作しますが、ブロック長を長くすることで理論的な限界に近づけることができるという示唆は、システム設計の重要な指針となります。
ただし、実際の応用ではブロック長を無限大にすることはできません。有限のブロック長における性能（有限長効果）や、符号化・復号の計算量といった問題は、シャノンの基本定理の範囲を超える発展的な研究テーマとなります。シャノンの定理は「達成可能性（Achievability）」と「逆定理（Converse）」から成り立ちますが、達成可能性の証明は多くの場合、存在証明（ランダム符号化など）であり、具体的な構成法の探索は後世の研究者に委ねられました。
歴史的背景と現代における位置づけ
シャノンが固定長ブロック符号化のフレームワークを採用したのは、当時の通信システム（電信や初期のデジタル通信）がメッセージをある程度の長さの塊（ブロック）として扱うことが自然であったこと、そして何よりも数学的な解析、特に確率論的な漸近解析を適用する上で非常に都合が良かったことが挙げられます。これにより、情報源や通信路といった複雑なシステムを、確率分布と遷移確率という比較的単純な数学的モデルで捉え、その情報伝送能力の限界を定量化することが可能になりました。
現代の通信工学やデータ圧縮技術は、シャノンの確立したこの固定長ブロック符号化のフレームワークを基礎としています。例えば、LDPC符号やターボ符号といった高性能な誤り訂正符号は、大規模なブロック符号の構成法であり、シャノンの定理が示す通信路容量に近いレートでの通信を可能にしています。また、JPEGやMPEGといった画像・音声圧縮技術も、データを小さなブロックに分割して処理するという点で、情報源符号化におけるブロック処理の考え方に基づいています。
もちろん、ストリーム符号化（可変長、逐次的な処理）など、シャノンの固定長ブロック符号化とは異なるアプローチや、計算量制約、遅延制約を考慮した理論も発展していますが、シャノンの基本定理は、これらの発展も含む情報理論全体の基盤として、その普遍的な価値を保ち続けています。
結論
クロード・シャノンの情報理論における固定長ブロック符号化は、情報源符号化定理と通信路符号化定理という二つの基本的な定理を定式化し証明するための数学的な基盤を提供します。このフレームワークは、入力・出力シンボル列を固定長ブロックとして扱い、ブロック長を無限大に漸近させることで、情報源のエントロピーや通信路容量といった情報システムの究極的な性能限界を確率論的な手法を用いて明らかにするものです。
固定長ブロック符号化の概念とその漸近解析は、情報科学分野におけるその後の多くの研究の出発点となり、現代の様々な通信・情報処理技術の発展に不可欠な思想的、数学的基盤を提供しています。シャノンの原論文におけるこの概念の厳密な定義と展開を理解することは、情報理論を深く探求する上で避けては通れない重要なステップと言えるでしょう。