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

情報の基礎理論

情報理論その１

符号理論（パリティチェック方式）

通信路上で起きるデータの誤りデータを検出または、訂正できるようにするには、元のデータ方ある計算方法で求めた検査用のデータ（ビット）を付加して送信データとし、受信側で送信データから冗長データを切り離して、誤りの有無を検出します。
代表的な符号化方式には、「パリティチェック」や「CRC」などがあります。

「パリティチェック方式」は、1ビットの「冗長ビット」（これを「パリティビット」という）を送信データに付加した符号方式のことです。
「パリティビット」には、送信データに含まれる1の数が偶数になるように付加する「偶数パリティ」と、1の数が奇数になるように付加する「奇数パリティ」があります。
受信側では、受け取ったデータから再び1の数を数え、パリティビットに入るべき値と同じものが「パリティビット」に入っていれば「誤りなし」、異なれば「誤りあり」とみなします。

LRCとVRCを併用したパリティチェックの特徴は、以下のとおりとなります。

1ビットの誤りは、検出・訂正が可。
2ビットの誤りは、検出できるが訂正は不可。

以下は、奇数パリティにおいて、網掛けのビットが誤った状態です。本来は1の数が奇数であるはずなのに、偶数になっているので誤った状態であることがわかります。

2ビットで誤った場合も、以下のように水平パリティ、垂直パリティともに本来奇数であるはずなのに偶数になります。しかし、誤った位置の組み合わせが2通り存在し、どのように訂正したらいいのかわかりません。

なお、パリティチェックのように、チェックのためにビットを追加したコードを「ハミングコード」といいます。

符号理論（CRC方式）

②CRC方式
「CRC（Cyclic Redundancy Check）」は、一定の多項式による除算の余りを検査用のビットとする方法です。1伝送単位ごとにビット列を2進数とみなし、あらかじめ定められた多項式（「ITU-T」では、「X¹⁶ + X¹² + X⁵ + 1」を推奨しています。）で割った余りをチェックビットとして伝送単位の最後に付加して送信します。受信側は伝送された情報を同じ多項式で割り、余りが「0」であれば誤りが発生していないと判断します。

「CRC」では、「ブロック誤り」（一塊の誤り）、「バースト誤り」（連続するビット誤り）、「ランダム誤り」（規則性のない誤り）の検出に有効です。