誤り訂正符号系列の存在条件
田中郁美 (指導教員：萩田真理子)

1と書ける。
F(2 )上の符号では、q = 2 で |2k |(1 +(n)nn2 + · · · + e ) ≥ 2 となる。

はじめに誤り訂正符号系列の存在条件において、これまでに１個の誤りが訂正できる最小距離 3 の誤り訂正符号系
列の存在条件については研究が進んでいて、参考文献[2][3] などでいくつかの存在条件が示されているが、2個以上の誤りを訂正できる、最小距離 5 以上の場合についてはまだ研究されていなかった。そこで、本研究では F2 上の 10 次の原始多項式を使って、2 誤り訂正符号系列にどのような存在条件があるかを調べた。

24

1+誤り符号訂正系列[誤 り 訂 正 符 号 系 列 (error-correctingsequence(ECS))]
X 上の (N, k, d) 誤り訂正符号系列 (ECS) とは、周期N の数列
a0 a1 a2 . . . aN −1 . . . (ai+N = ai , aj ∈ X)
であり、どの連続する k 項も異なり、最小距離∑k−1
d = min{ i=0 δ(a{i+s , ai+t )|0 ≤ s < t ≤ N − 1}1(x ̸= y)
ただし、δ(x, y) =0(x = y)の誤り訂正符号をなすものをいう。
[m 系列]
F2 上の n 次の原始多項式 f (t) = tn + an−1 tn−1 +· · · + a1 t + a0 の係数から作られる漸化式 xn+i +an−1 xn+i−1 + · · · + a1 xi+1 + a0 xi = 0 で生成される数列 x0 x1 x2 x3 . . . を m 系列という。
m 系列は、周期 2n − 1 で、連続する n 個見た時の最小距離が 1 であるから、(2n − 1, n, 1)ECS である。つまり、d = 1 となり、誤りを訂正することはできない。
そこで、d ≥ 3 とするために、(2n − 1, n + s, d)ECSとし、d を大きくするために、見る範囲を +s だけ拡張し、m 系列に現れる連続する n + s 個を見る。これは
a0 a1 . . . an000 ... 0 0 a0 a1 . . . an 00 ... 0 

A =  0 0 a0 a1 . . . an 0 . . . 0 

..
..

.
.


0 00 ...
0 a0 a1 . . . an

符号

[符号]
X:有限集合とする時、C ⊂ X n を符号という。x =(x1 , x2 , . . . , xn ), y = (y1 , y2 , . . . , yn ) ∈ X n について、d(x, y) = ♯{i|xi ̸= yi } を x と y のハミング距離という。
[誤り訂正符号]
符号 C の最小距離 d = min{d(x, y)|x, y ∈ C, x ̸=y} ≥ 2e + 1 の時、送る元が X n の中の C の元だけだとわかっていれば、C にない元が届いた時に１番近い符号に直す事で e 個までの誤りを訂正できる。このような符号を e 誤り訂正符号という。
[線形符号]C ⊂ Fnq が Fnq の k 次元部分空間のときつまり、基底ベクトル ∃ c1 , c2 , . . . , ck ∈ C について C = {a1 c1 +a2 c2 + · · · + ak ck |ai ∈ X} と書ける時、C を線形符号という。この時、C の大きさは q k である。この符号の最小距離が d の時、(n, k, d) 符号という。
[パリティ検査行列]
C の直交補空間は線形代数の次元公式の定理より、n−k次元である。つまり、ある行列 H について、C = {c ∈−→X n |Hc = 0 } とかける。この H をパリティ検査行列という。
以上より、n を固定したとき、送れる情報の割合を大きくするには |C| は大きい方がよい。つまり、F2 上の (n, k, d) 符号では |C| = 2k なので、k が大きい方がよい。また、たくさんの誤りを訂正できるので、e も大きい方がよい。

3(n)を s × (n + s) 行列とすると、Ax = 0 を満たす、全て0 以外のベクトル x の全体である。d ≥ 3 にするためには、行列 A のどの 2 列以下の組み合わせも線形独立、d ≥ 5 にするためには、行列 A のどの 4 列以下の組み合わせも線形独立でなくてはならない。

5符号の限界式

F2 上の 10 次の原始多項式の比較

F2 上の 10 次の原始多項式の m 系列からパリティ検査行列を作り、以下の 2 つについて調べた。

しかし、k も e も大きくするのは難しい。例えば、以下のシングルトン限界式とハミング限界式を満たさなければならないことが知られている。
[シングルトン限界式]
Fq 上の符号において、符号語の長さが n であるとき、可能な最大符号語数は q k 。2 つの符号語間の最小ハミング距離を d とする。すると、q k ≤ q n−d+1 が成り立つ。F2 上の符号では、q = 2 で 2k ≤ 2n−d+1 となる。
[ハミング限界式]
C の元 x から、距離 e 以下の点の集まりは全て異な( )x から距離 e( 以下の点の数は1 + n1 (q − 1) +(る。
))
nn2e
よって、ハミング限界式は2 (q−1)(n)+· · ·+ e(n(q−1))( )|C|(1+ 1 (q −1)+ 2 (q −1)2 +· · ·+ ne (q −1)e ) ≥ q n• 多項式ごとのパリティ検査行列の行数の比較• 2 列独立になるための行数と 4 列独立になるのための行数の比較[1 誤り訂正符号系列]
最小距離 d ≥ 3、つまり、A のどの２列以下も線形独立であるパリティ検査行列 A をもつ誤り訂正符号系列
を 1 誤り訂正符号系列という。また、ドブライン系列
からこの条件を満たす原始多項式が知られている。
[2 誤り訂正符号系列]
最小距離 d ≥ 5、つまり、A のどの 4 列以下も線形独23

立であるパリティ検査行列 A をもつ誤り訂正符号系列
を 2 誤り訂正符号系列という。
[比較]
パリティ検査行列を作った時、どの 2 列以下も独立になる行数とどの 4 列以下も独立になる行数を図 1 にまとめた。

を相関係数とよぶ。ただし、x, y はそれぞれデータ x =xi , y = yi の相加平均である。これは、各データの平均からのずれを表すベクトルx−x = (x1 −x, . . . , xn −x), y−y = (y1 −y, . . . , yn −y)のなす角の余弦である。
相関係数は-1 から 1 の間の実数値をとり、1 に近いときは 2 つの確率変数には正の相関があるといい、-1に近いときは負の相関があるという。0 に近いときはもとの確率変数の相関は弱いという。
これを計算すると図 3 の相関係数は 0.357297087 で、正の相関があり、やや相関があるといえる。

6まとめ

図 1 より、以下の存在定理が示された。
[誤り訂正符号系列の存在定理]
誤り訂正符号系列として、1 誤り訂正符号系列は(210 − 1, 14, 3)ECS 、2 誤り訂正符号系列は (210 −1, 20, 5)ECS が存在する。
(210 − 1, 14, 3)ECS は x10 + x7 + x6 + x2 + x + 1から生成される m 系列であり、(210 − 1, 20, 5)ECS は
x10 + x6 + x5 + x3 + x2 + x + 1,x10 + x9 + x8 + x7 +x4 + x + 1,x10 + x8 + x4 + x3 + 1,x10 + x9 + x4 + x2 + 1から生成される m 系列である。ただし、m 系列から作られる 1 誤り訂正符号系列としては最もよいパラメー
タを与えた原始多項式 x10 + x7 + x6 + x2 + x + 1 で作られる m 系列は、2 誤り訂正符号系列としてはあまりよいパラメータとは言えず、(210 − 1, 25, 5)ECS であるが、k ≤ 24 については (210 − 1, k, 5)ECS でない事がわかった。

図 1: 原始多項式 (m 系列表示) の 2 列独立になる行数と 4 列独立になる行数

図 1 から、図 2 のような関係性がわかる。

図 2: (左)x 軸:2 列独立になる行数と y 軸:その多項式の数の関係,(右)x軸:4 列独立になる行数と y 軸:その多項式の数の関係

7

図 2 から、図 3 のような 2 列独立になる行数と 4 列独立になる行数の関係性がわかる。

少ない行数で最小距離 5 以上になるための簡単な条件を見つけ，一般的な次数についての”何行で最小距離 5 になる原始多項式が存在する”というような存在定理を作り、具体的な原始多項式の見つけ方を与えることが今後の課題である。そのために、まずもう少し大きな次数について実験し、最小距離をもっと増やそうとするとよい原始多項式が変わるかどうか調べ、F2だけではなく、F3 など他の体上の m 系列についても調べることを考えている。

今後の課題

参考文献
[1] Oliver Pretzel:Error-Correcting Codes and FiniteFields[2] 佐藤春菜:”Projective DeBruijn 系列を係数に持つ多項式の原始既約性の判定” 2009 年度お茶の水女子大学修士論文

図 3: x 軸:2 列独立になる行数と y 軸:4 列独立になる行数の関係
以上の結果をより正確に分析する為に、相関係数を使う。相関係数とは、2 つの確率変数の間の相関を示す統計学的指標である。
[相関係数]
2 組の数値からなるデータ列 (x, y) = {(xi , yi )}(i =1, 2, . . . , n) があたえられたとき、∑n(xi − x)(yi − y)√∑n i=1√∑n22i=1 (xi − x)i=1 (yi − y)[3] Mariko Hagita, Makoto Matsumoto, Fumio
Natsu, Yuki Ohtsuka: ”Error Correcting Sequenceand Projective De Bruijn Graph” Graphs andCombinatorics 24,185-194,2008.

24