Development of Universal Decoding Algorithms for BCH codes and LDPC codes

对于给定的一类线性码，如BCH码或LDPC（低密度奇偶校验）码，我们开发了不依赖于离散无记忆信道的统计特性的通用解码器，并获得了以下结果。我们研究了众所周知的通用解码器——最小熵解码器的性能。对于一类m元加性信道，我们给出了最小熵译码器译码错误概率的上界。得到的界取决于给定码的权谱以及信道的转移概率。进一步阐明了当码块长度趋于无穷大时，得到的误差指数与随机编码指数重合的条件。为了降低通用解码器的复杂度，我们提出了一种新的通用多级解码器方案。通过将该解码器与传统的多电平编码方案相结合，可以实现信道容量的最大化。此外，我们还推导出了当采用所提出的多级解码器时，一类m级加性信道的译码错误概率的上界。我们已经证明，最小熵译码器和通用多级译码器都可以利用编码的网格结构有效地实现。我们还通过计算机仿真阐明了所提出的通用解码器的性能。

For a given class of linear codes such that BCH codes or LDPC(Low Density Parity Check) codes, we develop universal decoders which do not depend on the statistical characteristics of the discrete memoryless channel, and obtained following results.1.We investigate the performance of the well-known universal decoder called the minimum entropy decoder. For a class of M-ary additive channels, we have derived an upper bound on the probability of decoding error when the minimum entropy decoder is employed. The obtained bound depends on the weight spectrum of the given code as well as the transition probability of the channel. Further, we have clarified a condition such that the obtained error exponent coincides with the random coding exponent as the block length of the code tends to infinity.2.In order to reduce the complexity of the universal decoder, we have proposed a new scheme called universal multistage decoder. By combining this decoder with the conventional multilevel coding scheme, the capacity of the channel can be achieved. Further, we also derive an upper bound on the probability of decoding error for a class of M-ary additive channels, when the proposed multistage decoder is employed.3.We have shown that both the minimum entropy decoder and the universal multistage decoder can be efficiently implemented by using the trellis of the code. We have also clarified the performance of the proposed universal decoder by using computer simulation.