シャノン符号化のソースを表示

{{混同|シャノン・ファノ符号化|シャノン・ファノ・イライアス符号化}}

'''シャノン符号化'''（シャノンふごうか、{{lang|en|Shannon coding}}）は、[[クロード・シャノン]]によって考案された、[[可逆圧縮]]の方法である。

==概要==
記号の（推定もしくは実際の）出現[[確率]]に基づく[[接頭符号]]を使用している。同じ接頭符号でも、常に最短の符号長を表すことができる[[ハフマン符号]]に比べ、シャノン符号化は最適化されていない。[[シャノン・ファノ符号化]]とは同程度かそれより劣る。

シャノン符号化は接頭符号の最初のもので、1948年のシャノンの記事『[[通信の数学的理論]]』で[[シャノンの情報源符号化定理]]の証明のために用いられた<ref>"A Mathematical Theory of Communication" http://cm.bell-labs.com/cm/ms/what/shannonday/shannon1948.pdf</ref>。

この符号化法は情報理論の分野に進歩をもたらした。そして、シャノン符号化を元にして多くの符号化が生み出された（シャノン・ファノ符号化、ハフマン符号、算術符号など）我々の日々の生活は[[デジタルデータ]]に大きく影響されているが、これは、シャノン符号化やその後継の符号化の恩恵なくしては不可能である。

==符号化の原理==
#記号を出現確率の高い順に並べる。
#それぞれの記号について、その1つ前の記号までの累積の確率を求める。(<math> \sum\limits_{i=k}^{i-1} p_k(x)</math>)
#2.の値を二進数にする。
#3.の値の<math>l_i = \left\lceil -\log_2 p_i(x) \right\rceil </math>桁までをその記号の符号とする（<math>\lceil x \rceil</math> は[[端数処理#切り捨て・切り上げ|切り上げ]]を意味する）。

==例==
以下の表は、a<sub>1-6</sub>の記号の符号化の様子を示したものである。l<sub>i</sub>は-2の累乗を示し、二進数による累積確率の小数点以下のこの桁までを符号とする。第5列は二進数による累積確率を示す。最終列がその記号の符号である。

{| class="wikitable"
!a<sub>i</sub>
!p(a<sub>i</sub>)
!l<sub>i</sub>
!i-1までのp<sub>i</sub>の合計
!p(a<sub>i</sub>)（二進数）
!結果
|-
!a<sub>1</sub>
|0.36
|2
|0.0
|0.0000
|00
|-
!a<sub>2</sub>
|0.18
|3
|0.36
|0.0100
|010
|-
!a<sub>3</sub>
|0.18
|3
|0.54
|0.1000
|100
|-
!a<sub>4</sub>
|0.12
|4
|0.72
|0.1011
|1011
|-
!a<sub>5</sub>
|0.09
|4
|0.84
|0.1101
|1101
|-
!a<sub>6</sub>
|0.07
|4
|0.93
|0.1110
|1110
|}

==出典==
{{Reflist}}

==外部リンク==

{{データ圧縮}}

{{DEFAULTSORT:しやのんふこうか}}
[[Category:データ圧縮]]
[[Category:クロード・シャノン]]
[[Category:エポニム]]