デジタルデータの誤り検出・誤り訂正(後編)


前回の「デジタルデータの誤り検出・誤り訂正(前編)」では、代表的な誤り検出・訂正符号の概要と、垂直水平パリティによる簡易的なECCについて説明しました。ECCは、信頼性が求められるメモリ製品に多く搭載されている機能です。データの信頼性を高めるためにもECC機能を理解して効果的に使用することが重要になりますので、今回はもう少し実用的な例として、ハミング符号を用いたECC機能の基本的な仕組みについて説明します。
ECC(Error Correction Code/Error Check and Correct)
ECC は、Error Correction Code(誤り訂正符号)や、Error Check and Correct(誤り検出・訂正)の略で、「デジタルデータの1bitエラーの訂正もしくは2bitエラーを検出するために付加される符号または検出機構」のことです。ECCの「誤り訂正符号」は「誤り検出符号」の組み合わせで構成することができ、様々な構成がありますが、今回は代表的な例としてハミング符号を用いたECCの基本的な仕組みを説明します。
メモリ製品においては、長期連続稼働におけるデータエラーの予防や信頼性向上のため、ECC機能を搭載したものが多く出てきています。なお、メモリ製品などに搭載される 1bitエラー訂正/2bitエラー検出の「回路」のことは、SECDED(Single-bit Error Correction Double-bit Error Detection)と呼ばれています。
ハミング符号を使用したECCの例
ハミング符号(Hamming code)
ハミング符号は、パリティチェックを拡張した誤り検出・訂正符号の一つです。
パリティチェックでは、元のビット列中にある「1」の数が偶数個か奇数個かのパリティビットを付加しますが、ハミング符号では元のビット列からいくつかの異なる複数ビットの組み合わせを用意し、それぞれのパリティを算出して付加することで、元のビット列のどこに1bitエラーが発生したのかを検出することができます。
ハミング符号を使用したECCの例
今回のECCの例では、ビット位置を2進数で表すようにハミング符号を設定してみます。
一例として、16bitの情報データでの計算式の考え方を示します。
16bitの各ビット位置を表す 0~15 の数値は、左下図のように4桁の2進数で表すことができ、各桁にはそれぞれ’0’と’1’が混在しています。ここで、例えば1桁目が’0’であれば偶数ビットを表し、’1’であれば奇数ビットを表していることから、1桁目は偶数・奇数のどちらかに絞り込むことができるので、’0’のグループと’1’のグループに分けます。
他の2、3、4桁目も同様に‘0’と’1’に分けることで、計8パターンの異なる複数ビットの組み合わせが構成されます(右下図参照)。
右上図を左に90°回転させ、’0’ を P、’1’ を Q に置き換えた表が下図になります。
各桁の’0’と’1’のグループは便宜上、p[n]、q[n] とします。(nは各桁数-1)
この、異なる複数ビットの組み合わせで構成されたハミング符号 p[n]、q[n] の算出方法は、上表に従って、以下のように各bitの XOR(排他的論理和)の組み合わせで計算します。
p[0] = bit[14] xor bit[12] xor bit[10] xor bit[8] xor bit[6] xor bit[4] xor bit[2] xor bit[0]
q[0] = bit[15] xor bit[13] xor bit[11] xor bit[9] xor bit[7] xor bit[5] xor bit[3] xor bit[1]
p[1] = bit[13] xor bit[12] xor bit[9] xor bit[8] xor bit[5] xor bit[4] xor bit[1] xor bit[0]
q[1] = bit[15] xor bit[14] xor bit[11] xor bit[10] xor bit[7] xor bit[6] xor bit[3] xor bit[2]
p[2] = bit[11] xor bit[10] xor bit[9] xor bit[8] xor bit[3] xor bit[2] xor bit[1] xor bit[0]
q[2] = bit[15] xor bit[14] xor bit[13] xor bit[12] xor bit[7] xor bit[6] xor bit[5] xor bit[4]
p[3] = bit[7] xor bit[6] xor bit[5] xor bit[4] xor bit[3] xor bit[2] xor bit[1] xor bit[0]
q[3] = bit[15] xor bit[14] xor bit[13] xor bit[12] xor bit[11] xor bit[10] xor bit[9] xor bit[8]
上述は16bitデータ長を例にしていますが、この法則に従ってデータ長を増やすこともできますので、32bitデータ長でも128bitデータ長でも計算式は容易に想像できると思います。
なお、情報データが16bitデータの場合の検出・訂正符号(ハミング符号)の数は8ビット使用しますので、この場合は、垂直水平パリティを用いた場合の冗長ビット数と変わりません。
ただし、このECCの例では、(2^n)bit の情報データに対し、検出・訂正符号は(2n)bitで構成されますので、
- 情報データ長 16bit =(2^4)bit ⇒ 検出・訂正符号 8bit =(2×4)bit
- 情報データ長 32bit =(2^5)bit ⇒ 検出・訂正符号 10bit =(2×5)bit
- 情報データ長 128bit =(2^7)bit ⇒ 検出・訂正符号 14bit =(2×7)bit
となり、元の情報データ長が多いほど冗長ビットを少なくすることができます。
ECCの基本的なアルゴリズムの考え方
ECC機能を搭載したメモリの場合、基本的にはメモリへのWrite(データ書き込み)が行われる際に検出・訂正符号を算出し、本来のデータと共にこの検出・訂正符号(冗長ビット)がメモリ内に書き込まれます。
そして、このデータをRead(データ読み出し)したり、データ転送後の受信側でのチェックする時には該当データの検出・訂正符号は再計算され、データに付加された検出・訂正符号と比較してデータの正しさを判断します。
Read時もしくはデータ受信後のチェックにおいて、本来のデータに異常が無ければ、受信データの算出結果と、元データと共に書き込まれている検出・訂正符号の値に差異は生じませんのでデータが正しいと判断できますが、例えば、元のデータに1bitもしくは2bitのbitエラーが発生していた場合は、改めて算出された検出・訂正符号とは異なる値になります。
この時の、元データの検出・訂正符号と、Read時もしくはデータ受信時におけるデータから算出した検出・訂正符号との比較によって不一致だった p[n]、q[n] に着目し、以下の条件に該当すれば1bitの検出・訂正が可能になる判断ができます。
1bitエラー検出・訂正が可能な条件
- 不一致の p[n]、q[n] の内、同じ n の p[n]、q[n] がどちらか1つの場合
- かつ、n が 3,2,1,0 の全て揃っている場合
検出・訂正符号の不一致があり、かつ上述の条件を満たさない場合は2bitエラーが発生していることの判断はできますが、bitエラーが発生している箇所は特定できないため、検出のみ(修正不可)となります。
なお、3bit以上のbitエラーがあった場合は、上述の何れかと誤認されたり、算出した検出・訂正符号が元データの検出・訂正符号と一致することもあり、間違った判断に基づいて誤り訂正を行ったり、誤りが無いと判断される場合もありますので、3bit以上のエラーに対してはECCは機能しません。
・ECCの1bit検出・訂正例
元の16bitデータが 0xFFFF= All ‘1’ として、(この場合の検出・訂正符号計算値は、All ‘0’ になります)
この例では、13bit目でbitエラーが発生していることが特定できるので訂正可能です。
もしも、2bit以上のbitエラーが発生していた場合は、
検出・訂正符号の比較では不一致になるため、どこかで bitエラーが発生していることの検出はできますが、「同じ ‘n’ の q[n]、p[n] はどちらか1つずつ」かつ「‘n’ が 3,2,1,0 の全て揃っている場合」の条件を満たさないため訂正はできません。
まとめ
今回は、ECCの基本的な考え方の説明としてハミング符号を用いたECCについて紹介しました。
誤り検出・訂正符号や検出機構については、ECCだけでなく他にも多数存在していますが、誤りを完全に検出する符号や、万能な誤り訂正は存在しません。システムに誤り検出・訂正を実装する際には、データ量や誤りの発生頻度、誤り発生が想定される状況によって適切な検出方法を選択して頂くことをお勧めします。
丸文では、データ信頼性のためのECC機能を内蔵したメモリ製品やFlash/SRAM搭載マイコン製品を多数取り扱っておりますので、以下の製品紹介ページもご参照ください。