Mixing
パリティビット
| 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 誤り検出
2 使用例
2.1 パリティブロック
3 外部リンク
誤り検出
パリティビットを用いた誤り検出を「パリティチェック」と呼ぶ。
パリティビットも含めて奇数個のビットが転送中に変化した場合、パリティビットは正しくないことになり、転送中に誤りが発生したことを示す。従って、パリティビットは誤り検出符号であるが、どのビットが変化したかを指摘できないため、誤り訂正符号ではない。データはパリティビットを付与された単位全体が捨てられ、再送される。雑音の多い伝送路では、転送が成功するまで非常に時間がかかったり、全く転送できないということが考えられる。パリティビットは最善の方式ではないが、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ビット誤りが起きていないことを示している。次の例では 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 = 0000000 としたとき、Ap は A1 から A3 をビット毎に XOR することで生成され 00000010 となる。2台目のディスクドライブが故障すると A2 にアクセスできなくなるが、A1、A3、Ap を XOR することで A2 を再構築できる。
A1 XOR A3 XOR Ap = 00000101
RAID5 Array
A1 A2 A3 Ap
B1 B2 Bp B3
C1 Cp C2 C3
Dp D1 D2 D3
注: データブロック群が A# のとき、そのパリティブロックは Ap である。
外部リンク
- Quick way to get the odd parity of an integer
- Different methods of generating the parity bit, among other bit operations
