第5回 情報源符号化

初めに必ず連絡事項を確認してください。

情報源符号化

概要

解説動画

19世紀から20世紀初めには、人間が使う「a, b, c,...」を「•(トン)」「― (ツー)」の並びに置き換えて通信する、モールス符号が使われていた。モールス符号で英文を送るには、

表1
文字 モールス符号
a • ―
b ― •••
c ― • ― •
h ••••
i ••
z ― ― ••
. (ピリオド) • ― • ― • ―
のような置き換えを行う (参考:モールス符号 ‐ 通信用語の基礎知識)。さらに文字と文字の間には短い空白、単語と単語の間には長い空白を入れて区切る。その結果、どのような英文も「・」「―」「短い空白」「長い空白」の4種類の文字の並びに置き換えられることになる。便宜上短い空白を「|」、長い空白を「‖」で表わすことにすると、例えば次のようになる。

this is a pen. → ―|••••|••|•••‖••|•••‖• ―‖• ― ― •|•|― •|• ― • ― • ―

これを受信した人は、|と‖で区切ってから表を逆に使って人間用の文字に置き換えれば元の英文が得られる。

一方、現代の情報通信で使えるのは0と1の信号で、モールス符号と違って空白は存在しない。そのため、単純に • のかわりに0, ― のかわりに1を使って同じ置き換えのルールにしてしまうと、モールス符号の「••••」にあたる「0000」を受け取った受信者は「h」か「ii」かを区別できなくなってしまう。そのため、例えば

表2
文字 置き換え先
a 00000
b 00001
c 00010
d 00011
z 11001
単語間スペース 11010
. (ピリオド) 11011
のように、一つの文字に同じ桁数のものを割り当てる。こうすれば、受信者はその桁数ごとに区切って人間用の文字に置き換えれば元の英文を得ることができる。

このような置き換えに関わる情報通信の用語は以下の通り。 表2のような符号はすべての符号語の長さが同じなので等長符号、表1のような符号はシンボルによって符号語の長さが異なるので非等長符号と呼ばれる。
英文では a, e, h, i などのシンボルは頻繁に使われるので、モールス符号では短い符号語 (「・」「―」では「・」の方が時間的に短いことも考慮して) が割り当てられ、q, x などのあまり使われないシンボルには長い符号語が割り当てられている。こうすることで、長い文を送信するのにかかる時間を短縮できている。

0, 1への置き換えでも同様に工夫することができる。
話を簡単にするために、シンボルは a, i, u, e の4つだけで、文には単語間スペースもピリオドもないものとする。
表3
シンボル 符号語
a 00
i 01
u 10
e 11
  表4
シンボル 符号語
a 0
i 10
u 110
e 111
のような2つの符号を考えると、a, i, u, eが均等に使われている12文字の文「aaaiiiuuueee」は
表3の符号では「000000010101101010111111」(24ビット)
表4の符号では「000101010110110110111111111」(27ビット)
に符号化される。つまり、この場合は表3の符号の方が効率が良い。

一方、aがそれ以外よりも多く使われる12文字の文「aaaaaaaaaiue」は
表3の符号では「000000000000000000011011」(24ビット)
表4の符号では「00000000010110111」(17ビット)
に符号化される。つまり、この場合は表4の符号の方が効率が良い。

課題1

自分の姓名をローマ字で書いたものから a, i, u, e だけを抜き出し、それを表3と表4の方法で符号化したもののビット数を求めよ。ただし、導出過程も書くこと (以下の太枠の囲みを参考にする)。
課題1ヒント
wajima shigeru → aiaieu
表3の符号:どのシンボルに対応する符号語も2ビットなので、2×6=12(ビット)
表4の符号:1+2+1+2+3+3=12(ビット)

平均符号長

概要

解説動画

前述のように、英文では文字によって使われる頻度が異なる (参考:英語アルファベット - 文字の出現頻度 - わかりやすく解説 Weblio辞書)。
効率の良い符号を考えるために単語や文の構成を無視して使われる文字だけに注目すれば、「文字を発生させる事象系」が1つずつシンボル (文字) を発生させて文を作っていると考えてもよい。
\( \begin{eqnarray} X&&= \begin{bmatrix} x_a & x_b & \cdots & x_z \\ p_a & p_b & \cdots & p_z \end{bmatrix}\\ &&= \begin{bmatrix} x_a & x_b & \cdots & x_z \\ 0.0817 & 0.0149 & \cdots & 0.0007 \end{bmatrix}\\ \end{eqnarray} \)

このような事象系を情報源事象系という。
非等長符号でシンボル \(a\)~\(z\) に割り当てられる符号語の長さをそれぞれ \(l_a\)~\(l_z\) とすると、一つのシンボルに対して割り当てられる符号語の長さは平均で

\(L=\displaystyle \sum_i p_il_i\) (ビット)

となる。この量を平均符号長という。平均符号長が小さいほど文全体を符号化したもののデータ量が小さくなり、効率の良い符号だということになる。

課題2

シンボルが a, i, u, e だけの場合に情報源事象系が \( X= \begin{bmatrix} x_a & x_i & x_u & x_e \\ 0.25 & 0.25 & 0.25 & 0.25 \end{bmatrix} \) のとき、表4の符号での平均符号長を求めよ。また、表3と表4の符号のどちらが効率が良いか述べよ。

課題2ヒント (この動画中で「表3, 表4」のことを誤って「表2, 表3」としていました。正しくは「表3, 表4」です)

課題3

シンボルが a, i, u, e だけの場合に情報源事象系が \( X= \begin{bmatrix} x_a & x_i & x_u & x_e \cr 0.8 & 0.1 & 0.05 & 0.05 \end{bmatrix} \) のとき、表4の符号での平均符号長を求めよ。また、表3と表4の符号のどちらが効率が良いか述べよ。

課題3ヒント (この動画中で「表3, 表4」のことを誤って「表2, 表3」としていました。正しくは「表3, 表4」です)

符号の木

概要

解説動画

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


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


描き方の規則

同様にすれば表4の符号の木はこのようになる。


表3や表4の符号のように(右端を除く)すべての節点から2本に枝分かれしている符号は完全であるという。

一方、このような符号
表5
シンボル 符号語
a 1
i 01
u 001
e 0001

の木を描くとこのようになる。


こちらは表3や表4と違い、2本に枝分かれせずに節点から右に1本だけの線が出ているところがある。このような符号を不完全であるという。

課題4

以下の符号の符号の木を描け。
シンボル 符号語
a 00
i 01
u 100
e 101
o 11

課題4ヒント
「0」「1」は接点ではなく枝に属するもの。接点の近くではなく、枝の中央近くに書く。
「0」「1」が枝分かれのどちらに属するのかがわかりにくくならないように注意。

提出

ノート・紙に解いた課題を撮影したものを以下のフォームから送信してください。
課題提出用フォーム
※ 締切は10/12(土) 正午です。提出によって出席・点数がつきます。