Binary self-dual code の被覆半径の問題総括

山形大学理学部小関道夫 email address : ozeki@kszaoh3.kj.yamagata-u.ac.jp

1 序論

始めに、符号理論におけるいくつかの基本的問題を述べておく。 (I) 符号の重み枚挙多項式の決定。 (II) 指定された最小重み、あるいはより一般に指定された条件を持つ符号の存在、非存在、存在する場合の多様性。 (III) 符号の被覆半径の決定問題。

S_{r}(u) = {x ∈ 𝔽_{2}^{n} | d(u, x) ≤ r} .

を符号 C の符号語 u を中心とする半径 rの Hamming 球とするとき、

𝔽_{2}^{n} = ∪_{u∈C}S_{r}(u)

となるような r の最小値を符号 C の被覆半径といい、 t(C) であらわす。与えられた符号 C に対して t(C) を決定することが、被覆半径の決定問題である。 (IV) 符号の符号化、復号化のアルゴリスム。符号 C が与えられたとき、それを用いて送信が実行されるが、受信信号を復号する方法は、ごく粗い一般的方法を除けば、個々の符号の特性に根ざした良い復号化のアルゴリスムを探求することは、困難な課題である。

2 符号の被覆半径の決定問題

符号の被覆半径を単に決定する問題は、もしその上限あるいは下限が適当な範囲に収まっている場合には、プログラミングと計算機の性能が良ければ時間を掛ければ辛抱できる時間内で求めることができる。例えば、 2 元自己双対 [56,28,12] 符号^{1}、 2 元自己双対 [64,32,12] 符号、 2 元自己双対 [80,40,16] 符号、 2 元自己双対 [88,44,16] 符号、 3 元自己双対 [28,14,9] 符号、 3 元自己双対 [32,16,9] 符号、 3 元自己双対 [36,18,12] 符号、 3 元自己双対 [40,20,12] 符号、 3 元自己双対 [44,22,12] 符号、等々。ここで、断って置きたいことは、上記のパラメータより小さい自己双対符号については既に充分な方法や結果が存在していることである。 (c.f. [16],[19],[20] ) 従って、この程度のレベルの問題ならば、数学的な関心よりはむしろ工学的な関心から扱う種類の問題と見なせる。従ってここでは扱わない。

しかし、符号の性能の評価あるいは復号化アルゴリスムまでを視野にいれると、コセットの重み分布までを知らなければならない。この問題意識から見ると、これまである方法としては、 Delsarte の方法がほとんど唯一のものだった。議論の始めにこれを解説する。

基本的な定義等については [12], [24] を参照。

3 Delsarte の方法 (2 元体の場合)

3.1 符号の基本量

C を長さが n で次元が h の元線形符号とする。 d を Hamming 距離、 wt を Hamming 重みとする。符号 C の双対符号 C^{⊥} は

C^{⊥} = {b ∈ 𝔽_{2}^{n}| (a, b) = 0 ∀a ∈ C}

により定義される。ここで、 (a, b) は内積をあらわす。以下 Delsarte [7] に従って符号 C の基本量を定義する。

d(C) = min_{0≠x∈C} wt(x),

s = s(C) = {wt(x)|x ∈ C},

d′(C) = d(C^{⊥}), s′(C) = s(C^{⊥}).

1この場合については Tsai [25] が一例について実行している

このとき、次の限界はよく知られている。

Delsarte bound : t(C) ≤ s′

3.2 符号の重み枚挙多項式その他

前節のように C を長さが n で次元が h の元線形符号とする。 C の非斉次重み枚挙多項式 W_{C}(X) は

W_{C}(X) = _{v∈C}^{∑} X^{wt(v)}

により定義される。例えば、ハミング符号 [8,4,4] H_{8} の非斉次重み枚挙多項式は

W_{H_{8}}(X) = 1 + 14X^{4} + X^{8}

で与えられる。

A_{i}(C) = #{a ∈ C| wt(a) = i} i = 0, 1, ⋯, n

とするとき、

W_{C}(X) = ∑_{i=0}^{n} A_{i}(C)X^{i}

と展開される。 F_{2}^{n}/C 内のコセット U に対するコセット重み枚挙多項式 W_{U}(X) を

W_{U}(X) = ∑_{x∈U} X^{wt(x)}

により定義する。

3.3 Krawtchouk 多項式

Krawtchouk 多項式を定義する。

P_{k}(x) = ∑_{j=0}^{k}(−1)^{j} ( \begin{matrix}x \\ j \end{matrix} ) ( \begin{matrix}n − x \\ k − j \end{matrix} ) 0 ≤ k ≤ n,

ここで、 x は変数で、

( \begin{matrix}x \\ j \end{matrix} ) = \frac{x(x − 1) ⋯ (x − j + 1)}{j!}, j ≥ 1 ( \begin{matrix}x \\ 0 \end{matrix} ) = 1

とする。 i, j, u ∈ {0, 1, ⋯, n} とするとき、

P_{i}(u)P_{j}(u) = ∑_{k=0}^{n} p_{i,j}^{(k)}P_{k}(u)

が成り立つ。ただし、 p_{i,j}^{(k)} は次のようにして定められる量である。

D_{i} = {a ∈ 𝔽_{2}^{n}| wt(a) = i}

として、 c ∈ D_{k} を一つ決めたとき、

p_{i,j}^{(k)} = #{< a, b > | a ∈ D_{i}, b ∈ D_{j} }.

p_{i,j}^{(k)} は c の取り方に依存しないことがわかる。 2 元符号に対しての p_{i,j}^{(k)}の公式は、例えば、 MacWilliams and Sloane [12], Ch. 21 section 3 に記載されている。

3.4 Distance Matrix

C を 2 元符号として,e ∈ 𝔽_{2}^{n} に対して

B_{i}(e) = #{a ∈ C | d(a, e) = i } 0 ≤ i ≤ n

を係数とする 2^{n} × (n + 1) 行列 B = (B_{i}(e))_{e∈𝔽_{2}^{n},0≤i≤n} を C の distance matrix という。より具体的に書くと、

B = ( B_{0}(e_{1}) B_{1}(e_{1}) B_{2}(e_{1}) ⋯ B_{n}(e_{1}) B_{0}(e_{2}) B_{1}(e_{2}) B_{2}(e_{2}) ⋯ B_{n}(e_{2}) ⋮ B_{0}(e_{m}) B_{1}(e_{m}) B_{2}(e_{m}) ⋯ B_{n}(e_{m}) ⋮ B_{0}(e_{2^{n}}) B_{1}(e_{2^{n}}) B_{2}(e_{2^{n}}) ⋯ B_{n}(e_{2^{n}}) )

distance matrix B の行の順序を変更するだけで、係数 B_{i}(e) が左から右への、および上から下への辞書式順序を満たすようにすることができる。すなわち、 0 ≤ m_{1} < m_{2} ≤ 2^{n} ならば

B_{i}(e_{m_{1}}) = B_{i}(e_{m_{2}}) i = 0, 1, ⋯, n

またはある 0 ≤ t ≤ n − 1 があって

B_{i}(e_{m_{1}}) = B_{i}(e_{m_{2}}) i = 0, 1, ⋯, t

かつ B_{t+1}(e_{m_{1}}) < B_{t+1}(e_{m_{2}}). このようにして新しく配列し直した行列を normalized distance matrix と呼ぶことにする。

3.5 Distance Matrix の垂直方向の情報

C を長さが n で次元が h の 2 元符号とし、

A_{i}(C) = #{a ∈ C| wt(a) = i} i = 0, 1, ⋯, n

とするとき、

(1)  _{e∈𝔽_{2}^{n}}^{∑} B_{i}(e)B_{j}(e) = M ∑_{k=0}^{n} p_{i,j}^{k}A_{k}(C) M = 2^{h}

3.6 Distance Matrix の水平方向の情報

J = {wt(b)| b ∈ C^{⊥} − {0}} とし、整数 m を 0 ≤ m ≤ n − s′ の範囲で取り、次数 m + s′ の多項式

β_{m}(x) = M^{−1}2^{n}x^{m} ∏_{j∈J}(1 − \frac{x}{j})

を Krawtchouk 多項式で展開する。

β_{m}(x) = γ_{0}^{(m)}P_{0}(x) + γ_{1}^{(m)}P_{1}(x) + ⋯ + γ_{m+s′}^{(m)}P_{m+s′}(x).

上の展開の係数から定まるベクトル

γ^{(m)} = (γ_{0}^{(m)}, γ_{1}^{(m)}, γ_{2}^{(m)}, ⋯, γ_{m+s′}^{(m)} ∈ Q^{n+1}

は関係

(2)  γ^{(m)}B^{T} = δ_{0,m}j^{T}

を満たす。ここで、 B^{T} は B の転置行列で、 j^{T} = (1, 1, ⋯, 1).

3.7 具体例による解説

ハミング [8,4,4] 符号 H_{8} では distance matrix B = (B_{i}(e)) は 256 × 9 行列である。

B_{i}(e) = #{a ∈ C | d(a, e) = i}
= #{a ∈ C | wt(a + e) = i}

より B_{i}(e) は e が属するコセット e + C のベクトルで重みが i のものの個数である。言い換えると B_{0}(e), B_{1}(e), ⋯, B_{n}(e) は e + C のコセット重み分布ベクトルである。従って B が分かれば C のコセット重み分布が分かったことになる。

n = 8 のときの Krawtchouk 多項式は

P_{0}(x) = 1
P_{1}(x) = 8 − 2x
P_{2}(x) = 2x^{2} − 16x + 28
P_{3}(x) = −\frac{4}{3} + 16x^{2} − \frac{170}{3} + 56
P_{4}(x) = \frac{2}{3}x^{4} − \frac{32}{3}x^{3} + \frac{172}{3}x^{2} − \frac{352}{3} + 70
⋮

H_{8} では J = {4, 8}, s′ = 2, M = 2^{4} なので、

β_{m}(x) = M^{−1}2^{8}x^{m}(1 − \frac{x}{4})(1 − \frac{x}{8})
= 2^{−1}x^{m}(x − 4)(x − 8)
β_{0}(x) = 2^{−1}(x − 4)(x − 8)
= P_{0}(x) + P_{1}(x) + \frac{1}{4}P_{2}(x)

となり、

γ^{(0)} = (1, 1, \frac{1}{4}, 0, 0, 0, 0, 0, 0)

を得る。またγ^{(0)}B^{T} = j^{T} より

(3)  B_{0}(e) + B_{1}(e) + \frac{1}{4}B_{2}(e) = 1 ∀e ∈ 𝔽_{2}^{8}

β_{1}(x) = 2^{−1}x(x − 4)(x − 8)
= \frac{21}{8}P_{1}(x) − \frac{3}{8}P_{3}(x)

となり、

γ^{(1)} = (0, \frac{21}{8}, 0, −\frac{3}{8}, 0, 0, 0, 0, 0)

を得る。 γ^{(1)}B^{T} = 0 より

(4)  \frac{21}{8}B_{1}(e) − \frac{3}{8}B_{3}(e) = 0 ∀e ∈ 𝔽_{2}^{8}

さらに

β_{2}(x) = 2^{−1}x^{2}(x − 4)(x − 8)
= −\frac{21}{2}P_{0}(x) + \frac{21}{2}P_{1}(x) − \frac{3}{2}P_{2}(x) − \frac{3}{2}P_{3}(x) + \frac{3}{4}P_{4}(x)

から

γ^{(2)} = (−\frac{21}{2}, \frac{21}{2}, −\frac{3}{2}, −\frac{3}{2}, −\frac{3}{4}, 0, 0, 0, 0)

を得て、 γ^{(2)}B^{T} = 0^{T},

(5) −\frac{21}{2}B_{0}(e) + \frac{21}{2}B_{1}(e) − \frac{3}{2}B_{2}(e) − \frac{3}{2}B_{3}(e) + \frac{3}{4}B_{4}(e) = 0 ∀e ∈ 𝔽_{2}^{8}

τ = τ(e) により、 B_{τ}(e) ≠ 0 となる最小の τ を表わすことにする。この τ は e + C の重みでもある。

(a) τ = 0 のとき、 (3) より B_{0}(e) = 1, B_{1}(e) = 0, B_{2}(e) = 0. (4) より B_{3}(e) = 0, (5) より、 B_{4}(e) = 14.

(b) τ = 1 のとき、 (3) より B_{0}(e) = 0, B_{1}(e) = 1, B_{2}(e) = 0. (4) より B_{3}(e) = 7, (5) より、 B_{4}(e) = 0.

(c) τ = 2 のとき、 (3) より B_{0}(e) = B_{1}(e) = 0, B_{2}(e) = 4. (4) より B_{3}(e) = 0, (5) より、 B_{4}(e) = 8. m = 3, 4, 5, 6 に対して β_{m}(x) の情報を使えば、 B_{5}(e), B_{6}(e), B_{7}(e), B_{8}(e) 等が定まる。以上の計算から Hamming 符号 H_{8} の normalized distance matrix B は

B = ( 1 0 0 0 14 0 ⋯; ⋮ ; 1 0 0 0 14 0 ⋯; 0 1 0 7 0 7 ⋯; ⋮ ; 0 1 0 7 0 7 ⋯; 0 0 4 0 8 0 ⋯; ⋮ ; 0 0 4 0 8 0 ⋯; ⋮ ; ⋮ )

の形をとる。 B において、初めの形の行が α 個、次の形の行が β 個、 3 番目の形の行が γ 個等々現れるとするとき、 α, β, γ, ⋯ はどのようにして決められるか。一般には、計算にたよるしか方法がない。その場合でも、条件 (1) は強い制約条件になる。特に、 Hamming [8,4,4] 符号、 Golay [24,12,8] 符号等の場合にはだけで行列 B が決定できる。 C = H_{8} の場合にこのことを示そう。

A_{0}(C) = 1, A_{4}(C) = 14, A_{8}(C) = 1, A_{i}(C) = 0i ≠ 0, 4, 8

はよく知られている。また、 p_{0,0}^{(0)} = 1, p_{0,0}^{(4)} = 0, p_{0,0}^{8} = 0 なので、

_{e∈𝔽_{2}^{8}}^{∑} B_{0}^{2}(e) = 2^{4} ∑_{k=0}^{8} p_{0,0}^{(k)}A_{(k)}(C)
= 16

B_{0}(e) = 1 となる e ∈ 𝔽_{2}^{8} は 16 個, 従って α = 16 が導かれた。

_{e∈𝔽_{2}^{8}}^{∑} B_{1}^{2}(e) = 2^{4} ∑_{k=0}^{8} p_{1,1}^{(k)}A_{(k)}(C)

上で p_{1,1}^{0} = 8, p_{1,1}^{(4)} = 0, p_{1,1}^{(8)} = 0 を使った。 B_{0}(e) = 0, B_{0}(e) = 1 となる e ∈ 𝔽_{2}^{8} は 128 個, よって β = 128。 p_{2,2}^{0} = 28, p_{2,2}^{(4)} = 6, p_{2,2}^{(8)} = 0 となるので

_{e∈𝔽_{2}^{8}}^{∑} B_{2}^{2}(e) = 2^{4} ∑_{k=0}^{8} p_{2,2}^{(k)}A_{(k)}(C)
= 2^{4} · 112

B_{0}(e) = 0 = B_{1}(e) = 0, B_{2}(e) ≠ 0 ⟶ B_{2}(e) = 4 となっていることが分かっているから B_{0}(e) = 0 = B_{1}(e) = 0, B_{2}(e) = 4 となる e の情報が得られる。そのような e の個数は 112 。故に γ = 112 。

α + β + γ = 16 + 128 + 112 = 256

なので、 Hamming [8,4,4] 符号の normalized distance matrix B の形はこれで決まったことになる。

Remark 1 distance matrix B の横の情報を計算するために Krawtchouk polynomials を使うので、面倒である。

Remark 2 𝔽_{2}^{n} のベクトルと C の全ての符号語を相手にして計算するので計算量も多い。

Remark 3 異なるコセットを識別する手段がこのままではない。すなわち、符号毎に工夫をしなければならない。

4 符号の Jacobi polynomial による方法

u = (u_{1}, u_{2}, ⋯, u_{n}), v = (v_{1}, v_{2}, ⋯, v_{n}) ∈ 𝔽_{2}^{n} に対して

u ∗ v = #{i|u_{i} = v_{i} = 1, 1 ≤ i ≤ n}

により u と v の intersection number を定義する。 2 元線形符号 C とつの独立な変数 X, Z に対して

Jac(C, v; X, Z) = _{u∈C}^{∑} X^{wt(u)}Z^{u∗v}

により定義される多項式を符号 C の Jacobi 多項式という。 wt(v = α のとき、 α をこの Jacobi 多項式の index (指数) という。 Jacobi 多項式とコセット U = v + C のコセット重み枚挙多項式 W_{U}(X) の関係は

W_{U}(X) = X^{wt(v)}Jac(C, v | X, X^{−2}),

により与えられる。 (c.f. [15],[16]) Hamming [8,4,4] 符号について Jacobi 多項式を計算する。

(1) wt(v) = 1 のとき

Jac(H_{8}, v | X, Z) = 1 + X^{4}(7Z + 7) + X^{8}Z

となり、このような v は 8 個ある。この vが属するコセット U = v + C の重み枚挙多項式 W_{U}(X) は

W_{U}(X) = X + 7X^{3} + 7X^{5} + X^{7}

となる。

(2) wt(v) = 2 のとき

Jac(H_{8}, v | X, Z) = 1 + X^{4}(3Z^{2} + 8Z + 3) + X^{8}Z^{2}

により与えられる。このような v は ( \begin{matrix}8 \\ 2 \end{matrix} ) = 28 個ある。これらの vが属す

るコセット U = v + C の重み枚挙多項式 W_{U}(X) は

W_{U}(X) = 4X^{2} + 8X^{4} + 4X^{6}

となる。ここで、注意しておきたいことは、一つのコセットに 4 つのコセットリーダーがあることで、このことから異なるコセットは 28/4 = 7 個しかないことが分かる。

(3) wt(v) = 3 のとき

Jac(H_{8}, v | X, Z) = 1 + X^{4}(Z^{3} + 6Z^{2} + 6Z + 1) + X^{8}Z^{3}

により与えられる。このような v は ( \begin{matrix}8 \\ 3 \end{matrix} ) = 56 個ある。しかし、これらの

vが属するコセット U = v + C の重み枚挙多項式 W_{U}(X) は

W_{U}(X) = X + 7X^{3} + 7X^{5} + X^{7}

となり、 wt(v) = 3 となるベクトル v はもはやコセットリーダーになり得ないことを結論できる。上の計算を表にすると、次のようになる。

coset wt\ wt 0 1 2 3 4 5 6 7 8 num. of cosets
0  1  14  1  1
1  1  7  7  1  8
2  4  8  4  7

1 + 8 + 7 = 16 = |𝔽_{2}^{8}/H_{8}| より全ての H_{8} のコセットの重み分布が尽くされたことが分かる。

5 符号のコセット重み分布の計算の現状

5.1 extremal weight enumerator

いくつかの 2 元極値的自己双対符号 C の重み枚挙多項式 W_{C}(X) をここに記す。その理由はこれらの多項式が困難の所在をやや漠然と示すからである。

(i) C : [40,20,8] 符号のとき

W_{C}(X)

= 1 + 285X^{8} + 21280X^{12} + 239970X^{16} + 525504X^{20} + 239970X^{24}

+21280X^{28} + 285X^{32} + X^{40}

(ii) C : [48,24,12] 符号のとき

W_{C}(X)

= 1 + 17296X^{12} + 535095X^{16} + 3995376X^{20} + 7681680X^{24}
+3995376X^{28} + 535095X^{32} + 17296X^{36} + X^{48}

(iii) C : [56,28,12] 符号のとき W_{C}(X)

= 1 + 8190X^{12} + 622314X^{16} + 11699688X^{20} + 64909845X^{24} + 113955380X^{28}

+64909845X^{32} + 11699688X^{36} + 622314X^{40} + 8190X^{44} + X^{56}

(iv) C : [64,32,12] 符号のとき W_{C}(X)

= 1 + 2976X^{12} + 454956X^{16} + 18275616X^{20} + 233419584X^{24}

+1041971008X^{28} + 1706719014X^{32} + 1041971008X^{36} + 233419584X^{40} +18275616X^{44} + 454956X^{48} + 2976X^{52} + X^{64}

(v) C : [72,36,16] 符号のとき (存在の方は未だ不明であるが) W_{C}(X)

= 1 + 249849X^{16} + 18106704X^{20} + 462962955X^{24} + 4397342400X^{28}

+16602715899X^{32} + 25756721120X^{36} + 16602715899X^{40} + 4397342400X^{44} +462962955X^{48} + 18106704X^{52} + 249849X^{56} + X^{72}

(vi) C : [80,40,16] 符号のとき W_{C}(X)

= 1 + 97565X^{16} + 12882688X^{20} + 590073120X^{24} + 10588174080X^{28}

+79707678050X^{32} + 263303738880X^{36} + 391106339008X^{40} + 263303738880X^{44} +79707678050X^{48} + 10588174080X^{52} + 590073120X^{56} + 12882688X^{60} +97565X^{64} + X^{80}

(vii) C : [88,44,16] 符号のとき W_{C}(X)

= 1 + 32164X^{16} + 6992832X^{20} + 535731625X^{24} + 16623384448X^{28}
+225426781470X^{32} + 1405590745152X^{36} + 4163803131796X^{40}
+5968212445440X^{44} + 4163803131796X^{48} + 16623384448X^{60}

+535731625X^{64} + 1405590745152X^{52} + 225426781470X^{56} + 6992832X^{68}

+32164X^{72} + X^{88}

5.2 known bounds for t(C)

Assmus and Pless ([1]) で与えられている限界を (追加情報付きで) 再掲する。

code parameters covering radius  contributer
[8,4,4]  2
[16,8,4]  4
[24,12,8]  4
[32,16,8]  6 Assmus-Pless [1]
[40,20,8]  7 ≤ t(C) ≤ 8  [1],[16],[20]
[48,24,12]  8  [1]
[56,28,12]  9 ≤ t(C) ≤ 10  [20]
[64,32,12]  8 ≤ t(C) ≤ 12
[72,36,16]  10 ≤ t(C) ≤ 12
[80,40,16]  10 ≤ t(C) ≤ 14
[88,44,16]  12 ≤ t(C) ≤ 16
[96,48,20]  12 ≤ t(C) ≤ 16

5.3 [40,20,8] 符号のコセット重み分布

[40,20,8] 符号の生成行列が与えられさえすれば、そのコセット重み分布の完全な決定は 2,3 日でできる。 (c.f. [16]) 勿論電子計算機により符号の Jacobi 多項式を計算する必要があるが。しかし、有限群の不変式論が強力な援護射撃をしてくれて、重みが 8 の符号語についての計算をすればよいことが言えて、計算量を大幅に軽減することができた。また、このような符号は現在 1000 個以上あることが知られているので、そのすべてについて、そのコセット重み分布を決定することは、意義があることには思えない。

ただ、最近になり [40,20,8] 符号の被覆半径の下からの評価が改良されて ([20]) 7 ≤ t(C) ≤ 8 となり、しかも t(C) = 7 となる符号が原田氏 (山形大理) により発見され、この場合は原理的には終局を迎えたと考えられる。ほとんどの符号は t(C) = 8 となっている。

5.4 2 元 [56,28,12] 符号のコセット重み分布

平成 9 年 4 月の日本数学会春期総会で講演を行った時点、および本研究集会では 2 元 [56,28,12] 符号のコセット重み分布を完全に決定するためには、一つの符号でも、 10 年程度かかるという認識だった。 (c.f. [18]) その時想定した方法は Jacobi 多項式を主に使うことであった。その後 Delsarte の方法と Jacobi 多項式の方法を融合するアイデアを得て、半年ですべての必要な計算をパソコン (166Mhz 程度) で済ませられる見込みがついた。しかし、実行となると、様々な障害が立ちはだかり (例えば大学では設備の更新とか、点検のため停電がたまにある), 滑らかに進行しない。この報告を出してから 1 年経っても未だ完了していないようだったら、自分の怠惰さの再確認をせざるを得ない。もっともこの点については何度も再確認を強いられているが。

5.5 Concluding Remarks

Remark 4 いままで扱った符号は doubly even な符号であるが simply even な符号を扱うためには Jacobi 多項式の理論を simply even self dual codes の場合まで拡張しておく必要がある。

Remark 5 2 元自己双対 [64,32,12] 符号、 2 元自己双対 [80,40,16] 符号、の被覆半径の問題 (コセット重み分布の決定までを含む) が次の目標の一つであるが、これらについては余程の良い理由が見つからない限りは、調べるつもりはない。誰か他の人にまかせたい。これら場合には、さらに [40,20,8] 符号、 [56,28,12] 符号のときにあった幸運な事情があるかどうかは数式処理で当たってみなければ判明しない。その幸運な事情とは、最小重みの符号語だけで得られる情報で充分であるということである。この幸運がないときには、計算量は格段に多くなり、ゴールは遠くなる。 (上記の重み枚挙多項式を参照)

Remark 6 自己双対でない線形 2 元符号で実用的には重要な符号の系列がある。例えば、 BCH 符号、 Reed-Muller 符号、 Goppa 符号等である。これらの符号は小さいパラメータを除いては被覆半径すら分かっていない。増して、コセット重み分布の決定となると新しいアイデアも、高性能の計算機も必要になろう。 Remark 7 3 元自己双対符号でも被覆半径の問題は開始されている。 ([19]) この場合では Jacobi 多項式では現象をよく捕捉できなくて、 modified Jacobi polynomial が自然な道具になる。それらのなす多項式環の構造がはっきりしていないので、小さいパラメータしか未だ取り扱えない。

Remark 8 符号の被覆半径の問題と符号から構成される格子の被覆半径の問題をつなぐ bridge の理論が望ましい。

References

[1] E.F. Assmus,Jr. V. Pless, On the Covering Radius of Extremal Self-Dual Codes, IEEE Trans. Inform. Theory, IT-29 (1983), 359-363

[2] E. Bannai, E. Bannai, M. Ozeki and S. Teranishi, Rings of simultaneous invariants for the MacWilliams-Gleason group , (in preparation)

[3] R.A. Brualdi and V.S. Pless, Weight enumerators of self-dual codes, IEEE Trans. Inform. Theory, IT-37 (1991), 1222-1225

[4] J.H. Conway and N.J.A. Sloane, Sphere Packings, Lattices and Groups, Springer-Verlag 1988. Third Edition will appear in 1998

[5] J.H.Conway, V.Pless and N.J.A. Sloane, Self-dual codes over GF (3)and GF (4) of length not exceeding 16, IEEE Trans. Inform. Theory, IT-25 (1979), 312-322

[6] J.H. Conway and N.J.A. Sloane, A New Upper Bound on the Minimal Distance of Self-Dual Codes, IEEE Trans. Inform. Theory, V.36 (1990) 1319-1333

[7] P. Delsarte, Four fundamental parameters of a code and their combinatorial significance, Information and Control Vol.23, (1973) 407-438

[8] P. Delsarte, An algebraic approach to the association schemes of coding theory, Philips Research Reports Supplements, No. 10 (1973)

[9] M. Harada and M. Ozeki, Extremal Self-Dual Codes with the Smallest Covering Radius, submitted to a Journal (1998)

[10] W.C. Huffman, On extremal Self-Dual Ternary Codes of Lengths 28 to 40, IEEE Trans. Inform. Theory, Vol.38 (1992), 1395-1400

[11] J.S. Leon, V. Pless and N.J.A. Sloane, On ternary self-dual codes of length 24, IEEE Trans. Inform. Theory, IT-27 (1981), 176-180

[12] F.J. MacWilliams and N.J.A.Sloane, ”The Theory of Error-Correcting Codes”,North-Holl and, Amsterdam, 1977.

[13] C.L. Mallows, V. Pless and N.J.A. Sloane, Self-dual codes over GF (3), SIAM J. Appl. Math. Vol. 31, 649-666

[14] M. Ozeki, Determination of the ring of simultaneous invariants for a group associated with MacWilliams identity (an intermediate report of a joint work with E. Bannai), in Meeting on algebraic combinatorics, Suuri Kaiseki Kenkyuusho Koukyuuroku No. ??? (yet unpublished), (1995) Research Institute of Mathematical Sciences in Kyouto Univ.

[15] M. Ozeki, On the notion of Jacobi polynomilas for codes, Math. Proc. Cambridge Philos. Soc. Vol. 121 (1997) 15-30

[16] M. Ozeki, On covering radii and coset weight distributions of extremal binary self-dual codes of length 40, to appear in Theoretical Computer Science

[17] 小関道夫, Covering Radii of binary self-dual extremal codes 平成 8 年 7 月第 41 回代数学シンポジウム報告集 (1996)

[18] 小関道夫, 符号理論、その固有の問題および他の分野と関連した２、３の問題平成 9 年 4 月日本数学会春期総会代数学分科会特別講演

[19] M. Ozeki, On the covering radius problem for Ternary self-dual Codes, preprint 1997

[20] M. Ozeki, Two results on the covering radius problem for binary selfdual extremal codes, in preparation

[21] V. Pless, N.J.A. Sloane and H.N. Ward, Ternary codes of minimum weight 6, and the classification of length 20, IEEE Trans. Inform. Theory, IT-26 (1980), 305-316 [22] E.M. Rains and N.J.A.Sloane, Self-Dual Codes, in Handbook of Coding

Theory V. Pless (ed), North-Holland (1998)

[23] N.J.A. Sloane, Error-correcting codes and invariant theory: new applications of a nineteenth-century technique, Amer. Math. Month. 84 (1977) 82-107.

[24] N.J.A.Sloane, Self-dual codes and lattices, in ”Relations between Combinatorics and Other Parts of Mathematics”, Proc. Symp. in Pure Math., no.34 (1979) 273-308.

[25] H.-P. Tsai, The covering radius of extremal self-dual code D11 and its application, IEEE Trans. Inform. Theory, IT-43 (1997), 316-319