パリティビット
| 7ビットのデータ | パリティビット付きのバイト | |
| even | odd | |
| 0000000 | 00000000 | 10000000 |
| 1010001 | 11010001 | 01010001 |
| 1101001 | 01101001 | 11101001 |
| 1111111 | 11111111 | 01111111 |
パリティビット (英: parity bit) は、コンピュータと通信において、与えられた二進数に対して全体の偶奇性を保つために与えられる一桁の二進数︵つまり 0 か1︶である。パリティビットは最も単純な誤り検出符号である。
パリティ機構を使用するにあたっては、奇数(odd)か偶数(even)かを指定しなければならない。パリティ(奇偶性)がevenであるというのは、与えられた二進数の中に1が偶数個存在することを意味し、そうでなければoddである。多くの場合oddパリティが用いられる。even パリティは巡回冗長検査 (CRC) の特殊ケースであり、1ビット CRCは x+1 という多項式から生成される。
誤り検出 編集
パリティビットを用いた誤り検出を﹁パリティチェック﹂と呼ぶ。
パリティビットも含めて奇数個のビットが転送中に変化した場合、パリティビットは正しくないことになり、転送中に誤りが発生したことを示す。したがって、パリティビットは誤り検出符号であるが、どのビットが変化したかを指摘できないため、誤り訂正符号ではない[注釈1]。データはパリティビットを付与された単位全体が捨てられ、再送される。雑音の多い伝送路では、転送が成功するまで非常に時間がかかったり、全く転送できないということが考えられる。パリティビットは最善の方式ではないが、1ビットだけ追加するだけで済む点やいくつかのXORゲートだけで生成できる点が利点である。誤り訂正のできる符号の例としては、ハミング符号がある。
例えば、4ビットの値 1001 のパリティビットは以下のように計算され、転送されるとする︵送受信値の左端のビットがパリティビット︶。
1^0^0^1 = 0 : A にてevenパリティを計算 01001 : A から送信 01001 : B で受信 1^0^0^1 = 0 : B にてevenパリティ検証
~(1^0^0^1) = 1 : A にてoddパリティを計算 11001 : A から送信 11001 : B で受信 ~(1^0^0^1) = 1 : B にてoddパリティ検証この機構により1ビットの誤り検出が可能となる。これは、1ビットの値が変化すると、予め定めた奇遇性と '1' の数が合わなくなるためである。上記の例では、Bが計算したパリティ値と受信したパリティビットの値は一致しており、1ビット誤りが起きていないことを示している。なお、B側の検証においては、﹁パリティを除いて計算した値とパリティを比較﹂する代わりに、CRC と同様に﹁パリティを含めて計算した値が特定の値[注釈2]になるか﹂と言う方法でも良い。上記の例では、それぞれ最後の1ステップを
0^1^0^0^1 = 0 : B にてevenパリティ検証
1^1^0^0^1 = 1 : B にてoddパリティ検証とできる。一般にはこちら実装の方が回路等が単純になる[要出典]。次の例では4ビットの値 0010 を even パリティで送信して誤りが発生した場合を示す︵送受信値の左端のビットがパリティビット︶。
0^0^1^0 = 1 : A にてevenパリティを計算 10010 : A から送信 *** 転送中に誤り発生 *** 11010 : B で受信 1^0^1^0 = 0 : B にてevenパリティ検証Bが計算したパリティ値 (0) は、受信したパリティビットの値 (1) と一致しないため、誤りが発生していることが分かる。次の例も同じ値だが、パリティビット自体が誤りによって変化した場合を示す。
0^0^1^0 = 1 : A にてevenパリティを計算 10010 : A から送信 *** 転送中に誤り発生 *** 00010 : B で受信 0^0^1^0 = 1 : B にてevenパリティ検証この場合もBが計算したパリティ値 (1) と受信したパリティビットの値 (0) が一致しないので、誤りが検出される。 この技法には限界がある。パリティビットは奇数個のビットの誤りしか検出できない。偶数個のビットで誤りが発生した場合、パリティ値が変化しないため、誤りを検出できない︵誤り検出訂正参照︶。上記と同じ例で、偶数個のビットの誤りが発生した場合を示す。
0^0^1^0 = 1 : A にてevenパリティを計算 10010 : A から送信 *** 転送中に誤り発生 *** 11011 : B で受信 1^0^1^1 = 1 : B にてevenパリティ検証Bが計算したパリティ値 (1) と受信したパリティビットの値 (0) が一致してしまうので、2ビットの誤りを検出できない。
使用例 編集
非常に単純であるため、パリティはハードウェアの様々なところで使われている。ただしエラーが起きたら再送するか、あるいは単にエラーを検出するだけで足りる場合である。たとえばSCSIバスはパリティを使用してエラーを検出している。マイクロプロセッサの命令キャッシュもパリティビットを持っていることが多い。命令キャッシュの内容は単なるメインメモリのコピーなので、エラーを検出したら再度メモリから持ってくればよいからである。 シリアルなデータ転送では、データビット7個につき even パリティビット1個︵そして1～2個のストップビット=区切り︶というのが一般的である。even パリティとは、値が1であるビットの個数が偶数であることを意味する。このフォーマットは7ビットのASCIIキャラクタを適切に扱い、扱いやすい8ビットにするという意味で便利である。他のフォーマットも使用可能である。たとえば8ビットデータにパリティビットを追加するという場合もある。 通信においては、パリティは送受信ハードウェア (UART) 内で付与されチェックされる。エラーがあったかどうかはその周辺ハードウェアのステータスをCPUが読んで判断する。修復(訂正)は再度送信してもらうのが一般的である。詳細はCPU︵オペレーティングシステム︶が設定する。パリティブロック 編集
RAIDのレベルによっては、パリティブロックが使われる。これは冗長性を確保するための手法である。アレイ内の1つのドライブが故障したとき、故障していないドライブ群のデータブロックとパリティブロックから正しいデータを再構築できる。 下記の表で、縦の列が1つのディスクドライブを表し、横の行が対応するデータブロックとパリティブロックを表す。例えば、A1 = 00000111, A2 = 00000101, A3 = 00000000 としたとき、Apは A1 から A3 をビット毎に XOR することで生成され 00000010 となる。2台目のディスクドライブが故障すると A2 にアクセスできなくなるが、A1, A3, Ap を XOR することで A2 を再構築できる。 A1 XOR A3 XOR Ap = 00000101RAID5 Array A1 A2 A3 Ap B1 B2 Bp B3 C1 Cp C2 C3 Dp D1 D2 D3 注: データブロック群が A# のとき、そのパリティブロックは Ap である。