Codint Theory document 09
符号理論特論第9回補足資料

2.1 シンドローム復号，つづき

前回までの説明でスタンダードアレイによる復号が最尤復号であることを説明した． スタンダードアレイを実際に計算機で行おうとすると，ベクトル空間 $V$ の全てを要素とする表を作らなければならない．符号語長が $100$ であれば 表に格納する要素は $2^100$ 個になる．この数の要素をメモリに保存し， なおかつ復号時には受信語 $\vec{y}$がその中のどこにあるかを探索しなければ いけない．

スタンダードアレイは現実的に使用する目的で導入した復号法ではない． 次に説明するシンドローム復号が最尤復号であることを理解するために 用いた，中間的な復号法である．スタンダードアレイによる復号が 最尤復号であることは示したので，シンドローム復号がスタンダードアレイ による復号と同じものを出力することを示すことでシンドローム復号が 最尤復号であることを示す．

今回の最初に説明したように$[n,k]$線形符号であれば，スタンダードアレイによる 復号で最尤復号を行うことができるが，$2^n$ のメモリと探索時間がかかる． シンドロームを使うことでこれを大幅に削減できる．

ある$[n,k]$線形符号 $C$ について，全空間$V$の要素 $y$ のシンドロームは 以下のような列ベクトルとして定義される． ここで $H$ は $C$ のパリティ検査行列でその 各行を $\vec{h_1},\vec{h_2},\ldots,\vec{h_{n-k}}$ とする． \[ \mbox{syn}(\vec{y}) = \left( \begin{array}{l} \vec{y}\cdot\vec{h_1}\\ \vec{y}\cdot\vec{h_2}\\ \vdots\\ \vec{y}\cdot\vec{h_{n-k}}\\ \end{array} \right) = H\vec{y}^T \]

例 9.1
例 7.1 の符号の生成行列は \[ G =\left( \begin{array}{cccc} 1 & 0 & 1 & 0\\ 0 & 1 & 1 & 1 \end{array} \right) \] であった．パリティ検査行列 $H$ は定理 1 を使って \[ H =\left( \begin{array}{cccc} 1 & 1 & 1 & 0\\ 0 & 1 & 0 & 1 \end{array} \right) \] と求められる．$H$ の各行は $\vec{h_1} = 1110, \vec{h_2} = 0101$ である． 受信語 $\vec{y} = 0011$ のシンドロームは \[ \mbox{syn}(0011) = H \vec{y}^t = \left( \begin{array}{cccc} 1 & 1 & 1 & 0\\ 0 & 1 & 0 & 1 \end{array} \right) \cdot\left( \begin{array}{r} 0\\ 0\\ 1\\ 1 \end{array} \right) = \left( \begin{array}{r} 0011 \cdot 1110\\ 0011 \cdot 0101\\ \end{array} \right) = \left( \begin{array}{r} 1\\ 1\\ \end{array} \right), \] 受信語 $\vec{y} = 1010$ のシンドロームは \[ \mbox{syn}(1010) = H \vec{y}^t = \left( \begin{array}{cccc} 1 & 1 & 1 & 0\\ 0 & 1 & 0 & 1 \end{array} \right) \cdot\left( \begin{array}{r} 1\\ 0\\ 1\\ 0 \end{array} \right) = \left( \begin{array}{r} 1010 \cdot 1110\\ 1010 \cdot 0101\\ \end{array} \right) = \left( \begin{array}{r} 0\\ 0\\ \end{array} \right), \] となる．

（例終わり）

シンドロームに関して以下の定理が成り立つ

定理 3
あるコセットの要素のベクトルのシンドロームは全て等しい． また，異なるコセットの要素のベクトルのシンドロームは異なる． $2^{n-k}$個のありうるシンドロームは全てどれかのベクトルの コセットのシンドロームとして現れる．

例 9.2
例 9.1 で使用した例 7.1 の符号を例として説明する．この符号の全ての コセットは \begin{eqnarray} \{0011, 1001, 0100, 1110\}\nonumber \\ \{0000, 1010, 0111, 1101\}\nonumber \\ \{0001, 1011, 0110, 1100\}\nonumber \\ \{0010, 1000, 0101, 1111\}\nonumber \\ \end{eqnarray} であった．例 9.1 の 2 つの受信語 $0011$ と $1010$ は別のコセットの要素で，シンドロームは異なっている． ベクトル $0011$ と同じコセットの要素である $1001$ のシンドロームは \[ \mbox{syn}(1001) = \left( \begin{array}{r} 1001 \cdot 1110\\ 1001 \cdot 0101\\ \end{array} \right) = \left( \begin{array}{r} 1\\ 1\\ \end{array} \right) \] となり，$0011$ のシンドロームと等しい．

コセット $\{0011, 1001, 0100, 1110\}$ のベクトルのシンドロームは $\left( \begin{array}{r} 1\\ 1\\ \end{array} \right) $，コセット $\{0000, 1010, 0111, 1101\}$ のベクトルのシンドロームは $\left( \begin{array}{r} 0\\ 0\\ \end{array} \right) $ である．他のベクトルについては，コセット $\{0001, 1011, 0110, 1100\}$ のベクトルのシンドロームは $\left( \begin{array}{r} 0\\ 1\\ \end{array} \right) $ であり， $\{0010, 1000, 0101, 1111\}$ のベクトルのシンドロームは $\left( \begin{array}{r} 1\\ 1\\ \end{array} \right) $ である．これで要素が 2 個の列ベクトルの全パターン$2^{n-k}=2^{4-2}=4$ 個 全てが現れた．

（例終わり）

定理 3 の証明
まず，「同じコセットのベクトルは同じシンドロームである」ことを証明する． コセットはある $\vec{a} \in V$ を用いて $\vec{a} + C$ で表せる． このコセットの 2 つのベクトルは符号語 $\vec{c_1}, \vec{c_2} \in C$ を使って $\vec{a} + \vec{c_1}$, $\vec{a} + \vec{c_2}$ と書ける． シンドロームの第 $i$ 行はベクトルとパリティ検査行列の第 $i$ 行 $\vec{h_i}$ との内積である． $\vec{a} + \vec{c_1}$ と $\vec{h_i}$ の内積は線形性より $(\vec{a} + \vec{c_1})\cdot \vec{h_i} = \vec{a}\cdot \vec{h_i} + \vec{c_1}\cdot\vec{h_i}$，符号とパリティ検査行列の各行との 内積は $0$ なので $\vec{a} + \vec{c_1}$ と $\vec{h_i}$ の内積は $\vec{a}\cdot\vec{h_i}$ となる． 同様に $\vec{a} + \vec{c_2}$ と $\vec{h_i}$ の内積も $\vec{a}\cdot\vec{h_i}$ となり，等しい． つまりパリティチェック行列の全ての行との内積が等しいので $\vec{a} + \vec{c_1}$ と $\vec{a} + \vec{c_2}$ のシンドロームは 同一である． つまり，同じコセットのベクトルは同じシンドロームであることがいえた．

次に「異なるコセットのベクトルは異なる」ことを証明する． $\vec{a} +C$ と $\vec{b} +C$ が異なるシンドロームであるとし， 背理法の仮定として， 前者のベクトル $\vec{a}+\vec{c_1}$ と後者のベクトル $\vec{b} + \vec{c_2}$ のシンドロームが等しかったと仮定する． これは式で書くと， \[ (\vec{a}+\vec{c_1})\cdot\vec{h_i}=(\vec{b}+\vec{c_2})\cdot\vec{h_i} \hspace{20pt}(\mbox{ただし}1\leq i \leq n-k) \] であることを意味する．線形性と符号語とパリティ検査行列の内積が $0$ であることを使って， \[ \vec{a}\cdot\vec{h_i}=\vec{b}\cdot\vec{h_i} \hspace{20pt}(\mbox{ただし}1\leq i \leq n-k) \] 移項して， \[ (\vec{a}-\vec{b})\cdot\vec{h_i}=0 \hspace{20pt}(\mbox{ただし}1\leq i \leq n-k) \] これは $\vec{a}-\vec{b}$ が符号語であることを意味する． しかしそうすると $\vec{a}$ と $\vec{b}$ が同じコセットということになり，矛盾が生じる．これにより， 仮定法の仮定は否定され，$\vec{a}+\vec{c_1}$ と $\vec{b} + \vec{c_2}$ のシンドロームは異なる．るまり， 相異なるコセットのベクトルのシンドロームは異なることがいえた．

これらのことからコセットの数だけシンドロームがあることになるので コセットの数が $q^{n-k}$ であることからシンドロームも $q^{n-k}$ 個存在する．これは $q$ 元シンボルの長さ $n-k$ のベクトルの全ての種類である．

（証明終わり）

定理 3 は，「シンドロームを計算すれば，そのベクトルが どのコセットかわかる」ことを意味している．そして そのコセットのコセットリーダーがわかれば， スタンダードアレイを使った復号法の

1. 受信語 $\vec{y}$ の所属するコセットを探す．
2. そのコセットのコセットリーダーを誤りベクトル $\vec{e}$ として $\vec{y}-\vec{e} = \vec{x}$ に復号する． （$y$ が書かれているの列の一番上の符号語に復号する．）

と同じ結果を得ることができる．これがシンドローム復号である． シンドローム復号ではスタンダードアレイ全体を記憶することをせず， シンドロームと対応するコセットリーダーの組のみを記憶する．

例 9.3
例 9.2 のコセットについてであれば以下のコセットリーダーと シンドロームの組を記憶する．

内積の計算方法を考えると，重み 1 のベクトルのシンドロームについて， $1000$ のシンドロームは $H$ の第1列， $0100$ のシンドロームは $H$ の第2列， $0001$ のシンドロームは $H$ の第4列であることがわかる． $0010$ のシンドロームは $H$ の第3列なので $\left( \begin{array}{r} 1\\ 0 \end{array} \right) $ で第 1 列と同じである．このため $1000$ と $0010$ は同じ コセットのベクトルになる．

（例終わり）

例9.3 を一般化すると定理 4 になる

定理 4
$C$ が 2 元符号で $\vec{e}$ が任意のベクトルであるとき， $\vec{e}$ のシンドロームは $\vec{e}$ の $0$ でない要素の 列に対応する $H$ の列の和である．

定理 4 の証明
シンドロームの定義より明らか．

（証明終わり）

起こった誤りが単一誤り（2元符号であれば1ビット誤り）であれば， シンドロームは $H$ の対応する列を抜き出したものになる．

ここでシンドローム復号の手法を改めてまとめる． まず，$[N,k]$ 線形符号 $C$ のコセットリーダーを， そのシンドロームとともにリストアップする． 同じコセットのベクトルは同じシンドロームをもつので このリストはありうる $q^{n-k}$ 個全てのシンドローム を含む．実際に，スタンダードアレイのように $q^n$ 個の エントリがあるような巨大なテーブルを作る必要はなく， $q^{n-k}$ 個のコセットリーダーとシンドロームの組を 記憶するだけでよい．

コセットリーダーはコセットのうち重みが最小のものだから， $V$ のうち重みの小さいベクトルから順にコセットリーダー候補 としてシンドロームを計算してゆけばコセットリーダーとそのシンドロームの 組を作ることができる．最初は $V$ の中で最も重みの小さいゼロベクトル のコセットリーダーである．ゼロベクトルによる $C$ のコセットは 符号語からなるコセットで，符号語と $H$ の各行の内積がゼロであることからそのシンドロームはゼロベクトルである． 次に重み $1$ のコセットリーダー候補を調べる． 候補のベクトルのシンドロームを計算し，今まで出たことがない シンドロームが出れば新しいコセットが現れたことになるので そのコセットリーダーとシンドロームの列ベクトルを記録する． 重み 1 のコセットリーダーを全て使っても全てのコセットが出現していない 場合（シンドロームの列ベクトルの全てのパターンが出ていない場合）， 重み 2 のベクトルをコセットリーダー候補として同じことを行う． このようにして $q^{n-k}$ 個の全てのシンドロームが出るまで コセットリーダーとそのシンドロームの組の記録を行う．

$q^{n-k}$個全てのコセットリーダーとそのシンドロームの組が出来上がったら， 復号は以下のように行う．

1. 受信語を $\vec{y}$ とする．
2. $\mbox{syn}(\vec{y})$ を計算する．
3. 計算されたシンドロームをリストから探す．
4. そのコセットのコセットリーダーを $\vec{e}$ として $\vec{x} = \vec{y} - \vec{e}$ を復号結果として出力する．

例 9.4
例 9.3 のコセットリーダーとシンドロームを使い， 受信語 $\vec{y} = 1100$ を復号する． $\mbox{syn}(1100) = \left(\begin{array}{r}0\\1\end{array}\right)$ である．これのコセットリーダーは $0001$ なので $\vec{x} = \vec{y}-\vec{e} = 1100 - 0001 = 1101$ を復号結果として出力する．

（例終わり）

シンドローム復号がスタンダードアレイを用いた復号法と同じ復号結果を 出力することから以下の定理がいえる．

定理5
シンドローム復号は最尤復号である．

シンドローム復号がどれだけ記憶領域を節約できるかを説明する． 最も原始的な，全符号語のテーブルを用意してそれぞれと受信語との 距離を求めて最も距離の小さい符号語に復号する最尤復号法を 符号語ルックアップ法とよび，これと比較する． $[100,60]$ 線形符号の場合テーブルルックアップ法では $2^{60}$ 個のエントリを記憶する必要があるのに対し， シンドローム復号では $2^{40}$ 個のコセットリーダーとそのシンドロームを 記憶するだけでよい．項目数で比較すると約 100 万分の 1 に削減できる． また，$2^{60}$ 個の符号語との距離を全て調べることと比較して $2^{40}$ 個のシンドロームを計算することははるかに簡単である．

どんな受信語に対しても復号語を出力しなければいけない場合は上記の方法で 完全復号を行う．一方，符号の最小重みが $d$，すなわち誤り訂正能力 $t = \lfloor (d-1)/2 \rfloor$ のとき，コセットリーダーの重みが $t$ であるシンドロームのときだけ復号し，それ以外は誤り検出にとどめる 不完全復号を行うこともできる．例えば 最小重み 5 の符号であれば，重みが $t$ 以下，つまり 1, 2 の誤り ベクトルの場合は必ず正しく復号できるし，重み 3 の誤りの場合も 正しく復号できる場合がある．もし信頼性の要求が非常に高く， 再送信が可能な場合，信頼性の低い受信語については再送信を要求する ことができる．重み3の誤りはめったに起きないのでそれを許容する場合， または再送信が不可能な場合に完全復号を利用できる．

コセットの重み をコセットの中で 最小の重みをもつコセットリーダーの重みとして 定義する．符号は重み 0 のコセットである． コセット重み分布をコセットの重みが $i$ であるコセットの数 $a_i$ の集合 $\{a_i\}$ として定義する．

例 9.5
例 9.3 のコセットリーダーの重みが $0, 1, 1, 1$ であるから， この符号のコセット重み分布は $a_0 = 1, a_1 = 3$ である．

誤り訂正に使ったコセットリーダーが実際に起こった誤りであったとき， かつそのときだけメッセージは正しく復号される．このことから， コセット重み分布$a_i$ を使うと正しく復号できる確率 $P$ を求めることができる．

$[n,k]$ 2 元線形符号を通信路として BSC を用いて使った場合， 重み $i$ の誤りの一つが起こる確率は $q^{n-i}p^i$ であり，その重みをもつコセットリーダーが $a_i$ 個 あることから正しく復号できる確率は， \[ P = \sum_{i=0}^{n}a_iq^{n-i}p^i \] である．

二項係数を知ることは有用である．$n\geq r \geq 0$ である整数 $n$ と $r$ についてサイズ $n$ の集合のサイズ $r$ の部分集合の個数を 二項係数 \[ \left( \begin{array}{r}n\\r\end{array} \right) \] という．$n$ choose $r$ とよみ， \[ \frac{n!}{((n-r)!r!)} \] に等しい． 長さ $n$，重み $r$ の 2元ベクトルの個数は $\left( \begin{array}{r}n\\r\end{array} \right)$ である．$r > n$ の場合は $\left( \begin{array}{r}n\\r\end{array} \right)$ は $0$ と定義される．二項係数は正しく復号される確率を 求めるときに使われる．

課題9

\[ G =\left( \begin{array}{cccc} 1 & 0 & 1 & 1\\ 0 & 1 & 0 & 1 \end{array} \right) \] を生成行列とする符号 $C$ について以下の問に答えよ．

1. $C$ の検査行列 $H$ を書け．
2. 全てのコセットの，コセットリーダーとシンドロームの組を書け． メールでは列ベクトル $\left( \begin{array}{r} a\\ b \end{array} \right)$ を「(a,b)T」と書け．
3. 受信語 $\vec{y} = 0111$ を受信したときのシンドローム復号の手順を 書け．

授業の6日後までにメールで提出せよ． メールの件名（サブジェクト）は CT09 とせよ．

課題提出の注意事項

• hiroshi@tokai.ac.jp宛に 大学のメールアドレスから提出せよ．
• メールに不調があったときの ためにCc:で自分宛にも送信せよ．