情報理論 第11回　情報源符号化

• 情報源符号化
情報を送るためには、人間が使う「a, b, c,...」や「あ, い, う,...」のような種類の多い文字のままでは不便である。そのため、例えばモールス信号では「・(トン)」「― (ツー)」を使って

文字	モールス信号
a	・ ―
b	― ・ ・ ・
c	― ・
…	…

のような置き換えを行い、「・」と「―」の2種類 (正確には文字間の空白、単語間の空白を入れた4種類) の信号の組み合わせだけで情報を送る。

現代の情報通信でも、文章、音声、画像などの情報もすべて「0」「1」の組み合わせに置き換えることで通信路を通れるようにする。
このとき使われる用語は以下の通り。
• シンボル：置き換えられる前の、人間が使うための記号 (上の表でいうと「a, b, c,...」)
• 符号アルファベット：置き換え後に使われる最小単位 (モールス信号でいうと「・」「―」、現代の情報通信では「0」「1」)
• 符号化：シンボルの並びを符号アルファベットの並びに置き換えること (モールス信号でいうと「aba」から「・ ― □ ― ・ ・ ・ □ ・ ―」への置き換え)
• 符号語：一つのシンボルに対応する符号アルファベットの並び (上の表でいうと「・ ―」など)
• 符号：置き換えのルール (モールス信号でいうと上の表全体)
特に、ここでいう「符号」は今まで説明なしで使っていた「0, 1が複数並んだもの」とは意味が違うので注意。

符号が実用的であるためには、符号語の並びをシンボルに戻すときに必ずもとに戻せるようになっている必要がある。例えば以下の表のような符号では、

シンボル	符号語
a	0
b	1
c	01
d	10

「abba」を符号化すると「0110」になるが、あて先側では
0110 → 0 1 1 0 → abba
0110 → 01 1 0 → cba
0110 → 0 1 10 → abd
のように、いろいろに解釈できてしまう。このような符号は役に立たない。


例1
シンボル	符号語
a	00
b	01
c	10
d	11
のように、すべてのシンボルに対して同じ長さの符号語が割り当たるようにした符号のことを等長符号という。
等長符号では、あて先側では決められた長さごとに区切って符号語をシンボルに置き換えればよいので、確実にもとのシンボルの並びを再現できる。
(情報源側) abcd → 00011011
(あて先側) 00011011 → 00 01 10 11 → abcd
例2
シンボル	符号語
a	1
b	01
c	001
d	0001
のような符号では、あて先側で「1を受け取ったらそこで区切る」というルールに従ってシンボルに置き換えれば、確実にもとのシンボルの並びを再現できる。
(情報源側) abcd → 1010010001
(あて先側) 1010010001 → 1 01 001 0001 → abcd
このように、シンボルによって符号語の長さが異なる符号のことを非等長符号という (これはあくまで一例で、非等長符号は他にもいろいろ存在する)。
この非等長符号は一見非効率なように見えるが、abcdの4つのシンボルからなる「文」で
aaaaaaaabaaaaacaaaaaaaaaaaadaaa...
のようにaの出現頻度が極端に高い場合は、ほとんどのシンボルが「1」の1ビットで済むので、符号化された全体のデータ量は例1の場合 (aが2ビットになる) よりも少なくて済む。逆に

ddddddaddddddcccccddddddbdddddd...
のようにdの出現頻度が高いとデータ量は非常に多くなってしまう。

(モールス信号でも、英文で出現頻度の高い e, h などの文字には短い信号、頻度の低い j, q などの文字に長い信号を割り当てることで平均符号長を小さくし、技師が高速で信号を送れるように工夫されていた)

上で見たように、非等長符号の効率はシンボルの出現頻度によって変わる。その出現頻度は情報源事象系に記述されているので、それを使えば符号の効率を調べられる。
情報源事象系、つまり「シンボルaが出現する」～「シンボルdが出現する」という事象$x_a$ ～ $x_d$ からなる事象系

$X=\left[\begin{array}{cccc}{x}_a& x_b& x_c& x_d\\ p_a& p_b& p_c& p_d\end{array}\right]$

($p_a$ ～ $p_d$ はa～dが出現する確率) から、符号語の平均の長さは
　「aに対応する符号語の長さ」×$p_a$
＋「bに対応する符号語の長さ」×$p_b$
＋「cに対応する符号語の長さ」×$p_c$
＋「dに対応する符号語の長さ」×$p_d$

で求められる。これを平均符号長といい、文字 $L$ で表す。この値は「平均してシンボル1個の情報を送るのに何ビット必要か」を表わし、小さいほど符号の効率は良いことになる。


• 練習問題1
例2の符号で、情報源事象系が $X=\left[\begin{array}{cccc}{x}_a& x_b& x_c& x_d\\ 0.25& 0.25& 0.25& 0.25\end{array}\right]$ である場合の平均符号長を求めよ。また、この場合に例1と例2のどちらが効率が良いか述べよ。

※ 例1ではすべての符号語の長さが2なので、情報源事象系がどうであっても平均符号長は2になる。


• 練習問題2
例2の符号で、情報源事象系が $X=\left[\begin{array}{cccc}{x}_a& x_b& x_c& x_d\\ 0.8& 0.1& 0.05& 0.05\end{array}\right]$ である場合の平均符号長を求めよ。また、この場合に例1と例2のどちらが効率が良いか述べよ。


• 練習問題3
a～hの8文字を扱えるように例1, 例2を拡張した符号を考え、情報源事象系が $X=\left[\begin{array}{cccccccc}{x}_a& x_b& x_c& x_d& x_e& x_f& x_g& x_h\\ 1-7p& p& p& p& p& p& p& p\end{array}\right]$ である場合の例1(拡張)、例2(拡張)の平均符号長を求めよ。また、例2(拡張)の方が例1(拡張)よりも効率が良くなる条件を記述せよ。

※ 拡張版の符号を表の形で書き下す必要はない。
※ 2桁の2進数では8通りのシンボルは扱えない。例1(拡張)の平均符号長は例1のものとは異なる。

• 符号の木
表で書くかわりに、符号を図の形で表したものを符号の木という。
例1の符号の木は


のようになる。シンボルに対応する符号語は、黒丸 (節点という) を結ぶ線 (枝という) に沿って書かれた符号アルファベットを左から順に読めば得られる。
例えば b なら図のように見て「01」となる。


描き方の規則
• 左端から描き始める
• 節点から右に1本または2本の枝を出す
• それらの枝に沿って「0」「1」を書く
• 必要な分だけ分岐させる
• シンボルに対応する節点に沿ってシンボルの文字を書く

このルールに従って例2の符号の木を描くとこのようになる。


こちらは例1と違い、2本に枝分かれせずに節点から右に1本だけの線が出ているところがある。このような符号を不完全であるという。逆に、例1のように(右端を除く)すべての節点から2本に枝分かれしている符号は完全であるという。



• 練習問題4
以下の符号の符号の木を描け。

シンボル	符号語
a	1
b	10
c	100
d	1000



※ この符号では、あて先側では一つの符号語の一番後ろのビットを受け取ったときに「そこで本当に区切ってよいか」判断できない。
abcd → 1101001000を送った場合、受け取ったものを表に対応させて順に判定していくと
受けったもの	変換したもの	判定
1		今受け取ったのが何かはまだわからない(a～dのどれか)
1 1	a	最初のはaだった、今受け取ったのが何かはまだわからない(a～dのどれか)
1 10	a	最初のはaだった、今受け取ったのが何かはまだわからない(b～dのどれか)
1 10 1	ab	最初のはa、次はbだった、今受け取ったのが何かはまだわからない(a～dのどれか)
・・・	・・・	・・・
のように、符号語の分を受け取ってももう一つ後のものを受け取るまではシンボルに置き換えられない。このような符号を非瞬時符号といい、非常に不便なので実際に使われることはない。これに対して、例1, 例2のように符号語1つ分の最後の桁を受け取った瞬間にシンボルに置き換えられるものを瞬時符号という。
非瞬時符号では、符号の木の右端の節点だけでなく途中の節点にもシンボルが割り当たる。