数理解析研究所講究録1106 巻 1999 年 50-6050

線形符号の復号法について(Daisuke Ikegami)1

池上大介

大阪大学理学研究科

Abstract– This paper introduces a procedure for decoding linear codes up to half
. Tzeng
the Feng-Rao bound which is defined by R. Pellikaan [5]. G-L. Feng,.N.Rao found the procedure [2], [1], and they showed it was a generalization
andof the Berlekamp-Massey algorithm [3] in their paper [1]. We summarize thisdecoding methods from the view due to Miura’s thesis [4].
decoding, Feng-Rao designed distance, Feng-Rao bound,$\mathrm{K}.\mathrm{K}$$\mathrm{T}.\mathrm{R}$$\mathrm{K}\mathrm{e}\mathrm{y}_{\mathrm{W}\mathrm{o}\mathrm{r}}\mathrm{d}\mathrm{s}-\mathrm{F}\mathrm{e}\mathrm{n}\mathrm{g}-\mathrm{R}\mathrm{a}\mathrm{o}$BCH decoding

1

はじめに

1.1

誤り訂正符号と復号問題とは$q$個の元からなる有限体を

Definition 1$F_{q}$

上の$n$$F_{q}$と表す.

$n$を固定する.

次元ベクトル空間の部分空間 $C$ を線形符号, または単に符号と呼ぶ.

以下, 特に断わらない限り $k:=\dim \mathcal{F}C$ とおく.

Definition 2(Hamming 距離)$\mathrm{b}:=(b_{1}, \ldots, b_{\mathfrak{n}})\in \mathcal{F}^{n}$とおく. 正整数$\tau:=r_{l}$に対し,を符号 $C$ の符号長,$n$$\mathrm{a}:=(a_{1}, \ldots, a_{\hslash})$$k$

を符号 $C$ の次元と呼ぶ.

,$\mathrm{d}(\mathrm{a},\mathrm{b}):=\#\{i|a_{i}\neq b_{i}\}1$を a と$\mathrm{b}$のHamming 距離 と呼ぶ.

Hamming 距離は距離の公理を満たす.
符号 $C$ に対し,$\mathrm{d}(C, a):=\min_{\mathrm{a}C\ni \mathrm{c}\neq}\#\{i| Ci\neq a:\}$と表す. また,$\mathrm{d}(C):=$$\min_{\prime,c\ni \mathrm{c},\mathrm{c}’,\mathrm{c}\neq \mathrm{c}}\#\{i| ci\neq c_{*}’.\}$

を符号 $C$ の最小距離と呼ぶ. 以下, 特に断わらない限り$d:=\mathrm{d}(C)$とおく.

Definition 3(Hamming 重み) $\mathrm{w}(a):=\#\{i|a:\neq 0\}$ を a の Hamming 重みと呼ぶ.
正整数 $t\leq(\mathrm{d}(c)-1)/2$ を固定する. この定義のもとで,$t$

限界距離復号を定義する.

[ 限界距離復号]$t$

符号 $C$ におけるInput:
Output:$t$

限界距離復号とは次のアルゴリズムを言う:$\mathrm{y}\in \mathcal{F}^{n}$もし$\mathrm{d}(C,\mathrm{y})\leq t$$\mathrm{d}(\mathrm{c}, \mathrm{y})=\mathrm{d}(C,\mathrm{y})$

ならば,

を満たす

$\mathrm{c}\in C$.

さもなければ停止するか
もしくは $C$ の元を返す.

誤り訂正符号における復号問題を次に提示する.
$0_{8\mathrm{m}400}3\mathrm{i}\mathrm{d}@\mathrm{e}\mathrm{x}.\mathrm{e}\mathrm{c}\mathrm{i}\mathrm{p}.\mathrm{o}\mathrm{s}\mathrm{k}$1 有限集合

$A$

に対し,

$*A$

u.ac.jp
を $A$ の元の個数とする.

51[復号問題]
符号 $C$ および正整数 $t\leq(\mathrm{d}(C)-1)/2$ が与えられたとき,

$C$

の

$t$

限界距離復号をより少ないメモリー,

計算量で行うアルゴリズムを求めよ.
この論文では Feng-Rao 復号法を紹介する.

1.2

線形符号とは復号の対象である線形符号について, その性質をまとめる.

Definition 4 (生成行列)
Definition 5$C$の基底を各行とする$k\mathrm{x}n$$\mathrm{a}=(a_{1}, \ldots,a_{n}),\mathrm{b}=(b_{1}, \ldots, b_{n})\in\tau^{n}$$:=$$\mathrm{a}*\mathrm{b}$に対し$(a_{1}b_{1}, a_{2}b2, \ldots,a_{n}bn)\in \mathcal{F}nn$$:=$$\langle \mathrm{a},\mathrm{b}\rangle$

行列を生成行列と呼ぶ.

$. \sum_{*=1}$$aibi\in F$とする.

Definition 6$C^{\perp}:=$とする. 特に,おく.

$H$$C^{\perp}${$\mathrm{a}\in \mathcal{F}^{n}|\langle \mathrm{a},$$\mathrm{c}\rangle=0$

for$\forall \mathrm{C}\in c$}の生成行列を $H$ と表し, これを $C$ のパリティ検査行列と呼ぶ.

の各行ベクトルを$\{\mathrm{b}_{1}, \ldots,\mathrm{b}_{\mathrm{r}}\}$$r:=\dim_{\mathcal{F}}C^{\perp}$

と

と表す.

Feng-Rao 復号法

2
2.1

あらまし

この節では, まず Feng-Rao bound を定義し, そのうえで Feng-Rao 復号法を紹介する. Feng-Rao 復号法の定義は三浦の博士論文 [4] による.

2.2
$C^{\perp}$

Feng-Rao boundの基底 (行ベクトル) を$F^{n}\backslash C^{\perp}2$$\{\mathrm{b}_{1}, \ldots,\mathrm{b}_{\tau}\}$の基底 (行ベクトル) をとし,$\{\mathrm{b}_{t+1}, \ldots,\mathrm{b}_{n}\}$とする. この並び$\{\mathrm{b}_{1}, \ldots,\mathrm{b}_{n}\}$Definition 7 $i\in\{1, \ldots, n\}$ に対し,$\mathrm{s}_{\mathrm{p}\mathrm{a}\mathrm{n}}(\mathrm{b}_{1}, \ldots,\mathrm{b}_{i}):=\{\sum_{l=1}^{i}\lambda\ell \mathrm{b}\ell|\lambda_{l}\in \mathcal{F}\}$とする.
2 $A\supset B$ に対し,

$A\backslash B:=\{a\in A|a\not\in B\}$とする.

を固定する.

52

Definition 8
1.

$\mathrm{a}\in$

戸に対し, 次の 2 つの写像$\sigma,$$r:\mathcal{F}^{n}arrow\{1, \ldots, n\}$を定義する:$\sigma(\mathrm{a})=i^{\mathrm{d}}6^{t}$$\mathrm{a}\in \mathrm{S}_{\mathrm{P}}\mathrm{a}\mathrm{n}(\mathrm{b}1, \ldots,\mathrm{b}:)\backslash \mathrm{S}\mathrm{P}^{\mathrm{a}\mathrm{n}}(\mathrm{b}1, \ldots,\mathrm{b}:_{-1})$$\mathit{2}$.

$\tau(\mathrm{a})=i^{\oplus}$$\mathrm{a}\in \mathrm{S}_{\mathrm{P}^{\mathrm{a}\mathrm{n}}}(\mathrm{b}1, \ldots,\mathrm{b}:-1)^{\perp}\mathrm{B}^{\mathrm{a}}\cdot\supset$$\mathrm{a}\not\in \mathrm{S}_{\mathrm{P}^{\mathrm{a}}}\mathrm{n}(\mathrm{b}1, \ldots,\mathrm{b}:)^{1}$$\sigma(\mathrm{b}:*\mathrm{b}j)=S$を満たすような対に対し,$(\mathrm{b}:,\mathrm{b}_{\mathrm{j}})$の定義より$\sigma$$\mathrm{b}_{:}*\mathrm{b}_{j}$は$\mathrm{b}_{1},$$\ldots,\mathrm{b}_{s}$の 1 次結合として–意にかける. そこで,

(1)$\mathrm{b}_{i^{*}}\mathrm{b}_{j}=\sum_{=l1}s\alpha^{()}\mathit{1}:j|\mathrm{b}_{\ell}$

として,を決める. このとき$\alpha_{\mathit{1}}^{(i,j)}\in F^{n}$Lemma 1$0\neq \mathrm{c}\in C$$l:=\tau(\mathrm{c})$$\langle \mathrm{c},\mathrm{b}_{i^{*}}\mathrm{b}j\rangle=^{\mathrm{o}}$である.

に対して, 次が成り立つ.

1. $r+1\leq T(\mathrm{C})\leq n$
とおく. このとき,
2.
が3. 特に対$\langle \mathrm{c},\mathrm{b}_{l}\rangle\neq 0,$$\sigma(\mathrm{b}:*\mathrm{b}_{j})=^{\iota}$$(\mathrm{b}:,\mathrm{b}_{j})$$\alpha_{s}^{(:i)}\neq 0$

forl$\{\mathrm{c},\mathrm{b}:\}=0$を満たすならば,{$\mathrm{c},$$\leq\forall_{i}<l$$\mathrm{b}:*\mathrm{b}j\rangle\neq 0,$を満たすならば,$\sigma(\mathrm{b}:*\mathrm{b}_{\mathrm{j}})<l$

である.

Proof.
1.

$C^{\perp}$

およびの定義から,$\{\mathrm{b}_{1}, \ldots,\mathrm{b}_{r}\}$

義から $r(\mathrm{c})\geq r+1$ が従う. また,
が従う.
て定義から
の定義から, いま2.

$\mathrm{c}\in C\Leftrightarrow\langle \mathrm{c}, \mathrm{b}:\rangle=0$$\mathrm{c}\neq 0$であるから,

forl $\leq i\leq r$ が成り立つ. したがって定$\mathrm{c}\not\in \mathrm{s}_{\mathrm{P}^{\mathrm{a}\mathrm{n}}}(\mathrm{b}_{1,\ldots n},\mathrm{b})^{\perp}$

である.

したがっ

$r(\mathrm{c})\leq n$

る.

である.

$\mathrm{c}\in \mathrm{S}_{\mathrm{P}}\mathrm{a}\mathrm{n}(\mathrm{b}_{1}, \ldots,\mathrm{b}1-1)^{\perp}$$r(\mathrm{c})$

そこで

ゆえに,

$\langle$$\langle \mathrm{c},\mathrm{b}\iota\rangle=0$$\mathrm{c},\mathrm{b}\iota\}=0$と仮定すると,よって, ($\mathrm{c}\in \mathrm{s}_{\mathrm{P}^{\mathrm{a}\mathrm{n}}}(\mathrm{b}_{1,\ldots,\mathrm{I}}\mathrm{b})^{\perp}$$\mathrm{c},$$\mathrm{b}:\rangle=0$となり,$\tau(\mathrm{c})=l$が従う.

3. Definition 1. での基底表示から明らか.
$0$

Lemma 2

1. {
2. (
3.

$\mathrm{C}\in c_{\mathrm{e}\in},Fn,=\mathrm{y}:\mathrm{c}+\mathrm{e}$$\mathrm{c},\mathrm{b}:\rangle=0$

for$1\leq i\leq r$$\mathrm{e},\mathrm{b}_{i}\rangle=\langle \mathrm{y},\mathrm{b}_{i}\rangle$$\sigma(\mathrm{b}:*\mathrm{b}_{\mathrm{j}})\leq r$

for

ならば

について, 次が成り立つ.

‘$1\leq i\leq r$.

$\{\mathrm{e},\mathrm{b}_{\mathrm{i}}*\mathrm{b}_{\mathrm{j}}\rangle=\langle \mathrm{y},\mathrm{b}_{\mathrm{i}^{*}}\mathrm{b}\mathrm{j}\}$.

Definition 9 便利のため,$(u,v)<(i,j)^{d}\mathit{4}eu\leq i$ かつ $v\leq j$ かつ $(u, v)\neq(i,j)$と定義する.

Definition 10 (Well-behaved) 対$(\mathrm{b}:,\mathrm{b}_{\mathrm{j}})$が$\sigma(\mathrm{b}_{u}*\mathrm{b}_{v})<\sigma(\mathrm{b}:*\mathrm{b}_{j})$をみたすとき, well-behaved と呼ぶ.

for $\forall(u, v)<(i,j)$forl$\leq\forall_{i}<l$がわかの定義に矛盾する.

53

Definition 11 $s\in\{1, \ldots, n\}$ に対し,$\mathrm{W}(s):=\#\{(i,j)|\sigma(\mathrm{b}:*\mathrm{b}j)=s$

かつ$(\mathrm{b}_{i},\mathrm{b}_{j})$が well-behaved} とする.

Definition 12に対し,$F^{n}\ni \mathrm{a}:=(a_{1}, \ldots, a_{n})$$n\mathrm{x}n$行列$X(\mathrm{a})$を次のように定める.

$X(\mathrm{a}):=({}^{t}\mathrm{b}_{1}$Lemma 3 rank

Proof.

$(X(\mathrm{a}))=\mathrm{w}(\mathrm{a})$$\{\mathrm{b}_{1}, \ldots,\mathrm{b}_{n}\}$$\mathrm{w}(\mathrm{a})$である.

は $F^{n}$ の基底であるから,rankである. また${}^{t}\mathrm{b}_{\mathrm{n}})$$($($)=\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{k}($...

${}^{t}\mathrm{b}_{1}$${}^{t}\mathrm{b}_{n}$) $)=n$の定義から

rank $()=\mathrm{w}(\mathrm{a})$が成り立つ. よって結論が従う.

Lemma 4$0\neq \mathrm{c}\in C$

口

に対して,

$r:=r(\mathrm{C})$とおくとき次が成り立つ.
$\mathrm{w}(\mathrm{c})\geq \mathrm{W}(r)$Proof. Definition 12 により,.

行列 $X:=(x:,j):=x(\mathrm{C})$ を定める. Lemma 3 よりである. そこで, $n\cross n$ 行列 $Y$ を次のようにして定める: $\mathrm{Y}:=(y:,j)$ ,$n\mathrm{x}n$$X:,j$

if$\sigma(\mathrm{b}_{i^{*}}\mathrm{b}_{j})=T$$\delta^{1}\cdot\supset(\mathrm{b}:,\mathrm{b}_{j})\theta^{\backslash }$$y:,j:=\{$

条件$(^{*})$

rank$(X)\cdot\geq \mathrm{r}\mathrm{a}\mathrm{n}\mathrm{k}(Y)$をみたす坊,j について,

よび rank$(Y)=\mathrm{w}(\mathcal{T})$

が従う.

well

-

behmed... $(*)$
$0$

このとき,

$\mathrm{W}(C)=\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{k}(x)$otherwise

および rank $(Y)=\mathrm{W}(r)$ を示す.

$y:,j=\langle \mathrm{c}, \mathrm{b}_{i}*\mathrm{b}_{j}\rangle\neq 0$

まず, 先程示した Lemma 1 より,がわかっている. よって rank
お口

Proposition 1 以上の記法のもとで次が成り立つ.
$\mathrm{d}(C)\geq\min\{\mathrm{W}(\tau)|r+1\leq r\leq n\}$$(X)\geq \mathrm{r}\mathrm{a}\mathrm{n}\mathrm{k}(\mathrm{Y})$

54

. まず,

$Pr\sigma of$$\mathrm{d}(C)$の定義から,$\mathrm{d}(C)$

$=$

$=$

$=$

$\mathrm{d}(\mathrm{C}, \mathrm{C}’)$$\min_{C\ni \mathrm{c}\neq \mathrm{c}},$$C \ni \mathrm{c}-\mathrm{c}\min_{\neq 0},\mathrm{d}(\mathrm{c}-\mathrm{c}’,0)$$\min_{c\ni \mathrm{c}\neq 0}\mathrm{w}(\mathrm{c})$である. ゆえに Lemma 4. および Lemma 1 より結論が従う.

$\mathrm{O}$

これを Feng-Rao bound と呼ぶ.

Definition 13 $d_{FR}:= \min\{\mathrm{W}(\tau)|r+1\leq r\leq n\}$ と書き,

Gauss の消去法

2.3

この節では Feng-Rao 復号法の鍵となる行列の Gauss の消去法について述べる.

Algorithm 1 (Image and Karnel of a matrix$m\mathrm{x}n$の行列 $(m\leq n),\tilde{X}:,j\in F$ とするを与える.

$\circ$$\tilde{X}$)$\tilde{X}:=(\tilde{x}:,\mathrm{j})$X の image と kernel を求める, Gauss の消去法を変形した次$alg_{\theta\dot{\mathcal{H}}}thm$

Input :
Output : $M=(m:,i)$$\tilde{X}:=(\tilde{x}:,\mathrm{j})$$\mathrm{v}^{(s)}:=$$(v_{1}^{()}’, ..

., v_{n^{\theta)}}^{(})$$m\mathrm{x}n$$m\cross n$$\mathrm{v}^{(s)}$

:

行列
行列
$\tilde{X}$$m_{i,j}=0$の Kernelor 1,$1\leq\forall_{S}\leq \mathrm{r}\mathrm{a}\mathrm{n}\mathrm{k}(\tilde{X})$$i:=1,j:=1,$ $X:=(x:,\mathrm{j}):=X$
1. [Initialize] $r:=0,$ $m_{i_{l}j}=0$ for
かつとして, そならば, $r:=$. $r+1,$
もし,$m_{u,j}=0$
for
2. [Scan Column]の (i, のを保存して次に進め. この (i, のを “ピボット’ と呼ぶ. そうでなければ, 4 に行け.とする.
3. [Eliminate] $x:,\mathrm{j}:=-1,$ $X:,v:=-x:,v/x:,j$ for $v=j+\mathrm{i},$$\forall(i,j),$$1\leq\forall u\leq i$$x:_{|j}\neq 0$$\ldots,$$d_{\mathrm{j}}:=0$$n$$(a)l:=1$ とする.
$(b)\mathrm{r}\ell,j:=0$ とする.

(i). $s:=j+1$ とする.
(ii).
,
へ行け. さもなければ次に進め.
(iii). $s<n$ ならば, $s:=s+1$ として$\mathit{1}:=l+1$
として -?b へ行け. さもなければ次に進め.
$(c)\ell<m$ ならば,
$x_{\mathit{1},s}:=x_{\ell,s}+X_{\ell,j}m:_{S}$$\mathit{3}(b)(ii)$$(d)m:,j:=1,$ $d_{j}=i$ とする.
4. [Finished?] もし $l<n$ ならば $l:=l+1$ として 2 に飛べ.

5. [Output] $M=(m:,j)$ を返せ. $d_{s}=0$ となるような $s\in\{1, \ldots, n\}$ はこの時点でちょうど$r=\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{k}(X)$個ある. それらに対して,$x_{d_{\mathrm{j}},s}$$\mathrm{v}^{(s)}:=(v^{(}js))1\leq j\leq n=\{$$\mathrm{i}\mathrm{f}d_{j}>0$1$\mathrm{i}\mathrm{f}j=s$$0$otherwise

としてそれを返せ.

Lemma 5成り立つ.

$m\mathrm{x}n$行列 $\tilde{X}(m\leq n)$ に対して,$Algo\dot{\mathrm{M}}thm\mathit{1}$を適用して得る $M=(m:,j)$ について, 次が

55

1. rank $(\tilde{x})=\#\{(i,j)|m:,\mathrm{j}=1\}$ である.
ならば $m_{u,j}=0$ for2.
, かつ $m_{i,v}=0$ for$\forall_{u}<i$$m_{1\mathrm{j}},=1$

2.4$\forall_{v}<j$

である.

多数決決定

この節では, Feng-Rao 復号の鍵となる多数決決定について述べる.
$r+1\leq l\leq n$ を固定する.
$\mathrm{w}(\mathrm{e})\leq(d_{FR}-1)/2$ を仮定する.

Lemma 6行列について, AJgorithm 1 を適用して得る行列を $M$ とする. そ$\tilde{X}:=(\mathrm{f}^{\mathrm{e},\mathrm{b}_{\dot{i}^{*}}\mathrm{b}}j\})n\mathrm{x}n$

こで,
$U:=$

{

$U_{0}:=$$\{(i,j)|\sigma(\mathrm{b}:*\mathrm{b}j)\leq l-1, m:,j=1\}$$U_{1}:=$$\{(i,j)|\exists_{u<i_{\mathrm{S}}.\mathrm{t}.\sigma}(\mathrm{b}_{u^{*}}\mathrm{b}_{j})\leq\ell-1, mu,j=1\}$$(i,j)|\sigma(\mathrm{b}:*\mathrm{b}_{j})=l,$$\cup$$\{(i,j)|\exists_{v<j\mathrm{S}.\mathrm{t}}.

寡$U$$U_{2}:=$$\{(i,j)|m:,j=1\}\mathrm{n}U$$U_{3}.\cdot=$$U\backslash (U_{1^{\cup}}U_{2})$$u::=$$\# U_{\dot{*}}$$(\mathrm{b}_{i},\mathrm{b}_{j})\uparrow\mathrm{h}$well–behaved}\sigma(\mathrm{b}:*\mathrm{b}v)\leq\ell-1, m:,v=1\}$

for $\forall_{i}=0,1,2,3$

とおく. このとき,

1.
2. $u_{1}+u_{2}+u_{3}=\#$ {.

$2\mathrm{w}(\mathrm{e})+1\leq d_{FR}\leq \mathrm{w}(\ell)$$\mathit{3}$4.

$(i,j)|\sigma(\mathrm{b}:*\mathrm{b}_{j})=\ell,$$(\mathrm{b}:,\mathrm{b}_{j})[]\mathrm{h}$well– behaved}$=\mathrm{W}(\ell)$$u_{1}\leq 2u_{0}$$u_{0}+u_{2}\leq \mathrm{w}(\mathrm{e})$5. $u_{2}<u_{3}$6.

$(i,j)\in U_{\epsilon}$に対して,$\langle \mathrm{e}, \mathrm{b}_{i}*\mathrm{b}\mathrm{j}\rangle=\sum_{=\lambda 1}^{-}v((\lambda \mathrm{e},\mathrm{b}_{\lambda^{*}}\mathrm{b}_{j}\rangle j1j)$がなりたつ.

Proof.
1. 仮定
2.

$\mathrm{w}(\mathrm{e})\leq(d_{FR}-1)/2$

より.

であることから従う.
の定義から従う.

$U_{1}\cap U_{2}=\emptyset$

3.
4. $u_{0}+u_{2}\leq\#(i,j)|m_{i,j}=1=\mathrm{w}(\mathrm{e})$ より.
5. $2(u_{0}+u_{2})+1\leq W(\ell)=u_{1}+u_{2}+u_{3}$ , およびから従う.
の定義から, $X$ の第 列は第 $v(1\leq v<$ の列の線形従属であることが従う.
6.
$U_{0},$ $U_{1}$$u_{1}\leq 2u_{0}$$U_{3}$

口

$j$

56

2.5

Feng-Rao 復号法

基底表示 (Definition 1) から,$\ell\geq 1$についてゑ$\alpha_{\ell+^{l\mathrm{j}}1}^{(:})\langle \mathrm{e},\mathrm{b}\ell+1\rangle=\langle e,\mathrm{b}:*\mathrm{b}j\}-\sum\alpha^{(:}\mu--1’ \mathrm{j})\langle \mathrm{e},e\}\mu$に属する (幻) について, (が従う. -方 Lemma 6(5), (6) から,すると正しい値であることが保証される. よって次の命題が成り立つ.
$U\backslash U_{1}$Proposition 2(多数決決定) $Mwte\leq(d_{FR}-1)/2$ を仮定する. (
とする.

$U$

の元 $(i,j)$ に対し, 小行列$\overline{X}$$:=((\mathrm{e},\mathrm{b}_{u}*\mathrm{b}v\rangle)1\leq u\leq i,$$\mathrm{e},\mathrm{b}:*\mathrm{b}_{j}\rangle$$\mathrm{e},\mathrm{b}_{i}\rangle$

forを多数決により決定$1\leq\forall_{i}\leq l$$1\leq v\leq j$が既知であるに対して $Algo\text{剛ゐ_{}m}$$\mathit{1}$を適用する. 各 $(i,j)\in U\backslash U_{1}=U_{2}\cap U_{3}$ に対して,$j- \sum_{\lambda_{--}1}^{1}v\langle(\lambda \mathrm{e}\mathrm{j}),\mathrm{b}\lambda*\mathrm{b}j\rangle$を計算する. これを$\langle$$e,\mathrm{b}_{i^{*}}\mathrm{b}_{\mathrm{j}\mathrm{I}}$の推定値とする.

$\mathrm{b}_{i^{*}}\mathrm{b}_{j}$の基底表示 (Definition 1) から得られる$\langle \mathrm{e},\mathrm{b}_{\ell}+1\}$のうち最も多く現れたものが真の値である. すなわち,(:$( \sum_{\lambda--1}^{j1}v\lambda((j)e,\mathrm{b}_{\lambda}*\mathrm{b}j)--\sum_{\mu=1}^{\ell}\alpha^{(ij}l)\mathrm{t}\mu \mathrm{e},\mathrm{b}_{\mu}\})/\alpha l$のうち最も多く現れた値が yに等しい.

$\langle \mathrm{e},\mathrm{b}_{\mathit{1}+1}\rangle$

Definition 14 (Feng-Rao 復号アルゴリズム) つぎのものを準備する.
うな$(\mathrm{b}:, \mathrm{b}_{j})$$\sigma(\mathrm{b}:*\mathrm{b}_{j})\geq r+1$

に対し,$\mathrm{b}_{:}*\mathrm{b}_{j}=\sum_{l^{--}1}^{l}\alpha^{(}\mathrm{b}l:_{\dot{\theta}})l$Input:
Output:$\mathrm{y}:=\mathrm{c}+\mathrm{e}$$\mathrm{c}$もしくは, 途中で中断する.

J. [Initialize] {for$\mathrm{e},\mathrm{b}_{l}\rangle=\langle \mathrm{y},\mathrm{b}_{l}\rangle$$S_{*,\mathrm{j}}.=(\mathrm{y},\mathrm{b}_{i}*\mathrm{b}_{i}\rangle$

for$1\leq \mathrm{v}_{l}\leq r$$\forall(i, j)s.t$.

$\sigma(\mathrm{b}:*\mathrm{b}_{j})\leq r$$larrow r+1$

2. [APPly Gauss algorithm] $S=(s_{i,j})$ に Gauss algorithm (Algorithm 1) を適用する.
(っをみたす $(i,j)$ について,
3. [Calculate {$\mathrm{e},\mathrm{b}_{\ell}\rangle 1$$( \sum_{1\lambda--}^{1}v^{(}(\lambda\lambda^{*}j\}\mathrm{j})-\sum_{-}^{l}j-\mathrm{e},\mathrm{b}\mathrm{b}\mu_{-}1\alpha(|..j)\{\mu \mathrm{e},\mathrm{b}\mu\rangle)/\alpha^{(:}p\dotplus_{1}^{j)}$を計算し, もっとも多く現れた値を ($\mathrm{e},\mathrm{b}\ell+1\rangle$$(\mathrm{b}:,\mathrm{b}_{j})$とする. ただし$(^{*})$とは,が welf–behaved でかつ,

( :*bj)=\ell でかつ,$\mathrm{b}$$\sigma$$c_{i}>j$をみたす $(i,j)$ をいう.

$(^{*})$かつ F $c_{u}\neq j$ for $\forall u<i_{S}.t$ .

$\sigma(\mathrm{b}_{u}*\mathrm{b}_{v})\leq l-1$をみたす $(i,j)$ が存在しなければ復号を諦める.

をみたすよ

57

4

$[\mathrm{L}_{\mathrm{o}\mathrm{O}}\mathrm{p}]$$\cdot$$\ell<n$ならば $\ellarrow k+1$ として, 2 へ行け.

5. [Terminate]$\mathrm{r}_{\mathrm{e}=}$を計算する.

3$\mathrm{c}:=\mathrm{y}-e$を返す.

Feng-Rao 復号法と Berlekamp-Massey 復号法

3.1

あらまし

G-L. Feng,.Tzeng が論文 [1] のなかで示した (Feng-Rao 復号法は BCH 符号の復号における Berlekamp-Massey 復号法を含む–般化である》ことを検証する.
BCH 符号における Vandermonde 行列を用いた Feng-Rao 復号法について, 成分を推定する
過程は, Berlekamp-Massey 復号法におけるエラー位置多項式の計算を行う過程と同じ行列の操作である
この節では,$\mathrm{K}.\mathrm{K}$$\langle$$\mathrm{e},\mathrm{b}_{\delta-1})$

ことがわかる.

3.2

BCH 符号とはDefinition 15 (BCH 符号) をの原始 乗根とする. 正整数の最小多項式の最小公倍多項式を $g(x)$ とお .
$n$$F_{q^{m}}$$\beta$$n,$ $l,$$\delta$を与える.

$\beta^{\mathrm{I}},\beta^{\mathrm{l}+1},$$\langle$

環 $\mathcal{F}_{q}[x]/(x^{n}-1)$ のイデアル ($g(x)\}$ を考える. このとき,:$C:= \{(c0, \ldots, cn-1)\in \mathcal{F}_{q}^{n}|\langle g(X)\rangle\ni c(X)=n.-\sum_{1=0}^{1}c:x\}$は$\mathcal{F}_{q}$上の符号となる.

この $C$ を $BCH$ ($B_{oSe-}chaudhul\dot{\tau}$ -Hocquenghem) 符号という.

BCH 符号について次の Lemma がなりたつ:
Lemma 7$(\delta-1)\mathrm{x}n$行列 $H$ を次のように定める.

...

$l2+1l$)$H:=($$111^{\cdot}.\cdot$$\beta^{l+2}\beta^{\iota+}\rho_{\delta-}...11$$\beta^{()(l+-2)}\beta^{(.)}n-1\beta^{(}n-\mathfrak{n}_{1^{-1)l}(1+1)}..\delta)$$\beta^{2(-}\beta^{2(}\beta\iota+\cdot.\cdot\delta 2$

)

このとき,

$BCH$ 符号 $C$ は

$C=$

をみたす.

{

$\mathrm{c}\in \mathcal{F}_{q}^{n}|H^{t_{\mathrm{C}=}}\mathrm{o}$

in

$s-$
$\mathcal{F}_{q^{m}}^{(1})$}$\ldots,\beta^{\uparrow}+s-2$

58

Definition 16$F_{q}^{n}.\ni \mathrm{y}$に対し,$H^{t}\mathrm{y}=$

So,

とおく.

3.3

$\ldots$, S-2 をシンドロームと呼ぶ.

Berlekamp-Massey 復号法とはDefinition 17$\mathcal{F}_{q^{m}}\delta-1\ni \mathrm{a}=$($a\mathit{0},$$\ldots$, ai-2) に対し,$I( \mathrm{a}):=\max\#$とする.
$\mathrm{J}.\mathrm{L}$$\ell(\mathrm{a})${ $i|a_{u}\neq 0$ for$0\leq\forall_{u}\leq i$}

を a の長さと呼ぶ.

. Massey の論文 [3] によれば, この定義の下で BCH 符号における復号問題は次の問題におきかえる

ことができる.

[Massey によるをみたす$\mathrm{B}\mathrm{M}$

復号法の行列表示][3]$=$$\mathrm{c}\in \mathcal{F}_{q^{m\mathrm{P}}}\delta-2,\in F_{q^{m}}\delta-1$のうち,$\ell(\mathrm{p})$を最小にするものを, 右辺の行列を上の行から順に線形従属性を調べることで見つけよ.

このことは次のように言いかえることができる.

[$\mathrm{B}\mathrm{M}$

復号法の言いかえ]$=(p_{0}**$$ps-2**)$$p_{1}**\cdot$
$**$

をみたす

$\mathrm{c}\in f_{q^{m}}i-2,\mathrm{p}\in F_{q^{m}}i-1$のうち,$\ell(\mathrm{p})$を最小にするものを, 左辺の行列の積を左の列から順に Gauss の消去法を用いて線形従属性を調べることで見つけよ.

59

3.4

Vandermonde 行列を用いた BCH 符号の Feng-Rao 復号法$n\mathrm{x}n$行列 $B$ を,

とおく.

$B=$

このとき $B$ は Vandermonde 行列である.

$\{\mathrm{b}_{1}, \ldots,\mathrm{b}_{n}\}$は$\mathcal{F}_{q^{m}}^{n}$(2)であるから $B$ の各$\det B\neq 0$

$i$

行を

$\mathrm{b}_{i}$とおくとの基底をなす.

$X’(e)$$:=B{}^{t}B$$=(\langle \mathrm{e},\mathrm{b}_{\delta 1}.\cdot.-\rangle S_{t}s_{1}^{0}S*-2$$\langle \mathrm{e},\mathrm{b}_{\delta-1}S_{1}**\rangle$$\{\mathrm{e},\mathrm{b}_{\delta}^{-}-1\rangle s_{\iota}***2$$\langle \mathrm{e},\mathrm{b}_{\delta-1}****\rangle$$*****\cdot.\cdot)$$S_{\delta-2}***$

とする.

3.5

Feng-Rao 復号法と Berlekamp-Massey 復号法との比較

BCH 符号におけるこれら 2 つの復号法を比較する.
を用いて BCH 符号の Feng-Rao 復号を行うとき, 成分を決定するための操作は Berlekamp-Massey 法におけるエラー位置多項式の係$X’(\mathrm{e})$$\mathrm{t}\mathrm{e},\mathrm{b}_{\delta-1}\rangle$

数ベクトル$\mathrm{c}$を決定するための操作と同等である.

この後, Feng-Rao 復号法は各 (て,Berlekamp-Massey 法は$\mathrm{c},\mathrm{p}$

を求めて
for
との積をとって復号するのに対しを用いて決まるエラー位置多項式およびエラー評価多項式から復号す$\mathrm{e},\mathrm{b}.\rangle$$\delta\leq i\leq n$$B^{-1}$

る点が異なっている.

4

最後に

一般の線形符号における Feng-Rao 復号法を紹介した. Feng-Rao bound および Feng-Rao 復号法は,
符号 $C$ および
および
の基底
の基底
の選びかたと並べかたに依存する. そこで, 符号 $C$ が与えられたときに基底と並べかたをどのように選べばよいかという問題が$C^{\perp}$

残っている.

$\{\mathrm{b}_{1}, \ldots,\mathrm{b}_{\gamma}\}$$\mathcal{F}^{n}\backslash C^{\perp}$$\{\mathrm{b}_{r+1}, \ldots , \mathrm{b}_{n}\}$

60

参考文献
Generalization of the Berlekamp-Massey Algorithm[1] Gui-Liang Feng and Kenneth K. Tzeng,for Multisequence Shift-Register Synthesis with Applications to Decoding Cyclic Codes”, IEEE
, No 1., pp. 1274-1287, Sep. 1991.
Transactions on Information Theory,$‘(\mathrm{A}$$\mathrm{v}\mathrm{o}\mathrm{l}37$[2] Gui-Liang Feng andmum Distance”, IEEE$\mathrm{T}.\mathrm{R}$.N.Rao, “Decoding Algebraic-Geometric Codes up to the Designed Mini, No 1., pp. 37-45, Jan. 1993.
on Information Theory,$\mathrm{v}\mathrm{o}\mathrm{l}39$$\prime \mathrm{n}\mathrm{a}\mathrm{n}\mathrm{s}\mathrm{a}\mathrm{C}\mathrm{t}\mathrm{i}_{\mathrm{o}\mathrm{n}\mathrm{S}}$-Register Synthesis and BCH Decoding”, IEEE TRansactions on Information[3] James L. Massey,
IT-15, No 1., pp. 122-127, Jan. 1969.
Theory,$u_{\mathrm{S}\mathrm{h}\mathrm{i}\mathrm{f}\mathrm{t}}$$\mathrm{v}\mathrm{o}\mathrm{l}$[4] 三浦晋示, 代数幾何に基づく誤り訂正符号の研究, 博士論文, 東京大学, 1997.

-Muller and geometric Goppa codes”, Appeared[5] Ruud Pellikaan,
shift bound for cyclic,.
in Arithmetic, Geometry and Coding Theory 4, Luminy 1993 (R. Pellikaan, M. Perret and$‘(\mathrm{T}\mathrm{h}\mathrm{e}$${\rm Re} e\mathrm{d}$$\mathrm{S}.\mathrm{G}$.

$\mathrm{V}\mathrm{l}\check{\mathrm{a}}\mathrm{d}\mathrm{u}\mathrm{t}\mathrm{e}\mathrm{d}_{\mathrm{S}}.$), Walter de Gruyter &Co, Berlin, pp. 155-174, 1996.