Share to: share facebook share twitter share wa share telegram print page

パリティビット

曖昧さ回避 この項目では、符号理論の一つについて説明しています。「ダービースタリオン」などのコンピュータゲーム開発企業については「パリティビット (ゲーム会社)」をご覧ください。
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 = 00000101 

            RAID5 Array
 A1        A2        A3        Ap
 B1        B2        Bp        B3
 C1        Cp        C2        C3
 Dp        D1        D2        D3

注: データブロック群が A# のとき、そのパリティブロックは Ap である。

注釈

  1. ^ ただし、エラーの発生した箇所が高々1つであり、その箇所が特定できるならば訂正ができる。そのような例の一つが RAID である。詳細は#パリティブロックを参照
  2. ^ evenパリティでは0。oddパリティでは1

外部リンク
Kembali kehalaman sebelumnya