符号理論

この記事での学習内容 ITパスポート 基本情報 応用情報

アナログとデジタルの特徴、量子化、標本化、A/D変換などの符号化、符号化の目的、情報伝送における信頼性、効率性、安全性の向上などの効果を理解する。

用語例:通信路符号化、ハフマン符号、データ圧縮

符号化理論

符号化とは、データを数値に変換し、情報量として表現することで、コード化ともいいます。

符号化理論とは、情報を符号化し、伝送を行う場合の正確性や高速性に関する理論です。

符号化理論には大きく分けて下記の2つがあります。

  • 情報源符号化
  • 通信路符号化

情報源符号化

元のデータに適した形で符号化を行う方法です。

特性として、圧縮率を高めるほど、データサイズは小さくなりますが、負荷が大きくなります。逆に、圧縮率を低くすれば、データサイズは大きくなりますが、負荷は小さくなります。

通信路符号化

符号化されたデータを伝送する際に、伝送路の帯域や雑音、妨害などによって、正しく届かない可能性もあります。
そこで、既に符号化されたデータに冗長なデータを付け加えて再度符号化します。これを通信路符号化と言います。

例えば、データの信頼性を高めるための誤り検出や誤り訂正機能を付け加えます。

ハフマン符号化

データを圧縮する方法の1つで、出現頻度の高いデータには短いビット列を、頻度の低いデータには長いビット列を割り当てて、全体としてデータの圧縮を行う方法です。

例えば、元データが以下の34バイト(1文字1バイト)からなる文字列だったとします。これをハフマン符号化を用いて圧縮してみます。

元データ:AAJABBDBDBFAAAABAABABAFADAAJLAFBAD

・出現する文字は、A, B, D, F, J, L の6文字なので、この6文字に出現頻度に合わせて各文字にハフマン符号を割り当てます。

各文字の登場頻度ハフマン符号データ長
A:16回01ビット
B:8回102ビット
D:4回1103ビット
F:3回11104ビット
J:2回111105ビット
L:1回1111106ビット

表のように出現頻度の高い文字に少ないビットを割り当てるため、ビット列の容量を減らすことが出来ます。
表のハフマン記号に基づいて元データを変換すると、以下のようなビットの並びになります。(便宜上、元の文字の区切りにスペースを入れていますが、実際には空白はありません)

0 0 11110 0 10 10 110 10 110 10 1110 0 0 0 0 10 0 0 10 0 10 0 1110 0 110 0 0 11110 111110 0 1110 10 0 110 

上記のビットの並びで、72ビットになります。元データの34バイトは272ビットになりますので、おおよそ4分の1のデータ量に圧縮できたことになります。

このように元のデータ量を縮小することを「データ圧縮」と呼びます。
その手法には大きく分けると2種類あり、圧縮後のデータから元データが復元できる「可逆圧縮」と、復元不可能な「不可逆圧縮」があります。