パリティチェック
ビット列に検査用のビットを付け、1の個数の偶奇を確認して誤りを見つける方法。単一の検査では奇数個のビット反転を検出できるが、誤った場所までは分からない。
イマシルちゃんの解説
箱に印を付け、全体の印の数が決めた数え方に合うか確かめるとするよ。
途中で一つの印が変われば、約束と合わなくなるんだ。
でも、別の印も一緒に変わると、見かけ上は約束に合ってしまうことがあるよ。
合わないと分かっても、どの印を戻せばよいかまでは決まらないんだ。
より深い解説
検査用のビットを付ける
元のデータにパリティビットを加え、データとその検査ビットを合わせた1の個数について、送受信側で同じ規則を使う。
| 方式 | 合計の1の個数 |
|---|---|
| 偶数パリティ | 偶数にそろえる |
| 奇数パリティ | 奇数にそろえる |
検査ビット自身も誤りの対象である。データが正しくても、検査ビットの反転により不一致となり得る。
独自の計算例
データ1011001には、1が4個ある。全体を偶数にそろえるなら、付加する値は0となる。
| 受信したデータ部分 | 付加された値 | 1の合計 | 判定 |
|---|---|---|---|
| 1011001 | 0 | 4 | 規則に一致 |
| 1011000 | 0 | 3 | 不一致 |
| 1011010 | 0 | 4 | 規則に一致するが、元と異なる |
最後の例は2か所が反転している。検査を通ったことは、誤りが絶対にないという保証ではない。
能力の限界
| 変化 | 単一の検査による結果 |
|---|---|
| 奇数個のビット反転 | 偶奇が変わるので検出できる |
| 偶数個のビット反転 | 偶奇が変わらず検出できない |
| 誤りの位置 | 検査結果だけでは特定できない |
不一致を検出しても、それだけでは正しいビット列へ訂正できない。再送を要求するなど、次の対応が必要である。
複数の方向で確かめる
複数の文字などを行に並べ、各文字のビットを検査する方法を垂直パリティ、同じビット位置を複数文字にわたって検査する方法を水平パリティという。図の縦横は配置によって変わるため、名前だけでなく検査するまとまりを見る。
両方を使う二次元の検査では、単一誤りなら、不一致の行と列の交点から位置を絞れる。ただし、長方形の四隅が反転するように検査を通る組合せもある。すべての多重誤りを検出できるわけではない。
ECCメモリとの比較
ECCはError Correcting Codeの略で、誤り訂正符号を意味する。メモリでは、符号の性質を利用してデータの誤りを訂正する。
1ビット訂正と2ビット誤り検出を行う構成には、拡張ハミング符号などを使う。単に各データへ一つ検査ビットを付けただけの方式とは、検査情報の組合せと訂正能力が違う。
| 手法 | 主な特徴 |
|---|---|
| 単一のパリティ | 計算が簡単だが、位置を特定できない |
| ハミング符号 | 複数の検査結果から位置を求める |
| CRC | 通信でのバースト誤りの検出などに適する |
| チェックサム | データを加算する方式など。計算法によって能力が異なる |