IBMの研究員が考案したHsiaoコード

エラー訂正を行うには、チェックビットやシンドロームを計算するする必要がある。この計算ではHマトリクスに"1"があるビットの値のXORを取る。従って、できるだけHマトリクスの"1"の数が少ない方が、必要なXORゲートが少なくて済むし、 XORゲートの遅延の合計である計算時間も短くて済む。

この考え方で作られたコードに、IBMの研究員であったHsiao氏が考案したHsiaoコードがある。各列に"1"が1つしかない列をチェックビットとする点はハミングコードと同じであるが、データビットに対応する列は、3個の"1"があるものを使う。ただし、同じ列は一度しか使ってはならない。図2.17に示す(8、4)コードではデータビットに対応するすべての列は3個の"1"となっているが、より長いコードでは3個の"1"の組み合わせを使いきると、5個の"1"、7個の"1"というように奇数の"1"を持つ列を"1"の数が少ない順に使っていく。後に説明するように偶数個の"1"を持つ列は使えないので、Hsiaoコードのように"1"の数の少ない順に各列を選ぶとHマトリクスの中の"1"の数は最小になる。

この場合、各列は4要素であり、3個が"1"となる組み合わせは4個しかないので、そのすべてが使われることになるが、d0～d3と列の対応はどのようにしても良い。

前に述べたハミングコードの場合と同じで、1ビットエラーが起こった場合のシンドロームは、エラービット位置のHマトリクスの列の値と等しい。Hsiaoコードでは各列の"1"の個数は奇数であるので、1ビットエラーの場合のシンドロームに含まれる"1"の数は奇数となる。そして、Hマトリクスの各列の値は全て異なっているので、シンドロームの値を見ればどのビットがエラーしたかが分かる。

しかし、Hsiaコードの場合は列が2進数の順に並んでいない。このため、シンドロームの値とビット位置の対応はハミングコードとは異なるが、図2.15の中のシンドロームのデコーダ出力とビットを反転させるXORとの接続を変えることで対応できる。

2ビットのエラーが起こった場合は、エラービット位置の2つの列のXORを取ったものがシンドローム値となる。Hsiaoコードでは、各列の"1"の数は奇数となっているので、2つの列を比べると、必ず偶数個の値が異なっており、シンドロームの中の"1"の数は偶数となる。

つまり、シンドローム値はエラーが無い場合は0、1ビットエラーの場合は奇数個の"1"、2ビットエラーの場合は偶数個の"1"を持つことになるので、1ビットエラーの訂正と2ビットエラーの検出が可能であることが分かる。

図2.16のSECEDハミングコードのHマトリクスでは20個の"1"があるのに対して、図2.17のHsiaoコードでは16個の"1"である。(8、4)のような短いコードではあまり大きな差ではないが、実用的に使われる64ビットデータに対する(72、64)コードの場合は、Hsiaoコードの"1"の個数は216個であるのに対して、ハミングコードは296個の"1"というように大きな差がつく。

ここでは、直感的に理解しやすい、1ビットエラー訂正と2ビットエラー検出を行うハミングコードとHsiaoコードを説明したが、抽象代数に基づくBCH(Bose Chaudhuri Hochenghem)コードを使うと最小距離が5以上となるコードを作ることができる。Intelのミッションクリティカルサーバ用のItaniumプロセサ「Poulson」の3次キャッシュには最小距離6のDECTED(Double bit Error Correction Triple bit Error Detection)エラー訂正コードが使われている。