ECC
をテンプレートにして作成
[
トップ
] [
新規
|
一覧
|
単語検索
|
最終更新
|
ヘルプ
]
開始行:
* ECC (Error Correcting Code) [#u85cd7ed]
-「Error Check and Correction」の略だと説明している例もあ...
-ハードウェアを制御していると、ECCフィールドやCRC値があっ...
-CRCについては、資料が少なくてまだわかってないので、分か...
* ECCはどんな所に使われているか [#v285c20a]
-CD-ROMのエラー訂正、L2キャッシュのエラー訂正など(Pentiu...
-スマートメディアの内部物理フォーマットでも使われているら...
* ECCの基本 [#k7973645]
-ECCは2のべき数個のbitを対象にして、エラーの検出と訂正を...
--データとECCをあわせて、もしビット化けが1ヵ所もなければ...
--データとECCをあわせて、もしビット化けが1ヵ所あれば、間...
--データと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の算出) [#b7f1ed1b]
-説明の便宜上、与えられたデータのbit列に対して、bit[i]で...
--たとえば、8bitのデータで、これが0x43であれば、bit[] = {...
-そして次の値を計算する(ここでは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]のうちの半数...
||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の場合は次のようになる。これを見れば、他のb...
||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のアルゴリズム (エラー検出・訂正) [#oc8fa44e]
-ここでは通信相手からbit[]とECC(p[]とq[])を受信している状...
-まず、受信したbit[]を元に、ECCを構築してみる。そして受信...
-全ビットにbit化けがなかった場合:
--この場合当然ながら、構築したECCと受信したECCは同一にな...
-bit[]に1ヵ所のbit化けがあった場合:
--ここでは説明のために16bitデータ列を例に、bit[5]が反転し...
--計算式と上記の表を見比べると分かるか、この場合ECCの不一...
--そして、この並びにおいて、pを0、qを1と見立てると、0101(...
-ECCに1ヵ所のbit化けがあった場合:
--ここでは説明のために16bitデータ列を例に、p[2]が反転して...
--この場合もECCの不一致が起こる。しかし今回は不一致なのは...
--データが化けた場合は、不一致が全てのiに対してp[]かq[]の...
--だからこれはECCのビット化けであると判断でき、データ部の...
-bit[]に2ヵ所のbit化けがあった場合:
--ここでは説明のために16bitデータ列を例に、bit[0]とbit[9]...
--今回もECCの不一致が起こる。不一致なのは、p[3]、q[3]、p[...
--もはや1bit化けのときのようなパターンでないのは明白であ...
-bit[]に1ヵ所、ECCにも1ヵ所のbit化けがあった場合:
--ここでは説明のために16bitデータ列を例に、bit[1]とp[3]が...
--ECCの不一致が起こる。不一致なのは、p[2]、p[1]、q[0]であ...
--この場合もエラー訂正はできない(このようなパターンに対...
-ECCに2ヵ所のbit化けがあった場合:
--ECCの不一致が起こる。不一致なのはもちろん化けた2つの部...
-もっとたくさんのbit化けがあった場合:
--つじつまが合うように化ければ、ECCの不一致が起きなかった...
* 簡単な考察 [#b5e74c18]
-ECCはパリティを発展させたものだと考えることができる。
--パリティは、全てのデータbitをXORしたもの、つまりp = bit...
--パリティは1bitのbit化けを検出することができるが、訂正す...
--ECCもパリティのようにXORだけで演算可能だが、その組み合...
-ECCは長いデータに対しては相対的に少ないbit数で構成可能で...
--たとえば256バイトのデータに対して3バイトほどのECCであり...
--しかしエラー訂正能力も落ちていることに注意してほしい。1...
--もし大量のデータに対してエラー訂正力を高めたければ、デ...
--もちろん、ECC以外の方法を検討するという方法もある。
--CD-ROMでは、2048バイトのデータに対して276バイトのECCを...
-データサイズが2のべきでない場合は、足りない部分に0を補え...
* ECCの計算プログラム例 [#jd832a71]
-この程度のプログラムで計算できるだろう。
--高速化のため、一応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以下になったときに備えて */
}
* こめんと欄 [#w886c25b]
-すみません、気になったので書き加えました・・・。CRCも書...
-勝手な書き足しは非常に残念です。可能なら元に戻した後、[[...
-思いっきりポリシーに違反していました。まさに「最悪」です...
-ご理解とご協力に感謝いたします! -- [[K]] SIZE(10){2009-...
-私ではどうにもならないみたいなので、バックアップの削除の...
-バックアップはこのままでいいので、気にしないでください。...
-気にするしないではなく、表から消すよう言われた内容をこっ...
#comment
終了行:
* ECC (Error Correcting Code) [#u85cd7ed]
-「Error Check and Correction」の略だと説明している例もあ...
-ハードウェアを制御していると、ECCフィールドやCRC値があっ...
-CRCについては、資料が少なくてまだわかってないので、分か...
* ECCはどんな所に使われているか [#v285c20a]
-CD-ROMのエラー訂正、L2キャッシュのエラー訂正など(Pentiu...
-スマートメディアの内部物理フォーマットでも使われているら...
* ECCの基本 [#k7973645]
-ECCは2のべき数個のbitを対象にして、エラーの検出と訂正を...
--データとECCをあわせて、もしビット化けが1ヵ所もなければ...
--データとECCをあわせて、もしビット化けが1ヵ所あれば、間...
--データと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の算出) [#b7f1ed1b]
-説明の便宜上、与えられたデータのbit列に対して、bit[i]で...
--たとえば、8bitのデータで、これが0x43であれば、bit[] = {...
-そして次の値を計算する(ここでは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]のうちの半数...
||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の場合は次のようになる。これを見れば、他のb...
||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のアルゴリズム (エラー検出・訂正) [#oc8fa44e]
-ここでは通信相手からbit[]とECC(p[]とq[])を受信している状...
-まず、受信したbit[]を元に、ECCを構築してみる。そして受信...
-全ビットにbit化けがなかった場合:
--この場合当然ながら、構築したECCと受信したECCは同一にな...
-bit[]に1ヵ所のbit化けがあった場合:
--ここでは説明のために16bitデータ列を例に、bit[5]が反転し...
--計算式と上記の表を見比べると分かるか、この場合ECCの不一...
--そして、この並びにおいて、pを0、qを1と見立てると、0101(...
-ECCに1ヵ所のbit化けがあった場合:
--ここでは説明のために16bitデータ列を例に、p[2]が反転して...
--この場合もECCの不一致が起こる。しかし今回は不一致なのは...
--データが化けた場合は、不一致が全てのiに対してp[]かq[]の...
--だからこれはECCのビット化けであると判断でき、データ部の...
-bit[]に2ヵ所のbit化けがあった場合:
--ここでは説明のために16bitデータ列を例に、bit[0]とbit[9]...
--今回もECCの不一致が起こる。不一致なのは、p[3]、q[3]、p[...
--もはや1bit化けのときのようなパターンでないのは明白であ...
-bit[]に1ヵ所、ECCにも1ヵ所のbit化けがあった場合:
--ここでは説明のために16bitデータ列を例に、bit[1]とp[3]が...
--ECCの不一致が起こる。不一致なのは、p[2]、p[1]、q[0]であ...
--この場合もエラー訂正はできない(このようなパターンに対...
-ECCに2ヵ所のbit化けがあった場合:
--ECCの不一致が起こる。不一致なのはもちろん化けた2つの部...
-もっとたくさんのbit化けがあった場合:
--つじつまが合うように化ければ、ECCの不一致が起きなかった...
* 簡単な考察 [#b5e74c18]
-ECCはパリティを発展させたものだと考えることができる。
--パリティは、全てのデータbitをXORしたもの、つまりp = bit...
--パリティは1bitのbit化けを検出することができるが、訂正す...
--ECCもパリティのようにXORだけで演算可能だが、その組み合...
-ECCは長いデータに対しては相対的に少ないbit数で構成可能で...
--たとえば256バイトのデータに対して3バイトほどのECCであり...
--しかしエラー訂正能力も落ちていることに注意してほしい。1...
--もし大量のデータに対してエラー訂正力を高めたければ、デ...
--もちろん、ECC以外の方法を検討するという方法もある。
--CD-ROMでは、2048バイトのデータに対して276バイトのECCを...
-データサイズが2のべきでない場合は、足りない部分に0を補え...
* ECCの計算プログラム例 [#jd832a71]
-この程度のプログラムで計算できるだろう。
--高速化のため、一応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以下になったときに備えて */
}
* こめんと欄 [#w886c25b]
-すみません、気になったので書き加えました・・・。CRCも書...
-勝手な書き足しは非常に残念です。可能なら元に戻した後、[[...
-思いっきりポリシーに違反していました。まさに「最悪」です...
-ご理解とご協力に感謝いたします! -- [[K]] SIZE(10){2009-...
-私ではどうにもならないみたいなので、バックアップの削除の...
-バックアップはこのままでいいので、気にしないでください。...
-気にするしないではなく、表から消すよう言われた内容をこっ...
#comment
ページ名: