DeBruijn 系列から作られる多項式について
松木

1

みなみ(指導教員：萩田真理子)

はじめにDefinition 5 (error-correcting sequence) X 上の (N, k, d)error-correcting sequcnce(ECS) とは，周期 N の数列
a0 a1 a2 · · · aN −1
ai = aN +i , aj ∈ Xであり，どの連続する k 個も異なり，最小距離k−1∑
δ(ai+s , ai+t ) ただし
d :=min0≤s<t≤N −1i=0{1 (x 6= y)δ(x, y) =0 (x = y)の error-correcting code をなすものをいう.

ストリーム暗号の多くは、鍵から生成した擬似乱数列と平文を XOR して暗号化され、復号時には再び暗号文と擬似乱数列を XOR する。このとき、暗号化した時と同じ位置で XOR しなければならないため、送信者と受信者の間で同期を取る必要がある。そのため、送信者が周期的な数列を単位時間に１ビットずつ送り続けたとき、受信者の側で受け取った数列の一部分を見れば、たとえそれが誤りを含む列でも、それを訂正して相手の送った数列を知り、同期を取ることができる誤り訂正符号系列が必要とされている。このような誤り訂正符号系列は、F2 上では DeBruijn 系列、Fq (q ≥ 3)
上では Projective DeBruijn 系列を係数に持つ原始多項式が存在すれば、これを用いて m 系列を作ると性質の良いものが得られる。本研究では F2 上の４次以下の多項式から作られる行列が何行まで行を増やせばどの２列も独立になるか確認した。どの２列も独立になるように増やす行数が少なくて済む多項式からｍ系列を生成すると効率良く誤り訂正できる符号が得られるためである。多項式によって必要な行数にどの程度差があるのか調べた。

2例：m 系列は，周期 q n − 1 で，連続する n 個を見たときの最小距離が 1 であるから，(q n − 1, n, 1)ECS である.

3DeBruijn 系列

２章より，e 個の誤り訂正をするための最小距離 dは d ≥ 2e + 1 であることから，１個の誤りを訂正するには d は３以上でなくてはならないことが分かる. しかしｍ系列は (q n − 1, n, 1)ECS，すなわち d = 1 であるため，誤りを訂正することができない.
そこで，d ≥ 3 とするため，(q n − 1, n + s, d)ECS とし，d を大きくするために，見る範囲を +s だけ拡張し，ｍ系列に現れる連続する n + s 個を見る. これは誤り訂正符号とｍ系列

Definition 1 (ハミング距離) F n の任意の２つの元
x = (x1 , · · · , xn ) と y = (y1 , · · · , yn ) に対して，xi 6=yi である座標 i の数を x と y のハミング距離といい，d(x,y) と書く.

Definition 2 (最小距離)
C(⊂ F n ) を符号とす
る.C の任意の 2 つの符号語のハミング距離の最小値a0
 0A=


a1a0···a1..
.

an−1···..
.

an−1..
.

0···0a0a1101·········

an−1

0
0 1を s × (n + s) の行列とすると，Ax = 0 を満たす，全て０以外のベクトルxの全体である.d ≥ 3 にするためには，行列 A のどの２つの列も線型独立でなくてはな
qs − 1らない. 線型独立な列の個数は高々個であるかq−1
sq −1とわかる. 本研究では q = 2 とし、ら，n + s ≤q−1s が小さくなるための条件を考える。

d = min{d(x, y) : x, y ∈ C, x 6= y}を符号 C の最小距離という.

Definition 3 (e-誤り訂正符号) e ビット以内の誤りを正確に復号することが出来る符号を e-誤り訂正符号(e-error correcting code) と呼び，e をこの符号の誤り訂正能力という.
符号 C の最小距離 d が d ≥ 2e + 1 を満たすとき，Cは e-誤り訂正符号となる.

Definition 6 (Debruijn 系列) s 次の DeBruijn 系
列とは，F2 上の周期 2s の数列であり，連続する s 個を見ると，周期の中でどのパターンもちょうど 1 回ずつ出ている数列である.

Definition 4 (m 系列) Fq 上の n 次のｍ系列とは，原始多項式
f (t) = tn + an−1 tn−1 + · · · + a1 t + a0

Theorem 1 F2 上の DeBruijn 系列を係数に持つ多項式からｍ系列を作ると，n + s = 2s − 2 の (2n − 1, n +s, 3)ECS となる. ただし s 次の DeBruijn 系列を係数に持つ多項式とは、DeBruijn 系列の０が s 個連続する部分の次からその s 個の前までの列から，１が s 個連続する部分の１つの１を除いた列を係数列とする多項式である．の係数から作られる漸化式

xn+i + an−1 xn+i−1 + · · · + a0 xi = 0で生成される，周期 q n − 1 の数列

C := xi xi+1 · · · xi+m−1 (i = 0, 1, · · · , q n − 1)である.

11Theorem 2 (DeBruijn 系列の個数) Fq 上の s 次の
DeBruijn 系列の個数は

表 3: ３次の多項式

r2r3d2x +1693322s−1−s3個である.

Conjecture 1 F2 上の DeBruijn 系列を係数に持つ多項式の中には，原始既約であるものが存在する．

x +x+1352x3 + x2 + 134134512x +x +x+1

この予想が成り立てば，次の予想も成り立つ．

表 4: ４次の多項式

r2r3d2x4 + 181244x +x+14624x +x +16824374x +x +146243x +x +x+1583x4 + x3 + x2 + 1

3744561Conjectureが正しければ，各 s で( 2s −s−2 s 2 Conjecture1)
2, 2 − 2, 3 ECS が存在する．

4多項式の選択による行数の差異

Definition 7 多項式

2x +x +x+1
4f (x) = a0 xn + a1 xn−1 · · · + an−1 x + anから作られる行列を



2a1a0···a1..
.

an−1···..
.

anan−1..
.

0an······

00 

0···

0a0a1···an−1

an

2x +x +x +x+1

a0 0A=335４次多項式の r2 が最小の例と最大の例
行数 r2 が一番少なかった例１：x4 + x2 + x + 1
1 0 1 1 1 0 0
A= 0 1 0 1 1 1 0 とする。この s × (n + s) 行列 A を行数 s の行列と呼ぶ。

0 00 0Definition 8 多項式 f (x) がどの k 列も独立になるために必要な行の数を rk (f (x)) とし、その差を dk = rk+1 − rk とする。

表 1: １次の多項式x+1d22316r2r3d2x +14622341x +x+11111101000000000100001000 0 
0 0 
0 
0 
1

まとめと今後の課題

多項式の選び方によってどの２列も独立になるために必要な行の数が大きく異なることが確認された。
一般のｋについてどのｋ列も線形独立になるために必要な行の数 rk (f (x)) についても調べていきたい。
また、r2 (f1 (x)) < r2 (f2 (x)) のときに r3 (f1 (x)) >r3 (f2 (x)) となる例が確認されたが、一般のｋについて rk (f1 (x)) < rk (f2 (x)) となるための条件や、DeBruijn 系列から作った多項式の r2 , r3 , d2 の値について考えていきたい。

表 2: ２次の多項式21

行数 r2 が一番多かった例：x4 + 1

1 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 0 0
 0 0 1 0 0 0 1 0 0
 0 0 0 1 0 0 0 1 0A=
 0 0 0 0 1 0 0 0 1

 0 0 0 0 0 1 0 0 0

 0 0 0 0 0 0 1 0 0

0 0 0 0 0 0 0 1 0

それぞれの多項式の r2 , r3 , d2 の値は次のようになった。特に４次の場合、r2 の値が３から８と大きな差があることがわかった。また、r2 (f1 (x)) ≤ r2 (f2 (x)) のときに rk (f1 (x)) ≤ rk (f2 (x)) となると予想していたが、ならない場合もあることがわかった。

r30

行数 r2 が一番少なかった例２：x4 + x3 + x2 + 1
1 1 1 0 1 0 0
A= 0 1 1 1 0 1 0 

本研究においては, 多項式から作られる行数を何行まで増やせばどの２列も独立になるか、４次以下の多項式について調べた。

r2112