最適化手法に基づく誤り訂正符号の復号アルゴリズムについて

摘要

近年，線形計画法などの連続最適化に基づく誤り訂正符号の復号法が登場し，符号理論研究者の注目を集めている.本稿では，著者の提案する内点法に基づくLDPC符号(Low-Density Parity-Check符号)の復号法の概要とその特徴を紹介する.この復号法(内点復号法)は，LDPC符号の復号問題を凸計画問題として定式化し，バア関数に基づく主パス追跡内点法により近似的にその凸計画問題を高速に解く，という考え方に基づいて構成されている.本復号アルゴリズムは，線形ベクトル通信路の範疇に入る定常無記憶通信路，シンボル間干涉通信路，MIMO通信路，マルチプルアクセス通信路など様々な通信路に適用が可能であり，幅広い応用が期待されている.%This paper reviews a decoding algorithm for low-density parity-check (LDPC) codes based on convex optimization according to the reference Wadayama (2010). The decoding algorithm, called interior point decoding, is designed for linear vector channels. The linear vector channels include many practically important channels such as inter-symbol interference channels and partial response channels. It is shown that the maximum likelihood decoding (MLD) rule for a linear vector channel can be relaxed to a convex optimization problem called a relaxed MLD problem. The decoding algorithm is based on the primal path-following interior point method with a barrier function. Approximate variations of the gradient descent and the Newton methods are used to solve the convex optimization problem.