2 デジタル符号化

一般に，情報を記号によって表現することを符号化(コード化)と言う．表現されたものを 符号(コード)と呼ぶ．情報を表す記号は，何を使っても良いが，整数を使うのが最も簡単 であるし，コンピューターとの相性も良い．特に，コンピューターでは2進数がもっとも 扱いやすい．

2.1 デジタル符号化の事例

2.1.1 2進数符号

10進数2進数で表す話である．しかし，講義ではこのこの辺の話は，省略する．10進数と2 進数，16進数の間の変換については，諸君はしつこく学習したであろう．私も，3年生の 電子計算機の第2回の講義「位取り基数法(2進数，10進数，16進数)」で，説明した．よも や，これらの変換が分からない者など，いないはず．

ただし，ハミング距離(Hamming distance)²については，述べておくべきであろう．

二つのデータで，同じ位置にあるビットで異なるビットの個数をハミング距離と呼ぶ．た とえば，(01000110)と(01000001)のハミング距離は3である．

• 8ビット整数(0-255)のうち，隣り合う整数の組でハミング距離が最大の組を示せ．

2.1.2 グレイ符号

グレイ符号は，値が一つ異なる整数のハミング距離がいつでも1の符号である．教科書  [1]のpp.28の表2.2を見れば，このことが分かるだろう．詳細につ いては，応用上，重要な話もあるが，今後の講義にあまり関係なので，説明しない．

グレイ符号については，私の講義ノート「グレイコード　誤り の検出」に書いてあるので見ると良いだろう．また，参考文献 [2]も詳しい．

2.2 デジタル符号の圧縮

$p$の確率(probability)で生じる事実が発生した時，それを観測することにより得られる 情報量は$-\log_2 P$[bit]である．たとえば，X先生はテストの出題には癖があり，練習問 題AとBが出題される確率は表1のとおりである．両方の問題が 出題された場合，それにより得られる情報量は1[bit]である．

• 問題Bのみ出題されたとき，得られる情報量は何[bit]か?

表を見て分かるとおり，これらの事実は4通りある．そのため，2桁の2進数で符号化可能で ある．しかし，得られる情報量は2ビットとは限らない．

表 1: テストに練習問題AとBが出題されるときの符号化と確率

問題AとBの出題	どちらも出題されない	問題Bのみ	問題Aのみ	両方出題
符号化	00	01	10	11
確率	1/8	1/8	1/4	1/2

すなわちデジタル符号(データ)の圧縮は，情報量[bit]と2進数の桁数が異なることを利用 する．すなわち，情報を2 進数で符号化すると，その桁数と情報量は一般には異なる．先 に示したように，符号化された2進数の0と1の出現確率が異なるためである．もし，0と1 の出現確率が同じ$1/2$ならば，桁数と情報量は同じになり，デジタル符号の圧縮はでき ない．

実際の圧縮の例として，教科書 [1]のpp.30-31ではハフマン符号化とラングレ ス圧縮の例が記述されている．

• ハフマン符号化は，出現確率の大きな記号に短いビット列を，小さいに記号に長いビット列を当て る方法である．すべての記号に同じ長さのビット列を与えるよりも，短いビット列で符 号化できる確率が高い．
• ラングレス圧縮は，ビットの値とその繰り返しで符号化する．

人間の感覚では気がつかない部分の情報を減らすことにより，デジタル符号を圧縮するこ とも可能である．たとえば，画像データフォーマットで使われるJPEGなどがその例である． 教科書 [1]のpp.27の図 2.10のように，周波数の高い成分の情報を削除しても人 間は気がつかない．人間が気がつかない周波数の高い成分を圧縮しても，人間への伝達は 問題がない．

符号の圧縮には，可逆圧縮と非可逆圧縮がある．圧縮されたデジタル符号が元の状態に戻 せるものを可逆圧縮，戻せないものを非可逆圧縮と呼ぶ．ハフマン符号化とラングレス圧 縮は可逆圧縮で，JPEG圧縮は非可逆圧縮である．

コーヒーブレイク TEX関係で有名な奥村晴彦先生が，圧縮のジレンマとして，おもしろいことを書い ている [3]ので引用しておく．

定理 最悪の場合でも圧縮データが元データより大きくならない圧縮ソフトは，どん なデータも圧縮できない．

証明 元データのサイズが0ビットなら，圧縮して大きくなることはないのだから， 圧縮データのサイズも0ビットでなくてはならい．元データのサイズが1ビットなら，も う0ビットは使用済みなので，圧縮データは1ビットでなくてはならない．1ビットの元デー タ(2通り)が，1:1に対応する．以下同様に続けていけば，元データのサイズが$n$ビットな ら，圧縮してもnビットでなければ成らないことがわかる．

要するに，元データと圧縮データは1:1に対応するため，全く圧縮できないことになる． また，もしこの定理が成り立たなければ，この圧縮ソフトを繰り返し使うことにより，ど んなデータも0ビットに圧縮できてしまう．これは，矛盾である．

ホームページ: Yamamoto's laboratory
著者: 山本昌志