1．ま え が き 情報・通信システムに深く依存している現代社会では， 情報の伝達や記憶に対する信頼性の確保は情報化社会の 存立基盤にかかわる重要な課題である。情報・通信シス テムにおける通信媒体や記録媒体はあわせて通信路と呼 ばれ，この通信路を介して伝達・記憶される情報は，電 波障害や媒体の傷などといった確率的に発生する雑音の 影響を受ける。このような雑音の影響を取り除くために 用いられる誤り訂正符号は，情報・通信システムの重要 な基盤技術の一つとなっている。 誤り訂正符号の中でも線形ブロック符号は美しい代数 的（あるいは代数幾何的）構造を有するため，古くから その効果的な符号化法及び復号法が研究されてきた。線 形ブロック符号は，送信符号語のシンボルと同一の有限 体上から通信路の雑音が発生すると仮定した場合には高 速な復号法が存在する。しかしより一般には通信路上の 雑音は連続の濃度を有し，この雑音の発生確率を積極的 に利用する最尤復号法は通信路情報を有効に利用するた め，復号誤り確率を大幅に低減することができる。しか し符号長が大きくなるに従いその計算量が莫大となるた め，近年これを低減する研究が盛んに行われている。 なかでも符号長 n, 情報記号数 k, 最小距離 d を持つ 2 元線形 (n, k, d) ブロック符号に対し，通信路から出力され る信頼度情報に従って信頼度の高い方から線形独立な k シンボルを情報シンボルと見なした生成行列（置換生成 行列と呼ぶ）を作成し，この情報シンボルにテスト誤り パターンを加え，複数回符号化を行うことにより候補と なる符号語を多数生成する最尤復号法が種々提案されて いる1)–6) 。D. Gazelle と J. Snyders はこのテスト誤りパター ンの効率良い生成手順を提案し，メモリをほとんど用い ずに効率良く最尤復号を行う復号法を提案している（以 降 GS 復号法と呼ぶ）。 本研究では置換生成行列を用いる GS 復号法の改良を 目的とする。このとき (1) 既に生成されているいくつかの符号語を記憶して おくことにより，次に生成すべき符号語を O(n) の 計算量で生成する手法 (2) 一回の符号化で複数符号語の信頼度損失を生成・ 比較する手法
生成行列を用いた誤り訂正符号の効率的最尤復号法
小 林
学 *
An Efficient Maximum-Likelihood Decoding Algorithm using Generator Matrix
for Error Correcting Block Codes
Manabu KOBAYASHI*
Maximum-Likelihood Decoding (MLD) is the most powerful decoding for error correcting codes to minimize the de-coding error probability. However, the complexity of MLD for linear block codes is very large. Therefore, many re-searchers have been investigating to reduce the time and space complexity of MLD. D. Gazelle and J. Snyders have pro-posed an efficient MLD method using reliability-based code-search algorithm. This decoding algorithm consecutively generates candidate codewords of maximum likelihood one. Then this algorithm reduces the complexity of MLD by eliminating unnecessary candidate codewords effectively.
We propose an algorithm that efficiently generates the next candidate codeword by storing previously generated code-words for Gazelle et al. MLD decoding. Furthermore, we propose a new method to calculate the metrics of several candi-date codewords at once. Finally, we show that the complexity of the proposed decoding method is reduced compared to Gazelle et al. decoding without increase of decoding error probability.
Key words: error correcting codes, soft decision decoding, reliability information, permuted generator matrix.
Vol. 37, No. 1, 2003
* 情報工学科 講師
を導入する。結果的に GS 復号法の計算量を大幅に低減 することができることを示す。 2．準 備 2.1 通信路のモデル 符号長 n, 情報記号数 k, 最小距離 d の 2 元線形 (n, k, d) ブロック符号を C とし，符号 C に対する k 行 n 列の生成 行列を G Œ{0, 1}knと表す。このとき任意の k シンボルの 情報 u Œ{0, 1}k に対する符号語 c ŒC{0, 1}n は cuG で 定義される。またこの u より c を求める作業を符号化と 呼ぶ。 いま符号語 c(c1, c2, . . . , cn)ŒCを送信する場合，送信エ ネルギーを Esとすると符号語の各シンボル ciŒ{0, 1}は変 調器によりEs(2ci1) の信号として通信路へ送出される。 この送信信号は信号対雑音比 Es/N0の加法的白色ガウス 雑音 (AWGN) 通信路を介して送信されると仮定する。す なわち n シンボルの雑音系列を z(z1, z2, . . . , zn)Œ n と表 すと，各シンボル ziは独立にガウス分布(0, N0/2)に従 い，受信側で受信する系列 w Œn の各シンボル wiは送 信 シ ン ボ ルEs( 2 ci1) と 雑 音 シ ン ボ ル ziの 和 wi Es(2ci1)ziで表される。 受信側では受信系列 w から信頼度系列 qq(q1,q2, . . . , qn), qiln , を生成し，軟判定復号器に入力する。こ こで硬判定受信系列を y(y1, y2, . . . , yn), (1) と定義する。このとき軟判定復号器においてはこの qq お よび y から送信された符号語を推定する *1。 2.2 GS 復号法3) 軟判定復号器ではまず，信頼度 |qi|の大きな順に y を 置換し，これを y と表す。またこの置換と同一の順に生 成行列 G の列を置換し，この行列を G とする。さらに この生成行列 G に対して信頼度の高い方から線形独立 な k 列を見つける。この k 列を信頼度の高い順に並べ， またその他残りの列をその後にやはり信頼度の高い順に 並べた行列を作成する。最終的にこの行列を行基本操作 によってはじめの k 列を単位行列にする。本論文ではこ の行列を置換生成行列とよび，˜Gと表す。 次に信頼度系列 qq と硬判定受信系列 y をこの置換生成 行 列 の 信 頼 度 の 順 に 置 換 し た ベ ク ト ル を そ れ ぞ れ
q˜(q˜1, q˜2, . . . , q˜n), y˜(y˜1, y˜2, . . . , y˜n)とする *
2
。いま u˜(u˜1, u˜2,
. . . , u˜k)Œ{0, 1}kを y˜ のはじめの k シンボルとする。すなわ
ち u˜iy˜i, i1, 2,..., k である。ここで GS 復号法は u˜ を情報
とみなして置換生成行列 G˜ により符号化し， 符号語 c˜0u˜G˜ を生成することからはじめる * 3 。GS 復号法では この u˜ にテスト誤りパターンを加え，これを G˜ により符 号化することを繰り返し，最尤の符号語が得られたと判 定されるまで候補符号語を生成する。 定義 1 長さ n の 2 元系列 x(x1, x2, . . . , xn) {0, 1} n に対 し信頼度の損失 L(x) を次式で定義する *4。 (2) さらに x の Hamming 重みを wH(x) と表す。 このとき，˜qq に対する C˜ の中の最尤の符号語 c˜* は (3) を満足することが一般に知られている。 定義 2 l0, 1, 2,..., k に対し l{eŒ{0, 1}k|w H(e)l} , (4) と定義する。さらにlに対し，その要素をそれぞれ 2 進
数の整数と見たとき，数の小さい順に ei(ei,1, ei,2, . . . , ei,k),
1, 2,..., , と順序付ける。すなわち 1pq を満 たす任意の ep, eqŒlに対し (5) が成り立つものとする。 このとき ei1から eiは次のようにして生成することが できる。まずlの始めの要素を e1(0kl, 1l)とする。た だし (0a, 1b) は(00 · · · 0 11 · · · 1)を表すものとする。また i a
}
b}
ep j k j e j k q j k j j k ,2 ,2 , 1 1Â
Â
k l Ê Ë Á ˆ ¯ ˜ k l Ê Ë Á ˆ ¯ ˜ L L C ( ˜ min ( ˜) ˜ ˜ c c c *) Œ xi i n 1Â
L yi x i n i i i i yi xi ( ) ( ˜ )| ˜ | | ˜ |. |˜ x 1Â
≈Â
π q q yi i 0 0 1 , ; , q otherwise , Ï Ì Ó P w P w i i ( | ) ( | ) 1 0 *1|qi|は値が大きいほど yiciである確率 P(yici)が大
きいので，|qi|は信頼度と呼ばれる。
*2
従って 1ijk に対し |˜qi||˜qj|, k1ijn に対
し |˜qi||˜qj|である。 *3C˜ の符号語すべてをこの置換生成行列の信頼度の順 に置換した符号を C˜ と表す。すなわち C˜{uG˜|u Œ {0, 1}k} である。従って ˜c0ŒC˜ である。 *4 ≈ は排他的論理和を表す。
2, 3, . . . , それぞれに対し eiは，ei1の最も右にある部 分系列 (0, 1) の並びを (1, 0) に変更し，これより右にある ei1の 部 分 系 列 を (0a, 1b)に 置 き 換 え る 。 た だ し b は wH(ei)l となるように選ばれる。このとき，最も簡潔な GS復号法は次のように表される。 [GS Decoding Algorithm] 1) c˜0:u˜ ˜G を生成し，c˜*:c˜0; L:L(c˜0); l:1 とする。 2) e1Œlを生成する。 もし次式を満足するならば c˜* を出力し終了。 (6) そうでなければ c˜1:(u˜≈e1) ˜Gを生成する。 もし L(c˜1)L ならば L:L(c˜1)かつ c˜*:c˜1; 3) i:2, 3, ..., それぞれに対し次の操作を繰り返す。 a) ei1より eiを生成し，c˜1:(u˜≈ei) ˜Gを生成する。 b) もし L(c˜i)L ならば L:L(c˜i)かつ c˜*:c˜i; 4) l:l1; もし lk ならば 2) へ。 そうでなければ c˜* を出力し終了。 このアルゴリズムにおいて，ステップ 3)におけるテス ト誤りパターン eiの生成と c˜iの符号化が最も計算量を 必要とする。そこで，Gazelle et al. は不必要なテスト誤 りパターンを効率良く省く手法を提案した。ステップ 3) において，ある eiŒlに対し (7) ならば LL(c˜i)が成り立つ。従って式 (7) が成り立つよう な eiは符号化する必要がないことが分かる * 5 。さらに Gazelle et al. はある eiについて式 (7) が成り立ったときに， 連続して式 (7) が成り立ってしまうテスト誤りパターンを 効率良く取り除くアルゴリズムを示した。いま，ある eiŒlに対し式 (7) が成り立ったと仮定する。また eiの直 前に生成されたテスト誤りパターンを ep(ep,1, ep,2, . . . , ep,k) と表す。このとき次のテスト誤りパターン es(es,1, es,2, . . . , es,k)は以下のようにして生成される。まず ep,I0, ep,I11, ei,I1, ei,I10 を満たす位置 I を見つける。ここで仮のテ
スト誤りパターン e¯(e¯1,e¯2, . . . , e¯k)を次のように与える。
(8) もし wH(e¯)0 ならばlの残りの要素全てを削除するこ とができる。そうでなければ esは，e¯ の最も右にある部 分系列 (0, 1) の並びを (1, 0) に変更し，これより右にある e¯ の部分系列を (0a, 1b) に置き換える。ただし b は wH(es)l となるように選ばれる。 このようにテスト誤りパターンを更新しても GS 復号 法の最尤性は失われない。なぜならば ims を満たす mに対し (9) が常に成り立つからである。 結果的に，GS 復号法は効率良く不必要なテスト誤り パターンを削除することができ，符号化回数は少なくす む。また，復号に必要となるメモリ量も非常に少なくす む利点も併せ持つ。 ここで GS 復号法に必要となる計算量について述べる。 まず信頼度の高い順に並べ替えるのに O(n log n) の計算量 が必要となる。また ˜Gを生成する計算量は O(nk2)または O(n(nk)2) で済むことが知られている3),4) 。これらは復号 を通して 1 回行えば良い。これに対し GS 復号法のス テップ 3) の符号化は，通常の手法を用いると 1 回当り O(nk)の計算量が必要であり，これを複数回繰り返すた め復号全体の計算量としてはこの符号化に必要となる計 算量が支配的となる。 そこで本論文ではこの GS 復号法全体で支配的となる， 符号化の計算量および符号語の信頼度損失を求める計算 量双方の低減を目的とする。 3．符号語更新アルゴリズム GS復号法は符号化する回数は少なく済むが，1 回の符 号化に必要となる計算量は通常と変わらない。しかしテ スト誤りパターン同士はさほど Hamming 距離が離れて いるわけではない。そこで本節では生成行列の一部の行 を復号途中にて得られる符号語に加えることにより，次 の候補符号語を高速に導出するアルゴリズムを提案する。 定義 3 置換生成行列 ˜Gを次式のように表現する。 ei j j e j k m j j j k ,| ˜ |q ,| ˜ |,q 1 1
Â
Â
e e j I I j k j i j , , ; , 1 1 0 . Ï Ì Ó L ei j j j k ,| ˜ |,q 1Â
k l Ê Ë Á ˆ ¯ ˜ L e j j j k 1 1 ,| ˜ |.qÂ
k l Ê Ë Á ˆ ¯ ˜ *5Gazelle et al. は式 (7) より厳しい十分条件も示してい るが，簡単のため本論文では触れない。しかし本論文 の議論はより厳しい十分条件を用いても同様に成り立 つ。(10) また j1, 2, ..., k1 それぞれに対し fjg˜j≈ g˜j1と定義す る。 このとき次の補題が成り立つ。 補語 1 前節で述べた不必要なテスト誤りパターンを 省く GS 復号法のステップ 3) におけるテスト誤りパター ン eiに対し，eiの直前に生成されたテスト誤りパターン
を epとし，ep,I0, ep,I11, ei,I1, ei,I10 を満たす位置を
Iとする。このとき
(11)
を満たす eq, は qp が成り立ち，
(12)
を満足する。
（証明）まず，eiと epについて，ei,jep, j, j1, 2,..., I1,
である。またその生成手順より(ei,I2, ei,I3, . . . , ei,k)(0 a, 1b) である。 ただし a, b は wH(ei)l を満たす整数である。 従って (13) となるため，式 (11) を満たす eqは qp となる。 また式 (11) より (14) が成り立つため，補題が成り立つ。 式 (11) を満たす eqに対し符号化が行われ，c˜qが得られ ているとするとこの補題より c˜i(u˜ ≈ ei)G˜ (u˜ ≈ eq)G˜ ≈ (ei≈ eq)G˜ c˜ ≈ fI, (15) が成り立つ。また eiが式 (7) を満たさない（すなわち ei を符号化する必要がある）ならば式 (12) より c˜qは必ず得 られている。従ってこのような c˜qをメモリに蓄えておく ことにより，式 (15) から高速に符号語 c˜iを得ることがで きる。同様に j1, 2,..., k1 に対し dj|q˜j||q˜j1|と定 義すると，式 (6), (7) の右辺も効率良く求めることができ る。これらを用いた提案復号法 1 を以下に示す。
[Proposed decoding algorithm 1]
1) c˜(0):u˜G˜ を生成し，c˜*:c˜(0); L:L(c˜(0)); D(0):0; l:1 とする。 2) e1Œlを生成し，D(0):D(0):|q˜kl1|; D(kl1):D(0)と する。 もし LD(0)を満足するならば c˜* を出力し終了。そ うでなければ c˜(0):c˜(0)≈ g˜ kl1; c˜(kl1):c˜(0)とする。 もし L(c˜(0))L ならば L:L(c˜(0))かつ c˜*:c˜(0); 3) a) p:1; i:2; J:kl1 とし，e2を生成する。 b) ep, eiから I を見つけ，もし J I ならば D(I ):D(I1) dIを計算する。 もし JI ならば D(I ):D(J )dIとする。 c) もし LD(I ) を満たすならば J:I とし，esを生成す る。 生成できた場合 ep:ei; ei:esとして b) へ。 生成できなければ 4) へ。 d) もし J I ならば c˜(I ):c˜(I1)≈ f Iを計算する。 もし JI ならば c˜(I ):c˜(J )≈ f Iとする。 e) J:I; もし L(c˜(I ))L ならば L:L(c˜(I )) かつ c˜*:c˜(I ) と する。
ep:ei; i:i1 とし，eiを生成して b) へ。
4) l:l1;もし lk ならば 2) へ。 そうでなければ c˜* を出力し終了。 提案復号法 1 ではすでに得られている符号語を効率良 く利用することにより次の符号語を O(n) の計算量で求め ることができる。これは通常の符号化の O(nk) より大幅 に少ない。また既に得られた符号語を蓄えるために必要 となるメモリ量が O(nk) で済すんでいることも明らかで あろう。これは置換生成行列を蓄えるメモリ量も O(nk) で あることを考えると，さほど大きなメモリ量の増加では ない。さらに D(I ) を利用すると，L(c˜(I )) も効率良く求める ことができる。なぜなら (16) が成り立つからである。次節では，この信頼度の損失を D( ) ( ) ( ˜ ˜ )| ˜ |, I j k n j j I j y c 1
Â
≈ q L I y c j j n j I j ( ˜ )c( ) ( ˜ ˜ )| ˜ |( ) 1Â
≈ q ei j j e j k q j j j k I I ,| ˜ |q ,| ˜ | | ˜ | | ˜q q q | , 1 1 1 0Â
Â
ep j e k j j I k i j k j j I k ,2 ,2 , 2 2Â
Â
eq j j e j k i j j j k ,| ˜ |q ,| ˜ |,q 1 1Â
Â
e e j I I e q j i j i j , , , , , ; , ÏÌÔ ≈ 1 otherwise , 1 Ó Ô ˜ ˜ ˜ ˜ ˜ ˜ ˜ ˜ ˜ ˜ ˜ ˜ ˜ . , , , , , , , , , G k n n k k k n g g g 1 2 1 1 1 2 1 2 1 2 2 2 1 2 M L L M M O M L È Î Í Í Í Í Í ˘ ˚ ˙ ˙ ˙ ˙ ˙ È Î Í Í Í Í Í ˘ ˚ ˙ ˙ ˙ ˙ ˙ g g g g g g g g gさらに効率良く求める手法について述べる。 4．符号語同時生成アルゴリズム 前節で提案した提案復号法 1 では，1 回の符号化で O(n)の計算量が必要となる。この符号化・信頼度損失の 計算複数回分をまとめて 1 回で行うことができれば，さ らに計算量を低減することが可能となる。そこで本節で は，前節の提案復号法 1 におけるステップ 3) に対し，同 時に複数の候補符号語に対する信頼度の損失を（符号化 せずに）効率良く計算する手法について述べる。 そのためにまず次の定義を行う。 定義 4 2元ベクトル x(x1, x2, . . . , xk)に対し， [x]ij (xi, xi1, . . . , xj)と定義する。すなわち[x]i j は x の i から j ま での部分系列とする。 4.1 [ei] k kv(0v,1), v2 のとき
ei,k1, ei,k1ei,k2···ei,kv0, v2 であるような eiに
対し，c˜iが得られていると仮定する。このとき，1rv に対し (17) であるから c˜ir(u˜ ≈ eir) ˜Gc˜i≈ g˜k≈ g˜kr, (18) と表すことができる。この関係を利用して，0m, mh v, を満たす m, h に対し c˜imr, r1, 2,..., h, の信頼度の損 失を同時に求めることを考える。 定義 5 g˜(j )g˜k≈ g˜k j, j1, 2,..., k1, と置き，a(a1, a2, . . . , ah) Œ{0, 1} h と m に対し集合aamを (19) と定義する。また，ある集合 X {1, 2,..., n} に対し(X) を (20) と定義する。 このとき次の補題が成り立つ。 補語 2 符号語 c˜imr, r1, 2,..., h, の信頼度の損失に 対し次式が成り立つ。 (21) （証明）まず，c˜iの信頼度の損失は次式のように表すこ とができる。 (22) また，式 (19) より (23) が成り立つことに注意すると，式 (18), (22), (23) を用いて (24) となる。したがって補題が成り立つ。 補題 2 より，a Œ{0, 1}h\{0} それぞれに対し(aam)を 計算すれば，これを用いて r1, 2,..., h それぞれに対し式 (21)を求めることができる。ただし各 r1, 2,..., h で共通 に求めることができる項はなるだけ共通に計算する。ま た，目的は最も信頼度の損失の少ない符号語の探索であ るから (25) が成り立つかどうかだけ考えればよい。従って式 (25) の 右辺が最も小さい r を見つけ，式 (25) が成り立つかどう かを比較すれば良い。ここで (26) である。ただし· は集合の要素数を表す。したがって (aam), aa Œ{0, 1}h\{0}, をすべて求めるために必要となる 実数の加減算は高々 nkh 回で済む。またこの後 r 1, 2, . . . , hに対し式 (25) の右辺を全て求める計算量は，例 am h n k h a a Œ{ , } \{ } , 0 1 1 O
Â
L L i m h r ( ˜ ) ( ) , { , } c a a aŒ 0 11Â
L i m h r ( ˜ ) ( ) , { , } c a a aŒ 0 11Â
L i c y j j i j j jm r ( ˜ ) ( )˜ ˜| ˜ | |˜ , ( ) c 1 1 ≈ gÂ
q ( ˜, ˜ ˜ )| ˜ | ( ) ci j y j n j j m r j 1Â
≈ ≈ g q L i m r ci m r j y j n j j ( ˜c ) ( ˜ , ˜ )| ˜ | 1Â
≈ q { | ˜( ) } , { , } 1 1 0 1 1 j n j m r m h r g a a aŒI
L i j c y j c y i j j n j j i j j ( ˜ ) | ˜ | ( ˜ ˜ )| ˜ |. |˜ ˜ , , c q q πÂ
Â
1 ≈ L i m r L i m h r ( ˜ ) ( ˜ ) ( ) . { , } c c a a a Œ 0 1 1Â
( )X ( )˜, ˜| ˜ |, j X c y j i j j Œ ≈Â
1 q am a r h j m r r j n {1 | ˜( ) }, 1I
g e e j k k e i r j i j i j , , , , , ; , ≈ 1 1 otherwise . Ï Ì Ô Ó Ôえば h4 の場合高々 22 回，h5 の場合高々 53 回，h6 の場合高々 114 回の実数の加算で済む。以上の議論よ り，m0, h, 2h,...それぞれに対しこの手法を連続的に用 いることにより大幅な計算量の低減が期待できる *6。ま たこのとき必要となるメモリ量は，リスト構造を用いる と で済む。 4.2 [ei]kk3(0, 0, 1, 1) の場合
ei,k1, ei,k11, ei,k20, ei,k30, であるような eiに対し，
c˜iが得られている場合について考える。このとき次式が 成り立つ。 c˜i1c˜i≈ g˜k1≈ g˜k2, c˜i2c˜i≈ g˜k≈ g˜k2, c˜i3c˜i≈ g˜k1≈ g˜k3, c˜i4c˜i≈ g˜k≈ g˜k3, c˜i5c˜i≈ g˜k≈ g˜k1≈ g˜k2≈ g˜k3. (27) 定義 6 bb(b1, b2, b3, b4)Œ{0, 1}4に対し (28) と定義する。さらに D1{2, 3}, D2{1, 3}, D3{2, 4}, D4 {1, 4}, D5{1, 2, 3, 4} とし， r1, 2,..., 5 , (29) と定義する。 この定義より式 (27) は次式で表すことができる。 (30) ただし は排他的論理和の加算を表す。このとき次の 補題が成り立つ。 補語 3 r1, 2,..., 5 に対し次式が成り立つ。 (31) （証明）まず式 (28) より (32) が成り立つ。同様に (33) となり，この集合を J で表す。以上より (34) となる。したがって補題が成り立つ。 補題 2 と同様，補題 3 を用いると複数の候補符号語の 信頼度の損失を効率良く求めることができる。 具体的には提案復号法 1 におけるステップ 3) において， もし [ei] k khb1(0h1, 1, 0b), b0, である場合には補題 2 を 用いて，h 個の符号語 c˜i, c˜i1, . . . , c˜ih1の信頼度損失を一 度に導出することが可能である。 また [ep] k k3(0, 0, 1, 1) の場合，補題 3 を用いて符号語 c˜ic˜p1, c˜i1, . . . , c˜i4の信頼度損失を同時に計算可能であ る。 本節で述べた手法を用いても復号誤り確率の劣化はな いことは明らかであろう。 5．計算機シミュレーションによる評価 本節では 4 節で述べた複数符号語の信頼度損失を同時 に求める手法の有効性を示すために，計算機シミュレー ションによる評価を行う。 符 号 は 2 元 (127, 64, 21) BCH 符 号 ， 2 元 (255, 131, 37) BCH符号を用い，これらの符号に対し 3 節で述べた提案 復号法 1（表中提案 1 と表記）と 4 節で述べた提案復号 法 2（表中提案 2 と表記）それぞれに必要となる符号化 回数と，符号語の信頼度損失を求めるために必要な実数 の加減算回数を表 1, 2 に示す。表 1, 2 ではそれぞれの復 号法を 10000 回実行したときの平均を示している。4 節 の復号法は h4 とし，複数符号語の信頼度損失を求め る動作は符号化 1 回として数えている。また 1 回の符号 語の信頼度損失を求めるのに必要な実数の加減算回数は 3節の手法では cAnk1，4 節で述べた複数符号語の L i Fr ( ˜ )c ( b) , b Œ
Â
L i j J c y j i j j ( ˜ )c ( )˜, ˜| ˜ | Œ ≈Â
1 q L i r ci r j y j n j j ( ˜c ) ( ˜, ˜ )| ˜ | 1Â
≈ q { | ˜ } , { , } 1 1 1 0 1 1 4 j n k m j m g , b b bŒU
L i r L i Fr ( ˜c ) ( ˜ )c ( b) . b ŒÂ
Fr j j Dr bb Œ Œ { , }0 14 1 , b ∫ Ï Ì Ô Ó Ô ¸ ˝ Ô ˛ ÔÂ
(mod 2) b b {1 | ˜ }, 1 4 1 j n m k m j mI
g , O k h n h ( 2 ) Ê Ë Á ˆ ¯ ˜ *6 計算量の低減率の下限が 1/h であることは明らかで あろう。信頼度損失を求めるために必要となる実数の加減算は， h4 の場合 cBnkh22 とした *7。 表 1, 2 より，3 節で述べた提案復号法 1 に比べ 4 節で 述べた提案復号法 2 の符号化回数は約 1/3 程度となって いる *8 。これは理論的な最適値 1/h1/4 に近い値であり， 4節の手法が有効に働いていることを示している。さら に実際に複数符号語の信頼度損失を導出するために付加 的に必要な演算量を加味した加減算回数を見てみると， (127, 64, 21) BCH符号で 1/2 程度，(255, 131, 37) BCH 符号 では 1/3 程度となっている。これは冗長度 nk が大きく なるに従い付加的な演算量の割合が小さくなることを表 している。 6．まとめと今後の課題 本論文では置換生成行列を用いる最尤復号法の一つで ある GS 復号法の計算量を低減する手法を提案した。こ の手法は，GS 復号法に比べ復号誤り確率の劣化はまっ たくなく，最尤復号を達成する。もちろん本論文の手法 に対しテストパターンを制限することにより，準最尤復 号を行うことも容易である。また，今回は GS 復号法に 対し計算量の低減を試みたが，本手法は他の復号法にも 併用して用いることも可能である。そのときも本論文で 示した有効性が期待できる。 今後の課題として，本手法により適応するテストパ ターンの生成順序を考える必要がある。さらに 4 節で述 べたテストパターン以外の場合についても，効率良く複 数符号語の信頼度損失を導出することは可能である。そ れらを統一的に表現し，さらに効率良く信頼度損失を求 める手法の開発も今後行う予定である。また計算量の定 量的な減少分の理論的保証なども今後の課題である。 参 考 文 献
1) M. P. C. Fossorier and S. Lin, “Soft-decision decoding of linear block codes based on ordered statistics,” IEEE Trans. Inform. Theory, Vol. IT-41, pp. 1379–1396, Sept. 1995.
2) M. P. C. Fossorier and S. Lin, “Computationally efficient soft-decision decoding of linear block codes based on or-dered statistics,” IEEE Trans. Inform. Theory, Vol. IT-42, pp. 738–750, May 1996.
3) D. Gazelle and J. Snyders, “Reliability-based code-search algorithm for maximum-likelihood decoding of block codes,” IEEE Trans. Inform. Theory, Vol. IT-43, pp. 239– 249, Jan. 1997.
4) Y. S. Han, C. R. P. Hartman and C.-C. Chen, “Efficient pri-ority-first search maximum-likelihood soft-decision de-coding of linear block codes,” IEEE Trans. Inform. The-ory, Vol. IT-39, pp. 1514–1523, Sept. 1993.
5) Y. S. Han, “A new treatment of priority-first search maxi-mum-likelihood soft-decision decoding of linear block codes,” IEEE Trans. Inform. Theory, Vol. IT-44, pp. 3091–3096, Nov. 1998.
6) C.-C. Shih, C. R. Wulff, C. R. P. Hartman and C. K. Mohan, “Efficient heuristic search algorithms for soft-decision decoding of linear block codes,” IEEE Trans. Inform. Theory, Vol. IT-44, pp. 3023–3038, Nov. 1998.
7) 小林 学，松嶋敏泰，平澤茂一，“信頼度情報に基 づく置換生成行列を用いた最尤復号法の効率化につ いて,”第 22 回情報理論とその応用シンポジウム予 稿集，pp. 323–326, Dec. 1999. 8) 岡田知嗣，小林 学，平澤茂一，“置換生成行列を 表 1 (127, 64, 21) BCH符号に対する各復号法の符号 化回数及び信頼度損失導出のための加減算回数 提案 1 提案 2 Eb/No [dB] 符号化 加減算 符号化 加減算 3.00 2.51 · 105 1.63 · 107 9.92 · 104 7.88 · 106 3.50 2.63 · 104 1.71 · 106 9.97 · 103 7.98 · 105 4.00 3.19 · 103 2.08 · 105 1.16 · 103 9.39 · 104 4.50 4.79 · 102 3.12 · 104 1.66 · 102 1.37 · 104 5.00 9.00 · 101 5.92 · 103 3.03 · 101 2.55 · 103 表 2 (255,131,37) BCH 符号に対する各復号法の符号 化回数及び信頼度損失導出のための加減算回数 提案 1 提案 2 Eb/No [dB] 符号化 加減算 符号化 加減算 5.00 4.43 · 104 5.58 · 106 1.43 · 104 2.06 · 106 5.50 2.91 · 103 3.67 · 105 9.05 · 102 1.31 · 105 6.00 2.51 · 102 3.18 · 104 7.54 · 101 1.11 · 104 6.50 3.21 · 101 4.18 · 103 1.00 · 101 1.57 · 103 7.00 6.41 9.32 · 102 2.48 4.68 · 102 *7bit 演算の回数もこれにほぼ比例する。 *8 符号化回数に関しては従来の GS 復号法と提案復号 法 1 は同一である。
用いた線形ブロック符号に対する最尤復号法，”第 23回情報理論とその応用シンポジウム予稿集，pp. 13–16, Oct. 2000. 9) 八木秀樹，岡田知嗣，小林 学，平澤茂一，“置換 生成行列を用いた尤度計算量を低減する最尤復号 法，”電子情報通信学会研究技術報告，IT2000-42, pp. 9–16, Jan. 2001.
