基本情報技術者試験(FE) ~情報の基礎理論「情報理論」~ 【第1回】

この記事は2013年5月30日に書かれたものです。内容が古い可能性がありますのでご注意ください。


符号理論(ハミング符号方式)

 
「ハミング符号」は、1ビットの誤りが訂正可能な符号方式で、コンピュータ内のメモリアクセスにも使用できます。
「ハミング符号」は、冗長ビットをnビットとした時、送信データ全体のビットは、「2ⁿ-1」となります。つまり、本来のデータは、「2ⁿ-1-n」ビットを送ることになります。
4ビットのデータ(X4X3X2X1)を送信する場合、3ビットの冗長ビット(C3C2C1)を付加する必要があります。ここで、C3~C1を求めるには、以下の式を用います。
 
kihon03-04
 
誤りの検出は、送信先で同様の式を使って計算を行い、式が成立するかどうかでわかります。また、前頁の式の特徴は、送信データに1ビットの誤りを起こすと、その項を持つ式が不成立になることです。
たとえば、X1に誤りが生じれば、式(1)と式(2)の結果が不成立となり、X4に誤りが生じれば、式(1)~式(3)の結果が不成立となります。よって、不成立となった式に共通して持つ項が誤りを起こしているビットであることがわかります。
 
kihon03-05
 

送信元の情報を短く(圧縮)する符号化方式

 
送信データの転送時間は、そのデータの長さに比例します。よって、データ量を減らすことで転送に必要な時間を短くすることができます。
データを短くする(圧縮)する方法に、データの出現頻度を利用する方法があります。この方法を利用する代表的な符号方式として、「ランレングス符号化」、「ハフマン符号化」があります。

①ランレングス符号化
「ランレングス符号化(連長圧縮法)」は、データ列の中で繰り返し現れる文字を「繰り返し回数」と「文字」組み合わせに置き換えて符号化する方法です。
 
kihon03-06
 
②ハフマン符号化
「ハフマン符号化」は、出現頻度の高い文字には短いビット列、低い文字には長いビット列を対応させることで、1文字当たりの平均ビット長を最小にする符号化方式です。
「ハフマン符号化」は、「JPEG」や「ZIP」などの圧縮方式として使用されています。
 

次回は、「オートマトン」から説明していきたいと思います。

 

ページ:
1

2

  • このエントリーをはてなブックマークに追加

PAGE TOP