線形ブロック符号の最尤復号特性の評価法について

Tan Soon Keong (9951133)


与えられた誤り訂正符号が, 与えられた通信環境においてどの程度の誤り訂正 能力を発揮するかを評価することは, 信頼性の高い通信系を実現するうえで不可 欠なことである. 誤り訂正能力の指標としては, その環境において最尤復号を 行ったときの復号誤り率がしばしば用いられるが, 規模の大きなブロック符号 に対して実際に最尤復号を行うことは, 計算量的に困難である. 筆者の属する 研究グループでは, 従来法よりも効率的な最尤復号アルゴリズムとして, 適応 型最尤復号アルゴリズムを提案しているが, それでも最尤復号が可能な符号の 規模には限りがある. そこで本論文では, 符号の持つ線形性に着目して符号を コセット (剰余類) 分割し, 各コセットに対する最尤復号手続きを組み合わせ て, 最尤復号時の誤り制御特性を評価するような手法を検討する. 提案手法 では, 同値類分割の手法や分割数などにより, 特性評価に要する時間が変化す る. 本研究では, 符号の線形構造に基づいて効果的な分割方法を提案し, 計算 機模擬によって最適な分割数を決定する. テストケースとして長さ 128 リード ・マラー符号を対象とし, 提案法を用いて特性評価を行う.

キーワード:誤り訂正符号, 最尤復号法, 適応型復号アルゴリズム, コセット展 開, 線形ブロック符号


An Evaluation Method of the Error Probability of the Maximum Likelihood Decoder of Linear Block Codes


Evaluation of the error performance of an error correcting code is significant for realizing a reliable communication system. However, computing the error probability of a maximum-likelihood decoder (MLD) is especially a difficult task for long practical codes. Though an efficient algorithm for the MLD, named an adaptive MLD algorithm, has been proposed by the author's research group, the algorithm cannot be applied for very large block codes. This thesis proposes a new method of evaluating the error performance of linear block codes. In the proposed method, a code $C$ to be evaluated is divided into cosets of a subcode of $C$, and MLD algorithms for the cosets constitute the whole evaluation system. The total evaluation time depends on how many and in what way the cosets are chosen. A method for heuristically constructing good cosets are presented in the thesis. The optimum number of cosets is also investigated by computer simulation. The error performance of the Reed-Muller codes with length 128 are evaluated as a case study.

keywords: error correcting code, the maximum likelihood decoding, adaptive decoding algorithm, coset expansion, linear block code


E-mail: keong-ta@is.aist-nara.ac.jp