エラー検出訂正 ─ ECCメモリとパリティ・CRCの数理

なぜ冗長ビットで誤りが直せるのか

メモリのセルは宇宙線や微細化による電荷漏れで、伝送路はノイズで、ビットが勝手に反転します。生のデータだけでは、受け取った 1011 が送られた値そのものなのか化けた結果なのか判別できません。そこで送る前に冗長ビットを計算して付け、受信側で同じ計算を再現して食い違いを調べます。

鍵は「全2^kの値のうち、規則を満たす組み合わせだけを正しい符号語（codeword）として使う」点にあります。正しい符号語どうしを十分に離して配置すれば、1ビット程度の化けでは別の正しい符号語に化けきれず、最も近い符号語へ復元できます。この「離れ具合」を測るのがハミング距離（異なるビット数）です。

最小ハミング距離 d の符号で保証できる能力
  検出: d - 1 ビットまで
  訂正: floor((d - 1) / 2) ビットまで

距離2なら1ビット検出のみ（パリティ）、距離3なら1ビット訂正、距離4なら1ビット訂正＋2ビット検出（SECDED）になります。符号理論はこの距離をいかに安く稼ぐかの工学です。

パリティ ─ 距離2の最小冗長

最も単純なのがパリティビットです。データビット全体のXOR（1の個数の偶奇）を1ビット付加します。

偶数パリティ: データ + パリティ の中の 1 の総数が偶数になるよう付ける
  data = 1011 (1が3個) -> parity = 1 -> 送出 10111
受信側: 全ビットをXOR
  結果が 0 なら偶数のまま（誤りなしと判定）
  結果が 1 なら 1 の個数が奇数 = 奇数個のビット誤り

パリティは奇数個（1,3,5…）の誤りを検出できますが、どのビットが化けたかは分からず訂正できません。偶数個の誤りはパリティが元に戻るため見逃します。最小ハミング距離が2しかないためで、検出専用の下限です。それでも安価ゆえ、UART通信やかつてのパリティメモリで広く使われました。

ハミング符号 ─ 位置をビットで特定する

R・ハミングのアイデアは、複数の検査ビットを重なり合う部分集合にかけ、各検査結果を2進数の桁として読むことで誤り位置そのものを表す点にあります。

ビット位置を1から順に番号付けし、2の冪の位置（1,2,4,8…）を検査ビット、残りをデータビットとします。検査ビット Pi（位置 2^i）は、「位置番号を2進表記したとき第i桁が1である全ビット」のパリティを担当します。

(7,4)ハミング符号: 7ビット中4データ・3検査
  位置 1 2 3 4 5 6 7
       P1 P2 D1 P4 D2 D3 D4
  P1(位置1) = 位置3,5,7 のXOR  (2進下位桁が1)
  P2(位置2) = 位置3,6,7 のXOR  (2進中位桁が1)
  P4(位置4) = 位置5,6,7 のXOR  (2進上位桁が1)

受信側は各検査群のパリティを再計算し、結果を s3 s2 s1 と並べたシンドロームを得ます。シンドロームが0なら誤りなし。0でなければ、その値こそが**化けたビットの位置番号（2進数）**です。

位置5(D2)が反転した場合
  P1群(1,3,5,7)に5が含まれる -> s1 = 1
  P2群(2,3,6,7)に5は無い     -> s2 = 0
  P4群(4,5,6,7)に5が含まれる -> s3 = 1
  シンドローム = 101(2) = 5 -> 位置5を反転して訂正

検査群を「位置番号の各桁」に対応させたからこそ、シンドロームを読むだけで位置が出ます。これがハミング符号の核心で、最小距離は3、1ビット訂正が可能です。検査ビット数 r とデータ長の関係は 2^r >= データ長 + r + 1 を満たす必要があります。

SECDED ─ ECCメモリの実装

ハミング符号単体は1ビット訂正できますが、2ビット誤ると別の有効な符号語に化けて誤訂正します。そこで全体パリティを1本追加し、最小距離を4へ引き上げたのが SECDED（Single Error Correct, Double Error Detect） です。

判定ロジック
  シンドローム=0 かつ 全体パリティ一致  -> 誤りなし
  シンドローム≠0 かつ 全体パリティ不一致 -> 1ビット誤り(位置=シンドローム) 訂正
  シンドローム≠0 かつ 全体パリティ一致  -> 2ビット誤り 検出のみ(訂正不可)

全体パリティは「誤りビット数の偶奇」を、シンドロームは「位置情報」を示します。1ビット誤り（奇数）なら全体パリティが崩れ、2ビット誤り（偶数）なら全体パリティは戻るがシンドロームは非ゼロ——この組み合わせで両者を区別します。

サーバーのECCメモリは64bitデータに8bit検査を足した (72,64) 構成が標準で、64bitワードあたり1ビット訂正・2ビット検出します。さらに堅牢なチップキルは、DRAMチップ1個が丸ごと故障してもリードソロモン系の符号で復元し、メモリ単位の信頼性階層を底上げします。

CRC ─ 多項式剰余によるバースト検出

メモリが「ランダムな単一ビット化け」を相手にするのに対し、伝送路やストレージでは連続した区間がまとめて化けるバースト誤りが支配的です。これに強いのが CRC（Cyclic Redundancy Check） で、ビット列を GF(2)上の多項式とみなして扱います。

GF(2)は0と1だけの体で、加減算はXOR、繰り上がりはありません。kビットのデータを係数列とする多項式 M(x) を考え、あらかじめ決めた 生成多項式 G(x)（次数 r） で割った剰余を検査ビットとします。

送信:
  1. データを r ビット左シフト  ->  M(x) * x^r
  2. それを G(x) で割った剰余 R(x) を求める (XORベースの筆算)
  3. 送出フレーム = M(x)*x^r + R(x)   (剰余を末尾に連結)

受信:
  受け取ったフレームを G(x) で割る
  剰余が 0      -> 誤りなしと判定
  剰余が非ゼロ  -> 誤りあり

送出フレームは構成上 G(x) で割り切れる（剰余0）ように作られています。受信フレームを G(x) で割って剰余が出れば、途中で誤りが入った証拠です。誤りパターンを E(x) とすると、受信は 送出 + E(x)。送出は割り切れるので、検出できないのは E(x) が G(x) の倍数のときだけ——G(x) の選び方が検出力を決めます。

CRCは検出専用で訂正はしません。だからこそ計算が軽く、G(x) による除算はシフトとXORだけのLFSR（線形帰還シフトレジスタ）で高速にハード実装でき、イーサネットフレーム、ストレージのセクタ、PCIeのリンク層など、桁違いのスループットが要る場所に向きます。誤り検出後は再送（ARQ）で回復するのが基本方針です。

まとめ

• 誤り検出訂正は「正しい符号語を最小ハミング距離だけ離して配置する」発想で、距離が検出 d-1・訂正 floor((d-1)/2) を決める。
• パリティは距離2で奇数個の誤りを検出するのみ、ハミング符号はシンドロームに誤り位置を埋め込み1ビットを自動訂正する。
• SECDEDは全体パリティで距離を4へ上げ、サーバーのECC DRAM（72,64構成）で1訂正・2検出を担い、スクラビングで誤りの蓄積を防ぐ。
• CRCはGF(2)上の多項式剰余でバースト誤りを高確率に検出する検出専用符号で、伝送・ストレージの高速経路を守る。

セル側でなぜビットが化けるのかはNANDフラッシュの内部が、誤り訂正が守るメモリ階層全体の設計はキャッシュとDRAMの章が掘り下げます。