シャノン＝ハートレーの定理
クロード・シャノンの情報理論は第二次世界大戦中に構築され、ノイズのある通信路上で確実に通信できる情報量を把握するための大きな進歩となった。ハートレーの成果を発展させ、シャノンが1948年に発表した通信路符号化定理は、ノイズの影響下での誤り訂正方法の効率の最大値を示した。この定理の証明によって、無作為に構築された誤り訂正符号が本質的に最高の符号でもあることを示した。証明はそのような無作為な符号の統計的操作によって行われた。
シャノンの定理は通信路の統計的記述から通信路容量を計算する方法を示している。ノイズのある通信路での容量 C と転送レート R の関係が
R < C {\displaystyle R<C\,}
であるとき、受信側での誤り率を極めて小さくする符号化技法が存在する。つまり、理論上は C (ビット毎秒)を上限として誤り率をほぼゼロで情報を転送できることを示している。
反対も重要である。もし
R > C {\displaystyle R>C\,}
である場合、転送レートの上昇とともに受信側での誤り率も増大していく。従って、通信路容量を超えて意味のある情報を転送することはできない。この定理では転送レートと通信路容量が同じという稀な状況については特に何も示していない。
1920年代後半ごろ、ハリー・ナイキストとラルフ・ハートレーは様々な情報転送に関する基本概念を生み出した。特に通信システムとして電報を対象としていた。当時、それらの概念は強力なブレークスルーではあったが、理論として体系化されるまでには至らなかった。1940年代、クロード・シャノンはナイキストやハートレーの業績に基づいて通信路容量の概念を生み出し、情報理論として体系化した。