シャノンの通信路符号化定理
2 n R {\displaystyle 2^{nR}} 個の符号語からなる符号について考える。Wは、この集合から一様的に選んだ符号語の番号であるとする。 X n {\displaystyle X^{n}} および Y n {\displaystyle Y^{n}} は、それぞれ送出した符号語と受信した符号語であるとする。
n R = H ( W ) = H ( W | Y n ) + I ( W ; Y n ) {\displaystyle nR=H(W)=H(W|Y^{n})+I(W;Y^{n})} (エントロピーと相互情報量に関する恒等式を用いて)
≤ H ( W | Y n ) + I ( X n ( W ) ; Y n ) {\displaystyle \leq H(W|Y^{n})+I(X^{n}(W);Y^{n})} (XはWの関数であるため)
1948年にクロード・シャノンによって定式化されたこの定理は、誤り訂正の可能な最大効率と雑音干渉およびデータ破損のレベルを記述している。 シャノンの定理は、通信と情報記録の両方に幅広く応用されている。この定理は、現代的な情報理論の分野にとって根本的に重要なものである。シャノンは証明の概要を記述しただけで、離散した場合の最初の厳密な証明は、1954年のAmiel Feinsteinによるものである。
シャノンの定理によれば、雑音のある通信路の通信路容量を C 、情報の送信レートを R と与えたとき、 R < C {\displaystyle R<C} ならば、受信機での誤り率を任意に小さくすることが可能な符号化が存在する。これは、理論的には、限界速度 C 未満のいかなる速度でも、ほぼ誤差なく情報を伝送することが可能であることを意味する。
逆も重要である。 R > C {\displaystyle R>C} ならば、任意の小さな誤り率を達成することはできない。全ての符号は、ある正の最小レベルよりも大きい誤り率を有し、このレベルは、レートが増加するにつれて増加する。