低密度パリティ検査符号復号問題を制約なし二次形式二値変数最適化問題に変換した解法

IPSJ

Description

制約なし二次形式二値変数最適化 (quadratic unconstrained binary optimization; QUBO) 問題を解くハードウェアアクセラレータの開発が進められている．QUBO問題の計算複雑度は一般にNP困難であり，古典的コンピュータで効率的に解く手法は発見されていない．古典的コンピュータと異なる原理で動作するイジングマシンによりQUBO問題を解くことが期待されている．特に実用的な問題の多くはNP困難な組合せ最適化問題であり，QUBO問題を介してイジングマシンで解く研究がされている．ここで低密度パリティ検査(low density parity check; LDPC)符号復号問題に注目する．LDPC符号は通信路の誤り訂正を可能とする符号であり，復号処理を組合せ最適化問題としてとらえて解法するアプローチが研究されているがQUBO問題へ厳密に変換して解く手法は存在しない．本稿ではLDPC符号復号を組合せ最適化問題として定義し，QUBO問題へ変換する手法を提案する．提案手法により変換されたQUBO問題をイジングマシンを用いて求解し，元のLDPC符号復号問題の解が得られることを示す．

Journal

Keywords

Details 詳細情報について

Report a problem

Back to top