提案アルゴリズムについて

本節では，(n, k, d)-BCH符号を用いて，逆シャノン定理を検証するアルゴリズムについ て述べる．このアルゴリズムは，誤り確率ϵの2元対称通信路を再現するために，(n, k, d)-BCH符号のレートRがどの程度必要なのかを調べている．

RST検証アルゴリズム

1．n, ϵを決める．

2．k, dを決める．（C_n ={cⁿ₁, cⁿ₂,· · · , cⁿ₂k}が定まる．） 3．xⁿ∈ {0,1}ⁿをランダムに作成する．

4．d_H(xⁿ, cⁿ_i)が n·ϵに一番近い符号語 cⁿ_i を選ぶ．（i= 1∼2^k） 5．d_H(xⁿ, cⁿ_i)≈n·ϵなら成功とする．

6．3．∼6．をN 回繰り返す．

7．R= ^k_nでの成功率（成功数/N)を計算する．

8．kを変えて 2.∼7.を実行する．

RST検証アルゴリズムでは，まずn, ϵ, k, dを決定する．これにより，(n, k, d)-BCH符号 の符号語C_n={cⁿ₁, cⁿ₂,· · · , cⁿ₂k}が定まる．次に，入力xⁿ ={0,1}ⁿをランダムに作成し，

xⁿとのハミング距離がn·ϵに最も近い符号語cⁿ_i を一つ選ぶ．再現したい通信路の入力 xⁿ と出力yⁿ間のハミング距離 d_H(xⁿ, yⁿ)はn·ϵ程度だと考えられるので，d_H(xⁿ, cⁿ_i)≈n·ϵ ならば，再現に成功したと見なす．そして，xⁿをランダムに作り，ハミング距離が n·ϵ に近い符号語を探索する事を N回繰り返し，成功率を計算する．上記の計算を kを変え る事でレート Rと成功率の関係を調べた．（R =k/nのため，nを固定した場合，kを変 えることと Rを変えることは同義である．）

ここで(n, k, d)-BCH符号は誤り訂正符号なので，xⁿをそのまま復号すると，任意のハ

ミング距離にある符号語を見つけられないという問題がある．しかし，全探索を行うと 計算量が O(2^k)となり，プログラムの効率が悪くなってしまう．そのため，本研究では BCH符号の性質を利用し，目的の符号語を効率良く探索するプログラムを加えた．その アルゴリズムを以下で述べる．

6.2.1 符号語の探索方法

まず，準備として (n, k, d)-BCH符号の中で，ハミング重み w_H(cⁿ)が小さい符号語を 以下のアルゴリズムで探索する．

最小重みの符号語探索アルゴリズム

1．u^k = 100· · ·000を符号化する．（C_n(u^k)を求める．） 2．ハミング重みw_H(C_n(u^k))を計算する．

3．w_H(C_n(u^k)) =dなら終了する．

4．u^kを１ビット右へシフトする．

5．2.∼4を繰り返し，最小重みの符号語C_minを見つける．

最小重みの符号語探索アルゴリズムは，u^k = 10· · ·00を1ビット右へシフトさせ，u^k = 00· · ·01までの全ての符号語についてハミング重みを調べている．また，(n, k, d)-BCH符 号の場合，00· · ·00は符号語なので，符号語の最小重みは符号語間最小距離 dより大き い．そのため，ハミング重みがdの符号語が見つかれば，アルゴリズムを終了させる．

(n, k, d)-BCH符号は線型符号の１種のため，C_nが BCH符号であるとき，

∀x,y∈C_n,x⊕y∈C_n (6.1)

が成り立つ．

xⁿとのハミング距離 n·ϵの符号語を探索をするアルゴリズムは，式(6.1)と定義24を 利用している．具体的に述べると，始点となる符号語を一つ求め，最小符号語アルゴリ ズムで求めたC_minを巡回させていき，符号語に加えることで目的の符号語に近づけてい る．

まず，始点となる符号語を決める．この時，適当な符号語を選ぶよりも，可能な限り xⁿにハミング距離が近い符号語を選ぶ方が効率が良いと考えられる．(n, k, d)-BCH符号 において，ある符号語からのハミング距離が t以下の系列xⁿに対しては誤りの訂正は容 易である．これは，xⁿから一番ハミング距離が近い符号語を見つけることは容易である 事を示している．しかし，tを越える系列に対してはその限りではない．実際，そのよう な系列に対して，最も近い符号語を求める効率の良い方法は見出されていない．そこで，

本研究では，入力されたxⁿに対し誤り訂正を行う．訂正できれば，訂正した符号語を用 いて探索を行う．しかし，訂正出来ない場合，xⁿ =x1x2· · ·xnの n−kビット目から n ビット目（xn−kxn−k+1· · ·xn）を符号化し，その符号語 cnを始点とする．このようにす

る事で，n−kビット目から nビット目までは xⁿと cⁿは同じ文字であるため，xⁿとの ハミング距離が n−k以下の符号語を始点にする事が出来る．

以上で求めた符号語cⁿとCminを用いて，xⁿとのハミング距離が n·ϵとなる符号語を 探索する．そのためのアルゴリズムを以下で示す．

距離 n·ϵの符号語探索アルゴリズム

1．C^′ =cⁿ⊕C_minを求める．

2．xⁿとのハミング距離 d_H(xⁿ, C^′)を計算する．

3．dH(xⁿ, C^′)の値がdH(xⁿ, cⁿ)よりもn·ϵに近ければ，cⁿ :=C^′とする．（dH(xⁿ, C^′) = n·ϵなら終了する．）

4．Cminを1ビット右へシフトする．

5．1.∼4.を繰り返す．（Cminが最初の符号語に戻ったら終了）

上記のアルゴリズムについて述べる．まず，線形符号の性質（式（6.1））を利用し，最 初に求めたcⁿと C_minを排他的論理和で足しあわせることで，符号語 C^′を作成する．xⁿ とのそれぞれのハミング距離 d_H(xⁿ, cⁿ)，d_H(xⁿ, C^′)を比べ，C^′の方が n·ϵに近ければ 始点をcⁿ:=C^′で更新する．もし近くなければ，cⁿはそのままで，C_minを１ビット右に シフトさせる．例として，C_min = 10001ならば，１ビット右へシフトした後の符号語は C_min^′ = 11000となる．１ビット右へシフトした符号語 C_min^′ と c_nを排他的論理和で足し，

ハミング距離を比べる．n·ϵに近づかなければ C_min^′ を１ビット右にシフトさせる．以上 の処理を C_min^′ が C_minに戻るまで繰り返す事で，始点とした符号語を目的の符号語に近 づけている．

6.2.2 ^{提案アルゴリズム}

RST検証アルゴリズムに最小重み符号語と距離n·ϵの符号語を探索するアルゴリズム を加えた提案アルゴリズムを以下で示す．

提案アルゴリズム

1．n, ϵを決める．

2．k, dを決める．（C_n ={cⁿ₁, cⁿ₂,· · · , cⁿ₂k}が定まる．）

3．最小重みの符号語探索アルゴリズムを使用する．（C_minを探索する．） 4．xⁿ∈ {0,1}ⁿをランダムに作成する．

5．距離n·ϵの符号語探索アルゴリズムを使用し，目的の符号語 cⁿ_i を探索する．

6．d_H(xⁿ, cⁿ_i)≈n·ϵなら成功とし，成功数をカウントする．

7．4．∼6．をN 回繰り返す．

8．R=k/nでの成功率（成功数/N)を計算する．

9．kを変えて 1．∼8．を繰り返す．

提案アルゴリズムで求めた，レート Rと成功率の関係の結果を次節で述べる．