2026-08-22·無料·13分で読めます

誤り訂正を1から — 壊れる前提で送るという発想

パリティ1ビットから始めて、ハミング距離・シンドローム復号・リード・ソロモンまでを前提知識ゼロで積み上げ、QRコードが汚れても読める理由と、現場でECCを扱う落とし穴までつなげます。

#error-correction #hamming-code #reed-solomon #qr-code #coding-theory

壊れる前提で送る

電話で「サトウです」と名乗って「カトウさんですね」と返された経験は、たぶん誰にでもあります。そこで人は「砂糖の佐に、藤の藤です」と言い直す。伝えたい中身は同じなのに、わざと言葉を増やしている。膨らませた分は無駄ではなく、壊れたときに元を推測するための材料です。

前提を1つひっくり返しておきます。通信路やディスクは「めったに壊れない」のではなく、一定の割合で必ず壊れるものとして扱う。壊れないようにするのではなく、壊れても復元できるようにする——この切り替えが入口です。

この分野はエントロピー符号化を1からとちょうど逆向きの営みでもあります。圧縮は重複という無駄を削り、誤り訂正は役に立つ無駄を計画的に足す。だから実システムでは圧縮してから冗長を足します。順番が逆だと、足した冗長を圧縮器が削り取ってしまいます。

いちばん安い保険 — パリティ1ビット

最小の冗長は1ビットです。1の個数が偶数になるよう末尾に0か1を足す。これがパリティビットで、1011 なら1が3個だからパリティは1、送るのは 10111 です。受信側も1を数え、奇数なら「どこかが壊れた」と分かります。

限界は2つ。どこが壊れたか分からないので直せないこと。そして2ビット同時に反転すると偶奇が元に戻るので、パリティが静かに「無事です」と答えてしまうこと。先へ進むには、冗長を増やすだけでなく足し方を設計する必要があります。

「距離」で考えると全部が見える

見方を変えます。長さ $n$ のビット列を $n$ 次元空間の1点だと思ってください。2点の隔たりを測る物差しがハミング距離です。

d(x, y) = \#\{\, i : x_i \neq y_i \,\}

(1)

$\#\{\,\cdot\,\}$ は「条件に当てはまるものが何個あるか」、 $x_i \neq y_i$ は「 $i$ 桁目が食い違っている」。つまりこの式は、2つのビット列を上下に並べて桁が食い違っている場所の個数を数えただけ、それ以上のことを言っていません。誤りが1ビット起きるとは、この空間を距離1だけ隣に動くこと、と言い換えられます。

符号を作るとは、 $2^n$ 個の点から実際に送ってよい点（符号語）を選ぶことです。質を決めるのが符号語同士の最小距離 $d_{\min}$ 。 $d_{\min}$ 離れていれば $d_{\min}-1$ 個までの誤りは符号語でない点に落ちるので検出でき、そこからいちばん近い符号語へ引き戻せば訂正になります。

t = \left\lfloor \frac{d_{\min} - 1}{2} \right\rfloor

(2)

最小の隔たりから1を引いて半分にした個数だけ直せる、という意味です。 $\lfloor\,\cdot\,\rfloor$ は小数の切り捨て記号なので、半端は安全側に捨てます。つまり、符号語どうしがどれだけ離れているか（ $d_{\min}$ ）さえ決めてしまえば、何ビットまで直せるか（ $t$ ）は自動的に決まる、ということ。各符号語のまわりに半径 $t$ の球を描いたとき、球どうしが重ならないぎりぎりの $t$ がこれ。 $d_{\min}=3$ なら1ビット壊れた点は元から距離1・他からは距離2以上なので一意に直せますが、2ビット壊れると別の符号語に近づく。だから1ビット訂正までです。

もう1つ実務で効く区別があります。誤りは壊れた場所が分からない状態、消失は場所が分かっている状態（ビットが読めず ? になった、何番目のパケットが届かなかった、など）。場所が分かれば値を当てるだけなので、同じ冗長で倍の個数を復元できます。

ハミング符号 — 誤りに住所を答えさせる

1950年、ベル研究所の Richard Hamming は「機械が誤りを検出できるなら、なぜ場所を突き止めて直せないのか」という問いから $d_{\min}=3$ の符号を作りました。有名なのがハミング符号(7,4)、データ4ビットに検査3ビットを足して7ビットで送るものです。

うまいのは検査ビットの置き方です。7つの位置に1〜7の番号を振り、番号を2進数で書いたとき1の位が立つ位置（1,3,5,7）のパリティを1本目、2の位（2,3,6,7）を2本目、4の位（4,5,6,7）を3本目に担当させ、検査ビット自身は 1, 2, 4 に置きます。受信側は同じ3つを計算し直すだけ。まとめて書けば検査行列 $H$ を掛ける操作です。

s = H r^\top \pmod 2

(3)

$r$ は受け取った7ビット、 $H$ は各列がその位置番号の2進表現になっている3行7列の表、 $s$ は3ビットの結果でシンドロームと呼びます。 $\pmod 2$ は「2で割った余り」、要するに1の個数が偶数なら0・奇数なら1という判定です。つまりこの式は「届いた7ビットについて、あらかじめ決めておいた3組のパリティをもう一度計算し直す」以上のことは言っていません。000 なら無事。0でなければ——ここが仕掛けです——その3ビットを2進数として読むと、壊れたビットの位置番号そのものになります。

確かめます。データ 1011 を符号化すると 0110111（位置1から順）。5ビット目が反転して 0110011 が届くと、3つのパリティは 1, 0, 1 で、下位から読んで $1 + 0\times2 + 1\times4 = 5$ 。符号自身が「5番目が壊れている」と答えるので、そこを反転させれば元に戻ります。

これがシンドローム復号です。素朴にやるなら全符号語と距離を比べますが、データが $k$ ビットなら符号語は $2^k$ 個、総当たりは指数的に増える。シンドローム復号は $n-k$ ビットの表を1回引くだけです。

FIG 1総当たり復号は符号語の数だけ距離を比べるので O(2ⁿ) の赤い線に乗る。nを右へ動かすと、対数目盛でも線形目盛でも実用にならないことが見えます。シンドローム復号はこの探索を表引き1回に潰す工夫です

実運用では全体のパリティを1ビット足した拡張ハミング符号が使われます。 $d_{\min}=4$ になり、1ビット訂正・2ビット検出（SECDED）。式(2)で $t=1$ のまま検出だけが強くなる形で、サーバのECCメモリは64ビットに8ビットを足した(72,64)構成が定番です。2ビット誤りを訂正せず検出で止めるのが要点。能力を超えた誤りを無理に直すと別のもっともらしい符号語に化けるので（誤訂正）、「読めません」と言うほうが安全です。

コードで書くハミング(7,4)

復号側は驚くほど短く書けます。

import numpy as np

# 各列が「位置番号の2進表現」になっている検査行列 (3x7)
H = np.array([[1, 0, 1, 0, 1, 0, 1],    # 1の位: 位置 1,3,5,7
              [0, 1, 1, 0, 0, 1, 1],    # 2の位: 位置 2,3,6,7
              [0, 0, 0, 1, 1, 1, 1]])   # 4の位: 位置 4,5,6,7

def decode(r):                          # r: 受け取った7ビットの配列
    s = H @ r % 2                       # シンドローム(3ビット)
    pos = s[0] + 2 * s[1] + 4 * s[2]    # そのまま誤りの位置番号になる
    if pos:
        r = r.copy()
        r[pos - 1] ^= 1                 # 1ビットだけ反転して直す
    return r[[2, 4, 5, 6]]              # データビットを取り出す

% 2 が全体を支配していることに注目してください。誤り訂正は最初から最後まで2を法とする世界（GF(2)）で計算され、足し算も引き算もXOR。繰り上がりがないのでハードウェアではXORゲートの網だけで実装でき、ECCがメモリコントローラの中で1クロック程度の遅延に収まるのはこの単純さのおかげです。

バイト単位で守る — リード・ソロモン

ハミング符号はぽつぽつ独立に反転する誤りには強い一方、現実の壊れ方の多くはバーストです。ディスクの傷、無線のフェージング、QRコードの汚れ——どれも連続した領域をまとめて潰します。7ビット中3ビットが連続で壊れたら、ハミング符号は無力です。

1960年に Irving Reed と Gustave Solomon が発表したリード・ソロモン符号は、ビットではなくシンボル（ふつう1バイト）を単位に扱うことでここを解きます。1バイトの中で1ビット壊れようが8ビット全部壊れようが「1シンボルの誤り」として同じ1枠しか消費しない。バースト誤りが構造的に安く済みます。

RS( $n$ , $k$ ) は $k$ 個のデータシンボルに $n-k$ 個の検査シンボルを足します。原理は多項式で、データを係数とする多項式を $n$ 個の点で評価した値を送る。 $k$ 点あれば多項式は一意に決まるので、余分な $n-k$ 点が壊れた点の特定と修復に使えます。

2t + e \le n - k

(4)

$t$ が場所の分からない誤り、 $e$ が場所の分かっている消失の個数で、誤りは検査シンボルを2枠、消失は1枠だけ消費する、と読みます。つまり、検査シンボル $n-k$ 個を予算とみなし、誤り1個につき2枠・消失1個につき1枠を支払って、予算内に収まっているうちは復元できる、という会計の式です。前節の「場所が分かれば倍直せる」がそのまま式になっています。

NASAの深宇宙通信で長く使われた RS(255,223) は検査32シンボルで、誤りなら16バイト、消失なら32バイトまで復元できます。音楽CDは RS(32,28) と RS(28,24) を交差インターリーブする方式（CIRC）で、傷による連続した欠損を複数ブロックへばらまいてから訂正します。インターリーブは訂正能力を上げる技ではなく、バーストを符号が得意な個別誤りに変換する前処理です。

QRコードはなぜ汚れても読めるのか

身近な実例がQRコードです。中身は GF(256) 上のリード・ソロモン符号で、データをバイト列に直し、検査バイトを付けて白黒のマス目に並べています。訂正レベルは L / M / Q / H の4段階、復元できるコードワードの割合はおおよそ 7% / 15% / 25% / 30%。同じ大きさに入る情報量は決まっているので、レベルを上げるほど入るデータは減ります。

効いているのは符号そのものより配置です。

データと検査バイトは複数ブロックに分けてインターリーブ配置される。一点の汚れが1ブロックを全滅させず、各ブロックを少しずつ削るようにするため
三隅の大きな四角（位置検出パターン）は訂正用ではなく、読み取り機が位置・傾き・大きさを求めるためのもの。ここが潰れると訂正以前に見つけてもらえない
レベルとマスクを示す形式情報は別のBCH符号で守られ、離れた2か所に重複して置かれる
白黒の偏りを避けるため、8種類のマスクパターンから評価値の良いものを選んで全体にXORする

「真ん中にロゴを載せても読める」は、この訂正能力を前借りしているだけです。ロゴで消えたマスは誤りとして訂正され、その分だけ余力が減る。印刷のかすれやブレが加われば合算で閾値を超え、ある日突然読めなくなります。ロゴが位置検出パターンや形式情報にかかっていれば、レベルHでも救えません。

現場ではこう使う

インフラ・ストレージ運用が最初に出会うのはECCメモリです。Linuxでは rasdaemon や edac-util が訂正済み誤り（CE）と訂正不能誤り（UE）を数えており、見るべきはCEの増加率。訂正されているから正常、ではありません。特定のDIMMでCEが増え続けるのはUEに育つ前触れであることが多く、SSDでも smartctl の訂正不能エラー数は寿命の指標になります。

組込み・通信のファームウェア担当は符号の選択そのものを触ります。NANDのコントローラはかつてBCH符号、近年はLDPC符号が主流で、微細化でセルあたりのエラー率が上がるほど強い符号が要求されてきました。5G NRはデータチャネルにLDPC、制御チャネルにpolar符号と、短い制御情報と長いデータで別の符号を使う設計です。

QRを印刷物に載せる担当が触るのはレベルとクワイエットゾーン。Pythonの qrcode なら error_correction=ERROR_CORRECT_H、border（余白のモジュール数、規格上4以上）、box_size で、検証は zbar や zxing で実物をスキャンします。事故で多いのはデザイン都合で border を詰めるケースで、クワイエットゾーンの不足は誤り訂正では一切救えません。符号の外側の問題だからです。

アプリを書く人が押さえるべきは検出と訂正の区別です。CRC32やSHA-256は壊れていることを教えますが直しません。PNGはなぜ劣化しないのかで触れたチャンクごとのCRCも役割は検出だけ。再送できるリンクなら検出＋再送が安上がりで、ライブ配信やCDの読み取りのように送り直せない場面が訂正符号の出番です。

落とし穴は3つ。誤訂正——能力を超えた誤りは低確率ながら別の正しい符号語に化けるので、重要なデータでは訂正符号の外側にCRCを重ねて検算します。冗長は足し算にならない——弱い符号を2回かけても強い符号1回にはならず、インターリーブで壊れ方を整える工程が要ります。符号は誤りの分布の仮定込みの道具——独立誤り前提の符号にバーストを食わせれば、公称の訂正能力は簡単に割り込みます。設計レビューで問われる「 $d_{\min}=3$ がなぜ1ビットしか直せないか」も、式(2)を球の重なりに翻訳できれば答えられます。

まとめ

誤り訂正は「壊れない線を引く」のではなく「壊れる前提で、復元できる冗長を計画的に足す」設計思想
検出も訂正も最小距離という1つの物差しで説明でき、 $d_{\min}$ から $t=\lfloor (d_{\min}-1)/2 \rfloor$ が決まる
ハミング符号は誤りの住所をシンドロームとして答えさせ、総当たり探索を表引き1回に潰す
リード・ソロモンはシンボル単位で扱うためバーストに強く、QRコード・CD・深宇宙通信で使われている
場所の分かっている消失は、場所の分からない誤りの半分のコストで直せる

冗長をどれだけ足せばどれだけの雑音に耐えられるのか、その限界を最初に定めたのはシャノンの通信路容量です。同じ「情報量」という物差しが機械学習の損失関数にどうつながるかは情報理論とAIで扱っています。