Hyper-Kloosterman 符号の諸性質

知念宏司^{∗}  平松豊一^{†}

「第３回代数学と計算」研究集会 (東京都立大学) 1999.10.18

概要

Hyper-Kloosterman 符号は Chinen-Hiramatsu [4] により導入された符号である. 本稿では最近明らかになった性質について述べる. 具体的には, 重偶性 (binary のとき) と準巡回性である. その他に, 研究集会終了後の結果であるが, 最小距離の評価, そして Gilbert-Varshamov 限界を越える符号無限列が Hyper-Kloosterman 符号で構成できることについても簡単に触れる. また, 指数和と trace code に関する一般的事項について, 最初に解説する.

1 指数和と trace code

1.1 指数和と trace code

素数 p をとり, q = p^{r} とおく (ただし r ≥ 2). また, e(x) = e^{2πix/p} とし, 行列 M の転置行列は M^{T} で表すことにする. まず指数和の定義から始める. f(x) ∈ F_{q}[x] に対して,

S(f) := ∑_{x∈F_{q}^{×}} e(tr f(x))

の形の和を指数和 (exponential sums) と呼ぼう. ただし tr : F_{q} → F_{p},

tr α := α + α^{p} + ⋯ + α^{p^{r−1}}.

もちろん, 指数和そのものは r = 1 でも定義できる. しかし以後の議論では r ≥ 2 は本質的である. また, 指数和の一般論については [7, Chap. 5] を参照.

例 1.1 (i) f(x) = x^{m} なら,

S(f) = g_{m} = ∑_{x∈F_{q}^{×}} e(tr (x^{m})) (m 次 Gauss 和).

(ii) f(x) = ax + bx^{−1} = ax + bx^{q−2} なら,

S(f) = K(a, b; q) = ∑_{x∈F_{q}^{×}} e(tr (ax + bx^{−1})) (Kloosterman 和).

∗大阪府立大学総合科学部. E-mail: YHK03302@nifty.ne.jp †法政大学工学部. E-mail: hiramatu@k.hosei.ac.jp

このあと, Hamming 重さが指数和で表示できる符号の特徴づけをおこなう. 定義 1.2 F_{p} 上の線型符号 C に対して F_{q} 上の線型符号 C̃ が存在して

C = tr C̃ := {(tr c_{1}, tr c_{2}, ⋯, tr c_{n}) ∈ F_{p}^{n} | (c_{1}, c_{2}, ⋯, c_{n}) ∈ C̃}

が成り立つとき C を trace code という.

”trace code” について, 定まった訳語はないように思われる (知念 [1] では「跡符号」と訳しておいた). 後述の simplex code も同様.

ここで F_{q} の原始元 α (すなわち F_{q}^{×} = ⟨α⟩ となるもの) をとっておく. C̃ が関数の族 {f_{j}(x)}_{j∈J} ⊂ F_{q}[x] で

C̃ = {(f_{j}(1), f_{j}(α), f_{j}(α^{2}), ⋯, f_{j}(α^{q−2})) | j ∈ J}

の形で与えられるとき, その trace code C について次が成り立つ: 定理 1.3 符号語 x_{j} = (tr f_{j}(1), tr f_{j}(α), tr f_{j}(α^{2}), ⋯, tr f_{j}(α^{q−2})) ∈ C の重さは次の式で与えられる:

w(x_{j}) = \frac{1}{p}(p − 1)(q − 1) − \frac{1}{p} ∑_{b∈F_{p}^{×}} S(b · f_{j}).

証明一般に,

∑_{b∈F_{p}} e(b · tr f_{j}(x)) = \{ \begin{matrix}p, & if tr f_{j}(x) = 0, \\ 0, & if tr f_{j}(x) ≠ 0. \end{matrix}

したがって, x_{j} の 0 である成分の個数は

♯\{x ∈ F_{q}^{×} | tr f_{j}(x) = 0\} = ∑_{x∈F_{q}^{×}} \frac{1}{p} ∑_{b∈F_{p}} e(b · tr f_{j}(x)) = \frac{1}{p} ∑_{b∈F_{p}} ∑_{x∈F_{q}^{×}} e(tr (bf_{j}(x)))
= \frac{1}{p} ∑_{b∈F_{p}} S(b · f_{j}).

w(x_{j}) は, x_{j} の 0 でない成分の個数だから,

w(x_{j}) = q − 1 − \frac{1}{p} ∑_{b∈F_{p}} S(b · f_{j})
= q − 1 − \frac{1}{p}(q − 1) − \frac{1}{p} ∑_{b∈F_{p}^{×}} S(b · f_{j})

(b = 0 のとき S(b · f_{j}) = ∑_{x∈F_{q}^{×}} 1 = q − 1 に注意). これより目標の式を得る. とくに p = 2 なら,

w(x_{j}) = \frac{q − 1 − S(f_{j})}{2}

となる.

この定理が成り立つための C の条件はかなり厳しい (C の形が相当限定される) ように思われる. しかし重要な古典的符号には, その双対符号がこの条件を満たしているものが少なからず存在する. そのことを見るためにはもう少し準備が必要である.

1.2 部分体部分符号と Delsarte の定理

今度は Č を F_{q} 上の符号とする. 即ち, Č は F_{q}^{n} の部分空間である.

定義 1.4 Č に対して F_{p} 上の符号

C = Č ∩ F_{p}^{n}

を, Č の部分体部分符号 (subfield subcode) という.

これはもともと, 最小距離のより大きな符号の構成法として考案された. つまり, C は Č のさらに一部分なのだから, 符号語間の距離は増えることはあっても減ることはないのである. また, より一般的に F_{q^{m}} 上の符号から F_{q} への部分体部分符号を構成することもできるが, ここでは簡単のため, 素体 F_{p} への部分体部分符号のみを考えることにした.

Č が検査行列 Ȟ = (ȟ_{ij}) で定義されているときは, Č の部分体部分符号は, 次のように具体的に構成できる:

定理 1.5 Č を s 行 n 列の検査行列 Ȟ = (ȟ_{ij}) で定義された F_{q} 上の線型符号とする. F_{q} の F_{p} 上の基底 α_{1}, α_{2}, ⋯, α_{r} をとり, 各 i, j に対して

ȟ_{ij} = ∑_{l=1}^{r} h_{ijl}α_{l} (h_{ijl} ∈ F_{q})

とおき, h_{ij} = (h_{ij1}, h_{ij2}, ⋯, h_{ijr})^{T} とする. このとき, Č の部分体部分符号 C の検査行列は次の sr × n 行列 H である:

H = ( \begin{matrix}h_{11} & h_{12} & ⋯ & h_{1n} \\ h_{21} & ⋮ & & ⋮ \\ ⋮ & & & ⋮ \\ h_{s1} & ⋯ & & h_{sn} \end{matrix} ) .

証明明らかに

C = {x ∈ F_{p}^{n} | Ȟx^{T} = 0}

であるから, x = (x_{1}, x_{2}, ⋯, x_{n}) ∈ F_{p}^{n} に対して,

x ∈ C ⇔ ∑_{j=1}^{n} ȟ_{ij}x_{j} = 0 (1 ≤ ∀i ≤ s)
⇔ ∑_{j=1}^{n} ∑_{l=1}^{r} h_{ijl}α_{l}x_{j} = 0 (1 ≤ ∀i ≤ s)
⇔ ∑_{l=1}^{r}(∑_{j=1}^{n} h_{ijl}x_{j})α_{l} = 0 (1 ≤ ∀i ≤ s).

ところが α_{1}, α_{2}, ⋯, α_{r} は F_{p} 上 1 次独立だから, これは

∑_{j=1}^{n} h_{jil}x_{j} = 0 (1 ≤ ∀i ≤ s, 1 ≤ ∀l ≤ r)

と同値である. これは Hx^{T} = 0 を意味する.

系 1.6 dim Č = n − s かつ sr ≤ n ならば, dim C ≥ n − sr.

もちろん, 部分体部分符号を構成して意味があるのは n − sr > 0 のときである.

例 1.7 (Hammimg 符号) p = 2 とする. F_{2}^{r} の 2^{r} − 1 個の 0 でない列ベクトルを並べて作った r × (2^{r} − 1) 行列を検査行列とする 2 元符号を Hamming 符号 (Hamming code) という. 例えば r = 3 なら

H = ( \begin{matrix}1001011 \\ 0101101 \\ 0010111 \end{matrix} ) .

これは F_{2^{r}} の原始元を α とするとき, Ȟ = (1, α, α^{2}, ⋯, α^{2^{r}−2}) を検査行列とする F_{2^{r}} 上の符号の部分体部分符号と考えられる.

部分体部分符号と trace code を結びつけるのが次の定理である:

定理 1.8 (Delsarte) Č を F_{q} 上の符号, C をその部分体部分符号とする. このとき,

C^{⊥} = tr (Č^{⊥}).

証明 MacWilliams - Sloane [8, p.208] または Stichtenoth [10, p.222].

最後にいくつかの具体例を見ていこう.

1.3 例 (1) — Simplex code

F_{q} の原始元 α をとる. H = (1, α, α^{2}, ⋯, α^{q−2}) を検査行列とする F_{q} 上の [q − 1, q − 2] 符号を Č とおく. p = 2 の場合, これの素体への部分体部分符号は Hamming 符号である (一般標数の場合, Hamming 符号の定義は少し異なる). さて, α の F_{p} 上の最小多項式を m_{α}(x) とする. 明らかに m_{α}(x)|(x^{q−1} − 1) である. このとき,

命題 1.9 Č の部分体部分符号を C とすると, C は巡回符号で

C = (m_{α}(x)).

ただし, (f(x)) は環 R_{n} := F_{p}[x]/(x^{n} − 1) において f(x) で生成された単項イデアルを表す.

証明符号長 q − 1 を n とおく. c = (c_{0}, c_{1}, ⋯, c_{n−1}) ∈ F_{p}^{n} について,

c ∈ C ⇔ Hc^{T} = 0
⇔ c_{0} + c_{1}α + ⋯ + c_{n−1}α^{n−1} = 0.

すなわち, c ∈ C であることは c(x) = c_{0} + c_{1}x + ⋯ + c_{n−1}x^{n−1} が α を根にもつことと同値である. したがって, m_{α}(x) が α の最小多項式であることに注意すれば

C = {c(x) ∈ F_{p}[x] | deg c ≤ n − 1, c(α) = 0}
= {f(x)m_{α}(x) (mod x^{n} − 1) | f(x) ∈ F_{p}[x]}.

よって C = (m_{α}(x)) となる.

さて, (m_{α}(x))^{⊥} は simplex code と呼ばれるが, それは Delsarte の定理により trace code で, 次のように表示できる:

まず, Č^{⊥} の生成行列は H だから,

Č^{⊥} = {(a, aα, ⋯, aα^{n−1}) ∈ F_{q}^{n} | a ∈ F_{q}}.

よって, Delsarte の定理より

(m_{α}(x))^{⊥} = tr (Č^{⊥})
= {(tr a, tr (aα), ⋯, tr (aα^{n−1})) ∈ F_{p}^{n} | a ∈ F_{q}}.

(m_{α}(x))^{⊥} の重さ分布を求めてみる. 定理 1.3 の記号で, J = F_{q}, a ∈ J に対して f_{a}(x) = ax の場合だから, 符号語 x_{a} = (tr a, tr (aα), ⋯, tr (aα^{n−1})) の Hamming 重さは

w(x_{a}) = \frac{1}{p}(p − 1)(q − 1) − \frac{1}{p} ∑_{b∈F_{p}^{×}} S(b · f_{a}).

ここで, S(b · f_{a}) = ∑_{x∈F_{q}^{×}} e(tr (bax)) だが, a ≠ 0 なら bax も F_{q}^{×} 全体を動くからこの和は −1 に等しく,

w(x_{a}) = \frac{1}{p}(p − 1)(q − 1) − \frac{1}{p}(p − 1)(−1)
= (p − 1)p^{r−1}.

すなわち, simplex code の 0 以外の符号語はすべて同じ重さをもつ.

1.4 例 (2) — Melas 符号とその双対符号 (Kloosterman 符号)

これまで同様, p を素数, q = p^{r} (r ≥ 2), F_{q} の原始元 α をとる. さらに, α および α^{−1} の F_{p} 上の最小多項式をそれぞれ m(x), m_{−}(x) とする.

定義 1.10 巡回符号 M = (m(x)m_{−}(x)) を Melas 符号という.

Melas 符号については MacWilliams - Sloane [8, p.206], Melas [9], Wolfmann [12] を参照. この Melas 符号の双対符号の Hamming 重さを Kloosterman 和で表すのがこのあとの目標である. 1 つの補題を用意する:

補題 1.11 (n, p) = 1, f(x), g(x) ∈ F_{p}[x], f(x)|(x^{n} − 1), g(x)|(x^{n} − 1), (f(x), g(x)) = 1 とする. このとき, 3 つの巡回符号 (f(x)), (g(x)), (f(x)g(x)) について,

(f(x)g(x))^{⊥} = (f(x))^{⊥} ⊕ (g(x))^{⊥} (ベクトル空間としての直和).

証明 f(x)g(x) は (f(x)), (g(x)) の両方に含まれるから (f(x)g(x)) は (f(x)), (g(x)) 両方の部分空間. よって (f(x))^{⊥} ⊂ (f(x)g(x))^{⊥}, (g(x))^{⊥} ⊂ (f(x)g(x))^{⊥} で,

(f(x))^{⊥} + (g(x))^{⊥} ⊂ (f(x)g(x))^{⊥}.

次に (f(x), g(x)) = 1 から x^{n} − 1 = f(x)g(x)h(x) とおけば, 双対符号の性質により, (f(x)g(x))^{⊥} の任意の元は a(x)h(x) (a(x) ∈ F_{p}[x], deg a < n − deg h) と書ける. また (f(x), g(x)) = 1 より f(x)s(x) + g(x)t(x) = 1 となる s(x), t(x) ∈ F_{p}[x] が存在する. よって

a(x)h(x) = a(x)h(x) {f(x)s(x) + g(x)t(x)}
= a(x)t(x) · g(x)h(x) + a(x)s(x) · f(x)h(x)
∈ (f(x))^{⊥} + (g(x))^{⊥}.

よって (f(x))^{⊥} + (g(x))^{⊥} = (f(x)g(x))^{⊥}. 最後に b(x) ∈ (f(x))^{⊥} ∩ (g(x))^{⊥} をとると, g(x)h(x)|b(x) かつ f(x)h(x)|b(x) より (x^{n} − 1)|b(x), これは R_{n} = F_{p}[x]/(x^{n} − 1) では b(x) = 0 を意味する. よって直和である.

さて, m(x) と m_{−}(x) は α が F_{4} の原始元である場合を除いて互いに素であることが示されるから, その場合以外は補題 1.11 の仮定が満たされる.

F_{4} は x^{4} − x の根全体の集合だが, x^{4} − x = x(x − 1)(x^{2} + x + 1) であるから m(x) = m_{−}(x) = x^{2} + x + 1 である. また, このようなことが起こるのが F_{4} の場合だけであることを示すのも, そう難しくない.

よって

M^{⊥} = (m(x)m_{−}(x))^{⊥} = (m(x))^{⊥} ⊕ (m_{−}(x))^{⊥}.

右辺の直和の各成分はすでに前の 1.3 節で求めてある. その結果を利用すると,

M^{⊥} = {(tr a, tr (aα), ⋯, tr (aα^{n−1})) ∈ F_{p}^{n} | a ∈ F_{q}}
⊕{(tr b, tr (bα^{−1}), ⋯, tr (bα^{−(n−1)})) ∈ F_{p}^{n} | b ∈ F_{q}}
= {(tr (a + b), tr (aα + bα^{−1}), ⋯, tr (aα^{n−1} + bα^{−(n−1)})) ∈ F_{p}^{n} | a, b ∈ F_{q}}.

この式により, M^{⊥} の各元の Hamming 重さが Kloosterman 和で表されることがわかる. そこで M^{⊥} は Kloosterman 符号と呼ばれることがある:

定理 1.12 M^{⊥} の符号語

φ(a, b) := (tr (a + b), tr (aα + bα^{−1}), ⋯, tr (aα^{n−1} + bα^{−(n−1)}))

の Hamming 重さ w(φ(a, b)) は次の式で与えられる:

w(φ(a, b)) = \frac{1}{p}(p − 1)(q − 1) − \frac{1}{p} ∑_{m∈F_{p}^{×}} K(ma, mb; q),

ただし, K(a, b; q) は Kloosterman 和 (1.1 節参照).

Simplex code の場合は指数和の部分が具体的に求まったが, Kloosterman 和の偏角, 絶対値を一般的に決定することはできない. しかし, w(φ(a, b)) がただ 1 つの K(a, b; q) で表せる場合 (p = 2 の場合はそうである), q → ∞ のときに M^{⊥} の Hamming 重さは, ある測度に関して一様分布することが知られている (Hiramatsu [5], Lachaud [6]).

2 Hyper-Kloosterman 符号

2.1 定義と基本性質

p: 素数, r, m ∈ N, r, m ≥ 2 とする. 前節最後の例で定義した Kloosterman 符号 M^{⊥} の拡張として, hyper-Kloosterman 符号を定義することができる:

定義 2.1 Hyper-Kloosterman 符号 C_{m}(q) を, 写像

φ_{m} : F_{q}^{m} → F_{p}^{(q−1)^{m−1}},
φ_{m}(a) = {Tr (a, x)}_{x∈(F_{q}^{×})^{m−1}}

の像として定義する. ここで, a = (a_{1}, a_{2}, ⋯, a_{m}) ∈ F_{q}^{m}, x = (x_{1}, x_{2}, ⋯, x_{m−1}) ∈ (F_{q}^{×})^{m} に対して,

Tr (a, x) := tr (a_{1}x_{1} + a_{2}x_{2} + ⋯ a_{m−1}x_{m−1} + a_{m}(x_{1}x_{2} ⋯ x_{m−1})^{−1}).

上の記号 {Tr (a, x)}_{x∈(F_{q}^{×})^{m−1}} は, すべての x ∈ (F_{q}^{×})^{m−1} に対して Tr (a, x) を考え, それらを一列に並べた (q − 1)^{m−1} 次元行ベクトルを表している (この記法は trace code の文献でしばしば用いられている). C_{m}(q) は Chinen-Hiramatsu [4] で初めて定義された. M^{⊥} = C_{2}(q) であることは容易にわかり, したがって C_{m}(q) は M^{⊥} の自然な拡張になっている. また, 前節では, 多項式の根によって記述できる巡回符号について, その双対符号が trace code となること, そしてその Hamming 重さが (1 変数の) 指数和で表されることなどを見たが, C_{m}(q) の構成は, その「多変数化」の 1 つの試みである. 多変数化が符号のどのような性質に反映されるのか, C_{m}(q) という一例を調べるだけでも, かなり多くのことがわかる. この小節では, 以後の議論の基礎となる, Hamming 重さの表示式と生成行列について見ておく.

定理 2.2 φ_{m}(a) ∈ C_{m}(q) (a = (a_{1}, a_{2}, ⋯, a_{m})) の Hamming 重さを w(φ_{m}(a)) とすると,

w(φ_{m}(a)) = \frac{1}{p} \{(p − 1)(q − 1)^{m−1} − ∑_{b∈F_{p}^{×}} K_{m}(ba; q)\} ,

ただし, K_{m}(a; q) は hyper-Kloosterman 和:

K_{m}(a; q) = ∑_{x∈(F_{q}^{×})^{m−1}} e(Tr (a, x)).

証明定理 1.3 と全く同様である.

C_{m}(q) は trace code として定義されたが, 生成行列を具体的に書くことができる. そのために, F_{q} の原始元 α を固定し, (F_{q}^{×})^{m−1} のベクトルすべてに次のような番号づけをしよう:

f_{0} = (1, 1, ⋯, 1)  · · · · · ·
f_{1} = (α, 1, ⋯, 1)  f_{(q−1)^{2}} = (1, α^{2}, 1, ⋯, 1)
f_{2} = (α^{2}, 1, ⋯, 1)  · · · · · ·
· · · · · ·  f_{(q−1)^{m−2}} = (1, ⋯, 1, α)
f_{q−2} = (α^{q−2}, 1, ⋯, 1)  · · · · · ·
f_{q−1} = (1, α, 1, ⋯, 1)  f_{(q−1)^{m−1}−1} = (α^{q−2}, α^{q−2}, ⋯, α^{q−2}).
f_{q} = (α, α, 1, ⋯, 1)

また, x = (x_{1}, x_{2}, ⋯, x_{m−1}) ∈ (F_{q}^{×})^{m−1} に対し,

I(x) = (x_{1}x_{2} ⋯ x_{m−1})^{−1}

とおく. すると, 前節の議論 (とくに Delsarte の定理) によれば, C_{m}(q) の 1 つの生成行列 G_{m,q} が

G_{m,q} = ( \begin{matrix}f_{0}^{T} & f_{1}^{T} & ⋯ & f_{(q−1)^{m−1}−1}^{T} \\ I(f_{0}) & I(f_{1}) & ⋯ & I(f_{(q−1)^{m−1}−1}) \end{matrix} )

で与えられることがわかる. ただし, G_{m,q} の各成分に現れる F_{q}^{×} の元は, すべて F_{p} 上の列ベクトルと同一視する (したがって G_{m,q} は F_{p} の元を成分とする mr 行 (q − 1)^{m−1} 列の行列と考える).

例 2.3 C_{3}(4) の生成行列. α を F_{4} の原始元とする. このとき α^{3} = 1, α^{2} + α + 1 = 0 である. そして

G_{3,4} = ( \begin{matrix}1 & α & α^{2} & 1 & α & α^{2} & 1 & α & α^{2} \\ 1 & 1 & 1 & α & α & α & α^{2} & α^{2} & α^{2} \\ 1 & α^{−1} & α^{−2} & α^{−1} & α^{−2} & 1 & α^{−2} & 1 & α^{−1} \end{matrix} )

= ( \begin{matrix}1 & α & α^{2} & 1 & α & α^{2} & 1 & α & α^{2} \\ 1 & 1 & 1 & α & α & α & α^{2} & α^{2} & α^{2} \\ 1 & α^{2} & α & α^{2} & α & 1 & α & 1 & α^{2} \end{matrix} )

= ( \begin{matrix}1 & 0 & 1 & 1 & 0 & 1 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 & 1 & 1 & 0 & 1 & 1 \\ 1 & 1 & 1 & 0 & 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 1 & 1 & 0 & 1 & 0 & 1 \end{matrix} ) ,

ただし, F_{2} 上 1 = (1, 0)^{T}, α = (0, 1)^{T} and α^{2} = (1, 1)^{T} と表した. この生成行列から, 例えば C_{m}(q) の次元を知ることができる. 実際 G_{m,q} の, 素体 F_{p} 上の行列としての階数を計算することにより, 定理 2.4 m ≥ 2, r ≥ 2 のとき

dim C_{m}(p^{r}) = \{ \begin{matrix}2, & m = p = r = 2 のとき, \\ mr, & その他の場合. \end{matrix}

以下の小節で C_{m}(q) の種々の性質を見ていこう. 2.2 準巡回性

準巡回符号 (quasi-cyclic code) は, Townsend-Weldon [11] で導入されて以来, 海外では今も盛んに研究されている. まず定義を述べよう: 定義 2.5 s を自然数とする. 符号 C が s-準巡回的 (s- quasi-cyclic) とは,

c_{1}c_{2} ⋯ c_{n} ∈ C ⇒ c_{n−s+1} ⋯ c_{n}c_{1}c_{2} ⋯ c_{n−s} ∈ C

が任意の c_{1}c_{2} ⋯ c_{n} ∈ C に対して成り立つことである. 明らかに, s = 1 の場合が通常の巡回符号である. またこの性質は, 巡回性と同様, 座標の入れ換えでは保たれない性質である. C_{m}(q) は, さきに定義した G_{m,q} を生成行列とすることにより, 準巡回符号の構造が入る: 定理 2.6 C_{m}(q) は (q − 1)^{m−2}-準巡回符号である. 証明 C_{m}(q) から符号語

φ_{m}(a_{1}, a_{2}, ⋯, a_{m}) = (a_{1}, a_{2}, ⋯, a_{m})G_{m,q}

を取り, これの最後の (q − 1)^{m−2} 桁を先頭へ移し, 以下を順にずらしたベクトルを考える. すると簡単な計算により, それは

(a_{1}, a_{2}, ⋯, a_{m−2}, a_{m−1}α^{q−2}, a_{m}α^{−(q−2)})G_{m,q}

であることがわかる. これはもちろん C_{m}(q) の元である.

例 2.7 C_{3}(4). 生成行列として前述の G_{3,4} を取ると, C_{3}(4) の符号語は次のようになる:

重さ 0: 000000000

重さ 2: 000010001 000100010 000001100 010001000 100010000 001100000 001000010 010000100 100000001

重さ 4: 011100100 110001001 101010010 011001010 101100001 110010100 100100011 001001110 010010101 100001101 010100110 001010011 100011100 001110001 010101010 100110010 010011001 001101100 000101110 110000101 101110000 101000011 011101000 000011101 110011000 000110011 011000110

重さ 6: 110111010 101001111 101111100 011010111 110100111 011111001 000111111 111010110 001111101 010111011 111100101 111001011 100111110 111111000 111101001 010110111 100101111 111011010 001011111 111110100 111000111 011011011 110110110 101101101 011110101 101011110 110101011

これは q = 4, m = 3 の場合だから, 長さ 9 で, 3-準巡回的となる. 実際, 例えば重さ 2 の第 1 番目の語 000010001 の最後 3 桁を先頭へ移し, 以降を順にずらすと 001000010 となるが, これは第 7 番目の語に等しい. さらにこの語に同じ操作を行うと第 4 番目の 010001000 となる. これに再び同じ操作を行うと, 最初の 000010001 に戻る. 他の符号語に関しても同様で, 各符号語の最後 3 桁を先頭へ移し, 以降を順にずらしてできたベクトルはやはり符号語になっている.

さて, これで trace code の「多変数化」が符号の性質に与える影響の 1 つが見えてくる. つまり, 多項式の根で記述された巡回符号の双対には, その Hamming 重さに 1 変数の指数和が現れたが,

準巡回的 trace code の Hamming 重さは多変数指数和で表される

という一般的原則が見えるのである.

なお, 従来考えられてきた準巡回符号は, 符号化率 R が整数の逆数となるものである. しかし C_{m}(q) の場合は R = mr/(q − 1)^{m−1} であり, 違ったパラメータを持っている. これが符号の性能にどのように反映されるかを探ることは今後の課題である.

2.3 C_{m}(2^{r}) の重偶性

この小節では q = 2^{r} とする. したがって C_{m}(q) は F_{2} 上の符号である. このとき, ほとんどの C_{m}(q) は重偶 (doubly-even) となる. まず定義だが,

定義 2.8 符号 C が重偶 (doubly-even) とは, C の任意の符号語に対し, その Hamming 重さが 4 で割り切れることである.

また, 符号 C が重偶なら, それは自己直交的 (self-orthogonal), すなわち C ⊂ C^{⊥} であることも示される. ここでの最終目標は次の定理である:

定理 2.9 m ≥ 3 かつ r ≥ 3 なら, C_{m}(2^{r}) は重偶である.

これは次の定理の系として得られる:

定理 2.10 m ≥ 2, r ≥ 2 とする. 任意の x ∈ C_{m}(2^{r}) に対し,

min(2^{r−1}, 2^{m−1})|w(x).

ただし, w(x) は x の Hamming 重さを表す.

証明まず, hyper-Kloosterman 和 K_{m}(a; q) は, a = (a_{1}, a_{2}, ⋯, a_{m}) の成分のうち, 0 であるものが s 個 (s ≥ 1) あれば

K_{m}(a; q) = (−1)^{m−s}(q − 1)^{s−1},

a ∈ (F_{q}^{×})^{m} ならば

K_{m}(a; q) = K_{m}(a; q) = ∑_{{x_{i}∈F^{×}_{q} \atop x_{1}x_{2}···xm=a}} e(tr (x_{1} + x_{2} + ⋯ + x_{m}))

(a := a_{1}a_{2} ⋯ a_{m} ∈ F_{q}^{×}) となることが知られている (簡単な計算によりわかる. Chinen-Hiramatsu [4, §2] 参照). このことから, C_{m}(2^{r}) の符号語 x = φ_{m}(a) の Hamming 重さが取り得る値は, 次のいずれかである:

w_{s} = \frac{1}{2} \{(q − 1)^{m−1} + (−1)^{m−s+1}(q − 1)^{s−1}\} , (1 ≤ s ≤ m)  (2.1)
W_{a} = \frac{1}{2} \{(q − 1)^{m−1} − K_{m}(a; q)\} , (a ∈ F_{q}^{×}).  (2.2)

w(x) = w_{s} のときは, 具体的計算により 2^{r−1}|w(x) であることが示される. w(x) = W_{a} のとき, F_{q} の原始元 α をとり, a = α^{j} とおくと

K_{m}(a; q) = \frac{1}{q − 1} ∑_{k=0}^{q−2} ψ̄_{k}(α^{j})G(ψ_{k})^{m}

が成り立つ. ただし

ψ_{k}(α^{j}) = e^{2πikj/(q−1)} (F_{q} の乗法指標),
G(ψ_{k}) = ∑_{t=0}^{q−2} ψ_{k}(α^{t})e(tr (α^{t})) (ψ_{k} に対する Gauss 和).

これは有限体上の Fourier 解析における, K_{m}(a; q) の Fourier 逆変換である. これを用いると, ψ_{k} が単位指標のとき (⇔ k = 0), G(ψ_{0}) = −1 であることに注意して

(q − 1)K_{m}(a; q) = (−1)^{m} + ∑_{k=1}^{q−2} ψ̄_{k}(α^{j})G(ψ_{k})^{m}

が得られる. そこで 1 ≤ k ≤ q−2 に対して G(ψ_{k}) の整除を考える. いまの場合, e(1) = −1 だから,

G(ψ_{k}) = ∑_{0≤t≤q−2} ψ_{k}(α^{t}) − 2 ∑_{{0≤t≤q−2 \atop tr(α^{t})=1}} ψ_{k}(α^{t})

であることが簡単な計算によってわかるが, 第一の和は F_{q}^{×} 全体をわたる和で 0 となるから,

G(ψ_{k}) = −2 ∑_{{0≤t≤q−2 \atop tr(α^{t})=1}} ψ_{k}(α^{t}) ≡ 0 (mod 2).

ただし, 合同式は円分体 Q(ζ_{q−1}) の整数環におけるものである. これより

(q − 1)K_{m}(a; q) ≡ (−1)^{m} (mod 2^{m})

となるが, 左辺は定義によって有理整数だから, 合同式は Z におけるものとしてよく,

K_{m}(a; q) ≡ (−1)^{m−1} (mod min(2^{m}, 2^{r}))

が得られる. Hamming 重さに関する式はこれからただちに出る. 例 2.11 いくつかの C_{m}(2^{r}) について重さ分布を計算すると次のようになる:

\underline{r = 2}

C_{3}(2^{2}) (符号長 9) \begin{matrix}重さ & 0 & 2 & 4 & 6 & 計 \\ 個数 & 1 & 9 & 27 & 27 & 64 \end{matrix}

C_{4}(2^{2}) (符号長 27) \begin{matrix}重さ & 0 & 8 & 12 & 14 & 16 & 18 & 計 \\ 個数 & 1 & 27 & 54 & 108 & 54 & 12 & 256 \end{matrix}

C_{5}(2^{2}) (符号長 81) \begin{matrix}重さ & 0 & 30 & 36 & 40 & 42 & 46 & 54 & 計 \\ 個数 & 1 & 81 & 90 & 405 & 270 & 162 & 15 & 1024 \end{matrix}

\underline{r = 3}

C_{2}(2^{3}) (符号長 7) \begin{matrix}重さ & 0 & 2 & 4 & 6 & 計 \\ 個数 & 1 & 21 & 35 & 7 & 64 \end{matrix}

C_{3}(2^{3}) (符号長 49) \begin{matrix}重さ & 0 & 16 & 24 & 28 & 計 \\ 個数 & 1 & 49 & 294 & 168 & 512 \end{matrix}

C_{4}(2^{3}) (符号長 343) \begin{matrix}重さ & 0 & 160 & 168 & 172 & 184 & 196 & 計 \\ 個数 & 1 & 1029 & 637 & 1372 & 1029 & 28 & 4096 \end{matrix}

\underline{r = 4}

C_{2}(2^{4}) (符号長 15) \begin{matrix}重さ & 0 & 4 & 6 & 8 & 10 & 計 \\ 個数 & 1 & 30 & 60 & 105 & 60 & 256 \end{matrix}

C_{3}(2^{4}) (符号長 225) \begin{matrix}重さ & 0 & 96 & 108 & 112 & 116 & 120 & 計 \\ 個数 & 1 & 450 & 900 & 675 & 900 & 1170 & 4096 \end{matrix}

このように, r = 2 または m = 2 なら重偶でないものが実際に存在することもわかる.

一般標数の場合, (p − 1)|m という仮定のもとで K_{m}(a; q) ∈ Z かつ (q − 1)K_{m}(a; q) ≡ (−1)^{m} (mod p^{m/(p−1)})

が成り立ち, x ∈ C_{m}(q) に対して

min(p^{r−1}, p^{m/(p−1)−1})|w(x)

となる (Chinen-Hiramatsu [4, §4]). また, K_{m}(a; q) の Fourier 逆変換公式については, hyper-Kloosterman 和が満たす漸化式を用いた証明もある. これについては Chinen [3, Theorem 2.2] を参照.

2.4 その他の話題

この小節では研究集会終了後に新たにわかったことを, 結果のみ紹介する (詳しくは Chinen [2] 参照). ここでも q = 2^{r} とし, binary の場合を考える.

まず, C_{m}(q) の元の Hamming 重さは (2.1), (2.2) のように表せるから, K_{m}(a; q) に対する Deligne の評価

|K_{m}(a; q)| ≤ mq^{\frac{m−1}{2}}

を用いて, 最小距離を評価することができる:

定理 2.12 C_{m}(2^{r}) の最小距離を d(m, r) とすると, 次が成り立つ.

(i) r = 2, m ≥ 8; r = 3, m ≥ 5 または r ≥ 4, m ≥ 6 のとき

d(m, r) = \frac{1}{2} \{(2^{r} − 1)^{m−1} − (2^{r} − 1)^{m−3}\} .

(ii) r ≥ 2, 2 ≤ m ≤ 5 かつ (m, r) ≠ (2, 2) のとき

d(m, r) ≥ d̃(m, r) = \frac{1}{2} \{(2^{r} − 1)^{m−1} − m · 2^{\frac{(m−1)r}{2}} \} .

Deligne の評価は必ずしも best ではないが, ほとんどの場合 (上の定理の (i)), 最小距離は Deligne の評価が関係しない w_{s} のタイプの Hamming 重さで決まってしまうのである. なお, この定理を導くには, Deligne の評価だけでなく, 小さな m, q に対する K_{m}(a; q) の数値計算も必要である. そのためのアルゴリズムは Chinen [3] で論じられている. また, この結果を用いると, binary hyper-Kloosterman 符号は, よい符号の無限列を含むこともわかる:

定理 2.13 2 ≤ m ≤ 5 のとき, 各 m に対してある r_{m} ∈ N が存在し,

(C_{m}(2^{r}))_{r=r_{m}}^{∞}

は, Gilbert-Varshamov 限界を越える符号の無限列である.

C_{m}(2^{r}) では, m または r → ∞ のとき, (d/n, k/n) → (1/2, 0) となってしまうので, Manin の問題 ((d/n, k/n) の集積値集合が Gilbert-Varshamov 限界を越えるか) の立場からはあまり意味のある結果ではないかも知れないが, C_{m}(2^{r}) には比較的よい符号が存在することは, 少なくともわかる.

Hyper-Kloosterman 符号以外にも, 多項式の根で定義された種々の巡回符号について, その双対符号は同様の準巡回化が可能であり, それらは 1. 完全に具体的に構成できる (生成行列が具体的に書ける).

2. 符号長のきわめて長い符号が容易に構成できる.

3. 重さ分布が指数和を用いて具体的に表示できる.

4. 概して, 最小距離は大きい. などのさまざまな長所を持っており, 興味深い符号の一群である.

参考文献

[1] 知念宏司「有限体上の指数和計算アルゴリズム」 , 第 2 回「代数学と計算」研究集会 (東京都立大学) 報告集 (1997), ftp://ftp.math.metro-u.ac.jp/tnt/ac97

[2] K. Chinen; The hyper-Kloosterman code and the Gilbert-Varshamov bound, in preparation.

[3] ; Some applications of the recurrence relation of the hyper-Kloosterman sums, submitted for publication

[4] K. Chinen and T. Hiramatsu; Hyper-Kloosterman sums and their applications to the coding theory, submitted for publication

[5] T. Hiramatsu; Uniform distribution of the weights of the Kloosterman codes, SUT J. Math. 31-1 (1995), 29-32.

[6] G. Lachaud; Distribution of the weights of the dual of the Melas code, Discrete Math. 79 (1989/90), 103-106.

[7] R. Lidl and H. Niederreiter; Introduction to Finite Fields and Their Applications, Cambridge Univ. Press, 1994.

[8] F. J. MacWilliams and N. J. A. Sloane; The Theory of Error Correcting Codes, New York:North Holland, 1977.

[9] C. M. Melas; A cyclic code for double error correction, IBM J. Res. Devel. 4 (1960), 364-366.

[10] H. Stichtenoth; Algebraic Function Fields and Codes, Springer-Verlag, 1993.

[11] R. L. Townsend and E. L. Weldon, Jr., Self-orthogonal quasi-cyclic codes, IEEE Trans. Inform. Theory IT-13 no.2 (1967), 183-195.

[12] J. Wolfmann; The weights of the dual code of the Melas code over GF(3), Discrete Math. 74 (1989), 327-329.