MacWilliams恒等式

同義語:MacWilliamsの恒等式MacWilliams identityMacWilliams identities

概要

MacWilliams恒等式(MacWilliams identity)とは、有限体 $\mathbb{F}_q$ 上の長さ $n$ の線形符号 $C$ の重み枚挙多項式 $W_C(x,y)=\sum_{c\in C}x^{n-\mathrm{wt}(c)}y^{\mathrm{wt}(c)}$ と双対符号 $C^\perp$ のそれとの間に $W_{C^\perp}(x,y)=\frac{1}{|C|}W_C(x+(q-1)y,\,x-y)$ が成り立つという定理である。線形符号の重みの分布が双対符号の重みの分布を完全に決めることを意味し、係数は Krawtchouk 多項式で書ける。有限体の加法指標による Poisson 和公式から証明され、Hamming 符号の重みの分布の計算、自己双対な符号の重み枚挙多項式の不変性、符号の大きさの線形計画法の限界に使われる。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: 線形符号, 有限体, 群の指標

線形符号 $C$ の符号語を重みごとに数えた列 $A_0,A_1,\dots,A_n$ を重みの分布という。符号の誤り検出・訂正の性能は重みの分布でほぼ決まるので、これを知ることは符号理論の基本的な問題である。MacWilliams 恒等式(MacWilliams identity)は、線形符号の重みの分布が、その双対符号 $C^\perp$ の重みの分布を完全に決めることを、次の多項式の等式で述べる。
$$ W_{C^\perp}(x,y)=\frac1{|C|}\,W_C\bigl(x+(q-1)y,\ x-y\bigr),\qquad W_C(x,y):=\sum_{c\in C}x^{\,n-\operatorname{wt}(c)}y^{\operatorname{wt}(c)}. $$
ここで $q$ は符号の文字の体 $\mathbb F_q$ の元の個数、$\operatorname{wt}$ は Hamming 重み($0$ でない座標の個数)である。符号語を 1 つも書き出さずに、$C$ の分布だけから $C^\perp$ の分布が出る。たとえば Hamming 符号の重みの分布は、すべての $0$ でない符号語の重みが等しいその双対(単体符号)から計算でき、自己双対な符号の重み枚挙多項式は特別な変数変換で不変になる。符号の大きさの上界を与える Delsarte の線形計画法の限界も、この恒等式から出る不等式に基づいている。
恒等式は F. J. MacWilliams が 1963 年に証明した。この記事では、有限体の加法指標による Poisson 和公式から恒等式を証明し、重みごとの係数の式(Krawtchouk 多項式)、Hamming 符号と自己双対符号への応用を述べる。

定義

以下、$q$ は素数 $p$ の冪 $q=p^e$、$\mathbb F_q$ は位数 $q$ の有限体、$n\ge1$ とする。語 $u\in\mathbb F_q^n$ の重み $\operatorname{wt}(u)$、線形符号、標準の内積 $u\cdot v=\sum_iu_iv_i$、双対符号 $C^\perp=\{v\mid u\cdot v=0\ (u\in C)\}$ は 線形符号 の記事の定義による。$\dim C^\perp=n-\dim C$ である(同記事の命題「双対符号の次元」)。

重みの分布と重み枚挙多項式

$C\subseteq\mathbb F_q^n$ を線形符号とする。$A_i:=|\{c\in C\mid\operatorname{wt}(c)=i\}|$($0\le i\le n$)を $C$ の 重みの分布 といい、2 変数の斉次多項式
$$ W_C(x,y):=\sum_{c\in C}x^{\,n-\operatorname{wt}(c)}y^{\operatorname{wt}(c)}=\sum_{i=0}^nA_ix^{n-i}y^i $$
を $C$ の 重み枚挙多項式 という。

$A_0=1$ で、$A_0+\dots+A_n=|C|=q^{\dim C}$ である。$x=1$ とおいた 1 変数の多項式 $\sum_iA_iz^i$ を重み枚挙多項式とよぶ流儀もある。

加法指標と Poisson 和公式

$\mathbb F_q$ の トレース $\operatorname{Tr}(a):=a+a^p+a^{p^2}+\dots+a^{p^{e-1}}$ を使い、
$$ \chi(a):=\exp\Bigl(\frac{2\pi i}{p}\operatorname{Tr}(a)\Bigr)\qquad(a\in\mathbb F_q) $$
とおく。ここで $\operatorname{Tr}(a)\in\mathbb F_p=\mathbb Z/p\mathbb Z$ の代表元を $\{0,\dots,p-1\}$ からとる($\exp(2\pi ik/p)$ は代表元の取り方によらない)。$q=p$ なら $\chi(a)=e^{2\pi ia/p}$ である。

加法指標
  1. $\chi(a+b)=\chi(a)\chi(b)$ であり、$\chi(a_0)\ne1$ となる $a_0\in\mathbb F_q$ がある。
  2. $b\in\mathbb F_q$ について、$\displaystyle\sum_{a\in\mathbb F_q}\chi(ba)=\begin{cases}q&(b=0)\\0&(b\ne0)\end{cases}$ である。とくに $b\ne0$ なら $\sum_{a\ne0}\chi(ba)=-1$ である。

1:Frobenius 写像 $a\mapsto a^p$ は加法を保ち、$a^{p^e}=a$ なので、$\operatorname{Tr}(a)^p=\operatorname{Tr}(a)$ である。$x^p=x$ の解は $\mathbb F_p$ の $p$ 個の元ですべてなので $\operatorname{Tr}(a)\in\mathbb F_p$ で、$\operatorname{Tr}$ は加法を保つ。よって $\chi$ は加法群から $\mathbb C^\times$ への準同型である。$\operatorname{Tr}$ は次数 $p^{e-1}< q$ の多項式で表されるので $\mathbb F_q$ の $q$ 個の元すべてで $0$ にはなれず、$\operatorname{Tr}(a_0)\ne0$ となる $a_0$ で $\chi(a_0)\ne1$ である。
2:$b=0$ なら各項が $1$ である。$b\ne0$ なら $a\mapsto ba$ は全単射なので和は $S:=\sum_a\chi(a)$ に等しい。$a\mapsto a_0+a$ も全単射なので $S=\sum_a\chi(a_0+a)=\chi(a_0)S$ であり、$\chi(a_0)\ne1$ から $S=0$ である。最後の主張は $a=0$ の項 $\chi(0)=1$ を除けばよい。$\square$

部分空間の上の指標和

線形符号 $C\subseteq\mathbb F_q^n$ と $v\in\mathbb F_q^n$ について、
$$ \sum_{c\in C}\chi(c\cdot v)=\begin{cases}|C|&(v\in C^\perp)\\0&(v\notin C^\perp)\end{cases} $$
である。

$v\in C^\perp$ なら各項が $\chi(0)=1$ である。$v\notin C^\perp$ なら、線形写像 $\varphi\colon C\to\mathbb F_q$、$c\mapsto c\cdot v$ は $0$ でないので全射で、各値の逆像は核の平行移動で $|C|/q$ 個の元をもつ。よって和は $\frac{|C|}{q}\sum_{a\in\mathbb F_q}\chi(a)=0$ である(lem-mw-character の 2 で $b=1$)。$\square$

関数 $f\colon\mathbb F_q^n\to R$($R$ は $\mathbb C$ を含む可換環、たとえば $\mathbb C[x,y]$)の Fourier 変換 を $\hat f(u):=\sum_{v\in\mathbb F_q^n}\chi(u\cdot v)f(v)$ と定める。離散Fourier変換 の $\mathbb F_q^n$ 版である。

線形符号の上の Poisson 和公式

線形符号 $C$ と関数 $f\colon\mathbb F_q^n\to R$ について
$$ \sum_{v\in C^\perp}f(v)=\frac1{|C|}\sum_{u\in C}\hat f(u) $$
である。

和の順序を入れ替える

$$ \sum_{u\in C}\hat f(u)=\sum_{v\in\mathbb F_q^n}f(v)\sum_{u\in C}\chi(u\cdot v)=|C|\sum_{v\in C^\perp}f(v) $$
で、最後の等号は lem-mw-subspace による。$\square$

主定理

MacWilliams 恒等式

$C\subseteq\mathbb F_q^n$ を線形符号とする。このとき
$$ W_{C^\perp}(x,y)=\frac1{|C|}\,W_C\bigl(x+(q-1)y,\ x-y\bigr) $$
が $\mathbb C[x,y]$ の等式として成り立つ。

座標ごとの Fourier 変換

$g\colon\mathbb F_q\to\mathbb C[x,y]$ を $g(0):=x$、$g(a):=y$($a\ne0$)と定め、$f(v):=\prod_{i=1}^ng(v_i)=x^{\,n-\operatorname{wt}(v)}y^{\operatorname{wt}(v)}$ とおく。すると $\sum_{v\in C^\perp}f(v)=W_{C^\perp}(x,y)$ である。
$f$ の Fourier 変換を計算する。$\chi(u\cdot v)=\prod_i\chi(u_iv_i)$ なので、和を座標ごとに分けて
$$ \hat f(u)=\sum_{v_1,\dots,v_n\in\mathbb F_q}\ \prod_{i=1}^n\chi(u_iv_i)g(v_i)=\prod_{i=1}^n\Bigl(\sum_{a\in\mathbb F_q}\chi(u_ia)g(a)\Bigr) $$
である。各因子は $x+y\sum_{a\ne0}\chi(u_ia)$ で、lem-mw-character の 2 により、$u_i=0$ なら $x+(q-1)y$、$u_i\ne0$ なら $x-y$ である。よって
$$ \hat f(u)=\bigl(x+(q-1)y\bigr)^{n-\operatorname{wt}(u)}(x-y)^{\operatorname{wt}(u)} $$
となる。prop-mw-poisson に代入すると
$$ W_{C^\perp}(x,y)=\frac1{|C|}\sum_{u\in C}\bigl(x+(q-1)y\bigr)^{n-\operatorname{wt}(u)}(x-y)^{\operatorname{wt}(u)}=\frac1{|C|}W_C\bigl(x+(q-1)y,\ x-y\bigr) $$
である。$\square$

所在と由来

二元($q=2$)の場合の恒等式は、GRS25 Exercise 2.36(p. 51)に、生成関数を使って順に示す形の演習として置かれている。同書の第 2 章の文献の注(§2.8、p. 51)は、これが MacWilliams(1963)が証明した恒等式に基づくと述べている。同演習の 4 は、1 変数の形 $\sum_iA^\perp_iz^i=\frac{(1+z)^n}{|C|}\sum_iA_i\bigl(\frac{1-z}{1+z}\bigr)^i$ で、上の定理で $x=1$、$y=z$ とおいたものにあたる。上の証明は一般の $q$ について、加法指標で書いたものである。

$C^\perp$ の双対は $C$ なので(線形符号 の命題「双対符号の次元」)、$C$ と $C^\perp$ の役割を入れ替えた式も成り立つ。$|C|\,|C^\perp|=q^n$ であり、変換 $(x,y)\mapsto(x+(q-1)y,\ x-y)$ を 2 回続けると $(qx,qy)$ になるので、2 つの式は互いに整合している。

係数の式

Krawtchouk 多項式による形

$C$ の重みの分布を $A_0,\dots,A_n$、$C^\perp$ の重みの分布を $A^\perp_0,\dots,A^\perp_n$ とすると、$0\le k\le n$ について
$$ A^\perp_k=\frac1{|C|}\sum_{i=0}^nA_iK_k(i),\qquad K_k(i):=\sum_{j=0}^k(-1)^j(q-1)^{k-j}\binom ij\binom{n-i}{k-j} $$
である。$K_k$ を(長さ $n$、$q$ 元の)Krawtchouk 多項式 という。

証明を開く

thm-mw-main の右辺の $A_i$ の項 $\bigl(x+(q-1)y\bigr)^{n-i}(x-y)^i$ を展開すると、$(x-y)^i$ から $y^j$ を、$\bigl(x+(q-1)y\bigr)^{n-i}$ から $y^{k-j}$ を選ぶ項の和として、$x^{n-k}y^k$ の係数は $\sum_j\binom ij(-1)^j\binom{n-i}{k-j}(q-1)^{k-j}=K_k(i)$ である。左辺の $x^{n-k}y^k$ の係数は $A^\perp_k$ である。$\square$

$K_0(i)=1$ なので $A^\perp_0=\frac1{|C|}\sum_iA_i=1$ となり、式は整合する。$K_1(i)=(q-1)(n-i)-i=(q-1)n-qi$ なので、$C^\perp$ の重み $1$ の語の個数は $\frac1{|C|}\sum_iA_i\bigl((q-1)n-qi\bigr)$ である。

反復符号と偶数重み符号

二元の反復符号 $C=\{000,111\}$ は $W_C=x^3+y^3$ で、$C^\perp$ は重みが偶数の語の全体 $\{000,011,101,110\}$ である。恒等式の右辺は
$$ \tfrac12\bigl((x+y)^3+(x-y)^3\bigr)=x^3+3xy^2 $$
で、確かに $C^\perp$ は重み $0$ の語を $1$ 個、重み $2$ の語を $3$ 個もつ。

Hamming 符号の重みの分布

$r\ge2$ とし、$n:=(q^r-1)/(q-1)$ とする。$q$ 元の Hamming 符号 $\mathcal H_r$ は $[n,n-r,3]_q$ 符号で、その双対の単体符号 $\mathcal H_r^\perp$ は次元 $r$ で、$0$ でない符号語の重みがすべて $q^{r-1}$ である(Hamming符号 の定理「単体符号の重み」)。

Hamming 符号の重み枚挙多項式

$$ W_{\mathcal H_r}(x,y)=\frac1{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] $$
である。

単体符号は $W_{\mathcal H_r^\perp}=x^n+(q^r-1)x^{n-q^{r-1}}y^{q^{r-1}}$ で、$|\mathcal H_r^\perp|=q^r$ である。$(\mathcal H_r^\perp)^\perp=\mathcal H_r$ なので、thm-mw-main を $\mathcal H_r^\perp$ に当てはめればよい。$\square$

二元 $[7,4]$ Hamming 符号

$q=2$、$r=3$、$n=7$ では
$$ W_{\mathcal H_3}=\tfrac18\bigl[(x+y)^7+7(x+y)^3(x-y)^4\bigr]=x^7+7x^4y^3+7x^3y^4+y^7 $$
である。展開は、$(x+y)^3(x-y)^4=(x^2-y^2)^3(x-y)$ を使うと速い。重みの分布 $1,0,0,7,7,0,0,1$ は、16 個の符号語を書き出して得られる分布(Hamming符号 の記事)と一致する。三元 $q=3$、$r=2$、$n=4$ では $W=\frac19\bigl[(x+2y)^4+8(x+2y)(x-y)^3\bigr]=x^4+8xy^3$ で、$[4,2,3]_3$ 符号の $0$ でない $8$ 個の符号語はすべて重み $3$ である。

二元 $r=4$(長さ $15$)でも、この式の分布 $1,0,0,35,105,168,280,435,435,280,168,105,35,0,0,1$ を計算機で求め、和が $2^{11}$ になることを確かめた。

自己双対な符号

$C=C^\perp$ のとき $C$ を 自己双対 という。$n$ は偶数で $|C|=q^{n/2}$ である。

自己双対な符号の不変性

$C$ が自己双対なら
$$ W_C(x,y)=W_C\Bigl(\frac{x+(q-1)y}{\sqrt q},\ \frac{x-y}{\sqrt q}\Bigr) $$
である。

thm-mw-main で $C^\perp=C$、$|C|=q^{n/2}$ とし、$W_C$ が $n$ 次斉次であることから $q^{-n/2}W_C(x+(q-1)y,\ x-y)=W_C\bigl(\frac{x+(q-1)y}{\sqrt q},\frac{x-y}{\sqrt q}\bigr)$ を使えばよい。$\square$

拡大 Hamming 符号

二元の拡大 Hamming 符号 $\widehat{\mathcal H}_3$ は自己双対な $[8,4,4]$ 符号で、$W=x^8+14x^4y^4+y^8$ である(Hamming符号 の例「自己双対な $[8,4,4]$ 符号」)。$\frac1{16}W(x+y,x-y)$ を展開すると、$(x+y)^8+(x-y)^8=2(x^8+28x^6y^2+70x^4y^4+28x^2y^6+y^8)$ と $(x+y)^4(x-y)^4=(x^2-y^2)^4$ から、$\frac1{16}\bigl[2(x^8+28x^6y^2+70x^4y^4+28x^2y^6+y^8)+14(x^8-4x^6y^2+6x^4y^4-4x^2y^6+y^8)\bigr]=x^8+14x^4y^4+y^8$ で、確かに不変である。

二元の自己双対な符号では、各符号語 $c$ について $c\cdot c=\sum_ic_i^2=\sum_ic_i$ が $\mathbb F_2$ で $\operatorname{wt}(c)$ の偶奇に等しく、これが $0$ なので、重みはすべて偶数である。したがって $W_C(x,-y)=W_C(x,y)$ でもあり、$W_C$ は prop-mw-selfdual の変換と $y\mapsto-y$ の両方で不変になる。Golay符号 の $\mathcal G_{24}$ も自己双対な二元符号の例である。

線形計画法の限界との関係

cor-mw-kraw の左辺 $A^\perp_k$ は個数なので $0$ 以上である。したがって、長さ $n$、最小距離 $d$ の線形符号の重みの分布 $A_0=1$、$A_1=\dots=A_{d-1}=0$、$A_i\ge0$ は、すべての $k$ について $\sum_iA_iK_k(i)\ge0$ をみたす。この不等式を制約として $\sum_iA_i$ を最大化する線形計画問題の最適値は、符号語の個数の上界になる(線形計画法)。GRS25 §8.2(pp. 163–165)は二元の符号について、この線形計画法の限界の不等式が MacWilliams 恒等式に基づくことを述べ(p. 164)、線形でない符号についても距離の分布を使って同じ不等式を示している(pp. 164–165)。

反例の表

外す条件例成り立たなくなること
$C$ が線形(部分空間)二元の $C=\{000,011,101\}$恒等式($C$ に直交する語の全体は $\{000,111\}$ で $W=x^3+y^3$ だが、右辺は $x^3+\frac13x^2y+\frac13xy^2+y^3$)
prop-mw-selfdual の $C=C^\perp$($C\subsetneq C^\perp$ にする)二元の $C=\{0000,1111\}$不変性(右辺は $\frac12x^4+3x^2y^2+\frac12y^4$)
反例の確認

1 行目:$C=\{000,011,101\}$ は $011+101=110\notin C$ なので部分空間でない。$W_C=x^3+2xy^2$ で、$\frac13W_C(x+y,x-y)=\frac13\bigl[(x+y)^3+2(x+y)(x-y)^2\bigr]$ を展開すると $x^3+\frac13x^2y+\frac13xy^2+y^3$ になり、係数が整数ですらない。$011$ と $101$ の両方に直交する語は $000$ と $111$ だけである。証明では lem-mw-subspace で $C$ が部分空間であること($c\mapsto c\cdot v$ が線形写像であること)を使っている。
2 行目:$C=\{0000,1111\}$ は自己直交($1111\cdot1111=0$)だが、$C^\perp$ は重みが偶数の 8 個の語からなり $C\ne C^\perp$ である。$\frac14W_C(x+y,x-y)=\frac14\bigl[(x+y)^4+(x-y)^4\bigr]=\frac12x^4+3x^2y^2+\frac12y^4$ は $W_C=x^4+y^4$ と異なる。なお $\frac12W_C(x+y,x-y)=x^4+6x^2y^2+y^4$ は thm-mw-main どおり $C^\perp$ の重み枚挙多項式である。

二元の長さ $5$ 以下、三元の長さ $3$ 以下、四元($\mathbb F_4$)の長さ $2$ 以下のすべての線形符号について、thm-mw-main と cor-mw-kraw を計算機で確かめた。上の例と反例の数値も同じ計算で確かめた。

関連項目

参考文献

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する