シャノン (Shannon )の通信路符号化定理はディジタル通信の基礎であり、すべての人がこの恩恵にあずかっているといっても過言ではありません。　ただ、この定理をシャノンの論文にしたがって一般的に証明すると、話が抽象的になってしまいます。　そのため、シンボルが２値（１と０）の伝送を例にとって、直感的な具体例で話を進めてみます。

通信路の符号化は、簡単にいえば次のような内容です。

通信路符号化定理

通信路容量（単位はビット／シンボル）よりも
小さな通信能力（単位はビット／シンボル）で
情報を送信することによって、
限りなく誤りの少ない通信ができる。

A Mathematical Theory of Communication 1948

この定理でいう「通信路容量」とは、平たくいえば、チャンネルが発揮できる最大の通信能力を指します。　チャンネルは、ある種の送信信号を通しやすいとか、ある種の送信信号を通しにくいといった性質をもちますが、もっとも通しやすい信号を送っている状態でのチャンネルの情報通信能力を意味します（雑音が白色ガウスのときの通信路容量、更に、雑音が有色ガウスのときの注水定理を参照）。　
上の定理でいう通信能力は物理的な時間が含まれていませんが、これにシンボル／秒を掛ければ、単位はビット／秒になります。ビット／秒 で解説したいように、「このモデムは６４ｋ（ビット／秒）である」 という言い方は、本当は正しくありません。　これをいうなら、６４ｋ（パルス／秒）というべきです。　すなわち、１秒間に１と０の２値シンボル（あるいは正と負のパルス）を６万４千個送る物理的スピードを意味しています。　このシンボルのスピードで実質的にどれだけの情報を送れるかが、ここでいう速度に相当し、これこそ（ビット／秒）で表すべきであり、以下で用いる速度はすべてこの意味です。

＊誤り率を無限に小さくする
受信者が２値送信シンボルを判定するとき、チャンネルで加わった雑音やパルスの波形歪は判定誤りを引き起こします。　この判定誤りの確率を とします。　誤り率を改善する方法として、まず思いつくことはシンボルを反復して送ることです。　たとえば、

１１１１１

のように５回続けて１を送るとしましょう。　そして、これを受けた受信者は多数決で判定すると考えます。　もし、０が３個または４個または５個ならば、０に誤判定されてしまいます。　この誤り率は

となります。　ここで  はｎ 個の異なるものから ｒ 個をとる組み合わせを表し、

で計算されます。　したがって、反復数 ｎ を増やせば、下図のように誤り率を無限に小さくできます。　縦軸は誤り率の常用対数です。

しかし、この方法で誤り率をゼロにしようとすると、通信速度を無限に小さくしなければなりません。　これに対して、シャノンは　

誤り率を無限に小さくするには、
通信速度を一定の比率まで落せば済む。

ということを主張しました。　以下にその理由を説明します。

注１：シャノン理論は定常ガウス雑音（雑音発生の確率的メカニズムは時間的に不変）を前提にしています。雑音が周期定常（ cyclostationary ）のときは、繰り返し伝送方式とシャノン方式の優劣は逆転することがあります。ロバスト伝送を参照してください。

まず、ハミング距離を定義します。　下の二つのフレームをみてください。

A：　　０００１１１０１０１００１１１０１０

B：　　０１０１１１０００１００１１００１０

フレームＡ を送って、フレームＢ を受けたと考えてください。　赤色で示した３個所でシンボルが誤っています。　このとき、フレーム Ａ とフレーム Ｂ のハミング距離は３ であるといいます。　では、フレーム長をだんだん大きくしながら、ハミング距離の誤り率がどのように分布するかを調べてみましょう。　一つのシンボルを送信したときの誤り率を 0.1 とします。

このとき、フレームを長くすると、
ハミング距離はどんな分布をするでしょうか？

下図は、誤りのハミング距離の確率密度を示しています。　上からフレーム長が 2000,  4000,  8000 の場合を示しています。　横軸の目盛りが縮尺されていることに注意してください。

この縮尺でみると、フレーム長が長くなるにしたがって、確率密度が 0.1×フレーム長 のところにどんどん集中して行くことがわかります。　言い換えると、フレーム長 をどんどん長くすると、誤りのハミング距離の密度が  の近傍にどんどん集中することがいえます。　したがって、小さな正数 を選び、

誤りのハミング距離の密度 ＞

を考えてみると、 で、この確率がゼロになるという予想がたちます。　実際に数値計算して当たってみましょう。　シンボル誤り率 p を 0.1 とし、 と の場合について、誤りのハミング距離が上の不等式を満たす確率を計算してみると下図のようになり、指数関数的に減少することがわかります。　横軸はフレーム長、縦軸は上の不等式を満たす確率の常用対数です。

＊送信フレームの個数
以上から、次のような誤りのない通信方法を想定することができます。

1. どの二つをとってみてもハミング距離が  だけ隔たるような送信フレームの集合を選択し、これらを用いて情報を送る。
2. 受信側では、ハミング距離が一番近い送信フレームに判定する。
3. 以上のことを、フレーム長を十分長くして実現する。

この想定が正しければ、速度を一定比率落とすだけで、誤りのない通信ができます。　その代わり、フレームを全部受信しないと送信信号を判定できないので、無限に長いフレームは理論としての概念です。この辺のことは、現実から離れて考えてください。

さて、まだ大きな疑問が残っています。　その疑問は次のようです。

上で選択された送信フレームの個数（これを Ｍ とする）は
十分多くとれるでしょうか？
M はフレーム長 ｎ とどんな関係にあるでしょうか？

すなわち、限定されたＭ個のフレームを用いて、

   ビット／フレーム

の速度で情報を送ることができますが、もしＭがフレームを長くしてもあまり大きくならないようなら、反復送信と大差ないということになります。　上の疑問は、フレーム長をどんなに長くしても、

が一定値以下にならないという答えを期待しています。　実は、このことを２値伝送以外の一般的なケースで証明するのは大変抽象的でやっかいなので、できるだけ直感的な解釈を試みましょう。　まず、Ｍの大きさに見当をつけましょう。　可能なフレームの個数は全部で  個です。　この中から、どのフレーム同士も （ としましたが、これはあまり本質的ではありません）だけ離れているようなフレームの集合を求めるわけですが、この中の一つに着目します。　これを中心に半径 （ハミング距離！）の球の中に含まれるフレームの個数は、自分自身も含めて次のように計算できます。

したがって、この  でフレームの総数を割ったものは送信フレームの個数の上限を与えています。

上式右辺に注目し、これを具体的に計算してみます。　下図は、フレーム長  が３２ビット、６４ビット、１２８ビット、２５６ビットの場合について、ハミング距離が互いに  離れたフレーム数の上限評価  ビットを  で割った値を表しています。　この意味は、誤りを訂正するために情報伝送速度を落とさなければならないレートです。　横軸は誤り率 です。　直線は  を  で割った値です。オレンジ色はを十分に大きくしたときの極限を表しています。オレンジ以外の階段状のカーブでは、誤り訂正の見逃し率は小さいが、完全にゼロではありません。

緑色＝32bit、空色＝64bit、青色＝128bit、赤色＝256bit
オレンジ色（極限）＝

上図の連続的なオレンジ色のカーブが通信路容量であることが通信路符号化定理のポイントですが、オレンジ色の限界を上回る速度ではどんなにフレームを長くしても誤り訂正の見逃しは小さくなるが急速にゼロに収束できません。逆に、この限界以下の速度での安全運転では、フレーム長をそこそこ長くすれば、誤り訂正の見逃し率を急速にゼロにできることを暗示しています。実用的な設計では、この限界以下の速度で、フレーム長のトレードオフを設計することになります。

以下、誤り率が小さい範囲での補足的な検討です。　誤り訂正の対象となるチャンネルのシンボル誤り率を 0.01 ぐらいとすると、この周辺では（上図の左端では） と は非常に接近しています。そこで、今度は  に固定して、フレーム長を変えて上と同様の数値評価をしてみます。　下図の横軸はフレーム長を表し、１００００までの と をプロットしています。

この図の縦軸をフレーム長 で割って規格化し、二つのカーブ

を描くと下図のようになります。　上の直線が  で、下の曲線が です。

２本の線は  で平行になる傾向を示しています。　この差が本当に一定かどうか、気になるところです。　そこで、 が比較的小さい現実の場合について、

として一体どうなるのか、ちゃんと確認しておく必要があります。　ちょっと退屈かもしれませんが、しばらくは近似論を追跡しましょう。　まず、 が十分大きくて、 が小さければ、組み合わせの個数は

さらに、分母にスターリングの公式を用いると、

となります。　半径  の中に含まれるフレーム数は

ですが、

のような不等式を満たします。　ここで各辺の対数をとります。　右辺の対数は

ですが、 が大きいとき、第１項と第２項は第３項に比べて無視できるから、左辺の対数に近似します。　したがって、

となります。　２値無記憶情報源のエントロピーを測る関数

は、 が小さいとき、

ですが、これを上に代入して、

が導かれました。　この近似を用いて、送信可能な最大情報量が

によって与えられることがいえました。　また、 と  の大小関係は、

なので、

がいえます。

以上では、もっぱら半径  のセルがいくつとれるかという計算をしてきました。

セルの数は実際に設計できるフレーム符号の個数の上限を与えていますが、
この差はどれくらいでしょうか？
この問題は、まさに誤り訂正符号の具体的な設計問題になってきます。

＊通信路容量との関係
いままで求めた結果は、誤り率と一つのフレームが送れる最大情報量の関係を表しています。

では、通信路符号化定理にいう通信路容量との関係はどうなっているでしょうか？

 これについては 相互情報量 をもう一度復習する必要があります。

と  はそれぞれ送信信号のエントロピーと受信信号のエントロピーです。　右辺第２項の や はちょっと分かりにくいですが、以下に説明する特異なケースを考察してみるとなんとなく理解できます。　下図は、左の４通りのシンボルを送り、それを右のように判定するモデルの一例です。　枝にはゼロでない確率が割りつけらっれており、確率ゼロの枝は描いていません。

このようなグラフの中で、次の二つは大変特徴的です。　枝のないところは確率がゼロです。

左のグラフは、送信シンボルのグループが同一のシンボルに判定され、それらのグループは互いに交わっていません。　逆に、右のグラフは、送信シンボルが誤る先のグループが互いに交わっていません。　まず、左の場合について  はどうなるでしょうか？　 は送信側から受信側へのシンボルの広がりの度合いを表しています。　各シンボルが誤る先のシンボルは一つに固定されているので、各枝の条件付き確率は１です。　描かれた枝を拾って、 の計算に必要な項を書くと次のようですが、

ここで、４つの対数関数の変数はすべて１ なので、

が言えます。　したがって、

が結論できます。　次に、右のグラフの場合では、誤らないにしろ、誤るにしろ、判定結果はいつも唯一の送信シンボルを確率 １ で指しています。　このことは、すべての事後確率が １ であることを意味していますから、

すなわち、

が結論されます。　この結果をそのまま翻訳すれば、”チャンネルの相互情報量が送信信号の平均情報量に等しい” ですが、分かりやすくいえば、”チャンネルは送信情報を損失無く伝送している” といえます。
このページの主題である「誤りのない通信」は後者のケース（右のグラフ）を作り出して、誤りのない通信を実現しようとしたわけです。　そして、

となっていることがいえました。

このとき、通信路容量（送信情報源をいろいろ選んで、相互情報量を最大化した状態）は、

となります。　すなわち、誤りのない状態では、情報源の最大エントロピーがそのまま通信路容量になります。　さらに、いままで仮定してきた対称チャンネルの場合は、相互情報量でみたように、 は送信情報源に依存せず、

のようにチャンネルの誤り確率 の関数だけで表せますので、以下が結論されます。

十分長い長さ の２値シンボルからなるフレームを用いて通信したい。
誤り率ゼロならば、となり、最大  ビットの情報を運ぶことができる。
シンボル誤り率が  である対称チャンネルを仮定すると、
誤りのない通信をするためには、
フレーム当たり ビットだけ減速しなければならない。
このとき、
であり、これが最大の送信情報量である。

注２：　上の通信路容量は２値符号の誤りモデルから引き出されたものである。　広く用いられる通信路容量として、アナログ値伝送と加法的ガウス雑音を仮定して求めた通信路容量

がある。　この公式がディジタル通信にどの程度あてはまるか確認する必要がある。　実際の多値ディジタル通信の場合、２値ビット列の平均ビット誤り率 を求め、 のような関数によって通信路容量（ビット／秒）を求めることになるが、いろいろな伝送技術が関係し、数値評価はかなり複雑になる。アナログ通信容量とディジタル通信の最高速度を参照。