Document

分枝カット法に基づいた
線形符号の復号法に関
する一考察
堀井俊佑
松嶋敏泰
平澤茂一
早稲田大学
研究背景

対象とする問題
無記憶通信路に対する2元線形符号の最尤復号



LDPC符号・ターボ符号に対しては，確率伝搬法が幅広く用いられている
近年，線形計画法に基づいた復号法に関する研究が盛ん（LP復号法）
LP復号法の性能
整数解が得られれば最尤であることが保証される
 計算量は一般的に，確率伝搬法より多い
 復号誤り率も，確率伝搬法より劣ることが多い
⇒復号アルゴリズムを改良する研究が多く存在

関連研究と本研究の目的
分枝限定法に基づく復号
[Yang et al.]
Adaptive LP (ALP) 復号
[Taghavi et al.]
LPの計算量削減
分枝限定法を利用
逐次的に不等式を問題に組み込む
逐次的に等式制約を問題に組み込む
不等式の候補を増やすことで，
最尤復号が保証される
復号誤り率が改善
組合せ
本研究
分枝カット法に基づく復号という形で一般化
分枝限定法とALPの組合せ．
逐次，等式制約・不等式制約を問題に組み込む．
最尤復号が保証される．
[Draper et al.] によって提案されている復号法も分枝カット法の1つと見る
ことができる
線形符号の最尤復号問題
（通信路は無記憶を仮定．AWGN等）
最尤復号問題
(1)
最適化問題の形に変換
(2)
従来研究：LP復号法

LP 復号法
(6)




得られた解が整数解ならば，その解は最尤解である．
従来研究：Adaptive LP 復号法

必要な不等式を逐次問題に組み込んでいく
Adaptive LP (切除平面法)
不等式が見つかる
新たな不等式が無い．
最後に解いた最適化問題の最適解を出力
※途中で見つかった不等式をカット（切除平面）と呼ぶ．
探索する不等式の範囲が(6)式であれば，出力はLP復号法と同じ．
従来研究：Adaptive LP 復号法

不等式の探索範囲を広げることで，



新たなカットが見つかれば，復号誤り率が改善される場合がある．
ただし，計算量も増大する．
符号の場合，パリティ検査式の排他的論理和をとることで，冗長なパ
リティ検査式(RPC)を構成できる．
[Taghavi et al.]によるRPCの探索アルゴリズム
• Step1: ALPの結果得られた解をとする
• Step2:タナーグラフから，整数解のノードを取り除く
• Step3:得られたグラフ上でランダムウォークもしくは探索によりサイクルを見つける
• Step4:サイクルに含まれるパリティ検査式の排他的論理和をとる
• Step5:パリティ検査式がカットを生成すれば終了．そうでなければStep3に戻る．
上記を決められた回数だけ行う．回数が多ければカットが見つかる確率が
大きくなるが，計算量が多くなる．
従来研究：分枝限定法に基づく復号



LP decoder の出力が，非整数ならば，等式制約を加えて解きなおす．
復号の過程は，木で表現できる．
各ノードは，LPとその解，目的関数値を保持．根ノードには(6)のLP．そ
の他のノードは，親ノードのLPに等式制約を1つ加えたLPが対応する．
分枝限定法
Step.1：
Step.2：
Step.3：
Step.4：
従来研究：分枝限定法に基づく復号

復号過程の例:
最尤符号語
分枝限定法の計算戦略

探索の仕方には，幾つかの選択肢がある





深さ優先探索
幅優先探索
評価値優先探索
ヒューリスティック探索
etc
※[Yang et al.]では，深さ優先・幅優先のみ

子問題を生成する際に，どのビットに整数制約を入れるか（分枝変数の
選択）によってもアルゴリズムの性能は大きく変化する．
親ノードのLPの最適解において，値が0.5に最も近いビット
 対数尤度比が最も大きいビット
 ループが多く解消されるビット
 etc.

※[Yang et al.]では，(6)のLPの最適解が，0.5に
近い順．これだと，子ノードのLPが親ノードのLP
と変わらない場合が生じる．
分枝カット法に基づいた復号

分枝限定法にカットの探索を組み込む
Step.1：
Step.2：
Step.3：
Step.4：
分枝カット法の計算戦略


分枝限定法と同様，探索の仕方・子問題の選択に自由度がある．
その他に，「カットの候補となる不等式の集合」の取り方に関する自由度
がある．
不等式の集合を多く取っておけば，1つ1つのLPを解く時間が大きくなるが，
探索ノード数の減少が見込める．
 符号語であることを保証するためには，全ての不等式を満たす整数ベクトル
が符号語であることが条件
 以下のようにすると，[Draper et al.]のアルゴリズムが復元される




探索方法は，幅優先探索
子問題の生成は，「親ノードの最適解が0.5に近いビット」に等式制約を入れる．
不等式の探索範囲は(6)式
実験

探索の仕方の違いによる，探索ノード数の差を見る
分枝限定法・子問題の生成法は[Draper et al.]のもの
(60,30)-正則LDPC符号を使用

評価値優先探索が一番少ない．


実験

評価値優先探索では，リストのソート作業が入るので，ノード数の比較だ
けでは公平でない．計算時間で比較．

グラフの形が，探索ノード数と殆ど変わらない．ソートにかかる時間に比
べて，LPを解く時間の方が支配的．
実験


分枝変数の選択戦略の違いによる差を見る．
分枝カット法．探索方法は評価値優先探索
5000
4500
0.5に最も近いビット
4000
3500
対数尤度比の絶対値
が最大のビット
3000
2500
2000
1500
1000
500
0
3
3.5
4
4.5
5
5.5
6
実験

分枝限定法と分枝カット法の違い
探索方法は評価値優先探索．子問題の生成法は[Draper et al.]のもの．
カットの候補となる不等式集合は元のLP（分枝限定法と同じ探索）

分枝カット法のほうが早い（LPとALPの差が出ているのみ．）

実験


分枝カット法におけるカット探索範囲の違い
探索方法は評価値優先探索．子問題の生成法は[Draper et al.]のもの．
[Taghavi et al.]のRPC探索アルゴリズムを使用．（最大繰り返し回数10回）
1200
40
35
RPC無し
30
根ノードのみRPC
全ノードでRPC
25
RPC無し
1000
根ノードのみRPC
全ノードでRPC
800
20
600
15
400
10
200
5
0
0
4
5
6
4
5
6
まとめと今後の課題




分枝カット法に基づいた復号法というアルゴリズムの枠組みを
提案した．
いくつかの従来の復号法がこの枠組みに含まれることを示し
た．
ノードの選択・分枝変数の選択・不等式の探索範囲などを変更
することで，より良いアルゴリズムが得られることを示した．
符号の構造を活用したより良い計算戦略の提案が今後の課題
である．
付録

(6)式の制約を満たさない⇒符号語にならない
符号語が(6)式を満たさないとする
⇒N(j)において，Sに含まれるビットは1，それ以外のビットは0
⇒対応するベクトルはj行目のパリティ検査式を満たさず，符号語にならない．

符号語でない整数ベクトル⇒(6)式を満たさない
符号語で無ければ，パリティ検査式を満たさない行jが存在する．
⇒以下を満たすVが存在する．

Download Report