
パリティ・CRC・ハミング符号――誤りに気付き、元へ戻す
通信や保存でビットが変わったとき、正しいデータと区別する手掛かりが必要です。余分なビットの規則が、その手掛かりになります。
パリティとチェックサム
正確な意味: パリティ検査は、データと検査ビットに含まれる1の個数を偶数または奇数にそろえて誤りを検出する方法です。チェックサムはデータの和などから求めた検査値で整合性を確かめる方法の総称です。
ざっくり言うと: 決めた数え方の結果を添え、受信側でも計算し直します。
用途・問題での見方: 偶数パリティでデータ1011なら1が3個なので、検査ビット1を足して計4個にします。単純な1ビットのパリティでは奇数個のビット反転を検出できますが、偶数個の反転を見逃します。誤り位置は決まらず、訂正はできません。チェックサムも異なるデータが同じ値になる場合があります。偶発的な誤り検査と、悪意ある改ざんへの耐性を混同しないようにします。
CRC
正確な意味: CRCはビット列を係数0・1の多項式とみなし、生成多項式で割った剰余などを検査値として付ける方式です。加減算はXORに対応します。
ざっくり言うと: 決めた割算の余りを使う誤り検査です。
用途・問題での見方: フレームや保存データの誤り検出などに使います。通常の整数の割算と違って桁の借りや繰り上がりは使いません。生成多項式の次数がrなら検査ビットは通常rビットです。検出できる誤りの種類は多項式などの条件に依存し、CRCが一致してもデータの一致は保証されません。一般的なCRC利用は誤り検出が目的です。
ハミング距離・ハミング符号・ECC
正確な意味: ハミング距離は同じ長さの二つのビット列で値が異なる位置の数です。正しい符号語同士の最小距離をdとすると、d−1ビットまでの任意の誤りを検出でき、floor((d−1)/2)ビットまでの任意の誤りを訂正できます。
ざっくり言うと: 正しいデータの候補同士を十分離しておくと、少し壊れても元を推測できます。
ハミング符号は複数のパリティ検査を組み合わせ、単一ビット誤りの位置を特定して訂正できる符号です。検査結果の組をシンドロームと呼びます。通常の最小距離3のハミング符号と、全体パリティを追加して1ビット訂正・2ビット検出を行う拡張符号は区別します。
用途・問題での見方: ECCは誤り訂正符号の総称で、ECCメモリなどに使います。訂正可能な個数は符号方式によります。訂正モードで最も近い符号語へ決める場合、能力を超えた誤りを誤訂正する可能性があります。「検出できる」と「訂正しつつ別の誤りを検出できる」の条件も分けて考えます。
確認問題【オリジナル】
二つの8ビット列10110010と10011011のハミング距離はどれでしょうか。
ア:2
イ:3
ウ:4
エ:8
正解と理由
イ:3です。 左から3桁目、5桁目、8桁目が違います。XORを取ると00101001で、1が3個になります。ア・ウは位置の数え間違い、エは列全体の長さです。1の個数の差や、整数として読んだ値の差ではありません。
参考資料と問題について
学習範囲の確認:IPA「基本情報技術者試験 シラバス Ver.9.2」。本記事は独自の説明・例題です。
確認問題と解説はオリジナルです。公開過去問の転載・改変問題ではありません。出題頻度は未集計です。