LDPC符号におけるSum−Product復号法の演算量削減法

青山 瑠美 (0651001)


Sum−Product復号法に代表される反復復号は,低密度パリティ検査符号(LDPC符号)の誤り訂正において重要な役割を果たす. 十分に長い符号長を持つ LDPC 符号は,Sum−Product 復号法を適用することにより,シャノン限界に迫る復号性能を発揮する. Sum−Product復号法は,検査行列を隣接上列とする2部グラフ(タナーグラフ)上での確率伝播アルゴリズムとして解釈できる. タナーグラフは,2個のノード集合を持ち,一方は変数ノードと呼ばれるノード集合,他方はチェックノードと呼ばれるノード集合である. 各変数ノードと符号語を構成するシンボル(送信記号)との間には一対一の対応関係があり,チェックノードとパリティ検査方程式の値(シンドローム)との間には一対一の関係がある. Sum−Product復号法では,タナーグラフ上において,変数ノードとチェックノードの間でメッセージ(確率値)の更新・交換を繰り返すことにより,受信信号系列に対する送信記号の事後確率分布を計算し,送信記号の推定を行う.

本研究では,Sum−Product復号の繰り返し過程中に,タナーグラフ上のいくつかの変数ノードを「非活性化」することでSum−Product復号法を効率化する方式を提案する. 非活性化された変数ノードでは,その時点の対応する送信記号の一時推定結果に応じてメッセージの値を0または1に固定し,以降の反復ステップではメッセージの更新を停止する. したがって,非活性化された変数ノードでのメッセージの計算を省略できるため,復号の計算量を削減可能となる. 本方式では,誤った一時推定記号に対応する変数ノードを非活性化してしまうと,当該送信記号について誤った復号を与えるため,復号性能を著しく損なうこととなる.

本方式において復号性能を確保するためには,正解の一時推定記号に対応する変数ノードだけを適切に選定することが重要となる. そこで,本研究では,一時推定記号が正解であるための基準について検討を行い,同基準に基づいて非活性化する変数ノードを選定することを考える. この選定基準の与え方には大きな自由度があるが,本研究では,2つの異なるアプローチを検討する.

第1のアプローチでは,反復復号過程で得られる一時推定記号系列のシンドロームの要素に着目する. LDPC符号は線形符号であるため,一時推定記号系列が符号語であるための必要十分条件は,その一時推定記号系列に対して計算されたシンドロームが零となることである. 逆に,シンドローム内に非零要素が存在すれば,一時推定記号系列に誤りが発生していることがわかる. このことから,シンドロームの状態に注目することにより,一時推定記号の正しさについてある種の尺度を定義できる. 以上の考え方を発展させた非活性化する変数ノードの選定基準を用いる提案復号法では,復号性能の劣化を抑えつつ復号の演算量を削減可能である.

第2のアプローチでは,Forced Convergence復号法(FC法)と呼ばれる類似手法と第1のアプローチを組合わせた選定基準を検討する. FC法も,正解とみられる一時推定記号に対応する変数ノードを選定し,これを非活性化するSum−Product復号法の簡略化法であるが,復号性能の劣化が著しいことが実験的に確認されている. 本研究では,FC法の非活性化する変数ノードの選定基準に第1のアプローチのアイデアを組み合わせることで,変数ノードの非活性化による復号の演算量削減を達成しつつ,Sum−Product復号法を上回る復号性能を実現可能であることを示す. なお本発表では,時間の都合上,第2のアプローチの一部結果を中心に紹介する予定である.