ECC

ECC (Error Correcting Code) †

• 「Error Check and Correction」の略だと説明している例もある。
• ハードウェアを制御していると、ECCフィールドやCRC値があったりするが、これがいったいどんなものなのかを具体的に知ることは、非常に価値があると思う（一部のハードウェアドライバでは、ECCやCRC値を計算しなければいけないこともある）。このページでは、そのECCのことを説明したい。
• CRCについては、資料が少なくてまだわかってないので、分かったら別ページに書きます。

ECCはどんな所に使われているか †

• CD-ROMのエラー訂正、L2キャッシュのエラー訂正など（Pentium2以降だったかな？）。
• スマートメディアの内部物理フォーマットでも使われているらしい（アダプタを使ってPCカードATAとしてアクセスしている時は、ECCの管理はアダプタに隠蔽されているので、ドライバ作成には関係ないが）。

ECCの基本 †

• ECCは2のべき数個のbitを対象にして、エラーの検出と訂正をおこなう。
  • データとECCをあわせて、もしビット化けが1ヵ所もなければ、それはもちろんエラー無しと判断できる。
  • データとECCをあわせて、もしビット化けが1ヵ所あれば、間違いがあることが検出できる上に、どこで間違えたかを特定できる。そうなればそのbitを反転させればいいので、エラーは訂正できる。
  • データとECCをあわせて、もしビット化けが2ヵ所あれば、間違いがあることは検出できるが、どこで間違えたかを特定することはできない。したがって訂正はできない。
  • データとECCをあわせて、もしビット化けが3ヵ所以上あれば、上記のどれかであると誤認し、結果としてめちゃくちゃになる。
  • たとえば8bitのデータに対しては、ECCは6bitで構成される。
  • 16bitのデータに対しては、ECCは8bitで構成される。
  • 32bitのベータに対しては、ECCは10bitで構成される。
  • 16バイト(128bit)のデータに対しては、ECCは14bitで構成される。
  • 256バイト(2048bit)のデータなら、ECCは22bitで構成される。
  • 一般に(2^n)bitのデータでは、ECCは(2n)bitで構成される。
• ECCでは演算に、XORしか使わない。

ECCのアルゴリズム (ECCの算出) †

• 説明の便宜上、与えられたデータのbit列に対して、bit[i]で、i番目のbitのデータの値、を意味するとする。
  • たとえば、8bitのデータで、これが0x43であれば、bit[] = { 1, 1, 0, 0, 0, 0, 1, 0 };というわけである。
• そして次の値を計算する(ここでは8bitの例)。^はXORを意味する。
  • p[0] = bit[0] ^ bit[2] ^ bit[4] ^ bit[6];
  • q[0] = bit[1] ^ bit[3] ^ bit[5] ^ bit[7];
  • p[1] = (bit[0] ^ bit[1]) ^ (bit[4] ^ bit[5]);
  • q[1] = (bit[2] ^ bit[3]) ^ (bit[6] ^ bit[7]);
  • p[2] = (bit[0] ^ bit[1] ^ bit[2] ^ bit[3]);
  • q[2] = (bit[4] ^ bit[5] ^ bit[6] ^ bit[7]);
  • XOR演算なので本当は括弧は不要。単に見易くするためだけに、括弧を入れている。
• 上記の式を図に書くこともできる。
  • つまりp[n]、q[n]の算出は、それぞれbit[0〜7]のうちの半数のXOR値を計算することである。どのビットをpの計算のために使うか、そしてどのビットをqの計算のために使うかを、表にまとめたものである。

    	0	1	2	3	4	5	6	7
    p[0], q[0]	P	Q	P	Q	P	Q	P	Q
    p[1], q[1]	P	P	Q	Q	P	P	Q	Q
    p[2], q[2]	P	P	P	P	Q	Q	Q	Q

• データが16bitの場合は次のようになる。これを見れば、他のbit長の場合も類推できるだろう。

  0

  1

  2

  3

  4

  5

  6

  7

  8

  9

  A

  B

  C

  D

  E

  F

  p[0], q[0]

  P

  Q

  P

  Q

  P

  Q

  P

  Q

  P

  Q

  P

  Q

  P

  Q

  P

  Q

  p[1], q[1]

  P

  P

  Q

  Q

  P

  P

  Q

  Q

  P

  P

  Q

  Q

  P

  P

  Q

  Q

  p[2], q[2]

  P

  P

  P

  P

  Q

  Q

  Q

  Q

  P

  P

  P

  P

  Q

  Q

  Q

  Q

  p[3], q[3]

  P

  P

  P

  P

  P

  P

  P

  P

  Q

  Q

  Q

  Q

  Q

  Q

  Q

  Q

• こうして計算したp[]とq[]が、まさにECCである。

ECCのアルゴリズム (エラー検出・訂正) †

• ここでは通信相手からbit[]とECC(p[]とq[])を受信している状況を想定。
• まず、受信したbit[]を元に、ECCを構築してみる。そして受信したECCと比較してみる。
• 全ビットにbit化けがなかった場合：
  • この場合当然ながら、構築したECCと受信したECCは同一になるはずである。だから一致した場合は、エラー無しと判定する。
• bit[]に1ヵ所のbit化けがあった場合：
  • ここでは説明のために16bitデータ列を例に、bit[5]が反転してしまった場合を考える。
  • 計算式と上記の表を見比べると分かるか、この場合ECCの不一致が起こる。不一致なのは、p[3]、q[2]、p[1]、q[0]だけである（あえて上位から並べた）。
  • そして、この並びにおいて、pを0、qを1と見立てると、0101(2進数)、つまり5である。これで、bit[5]が反転していたと分かり、訂正できる（うまくできているよなあ）。
• ECCに1ヵ所のbit化けがあった場合：
  • ここでは説明のために16bitデータ列を例に、p[2]が反転してしまった場合を考える。
  • この場合もECCの不一致が起こる。しかし今回は不一致なのは、p[2]一つだけである。
  • データが化けた場合は、不一致が全てのiに対してp[]かq[]のどちらか一方に出てくるのに、今回はそうではなくてただ一つだけであることに注意してほしい。
  • だからこれはECCのビット化けであると判断でき、データ部の訂正はしない。
• bit[]に2ヵ所のbit化けがあった場合：
  • ここでは説明のために16bitデータ列を例に、bit[0]とbit[9]が反転してしまった場合を考える。
  • 今回もECCの不一致が起こる。不一致なのは、p[3]、q[3]、p[0]である。
  • もはや1bit化けのときのようなパターンでないのは明白である。しかも、この情報だけではどこが間違っているのかも分からない。ということで、訂正不能なエラーを検出したと判断する。
• bit[]に1ヵ所、ECCにも1ヵ所のbit化けがあった場合：
  • ここでは説明のために16bitデータ列を例に、bit[1]とp[3]が反転してしまった場合を考える。
  • ECCの不一致が起こる。不一致なのは、p[2]、p[1]、q[0]である。
  • この場合もエラー訂正はできない（このようなパターンに対して、bit[]に1ヵ所、ECCにも1ヵ所のbit化けがあったと仮定することは可能だし、そしてその仮定から反転部分をbit[1]＆p[3]か、bit[9]＆q[3]かに絞ることはできるかもしれない・・・しかし結局そのどちらなのかは分からないので、やっぱり訂正はできない）。
• ECCに2ヵ所のbit化けがあった場合：
  • ECCの不一致が起こる。不一致なのはもちろん化けた2つの部分である。この場合も、訂正はしないで訂正不能なエラーを検出したと判断するのが普通である。
• もっとたくさんのbit化けがあった場合：
  • つじつまが合うように化ければ、ECCの不一致が起きなかったりするだろうし、たとえばp[]ビットだけが全て化ければ、bit[0]が化けたと誤認して、訂正して通過するだろう。したがって、そういうbit化けにはECCは無力である。

簡単な考察 †

• ECCはパリティを発展させたものだと考えることができる。
  • パリティは、全てのデータbitをXORしたもの、つまりp = bit[0] ^ bit[1] ^ bit[2] ^ bit[3] ^ ...だと考えられる。
  • パリティは1bitのbit化けを検出することができるが、訂正することはできない。また2bit化けたら、検出することすらできない。
  • ECCもパリティのようにXORだけで演算可能だが、その組み合わせを工夫して、エラーの検出と訂正を可能にしているところがすばらしい。
• ECCは長いデータに対しては相対的に少ないbit数で構成可能であるが、この場合、当然のことながらエラー訂正能力は落ちる。
  • たとえば256バイトのデータに対して3バイトほどのECCであり、合計259バイトからECC用のデータの割合を考えれば、これは1.2％ほどでしかない。これに対して32バイトのデータならECCは1バイトであり、割合は5.8％にもなる。
  • しかしエラー訂正能力も落ちていることに注意してほしい。100バイトに1bitの割合でエラーが起きた場合、32+2バイトの場合はエラー訂正できるが、256+3バイトの場合は、エラー訂正できないのである。
  • もし大量のデータに対してエラー訂正力を高めたければ、データを分割して、それぞれでECC計算を行なうのがいいだろう。たとえば256バイトのデータを32バイトx8個に分割して、ECCも2x8=16バイトもつのである。当然ながら、この場合はECCの占める割合は5.8％になる。
  • もちろん、ECC以外の方法を検討するという方法もある。
  • CD-ROMでは、2048バイトのデータに対して276バイトのECCを持っているが、これは2048バイトを16バイトx128個に分割しているのだろうか？（実はよくわかっていない）。そうだとすればECCは2バイトx128=256バイトとなり、276バイトに近くなる。
• データサイズが2のべきでない場合は、足りない部分に0を補えば、ECCを計算したり利用したりできるようになる。

ECCの計算プログラム例 †

• この程度のプログラムで計算できるだろう。
  • 高速化のため、一応8bitずつ処理するように工夫しています。
  • table初期化は最初に一度だけやればいいです。
  • バグがあったらごめんなさい（教えてくれたら直します）。
  • copyright (C) 2003 川合秀実 (under KL-01)

    unsigned char p[N], q[N], data[1 << (N - 3)];
    unsigned char table[256]; /* bit4がp, bit5がq, bit0-3は縮退用 */
    unsigned char tmp;
    int i, j, size;
    
    for (i = 0; i < 256; i++) { /* table初期化 */
        unsigned char b[8];
        tmp = i;
        for (j = 0; j < 8; j++) {
            b[j] = tmp & 1;
            tmp >>= 1;
        }
        table[i] = (b[0] ^ b[2] ^ b[4] ^ b[6]) << 4
                 | (b[1] ^ b[3] ^ b[5] ^ b[7]) << 5
                 | (b[0] ^ b[1])      | (b[2] ^ b[3]) << 1
                 | (b[4] ^ b[5]) << 2 | (b[6] ^ b[7]) << 3;
    }
    
    /* ECC計算本体(この例ではdata[]を破壊するので注意) */
    size = 1 << (N - 3);
    for (i = 0; i < N; i++) {
        tmp = 0; j = 0; /* p[i]とq[i]の計算ループ */
        do {
            tmp ^= table[data[j++]];
        } while (j < size);
        p[i] = (tmp >> 4) & 1;
        q[i] = (tmp >> 5) & 1;
        size /= 2; j = 0; /* data[]を縮退させるループ */
        do {
            data[j] = (table[data[j * 2]] & 0xf)
                    | (table[data[j * 2 + 1]] & 0xf) << 4;
            j++;
        } while (j < size);
        data[j] = 0; /* sizeが1以下になったときに備えて */
    }

こめんと欄 †

• すみません、気になったので書き加えました・・・。CRCも書いたほうがいいですか？ -- victories 2009-07-26 (日) 16:11:46
• 勝手な書き足しは非常に残念です。可能なら元に戻した後、impressionsにて、ページを作るべきかどうかを相談してほしいです。 -- K 2009-07-27 (月) 01:00:15
• 思いっきりポリシーに違反していました。まさに「最悪」ですね。。。すみませんでした。元に戻しておきます。 -- victories 2009-07-27 (月) 11:58:13
• ご理解とご協力に感謝いたします！ -- K 2009-07-27 (月) 23:43:35
• 私ではどうにもならないみたいなので、バックアップの削除のほう、よろしくお願いします。 -- victories 2009-07-30 (木) 09:59:00
• バックアップはこのままでいいので、気にしないでください。 -- K 2009-07-30 (木) 12:29:27
• 気にするしないではなく、表から消すよう言われた内容をこっそり見れる状態はどうかと思うので、お手数ですが、削除願います。 -- victories 2010-01-04 (月) 17:35:08