巡回冗長検査(CRC)と多項式環の話 (1)

はじめに

この記事は UEC Advent Calendar 2022 その2 の 4 日目の記事です．授業で CRC の計算方法を習って，多項式環の言葉で記述できないかなぁと思って調べてたらいつの間にか符号理論の沼にはまっていました．長いのでパートを分けることにしました．今回は，有限体上の多項式の割り算を用いて CRC を構成し，誤り検出能力を多項式の計算を用いて導出したいと思います．巡回符号とか多項式環の話はパート2に譲りたいと思っています．

巡回冗長検査(CRC)とは

巡回冗長検査(Cyclic Redundancy Check)は，ネットワークなどで使用される誤り検出符号で，特にバースト誤りに強い性質がある．OSI 参照モデルのデータリンク層の実装のひとつである Ethernet では，CRC による誤り検出用の値を格納するフィールドとして Frame Check Sequence (FCS) が規定されている．以下に，Ethernet のフレームフォーマットを示す．

(出典: https://ascii.jp/elem/000/000/427/427324/)

CRC の計算方法

Wikipedia によい説明があるのでそこを参照してほしい．

巡回冗長検査 - Wikipedia

説明を付け足す．CRC では予め送信側と受信側で同じ除数 $(c_m,\,\ldots,\,c_0)$ を共有しておく(これはハードウェアの設計の段階で定められるものなので，共有時にビット誤りが生じることはない)．送信するデータ(符号理論では情報系列などと呼ぶ) $(d_{k-1},\,\ldots,\,d_0)$ が与えられたら，データの最下位ビットに $m$ 個の 0 を付け足して $(d_{k-1},\,\ldots,\,d_0,\,0,\,\ldots,\,0)$ とする．これを Wikipedia に示された手順で各桁に対して排他的論理和(xor)を取る演算を行って，余りを計算する．送信するビット列は，$m$ ビットの余りをデータ $(d_{k-1},\,\ldots,\,d_0)$ の後ろに付したものになる．この余りの部分が Ethernet においては FCS になる．あとで解説するように，余り(FCS)を付け足す作業は，受信側でフレーム全体に同じように除数を使った演算を行ったときに余りが0になるようにするためのものである．受信側でフレーム全体に対して余りを計算して0になるかどうか確かめることで，誤り検出を行う．受信側ではデータと FCS を区別せずに余りを求める演算を行うため，CRC においては FCS にビット誤りが発生しても構わない．実際，データか FCS か区別せずに誤り検出能力を計算する．詳しくは後述する．

有限体

有限体とは位数(元の数)が有限な体のことである．この記事では，位数が $q$ の有限体を $\mathrm{GF}(q)$ と記す．例えば，$\mathbb{Z}/p\mathbb{Z}$ は体を成す．したがって，$\mathrm{GF}(p) = \mathbb{Z}/p\mathbb{Z}$ とすることで，位数が素数の有限体を構成することができる．さらに，このように構成した $\mathrm{GF}(p)$ の1変数多項式環 $\mathrm{GF}(p)[X]$ を，その元である $m$ 次既約多項式 $P(X)$ が生成する単項イデアル

$$(P(X)) = \{\,A(X)P(X)\,|\,A(X) \in \mathrm{GF}(p)[X]\,\}$$

で割って得られる剰余環 $\mathrm{GF}(p)[X]/(P(X))$ は体を成すことが分かる．この体の元 $C(X)$ は

$$C(X) = c_{m-1}X^{m-1} + \cdots + c_1X + c_0\ \ \ (c_{m-1},\,\ldots,\,c_0 \in \mathrm{GF}(p))$$

と表されるから，この体の位数は $p^m$ である．すなわち，位数が $p^m$ の形の有限体は

$$\mathrm{GF}(p^m) = \mathrm{GF}(p)[X]/(P(X))$$

として構築できることがわかる．実は有限体の位数は $p^m$ の形に限られることが分かっている．さらに，位数が等しい有限体は環同型であることが証明されている(すなわち，有限体はその構成方法によらず，同型を除いて一意に定まる)．有限体 $\mathrm{GF}(p^m)$ に対して，$\mathrm{GF}(p)$ はその基礎体と呼ばれる．

CRC と GF(2) 上の多項式

$\mathrm{GF}(2) = \{\,0,\,1\,\}$ の演算は次に示す通りである:

a	b	a+b	a×b
0	0	0	0
0	1	1	0
1	0	1	0
1	1	0	1

ここで，足し算の列に注目すると，排他的論理和(xor)であることに気づくことができる．すなわち，CRC の計算では，各ビットについて，計算機上の 0 を GF(2) の 0 (加法単位元)，計算機上の 1 を GF(2) の 1 (乗法単位元) に対応させて，その GF(2) における足し算を行っていたと記述することができる．上の表にて，$0 + 0 = 0,\,1 + 1 = 0$ より，$0 = -0,\,1 = -1$ が成り立つので，GF(2) およびその拡大体(たとえば，$\mathrm{GF}(2)[X]$)では，一般に元 $x$ に対して $x = -x$ が成り立つことがわかる．したがって，GF(2) およびその拡大体では，足し算と引き算は同じである．

データが $k$ ビットで除数が $m+1$ ビットであるような CRC の計算を考える．データ $(d_{k-1},\,\ldots,\,d_0)$ を GF(2) 上の多項式

$$M(X) = d_{k-1}X^{k-1} + \cdots + d_1X + d_0$$

に対応させ，除数 $(c_m,\,\ldots,\,c_0)$ を

$$G(X) = c_mX^m + \cdots + c_1X + c_0$$

に対応させる．このように対応させると，これらの多項式の各桁は，CRC のアルゴリズムにおいて排他的論理和を用いて上位桁から順に計算され，さらにそれは GF(2) における引き算に対応していたことを考えれば，CRC の計算は，$X^mM(X)$ を $G(X)$ で割ることに他ならないことが分かる．このときの商を $Q(X)$，余りを $R(X)$ とすれば

$$X^mM(X) = Q(X)G(X) + R(X)$$

だが，$R(X) = -R(X)$ であることに注意すれば

$$X^mM(X) + R(X) = Q(X)G(X)$$

である．CRC では左辺をフレームとして送信するが，この式から分かるようにそれは $G(X)$ で割り切ることができる多項式である．受信側では，

$$X^mM(X) + R(X)$$

が $G(X)$ で割り切れるかどうかを調べていると考えることができる．このように，CRC の計算アルゴリズムを GF(2) 上の多項式の割り算として考えることができる(というより，そもそもこの事実を利用して設計されたものだと思われる)．

CRC の誤り検出性能

生成多項式が $m$ 次多項式であり，情報系列の長さが $k$ であるような，CRC を考える．このとき，次が成り立つことを示す:

• 長さが $m$ 以下のバースト誤りはすべて検出できる
• 長さが $m + 1$ のバースト誤りは $1 - 1/2^{m-1}$ の割合で検出できる
• 長さが $m + 2$ 以上のバースト誤りは $1 - 1/2^m$ の割合で検出できる
• 誤りビットが1つしかないとき，必ず検出できる
• 生成多項式が $n$ 次の原始多項式と次数の低い多項式の積からなるとき，2つのビット誤りしか発生しておらず，その間隔が $2^n - 1$ 未満の時は必ず検出できる
• CRC の最小ハミング距離を $d_{\mathrm{min}}$ とすると，$d_{\mathrm{min}} - 1$ 個以下のランダム誤りはすべて検出できる
• 生成多項式が $(X + 1)$ を因数に含むとき，奇数個のビット誤りはすべて検出できる

情報系列 $(d_{k-1},\,\ldots,\,d_0)$ を符号化すると

$$W(X) = X^mM(X) + R(X)$$

となる．これを送信すると，受信側では

$$U(X) = W(X) + E(X)$$

を受信する．ここで，$E(X)$ は誤り多項式と呼ばれ，誤りビットを表す．右から $i$ 番目のビットから $i + l$ 番目のビットまでの長さ $l$ のバースト誤りは

$$E(X) = x^iB(X)$$

と表される．ここで，$B(X)$ はバースト誤りの内容を表しており

$$B(X) = b_{l-1}X^{l-1} + \cdots + b_1X + b_0$$

である．生成多項式 $G(X)$ は $G(0) \neq 0$ を満たすから，$x^i$ は $G(X)$ で割り切れない．したがって，$E(X)$ が割り切れるためには $B(X)$ は $G(X)$ で割り切れなければならない．しかし，$l - 1 < m$ であれば，どんな $B(X)$ も $G(X)$ で割り切れることはない．したがって，$l \leq m$，すなわち長さが生成多項式の次数以下の任意のバースト誤りは検出できることがわかる．

以下の議論の前に，長さが $l$ のバースト誤りは $2^{l-2}$ 個存在していることを述べておこうと思う．バースト誤りは

$$B(X) = b_{l-1}X^{l-1} + \cdots + b_1X + b_0$$

と表されるが，バースト誤りの長さを決めるためには両端のビットは 1 でなければならないから，$b_{l-1} = b_0 = 1$ がわかる．したがって，残りの $l-2$ 個の係数 $b_{l-2},\,\ldots,\,b_1$ の分だけバースト誤りは存在するので，長さ $l$ のバースト誤りは $2^{l-2}$ 個存在していることがわかる．

次に，長さ $l$ が $l = m + 1$ であるバースト誤りを検出できる割合を計算する．このとき，$B(X) = G(X)$ であれば誤り検出エラー(すなわち誤りが発生しているのに，誤りを検出できないこと)が発生する．全体ではバースト誤りは $2^{l-2} = 2^{m-1}$ 個あるのだから，このとき誤り検出エラーが発生する割合は $1/2^{m-1}$ である．したがって，長さ $m+1$ のバースト誤りを $1 - 1/2^{m-1}$ の割合で検出できる．

長さ $l$ が $l > m + 1$ のバースト誤りを検出できる割合を計算する．このとき，定数項が 1 で $l - m - 1 (\geq 1)$ 次多項式 $A(X)$ を用いて，$B(X)$ が

$$B(X) = A(X)G(X)$$

と書ける場合に誤り検出エラーが発生する．ここで，$A(X)$ の定数項が 1 であることは，$B(X)$ の定数項が 1 であることから要求される(バースト誤りの両端のビットは 1 でなければならない)．さらに，$A(X)$ が $l - m - 1$ 次の多項式である，すなわち $A(X)$ の $X^{l-m-1}$ の係数が 1 であることも，$B(X)$ の $X^{l-1}$ の係数が 1 であることから要求される．このとき，$A(X)$ は

$$A(X) = X^{l-m-1} + a_{l-m-2}X^{l-m-2} + \cdots + a_1X + 1$$

と表される．したがって，$2^{l-2}$ 個のバースト誤りのうち $2^{l-m-2}$ 個で誤り検出エラーが発生する．以上のことから，長さが $m+2$ 以上のバースト誤りを検出できる割合は

$$1 - 2^{l-m-2}/2^{l-2} = 1 - 1/2^m$$

となる．

上で見たように，CRC はバースト誤りに強い特性を持っているが，生成多項式と符号長を適切に選べばランダム誤りにも強く設計できることを説明しようと思う．そのためにまず，ハミング距離および最小ハミング距離を定義する．符号語 $\bm{w} = (w_{n-1},\,\ldots,\,w_0)$ および $\bm{u} = (u_{n-1},\,\ldots,\,u_0)$ のハミング距離 $d_{\mathrm{H}}(\bm{w},\,\bm{u})$ は

$$d_{\mathrm{H}}(\bm{w},\,\bm{u}) = \sum_{i=0}^{n-1}d_{\mathrm{H}}(w_i,\,u_i)$$

と定義される．ここで，右辺に現れた $d_{\mathrm{H}}$ は，2つのアルファベット(すなわち，今考えている体の元) $a,\,b$ に対して，$a = b$ のとき $d_{\mathrm{H}}(a,\,b) = 0$，$a \neq b$ のとき $d_{\mathrm{H}}(a,\,b) = 1$ で定められているものである．ハミング距離を分かりやすい言葉で書けば，「先頭から見て同じ位置にあって，かつ異なっているような記号の数」である．また，ハミング距離は次のような性質を持つ．

$$d_{\mathrm{H}}(\bm{u},\,\bm{v}) = d_{\mathrm{H}}(\bm{u} - \bm{v},\,\bm{0})$$

ここで，$\bm{0} = (0,\,\ldots,\,0)$ である．

次に最小ハミング距離を定義する．最小ハミング距離は集合(空間)に対して定義される量で，簡単に言えばその集合から任意の2元を持ってきたときに考えられるハミング距離の最小値である．形式的に定義すると次のようになる．アルファベットとして $\mathrm{GF}(q)$ を取る．$\mathrm{GF}(q)$ の部分集合として符号 $C$ を考えたとき，$C$ の最小ハミング距離 $d_{\mathrm{min}}$ は

$$d_{\mathrm{min}} = \underset{\bm{u},\,\bm{v} \in C}{\mathrm{min}} d_{\mathrm{H}}(\bm{u},\,\bm{v})$$

で定義される．今回は詳しく解説しないが，符号の中でも特に $\mathrm{GF}(q)$ 上の線形空間になっているものを線形符号と呼ぶ．線形符号 $C$ は線形空間なので，$\bm{u},\,\bm{v} \in C$ ならば $\bm{u} - \bm{v} \in C$ が成り立つ．このことを用いると，線形符号 $C$ の最小ハミング距離は

$$d_{\mathrm{min}} = \underset{\bm{u},\,\bm{v} \in C}{\mathrm{min}} d_{\mathrm{H}}(\bm{u},\,\bm{v}) = \underset{\bm{u},\,\bm{v} \in C}{\mathrm{min}} d_{\mathrm{H}}(\bm{u} - \bm{v},\,\bm{0}) = \underset{\bm{w} \in C}{\mathrm{min}}\,d_{\mathrm{H}}(\bm{w},\,0)$$

と変形できる．この変形を使うと理論的に扱いやすくなるだけでなく，コンピュータを使って線形符号の最小ハミング距離を計算するときの計算量を $O(|C|^2)$ から $O(|C|)$ に落とすことができる．線形符号の最小ハミング距離は誤り検出と誤り訂正の両方で重要なので，この計算量の改善は重要である．最後の式に現れる $d_{H}(\bm{w},\,\bm{0})$ は($\bm{w}$ の)ハミング重みと呼ばれるもので

$$w_{\mathrm{H}}(\bm{w}) = d_{\mathrm{H}}(\bm{w},\,\bm{0})$$

と定義される．上で導いた関係式は，線形符号では最小ハミング距離と最小ハミング重みは一致するということ意味である．

話を CRC に戻す．CRC は符号，すなわち $\mathrm{GF}(2)$ の数ベクトル空間の部分集合であり，その符号語全体は $G(X)$ で割り切れる $\mathrm{GF}(2)$ 上の $m+k-1$ 次以下の多項式から成り

$$\{\,U(X)G(X)\,|\,U(X) \in \mathrm{GF}(2)[X],\,\mathrm{deg}(U(X)) \leq k - 1\,\}$$

と書ける．これは明らかに線形符号である．CRC の最小ハミング距離を $d_{\mathrm{min}}$ とすると，$d_{\mathrm{min}} - 1$ 個以下のランダム誤りをすべて検出できることは簡単にわかる．なぜなら，CRC は線形符号であるから最小ハミング重みは最小ハミング距離に等しいので，もし非零な $\mathrm{GF}(2)$ 上の多項式 $W(X)$ が CRC の符号語であるならば，$W(X)$ は少なくとも $d_{\mathrm{min}}$ 個のビットが 1 だからである．これを言い換えれば，高々 $d_{\mathrm{min}} - 1$ 個の 1 を含む符号語($\mathrm{GF}(2)$ 上の多項式)を $G(X)$ で割っても 0 にならないということであり，これは $d_{\mathrm{min}} - 1$ 個以下のビット誤りは必ず検出可能であることを意味する．ちなみに長さが $d_{\mathrm{min}} - 1$ 以下のバースト誤りも上記の理由から必ず検出されるが，バースト誤りに対する特性は上でみたように生成多項式の次数から決まる．なぜなら，生成多項式はそれ自身を割り切ることができるから最小ハミング距離は生成多項式の項の数より大きくならない．実際に CRC で運用される生成多項式は $X^{16} + X^{12} + X^5 + 1$ (CRC-16-CCITT)(4項からなる多項式である) のようなもので，係数が 0 の項が多いので，最小ハミング距離より生成多項式の次数の方がよっぽど大きいことが多いからである．

実は CRC では最小ハミング距離の最小値は 2 になる．最小ハミング距離が 1 となるのは，生成多項式 $G(X)$ が単項式($1,\,X,\,X^2,\,\ldots$)を割り切ることができるということである．ところが生成多項式には $G(0) \neq 0$ が課せられているので，$X,\,X^2,\,\ldots$ は生成多項式では割り切れない．$G(0) \neq 0$ は，$G(X)$ の定数項が 1 であることと同じである．また，1 が $G(X)$ で割り切れるとき，$G(X) = 1$ であるが，これは 0 次多項式であり，このとき CRC は誤り検出能力を持たない．なぜなら，すべての多項式は 1 で割ったとき余りが 0 になってしまうからである．よって，このような生成多項式が採用されることはない．以上の理由から，CRC での最小ハミング距離の最小値は 2 である．これはすなわち，CRC では $2-1=1$ 個のランダム誤りは必ず検出可能であることを意味する．

CRC は符号長 $m+k$ ($m$ は生成多項式の次数，$k$ は情報系列(データ)のビット長)がある程度以上長くなると最小ハミング距離が下限である 2 になってしまい性能が下がることが知られている．実は有限体 $\mathrm{GF}(q)$ 上の $F(0) \neq 0$ を満たす多項式 $F(X)$ に対して，ある自然数 $n$ が存在して

$$F(X)\,|\,X^n - 1$$

が成り立つことが知られている．この式の意味は，$F(X)$ が $X^n - 1$ を割り切ることができるという意味である．このような $n$ のうち最小のものを多項式 $F(X)$ の周期と呼ぶ．CRC の生成多項式の周期が $n$ のとき，符号長を $n+1$ 以上にした場合，受信側では $n$ 次多項式 $X^n - 1 = X^n + 1$ を受け取る可能性がある．これは，ビットパターンとしては，右側(最下位ビット側)から数えて 1 番目と $n+1$ 番目のビットだけが 1 で，その他のビットはすべて 0 というものであるから，$X^n - 1$ (をベクトル表記したもの)と $\bm{0}$ のハミング距離は 2 である．したがって，CRC の符号長を生成多項式の周期より長くしてしまうと最小ハミング距離が 2 になってしまうので，必ず検出できるというランダム誤りは 1 個のランダム誤りまでになってしまう．CRC のランダム誤り検出性能を向上させるには，周期が十分に長く，符号長が周期以下のときの最小ハミング距離が大きくなるような生成多項式を採用すればよい．

生成多項式が $n$ 次の原始多項式と次数の低い多項式との積になるとき，生成多項式の周期は $2^n - 1$ になる．$\mathrm{GF}(q)$ 上の $n$ 次多項式 $F(X)$ が原始多項式であるとは，$F(X)$ の周期が $q^n - 1$ になっているときを言う．次数の低い多項式が生成多項式の因数に含まれていても，その周期は無視される(厳密には，少し式をいじってから最小公倍数を取る)ので，この場合生成多項式の周期も $2^n - 1$ になる．2つのビット誤りが右端から数えて $i$ ビット目と $j$ ビット目に発生したとする．このとき誤り多項式は $X^{i+1}(X^{j-i} + 1)$ となる．誤り多項式が割り切れるためには $X^{j-i} + 1 = X^{j-i} - 1$ が生成多項式で割り切れなければならないが，そのためには $j-i \geq 2^n - 1$ である必要がある．したがって，間隔が $2^n - 1$ 未満の2つのビット誤りは必ず検出できる．

最後に生成多項式が $(X + 1)$ を因数に含んでいれば，奇数個のビット誤りはすべて検出できることを示したいと思う．奇数個のビット誤りの誤り多項式 $E(X)$ は，奇数個の項からなる多項式になる．したがって，$E(1) \neq 0$ となる(GF(2) では 1 + 1 = 0 であることを思い出してほしい)．一方，$E(X)$ が $(X + 1)$ で割り切れるのであれば，$E(1) = 0$ となるはずである．以上のことより，$E(X)$ は $(X + 1)$ で割り切ることはできない．また，$E(X)$ が生成多項式で割り切れるとしたら，$(X + 1)$ でも割り切れるはずだが，実際には $(X + 1)$ で割り切ることはできないので，$E(X)$ は生成多項式で割り切ることはできない．したがって，生成多項式が $(X + 1)$ を因数に持つときは，奇数個のビット誤りは必ず検出できる．

有限体の表現（おまけ）

原始多項式は有限体の表現において重要である．有限体の導入で，$\mathrm{GF}(p)$ 上の $m$ 次既約多項式を使って

$$\mathrm{GF}(p^m) = \mathrm{GF}(q)[X]/(P(X))$$

として拡大体を定義した．有限体の元は $X$ とか $X + 1$ のようなものであるが，この $X$ は，演算として常に $P(X)$ で割った剰余を取るという，$\mathrm{GF}(q)[X]$ の $X$ とは異なるものなので(厳密には剰余類であるから，$X$ ではなく $[X]$ として表記するべきであるといったようなことだと思う)，$\mathrm{GF}(q)[X]$ から $\mathrm{GF}(q)[X]/(P(X))$ への自然な全射を $\pi$ として，$\alpha = π(X)$ なる $\alpha$ を導入し，有限体の元を $\alpha$ の式で表すことにする．拡大体 $\mathrm{GF}(p^m)$ は $\mathrm{GF}(p)$ 上の $m$ 次既約多項式を使って構成できるが，特に周期が $q^m - 1$ となる既約多項式，すなわち原始多項式を使って構成することを考える．原始多項式を使って構成した体で元 $\alpha = \pi(X)$ を考えて，続けて $\alpha^2,\,\alpha^3,\,\ldots$ という元を考えてみる．このとき，$\alpha^e = 1$ となってしまう最小の $e$ を元 $\alpha$ の位数と呼ぶ(今は $\alpha = \pi(X)$ を考えているが，位数は $\mathrm{GF}(p^m)$ の元に対して一般に定義される．位数が $p^m - 1$ となる元を特に原始元と呼ぶ)．実は，拡大体 $\mathrm{GF}(p^m)$ を原始多項式によって生成しているときは，$\alpha = \pi(X)$ の位数は $p^m - 1$ となる．実際，$\mathrm{GF}(p^m)$ 上の式としての $\alpha^e = 1$ は，$\mathrm{GF}(p)[X]$ 上での式 $P(X)\,|\,X^e - 1$ と同値であることは少し考えればわかる．このような $e$ の最小値は，$P(X)$ が原始多項式であれば $p^m - 1$ であった．すなわち，原始多項式を使って有限体を生成すれば，有限体は

$$\mathrm{GF}(p^m) = \{\,0,\,1,\,\alpha,\,\alpha^2,\,\ldots,\,\alpha^{p^m - 2}\}$$

として書き表すことができる．これは有限体のベキ表現と呼ばれる．一般にベキ表現は有限体の原始元を使って得ることができる．ここで述べたことは，原始多項式を使って構成した有限体では，$\alpha = \pi(X)$ が原始元になるということである．

参考文献

• 巡回冗長検査 - Wikipedia
• 有限体 - Wikipedia
• 原始多項式 - Wikipedia
• 今井秀樹（1990）『符号理論』電子情報通信学会
• 平林隆一（2006）『工学基礎 代数系とその応用』数理工学社

さいごに

環論や体論についてまともな知識がなく，数学的な部分については mapsto 氏をはじめとする Twitter のフォロワーのみなさんに非常に助けられましたので，謝辞を述べさせていただくことにいたします．