シャノンの通信路符号化定理
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2024/01/13 17:16 UTC 版)
概要
1948年にクロード・シャノンによって定式化されたこの定理は、誤り訂正の可能な最大効率と雑音干渉およびデータ破損のレベルを記述している。 シャノンの定理は、通信と情報記録の両方に幅広く応用されている。この定理は、現代的な情報理論の分野にとって根本的に重要なものである。シャノンは証明の概要を記述しただけで、離散した場合の最初の厳密な証明は、1954年のAmiel Feinsteinによるものである[1]。
シャノンの定理によれば、雑音のある通信路の通信路容量を 、情報の送信レートを と与えたとき、 ならば、受信機での誤り率を任意に小さくすることが可能な符号化が存在する。これは、理論的には、限界速度 未満のいかなる速度でも、ほぼ誤差なく情報を伝送することが可能であることを意味する。
逆も重要である。 ならば、任意の小さな誤り率を達成することはできない。全ての符号は、ある正の最小レベルよりも大きい誤り率を有し、このレベルは、レートが増加するにつれて増加する。従って、情報は、通信路容量を超えた速度で通信路を介して確実に伝送されることを保証することはできない。この定理は、速度と容量が等しい稀な状況に対処するものではない。
通信路容量 は、通信路の物理的特性から計算することができる。ガウス雑音を伴う帯域制限された通信路に対しては、シャノン=ハートレーの定理を用いる。
「メッセージが3回送信され、受信されたメッセージが異なる場合に、3つの中で最良の2つを使用する」などの単純なスキームは、非効率的な誤り訂正法であり、データブロックが誤りなしに通信できることを漸近的に保証することはできない。リード・ソロモン符号、低密度パリティ検査符号(LDPC)、ターボ符号などの高度な技術は、理論的な通信路容量に近づくが、計算上の複雑さを犠牲にしている。今日のデジタルシグナルプロセッサでは、これらの高性能な符号化と計算能力を使用することで、通信路容量に非常に近いところまで到達することが可能になっている。 実際、LDPC符号は、非常に長いブロック長を有する2進AWGNチャネルの場合に、通信路容量の0.0045dB以内に到達することができることが示された[2]。
- ^ Feinstein, Amiel (1954). A new basic theorem of information theory. RLE Technical Reports (Report). Research Laboratory of Electronics, Massachusetts Institute of Technology.
- ^ Sae-Young Chung, G. David Forney, Jr., Thomas J. Richardson, and Rüdiger Urbanke, "On the Design of Low-Density Parity-Check Codes within 0.0045 dB of the Shannon Limit", IEEE Communications Letters, 5: 58-60, Feb. 2001. ISSN 1089-7798
- ^ MacKay (2003), p. 162; cf Gallager (1968), ch.5; Cover and Thomas (1991), p. 198; Shannon (1948) thm. 11
- ^ ここで、"sup"関数は上限を表す。
- ^ Robert Gallager. Information Theory and Reliable Communication. New York: John Wiley & Sons, 1968. ISBN 0-471-29048-3
- シャノンの通信路符号化定理のページへのリンク