誤り訂正符号とデータ圧縮

誤り訂正符号は、データに検査用の冗長ビットを付加して、受信側で誤りを検出し訂正できるようにした符号である。データ圧縮は、同じ情報をより少ないビット数で表現する符号化であり、目的は誤り訂正とは異なる。両者はいずれも、ビット列をどのような規則で表すかという符号理論に基づいており、試験では計算問題としてまとめて出題されやすい。

原理・仕組み

誤り訂正の基本は、送信側で情報ビットから検査ビットを計算して付加し、受信側で同じ計算を行って照合する点にある。受信語に誤りがなければ検査結果はすべて0になり、誤りがあれば検査結果の組合せが誤りの位置を指し示す。ハミング符号はこの考え方を代表する方式であり、符号長7ビット、情報ビット4ビットの構成では、3つの検査式の結果を並べて2進数と見なし、その値から誤りのあるビット位置を直接求める。

検査式がどの情報ビットを含むかによって、検査結果のパターンと誤り位置の対応が決まる。ある1ビットが3つの検査式すべてに含まれていれば、そのビットが誤ったとき3つの検査結果がすべて不一致になる。このように、不一致のパターンを検査式の構成と照らし合わせることで、誤り位置を一意に特定できる。

16ビットのデータを4×4の正方形状に並べ、各行と各列にパリティビットを付加する方式も代表的である。この方式では、1ビットの誤りがあればパリティが不一致となった行と列の交点として誤り位置を特定でき、そのビットを反転して訂正できる。

判断の基準や数値

誤り訂正能力は、付加する検査ビットの数と構成で決まる。単純なハミング符号は1ビットの誤りを訂正できるが、2ビット以上の誤りには対応できない。2ビットの誤りを検出することも求められる場合は、全体の偶奇を検査する1ビットを追加した拡張ハミング符号を用いる。この構成により、1ビットの誤りは訂正し、2ビットの誤りは検出するという機能を両立させる。

行と列の検査結果だけでは、2ビット以上の誤りの位置を一意に決められない場合が多い。したがって、この方式で訂正できる誤りは1ビットに限られると判断する。

データ圧縮では、圧縮率を圧縮後のデータ量を圧縮前のデータ量で割った値として扱う。圧縮データの転送時間は、転送するデータ量を転送速度で割ることで求められ、展開にかかる時間は展開対象となるデータ量に比例する。転送と展開が同時に行われない条件があれば、両方の時間を加算して全体の時間を求める。