解説動画
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 |
のように、一つの文字に同じ桁数のものを割り当てる。こうすれば、受信者はその桁数ごとに区切って人間用の文字に置き換えれば元の英文を得ることができる。
このような置き換えに関わる情報通信の用語は以下の通り。
- シンボル:置き換えられる前の、人間用の文字 (上の表でいうと「a, b, c,...」)
- 符号アルファベット:置き換え後に使われる最小単位 (モールス符号では「・」「―」「|」「‖」、現代の情報通信では「0」「1」)
- 符号化:文を符号アルファベットの並びに置き換えること (モールス符号でいうと「ab...」から「• ―|― •••...」や「0000000001...」への置き換え)
- 符号語:一つのシンボルに対応する符号アルファベットの並び (aに対する「・ ―」や「00000」)
- 符号:置き換えのルール (表1や表2全体。この用語は別の意味で使われることの方が多いが、今回からしばらくはこちらの意味で用いる)
表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の符号の方が効率が良い。
自分の姓名をローマ字で書いたものから a, i, u, e だけを抜き出し、それを表3と表4の方法で符号化したもののビット数を求めよ。ただし、導出過程も書くこと (以下の太枠の囲みを参考にする)。
課題1ヒント
- 実際に符号化する必要はない。それぞれの符号で a, i, u, e に対応する符号語が何ビットであるかがわかっていれば十分。
例
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\) (ビット)
となる。この量を
平均符号長という。平均符号長が小さいほど文全体を符号化したもののデータ量が小さくなり、効率の良い符号だということになる。
シンボルが 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の符号では \(l_a=l_i=l_u=l_e=2\) なので、情報源事象系がどうであっても \(L=\displaystyle \sum_k p_k l_k =
2 \displaystyle \sum_k p_k =2\) (ビット)になる。
シンボルが 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」となる。
描き方の規則
- 左端から描き始める
- 節点から右に1本または2本の枝を出す
- それらの枝に沿って「0」「1」を書く
- 必要な分だけ分岐させる
- シンボルに対応する節点の隣にシンボルの文字を書く
同様にすれば表4の符号の木はこのようになる。
表3や表4の符号のように(右端を除く)すべての節点から2本に枝分かれしている符号は
完全であるという。
一方、このような符号
表5
シンボル |
符号語 |
a |
1 |
i |
01 |
u |
001 |
e |
0001 |
の木を描くとこのようになる。
こちらは表3や表4と違い、2本に枝分かれせずに節点から右に1本だけの線が出ているところがある。このような符号を
不完全であるという。
以下の符号の符号の木を描け。
シンボル |
符号語 |
a |
00 |
i |
01 |
u |
100 |
e |
101 |
o |
11 |
課題4ヒント
「0」「1」は接点ではなく枝に属するもの。接点の近くではなく、枝の中央近くに書く。
「0」「1」が枝分かれのどちらに属するのかがわかりにくくならないように注意。
ノート・紙に解いた課題を撮影したものを以下のフォームから送信してください。
課題提出用フォーム
※ 締切は10/12(土) 正午です。提出によって出席・点数がつきます。