# 重み多項式と MacWilliams 恒等式・Golay 符号：指標和で双対符号の重み分布を決める > 有限体の加法指標と離散版の Poisson 和公式から MacWilliams 恒等式を証明し、Hamming 符号と MDS 符号の重み分布を求める。二元・三元 Golay 符号を平方剰余符号として構成し、最小距離・完全性・重み多項式を決定する。 > https://rikai.mugen-giken.com/mathematics/finite-fields-coding/weight-enumerators-golay ## 0. この記事の要点 通信や記録で起きる誤りを見つけて直すための「符号」について、符号語を重み（0 でない成分の個数）ごとに数えた表がどんな性質をもつかを調べます。ある符号の表から、その双対符号の表が計算だけで決まる、という驚くほど便利な関係を証明します。後半では、その関係を使って、23 ビットの語のうち 12 ビット分を情報にでき、しかも 3 か所までの誤りを必ず直せる Golay 符号の表を完全に求めます。 - 符号 $C$ の重みごとの符号語の個数 $A_i$ を係数に並べた斉次多項式 $W_C(x, y) = \sum_i A_i x^{n-i}y^i$ を**重み多項式**といいます。**MacWilliams 恒等式** $W_{C^{\perp}}(x, y) = |C|^{-1}W_C(x + (q-1)y,\ x - y)$ は、$C$ の重み分布だけから[双対符号](/mathematics/finite-fields-coding/linear-codes#def-dual-code)の重み分布が決まることを述べます。 - 証明は、$\mathbb{F}_q^n$ の上の離散 Fourier 変換についての **Poisson 和公式** $\sum_{u \in C^{\perp}} f(u) = |C|^{-1}\sum_{c \in C}\hat f(c)$ に、$f(v) = x^{n - \operatorname{wt}(v)}y^{\operatorname{wt}(v)}$ を代入するだけです。$\hat f$ は座標ごとの積に分かれて計算できます。 - [MDS 符号](/mathematics/finite-fields-coding/linear-codes#def-ball-volume)の重み分布は $n, k, q$ だけで決まります（包除原理）。[Hamming 符号](/mathematics/finite-fields-coding/linear-codes#def-hamming-code)の重み多項式は、双対の[単体符号](/mathematics/finite-fields-coding/linear-codes#def-hamming-code)から MacWilliams 恒等式で求まります。 - **二元 Golay 符号** $G_{23}$ は $x^{23} - 1$ の 11 次の既約因子が生成する[巡回符号](/mathematics/finite-fields-coding/cyclic-bch-reed-solomon#def-cyclic-code)で、$[23, 12, 7]_2$ の[完全符号](/mathematics/finite-fields-coding/linear-codes#def-ball-volume)（符号語を中心とする同じ半径の球で、空間を重なりも隙間もなく埋める符号）です。[パリティ拡大](/mathematics/finite-fields-coding/linear-codes#def-code-modifications)した $G_{24}$ は $[24, 12, 8]_2$ の自己双対な重偶符号で、重み多項式は $1 + 759y^8 + 2576y^{12} + 759y^{16} + y^{24}$ です。 - **三元 Golay 符号** $G_{11}$ は $[11, 6, 5]_3$ の完全符号、$G_{12}$ は $[12, 6, 6]_3$ の自己双対符号です。 - 符号が完全であることは、被覆半径（どの語も、どれかの符号語から距離いくつ以内にあるかの最小値）が $\lfloor (d-1)/2 \rfloor$ に等しいことと同値です。距離分布の Krawtchouk 変換は非負で（Delsarte の不等式）、これは線形でない符号にも使える限界式の出発点になります。 ## 1. 動機 [第 3 章](/mathematics/finite-fields-coding/linear-codes) では符号の性能を最小距離 $d$ という 1 つの数で測りました。しかし、誤りを見逃す確率や復号を誤る確率を計算するには、「重み $i$ の符号語が何個あるか」という分布全体が必要です。たとえば二元対称通信路（誤り率 $p$）で誤りが検出されないのは、誤りパターンがちょうど $0$ でない符号語に一致するときで、その確率は $\sum_{i \ge 1} A_i p^i(1-p)^{n-i}$ です。 重み分布を符号語の列挙で求めるには $q^k$ 個の語を調べる必要があります。ところが MacWilliams（1963）は、$C$ の重み分布と $C^{\perp}$ の重み分布が、符号の詳細によらない 1 つの線形変換で結ばれていることを発見しました。次元の大きい符号の重み分布を、次元の小さい双対符号から計算できるわけです。さらに、$C = C^{\perp}$ となる自己双対符号では、この恒等式が重み多項式に強い制約を課します。 その制約がもっとも劇的に効くのが **Golay 符号**です。Golay（1949）は、$1 + \binom{23}{1} + \binom{23}{2} + \binom{23}{3} = 2^{11}$ という数の一致に気づき、半径 $3$ の球で $\mathbb{F}_2^{23}$ を隙間なく埋める符号を見つけました。この章では、[第 4 章](/mathematics/finite-fields-coding/cyclic-bch-reed-solomon) の巡回符号の理論でこの符号を構成し、最小距離を決め、MacWilliams 恒等式で重み分布を完全に求めます。 この章が前の章のどの定理に乗っているかを先にまとめます。 | この章の定理 | 使う前の章の定理 | |---|---| | 加法指標（） | 第 2 章のトレースの線形性・全射性、トレース形式の非退化性 | | MacWilliams 恒等式（） | 第 3 章の $(C^{\perp})^{\perp} = C$ と $\dim C^{\perp} = n - k$ | | MDS 符号の重み分布（） | 第 4 章の MDS 符号の特徴づけ | | Golay 符号（、） | 第 2 章の $x^n - 1$ の分解、第 4 章の BCH 限界と双対符号の定義集合、第 3 章の Hamming 限界 | ## 2. 指標と離散 Fourier 変換 ### 2.1. 加法指標 有限アーベル群 $A$（演算を加法で書く）の**指標**とは、$A$ から乗法群 $\mathbb{C}^{\times}$ への群準同型 $\chi$、すなわち $\chi(a + b) = \chi(a)\chi(b)$ を満たす写像 $\chi : A \to \mathbb{C}^{\times}$ をいう。指標の全体は、値ごとの積で群をなす。これを $A$ の**双対群**といい $\widehat{A}$ と書く。つねに $1$ を取る指標を**自明な指標**という。 $|A| = N$ とすると $\chi(a)^{N} = \chi(Na) = \chi(0) = 1$ なので、指標の値は $1$ の $N$ 乗根で、絶対値は $1$、$\overline{\chi(a)} = \chi(a)^{-1} = \chi(-a)$ です。 $\mathbb{F}_q$ の標数を $p$ とし、$\operatorname{Tr} = \operatorname{Tr}_{\mathbb{F}_q/\mathbb{F}_p} : \mathbb{F}_q \to \mathbb{F}_p$ を第 2 章のトレースとします。$\mathbb{F}_p = \mathbb{Z}/p\mathbb{Z}$ の元 $t$ に対して $e^{2\pi i t/p}$ は代表元の取り方によらずに定まります。 $a \in \mathbb{F}_q$ に対し $$ \psi_a(x) = \exp\!\Bigl(\frac{2\pi i}{p}\operatorname{Tr}(ax)\Bigr) \qquad (x \in \mathbb{F}_q) $$ と定める。$\psi = \psi_1$ を $\mathbb{F}_q$ の**標準的な加法指標**という。$\psi_a(x) = \psi(ax)$ である。 1. 各 $\psi_a$ は加法群 $(\mathbb{F}_q, +)$ の指標である。 2. $a \in \mathbb{F}_q$ について $$ \sum_{x \in \mathbb{F}_q}\psi(ax) = \begin{cases} q & (a = 0) \\ 0 & (a \ne 0) \end{cases} $$ が成り立つ。とくに $a \ne 0$ なら $\sum_{x \ne 0}\psi(ax) = -1$。 3. $a \mapsto \psi_a$ は単射で、$(\mathbb{F}_q, +)$ の指標は $\psi_a$（$a \in \mathbb{F}_q$）の $q$ 個で尽くされる。 (1) トレースは加法的なので（）$\operatorname{Tr}(a(x+y)) = \operatorname{Tr}(ax) + \operatorname{Tr}(ay)$ で、指数関数の性質から $\psi_a(x + y) = \psi_a(x)\psi_a(y)$ です。 (2) $a = 0$ なら各項が $1$ です。$a \ne 0$ とします。トレース形式 $(x, y) \mapsto \operatorname{Tr}(xy)$ は非退化なので（）、$\operatorname{Tr}(ay_0) \ne 0$ となる $y_0 \in \mathbb{F}_q$ があり、$\psi(ay_0) \ne 1$ です。$x \mapsto x + y_0$ は $\mathbb{F}_q$ の全単射なので $$ \sum_{x}\psi(ax) = \sum_{x}\psi(a(x + y_0)) = \psi(ay_0)\sum_{x}\psi(ax) $$ で、$(1 - \psi(ay_0))\sum_x\psi(ax) = 0$ から和は $0$ です。$x = 0$ の項 $1$ を除けば $-1$ です。 (3) $\psi_a = \psi_b$ なら $\psi_{a-b}(x) = \psi_a(x)\overline{\psi_b(x)} = 1$ がすべての $x$ で成り立ち、(2) の和が $q \ne 0$ になるので $a = b$ です。よって $\psi_a$ は相異なる $q$ 個の指標です。 指標が $q$ 個以下であることを示します。$\chi \ne \chi'$ を $(\mathbb{F}_q, +)$ の指標とすると、$\theta = \chi\overline{\chi'}$ は自明でない指標で、$\theta(y_0) \ne 1$ となる $y_0$ を取って (2) と同じ計算をすると $\sum_x\chi(x)\overline{\chi'(x)} = 0$ です。また $\sum_x\chi(x)\overline{\chi(x)} = q$ です。相異なる指標 $\chi_1, \ldots, \chi_r$ が $\sum_j\lambda_j\chi_j = 0$（$\lambda_j \in \mathbb{C}$）を満たせば、$\overline{\chi_l(x)}$ を掛けて $x$ について和を取ると $q\lambda_l = 0$ なので、指標は $\mathbb{F}_q$ 上の複素数値関数の空間（$q$ 次元）の中で一次独立です。したがって $r \le q$ です。 一般の有限アーベル群でも $|\widehat{A}| = |A|$ が成り立ち（ がその形です）、指標の直交関係は [有限群の表現](/mathematics/algebra/group-representations) の一般論の特別な場合です。有限体では、トレース形式のおかげで双対群 $\widehat{\mathbb{F}_q}$ が $\mathbb{F}_q$ 自身と $a \leftrightarrow \psi_a$ で同一視できる点が重要です。 ### 2.2. 部分空間の上の指標和 $u, v \in \mathbb{F}_q^n$ に対し $u \cdot v = \sum_i u_iv_i$ とします。$v \mapsto \psi(u \cdot v)$ は $\mathbb{F}_q^n$ の指標です。 $C \subseteq \mathbb{F}_q^n$ を部分空間、$u \in \mathbb{F}_q^n$ とすると $$ \sum_{c \in C}\psi(c \cdot u) = \begin{cases} |C| & (u \in C^{\perp}) \\ 0 & (u \notin C^{\perp}) \end{cases} $$ が成り立つ。 $u \in C^{\perp}$ なら各項が $\psi(0) = 1$ です。$u \notin C^{\perp}$ とすると、$c_1 \cdot u = \beta \ne 0$ となる $c_1 \in C$ があります。 の 2 の証明で見たとおり $\psi(\beta y_0) \ne 1$ となる $y_0 \in \mathbb{F}_q$ があるので、$c_0 = y_0c_1 \in C$ とおくと $\psi(c_0 \cdot u) = \psi(y_0\beta) \ne 1$ です。$c \mapsto c + c_0$ は $C$ の全単射なので $$ \sum_{c \in C}\psi(c \cdot u) = \sum_{c \in C}\psi((c + c_0)\cdot u) = \psi(c_0 \cdot u)\sum_{c \in C}\psi(c \cdot u) $$ となり、和は $0$ です。 ### 2.3. 離散 Fourier 変換と Poisson 和公式 $V$ を複素ベクトル空間とする。関数 $f : \mathbb{F}_q^n \to V$ の**離散 Fourier 変換**（$q = 2$ のときは **Hadamard 変換**という）$\hat f : \mathbb{F}_q^n \to V$ を $$ \hat f(u) = \sum_{v \in \mathbb{F}_q^n}\psi(u \cdot v)\,f(v) $$ で定める。 $C \subseteq \mathbb{F}_q^n$ を部分空間、$f : \mathbb{F}_q^n \to V$ を複素ベクトル空間 $V$ に値をもつ関数とすると $$ \sum_{u \in C^{\perp}} f(u) = \frac{1}{|C|}\sum_{c \in C}\hat f(c) $$ が成り立つ。 有限和の順序を交換し、 を使います。 $$ \sum_{c \in C}\hat f(c) = \sum_{c \in C}\sum_{v \in \mathbb{F}_q^n}\psi(c \cdot v)f(v) = \sum_{v \in \mathbb{F}_q^n}f(v)\sum_{c \in C}\psi(c \cdot v) = |C|\sum_{v \in C^{\perp}}f(v). $$ 実数直線の Poisson 和公式 $\sum_{n \in \mathbb{Z}}f(n) = \sum_{m \in \mathbb{Z}}\hat f(m)$（）と見比べてください。格子 $\mathbb{Z}$ の役割を部分空間 $C$ が、双対格子の役割を $C^{\perp}$ が果たしています。有限の場合は収束の問題がなく、証明は和の交換だけです。 ## 3. 重み多項式と MacWilliams 恒等式 ### 3.1. 重み多項式 符号 $C \subseteq \mathbb{F}_q^n$ に対し、$A_i = \#\{ c \in C : \operatorname{wt}(c) = i \}$（$0 \le i \le n$）とおく。列 $(A_0, A_1, \ldots, A_n)$ を $C$ の**重み分布**、 $$ W_C(x, y) = \sum_{c \in C}x^{n - \operatorname{wt}(c)}y^{\operatorname{wt}(c)} = \sum_{i=0}^{n}A_i\,x^{n-i}y^i $$ を $C$ の**重み多項式**という。 線形符号では $A_0 = 1$、$A_i = 0$（$1 \le i < d$）、$W_C(1, 1) = |C|$ です。$x = 1$ とおいた $W_C(1, y) = \sum_iA_iy^i$ を使うこともあります。 ### 3.2. 重みの関数の Fourier 変換 次の補題は、MacWilliams 恒等式の証明に必要な計算を先に済ませておくものです。重みは座標ごとの 0 か 0 でないかで決まり、指標 $\psi(u \cdot v)$ も座標ごとの積なので、全体の和が座標ごとの和の積に分かれます。たとえば $n = 2$ なら $\sum_{a, b}F(a)G(b) = \bigl(\sum_aF(a)\bigr)\bigl(\sum_bG(b)\bigr)$ という、展開の逆向きの変形を $n$ 個の座標に使うだけです。 $v \in \mathbb{F}_q^n$ に対し、$\mathbb{C}[x, y]$ の中で $$ \sum_{u \in \mathbb{F}_q^n}\psi(u \cdot v)\,x^{n - \operatorname{wt}(u)}y^{\operatorname{wt}(u)} = \bigl(x + (q-1)y\bigr)^{n - \operatorname{wt}(v)}(x - y)^{\operatorname{wt}(v)} $$ が成り立つ。 $a \in \mathbb{F}_q$ に対し、$\phi(a) = x$（$a = 0$）、$\phi(a) = y$（$a \ne 0$）とおくと、$x^{n - \operatorname{wt}(u)}y^{\operatorname{wt}(u)} = \prod_{i=1}^{n}\phi(u_i)$ です。$\psi(u \cdot v) = \prod_i\psi(u_iv_i)$ なので、左辺は座標ごとの和の積に分かれます。 $$ \sum_{u \in \mathbb{F}_q^n}\prod_{i=1}^n\psi(u_iv_i)\phi(u_i) = \prod_{i=1}^{n}\Bigl(\sum_{a \in \mathbb{F}_q}\psi(av_i)\phi(a)\Bigr). $$ 各因子は、$v_i = 0$ なら $\sum_a\phi(a) = x + (q-1)y$、$v_i \ne 0$ なら $x + y\sum_{a \ne 0}\psi(av_i) = x - y$（ の 2）です。$v_i \ne 0$ となる $i$ は $\operatorname{wt}(v)$ 個です。 ### 3.3. MacWilliams 恒等式 線形符号 $C \subseteq \mathbb{F}_q^n$ について $$ W_{C^{\perp}}(x, y) = \frac{1}{|C|}\,W_C\bigl(x + (q-1)y,\ x - y\bigr) $$ が成り立つ。 $f : \mathbb{F}_q^n \to \mathbb{C}[x, y]$ を $f(v) = x^{n - \operatorname{wt}(v)}y^{\operatorname{wt}(v)}$ とします。 は $$ \hat f(u) = \bigl(x + (q-1)y\bigr)^{n - \operatorname{wt}(u)}(x - y)^{\operatorname{wt}(u)} $$ を述べています（補題の $u$ と $v$ の役割を入れ替えたもの）。Poisson 和公式（）の左辺は $\sum_{u \in C^{\perp}}f(u) = W_{C^{\perp}}(x, y)$、右辺は $$ \frac{1}{|C|}\sum_{c \in C}\bigl(x + (q-1)y\bigr)^{n - \operatorname{wt}(c)}(x - y)^{\operatorname{wt}(c)} = \frac{1}{|C|}W_C\bigl(x + (q-1)y,\ x - y\bigr) $$ です。 恒等式を係数で書くために、次の多項式を導入します。 $n \ge 1$、$q \ge 2$ を固定する。$0 \le k \le n$ に対し、**Krawtchouk 多項式** $K_k$ を $$ K_k(i) = \sum_{j=0}^{k}(-1)^j(q-1)^{k-j}\binom{i}{j}\binom{n-i}{k-j} \qquad (0 \le i \le n) $$ で定める（$\binom{a}{b}$ は $b > a$ のとき $0$）。 線形符号 $C \subseteq \mathbb{F}_q^n$ の重み分布を $(A_i)$、$C^{\perp}$ の重み分布を $(A_k^{\perp})$ とすると $$ A_k^{\perp} = \frac{1}{|C|}\sum_{i=0}^{n}A_i\,K_k(i) \qquad (0 \le k \le n) $$ が成り立つ。また、$v \in \mathbb{F}_q^n$ に対し $\sum_{u :\, \operatorname{wt}(u) = k}\psi(u \cdot v) = K_k(\operatorname{wt}(v))$ である。 二項定理（）で展開すると $$ \bigl(x + (q-1)y\bigr)^{n-i}(x - y)^{i} = \sum_{l}\binom{n-i}{l}(q-1)^{l}x^{n-i-l}y^{l}\cdot\sum_{j}\binom{i}{j}(-1)^jx^{i-j}y^{j} $$ で、$x^{n-k}y^{k}$ の係数は $l + j = k$ となる項の和 $\sum_j(-1)^j(q-1)^{k-j}\binom{i}{j}\binom{n-i}{k-j} = K_k(i)$ です。 の両辺の $x^{n-k}y^k$ の係数を比べると第 1 の式が、 の両辺の $x^{n-k}y^k$ の係数を比べると第 2 の式が得られます。 $K_0(i) = 1$、$K_1(i) = (q-1)(n - i) - i = (q-1)n - qi$ です。$k = 0$ の式は $1 = |C|^{-1}\sum_iA_i$、つまり符号語の総数の勘定です。 二元 $[7, 4, 3]$ Hamming 符号 $C$ の双対は $[7, 3, 4]$ 単体符号で、$0$ でない 7 語の重みはすべて $4$ です（）。つまり $W_{C^{\perp}} = x^7 + 7x^3y^4$ です。$(C^{\perp})^{\perp} = C$ なので、恒等式を $C^{\perp}$ に使って $$ W_C = \frac{1}{8}\Bigl[(x+y)^7 + 7(x+y)^3(x-y)^4\Bigr] $$ です。$(x+y)^3(x-y)^4 = (x^2 - y^2)^3(x - y) = x^7 - x^6y - 3x^5y^2 + 3x^4y^3 + 3x^3y^4 - 3x^2y^5 - xy^6 + y^7$ と $(x+y)^7$ の二項展開を足すと、$x^6y$、$x^5y^2$、$x^2y^5$、$xy^6$ の係数はそれぞれ $7 - 7$、$21 - 21$、$21 - 21$、$7 - 7$ で消え、 $$ W_C = \frac{1}{8}\bigl(8x^7 + 56x^4y^3 + 56x^3y^4 + 8y^7\bigr) = x^7 + 7x^4y^3 + 7x^3y^4 + y^7 $$ です。重み $3$ の語が $7$ 個、重み $4$ が $7$ 個、全 $1$ の語が $1$ 個で、合計 $16 = 2^4$ です。 逆向きも確かめます。$W_C$ から出発すると、係数表示で $A_1^{\perp} = \frac{1}{16}\sum_iA_iK_1(i)$、$K_1(i) = 7 - 2i$ なので $\frac{1}{16}(7 + 7\cdot 1 + 7\cdot(-1) + (-7)) = 0$ で、単体符号に重み $1$ の語がないことと合います。 $r \ge 2$、$n = (q^r - 1)/(q - 1)$ とする。$[n, n-r, 3]_q$ Hamming 符号 $C$ の重み多項式は $$ W_C(x, y) = \frac{1}{q^r}\Bigl[\bigl(x + (q-1)y\bigr)^{n} + (q^r - 1)\bigl(x + (q-1)y\bigr)^{n - q^{r-1}}(x - y)^{q^{r-1}}\Bigr] $$ である。 $C^{\perp}$ は単体符号で、$0$ でない $q^r - 1$ 個の符号語の重みはすべて $q^{r-1}$ です（）。よって $W_{C^{\perp}} = x^n + (q^r - 1)x^{n - q^{r-1}}y^{q^{r-1}}$ です。$(C^{\perp})^{\perp} = C$（）なので、 を $C^{\perp}$（元の個数 $q^r$）に使えば主張の式になります。 $[7, 4, 3]$ Hamming 符号にパリティ検査ビットを足した $[8, 4, 4]$ 拡大 Hamming 符号 $\widehat{C}$ は自己双対です（第 3 章）。重み $3$ の語は重み $4$ に、重み $7$ の語は重み $8$ になるので $W_{\widehat C} = x^8 + 14x^4y^4 + y^8$ です。自己双対なので、恒等式は $W(x, y) = \frac{1}{16}W(x + y, x - y)$ という不変性を要求します。確かめると $$ (x+y)^8 + (x-y)^8 = 2\bigl(x^8 + 28x^6y^2 + 70x^4y^4 + 28x^2y^6 + y^8\bigr), \qquad 14(x^2 - y^2)^4 = 14\bigl(x^8 - 4x^6y^2 + 6x^4y^4 - 4x^2y^6 + y^8\bigr) $$ の和は $16x^8 + 224x^4y^4 + 16y^8$ で、$16$ で割ると元に戻ります。 ## 4. MDS 符号の重み分布 MDS 符号では、重み分布が符号の作り方によらず、パラメータだけで決まります。 $1 \le k \le n-1$ とし、$C$ を $[n, k, d]_q$ MDS 符号（$d = n - k + 1$）とする。$d \le w \le n$ に対し $$ A_w = \binom{n}{w}\sum_{j=0}^{w-d}(-1)^j\binom{w}{j}\bigl(q^{\,w-d+1-j} - 1\bigr) $$ が成り立つ。とくに $A_d = \binom{n}{d}(q - 1)$。 証明の方針は次のとおりです。まず、台（0 でない成分の位置の集合）が座標の集合 $S$ に含まれる符号語の個数を、MDS の性質から $S$ の大きさだけで書きます。次に、台がちょうど $S$ になる語の個数を、包除原理で「含まれる」個数から引き算して求めます。 座標の集合 $S \subseteq \{1, \ldots, n\}$ に対し、$C(S) = \{ c \in C : c_i = 0\ (i \notin S) \}$ とおきます。これは $C$ の部分空間です。 **$|C(S)|$ の計算。** $|S| = s$ とし、$C$ から $S$ の外の $n - s$ 個の座標への射影を $\rho_S : C \to \mathbb{F}_q^{n-s}$ とすると、$C(S) = \ker\rho_S$ です。生成行列 $G$ のどの $k$ 列も一次独立です（）。$n - s \ge k$ なら、$S$ の外の座標から $k$ 個を選ぶと、そこで $0$ になる符号語 $uG$ は $u = 0$ だけなので $C(S) = \{0\}$ です。$n - s \le k$ なら、$S$ の外の $n - s$ 列は一次独立なので $\rho_S$（$u \mapsto uG$ を $S$ の外に制限した写像）の階数は $n - s$ で、次元定理（）から $\dim C(S) = k - (n - s) = s - d + 1$ です。まとめると $$ |C(S)| = q^{\max(0,\ |S| - d + 1)}. $$ **台がちょうど $S$ の符号語の個数。** $|S| = w \ge d$ とします。$X = C(S)$、$i \in S$ に対し $X_i = \{ c \in C(S) : c_i = 0 \} = C(S \setminus \{i\})$ とおくと、$U \subseteq S$ に対し $\bigcap_{i \in U}X_i = C(S \setminus U)$ です。台がちょうど $S$ である符号語の集合は $X \setminus \bigcup_{i \in S}X_i$ なので、包除原理（）により、その個数は $$ \sum_{U \subseteq S}(-1)^{|U|}\,|C(S \setminus U)| = \sum_{j=0}^{w}(-1)^j\binom{w}{j}q^{\max(0,\ w - j - d + 1)} $$ です。$w \ge 1$ なので $\sum_{j=0}^w(-1)^j\binom{w}{j} = (1 - 1)^w = 0$ で、各項から $1$ を引いても和は変わりません。$j > w - d$ の項は $q^0 - 1 = 0$ になるので、和は $\sum_{j=0}^{w-d}(-1)^j\binom{w}{j}(q^{w-d+1-j} - 1)$ です。 $w$ 元集合 $S$ は $\binom{n}{w}$ 個あり、上の個数は $S$ によらないので、主張の式が得られます。$w = d$ では $j = 0$ の項だけで $q - 1$ です。 $A_d = \binom{n}{d}(q-1)$ は、「どの $d$ 個の座標を選んでも、そこをちょうど台とする符号語が定数倍を除いて 1 つある」ことを意味します。 $n = 7$、$k = 3$、$d = 5$、$q = 8$ です。 $$ \begin{aligned} A_5 &= \binom{7}{5}(8 - 1) = 21 \cdot 7 = 147, \\ A_6 &= \binom{7}{6}\bigl[(8^2 - 1) - 6(8 - 1)\bigr] = 7 \cdot 21 = 147, \\ A_7 &= (8^3 - 1) - 7(8^2 - 1) + 21(8 - 1) = 511 - 441 + 147 = 217. \end{aligned} $$ 合計は $1 + 147 + 147 + 217 = 512 = 8^3$ で、符号語の総数と合います。 ## 5. 自己双対符号と Golay 符号 ### 5.1. 偶符号と重偶符号 二元符号 $C$ は、すべての符号語の重みが偶数のとき**偶符号**、すべての符号語の重みが $4$ の倍数のとき**重偶符号**という。 二元の語 $u, v$ について、$u$ と $v$ がともに $1$ である座標の個数を $|u \cap v|$ と書くと、$\operatorname{wt}(u + v) = \operatorname{wt}(u) + \operatorname{wt}(v) - 2|u \cap v|$ で、$u \cdot v = |u \cap v| \bmod 2$ です。とくに $u \cdot u = \operatorname{wt}(u) \bmod 2$ なので、二元の自己直交符号（$C \subseteq C^{\perp}$）は偶符号です。 二元符号 $C$ が $v_1, \ldots, v_k$ で張られ、すべての $i, j$ について $v_i \cdot v_j = 0$、すべての $i$ について $\operatorname{wt}(v_i) \equiv 0 \pmod 4$ ならば、$C$ は自己直交な重偶符号である。 双線形性から、$v_i$ の一次結合どうしの $\cdot$ も $0$ なので $C \subseteq C^{\perp}$ です。$C$ の元は $v_{i_1} + \cdots + v_{i_s}$ と書けます。項の数 $s$ についての帰納法で重みが $4$ の倍数であることを示します。$s = 0, 1$ は仮定です。$u = v_{i_1} + \cdots + v_{i_{s-1}}$ の重みが $4$ の倍数だとすると、$u \cdot v_{i_s} = 0$ から $|u \cap v_{i_s}|$ は偶数で、 $$ \operatorname{wt}(u + v_{i_s}) = \operatorname{wt}(u) + \operatorname{wt}(v_{i_s}) - 2|u \cap v_{i_s}| \equiv 0 \pmod 4 $$ です。 ### 5.2. 平方剰余符号 Golay 符号は、次の系列の最初の例として現れます。$p$ を奇素数、$q$ を $p$ と異なる素数で $p$ を法として平方剰余であるもの（）とします。$\mathcal{Q} \subseteq (\mathbb{Z}/p\mathbb{Z})^{\times}$ を平方剰余の全体、$\mathcal{N}$ を平方非剰余の全体とすると、$|\mathcal{Q}| = |\mathcal{N}| = (p-1)/2$ です。Legendre 記号は乗法的なので（）、$\mathcal{Q}$ は $q$ 倍で閉じています。つまり $\mathcal{Q}$ と $\mathcal{N}$ は $p$ を法とする $q$-円分剰余類の合併です。$\alpha$ を $\mathbb{F}_q$ の拡大体の中の 1 の原始 $p$ 乗根とします。 上の設定で、定義集合 $\mathcal{Q}$ の長さ $p$ の $\mathbb{F}_q$ 上の巡回符号を**平方剰余符号**という。次元は $p - |\mathcal{Q}| = (p+1)/2$ である。 の平方剰余符号を $Q$ とし、$p \equiv 3 \pmod 4$ とする。 1. $Q^{\perp} = Q_0$、ただし $Q_0 = \{ c \in Q : \sum_ic_i = 0 \}$ は定義集合 $\mathcal{Q} \cup \{0\}$ の巡回符号である。とくに $Q^{\perp} \subseteq Q$。 2. さらに $p \equiv -1 \pmod q$ とする。拡大符号 $\widehat{Q} = \{ (c_0, \ldots, c_{p-1}, c_{\infty}) : c \in Q,\ c_{\infty} = -\sum_ic_i \}$ は自己双対な $[p+1, (p+1)/2]_q$ 符号である。 (1) $p \equiv 3 \pmod 4$ なので $-1$ は平方非剰余で（）、Legendre 記号の乗法性から $-\mathcal{N} = \mathcal{Q}$ です。$Q$ の定義集合の補集合は $\{0\} \cup \mathcal{N}$ なので、$Q^{\perp}$ の定義集合は $\{0\} \cup (-\mathcal{N}) = \{0\} \cup \mathcal{Q}$ です（）。指数 $0$ が零点であることは $c(\alpha^0) = c(1) = \sum_ic_i = 0$ を意味するので（）、$Q^{\perp} = Q_0$ です。 (2) 全成分が $1$ の語 $\boldsymbol{j}$ は多項式 $1 + x + \cdots + x^{p-1} = (x^p - 1)/(x - 1)$ に対応し、$\alpha^i$（$i \ne 0$）で $0$ なので $\boldsymbol{j} \in Q$ です。$\sum_i\boldsymbol{j}_i = p \equiv -1 \ne 0$（$\mathbb{F}_q$ の中で）なので $\boldsymbol{j} \notin Q_0$ で、$\dim Q_0 = (p-1)/2 = \dim Q - 1$ から $Q = Q_0 \oplus \langle\boldsymbol{j}\rangle$ です。よって $\widehat{Q}$ は、$(c, 0)$（$c \in Q_0$）と $(\boldsymbol{j}, -p) = (\boldsymbol{j}, 1)$ で張られます。これらの間の $\cdot$ を計算します。 - $c, c' \in Q_0$ なら $(c, 0)\cdot(c', 0) = c \cdot c' = 0$（$c \in Q^{\perp}$、$c' \in Q$ だから）。 - $c \in Q_0$ なら $(c, 0)\cdot(\boldsymbol{j}, 1) = \sum_ic_i = 0$。 - $(\boldsymbol{j}, 1)\cdot(\boldsymbol{j}, 1) = p + 1 = 0$（$p \equiv -1 \pmod q$ だから）。 よって $\widehat{Q} \subseteq \widehat{Q}^{\perp}$ です。$\dim\widehat{Q} = \dim Q = (p+1)/2$、$\dim\widehat{Q}^{\perp} = (p + 1) - (p+1)/2 = (p+1)/2$（）なので、$\widehat{Q} = \widehat{Q}^{\perp}$ です。 次の補題は、$G_{23}$ の最小距離を決めるための道具です。語 $c$ とその「逆向きの語」$\tilde c$ の積を考えると、$c$ の零点と $\tilde c$ の零点を合わせて $1, \ldots, p-1$ のすべてが零点になり、積は全成分が等しい語に限られます。その積の係数が $w^2$ 個の項から作られることを数えると、$w$ の下からの評価が出ます。 の平方剰余符号 $Q$ で $p \equiv 3 \pmod 4$ とする。$c \in Q$ が $\sum_ic_i \ne 0$ を満たせば、$w = \operatorname{wt}(c)$ は $$ w^2 - w + 1 \ge p $$ を満たす。 $R_p = \mathbb{F}_q[x]/(x^p - 1)$ の中で $\tilde c(x) = c(x^{-1}) = \sum_ic_ix^{p-i}$ とおきます（$x^{-1} = x^{p-1}$）。$\tilde c(\alpha^{i}) = c(\alpha^{-i})$ なので、$\tilde c$ は $-i \in \mathcal{Q}$、すなわち $i \in -\mathcal{Q} = \mathcal{N}$ となる $\alpha^i$ で $0$ です。したがって積 $c\tilde c \in R_p$ は、$i \in \mathcal{Q} \cup \mathcal{N} = \{1, \ldots, p-1\}$ のすべてで $\alpha^i$ を零点にもちます。定義集合 $\{1, \ldots, p-1\}$ の巡回符号は生成多項式 $\prod_{i=1}^{p-1}(x - \alpha^i) = 1 + x + \cdots + x^{p-1}$ の $1$ 次元の符号なので（）、$c\tilde c = \lambda(1 + x + \cdots + x^{p-1})$ となる $\lambda \in \mathbb{F}_q$ があります。 $x \mapsto 1$ は $R_p$ から $\mathbb{F}_q$ への環準同型を定めます（$x^p - 1$ が $0$ に写るから）。両辺を写すと $c(1)\tilde c(1) = c(1)^2 = \lambda p$ で、仮定 $c(1) = \sum_ic_i \ne 0$ から $\lambda \ne 0$ です。よって $c\tilde c$ の $p$ 個の係数はすべて $0$ でありません。 一方、$c\tilde c = \sum_{i, j}c_ic_jx^{i-j}$ で、$c_ic_j \ne 0$ となる組 $(i, j)$ は $w^2$ 個、そのうち $i = j$ の $w$ 個はすべて指数 $0$ に寄与します。現れうる指数は高々 $w^2 - w + 1$ 種類なので、$p \le w^2 - w + 1$ です。 ### 5.3. 二元 Golay 符号 この節の流れは、(1) $x^{23} - 1$ を $\mathbb{F}_2$ 上で因数分解し、(2) 11 次の因子 $g$ を生成多項式とする巡回符号を作り、(3) 最小距離と完全性を調べる、の 3 段です。(1) では、23 を法として指数を 2 倍する操作で互いに移り合う指数の組（円分剰余類）が、因数分解の既約因子に 1 つずつ対応することを使います。 $p = 23$、$q = 2$ とします。$2^{11} = 2048 = 23 \cdot 89 + 1$ で、$23$ を法とする $2$ の位数は $11$ です。$2$-円分剰余類は $$ \{0\}, \qquad \mathcal{Q} = \{1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18\}, \qquad \mathcal{N} = \{5, 7, 10, 11, 14, 15, 17, 19, 20, 21, 22\} $$ の 3 つで、$\mathcal{Q}$ は $1$ の剰余類 $\{1, 2, 4, 8, 16, 9, 18, 13, 3, 6, 12\}$ であり、$23$ を法とする平方剰余の全体でもあります（$2$ は $23 \equiv 7 \pmod 8$ を法として平方剰余です。）。したがって $x^{23} - 1$ は $\mathbb{F}_2$ 上で次数 $1, 11, 11$ の既約多項式の積に分解します（）。具体的には $$ x^{23} - 1 = (x + 1)\,g(x)\,g^{*}(x), \qquad g(x) = x^{11} + x^9 + x^7 + x^6 + x^5 + x + 1, \quad g^{*}(x) = x^{11} + x^{10} + x^6 + x^5 + x^4 + x^2 + 1 $$ です（右辺を展開して確かめられます。$g^{*}$ は $g$ の係数を逆順にしたもの）。分解の一意性から、$g$ と $g^{*}$ が 2 つの 11 次の既約因子です。$\alpha$ を $g$ の根とすると、$\alpha^{23} = 1$、$\alpha \ne 1$（$g(1) = 1$）で $23$ は素数なので $\alpha$ は 1 の原始 $23$ 乗根で、$g$ の根は $\alpha$ の共役 $\alpha^{2^j}$、すなわち $\alpha^i$（$i \in \mathcal{Q}$）です（）。 $g(x) = x^{11} + x^9 + x^7 + x^6 + x^5 + x + 1$ を生成多項式とする $\mathbb{F}_2$ 上の長さ $23$ の巡回符号を**二元 Golay 符号** $G_{23}$ という。これは定義集合 $\mathcal{Q}$ の平方剰余符号である。$G_{23}$ にパリティ検査ビット $c_{\infty} = \sum_ic_i$ を付け加えた長さ $24$ の符号を**拡大 Golay 符号** $G_{24}$ という。 1. $G_{24}$ は $[24, 12, 8]_2$ の自己双対な重偶符号である。 2. $G_{23}$ は $[23, 12, 7]_2$ 符号で、完全符号である。 $\dim G_{23} = 23 - \deg g = 12$ です。 **第 1 段: BCH 限界。** 定義集合 $\mathcal{Q}$ は連続する指数 $1, 2, 3, 4$ を含むので、$d(G_{23}) \ge 5$ です（）。 **第 2 段: $G_{24}$ は自己双対で重偶。** $23 \equiv 3 \pmod 4$、$23 \equiv -1 \pmod 2$ なので、 により $G_{24}$ は自己双対な $[24, 12]_2$ 符号です（$\mathbb{F}_2$ では $-\sum_ic_i = \sum_ic_i$）。$g, xg, \ldots, x^{11}g$ は $G_{23}$ の基底で（）、どれも $g$ の巡回シフトなので重みは $g$ の項の数 $7$ です。これらを拡大した 12 個の語は $G_{24}$ の基底で、重みは $8$ です。自己双対なので互いの $\cdot$ は $0$ で、 により $G_{24}$ は重偶符号です。 **第 3 段: 最小距離。** $c \in G_{23}$、$c \ne 0$、$w = \operatorname{wt}(c)$ とします。第 1 段から $w \ge 5$ です。 - $w$ が偶数のとき。拡大しても重みは $w$ のままで、第 2 段から $w$ は $4$ の倍数です。$w \ge 5$ なので $w \ge 8$ です。 - $w$ が奇数のとき。$\sum_ic_i = 1 \ne 0$ なので、 から $w^2 - w + 1 \ge 23$ です。$w = 5$ では $21$ で足りないので $w \ge 6$、奇数なので $w \ge 7$ です。（第 2 段からも、拡大した重み $w + 1$ が $4$ の倍数で $w \ge 5$ なので $w \ge 7$ と分かります。） よって $d(G_{23}) \ge 7$ です。$g$ 自身が重み $7$ の符号語なので $d(G_{23}) = 7$ です。$G_{24}$ の $0$ でない語の重みは、もとの重み（$7$ 以上）以上で $4$ の倍数なので $8$ 以上、$g$ を拡大した語の重みが $8$ なので $d(G_{24}) = 8$ です。 **完全性。** 半径 $3$ の Hamming 球の体積は $$ 1 + \binom{23}{1} + \binom{23}{2} + \binom{23}{3} = 1 + 23 + 253 + 1771 = 2048 = 2^{11} $$ で、$|G_{23}| \cdot 2^{11} = 2^{12}\cdot 2^{11} = 2^{23}$ です。$t = \lfloor (7-1)/2 \rfloor = 3$ について Hamming 限界（）の等号が成り立つので、$G_{23}$ は完全符号です。 $$ W_{G_{24}}(1, y) = 1 + 759\,y^8 + 2576\,y^{12} + 759\,y^{16} + y^{24}. $$ により、重みは $4$ の倍数で、$0$ でない語の重みは $8$ 以上です。$(\boldsymbol{j}, 1)$（全成分が $1$ の語）は $G_{24}$ に属するので（ の証明）、$c \mapsto c + (\boldsymbol{j}, 1)$ は重み $i$ の語と重み $24 - i$ の語の全単射で、$A_i = A_{24-i}$ です。よって $A_0 = A_{24} = 1$、$A_4 = A_{20} = 0$ で、$a = A_8 = A_{16}$、$b = A_{12}$ とおくと、符号語の総数から $$ 2 + 2a + b = 2^{12} = 4096 $$ です。 もう 1 つの関係式を MacWilliams 恒等式から出します。$G_{24}$ は自己双対なので $A_2^{\perp} = A_2 = 0$ で、 から $\sum_iA_iK_2(i) = 0$ です。$n = 24$、$q = 2$ のとき $$ K_2(i) = \binom{24-i}{2} - i(24 - i) + \binom{i}{2} = \frac{(24 - 2i)^2 - 24}{2} $$ で、$K_2(0) = K_2(24) = 276$、$K_2(8) = K_2(16) = 20$、$K_2(12) = -12$ です。よって $$ 2 \cdot 276 + 2 \cdot 20\,a - 12\,b = 0, \qquad\text{すなわち}\qquad 3b = 138 + 10a $$ です。第 1 式の $3$ 倍 $6a + 3b = 12282$ に代入すると $16a = 12144$、$a = 759$、$b = 4094 - 1518 = 2576$ です。
04812162024 175925767591 重み
正二十面体の 12 個の頂点に番号を付け、$A$ を隣接行列（頂点 $i$ と $j$ が辺で結ばれていれば $A_{ij} = 1$）、$J$ を全成分が $1$ の行列、$B = J - A$（$\mathbb{F}_2$ の行列とみる）とします。$12 \times 24$ 行列 $G = (I_{12} \mid B)$ が生成する二元符号 $C$ を調べます。 各頂点の次数は $5$ なので、$B$ の各行の重みは $12 - 5 = 7$ で、$G$ の各行の重みは $8$ です。$B$ の第 $i$ 行と第 $j$ 行（$i \ne j$）がともに $1$ である列の個数は、$i$ にも $j$ にも隣接しない頂点 $l$ の個数です（$A_{ii} = 0$ なので $B_{ii} = 1$ で、$l = i, j$ も条件を満たせば数えます）。$i$ の隣接頂点の集合を $N(i)$ とすると、これは $12 - |N(i) \cup N(j)| = 12 - 5 - 5 + (\text{共通の隣接頂点の数})$ です。共通の隣接頂点は、$i, j$ が隣接するとき $2$ 個、距離 $2$ のとき $2$ 個、対蹠点のとき $0$ 個なので、この数は $4, 4, 2$ でいずれも偶数です。よって $G$ の行どうしの $\cdot$ はすべて $0$ で、 から $C$ は自己直交な重偶符号、次元が $12$ なので自己双対です。 最小距離が $8$ であることを確かめます。重偶なので、重み $4$ の語が無いことを示せば十分です。自己双対性 $GG^{\mathsf{T}} = I + BB^{\mathsf{T}} = 0$ と $B$ の対称性から $B^2 = I$ で、符号語 $(u \mid uB)$ の左右を入れ替えた $(uB \mid u) = (v \mid vB)$（$v = uB$）も符号語です。重み $4$ の語の左半分の重み $s = \operatorname{wt}(u)$ は、左右の入れ替えにより $s \le 2$ としてよく、$s = 0$ なら語は $0$、$s = 1$ なら $G$ の行で重み $8$、$s = 2$ なら右半分の重みは $7 + 7 - 2(2 + \text{共通の隣接頂点の数}) \in \{6, 10\}$ で全体の重みは $8$ 以上です。よって重み $4$ の語は無く、$C$ は $[24, 12, 8]_2$ の自己双対な重偶符号です。このパラメータの符号は座標の置換を除いて $G_{24}$ だけであることが知られています（Pless 1968）。 ### 5.4. 三元 Golay 符号 $p = 11$、$q = 3$ とします。$3^5 = 243 = 11 \cdot 22 + 1$ で、$11$ を法とする $3$ の位数は $5$ です（$3, 9, 5, 4, 1$）。$3$-円分剰余類は $\{0\}$、$\mathcal{Q} = \{1, 3, 4, 5, 9\}$、$\mathcal{N} = \{2, 6, 7, 8, 10\}$ で、$\mathcal{Q}$ は $11$ を法とする平方剰余の全体です（$3 \equiv 5^2$）。$\mathbb{F}_3$ 上で $$ x^{11} - 1 = (x - 1)\,g(x)\,\tilde g(x), \qquad g(x) = x^5 + x^4 + 2x^3 + x^2 + 2, \quad \tilde g(x) = x^5 + 2x^3 + x^2 + 2x + 2 $$ です（展開して確かめられます）。二元の場合と同じ理由で、$g$ と $\tilde g$ が 5 次の既約因子で、$g$ の根 $\alpha$ は 1 の原始 $11$ 乗根（$g(1) = 7 \equiv 1 \ne 0$）、$g$ の根は $\alpha^i$（$i \in \mathcal{Q}$）です。 $g(x) = x^5 + x^4 + 2x^3 + x^2 + 2$ を生成多項式とする $\mathbb{F}_3$ 上の長さ $11$ の巡回符号を**三元 Golay 符号** $G_{11}$ という。$G_{11}$ に座標 $c_{\infty} = -\sum_ic_i$ を付け加えた長さ $12$ の符号を**拡大三元 Golay 符号** $G_{12}$ という。 1. $G_{12}$ は $[12, 6, 6]_3$ の自己双対符号で、すべての符号語の重みは $3$ の倍数である。 2. $G_{11}$ は $[11, 6, 5]_3$ 符号で、完全符号である。 $\dim G_{11} = 11 - 5 = 6$ です。 **自己双対性。** $11 \equiv 3 \pmod 4$、$11 \equiv -1 \pmod 3$ なので、 により $G_{12}$ は自己双対な $[12, 6]_3$ 符号です。$c \in G_{12}$ について $c \cdot c = 0$ です。$\mathbb{F}_3$ の $0$ でない元 $\pm 1$ の平方は $1$ なので $c \cdot c = \sum_ic_i^2 = \operatorname{wt}(c)\cdot 1$ で、$\operatorname{wt}(c) \equiv 0 \pmod 3$ です。 **最小距離。** $\mathcal{Q}$ は連続する指数 $3, 4, 5$ を含むので、BCH 限界（、$b = 3$、$\delta = 4$）から $d(G_{11}) \ge 4$ です。$c \in G_{11}$、$c \ne 0$、$w = \operatorname{wt}(c)$ とします。拡大した語の重みは $w$ か $w + 1$ で、$3$ の倍数で $4$ 以上なので $6$ 以上です。よって $w \ge 5$ で、$d(G_{11}) \ge 5$、$d(G_{12}) \ge 6$ です。$g$ は項が $5$ 個の符号語なので $d(G_{11}) = 5$ です。$g(1) \ne 0$ なので $g$ を拡大した語の重みは $6$ で、$d(G_{12}) = 6$ です。 **完全性。** $t = 2$ で、半径 $2$ の球の体積は $$ 1 + \binom{11}{1}\cdot 2 + \binom{11}{2}\cdot 2^2 = 1 + 22 + 220 = 243 = 3^5 $$ です。$|G_{11}| \cdot 3^5 = 3^{6}\cdot 3^{5} = 3^{11}$ で Hamming 限界（）の等号が成り立つので、$G_{11}$ は完全符号です。 $$ W_{G_{12}}(1, y) = 1 + 264\,y^6 + 440\,y^9 + 24\,y^{12}. $$ により、$0$ でない語の重みは $6, 9, 12$ のいずれかです。$a = A_6$、$b = A_9$、$c = A_{12}$ とおくと $a + b + c = 3^6 - 1 = 728$ です。自己双対なので $A_1^{\perp} = A_1 = 0$、$A_2^{\perp} = A_2 = 0$ で、 から $\sum_iA_iK_1(i) = 0$、$\sum_iA_iK_2(i) = 0$ です。$n = 12$、$q = 3$ のとき $K_1(i) = 24 - 3i$、$K_2(i) = 4\binom{12-i}{2} - 2i(12-i) + \binom{i}{2}$ で、 | $i$ | $0$ | $6$ | $9$ | $12$ | |---|---|---|---|---| | $K_1(i)$ | $24$ | $6$ | $-3$ | $-12$ | | $K_2(i)$ | $264$ | $3$ | $-6$ | $66$ | です。よって $24 + 6a - 3b - 12c = 0$、$264 + 3a - 6b + 66c = 0$、すなわち $$ b = 8 + 2a - 4c, \qquad 88 + a - 2b + 22c = 0 $$ です。第 1 式を第 2 式に代入すると $72 - 3a + 30c = 0$、$a = 24 + 10c$ で、$b = 56 + 16c$ です。$a + b + c = 80 + 27c = 728$ から $c = 24$、$a = 264$、$b = 440$ です。 ## 6. 完全符号・被覆半径・Delsarte の不等式 ### 6.1. 被覆半径 符号 $C \subseteq \mathbb{F}_q^n$ の**被覆半径**を $$ \rho(C) = \max_{x \in \mathbb{F}_q^n}\ \min_{c \in C}\ d(x, c) $$ で定める。すなわち、符号語を中心とする半径 $\rho$ の球が全空間を覆うような最小の $\rho$ である。 最小距離が「球が重ならない最大の半径」を決めるのに対し、被覆半径は「球が全体を覆う最小の半径」です。第 3 章では、符号語を中心とする半径 $t = \lfloor (d-1)/2 \rfloor$ の球が全空間を覆う符号を完全符号と呼び、これが Hamming 限界の等号と同値であることを示しました（半径 $t$ の球は互いに交わらないので、覆うことと体積の合計が $q^n$ であることが同じになります）。 $C \subseteq \mathbb{F}_q^n$ を $2$ 個以上の語からなる符号、$d$ を最小距離、$t = \lfloor (d-1)/2 \rfloor$ とする。このとき $\rho(C) \ge t$ で、等号が成り立つことと $C$ が完全符号であることは同値である。 $d(c, c') = d$ となる符号語 $c, c'$ を取り、$c$ と $c'$ が異なる $d$ 個の座標のうち $t$ 個で $c$ の成分を $c'$ の成分に取り替えた語を $x$ とします。$d(x, c) = t$ です。$c$ と異なる符号語 $c''$ については、三角不等式（）から $d(x, c'') \ge d(c, c'') - d(c, x) \ge d - t \ge t + 1$ です（$d \ge 2t + 1$）。よって $\min_{c'' \in C}d(x, c'') = t$ で、$\rho(C) \ge t$ です。 $C$ が完全であることは、どの $x$ もある符号語から距離 $t$ 以内にあること、すなわち $\rho(C) \le t$ と同値です。前半と合わせて、これは $\rho(C) = t$ と同値です。 11 試合の結果（勝ち・引き分け・負けの 3 通り）を予想するくじで、「どんな結果になっても、少なくとも 9 試合が当たっている券が 1 枚はある」ようにするには、何枚買えばよいでしょうか。予想は $\mathbb{F}_3^{11}$ の語で、求めるものは被覆半径が $2$ 以下の符号です。半径 $2$ の球は $243$ 個の語を含むので、少なくとも $3^{11}/243 = 729$ 枚が必要です。$G_{11}$ は完全符号で被覆半径が $2$（）、語の数は $3^6 = 729$ なので、この下界をちょうど達成します。この符号は、Golay の論文より前の 1947 年に、フィンランドのくじの愛好家 Virtakallio が雑誌に発表していたことが知られています。 $q$ が素数冪のとき、自明でない完全符号（1 語だけの符号、全空間、二元の奇数長の反復符号を除く）のパラメータ $(n, |C|, d)$ は、Hamming 符号のパラメータ $\bigl((q^r-1)/(q-1),\ q^{n-r},\ 3\bigr)$ か、$G_{23}$ の $(23, 2^{12}, 7)$ か、$G_{11}$ の $(11, 3^6, 5)$ に限ります（Tietäväinen 1973、van Lint。参考文献 [4]）。証明は、完全符号が存在するための必要条件（Lloyd の定理: ある Krawtchouk 型の多項式が $t$ 個の相異なる整数根をもつ）を整数論的に調べるもので、この章の範囲を超えるため、ここでは定理として立てず紹介にとどめます。Golay 符号は、この意味で例外的な存在です。 ### 6.2. Delsarte の不等式 MacWilliams 恒等式は線形符号についての等式でしたが、その背後にある指標和の計算は、線形でない符号にも不等式として残ります。 $C \subseteq \mathbb{F}_q^n$ を空でない符号（線形とは限らない）、$M = |C|$ とし、**距離分布**を $$ B_i = \frac{1}{M}\,\#\{\, (c, c') \in C \times C : d(c, c') = i \,\} \qquad (0 \le i \le n) $$ で定める。このとき、すべての $0 \le k \le n$ について $$ \sum_{i=0}^{n}B_i\,K_k(i) \ge 0 $$ が成り立つ。 $u \in \mathbb{F}_q^n$ に対し $\Sigma(u) = \sum_{c \in C}\psi(u \cdot c)$ とおきます。$\overline{\psi(u \cdot c')} = \psi(-u \cdot c')$ なので $$ |\Sigma(u)|^2 = \sum_{c, c' \in C}\psi(u \cdot c)\overline{\psi(u \cdot c')} = \sum_{c, c' \in C}\psi\bigl(u \cdot (c - c')\bigr) $$ です。重み $k$ の $u$ について和を取り、 の第 2 の式 $\sum_{\operatorname{wt}(u) = k}\psi(u \cdot v) = K_k(\operatorname{wt}(v))$ を $v = c - c'$ に使うと $$ 0 \le \sum_{u :\, \operatorname{wt}(u) = k}|\Sigma(u)|^2 = \sum_{c, c' \in C}K_k\bigl(d(c, c')\bigr) = M\sum_{i=0}^{n}B_iK_k(i) $$ です。 $C$ が線形なら $B_i = A_i$ で、左辺は $M \cdot A_k^{\perp}$ に等しく（）、不等式は「双対符号の重み $k$ の語の個数は非負」という当たり前の事実になります。線形でない符号には双対符号がありませんが、「双対の重み分布にあたる量」が非負であることだけは残る、というのがこの命題の内容です。 最小距離 $d$ の符号の距離分布は $B_0 = 1$、$B_i = 0$（$1 \le i < d$）、$B_i \ge 0$、$\sum_iB_i = M$ を満たします。これらと Delsarte の不等式のもとで $\sum_iB_i$ を最大化する線形計画問題の最適値は、符号の語数 $M$ の上界です（**線形計画限界**）。もっとも簡単な場合が Plotkin 限界で、 で確かめます。 二元の自己双対な重偶符号の重み多項式は、MacWilliams 変換 $(x, y) \mapsto \bigl((x+y)/\sqrt2, (x-y)/\sqrt2\bigr)$ と $y \mapsto iy$ で不変です。Gleason（1971）は、このような多項式がすべて $$ x^8 + 14x^4y^4 + y^8 \qquad\text{と}\qquad x^4y^4(x^4 - y^4)^4 $$ の多項式で書けることを示しました（不変式論による。A. M. Gleason, "Weight polynomials of self-dual codes and the MacWilliams identities", 1970 年の国際数学者会議の報告集）。前者は の拡大 Hamming 符号の重み多項式で、次数を比べると重偶な自己双対符号の長さは $8$ の倍数に限ることが分かります。$G_{24}$ の重み多項式は $(x^8 + 14x^4y^4 + y^8)^3 - 42\,x^4y^4(x^4 - y^4)^4$ です。証明はこの章の範囲を超えるため、定理としては立てません。なお、拡大 Hamming 符号から $E_8$ 格子が、$G_{24}$ から Leech 格子が作られ、球充填の問題につながります（参考文献 [5]）。 誤り率 $p$ の二元対称通信路で線形符号 $C$ の符号語を送り、受信語が符号語かどうかだけを調べる（誤り検出）とします。誤りパターン $e$ が起こる確率は $p^{\operatorname{wt}(e)}(1-p)^{n - \operatorname{wt}(e)}$ で、誤りが見逃されるのは $e$ が $0$ でない符号語のときなので、見逃す確率は $$ P_{\mathrm{ud}}(p) = \sum_{i=1}^{n}A_i\,p^i(1-p)^{n-i} = W_C(1 - p,\ p) - (1-p)^n $$ です。$[7, 4]$ Hamming 符号では $7p^3(1-p)^4 + 7p^4(1-p)^3 + p^7$ で、$p = 0.01$ のとき約 $6.8 \times 10^{-6}$ です。MacWilliams 恒等式を使うと $W_C(1-p, p) = |C^{\perp}|^{-1}W_{C^{\perp}}(1, 1 - 2p)$ とも書け、次元の大きい符号では双対符号の重み分布から計算するほうが楽です。 ## 7. 演習 二元の長さ $n$ の反復符号 $C = \{00\cdots0, 11\cdots1\}$ の重み多項式と、MacWilliams 恒等式から得られる $C^{\perp}$ の重み多項式を求め、$C^{\perp}$ が偶数重みの語全体であることと合うことを確かめよ。 $W_C = x^n + y^n$ です。 から $$ W_{C^{\perp}} = \frac12\bigl[(x+y)^n + (x-y)^n\bigr] = \sum_{i\ \text{偶数}}\binom{n}{i}x^{n-i}y^i $$ です（奇数次の項は打ち消し合い、偶数次の項は 2 倍になる）。一方 $C^{\perp}$ は全 $1$ の語と直交する語、つまり偶数重みの語の全体で、重み $i$（偶数）の語は $\binom{n}{i}$ 個です。両者は一致します。 $G_{23}$ が完全符号であることを使って、$G_{23}$ の重み $7$ の符号語が $253$ 個であることを示せ。また と合わせて、重み $8$ の符号語が $506$ 個であることを示せ。 重み $4$ の語 $x \in \mathbb{F}_2^{23}$ は $\binom{23}{4} = 8855$ 個あります。完全性から、各 $x$ は距離 $3$ 以内にちょうど 1 つの符号語 $c$ をもちます。$\operatorname{wt}(c) \le 4 + 3 = 7$ で、$c = 0$ は距離が $4$ なので不適、$0$ でない符号語の重みは $7$ 以上なので $\operatorname{wt}(c) = 7$、$d(x, c) = 3$ です。これは $x$ の台が $c$ の台に含まれることを意味します（$d(x, c) = 7 + 4 - 2|x \cap c| = 3$ から $|x \cap c| = 4$）。逆に、重み $7$ の符号語 $c$ の台に含まれる重み $4$ の語は $\binom{7}{4} = 35$ 個で、どれも $c$ から距離 $3$ です。よって重み $7$ の符号語の個数は $8855/35 = 253$ です。 $G_{24}$ の重み $8$ の語は、$G_{23}$ の重み $7$ の語（パリティビットが $1$）と重み $8$ の語（パリティビットが $0$）を拡大したものです。$759 - 253 = 506$ です。 $\mathbb{F}_3$ 上の $[4, 2, 3]$ 符号（tetracode）$C$ を生成行列 $\begin{pmatrix}1&0&1&1\\0&1&1&2\end{pmatrix}$ で定める。$C$ が自己双対であることを示し、重み多項式を求め、MacWilliams 変換で不変であることを直接確かめよ。 行を $r_1, r_2$ とすると $r_1 \cdot r_1 = 1 + 1 + 1 = 0$、$r_2 \cdot r_2 = 1 + 1 + 4 = 0$、$r_1 \cdot r_2 = 1 + 2 = 0$（$\mathbb{F}_3$ で）なので $C \subseteq C^{\perp}$、次元がともに $2$ なので $C = C^{\perp}$ です。 の証明と同じく重みは $3$ の倍数で、$0$ でない $8$ 語の重みは $3$ です（重み $4$ ではないから）。よって $W_C = x^4 + 8xy^3$ です。不変性を確かめます。 $$ (x + 2y)^4 = x^4 + 8x^3y + 24x^2y^2 + 32xy^3 + 16y^4, \qquad (x + 2y)(x - y)^3 = x^4 - x^3y - 3x^2y^2 + 5xy^3 - 2y^4 $$ なので、$\frac19\bigl[(x+2y)^4 + 8(x+2y)(x-y)^3\bigr] = \frac19\bigl(9x^4 + 72xy^3\bigr) = x^4 + 8xy^3$ です。 二元符号 $C \subseteq \mathbb{F}_2^n$（線形とは限らない）の語数を $M$、最小距離を $d$ とし、$2d > n$ とする。Delsarte の不等式の $k = 1$ の場合から、Plotkin 限界 $M \le \dfrac{2d}{2d - n}$ を導け。 $q = 2$ のとき $K_1(i) = n - 2i$ です。距離分布は $B_0 = 1$、$B_i = 0$（$1 \le i < d$）、$\sum_{i \ge d}B_i = M - 1$ を満たします。$i \ge d$ では $K_1(i) = n - 2i \le n - 2d < 0$ なので、 から $$ 0 \le \sum_iB_iK_1(i) = n + \sum_{i \ge d}B_i(n - 2i) \le n + (M - 1)(n - 2d) $$ です。$(M - 1)(2d - n) \le n$ を整理すると $M(2d - n) \le 2d$、すなわち $M \le 2d/(2d - n)$ です。これは二元符号の Plotkin 限界（）と同じ形の評価で、線形計画限界のもっとも簡単な場合になっています。 ## 参考文献 1. F. J. MacWilliams, N. J. A. Sloane, *The Theory of Error-Correcting Codes*, North-Holland, 1977 — 第 5 章（双対符号と重み分布）、第 11 章（MDS 符号）、第 16 章（平方剰余符号）、第 20 章（Golay 符号）。 2. F. J. MacWilliams, "A theorem on the distribution of weights in a systematic code", *Bell System Technical Journal* 42 (1963), 79–94. 3. M. J. E. Golay, "Notes on digital coding", *Proceedings of the IRE* 37 (1949), 657. 4. A. Tietäväinen, "On the nonexistence of perfect codes over finite fields", *SIAM Journal on Applied Mathematics* 24 (1973), 88–96. 5. J. H. Conway, N. J. A. Sloane, *Sphere Packings, Lattices and Groups*, 3rd ed., Springer, 1999 — 符号から格子を作る構成と Leech 格子。 6. P. Delsarte, "An algebraic approach to the association schemes of coding theory", *Philips Research Reports Supplements* 10 (1973). 7. V. Pless, "On the uniqueness of the Golay codes", *Journal of Combinatorial Theory* 5 (1968), 215–228.