CRC — 「訂正しない」誤り検出符号という発想

この回で学ぶこと

リード・ソロモン符号の回では、有限体 $GF(2^m)$ 上のシンボルという単位を導入し、バースト誤りに強い誤り訂正符号(FEC: Forward Error Correction)の代数的な構成を見ました。それ以前に扱ってきた畳み込み符号も含め、この講座でこれまで登場した符号はすべて「送られてきたデータの中に誤りがあっても、受信側だけの情報でその誤りを推定し、正しいデータに復元する」という訂正を目的とした符号でした。

この回で扱う CRC(Cyclic Redundancy Check、巡回冗長検査) は、目的からして根本的に異なります。CRCは誤りがあるかどうかを検出するだけで、誤りを直すことは一切しません。「どのビットが化けたか」も「元の値が何だったか」も分かりません。分かるのは「このデータ、送信時から一致していますか?」という、はい/いいえの1ビットの答えだけです。

一見、これは機能として劣っているように見えます。実際、訂正できるならそのほうが望ましいはずです。しかし、CRCには訂正符号にはない決定的な利点があります。それは、同じ検査能力を、桁違いに少ない冗長ビットと、桁違いに軽い計算量で実現できることです。この回では、なぜ「多項式の割り算の余り」というシンプルな操作だけで、実用上十分な誤り検出能力が得られるのかを、$GF(2)$上の多項式演算から数式で追い、CCSDSのTMフレームで実際にCRCがどう使われているかを見ていきます。

直感的な導入: 「検出専用」符号という発想の転換

まず、なぜ「検出だけ」で十分な場面があるのかを考えましょう。深宇宙リンクの誤り訂正は、畳み込み符号やリード・ソロモン符号を連接符号として組み合わせるなど、非常に強力な訂正能力を持つように設計されています。しかし、どれほど強力なFECでも、訂正能力には必ず上限があります。$t$ 個までのシンボル誤りは直せても、$t+1$個目の誤りが来た瞬間、訂正は失敗します。

問題は、訂正に失敗したとき、受信機はその失敗に気づけるとは限らないことです。FEC復号器は「もっともらしい」符号語を出力しますが、それが本当に送信されたものと一致するかどうかを、復号器自身が保証してくれるわけではありません(誤り訂正能力を超える誤りパターンによっては、別の妥当な符号語に誤って収束してしまうことすらあります)。データが壊れているのに、壊れていないふりをして後段の処理(コマンド実行、科学データの記録)に渡ってしまうのは、探査機の運用にとって最も避けたい事態の1つです。

そこで登場するのがCRCです。CRCはFECの最後の砦として、FEC復号が終わったあとのデータに対して「これは本当に正しいか」を独立にチェックする役割を担います。訂正はできませんが、その代わり非常に軽量(数百ビットのフレームに対してわずか16〜32ビットの冗長データ)かつ高感度(バースト誤りをほぼ確実に検出)であり、「怪しいデータを黙って通過させない」という最終防衛ラインとして機能します。この回では、まずCRCの数学的な仕組みを見たあとで、この「FECとCRCの二段構え」という設計思想を、CCSDSの実例で確認します。

数式定式化: データを多項式とみなす

CRCの核心的なアイデアは、リード・ソロモン符号と同じく「ビット列を多項式として扱う」という発想です。ただし今回の係数体は $GF(2^m)$ ではなく、最も単純な $GF(2) = \{0, 1\}$ です。

送信したい $k$ ビットのデータ列 $d_{k-1}, d_{k-2}, \dots, d_1, d_0 \in \{0,1\}$ を、次数 $k-1$以下の多項式として表します。

$$D(x) = d_{k-1}x^{k-1} + d_{k-2}x^{k-2} + \cdots + d_1 x + d_0$$

この多項式の係数の足し算・掛け算は、すべて $GF(2)$ 上、すなわち $\mathrm{mod}\ 2$ で行います。$GF(2)$上では加算と減算が一致する($1+1=0$、$1-1=0$)ため、実装上はビットごとのXOR演算がそのまま多項式の加減算に対応します。これがCRCがハードウェア・ソフトウェアともに極めて軽量に実装できる理由の1つです。

次に、あらかじめ送信側・受信側の双方が合意しておく、次数 $r$ の固定多項式 $g(x)$ を用意します。

$$g(x) = x^r + g_{r-1}x^{r-1} + \cdots + g_1 x + 1$$

これを**生成多項式(generator polynomial)**と呼びます。最高次の係数と定数項が常に $1$ であることに意味があり、これは後述する検出能力の条件から要請されます。

チェックサムの計算

CRCの符号化は、次の3ステップで進みます。

ステップ1: データ多項式 $D(x)$ を $x^r$ 倍し、末尾に $r$ ビット分の「空き」(ゼロで埋めた場所)を作ります。

$$D(x) \cdot x^r$$

これはビット列で言えば、$D$ の末尾に $r$ 個のゼロを付け足す操作に対応します。

ステップ2: この $D(x)\cdot x^r$ を生成多項式 $g(x)$ で($GF(2)$上の多項式除算として)割り、余り $R(x)$ を求めます。

$$D(x) \cdot x^r = Q(x)\, g(x) + R(x), \qquad \deg R(x) < r$$

商 $Q(x)$ は捨て、余り $R(x)$ だけを使います。$R(x)$ は次数が $r$ 未満なので、係数はちょうど $r$ ビットに収まります。この $R(x)$ の係数列が**チェックサム(CRC値)**です。

ステップ3: 元のデータ $D(x)\cdot x^r$ の末尾のゼロ埋め部分を、計算した余り $R(x)$ で置き換えて送信符号語 $C(x)$ とします。

$$C(x) = D(x)\cdot x^r - R(x) = D(x)\cdot x^r + R(x)$$

(繰り返しになりますが $GF(2)$上では $-R(x) = +R(x)$ です。)ここで重要な性質が成り立ちます。式変形すると

$$C(x) = Q(x)\,g(x) + R(x) + R(x) = Q(x)\,g(x)$$

すなわち、送信符号語 $C(x)$ は必ず生成多項式 $g(x)$ で割り切れるように構成されています。この「割り切れる」という性質こそが、CRCのすべての検出ロジックの土台になります。

受信側での検証

受信機は、届いた符号語(データ部分+チェックサム部分)を1つのビット列 $C'(x)$ として受け取り、これを同じ生成多項式 $g(x)$ で割ります。

$$C'(x) = Q'(x)\, g(x) + R'(x)$$

伝送路で誤りが一切なければ $C'(x) = C(x)$ であり、$C(x)$ は $g(x)$ で割り切れることが構成上分かっているので、余りは必ずゼロになります。

$$C'(x) \bmod g(x) = 0 \quad (\text{誤りなしの場合})$$

逆に、伝送路で何らかの誤りが起きた場合を考えます。誤りパターンを多項式 $E(x)$ とすると(誤りが起きたビット位置に対応する係数が $1$、それ以外が $0$)、受信語は

$$C'(x) = C(x) + E(x)$$

と書けます。これを $g(x)$ で割った余りは、多項式の除算が線形演算であることから

$$C'(x) \bmod g(x) = \big[C(x) + E(x)\big] \bmod g(x) = \underbrace{C(x)\bmod g(x)}_{=0} + E(x)\bmod g(x) = E(x) \bmod g(x)$$

となります。つまり、受信語を$g(x)$で割った余りは、誤りパターン $E(x)$ そのものを $g(x)$ で割った余りと完全に一致するという美しい関係が得られます。判定ロジックはこれで尽きています。

$$E(x) \bmod g(x) = 0 \;\Longrightarrow\; \text{余りゼロ(誤りなし、または検出不能な誤り)}$$ $$E(x) \bmod g(x) \ne 0 \;\Longrightarrow\; \text{余りが非ゼロ(誤りを検出)}$$

ここで重要な注意点があります。「余りがゼロ」だからといって、必ずしも誤りが本当にゼロだとは限りません。$E(x) \ne 0$ であっても、たまたま $E(x)$ が $g(x)$ の倍数であれば、余りはゼロになってしまい、誤りを見逃すことになります。CRCの設計とは、実質的に「$g(x)$ の倍数になりにくい、かつ実際に起こりやすい誤りパターン $E(x)$ を、できるだけ広くカバーできるような $g(x)$ を選ぶ」問題に帰着します。次節でこれを具体的に見ていきます。

なぜ「割り算の余り」がバースト誤り検出に強いのか

1ビット誤りの検出

まず最も単純な誤り、1ビットだけが反転するケース $E(x) = x^i$($i$ビット目だけが誤り)を考えます。生成多項式 $g(x)$ の定数項が $1$(すなわち $g(0)\ne 0$、$x$ を因数に持たない)という条件を課しておけば、$x^i$ が $g(x)$ で割り切れることはありません($g(x)$ が2項以上の多項式である限り、単項式 $x^i$ の倍数にしかなりえないからです)。したがって、次数1以上の任意の生成多項式は、単独の1ビット誤りを必ず検出できます。これが $g(x)$ の定数項を $1$ に固定しておく理由です。

バースト誤りの検出

CRCが実務で高く評価される最大の理由が、このバースト誤り検出能力です。長さ $b$ ビットのバースト誤りとは、誤りが発生した最初のビットから最後のビットまでの区間の長さが $b$ ビットである誤りパターンを指します(区間の内部は0でも1でも構いません)。これは多項式で書くと

$$E(x) = x^{j}\big(x^{b-1} + e_{b-2}x^{b-2} + \cdots + e_1 x + 1\big), \qquad e_i \in \{0,1\}$$

の形になります(先頭ビットと末尾ビットが必ず誤り、つまり係数 $1$)。ここで $x^j$ の因数は、$g(x)$ の定数項が $1$ であることから前節と同様に無害化できるので、本質的なのは括弧の中、次数 $b-1$ の多項式 $B(x)$ の部分です。

もし生成多項式の次数が $r \ge b$ ならば、$\deg B(x) = b-1 < r = \deg g(x)$ であり、$B(x)$ は非ゼロである限り $g(x)$ で割り切れません(次数がより低い非零多項式が、次数がより高い多項式の倍数になることはあり得ないからです)。したがって、

$$r \ge b \quad \Longrightarrow \quad \text{長さ } b \text{ 以下のバースト誤りは100\%検出できる}$$

という、非常に強い保証が導けます。つまり、生成多項式の次数 $r$ こそが、そのCRCが「完全に検出できるバースト誤りの長さ」の上限を決めているわけです。$r=16$ のCRC-16なら、長さ16ビット以下のバースト誤りを見逃す確率はゼロです。これがランダムな1ビット誤りをポツポツ数える畳み込み符号的な発想とはまったく違う、「連続した区間をまるごと1つの多項式の余りとして畳み込む」ことによる強みであり、フェーディングや瞬間的な障害で誤りが固まって発生しやすい通信路の性質と相性が良い理由です。

さらに、長さが $r$ を超えるバースト誤りについても、$B(x)$ がランダムなビット列だと仮定すれば、それが偶然 $g(x)$ の倍数になってしまう(見逃してしまう)確率はおおよそ $2^{-r}$ 程度に収まることが知られています。次数 $r$ を上げるほど、この見逃し確率は指数的に小さくなります。

多重誤りとの相性

もう1つ実務上重要なのが、複数個所に散らばった誤り(2ビット誤りなど)の検出です。$g(x)$ として、次数 $r$ の原始多項式を選ぶと($GF(2^r)$ を構成する既約多項式のうち、非零元が位数 $2^r-1$ の巡回群を全て生成するもの)、$g(x)$ が割り切る最小の $x^n+1$ の $n$(これを $g(x)$ の周期と呼びます)が $2^r - 1$ となり、フレーム長がこの周期以下である限り、任意の2ビット誤り(2つの誤りビットがどれだけ離れていても)を確実に検出できることが保証されます。CRC-16やCRC-32で使われる生成多項式の多くは、この原始性や既約因子の性質を考慮して選定されています。

CRC-16, CRC-32 とビット長の選び方

これまで生成多項式の次数 $r$ を一般的な記号として扱ってきましたが、実務では $r$ の値によっていくつかの標準的なバリエーションが使われています。

• CRC-16: $r=16$。チェックサムは16ビット(2オクテット)。よく使われる生成多項式の1つが $g(x) = x^{16}+x^{12}+x^5+1$(CRC-CCITT、後述のCCSDS FECFがまさにこれです)。16ビット以下のバーストを完全検出でき、フレーム長が数百〜数千ビット程度の通信プロトコルで広く採用されています。
• CRC-32: $r=32$。イーサネット、ZIP、PNGファイルなど、より大きなデータブロック(数キロバイト〜)に対して使われます。見逃し確率がおよそ $2^{-32}$ と極めて小さく、32ビット以下のバーストを完全検出します。
• CRC-8, CRC-24 など: 短いパケットや、逆に非常に高い信頼性が要求される特定用途(CRC-24はOpenPGPやブルートゥースLEなど)で使われる中間的な選択肢です。

ビット長 $r$ の選定は、基本的に次のトレードオフです。

$$\text{オーバーヘッド比} = \frac{r}{k+r} \qquad (k: \text{データ長})$$

$r$ を大きくすれば見逃し確率が指数的に下がり、より長いバーストも完全検出できるようになりますが、その分だけ伝送するたびに余分なビットを常に付け加えることになり、オーバーヘッドが増えます。フレーム長 $k$ が大きいプロトコルでは $r=16$ でもオーバーヘッド比は無視できるほど小さくなりますが、フレーム自体が短い(あるいは検出したい誤りパターンの空間が広い、パケット数が膨大で見逃し確率をさらに下げたい)場合には $r=32$ が選ばれます。CCSDSのTMフレームのように、フレーム長が数千ビットで、かつFEC復号後の残留誤りという既に確率の低い事象を検出すれば十分な用途では、CRC-16で実務上十分なバランスが取れる、という設計判断がなされています。

実務での使われ方

CCSDS TMフレームのFECF = CRC-16

宇宙データリンクプロトコルの回で、CCSDSのTMトランスファフレームの末尾に付与される FECF (Frame Error Control Field) に軽く触れました。これはまさにこの回で導出したCRCそのものです。CCSDS 132.0-B (TM Space Data Link Protocol) の規定では、FECFは2オクテット(16ビット)で、生成多項式

$$g(x) = x^{16}+x^{12}+x^5+1$$

によるCRC-16(CRC-CCITTとして知られる多項式と同じもの)です。この $g(x)$ は、プライマリヘッダからトランスファフレームデータフィールド、(存在すれば)OCFまでを含めたフレーム全体(FECF自身を除く)に対して適用され、計算されたチェックサムがフレーム末尾に付加されます。地上局側の受信機は、フレーム全体(FECFを含む)を同じ $g(x)$ で割り、余りが規定値(通常ゼロ)であればフレームを正常と判定し、非ゼロであればそのフレームを破棄(または再送要求などの上位プロトコルに委ねる)します。

FECとCRCの二段構え

ここでこの回の冒頭の議論に戻りましょう。CCSDSのダウンリンクでは、TMフレームは通常、畳み込み符号やリード・ソロモン符号、あるいはそれらの連接符号、さらにはLDPC符号やターボ符号といった強力なFECによって、ビット誤り率が大幅に改善された状態でフレームが再構成されます。しかし、これらのFECにも訂正能力の上限があり、リンクマージンが想定より悪化した瞬間や、まれに発生する復号器の誤収束によって、FEC復号後にも訂正しきれなかった誤り(残留誤り)が紛れ込む可能性がゼロではありません。

FECF(CRC-16)は、この「FECをすり抜けてきたかもしれない残留誤り」を検出するための、パイプラインの最終防衛ラインとして機能します。CRCはFECのように誤りを直すことはできませんが、その代わり計算量がごくわずかで済み、フレーム全体に対して常にかけ続けても運用上の負荷になりません。もしFECFの検証に失敗すれば、そのフレームは「中身が保証できない」ものとして丸ごと破棄され、後段のパケット処理やコマンド実行には一切渡されません。

この設計思想は次のように整理できます。

1. FEC(畳み込み符号・RS符号・LDPC符号など): できる限り多くの誤りを実際に訂正し、伝送効率を最大化する。ただし訂正能力を超える誤りには対処できず、しかも失敗に気づけないことがある。
2. CRC(FECF): 訂正はしないが、FEC通過後のデータが本当に正しいかを軽量かつ高感度に検証し、怪しいデータが後段に紛れ込むのを防ぐ「見張り役」。

「できるだけ直す」FECと「直せなかったものを確実に弾く」CRCを直列に重ねることで、探査機の運用チームは「届いたテレメトリ・実行されたコマンドは、統計的にきわめて高い信頼度で正しい」という保証を手にすることができます。この二段構えの設計思想は、CCSDSのTMフレームに限らず、ファイルシステム、ネットワークプロトコル(イーサネットフレームのFCS、TCPのチェックサムなど)、ストレージデバイスなど、あらゆる高信頼性が要求されるデジタルシステムに共通する、極めて基本的かつ強力なパターンです。

演習問題

1. データ $D = 1101$(多項式 $D(x) = x^3+x^2+1$)を、生成多項式 $g(x) = x^3+x+1$(4ビット表現で $1011$)でCRC符号化してください。$D(x)\cdot x^3$ を $g(x)$ で($GF(2)$上のXORを使った筆算で)割り、余り $R(x)$ を求め、送信符号語 $C(x)$ のビット列を書いてください。
2. 上の問題で得た符号語 $C(x)$ の最下位ビットを1つだけ反転させた受信語 $C'(x)$ を作り、これを同じ $g(x)$ で割って余りが非ゼロになる(誤りが検出される)ことを確認してください。
3. 生成多項式の次数が $r$ のとき、「長さ $r$ 以下のバースト誤りを100%検出できる」理由を、本文中の $E(x) = x^j B(x)$($\deg B(x) = b-1$)という表現と、多項式の次数の比較を使って自分の言葉で説明してください。
4. CCSDSのTMフレームでは、なぜ強力なFEC(畳み込み符号やRS符号)を使っているにもかかわらず、さらにCRC-16(FECF)を末尾に付加しているのか。「訂正」と「検出」という2つの符号の役割の違いを踏まえて、この回で学んだ内容をもとに説明してください。

まとめと次回予告

この回では、これまで扱ってきたリード・ソロモン符号や畳み込み符号のような「誤りを訂正する」符号とは根本的に目的が異なる、「誤りの有無だけを検出する」符号としてCRCを導入しました。データを $GF(2)$上の多項式とみなし、生成多項式 $g(x)$ による多項式除算の余りをチェックサムとして付加することで、符号語全体が必ず $g(x)$ で割り切れるように構成する仕組みを見ました。受信側では同じ除算を行い、余りが非ゼロなら誤りありと判定でき、この判定ロジックは受信語 $C'(x)$ の余りが誤りパターン $E(x)$ の余りと完全に一致するという性質から導かれることを確認しました。また、生成多項式の次数 $r$ が「完全に検出できるバースト誤りの長さ」を直接決めるという関係から、CRC-16・CRC-32といったビット長の選び方が、検出能力とオーバーヘッドのトレードオフとして決まることも見ました。最後に、CCSDS TMフレームのFECFがまさにCRC-16($x^{16}+x^{12}+x^5+1$)であり、強力なFECの後段に置かれる「最終防衛ライン」として機能する二段構えの設計思想を確認しました。

次回は、この「検出専用」のCRCから少し視点を戻し、比較的単純な代数構造で誤り訂正までこなせる古典的な符号であるハミング符号・ゴレイ符号に軽く触れます。CRCの検出だけの仕組みと、リード・ソロモン符号の本格的な多シンボル訂正の中間に位置する、小さな訂正能力を持つ符号がどのような数学的背景を持つのかを見ていきます。

参考文献

• CCSDS 132.0-B, TM Space Data Link Protocol
• CCSDS 131.0-B, TM Synchronization and Channel Coding
• W. W. Peterson, D. T. Brown, “Cyclic Codes for Error Detection,” Proceedings of the IRE, vol. 49, no. 1, 1961
• R. E. Blahut, Theory and Practice of Error Control Codes, Addison-Wesley
• S. Lin, D. J. Costello, Error Control Coding, 2nd ed., Prentice Hall