遺伝的アルゴリズムによる正則低密度パリティ検査符号の構成法に関する研究

摘要

本研究では，新規に遺伝的アルゴリズムを用いた低密度パリティ検査（LDPC）符号の構成法を提案し，評価を行った．捷案方式では，LDPC 符号の検査行列の構成において，遺伝子演算の手法を取り入れて，行列の正則性を保ちながら誤り率特性劣化の要因となる最短長ループ（サイクル4）除去を可能とした．%Genetic algorithms are stochastic search algorithms based on the mechanism of natural selection or genetics. These algorithms are effective meta- heuristic optimization algorithms when problems belong to hard optimization, included in the NP-complete or NP-hard problems. A parity check matrix may be generated simply by running a binary random generator. This is very similar to the code construction used by Shannon in his proof of the Channel Coding Theorem, but with the constraint of matrix sparseness added in order to be able to find viable decoding algorithms. If the selected matrix does not provide an optimum code, the random generator is simply run once more. Theoretically, the probability of finding an optimum code by such a random construction is very close to 1 if the code length is large enough. Given this constraint condition, the random generator method isn't always effective and there exists a case in which the total computational complexity to search optimum codes becomes to solve a kind of NP-complete problem under the conditions of sparse matrices. This report shows a new genetic algorithm to get optimum parity check matrices which satisfy the given conditions for the low-density parity-check codes.