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

概要

論文の詳細を見る
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.
2009-10-30