講義「情報理論」

第１４回 通信路符号化法(3)

情報理工学部門 情報知識ネットワーク研究室喜田拓也

2019/7/24講義資料演習第2回解答例 http://www-ikn.ist.hokudai.ac.jp/~kida/lecture/IT2019_EX2ans.pdf

一般のハミング符号（おさらい）

検査ビット長𝑚𝑚，符号長𝑛𝑛 = 2𝑚𝑚 − 1，情報ビット数𝑘𝑘 = 2𝑚𝑚 − 1 −𝑚𝑚検査行列の転置𝐇𝐇𝑇𝑇の作成：𝐇𝐇𝑇𝑇の上部𝑘𝑘行には，各行が異なる

ビットパターン𝑃𝑃𝑇𝑇を，下部𝑚𝑚行は𝑚𝑚 × 𝑚𝑚単位行列𝐸𝐸𝑚𝑚を配置する

生成行列を𝐆𝐆 = 𝐸𝐸𝑘𝑘 𝑃𝑃𝑇𝑇 とする

2

検査行列𝐇𝐇𝑇𝑇 =

1 0 11 1 11 1 00 1 11 0 00 1 00 0 1

生成行列 𝐆𝐆 =

1 0 0 0 1 0 10 1 0 0 1 1 10 0 1 0 1 1 00 0 0 1 0 1 1

𝑃𝑃𝑇𝑇をコピー

この部分は固定的

𝑃𝑃𝑇𝑇

𝐸𝐸𝑚𝑚

𝐸𝐸𝑘𝑘

𝒙𝒙 = 𝑥𝑥1, 𝑥𝑥2, … , 𝑥𝑥𝑘𝑘

𝒚𝒚

𝒘𝒘 = 𝑥𝑥1, 𝑥𝑥2, … , 𝑥𝑥𝑘𝑘 , 𝑐𝑐1, 𝑐𝑐2, … , 𝑐𝑐𝑚𝑚 = 𝒙𝒙𝐆𝐆符号化

𝒘𝒘

𝒔𝒔 = 𝒚𝒚𝐇𝐇𝑻𝑻 を計算．もし𝒔𝒔 ≠ 𝟎𝟎かつ𝒔𝒔が𝐇𝐇𝑇𝑇の第𝑖𝑖行目と一致なら，𝑦𝑦𝑖𝑖 = 𝑦𝑦𝑖𝑖 + 1と訂正

復号

𝒚𝒚𝒚訂正済の系列 通信路

情報ビット

𝒙𝒙

最小距離と誤り訂正検出能力（おさらい）

符号Cの最小ハミング距離（最小距離）𝑑𝑑minの定義：

𝑑𝑑min = min𝒖𝒖≠𝒗𝒗; 𝒖𝒖,𝒗𝒗∈C

{𝑑𝑑H 𝒖𝒖,𝒗𝒗 } .

線形符号の最小距離は，符号の最小ハミング重みに一致する．

𝑑𝑑min = min𝒖𝒖≠𝒗𝒗;𝒖𝒖,𝒗𝒗∈C

𝑑𝑑H 𝒖𝒖,𝒗𝒗 = min𝒖𝒖≠𝒗𝒗;𝒖𝒖,𝒗𝒗∈C

𝑤𝑤H(𝒖𝒖－𝒗𝒗) = min𝒘𝒘∈C

𝑤𝑤H(𝒘𝒘) .

ハミング符号の場合

最小距離𝑑𝑑min = 3，誤り訂正能力 𝑡𝑡0 = 1(7,4)ハミング符号の場合，最小距離 𝑑𝑑min＝最小ハミング重み＝3

(9,4)水平垂直パリティ検査符号の場合

最小距離𝑑𝑑min = 4 ，誤り訂正能力 𝑡𝑡0 = 1単一誤り訂正・２重誤り検出符号

3

𝒘𝒘1 𝒘𝒘23

𝒘𝒘1 𝒘𝒘24

定理8.5

今日の内容

8.3 巡回符号

4

２元系列の多項式表現

巡回符号では，系列長 𝑛𝑛の2元系列を，0,1の2値を係数とする

多項式に対応付け，そのような多項式の演算に基づいて符号化

や復号を行う

0,1を成分とする𝑛𝑛次元ベクトル𝒗𝒗 = (𝑣𝑣𝑛𝑛−1, 𝑣𝑣𝑛𝑛−2, ・・・, 𝑣𝑣1, 𝑣𝑣0)を𝐹𝐹 𝑥𝑥 = 𝑣𝑣𝑛𝑛−1𝑥𝑥𝑛𝑛−1 + 𝑣𝑣𝑛𝑛−2𝑥𝑥𝑛𝑛−2 + ⋯+ 𝑣𝑣1𝑥𝑥 + 𝑣𝑣0

で表す．これを2元系列の多項式表現という

符号長𝑛𝑛の符号は，𝑛𝑛 − 1次以下の多項式の集合として表せる

このとき，各符号語に対応する多項式を符号多項式と呼ぶ

5

例8.7） 𝒗𝒗 = (1,0,1,1,0)

𝐹𝐹 𝑥𝑥 = 𝑥𝑥4 + 𝑥𝑥2 + 𝑥𝑥 変数 𝑥𝑥に大きな意味はない単に係数を区別するためのもの

1 ⋅ 𝑥𝑥4 + 0 ⋅ 𝑥𝑥3 + 1 ⋅ 𝑥𝑥2 + 1 ⋅ 𝑥𝑥 + 0

Try 問8.14

２元系列の多項式表現の演算

二つの多項式の加算は，通常の多項式の計算と同様，対応する

次数どうしをそれぞれ加算すればよい．ただし，係数は mod 2 の

計算なので，係数どうしの排他的論理和演算となる

例） 𝑥𝑥4 + 𝑥𝑥2 + 1 + 𝑥𝑥4 + 𝑥𝑥3 + 𝑥𝑥 + 1 = 𝑥𝑥3 + 𝑥𝑥2 + 𝑥𝑥

mod 2の計算では，加算と減算は同じ意味を持つ

例） 𝑥𝑥3 − 𝑥𝑥2 + 1 = 𝑥𝑥3 + 𝑥𝑥2 + 1変数 𝑥𝑥 どうしの乗算は，次数は通常通りに加算される

例） 𝑥𝑥 ⋅ 𝑥𝑥 = 𝑥𝑥2, 𝑥𝑥 + 1 𝑥𝑥 + 1 = 𝑥𝑥2 + 1

多項式を 𝑥𝑥倍すると，係数は１ビット左にシフトする

例） 𝑥𝑥3 + 𝑥𝑥2 + 1 × 𝑥𝑥 = 𝑥𝑥4 + 𝑥𝑥3 + 𝑥𝑥

6Try 問8.15(0,1,1,0,1) (1,1,0,1,0)

（𝑥𝑥 + 𝑥𝑥 = 0に注意）

巡回符号とは？

最大次数𝑚𝑚（𝑚𝑚 > 0）で定数項が 1 の任意の多項式𝐺𝐺(𝑥𝑥)を選ぶ．

𝐺𝐺 𝑥𝑥 = 𝑥𝑥𝑚𝑚 + 𝑔𝑔𝑚𝑚−1𝑥𝑥𝑚𝑚−1 + ⋯+ 𝑔𝑔1𝑥𝑥 + 1 .長さ 𝑛𝑛 (> 𝑚𝑚) のすべての２元系列に対応する 2𝑛𝑛 通りの多項式の

うち，𝐺𝐺(𝑥𝑥) で割り切れる多項式だけをすべて取り出し，それらを符

号語とした符号のことを巡回符号と呼ぶ．検査ビット長は𝑚𝑚, 情報

ビット長は𝑛𝑛 −𝑚𝑚となる．このとき𝐺𝐺(𝑥𝑥)を生成多項式とよぶ．

7

𝑔𝑔1,⋯ ,𝑔𝑔𝑚𝑚−1は0 か 1

定義8.14

巡回符号では，任意の符号語は𝑊𝑊 𝑥𝑥 = 𝑄𝑄 𝑥𝑥 𝐺𝐺 𝑥𝑥 という形の多

項式（符号多項式）に対応づけられる

巡回符号の特徴：• 線形符号である

• 符号長が長くても符号化・シンドローム計算の装置化が比較的容易

• 誤り検出能力に優れる．特にバースト誤りに対する理論的保証がある

𝑄𝑄(𝑥𝑥)は𝑛𝑛 −𝑚𝑚 − 1 次以下の任意の多項式

𝐺𝐺 𝑥𝑥 の符号多項式の例 （例8.9）𝑛𝑛 = 7,𝑚𝑚 = 4 ，次の多項式

𝐺𝐺 𝑥𝑥 = 𝑥𝑥4 + 𝑥𝑥2 + 𝑥𝑥 + 1を生成多項式とする巡回符号の

符号語を求めてみよう．

このとき，𝐺𝐺 𝑥𝑥 により作られる

符号Cの符号多項式は，符号長

が 𝑛𝑛 = 7 なので，

𝑊𝑊 𝑥𝑥 = 𝑤𝑤6𝑥𝑥6 + ⋯+ 𝑤𝑤1𝑥𝑥 + 𝑤𝑤0と書ける．

このうち，𝐺𝐺 𝑥𝑥 で割り切れる多項

式は，𝑄𝑄 𝑥𝑥 から逆算すると，右の

表8.3のとおり．8

𝑄𝑄(𝑥𝑥) 𝑊𝑊 𝑥𝑥 = 𝑄𝑄(𝑥𝑥)𝐺𝐺(𝑥𝑥) 𝒘𝒘0 0 00000001 𝑥𝑥4 + 𝑥𝑥2 + 𝑥𝑥 + 1 0010111

𝑥𝑥 𝑥𝑥5 + 𝑥𝑥3 + 𝑥𝑥2 + 𝑥𝑥 0101110

𝑥𝑥 + 1 𝑥𝑥5 + 𝑥𝑥4 + 𝑥𝑥3 + 1 0111001𝑥𝑥2 𝑥𝑥6 + 𝑥𝑥4 + 𝑥𝑥3 + 𝑥𝑥2 1011100𝑥𝑥2 + 1 𝑥𝑥6 + 𝑥𝑥3 + 𝑥𝑥 + 1 1001011𝑥𝑥2 + 𝑥𝑥 𝑥𝑥6 + 𝑥𝑥5 + 𝑥𝑥4 + 𝑥𝑥 1110010𝑥𝑥2 + 𝑥𝑥 + 1 𝑥𝑥6 + 𝑥𝑥5 + 𝑥𝑥2 + 1 1100101

表8.3. 𝐺𝐺 𝑥𝑥 = 𝑥𝑥4 + 𝑥𝑥2 + 𝑥𝑥 + 1 の倍多項式と対応する符号語

0,1 を係数とする多項式の乗算(a) (b)

𝑥𝑥4 + 𝑥𝑥2 + 𝑥𝑥 + 1 10111×) 𝑥𝑥2 + 𝑥𝑥 + 1 ×) 111

𝑥𝑥4 + 𝑥𝑥2 + 𝑥𝑥 + 1 10111𝑥𝑥5 + 𝑥𝑥3 + 𝑥𝑥2 + 𝑥𝑥 10111

𝑥𝑥6 + 𝑥𝑥4 + 𝑥𝑥3 + 𝑥𝑥2 10111𝑥𝑥6 + 𝑥𝑥5 + 𝑥𝑥2 + 1 1100101

足す項が偶数個だと消える

項は7つ．最大次数は6

巡回符号は線形符号

［証明］任意の二つの符号多項式𝑊𝑊1 𝑥𝑥 と𝑊𝑊2 𝑥𝑥 の和を考える．

いま，𝑊𝑊1 𝑥𝑥 = 𝑄𝑄1 𝑥𝑥 𝐺𝐺 𝑥𝑥 ，

𝑊𝑊2 𝑥𝑥 = 𝑄𝑄2 𝑥𝑥 𝐺𝐺 𝑥𝑥とおくと，

𝑊𝑊1 𝑥𝑥 + 𝑊𝑊2 𝑥𝑥 = 𝑄𝑄1 𝑥𝑥 + 𝑄𝑄2 𝑥𝑥 𝐺𝐺(𝑥𝑥)となるので，これは𝐺𝐺 𝑥𝑥 の倍多項式である．

よって，𝑊𝑊1 𝑥𝑥 + 𝑊𝑊2 𝑥𝑥 も符号多項式となるので，対応する系列も符号語となる．すなわち，任意のふたつの符号語の和が符号語となるので，巡回符号は線形符号である．【証明終】

9

線形符号の必要十分条件

𝐺𝐺 𝑥𝑥 で割れるってこと

巡回符合の符号化方法

𝑛𝑛 −𝑚𝑚個の情報ビット列𝒗𝒗 = (𝑣𝑣𝑛𝑛−𝑚𝑚−1,⋯ , 𝑣𝑣0)を長さ𝑛𝑛の符号語に符号化する．まず，情報ビットを係数とする多項式

𝑉𝑉 𝑥𝑥 = 𝑣𝑣𝑛𝑛−𝑚𝑚−1𝑥𝑥𝑛𝑛−𝑚𝑚−1 + ⋯+ 𝑣𝑣1𝑥𝑥1 + 𝑣𝑣0に 𝑥𝑥𝑚𝑚 を掛け，生成多項式𝐺𝐺 𝑥𝑥 で割る．

𝐺𝐺 𝑥𝑥 の次数は𝑚𝑚なので，剰余多項式を

𝐶𝐶 𝑥𝑥 = 𝑐𝑐𝑚𝑚−1𝑥𝑥𝑚𝑚−1 + ⋯+ 𝑐𝑐1𝑥𝑥 + 𝑐𝑐0とおき，また，𝑄𝑄 𝑥𝑥 を商多項式とすると，

𝑉𝑉 𝑥𝑥 𝑥𝑥𝑚𝑚 = 𝑄𝑄 𝑥𝑥 𝐺𝐺 𝑥𝑥 + 𝐶𝐶 𝑥𝑥 . ・・・(1)ここで，

𝑊𝑊 𝑥𝑥 = 𝑉𝑉 𝑥𝑥 𝑥𝑥𝑚𝑚 + 𝐶𝐶(𝑥𝑥)とおくと，式(1)から𝑊𝑊 𝑥𝑥 = 𝑄𝑄 𝑥𝑥 𝐺𝐺 𝑥𝑥 となる．よって，𝑊𝑊 𝑥𝑥 は符号C の符号多項式となる．𝑊𝑊 𝑥𝑥 をベクトルの形で表すと，𝒘𝒘 = (𝑣𝑣𝑛𝑛−𝑚𝑚−1,⋯ , 𝑣𝑣1, 𝑣𝑣0, 𝑐𝑐𝑚𝑚−1,⋯ , 𝑐𝑐1, 𝑐𝑐0).

10

𝑛𝑛 − 1次

× 𝑥𝑥𝑚𝑚

𝐺𝐺(𝑥𝑥) で割り剰余 𝐶𝐶 𝑥𝑥 を求める

⊕

𝑉𝑉 𝑥𝑥 𝑥𝑥𝑚𝑚

𝑉𝑉(𝑥𝑥) : 情報ビット(𝑣𝑣𝑛𝑛−𝑚𝑚−1,⋯ , 𝑣𝑣0)

符号語𝑊𝑊 𝑥𝑥= 𝑉𝑉 𝑥𝑥 𝑥𝑥𝑚𝑚 + 𝐶𝐶(𝑥𝑥)

𝑉𝑉 𝑥𝑥 𝑥𝑥𝑚𝑚

𝐶𝐶 𝑥𝑥 : 検査ビット(𝑐𝑐𝑚𝑚−1,⋯ , 𝑐𝑐1, 𝑐𝑐0)

𝑚𝑚− 1次

巡回符号の符号化の例（例題8.2）生成多項式が𝐺𝐺 𝑥𝑥 = 𝑥𝑥4 + 𝑥𝑥2 + 𝑥𝑥 + 1，符号長𝑛𝑛 = 7の巡回符号

において，情報ビット 1,1,0 を符号化せよ．

生成多項式は 4次なので，検査ビット数は 4．情報ビットを係数とする多項式は 𝑉𝑉 𝑥𝑥 = 𝑥𝑥2 + 𝑥𝑥で，これに 𝑥𝑥4 を掛けると，𝑉𝑉 𝑥𝑥 𝑥𝑥4 = 𝑥𝑥6 + 𝑥𝑥5 となる．

これを𝐺𝐺 𝑥𝑥 で割ると剰余は𝐶𝐶 𝑥𝑥 = 𝑥𝑥2 + 1 となる．

よって，符号多項式は𝑊𝑊 𝑥𝑥 = 𝑉𝑉 𝑥𝑥 𝑥𝑥4 + 𝐶𝐶 𝑥𝑥 = 𝑥𝑥6 + 𝑥𝑥5 +𝑥𝑥2 + 1 となり，符号語は (1,1,0,0,1,0,1) となる．

11

(a) (b)𝑥𝑥2 + 𝑥𝑥 + 1 111

𝑥𝑥4 + 𝑥𝑥2 + 𝑥𝑥 + 1 ) 𝑥𝑥6 + 𝑥𝑥5 10111 ) 1100000𝑥𝑥6 + 𝑥𝑥4 + 𝑥𝑥3 + 𝑥𝑥2 10111

𝑥𝑥5 + 𝑥𝑥4 + 𝑥𝑥3 + 𝑥𝑥2 11110𝑥𝑥5 + 𝑥𝑥3 + 𝑥𝑥2 + 𝑥𝑥 10111

𝑥𝑥4 + 𝑥𝑥 10010𝑥𝑥4 + 𝑥𝑥2 + 𝑥𝑥 + 1 10111

𝑥𝑥2 + 1 101

表．0,1を係数とする多項式の割り算

Try 練習問題8.2

ちょっと休憩

12

なぜ「巡回」符号と呼ばれるのか？

本来の巡回符号は，多項式 𝑥𝑥𝑛𝑛 − 1 が 𝐺𝐺 𝑥𝑥 で割り切れなければ

ならない．これが成立しないものを擬巡回符号と呼ぶ

𝐺𝐺(𝑥𝑥)で生成される符号は，この条件が成立していなくてもほとんど

同様に扱えるため，擬巡回符号も含めて単に巡回符号と呼ぶ13

定理8.7ある生成多項式𝐺𝐺(𝑥𝑥)から構成した符号長𝑛𝑛の巡回符号において，

多項式𝑥𝑥𝑛𝑛 − 1が𝐺𝐺(𝑥𝑥)で割り切れるとする．このとき，この巡回符号

の任意の符号語

𝒘𝒘 = (𝑤𝑤𝑛𝑛−1,𝑤𝑤𝑛𝑛−2,⋯ ,𝑤𝑤1,𝑤𝑤0)を左に１ビット巡回させた系列

𝒘𝒘′ = (𝑤𝑤𝑛𝑛−2,𝑤𝑤𝑛𝑛−3 ⋯ ,𝑤𝑤0,𝑤𝑤𝑛𝑛−1)もまた，この符号の符号語に含まれている． 【証明は教科書参照】

𝒘𝒘 = (𝑤𝑤𝑛𝑛−1,𝑤𝑤𝑛𝑛−2,𝑤𝑤𝑛𝑛−3,⋯ ,𝑤𝑤1,𝑤𝑤0)

𝒘𝒘′ = (𝑤𝑤𝑛𝑛−2,𝑤𝑤𝑛𝑛−3,⋯ ,𝑤𝑤1,𝑤𝑤0,𝑤𝑤𝑛𝑛−1)

巡回符号の誤り検出・訂正能力

右の表8.3に示した巡回符号

の例では，全ゼロ以外のすべ

ての符号語のハミング重みが

4 であることから，この符号の

最小距離は 4 であることが分

かる

よって，この巡回符号は単一

誤り訂正と2重誤り検出可能

訂正を行わない場合には，

3重誤り検出可能

では，一般の巡回符号はどの

ような誤り検出・訂正能力を

もっているのだろうか？14

𝑄𝑄(𝑥𝑥) 𝑊𝑊 𝑥𝑥 = 𝑄𝑄(𝑥𝑥)𝐺𝐺(𝑥𝑥) 𝒘𝒘0 0 00000001 𝑥𝑥4 + 𝑥𝑥2 + 𝑥𝑥 + 1 0010111

𝑥𝑥 𝑥𝑥5 + 𝑥𝑥3 + 𝑥𝑥2 + 𝑥𝑥 0101110𝑥𝑥 + 1 𝑥𝑥5 + 𝑥𝑥4 + 𝑥𝑥3 + 1 0111001

𝑥𝑥2 𝑥𝑥6 + 𝑥𝑥4 + 𝑥𝑥3 + 𝑥𝑥2 1011100𝑥𝑥2 + 1 𝑥𝑥6 + 𝑥𝑥3 + 𝑥𝑥 + 1 1001011𝑥𝑥2 + 𝑥𝑥 𝑥𝑥6 + 𝑥𝑥5 + 𝑥𝑥4 + 𝑥𝑥 1110010𝑥𝑥2 + 𝑥𝑥 + 1 𝑥𝑥6 + 𝑥𝑥5 + 𝑥𝑥2 + 1 1100101

表8.3. 𝐺𝐺 𝑥𝑥 = 𝑥𝑥4 + 𝑥𝑥2 + 𝑥𝑥 + 1 の倍多項式と対応する符号語

最小ハミング重み = 4 ⇔ 符号の最小距離 = 4

𝒘𝒘1 𝒘𝒘24

生成多項式𝐺𝐺 𝑥𝑥 の周期について

【例8.10】生成多項式 𝐺𝐺 𝑥𝑥 = 𝑥𝑥4 + 𝑥𝑥2 + 𝑥𝑥 + 1 の周期を調べる．

𝐺𝐺 𝑥𝑥 は4次式なので，𝑛𝑛 = 4 以下では明らかに割り切れない．𝑛𝑛 =5, 6 のときを計算すると，

𝑥𝑥5 + 1 = 𝑥𝑥 𝑥𝑥4 + 𝑥𝑥2 + 𝑥𝑥 + 1 + 𝑥𝑥3 + 𝑥𝑥2 + 𝑥𝑥 + 1𝑥𝑥6 + 1 = 𝑥𝑥2 + 1 𝑥𝑥4 + 𝑥𝑥2 + 𝑥𝑥 + 1 + (𝑥𝑥3 + 𝑥𝑥)

となり，やはり割り切れない．しかし，𝑛𝑛 = 7 のときに初めて

𝑥𝑥7 + 1 = (𝑥𝑥3 + 𝑥𝑥 + 1)(𝑥𝑥4 + 𝑥𝑥2 + 𝑥𝑥 + 1)となって割り切れる．よって，この多項式𝐺𝐺(𝑥𝑥)の周期は 7 である．

15Try 問8.17

ある生成多項式𝐺𝐺(𝑥𝑥)が与えられたときに，𝑥𝑥𝑛𝑛 − 1 𝑛𝑛 = 1, 2, 3, …という形の多項式が 𝐺𝐺 𝑥𝑥 で割り切れるかどうかを調べ，これが割り切れるような最小の 𝑛𝑛を，多項式 𝐺𝐺(𝑥𝑥) の周期と呼ぶ．

定義8.15

𝐺𝐺 𝑥𝑥 の周期と符号の最小距離の関係

生成多項式 𝐺𝐺 𝑥𝑥 = 𝑥𝑥4 + 𝑥𝑥2 + 𝑥𝑥 + 1 の周期は 7．したがって，

符号語長 𝑛𝑛を 8 以上にすると，最小距離が 2 となり誤り訂正がで

きない．【例8.10】の例では，符号語長を 7 としており，実際，最小

距離は 4 である．

16

定理8.8符号長 𝑛𝑛 の巡回符号において，𝑛𝑛 より短い周期の生成多項式

𝐺𝐺(𝑥𝑥) を用いると，符号の最小距離が 2 になってしまう．𝐺𝐺 𝑥𝑥 の

周期が 𝑛𝑛以上であれば，最小距離は 3 より小さくならない．

周期𝑝𝑝の生成多項式を選べば，符号長𝑝𝑝までの良い符号が作れる

【証明は教科書参照】

𝐺𝐺 𝑥𝑥 の項数と符号の最小距離の関係

巡回符号では 𝐺𝐺 𝑥𝑥 自体が符号語に含まれることと，𝐺𝐺 1 = 0ならば𝑊𝑊 1 = 𝑄𝑄 1 𝐺𝐺 1 = 0 であることから証明できる．

【例8.11】 先の例では，生成多項式 𝐺𝐺 𝑥𝑥 = 𝑥𝑥4 + 𝑥𝑥2 + 𝑥𝑥 + 1 の

周期は 7 で符号長と同じである．よって，（定理8.7より）符号の

最小距離は 3 以上である．𝐺𝐺 𝑥𝑥 の項数は偶数なので，符号語

のハミング重みは必ず偶数であり，最小距離は 4 以下となる．

しかも 𝐺𝐺 𝑥𝑥 の項数がちょうど 4 であるため，符号の最小距離も

ちょうど 4 となる．17

定理8.9巡回符号において，生成多項式𝐺𝐺 𝑥𝑥 の項数を𝑑𝑑とすると，符号

の最小距離を 𝑑𝑑 より大きくはできない．さらに 𝑑𝑑 が偶数ならば，

すべての符号語のハミング重みは必ず偶数となる．

【証明は教科書参照】

バースト誤りの検出と訂正

ある長さまでのバースト誤りを，すべて訂正（あるいは検出）するよう

な符号をバースト誤り訂正（検出）符号という

ある符号 C が訂正（検出）できる最大のバースト長を，符号 C の

バースト誤り訂正（検出）能力とよぶ

バースト誤り検出能力が 𝑙𝑙0 ⇔任意の符号語𝑤𝑤1に長さ 𝑙𝑙0以下の任意のバースト

誤りパターン𝑒𝑒を加えた𝑤𝑤1 + 𝑒𝑒が，別の符号語𝑤𝑤2にならない

バースト誤り訂正能力が 𝑙𝑙0 ⇔任意の符号語𝑤𝑤1に長さ 𝑙𝑙0以下の任意のバースト

誤りパターン𝑒𝑒1を加えた𝑤𝑤1 + 𝑒𝑒1が，別の符号語𝑤𝑤2に任意の

バースト誤りパターン𝑒𝑒2を加えた𝑤𝑤2 + 𝑒𝑒2と一致しない18

00・・・・・・001＊＊・・・＊100・・・・・・00𝑛𝑛

𝑙𝑙 ギルバートモデルやフリッチマンモデルも含む

長さ 𝑛𝑛のブロック内に１回のバースト誤りがある場合を考える

＊は0,1任意であることを示す

バースト誤りに対する理論的保証

19

定理8.10巡回符号において，生成多項式𝐺𝐺 𝑥𝑥 の次数を𝑚𝑚とする

と，長さ𝑚𝑚の区間内で発生する多重誤りはすべて検出

可能である．

連続して発生する誤りなら，長さ𝑚𝑚までのどんな誤りでも

検出できる！

定理8.10の証明

符号長を𝑛𝑛とする．長さ𝑚𝑚の多重誤りパターンを多項式で表現する

と，ある整数 𝑗𝑗 （0 ≤ 𝑗𝑗かつ 𝑗𝑗 + 𝑚𝑚 < 𝑛𝑛）に対して，

𝐸𝐸(𝑥𝑥) = 𝑥𝑥𝑗𝑗 𝑒𝑒𝑚𝑚−1𝑥𝑥𝑚𝑚−1 + 𝑒𝑒𝑚𝑚−2𝑥𝑥𝑚𝑚−2 + ⋯+ 𝑒𝑒1𝑥𝑥 + 𝑒𝑒0となる．𝑒𝑒𝑖𝑖 ∈ 0,1 は多重誤りパターンを表す係数である．符号語

𝑊𝑊(𝑥𝑥)に対する受信語𝑌𝑌 𝑥𝑥 = 𝑊𝑊 𝑥𝑥 + 𝐸𝐸 𝑥𝑥 が別の符号語になっ

ていなければ誤りを検出できる．すなわち，𝐸𝐸(𝑥𝑥)が𝐺𝐺(𝑥𝑥)で割り切れ

なければよい．𝐺𝐺(𝑥𝑥)は𝑥𝑥を因数として持たないので，𝐸𝐸(𝑥𝑥)が𝐺𝐺(𝑥𝑥)で割り切るのは，二つ目の項である

𝑒𝑒𝑚𝑚−1𝑥𝑥𝑚𝑚−1 + 𝑒𝑒𝑚𝑚−2𝑥𝑥𝑚𝑚−2 + ⋯+ 𝑒𝑒1𝑥𝑥 + 𝑒𝑒0が𝐺𝐺 𝑥𝑥 で割り切れるときのみである．いま，𝐺𝐺(𝑥𝑥)の次数が𝑚𝑚とする

と，この部分は最大次数が𝑚𝑚− 1であるため割り切れることはない．

したがって，𝑌𝑌(𝑥𝑥)は符号語とならないので必ず𝐸𝐸(𝑥𝑥)のような誤りは

検出できる．20

定数項が1だから！

CRC方式

巡回符号による誤り検出方式は，CRC（cyclic redundancy check; 巡回冗長検査）方式と呼ばれ，広く実用に用いられている

CRC方式には，CCITT（国際電信電話諮問委員会）の勧告による

𝐺𝐺 𝑥𝑥 = 𝑥𝑥16 + 𝑥𝑥12 + 𝑥𝑥5 + 1という生成多項式がよく用いられる

この生成多項式の周期は 32767 なので，符号長 32767 以下の符

号の場合，定理8.8と定理8.9より最小距離は 4 となる．したがって，

3 個以下の任意の誤りを検出できる

さらに，定理8.10より，長さ 16 以下の任意のバースト誤りは検出可

能となる．長さ17以上のバースト誤りには検出不可能なものも混じ

るが，その大部分は検出可能であることがわかっている

21

イーサネットの規格でのCRC方式

イーサネットの規格（IEEE802.3）でもCRCが使われている（CRC-32）

イーサネットでは約 500～12000 ビットで１つのパケットを構成し，パケットの末尾に

32 ビットの検査ビットが追加されている

生成多項式は次のとおり．

𝐺𝐺 𝑥𝑥 = 𝑥𝑥32 + 𝑥𝑥26 + 𝑥𝑥23 + 𝑥𝑥22 + 𝑥𝑥16 + 𝑥𝑥12 + 𝑥𝑥11 + 𝑥𝑥10

+𝑥𝑥8 + 𝑥𝑥7 + 𝑥𝑥5 + 𝑥𝑥4 + 𝑥𝑥2 + 𝑥𝑥 + 1 .パケット長の範囲内では符号の最小距離は 4．したがって，任意の３重誤りまでは

すべて検出可能

長さ 32 までの連続区間内で発生した多重誤りを全て検出可能

同じ符号化が，MPEG-2, zlib, PNG などでも利用されている

22

ヘッダー＋データ 検査ビット

480〜12112 bit 32 bit

図8.8 イーサネットのパケット構成

巡回ハミング符号

0,1 を係数とする𝑚𝑚次多項式の周期は，最大2𝑚𝑚 − 1であることが知

られている．この最大周期を持つ多項式を原始多項式といい，各次

数について原始多項式が存在することが証明されている．

𝑚𝑚次の原始多項式を生成多項式とする符号長𝑛𝑛 = 2𝑚𝑚 − 1の巡回

符号を考えよう！

23

次数 原始多項式 次数 原始多項式

1 𝑥𝑥＋1 11 𝑥𝑥11＋𝑥𝑥2＋12 𝑥𝑥2＋𝑥𝑥＋1 12 𝑥𝑥12＋𝑥𝑥6＋𝑥𝑥4＋𝑥𝑥＋13 𝑥𝑥3＋𝑥𝑥＋1 13 𝑥𝑥13＋𝑥𝑥4＋𝑥𝑥3＋𝑥𝑥＋14 𝑥𝑥4＋𝑥𝑥＋1 14 𝑥𝑥14＋𝑥𝑥10＋𝑥𝑥6＋𝑥𝑥＋15 𝑥𝑥5＋𝑥𝑥2＋1 15 𝑥𝑥15＋𝑥𝑥＋16 𝑥𝑥6＋𝑥𝑥＋1 16 𝑥𝑥16＋𝑥𝑥12＋𝑥𝑥3＋𝑥𝑥＋17 𝑥𝑥7＋𝑥𝑥＋1 17 𝑥𝑥17＋𝑥𝑥3＋18 𝑥𝑥8＋𝑥𝑥4＋𝑥𝑥3＋𝑥𝑥2＋1 18 𝑥𝑥18＋𝑥𝑥7＋19 𝑥𝑥9＋𝑥𝑥4＋1 19 𝑥𝑥19＋𝑥𝑥5＋𝑥𝑥2＋𝑥𝑥＋1

10 𝑥𝑥10＋𝑥𝑥3＋1 20 𝑥𝑥20＋𝑥𝑥3＋1

表. 20次までの原始多項式の例符号長が周期と一致するので，この符号の最小距離は3以上．また，ちょうど3になることも簡単に確認できる．この巡回符号は，符号長𝑛𝑛 = 2𝑚𝑚 − 1，情報ビット数2𝑚𝑚 − 1 −𝑚𝑚，検査ビット数𝑚𝑚のハミング符号になることが知られている．このようなハミング符号を巡回ハミング符号と呼ぶ．

今日のまとめ

8.2.6 バースト誤りの検出と訂正

8.3 巡回符号

8.3.1 2元系列の多項式表現

8.3.2 巡回符号の構成法

8.3.4 巡回符号による誤り検出・訂正能力𝐺𝐺 𝑥𝑥 の項数，周期，次数と符号の最小距離の関係

CRC方式

8.3.5 巡回ハミング符号

補足資料：

巡回符号の符号器のための回路構成 (8.3.3節の補足)

24