Koji Imamura
資料・アプリへ戻る

数学記事・メモ

MacWilliams恒等式で学ぶシリーズ第9回 / 全12回

MacWilliams恒等式で学ぶ因子グラフと分割関数入門

MacWilliams恒等式の五つの証明系統のうち，因子グラフ・分割関数として見える証明に着目し，局所因子，制約因子，分割関数，Tannerグラフ型因子グラフ，局所Fourier変換，双対化を導入する．
公開:
更新:
読了目安:
30分 (約17,990字)
Tagscoding theoryMacWilliams identityfactor graphspartition functionsnormal factor graphsFourier transformfinite fieldsweight enumeratorexpository note

はじめに

符号理論における基本定理の一つに，MacWilliams恒等式があります． EE を座標集合，n≔∣E∣n \coloneqq \card{E} とし，有限体 Fq\F_{q} 上の線形符号 C≤FqEC \leq \F_{q}^{E} に対して，その双対符号

C⊥≔{u∈FqE:u⋅c=0 for all c∈C}C^{\perp} \coloneqq \{ u \in \F_{q}^{E} : u \cdot c = 0 \text{ for all } c \in C \}

を考えます．ここで

u⋅c=∑e∈Eueceu \cdot c = \sum_{e \in E} u_{e} c_{e}

です． 符号語 c∈FqEc \in \F_{q}^{E} の台 (support) と Hamming重み (Hamming weight) を

supp⁡(c)≔{e∈E:ce≠0},wt⁡(c)≔∣supp⁡(c)∣\supp(c) \coloneqq \{ e \in E : c_{e} \neq 0 \}, \qquad \wt(c) \coloneqq \card{\supp(c)}

と書きます． 線形符号 CC の重み多項式 (weight enumerator) を

WC(X,Y)=∑c∈CXn−wt⁡(c)Ywt⁡(c)W_{C}(X, Y) = \sum_{c \in C} X^{n - \wt(c)} Y^{\wt(c)}

で定めます． MacWilliams恒等式は，双対符号の重み多項式が， CC の重み多項式から次のように計算できるという公式です：

WC⊥(X,Y)=1∣C∣WC(X+(q−1)Y,X−Y).W_{C^{\perp}}(X, Y) = \frac{1}{\card{C}} W_{C}\bigl( X + (q - 1)Y, X - Y \bigr).

これがMacWilliams恒等式です．

本稿では，このMacWilliams恒等式を， 因子グラフと分割関数の言葉で証明します． 本稿は単独で読めるように，必要な記号と概念を本文中で導入します． 前提にするのは，有限体上の線形符号，Hamming重み，双対符号の初歩だけです． 具体的には，次の程度を既知とします：

符号理論の初歩，具体的には

  • （有限）体とは何か

  • 有限体上の線形符号とは何か

  • Hamming重みとは何か

  • 双対符号とは何か

程度は既知であることを前提としています (MacWilliams恒等式の証明は知らなくても問題ありません)．

本稿は第1回から第8回を前提にしません． 連載全体ではMacWilliams恒等式の複数の証明を比較していますが， 連載全体の分類は，本稿の証明を読むために必須ではありません． パリティ検査行列，Tannerグラフ，因子グラフ，分割関数，Fourier変換については， 本文中で必要な範囲を説明します． 連載の他の回を読んでいなくても，MacWilliams恒等式そのものの証明を追えるように， 必要な記号と計算を順に導入します． 本稿の目標は，MacWilliams恒等式の証明を案内役として， 因子グラフと分割関数に入門することです．

因子グラフとは，多くの変数に依存する大きな関数を， 少数の変数だけに依存する小さな因子の積として表し， その依存関係をグラフで可視化する道具です． 分割関数とは，その積をすべての変数の値について足し上げたものです． 統計物理では状態全体にわたる重みの総和として現れ， 符号理論では制約を満たす語にわたる重みの総和として現れます．

線形符号 C≤FqEC \leq \F_{q}^{E} をパリティ検査行列 HH で書くと， CC は Hx⊤=0Hx^{\top} = 0 を満たす語 x=(xe)e∈E∈FqEx = (x_{e})_{e \in E} \in \F_{q}^{E} 全体です． この条件は，各検査式ごとの局所制約に分解できます． すると重み多項式は，

各検査式を満たす語 xx に対して，各座標の重みを掛け，それをすべて足す分割関数

として表せます． この分割関数の各局所制約をFourier展開すると， 双対符号 C⊥C^{\perp} が自然に現れます． これが，因子グラフ・分割関数から見たMacWilliams恒等式です．

本稿の流れは次のようになります．

分割関数 → 因子グラフ → 制約因子 → Tannerグラフ型因子グラフ → 局所Fourier変換 → 双対化 → MacWilliams恒等式

因子グラフと和–積アルゴリズムの標準的な入門としては Kschischang–Frey–Loeliger [KFL01] があります． Forney型の正規因子グラフについては Loeliger [Loe04] が読みやすく， 符号のグラフ上の正規実現については Forney [For01] が基本文献です． また，正規因子グラフの分割関数双対性とMacWilliams恒等式の関係については Forney [For11] を参照してください． 本稿ではこれらの一般論をすべて展開するのではなく， 有限体上の線形符号の通常のHamming重みMacWilliams恒等式に必要な部分だけを取り出して説明します．

分割関数：制約付きの重み付き和

まず，分割関数という言葉から始めます． 本稿では物理的な解釈には深入りせず，有限集合上の「和の形」として分割関数を扱います． ここでいう重みは，確率や正の実数に限りません． 本稿では，多項式値の重みや複素数値の重みも同じ言葉で扱います． 記号は，統計物理でよく使われる ZZ を使って Z\Zpart と書きます． また，本稿に出てくる分割関数はすべて有限和です． そのため，後で和の順序を入れ替えたり，有限直積上の和を座標ごとの和の積に分解したりしても問題ありません．

有限個の変数 x1,x2,…,xmx_{1}, x_{2}, \dots, x_{m} を考えます． 各変数 xix_{i} は有限集合 Xi\mathcal{X}_{i} の値を取るとします． 全体の状態空間は

X1×X2×⋯×Xm\mathcal{X}_{1} \times \mathcal{X}_{2} \times \dots \times \mathcal{X}_{m}

です．各状態 x=(x1,…,xm)x = (x_{1}, \dots, x_{m}) に重み F(x)F(x) が割り当てられているとき， その総和

Z≔∑x1∈X1∑x2∈X2⋯∑xm∈XmF(x1,…,xm)\Zpart \coloneqq \sum_{x_{1} \in \mathcal{X}_{1}} \sum_{x_{2} \in \mathcal{X}_{2}} \dots \sum_{x_{m} \in \mathcal{X}_{m}} F(x_{1}, \dots, x_{m})

を考えます． このような量を，本稿では分割関数 (partition function) と呼びます．

この定義だけだと，単に有限和を取っているだけに見えます． 重要なのは，重み F(x)F(x) が多くの場合，小さな因子の積として書けることです． たとえば

F(x1,x2,x3,x4)=f12(x1,x2)f23(x2,x3)f34(x3,x4)F(x_{1}, x_{2}, x_{3}, x_{4}) = f_{12}(x_{1}, x_{2}) f_{23}(x_{2}, x_{3}) f_{34}(x_{3}, x_{4})

のように書けるとします． すると分割関数は

Z=∑x1,x2,x3,x4f12(x1,x2)f23(x2,x3)f34(x3,x4)\Zpart = \sum_{x_{1}, x_{2}, x_{3}, x_{4}} f_{12}(x_{1}, x_{2}) f_{23}(x_{2}, x_{3}) f_{34}(x_{3}, x_{4})

です． この式は，単なる四変数関数の和ではなく， 隣り合う変数だけに依存する局所因子の積の和です． この「局所的な依存関係」をグラフで表したものが因子グラフです．

分割関数は，符号理論にも自然に現れます． 例えば，C≤FqEC \leq \F_{q}^{E} を線形符号とし，各座標値 a∈Fqa \in \F_{q} に 重み λ(a)\lambda(a) を割り当てます．このとき

∑c∈C∏e∈Eλ(ce)\sum_{c \in C} \prod_{e \in E} \lambda(c_{e})

は，符号語にわたる重み付き和です． これはまさに分割関数です． λ(0)=X\lambda(0) = X，λ(a)=Y\lambda(a) = Y (a≠0a \neq 0) とすれば， この分割関数は通常の重み多項式 WC(X,Y)W_{C}(X, Y) になります． つまり，重み多項式は，符号語空間上の分割関数です．

因子グラフ

因子グラフは，関数の因子分解をグラフとして表す道具です． ここでは最も基本的な二部グラフ型の因子グラフを定義します．

定義3.1（因子グラフ）．

変数集合を II，因子集合を A\mathcal{A} とする． 各変数 i∈Ii \in I に有限集合 Xi\mathcal{X}_{i} が割り当てられているとする． 各因子 α∈A\alpha \in \mathcal{A} に対して，その因子が依存する変数集合 ∂α⊆I\partial \alpha \subseteq I と関数

fα ⁣:∏i∈∂αXi→Kf_{\alpha} \colon \prod_{i \in \partial\alpha} \mathcal{X}_{i} \to \mathcal{K}

が与えられているとする1．

このデータを，変数頂点 i∈Ii \in I と因子頂点 α∈A\alpha \in \mathcal{A} からなる二部グラフで表し， i∈∂αi \in \partial \alpha のとき変数頂点 ii と因子頂点 α\alpha を辺で結ぶ． これを因子グラフ (factor graph) という．

因子グラフが表す大きな関数は

F(x)=∏α∈Afα(x∂α)F(x) = \prod_{\alpha \in \mathcal{A}} f_{\alpha}(x_{\partial\alpha})

です．ここで x=(xi)i∈Ix = (x_{i})_{i \in I} は全変数の値であり， x∂αx_{\partial\alpha} はそのうち ∂α\partial\alpha に属する変数だけを取り出したものです．

この関数の分割関数を

Z≔∑x∈∏i∈IXi∏α∈Afα(x∂α)\Zpart \coloneqq \sum_{x \in \prod_{i \in I} \mathcal{X}_{i}} \prod_{\alpha \in \mathcal{A}} f_{\alpha}(x_{\partial\alpha})

で定めます．つまり，因子グラフは

積として局所的に分解された関数と，その全状態にわたる和

を表す図式です．

例3.2（三つの局所因子）．

変数が x1x_{1}, x2x_{2}, x3x_{3}, x4x_{4} であり，因子が f12(x1,x2)f_{12}(x_{1}, x_{2}), f23(x2,x3)f_{23}(x_{2}, x_{3}), f34(x3,x4)f_{34}(x_{3}, x_{4}) であるとする．このとき分割関数は

Z=∑x1,x2,x3,x4f12(x1,x2)f23(x2,x3)f34(x3,x4)\Zpart = \sum_{x_{1}, x_{2}, x_{3}, x_{4}} f_{12}(x_{1}, x_{2}) f_{23}(x_{2}, x_{3}) f_{34}(x_{3}, x_{4})

である． 因子グラフでは，f12f_{12} は x1x_{1}, x2x_{2} に， f23f_{23} は x2x_{2}, x3x_{3} に， f34f_{34} は x3x_{3}, x4x_{4} にだけ接続する．

図 1三つの局所因子からなる因子グラフの例．丸が変数ノード，四角が因子ノードである．

図 1 は，式

f12(x1,x2)f23(x2,x3)f34(x3,x4)f_{12}(x_{1}, x_{2})f_{23}(x_{2}, x_{3})f_{34}(x_{3}, x_{4})

の依存関係を図にしたものです．

この例からわかるように，因子グラフは式の構造を見える形にします． もしグラフが木なら，sum-product algorithmによって分割関数や周辺和を効率よく計算できます． 一方，グラフにサイクルがある場合でも，因子グラフは依存関係を記述する言葉として有用です． 本稿では計算アルゴリズムとしての和–積アルゴリズムには深入りせず， 分割関数を変形してMacWilliams恒等式を導くための言葉として因子グラフを使います．

制約を因子で表す

因子グラフでは，重みだけでなく制約も因子として表せます． そのために，指示関数を使います．

定義4.1（指示関数）．

集合 SS と部分集合 T⊆ST \subseteq S に対して，TT の指示関数 (indicator function) を

1T(x)≔{1,x∈T,0,x∉T\one_{T}(x) \coloneqq \begin{cases} 1, & x \in T,\\ 0, & x \notin T \end{cases}

で定める．

有限体 Fq\F_{q} 上では，零元だけを示す指示関数を

δ0(t)≔{1,t=0,0,t≠0\delta_{0}(t) \coloneqq \begin{cases} 1, & t = 0,\\ 0, & t \neq 0 \end{cases}

と書くことにします． すなわち δ0=1{0}\delta_{0} = \one_{\{ 0 \}} です． これはKroneckerのデルタの有限体版です．

たとえば，条件 x+y=0x + y = 0 を満たす組だけを残したいなら，因子 δ0(x+y)\delta_{0}(x + y) を掛ければよいです． この因子は，x+y=0x + y = 0 のとき 11，そうでないとき 00 になります． そのため，分割関数の和の中では，条件を満たさない状態の寄与は消えます． たとえば F2\F_{2} 上では，次のようになります．

xxyyδ0(x+y)\delta_{0}(x + y)
000011
001100
110000
111111

つまり，0000 と 1111 だけが残り，0101 と 1010 の寄与は消えます．

例4.2（一つの線形制約）．

x1,x2,x3∈Fqx_{1}, x_{2}, x_{3} \in \F_{q} に対して，

a1x1+a2x2+a3x3=0a_{1} x_{1} + a_{2} x_{2} + a_{3} x_{3} = 0

という制約を課したいとする． この制約は因子

f(x1,x2,x3)=δ0(a1x1+a2x2+a3x3)f(x_{1}, x_{2}, x_{3}) = \delta_{0}(a_{1} x_{1} + a_{2} x_{2} + a_{3} x_{3})

で表せる． この因子は，制約を満たすときだけ 11 になり，満たさないときは 00 になる．

制約因子を使うと，線形符号を局所制約の積として表せます． これが次節のTannerグラフ型の因子グラフです．

符号をTannerグラフ型の因子グラフとして見る

C≤FqEC \leq \F_{q}^{E} を線形符号とします． k≔dim⁡Ck \coloneqq \dim C とおきます． 双対符号 C⊥C^{\perp} は次元 n−kn - k です． C⊥C^{\perp} の基底を選び，それを行に並べた行列を HH とします． (C⊥)⊥=C(C^{\perp})^{\perp} = C なので，この HH により

C={x∈FqE:Hx⊤=0}C = \{ x \in \F_{q}^{E} : Hx^{\top} = 0 \}

と書けます． ここで Hx⊤=0Hx^{\top} = 0 とは，xx が HH のすべての行と直交するという意味です． HH の行は C⊥C^{\perp} の基底なので，これは xx が C⊥C^{\perp} のすべての元と直交することを意味します． したがって x∈(C⊥)⊥=Cx \in (C^{\perp})^{\perp} = C であり， 逆に x∈Cx \in C なら C⊥C^{\perp} のすべての元と直交するので Hx⊤=0Hx^{\top} = 0 が成り立ちます． 抽象的な座標集合 EE と行集合を行列記法で書くときは， それぞれ一つ順序を入れていると思えばよいです． 以後は添字表示を使い，その順序に依存しない形で書きます．

行集合を JJ とし， H=(Hj,e)j∈J, e∈EH = (H_{j, e})_{j \in J,\,e \in E} と書きます．ここで ∣J∣=n−k\card{J} = n - k であり， HH の行は C⊥C^{\perp} の基底です． このとき

C={x∈FqE:∑e∈EHj,exe=0 for all j∈J}C = \left\{ x \in \F_{q}^{E}: \sum_{e \in E} H_{j, e} x_{e} = 0 \text{ for all } j \in J \right\}

です．

注意5.1．

一般には，冗長な検査式を含むパリティ検査行列も用いる． 本稿では，後で出てくる写像 y↦yHy\mapsto yH が C⊥C^{\perp} を一度ずつ走るように， 冗長行を含まない，すなわち C⊥C^{\perp} の基底を行にした HH を使う． この仮定により，yy の取り方と双対符号語 u=yHu = yH が一対一に対応するため， 後で余分な重複度を考えなくてよい． 冗長行を含む場合でも結論は同じだが，写像 y↦yHy\mapsto yH が一対一でなくなるため， 多重度の扱いが必要となる． また，同じ符号でも，パリティ検査行列の選び方によって Tannerグラフの形や辺ラベルは変わる． 本稿では証明を簡潔にするため，C⊥C^{\perp} の基底を行にした一つの HH を固定する．

符号理論では，座標に対応する変数ノードと検査式に対応する検査ノードからなるこの二部グラフを Tannerグラフ (Tanner graph) と呼びます [Tan81]． 変数ノードは座標 e∈Ee \in E に対応し，検査ノードはパリティ検査式 j∈Jj \in J に対応します． Hj,e≠0H_{j, e} \neq 0 のときだけ，検査ノード jj と変数ノード ee を辺で結びます． 因子グラフの言葉では，このTannerグラフの検査ノードに零制約因子を置いたものとして見られます． 二元符号では非零係数はすべて 11 なので，辺の有無だけで検査式をかなり表せます． しかし一般の Fq\F_{q} 上では，非零係数 Hj,eH_{j,e} の値も検査式に影響します． したがって，qq 元符号のTannerグラフでは，辺 jj–ee に係数 Hj,eH_{j, e} がラベルとして付いていると考えます．

各 j∈Jj \in J に対して，検査ノード jj に接続する座標集合， すなわち検査因子 hjh_{j} が依存する変数集合を

∂j={e∈E:Hj,e≠0}\partial j = \{ e \in E : H_{j, e} \neq 0 \}

と書きます． ここで ∂j\partial j は微分ではなく，因子グラフでよく使われる 「近傍」または「隣接変数集合」を表す記号です． このとき検査因子は

hj((xe)e∈∂j)=δ0(∑e∈∂jHj,exe)h_{j}((x_{e})_{e \in \partial j}) = \delta_{0} \left( \sum_{e \in \partial j} H_{j, e} x_{e} \right)

です． 和を EE 全体で書いても，Hj,e=0H_{j, e} = 0 の項は消えるので同じです． 因子グラフでは，e∈∂je \in \partial j である変数 xex_{e} とだけ接続します．

たとえば F2\F_{2} 上で

H=(11010110)H = \begin{pmatrix} 1 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 \end{pmatrix}

なら，二つの検査因子は

h1(x1,x2,x4)=δ0(x1+x2+x4),h2(x2,x3)=δ0(x2+x3)h_{1}(x_{1}, x_{2}, x_{4}) = \delta_{0}(x_{1} + x_{2} + x_{4}), \qquad h_{2}(x_{2}, x_{3}) = \delta_{0}(x_{2} + x_{3})

です．この例では h1h_{1} は x1x_{1}, x2x_{2}, x4x_{4} にだけ接続し， h2h_{2} は x2x_{2}, x3x_{3} にだけ接続します．

さらに，各座標 e∈Ee \in E に一座標重み因子 λ(xe)\lambda(x_{e}) を置きます． ここで λ ⁣:Fq→K\lambda \colon \F_{q} \to \mathcal{K} は任意の重み関数です． 後で λ(0)=X\lambda(0) = X，λ(a)=Y\lambda(a) = Y (a≠0a \neq 0) と特殊化します． 通常のTannerグラフは変数ノードと検査ノードからなりますが， 本稿の分割関数では，さらに各座標に一変数重み因子 λ(xe)\lambda(x_{e}) を付け足しています． 厳密には，Tannerグラフに座標重み因子を加えた因子グラフを考えています．

図 2Tannerグラフに一座標重み因子を加えた因子グラフの模式図．辺ラベルは検査式の非零係数を表す．

図 2 では，四角い検査ノード h1h_{1}, h2h_{2} が零制約因子を表し， 下側または上側の小さい四角が一座標重み因子を表しています．

このとき，因子グラフの分割関数は

ZC(λ)≔∑x∈FqE(∏j∈Jδ0(∑e∈EHj,exe))∏e∈Eλ(xe).(5.1)\begin{aligned} \Zpart_{C}(\lambda) &\coloneqq \sum_{x \in \F_{q}^{E}} \left( \prod_{j \in J} \delta_{0} \left( \sum_{e \in E} H_{j, e} x_{e} \right) \right) \prod_{e \in E}\lambda(x_{e}). \tag{5.1} \end{aligned}

制約因子の積は，x∈Cx \in C のときだけ 11 になり，それ以外では 00 になります． したがって

ZC(λ)=∑c∈C∏e∈Eλ(ce).(5.2)\Zpart_{C}(\lambda) = \sum_{c \in C} \prod_{e \in E} \lambda(c_{e}). \tag{5.2}

つまり，ZC(λ)\Zpart_{C}(\lambda) は符号語にわたる重み付き和です． この後は，任意の線形符号 D≤FqED \leq \F_{q}^{E} に対して

ZD(λ)=∑d∈D∏e∈Eλ(de)\Zpart_{D}(\lambda) = \sum_{d \in D} \prod_{e \in E} \lambda(d_{e})

と書きます． 最初の定義 (5.1) はパリティ検査行列を使った制約付き和であり， (5.2) によって， それが符号語上の重み付き和と一致することを確認したわけです． この記法により，後で出てくる ZC⊥(λ^)\Zpart_{C^{\perp}}(\what{\lambda}) は， 双対符号語上で重み λ^\what{\lambda} を掛けて足した分割関数を意味します． 特に，

λX,Y(a)≔{X,a=0,Y,a≠0(5.3)\lambda_{X, Y}(a) \coloneqq \begin{cases} X, & a = 0,\\ Y, & a \neq 0 \end{cases} \tag{5.3}

とおけば，

ZC(λX,Y)=WC(X,Y)\Zpart_{C}(\lambda_{X, Y}) = W_{C}(X,Y)

となります．

ここまでの話を言葉で言えば，次のようになります．

重み多項式は，Tannerグラフ型因子グラフの分割関数である．

この一文が，今回の出発点です．

一座標のFourier変換

ここから，局所因子を双対化するためのFourier変換を準備します． ψ ⁣:Fq→C×\psi \colon \F_{q} \to \C^{\times} を 有限体 Fq\F_{q} の非自明な加法指標，つまり，

ψ(a+b)=ψ(a)ψ(b)\psi(a + b) = \psi(a)\psi(b)

を満たし，恒等的に 11 ではない写像として一つ固定します． q=pq = p の場合は

ψ(a)=exp⁡(2π−1a/p)\psi(a) = \exp(2\pi\sqrt{-1}a/p)

と考えればよいです． ここでは a∈Fpa \in \F_{p} を 0,1,…,p−10, 1, \dots, p - 1 の代表元で表しています． 一般の q=pmq = p^{m} では，トレース写像を使って

ψ(a)=exp⁡(2π−1pTr⁡Fq/Fp(a))\psi(a) = \exp\left( \frac{2\pi\sqrt{-1}}{p} \Tr_{\F_{q}/\F_{p}}(a) \right)

と定めることができます．

必要な基本性質は次の直交関係です．

補題6.1．

b∈Fqb \in \F_{q} に対して

∑a∈Fqψ(ab)={q,b=0,0,b≠0\sum_{a \in \F_{q}} \psi(ab) = \begin{cases} q, & b = 0,\\ 0, & b \neq 0 \end{cases}

が成り立つ．

証明

b=0b = 0 なら，各項は 11 なので和は qq である． b≠0b \neq 0 とする．このとき a↦aba \mapsto ab は Fq\F_{q} の全単射であるから，

∑a∈Fqψ(ab)=∑t∈Fqψ(t)\sum_{a \in \F_{q}} \psi(ab) = \sum_{t \in \F_{q}} \psi(t)

である．右辺を SS とおく． ψ\psi は非自明なので，ある d∈Fqd \in \F_{q} が存在して ψ(d)≠1\psi(d) \neq 1 である． tt が Fq\F_{q} 全体を動くとき t+dt + d も Fq\F_{q} 全体を動くので，

S=∑t∈Fqψ(t+d)=ψ(d)∑t∈Fqψ(t)=ψ(d)SS = \sum_{t \in \F_{q}} \psi(t + d) = \psi(d) \sum_{t \in \F_{q}} \psi(t) = \psi(d)S

となる．ψ(d)≠1\psi(d) \neq 1 より S=0S = 0 である．

証明終わり

一座標重み関数 λ ⁣:Fq→K\lambda \colon \F_{q} \to \mathcal{K} に対して， そのFourier変換を

λ^(b)≔∑a∈Fqλ(a)ψ(ab)(b∈Fq)(6.1)\what{\lambda}(b) \coloneqq \sum_{a \in \F_{q}} \lambda(a)\psi(ab) \qquad (b \in \F_{q}) \tag{6.1}

で定めます． Fourier変換では値 ψ(ab)\psi(ab) が複素数になるので， 必要に応じて係数環を C\C を含む環に拡大して考えます． Hamming重み多項式では C[X,Y]\C\lbrack X, Y \rbrack，完全重み多項式では後で出てくる C[Ta:a∈Fq]\C\lbrack T_{a} : a \in \F_{q} \rbrack の中で計算すれば十分です． ここではFourier変換を非正規化の形で定義しています． そのため，零制約の展開には 1/q1/q が現れます． 後で出てくる係数 1/∣C⊥∣1/\card{C^{\perp}} は， この 1/q1/q が検査式の数だけ積み重なったものです．

Hamming重み多項式に現れる重み

λX,Y(a)={X,a=0,Y,a≠0\lambda_{X,Y}(a) = \begin{cases} X, & a = 0,\\ Y, & a \neq 0 \end{cases}

のFourier変換を計算しておきます．

補題6.2．

λX,Y\lambda_{X, Y} を (5.3) で定める． このとき

λ^X,Y(b)={X+(q−1)Y,b=0,X−Y,b≠0\what{\lambda}_{X, Y}(b) = \begin{cases} X + (q - 1)Y, & b = 0,\\ X - Y, & b \neq 0 \end{cases}

が成り立つ．

証明

b=0b = 0 のとき，

λ^X,Y(0)=∑a∈FqλX,Y(a)=X+(q−1)Y\what{\lambda}_{X, Y}(0) = \sum_{a \in \F_{q}} \lambda_{X, Y}(a) = X + (q - 1)Y

である．次に b≠0b \neq 0 とする． 補題 6.1 より

∑a∈Fqψ(ab)=0\sum_{a \in \F_{q}} \psi(ab) = 0

であるから，

∑a∈Fq×ψ(ab)=−1\sum_{a \in \F_{q}^{\times}} \psi(ab) = -1

である．したがって

λ^X,Y(b)=X+Y∑a∈Fq×ψ(ab)=X−Y\what{\lambda}_{X, Y}(b) = X + Y\sum_{a \in \F_{q}^{\times}} \psi(ab) = X - Y

となる．

証明終わり

この局所計算こそ，MacWilliams恒等式の変数変換

X↦X+(q−1)Y,Y↦X−YX \mapsto X + (q - 1)Y, \qquad Y \mapsto X-Y

の出所です． 因子グラフの言葉では，これは一座標の重み因子をFourier変換した結果です．

零制約因子のFourier展開

次に，検査因子に現れる零制約 δ0(t)\delta_{0}(t) をFourier展開します．

補題7.1．

任意の t∈Fqt \in \F_{q} に対して

δ0(t)=1q∑y∈Fqψ(yt)(7.1)\delta_{0}(t) = \frac{1}{q}\sum_{y \in \F_{q}}\psi(yt) \tag{7.1}

が成り立つ．

証明

t=0t = 0 なら右辺は q/q=1q/q = 1 である． t≠0t \neq 0 なら，補題 6.1 より

∑y∈Fqψ(yt)=0\sum_{y \in \F_{q}} \psi(yt) = 0

である．これは左辺 δ0(t)=0\delta_{0}(t) = 0 と一致する．

証明終わり

この式は，制約因子を双対変数 yy にわたる和として書き直しています． 因子グラフ的には，検査因子をFourier展開すると，その検査因子に双対変数が一つ現れる，と読めます． この双対変数が，後でパリティ検査行列の行の線形結合を作り，双対符号 C⊥C^{\perp} の符号語を生みます．

分割関数をFourier展開する

Tannerグラフ型因子グラフの分割関数

ZC(λ)=∑x∈FqE(∏j∈Jδ0(∑e∈EHj,exe))∏e∈Eλ(xe)\Zpart_{C}(\lambda) = \sum_{x \in \F_{q}^{E}} \left( \prod_{j \in J} \delta_{0} \left(\sum_{e \in E} H_{j,e} x_{e} \right) \right) \prod_{e \in E}\lambda(x_{e})

に，補題 7.1 を適用します． ここでは，Hj,e=0H_{j, e} = 0 の項を含めて EE 全体の和で書いています． これは ∂j\partial j 上の和と同じですが，後の座標ごとの整理が見やすくなります． すべての和は有限和なので，以下では和の順序を自由に入れ替えます． また，積が座標ごとに分かれたときには，有限直積上の和を各座標の和の積として書き直します．

各 j∈Jj \in J について

δ0(∑e∈EHj,exe)=1q∑yj∈Fqψ(yj∑e∈EHj,exe)\delta_{0} \left(\sum_{e \in E} H_{j,e} x_{e} \right) = \frac{1}{q}\sum_{y_{j} \in \F_{q}} \psi\left(y_{j} \sum_{e \in E} H_{j, e} x_{e} \right)

です．これをすべての検査式に代入すると，

ZC(λ)=q−∣J∣∑y∈FqJ∑x∈FqE∏j∈Jψ(yj∑e∈EHj,exe)∏e∈Eλ(xe).(8.1)\begin{aligned} \Zpart_{C}(\lambda) &= q^{-\card{J}} \sum_{y \in \F_{q}^{J}} \sum_{x \in \F_{q}^{E}} \prod_{j \in J} \psi\left( y_{j} \sum_{e \in E} H_{j, e} x_{e} \right) \prod_{e\in E}\lambda(x_e). \tag{8.1} \end{aligned}

ここで記号の役割を整理しておきます． xex_{e} は，元の符号語候補 x∈FqEx \in \F_{q}^{E} の ee 座標です． 一方，大文字の XX, YY は後でHamming重み多項式に使う形式変数であり， xex_{e} やここで現れる yjy_{j} とは別物です． y=(yj)j∈Jy = (y_{j})_{j \in J} は検査因子に対応する双対変数で， yjy_{j} は検査式 jj をFourier展開したときに現れる係数です． yjy_{j} は双対符号語の座標ではありません． 実際の双対符号語は後で u=yHu = yH として得られ，その ee 座標が

ue=(yH)e=∑j∈JyjHj,eu_{e} = (yH)_{e} = \sum_{j \in J} y_{j} H_{j,e}

です． つまり，この計算では元の座標変数 xex_{e} から， 検査式に付く係数 yjy_{j} を経て， 双対符号語の座標 ueu_{e} へと記号の役割が移っていきます．

\begin{tabular}{c|p{0.68\linewidth}} 記号 & 役割 \\ \hline xex_{e} & 元の符号語候補 xx の ee 座標 \\ yjy_{j} & 検査式 jj をFourier展開したときに現れる和変数，または HH の jj 行を線形結合する係数 \\ ueu_{e} & 双対符号語 u=yHu = yH の ee 座標 \\ X,YX, Y & Hamming重み多項式の形式変数 \end{tabular}

加法指標の性質 ψ(s+t)=ψ(s)ψ(t)\psi(s+t)=\psi(s)\psi(t) により， 内側の指標因子は座標ごとに分離できます． 実際，

∏j∈Jψ(yj∑e∈EHj,exe)=ψ(∑j∈Jyj∑e∈EHj,exe)=ψ(∑e∈E(∑j∈JyjHj,e)xe)=∏e∈Eψ((∑j∈JyjHj,e)xe).\begin{aligned} \prod_{j \in J} \psi\left(y_{j} \sum_{e \in E} H_{j, e} x_{e} \right) &= \psi\left(\sum_{j \in J} y_{j} \sum_{e \in E} H_{j, e} x_{e} \right) \\ &= \psi\left(\sum_{e \in E}\left(\sum_{j \in J} y_{j} H_{j, e} \right) x_{e} \right) \\ &= \prod_{e \in E} \psi\left(\left(\sum_{j \in J} y_{j} H_{j, e} \right) x_{e} \right). \end{aligned}

ここで使っているのは，有限直積上の和の基本的な分解です． 各 ee ごとの一変数関数 geg_{e} に対して

∑x∈FqE∏e∈Ege(xe)=∏e∈E∑a∈Fqge(a)\sum_{x \in \F_{q}^{E}} \prod_{e \in E} g_{e}(x_{e}) = \prod_{e \in E} \sum_{a \in \F_{q}} g_{e}(a)

が成り立ちます．これは，二変数の場合の

∑x1,x2g1(x1)g2(x2)=(∑x1g1(x1))(∑x2g2(x2))\sum_{x_{1}, x_{2}} g_{1}(x_{1}) g_{2}(x_{2}) = \left(\sum_{x_{1}} g_{1}(x_{1}) \right) \left(\sum_{x_{2}} g_{2}(x_{2}) \right)

を座標数だけ繰り返したものです． したがって (8.1) の内側の xx に関する和は

∑x∈FqE∏e∈Eλ(xe)ψ((∑j∈JyjHj,e)xe)=∏e∈E∑a∈Fqλ(a)ψ((∑j∈JyjHj,e)a)=∏e∈Eλ^(∑j∈JyjHj,e).\begin{aligned} &\sum_{x \in \F_{q}^{E}} \prod_{e \in E} \lambda(x_{e}) \psi\left(\left(\sum_{j \in J} y_{j} H_{j, e} \right) x_{e} \right) \\ &\qquad = \prod_{e \in E} \sum_{a \in \F_{q}} \lambda(a) \psi\left(\left(\sum_{j \in J} y_{j} H_{j, e} \right) a \right) \\ &\qquad = \prod_{e \in E} \what{\lambda}\left(\sum_{j \in J} y_{j} H_{j, e} \right). \end{aligned}

ここで，yH∈FqEyH \in \F_{q}^{E} を

(yH)e≔∑j∈JyjHj,e(yH)_{e} \coloneqq \sum_{j \in J} y_{j} H_{j,e}

で定めます． これは HH の行の線形結合です． よって上の計算から

ZC(λ)=q−∣J∣∑y∈FqJ∏e∈Eλ^((yH)e)(8.2)\Zpart_{C}(\lambda) = q^{-\card{J}} \sum_{y \in \F_{q}^{J}} \prod_{e \in E} \what{\lambda}((yH)_{e}) \tag{8.2}

を得ます．

いま，HH の行は C⊥C^{\perp} の基底として選んでいるので，写像

FqJ→C⊥,y↦yH\F_{q}^{J} \to C^{\perp}, \qquad y \mapsto yH

は全単射です． また ∣J∣=dim⁡C⊥=n−k\card{J} = \dim C^{\perp} = n - k なので，

q∣J∣=∣C⊥∣.q^{\card{J}} = \card{C^{\perp}}.

したがって (8.2) は

ZC(λ)=1∣C⊥∣∑u∈C⊥∏e∈Eλ^(ue)(8.3)\Zpart_{C}(\lambda) = \frac{1}{\card{C^{\perp}}} \sum_{u \in C^{\perp}} \prod_{e \in E} \what{\lambda}(u_{e}) \tag{8.3}

となります．右辺は，双対符号 C⊥C^{\perp} 上の分割関数です． つまり

ZC(λ)=1∣C⊥∣ZC⊥(λ^)(8.4)\Zpart_{C}(\lambda) = \frac{1}{\card{C^{\perp}}} \Zpart_{C^{\perp}}(\what{\lambda}) \tag{8.4}

です．

これが，計算から直接得られる向きの中心公式です． つまり，CC の分割関数を C⊥C^{\perp} 側で書く式です． 一方，通常よく見るMacWilliams恒等式は，C⊥C^{\perp} の重み多項式を CC 側で書く形です． その標準向きを得るには，この一般式を C⊥C^{\perp} に適用して向きを入れ替えます． 一般に，線形符号 D≤FqED \leq \F_{q}^{E} に同じ式を適用すると

ZD(λ)=1∣D⊥∣ZD⊥(λ^)(8.5)\Zpart_{D}(\lambda) = \frac{1}{\card{D^{\perp}}} \Zpart_{D^{\perp}}(\what{\lambda}) \tag{8.5}

です．ここで D≔C⊥D \coloneqq C^{\perp} とおくと，D⊥=CD^{\perp} = C なので

ZC⊥(λ)=1∣C∣ZC(λ^)(8.6)\Zpart_{C^{\perp}}(\lambda) = \frac{1}{\card{C}} \Zpart_{C}(\what{\lambda}) \tag{8.6}

となります． 係数が 1/∣C⊥∣1/\card{C^{\perp}} から 1/∣C∣1/\card{C} に変わるのは， 標準向きでは D=C⊥D = C^{\perp} と置くため，この場合の双対符号 D⊥D^{\perp} が CC になるからです．

直接得られる向きについて言葉で言えば，

正確には，符号 CC の分割関数は， 双対符号 C⊥C^{\perp} 上でFourier変換後の一座標重み λ^\what{\lambda} を用いた分割関数の 1/∣C⊥∣1/\card{C^{\perp}} 倍になる．

ということです．

因子グラフ双対性として読む

(8.4) は， 有限体上の線形符号についての分割関数双対性です． ここでは，この式を因子グラフの言葉で読み直します．

元の因子グラフには，次の二種類の因子がありました．

検査因子

各 j∈Jj \in J に対して

δ0(∑e∈EHj,exe)\delta_{0}\left(\sum_{e \in E} H_{j, e} x_{e} \right)

という線形制約を表す因子．

重み因子

各座標 e∈Ee \in E に対する λ(xe)\lambda(x_{e}) という一座標重み因子．

検査因子をFourier展開すると，検査ごとに双対変数 yjy_{j} が現れます． その双対変数の値を使って，座標ごとに

(yH)e=∑j∈JyjHj,e(yH)_{e} = \sum_{j \in J} y_{j} H_{j,e}

ができます． これは，パリティ検査行列 HH の行の線形結合です． したがって，yy が動くと yHyH は C⊥C^{\perp} 全体を走ります．

一方，座標変数 xex_{e} に関する和は，局所的に

∑a∈Fqλ(a)ψ(a(yH)e)=λ^((yH)e)\sum_{a \in \F_{q}}\lambda(a)\psi(a(yH)_{e}) = \what{\lambda}((yH)_{e})

になります． つまり，座標重み因子 λ\lambda がFourier変換された重み因子 λ^\what{\lambda} に変わります．

因子グラフ的に言えば，元の検査因子をFourier展開すると， その検査因子に対応する和変数 yjy_{j} が現れます． これらの yjy_{j} は，HH の行を線形結合して u=yHu = yH を作る係数です． 双対符号語の座標は e∈Ee \in E で添字付けられる ueu_{e} であり， yjy_{j} ではありません． また，元の座標重み因子 λ(xe)\lambda(x_{e}) は， xex_{e} について和を取った後， Fourier変換された重み因子 λ^(ue)\what{\lambda}(u_{e}) に変わります．

正規因子グラフの一般論では，これを各局所因子に対して同時に行います． 規約によって符号反転因子や正規化定数を伴いますが， 大まかには，各局所因子をFourier変換し，辺変数を双対変数に取り替えます． その結果得られる双対側の因子グラフの分割関数は， 元のグラフの分割関数と明示的な定数倍の関係にあります． 本稿で行った計算は，その一般論をTannerグラフ型因子グラフに特化したものです．

Hamming重み多項式への特殊化

ここで，通常のHamming重み多項式へ戻ります． 一座標重みを (5.3) の λX,Y\lambda_{X, Y} にします． このとき，任意の符号 D≤FqED \leq \F_{q}^{E} について

ZD(λX,Y)=WD(X,Y)\Zpart_{D}(\lambda_{X, Y}) = W_{D}(X,Y)

です．

また，補題 6.2 より

λ^X,Y(b)={X+(q−1)Y,b=0,X−Y,b≠0\what{\lambda}_{X, Y}(b) = \begin{cases} X + (q - 1)Y, & b = 0,\\ X - Y, & b \neq 0 \end{cases}

でした． この λ^X,Y\what{\lambda}_{X, Y} は，入力が 00 のとき X+(q−1)YX + (q - 1)Y を返し， 入力が非零のとき X−YX - Y を返す一座標重みです． したがって，CC 上でこの重みを掛けて足すことは， WC(X,Y)W_{C}(X, Y) の XX に X+(q−1)YX + (q - 1)Y，YY に X−YX - Y を代入することと同じです． そこで，(8.6) に λ=λX,Y\lambda = \lambda_{X,Y} を代入すると，

WC⊥(X,Y)=ZC⊥(λX,Y)=1∣C∣ZC(λ^X,Y)=1∣C∣WC(X+(q−1)Y,X−Y).\begin{aligned} W_{C^{\perp}}(X, Y) &= \Zpart_{C^{\perp}}(\lambda_{X, Y}) \\ &= \frac{1}{\card{C}}\Zpart_{C}(\what{\lambda}_{X, Y}) \\ &= \frac{1}{\card{C}} W_{C} \bigl( X + (q - 1)Y, X - Y\bigr). \end{aligned}

すなわち

WC⊥(X,Y)=1∣C∣WC(X+(q−1)Y,X−Y)W_{C^{\perp}}(X, Y) = \frac{1}{\card{C}} W_{C} \bigl( X + (q - 1)Y, X - Y \bigr)

が得られます． これはMacWilliams恒等式そのものです．

この証明で重要なのは，変数変換

X↦X+(q−1)Y,Y↦X−YX \mapsto X + (q - 1)Y, \qquad Y \mapsto X - Y

が，大域的に突然現れたのではないという点です． 各座標の重み因子 λX,Y\lambda_{X, Y} を一座標Fourier変換した結果が， この二つの値になっています． つまり，MacWilliams変換は，因子グラフの各座標における局所Fourier変換をグラフ全体に貼り合わせたものです．

小さな例：二元反復符号

最後に，小さな例で公式を確認します． E={1,2}E = \{ 1, 2 \} とし，二元反復符号

C={00,11}≤F22C = \{ 00, 11 \} \leq \F_{2}^{2}

を考えます．この符号は自己双対，つまり C⊥=CC^{\perp} = C を満たします． 実際，u=(u1,u2)u = (u_{1}, u_{2}) が CC のすべての符号語と直交する条件は，

u1+u2=0u_{1} + u_{2} = 0

であり，これは F2\F_{2} 上 u1=u2u_{1} = u_{2} が成り立つことを意味します． したがって C⊥=CC^{\perp} = C です．

パリティ検査行列として

H=(11)H = \begin{pmatrix} 1 & 1 \end{pmatrix}

を取れます．分割関数は

ZC(λ)=∑x1,x2∈F2δ0(x1+x2)λ(x1)λ(x2)=λ(0)2+λ(1)2.\begin{aligned} \Zpart_{C}(\lambda) &= \sum_{x_{1}, x_{2} \in \F_{2}} \delta_{0}(x_{1} + x_{2})\lambda(x_{1})\lambda(x_{2}) \\ &= \lambda(0)^{2} + \lambda(1)^{2}. \end{aligned}

λ(0)=X\lambda(0) = X，λ(1)=Y\lambda(1) = Y とすれば

WC(X,Y)=X2+Y2W_{C}(X, Y) = X^{2} + Y^{2}

です．

二元の場合の一座標Fourier変換は

λ^(0)=X+Y,λ^(1)=X−Y\what{\lambda}(0) = X + Y, \qquad \what{\lambda}(1) = X - Y

です． この例でも，一般の場合と同じ局所計算がそのまま見えます． F2\F_{2} の加法指標を ψ(t)=(−1)t\psi(t) = (-1)^{t} と書くと，

δ0(x1+x2)=12∑y∈F2(−1)y(x1+x2)\delta_{0}(x_{1} + x_{2}) = \frac{1}{2}\sum_{y \in \F_{2}}(-1)^{y(x_{1} + x_{2})}

です．これを分割関数に代入すると，固定した y∈F2y \in \F_{2} に対して

∑x1,x2∈F2λ(x1)λ(x2)(−1)yx1(−1)yx2=(∑x1∈F2λ(x1)(−1)yx1)(∑x2∈F2λ(x2)(−1)yx2)=λ^(y)2\begin{aligned} &\sum_{x_{1}, x_{2} \in \F_{2}} \lambda(x_{1}) \lambda(x_{2}) (-1)^{yx_{1}} (-1)^{yx_{2}} \\ &\qquad = \left(\sum_{x_{1} \in \F_{2}} \lambda(x_{1})(-1)^{yx_{1}} \right) \left(\sum_{x_{2} \in \F_{2}} \lambda(x_{2})(-1)^{yx_{2}} \right) \\ &\qquad = \what{\lambda}(y)^{2} \end{aligned}

となります． つまり，制約因子をFourier展開し，座標ごとの和を取ると， 一座標重み因子が λ^\what{\lambda} に変わる，という一般の場合の計算がこの小例にも現れています． 公式 (8.4) は， C=C⊥C = C^{\perp} かつ ∣C⊥∣=2\card{C^{\perp}} = 2 より

ZC(λ)=12ZC(λ^)\Zpart_{C}(\lambda) = \frac{1}{2} \Zpart_{C}(\what{\lambda})

と主張します．右辺を計算すると

12((X+Y)2+(X−Y)2)=X2+Y2\frac{1}{2}\left((X + Y)^{2} + (X - Y)^{2} \right) = X^{2} + Y^{2}

です．確かに元の重み多項式と一致します．

この例は自己双対なので，CC 側と C⊥C^{\perp} 側の区別は表面上見えにくくなっています． 一般には，まず

ZC(λ)=1∣C⊥∣ZC⊥(λ^)\Zpart_{C}(\lambda) = \frac{1}{\card{C^{\perp}}}\Zpart_{C^{\perp}}(\what{\lambda})

が得られ，通常のMacWilliams恒等式の向きに直すために， 同じ式を C⊥C^{\perp} に適用します．

この例ではグラフは非常に小さいですが，構造は一般の場合と同じです． 制約因子 δ0(x1+x2)\delta_{0}(x_{1} + x_{2}) をFourier展開し， 座標ごとの和を取ると，一座標重み因子がFourier変換されます． その結果，双対符号上の分割関数が現れます．

標準向きが見えやすい非自己双対の例も見ておきます． F2\F_{2} 上で

C={000,111}≤F23C = \{ 000, 111 \} \leq \F_{2}^{3}

とします．このとき

WC(X,Y)=X3+Y3W_{C}(X, Y) = X^{3} + Y^{3}

です．双対符号は

C⊥={000,011,101,110}C^{\perp} = \{ 000, 011, 101, 110 \}

であり，

WC⊥(X,Y)=X3+3XY2W_{C^{\perp}}(X, Y) = X^{3} + 3XY^{2}

です．例えば

H=(110101)H = \begin{pmatrix} 1 & 1 & 0 \\ 1 & 0 & 1 \end{pmatrix}

をパリティ検査行列として取れます．このとき

yH=(y1+y2,y1,y2)yH = (y_{1} + y_{2}, y_{1}, y_{2})

です． y1,y2∈F2y_{1}, y_{2} \in \F_{2} が動くと，

000,110,101,011000,\quad 110,\quad 101,\quad 011

が一度ずつ現れます． ここでも，y1,y2y_{1}, y_{2} は双対符号語の座標ではなく， HH の二つの行を線形結合して双対符号語 u=yHu = yH を作る係数です． MacWilliams恒等式の右辺は

12WC(X+Y,X−Y)=12{(X+Y)3+(X−Y)3}=X3+3XY2\begin{aligned} \frac{1}{2} W_{C}(X + Y, X - Y) &= \frac{1}{2}\{(X + Y)^{3} + (X - Y)^{3} \} \\ &= X^{3} + 3XY^{2} \end{aligned}

となり，確かに WC⊥(X,Y)W_{C^{\perp}}(X, Y) と一致します． この例では自己双対でないため，

WC⊥(X,Y)=1∣C∣WC(X+Y,X−Y)W_{C^{\perp}}(X, Y) = \frac{1}{\card{C}} W_{C}(X + Y, X - Y)

という標準向きが見えやすくなっています．

補足：正規因子グラフの見方

この節は，本文の証明には使わなかった背景説明です． MacWilliams恒等式の導出を一度読んだ後で， 今回の計算を正規因子グラフ一般論の中に位置づけるための補足として置いています． 本稿の証明自体は，正規因子グラフの一般定理を引用するのではなく， Tannerグラフ型の分割関数を直接Fourier展開して行いました． 正規因子グラフに不慣れな読者は，この節を背景説明として読めば十分です．

本稿の証明そのものは，Tannerグラフ型の通常の二部因子グラフを式で追う形で進めました． 一方で，正規因子グラフは，この局所Fourier変換がより一般のグラフ双対性の特別な場合であることを理解するための背景になります．

Forney型の正規因子グラフ (normal factor graph) では， 変数を辺として描き，因子を頂点として描きます． 普通の因子グラフでは，変数も因子も頂点でした． 正規因子グラフでは，変数は因子と因子をつなぐ辺になります． Forney型の正規因子グラフでは，内部変数は辺として，外部変数は半辺として描かれます．

正規因子グラフの基本的な利点は，双対を取る操作が局所的に書けることです． 規約によって符号反転因子や正規化定数を伴いますが，大まかには， 各因子をFourier変換し，各辺変数を双対変数に取り替えることで， 正規因子グラフ一般論では双対グラフと呼ばれるものが得られます． その分割関数は，元の分割関数と定数倍の関係にあります． この一般定理が，Forney型の正規因子グラフ双対性です．

本稿では，正規因子グラフの一般論を完全には展開しません． しかし，どのような考え方かは押さえておきます．

普通の因子グラフで，ある変数 xx が三つ以上の因子に現れることがあります． 正規形では，その変数のコピー x(1),x(2),x(3),…x^{(1)}, x^{(2)}, x^{(3)}, \dots を作り， それらがすべて等しいことを強制する等号因子 eq⁡(x(1),x(2),x(3),… )\eq(x^{(1)}, x^{(2)}, x^{(3)},\dots) を入れます． ここで

eq⁡(x(1),x(2),…,x(s))≔{1,x(1)=x(2)=⋯=x(s),0,その他\eq(x^{(1)}, x^{(2)}, \dots, x^{(s)}) \coloneqq \begin{cases} 1, & x^{(1)} = x^{(2)} = \dots = x^{(s)}, \\ 0, & \text{その他} \end{cases}

です． このようにすると，各変数コピーは高々二つの因子にだけ接続するようにできます．

今回のTannerグラフ型因子グラフでも，厳密なForney型正規因子グラフにするなら， 各座標変数のコピーと等号因子を導入します． ただし，MacWilliams恒等式を導く計算の本質は， 各検査因子をFourier展開し，座標ごとの和を局所的に分離することにあります． そのため，本稿では図式の正規化の細部には深入りせず，式の中で局所双対化を追いました．

この点を強調しておきます． 今回の証明は，通常の指標論的証明と同じFourier的原理を使います． しかし，一つの大きな指標和をいきなり書くのではなく，

検査因子ごとにFourier展開し，座標変数ごとに和を分離する

という局所的な操作として進めました． これが因子グラフ的な見方です．

補足：完全重み多項式版

この節は補足です． 通常のHamming重み多項式だけを読みたい場合は，飛ばしても構いません． ここでは，各非零元を同じ変数 YY でまとめる前の，より細かい重み多項式を見ます．

一座標重み λ\lambda を一般の変数で書くと，完全重み多項式が現れます． 各 a∈Fqa \in \F_{q} に変数 TaT_{a} を用意し， λ(a)≔Ta\lambda(a) \coloneqq T_{a} とおきます． すると

ZC(λ)=∑c∈C∏e∈ETce\Zpart_{C}(\lambda) = \sum_{c \in C} \prod_{e \in E} T_{c_e}

です． これは CC の完全重み多項式 (complete weight enumerator) です． 本稿ではこれを

cwe⁡C((Ta)a∈Fq)=∑c∈C∏e∈ETce\cwe_{C}((T_{a})_{a \in \F_{q}}) = \sum_{c \in C} \prod_{e \in E} T_{c_{e}}

と書きます．

一座標Fourier変換は，変数変換

TbF=∑a∈FqTaψ(ab)(b∈Fq)T_{b}^{\mathrm{F}} = \sum_{a \in \F_{q}} T_{a} \psi(ab) \qquad (b \in \F_{q})

として現れます． 上付きの F\mathrm{F} はFourier変換後の変数であることを示すための記号であり， 有限体を表す F\F とは別の記号です． ここでは係数環を C[Ta:a∈Fq]\C\lbrack T_{a} : a \in \F_{q} \rbrack に拡大して計算しています． したがって (8.4) は

cwe⁡C((Ta)a∈Fq)=1∣C⊥∣cwe⁡C⊥((TbF)b∈Fq)(13.1)\cwe_{C}((T_{a})_{a \in \F_{q}}) = \frac{1}{\card{C^{\perp}}} \cwe_{C^{\perp}}((T_{b}^{\mathrm{F}})_{b \in \F_{q}}) \tag{13.1}

と書けます． これは完全重み多項式版のMacWilliams恒等式の一つの向きです．

通常よく見る形にするには，(13.1) を C⊥C^{\perp} に適用します．(C⊥)⊥=C(C^{\perp})^{\perp} = C であり， ∣(C⊥)⊥∣=∣C∣\card{(C^{\perp})^{\perp}}=\card{C} なので，

cwe⁡C⊥((Ta)a∈Fq)=1∣C∣cwe⁡C((TbF)b∈Fq)(13.2)\cwe_{C^{\perp}}((T_{a})_{a \in \F_{q}}) = \frac{1}{\card{C}} \cwe_{C}((T_{b}^{\mathrm{F}})_{b \in \F_{q}}) \tag{13.2}

を得ます． この式が，完全重み多項式版のMacWilliams恒等式です．

注意しておくと，Fourier変換の規約によって ψ(ab)\psi(ab) の代わりに ψ(−ab)\psi(-ab) が現れることがあります． 完全重み多項式では，この違いは変換後の変数の添字を bb から −b-b に取り替える違いとして現れます． 一方，Hamming重み多項式へ特殊化する場合， 非零値をすべて同じ変数 YY に送るので， この添字の入れ替えは見えなくなります． したがって，最終的なHamming重み多項式版のMacWilliams恒等式には影響しません．

この証明で因子グラフと分割関数は何をしていたか

今回の証明を振り返ります．

第一に，重み多項式を分割関数として見ました． 重み多項式は，符号語 c∈Cc \in C に対して座標ごとの重みを掛け， それをすべて足したものです．すなわち

WC(X,Y)=∑c∈C∏e∈EλX,Y(ce)W_{C}(X,Y) = \sum_{c \in C} \prod_{e \in E} \lambda_{X, Y}(c_{e})

です． この見方により，重み多項式は「制約を満たす状態にわたる重み付き和」として捉えられます．

第二に，符号 CC を局所制約の積として表しました． パリティ検査行列 HH を使えば，CC は各行 jj に対応する制約

∑e∈EHj,exe=0\sum_{e \in E} H_{j, e} x_{e} = 0

の同時解です． このとき，qq 元Tannerグラフでは辺の有無だけでなく， 辺ラベル Hj,eH_{j, e} も検査式の一部です． この制約は，因子

δ0(∑e∈EHj,exe)\delta_{0} \left( \sum_{e \in E} H_{j, e} x_{e} \right)

として分割関数に組み込まれます． これにより，符号は一つの大きな集合ではなく， 検査式ごとの局所制約の集まりとして表されます． 本稿で実際に使った因子グラフは， このTannerグラフに各座標の一座標重み因子 λ(xe)\lambda(x_{e}) を加えたものです．

第三に，零制約をFourier展開しました．制約因子は

δ0(t)=1q∑y∈Fqψ(yt)\delta_{0}(t) = \frac{1}{q} \sum_{y \in \F_{q}} \psi(yt)

と書けます． これは，制約を双対変数 yy にわたる和に変換する操作です． 検査式ごとにこの変換を行うことで，双対変数 yjy_{j} が現れます． ここでも，yjy_{j} は双対符号語の座標ではなく，検査行を線形結合する係数です．

第四に，座標ごとの和が一座標Fourier変換になりました． 検査式ごとの双対変数 yjy_{j} をまとめると，各座標に

(yH)e=∑j∈JyjHj,e(yH)_{e} = \sum_{j \in J} y_{j} H_{j,e}

が現れます．その座標で xex_{e} について和を取ると，

∑a∈Fqλ(a)ψ(a(yH)e)=λ^((yH)e)\sum_{a \in \F_{q}} \lambda(a)\psi(a(yH)_{e}) = \what{\lambda}((yH)_{e})

となります． つまり，元の重み因子 λ\lambda がFourier変換された重み因子 λ^\what{\lambda} に変わります．

第五に，yHyH が双対符号を走りました． HH の行を C⊥C^{\perp} の基底として選んでいるので， yy が FqJ\F_{q}^{J} を動くと，yHyH は C⊥C^{\perp} 全体を一度ずつ動きます． 双対符号語を u=yHu = yH と書けば，その座標は ue=(yH)eu_{e} = (yH)_{e} です． これにより，元の符号 CC の分割関数は， 係数 1/∣C⊥∣1/\card{C^{\perp}} とFourier変換後の一座標重み λ^\what{\lambda} を伴って，双対符号 C⊥C^{\perp} 上の分割関数として書き直されます． 通常のMacWilliams恒等式の向きでは，同じ一般公式を C⊥C^{\perp} に適用するため， 係数は 1/∣C∣1/\card{C} になります．

要点を一文で言えば，次のようになります．

MacWilliams恒等式は，Tannerグラフ型因子グラフの分割関数において， 零制約因子を局所Fourier展開し，座標ごとの和を取ると， 定数倍とFourier変換後の一座標重みを伴って， 双対符号上の分割関数が現れるという事実である．

この回で見た概念

この回では，MacWilliams恒等式の証明を目標にしながら， 因子グラフと分割関数の基本的な道具を導入しました． 整理すると次のようになります．

分割関数

状態全体にわたる重みの総和です． 本稿では，有限集合上の和

Z=∑x∏αfα(x∂α)\Zpart = \sum_{x} \prod_{\alpha} f_{\alpha}(x_{\partial\alpha})

として扱いました．

因子

少数の変数だけに依存する局所関数です． 大きな関数を因子の積に分解することで，依存関係を見やすくできます．

因子グラフ

変数と因子の依存関係を二部グラフとして表したものです． 変数頂点と因子頂点を用意し，因子が依存する変数と辺で結びます．

制約因子

条件を満たすとき 11，満たさないとき 00 になる因子です． 線形制約は δ0\delta_{0} を使って表しました．

Tannerグラフ型因子グラフ

線形符号を，座標に対応する変数ノードと検査式に対応する検査ノードからなる Tannerグラフ上の局所制約として表す因子グラフです． qq 元符号では，辺ラベル Hj,eH_{j, e} も検査式を決めるデータです． 本稿では，さらに各座標に一座標重み因子 λ(xe)\lambda(x_{e}) を加えました． 重み多項式は，このグラフの分割関数として表せます．

正規因子グラフ

変数を辺として描き，因子を頂点として描くForney型の因子グラフです． 双対化を局所因子ごとに記述しやすい枠組みです．

一座標Fourier変換

一座標重み因子 λ\lambda を

λ^(b)=∑a∈Fqλ(a)ψ(ab)\what{\lambda}(b) = \sum_{a \in \F_{q}} \lambda(a)\psi(ab)

で変換する操作です． Hamming重み因子では，X+(q−1)YX + (q - 1)Y と X−YX - Y が現れます．

零制約のFourier展開

制約因子 δ0(t)\delta_{0}(t) を

δ0(t)=1q∑y∈Fqψ(yt)\delta_{0}(t) = \frac{1}{q} \sum_{y \in \F_{q}} \psi(yt)

と書く公式です． これにより，局所制約から双対変数が現れます．

分割関数双対性

局所因子をFourier変換すると，元の分割関数と双対側の因子グラフの 分割関数が定数倍で結ばれるという原理です． 正規因子グラフ一般論では，この双対側の因子グラフを 双対グラフとして扱います． 本稿では，その最も基本的な例として， 線形符号のMacWilliams恒等式を導きました．

今回の系統の振り返り

今回の証明は，表面的には因子グラフと分割関数の証明です． 符号をパリティ検査式ごとの局所制約として表し， 重み多項式をその制約付き分割関数として読みました． そのうえで，各制約因子をFourier展開し，座標ごとの和を分離しました．

五つの系統に圧縮すれば，今回の証明は

Fourier・指標・Poisson系

に属します． 理由は，双対符号が現れる根本原理が，有限体の加法指標による直交関係だからです． 実際，零制約因子の展開

δ0(t)=1q∑y∈Fqψ(yt)\delta_{0}(t) = \frac{1}{q}\sum_{y \in \F_{q}} \psi(yt)

は，有限Fourier変換そのものです．

ただし，今回の見方は通常の指標論的証明とは異なります． 通常の証明では，符号 CC 全体にわたる指標和

∑c∈Cψ(u⋅c)\sum_{c \in C}\psi(u \cdot c)

を一括で扱います． 一方，本稿では，検査因子ごとの局所Fourier展開から出発し， 座標ごとの和を通じて一座標重み因子を変換しました． つまり，Fourier変換を「全体に一回かける」のではなく， 因子グラフ上の局所操作として貼り合わせています．

この違いが，因子グラフ的な見方の価値です． 同じMacWilliams恒等式であっても， 「大域的な指標直交性」 として見ることもできれば， 「局所制約を持つ分割関数の双対性」 として見ることもできます． 後者の見方は，畳込み符号，tail-biting符号，グラフ上の符号， 統計物理の模型などへ自然に広がります．

次回へ

ここまでで，本稿の主張である因子グラフ・分割関数から見たMacWilliams恒等式の導出は完結しています．

次回は，MacWilliams恒等式を解析的な跡公式の側から見ます．

今回の証明では，重み多項式をTannerグラフ型因子グラフの分割関数として表し， 局所Fourier変換によって双対符号の分割関数へ移りました． 次回は，Hamming空間上の作用素，特にHamming graphの熱核やMarkov作用素を考え， その跡を二通りに計算します． 一方の計算ではスペクトル側から双対符号が現れ， もう一方の計算では平行移動作用の跡から元の符号の重み多項式が現れます．

つまり次回の主役は，

Hamming graph → 作用素 → 熱核 → 跡公式 → MacWilliams恒等式

です． 同じFourier・指標・Poisson系に属する証明であっても， 次回は「局所制約の分割関数」ではなく， 「作用素の跡を二通りに計算する」という解析的な姿が見えてきます．

脚注

  1. ここで K\mathcal{K} は，例えば C\C や多項式環のように，足し算と掛け算ができる係数の範囲である． 最初は可換半環や可換環を考えれば十分である． Fourier展開を使う節以降では，1/q1/q と指標値を扱うため， 必要に応じて C\C を含む係数環へ拡大する． ↩

参考文献

  1. [KFL01] Frank R. Kschischang, Brendan J. Frey, and Hans-Andrea Loeliger. Factor graphs and the sum-product algorithm. IEEE Trans. Inform. Theory, vol. 47, no. 2, pp. 498–519, 2001. doi:10.1109/18.910572 ↩
  2. [Loe04] Hans-Andrea Loeliger. An introduction to factor graphs. IEEE Signal Process. Mag., vol. 21, no. 1, pp. 28-41, 2004. doi:10.1109/MSP.2004.1267047 https://api.semanticscholar.org/CorpusID:7722934 ↩
  3. [For01] Jr. G. David Forney. Codes on graphs: normal realizations. IEEE Trans. Inform. Theory, vol. 47, no. 2, pp. 520–548, 2001. doi:10.1109/18.910573 ↩
  4. [For11] Jr. G. David Forney. Codes on graphs: duality and MacWilliams identities. IEEE Trans. Inform. Theory, vol. 57, no. 3, pp. 1382–1397, 2011. doi:10.1109/TIT.2011.2104994 ↩
  5. [Tan81] R. Michael Tanner. A recursive approach to low complexity codes. IEEE Trans. Inform. Theory, vol. 27, no. 5, pp. 533–547, 1981. doi:10.1109/TIT.1981.1056404 ↩

この連載

MacWilliams恒等式で学ぶシリーズ · 第9回 / 全12回

前の記事MacWilliams恒等式で学ぶ群作用と巡回指数入門
連載一覧へ戻る

免責事項

当サイトの記事は、運営者個人の理解・調査・研究メモに基づいて作成しています。内容については正確であるよう努めていますが、誤りや不十分な記述が含まれる可能性があります。正確性・完全性・有用性・最新性を保証するものではありません。

当サイトの情報の利用は、利用者ご自身の判断と責任において行ってください。当サイトの情報を利用したこと、または利用できなかったことにより生じた損害、損失、不利益等について、運営者は法律上許される範囲において責任を負いません。

ただし、記事内容の誤り、不明確な記述、リンク切れ、出典の不備等にお気づきの場合は、運営者までご連絡いただけると幸いです。内容を確認し、必要に応じて訂正・追記・削除等の対応を行います。