P Qパリティの計算方法

ウィキペディア小見出し辞書

P+Qパリティの計算方法

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/08/21 20:49 UTC 版)

「RAID」の記事における「P+Qパリティの計算方法」の解説

PパリティはRAID5と同じXORによるパリティであり、もう一つの冗長データであるQパリティは重みつきのガロア体GF(2) における剰余、つまり8ビットのCRCを用いる。8ビットCRCの制限により、この方式を用いる限りデータディスクは255台（+冗長ディスク2台）までしかサポートできない。 規格のようなものがないため、生成多項式や重みのつけかたが各社で異なる。また高速化やハードウェア的な最適化のためにあらかじめ定数をかけたテーブルが用意されているなど、単純なCRCには見えない場合もある。あるいは、これ以外の算出方法を採っている場合も有り得る。 具体的な算出方法は以下の通りである。 データディスクをA・B・C・Dとし、冗長ディスクをP・Qとする。現実には冗長ディスクは分散されているが、便宜上こうしておく。 P=A+B+C+D （RAID5と同じ） Q=CRC(A+B*2+C*4+D*8) ここで、AとはデータディスクAにある1バイトのデータであり、以下B・C・D・P・Qそれぞれ、対応する同じ位置にある1バイトのデータを示す。またCRC(x) は、値xをビット列とした時のCRC符号である。このCRCは、生成多項式が既約性を持つ（==原始多項式である）必要がある。また上記加算 (+) 及び乗算 (*) は、共にガロア体での加算乗算である。 また回復方法は以下の通りである。 データディスクA・B・C・Dのいずれか一つが破損した場合は、RAID5と同じ。また冗長ディスクP・Qのいずれか一つ乃至は二つが破損した場合は、データディスクA・B・C・Dから再計算する。 A・B・C・Dのいずれか一つとQが破損した場合は、Pと正常なデータディスクとで破損したデーターディスクを（RAID5と同様に）回復し、Qを再計算する。 A・B・C・Dのいずれか一つとPが破損した場合は、Qから、破損したデータディスクの位置に8ビットのバースト誤りがあったものとして消失訂正することで回復する。 A・B・C・Dのいずれか二つが破損した場合は、PとQに関する連立方程式を解いて回復する。 例えばB・Dが破損したとする。 P=A+B+C+D P-(A+C)=B+D P+A+C=B+D （加算と減算は共にXORで同一なので） Q=CRC(A+B*2+C*4+D*8) Q=CRC(A+C*4)+CRC(B*2+D*8) （CRCは加算 (XOR) に関して分配法則が成り立つ） Q-CRC(A+C*4)=CRC(B*2+D*8) Q+CRC(A+C*4)=CRC(B*2+D*8) （加算と減算は共にXORで同一なので） となるので、この連立方程式を解く。 P+A+C=B+D P+A+C-B=D P+A+C+B=D これを代入して Q+CRC(A+C*4)=CRC(B*2+D*8) Q+CRC(A+C*4)=CRC(B*2+(P+A+C+B)*8) Q+CRC(A+C*4)=CRC(B*2+(P+A+C)*8+B*8) Q+CRC(A+C*4)=CRC(B*2+B*8+(P+A+C)*8) Q+CRC(A+C*4)=CRC(B*(2+8)+(P+A+C)*8) Q+CRC(A+C*4)=CRC(B*10+(P+A+C)*8) Q+CRC(A+C*4)=CRC(B*10+(P+A+C)*8) Q+CRC(A+C*4)=CRC(B*10)+CRC((P+A+C)*8) Q+CRC(A+C*4)-CRC((P+A+C)*8)=CRC(B*10) Q+CRC(A+C*4)+CRC((P+A+C)*8)=CRC(B*10) ここで、CRCの生成多項式は原始多項式であるので、10と互いに素である。ここから中国の剰余定理を利用してBを算出する。つまり左辺を10（二進法で1010）で割る。それを P+A+C+B=D に代入して D を求める。