Recursive Decoding for Reed-Muller Codes and their Modifications

Reed-Muller码及其改进码的递归译码在现代通信系统中，强大的纠错能力有着巨大的需求。然而，最好的代码的实际性能往往是有限的，由于不可行的解码复杂性或过长的块使用。特别是，最佳最大似然解码具有巨大的复杂性，即使在短块的100位。相比之下，迭代解码使用包括数万比特的长块来组合低复杂度和上级性能。因此，本研究的重点是码的构造和译码算法，可以实现良好的性能和低译码复杂度，而使用的块长度适中。研究的特定目标是采用范围从100比特到1000比特的块，其中最大似然解码和迭代过程都不能以低复杂度实现良好的性能。由于短的长度和快速解码，新的代码可以用于各种高速应用中出现的宽带和无线系统。为了实现这一目标，研究人员采用了快速递归技术，将长度为n的原始代码分成两个长度为n/2的代码。这些技术被应用到Reed-Muller（RM）码，其子码，和新的代码修改。基本过程将RM码（r，m）分成两个组成RM码（m - 1，r - 1）和（m - 1，r）。然后，解码被进一步降级到较短的代码。在所有中间步骤中，解码器仅重新计算新定义的符号的可靠性。最后，对一阶基本RM码进行快速最优译码。对于较长的代码，这种重复的多级递归越来越优于其他低复杂度的算法，如有界距离解码和多数解码。 通过使用在递归的中间步骤中采取的非常短的候选者列表，该过程被进一步增强。 另一种增强使用RM码的子码，对于该子码，跟踪几个可能的候选者已经给出了接近最大似然解码。特别地，即使长度为128的短RM码也能在2.5dB的信噪比（SNR）下实现低输出误比特率（BER）。进一步的研究课题包括：递归解码算法的一般研究。目标是：（a）估计多级递归每一步的输出误码率;（B）选择RM码的最佳保护子码;（c）估计递归列表译码的输出误码率;（d）设计新的选择候选短列表的准则。设计新的递归算法。目标是设计更高级的构造，其：（a）将原始块分割成具有不同保护级别的多个子块;（B）使用具有不同于RM码的新组成码的递归;（c）在递归解码中结合置换技术;（d）在1至2 dB的SNR下实现对高达1024比特的块的有效解码。

Recursive decoding for Reed-Muller codes and their modifications Powerful error correction is in great demand in modern communication systems. However, practical performance of the best codes is often limited due to infeasible decoding complexity or excessive length of the blocks to be used. In particular, optimum maximum likelihood decoding has huge complexity even on short blocks of one hundred bits. By contrast, iterative decoding combines low complexity and superior performance using long blocks that include tens of thousands bits. Therefore this research focuses on code constructions and decoding algorithms that can achieve good performance and low decoding complexity while using the blocks of moderate length. The particular goal of the research is to employ the blocks ranging from 100 bits to 1000 bits, where neither maximum likelihood decoding nor iterative procedures achieve good performance at a low complexity. Due to short lengths and fast decoding, the new codes can be used in a variety of high-speed applications arising in broadband and wireless systems. To achieve this goal, the researchers employ fast recursive techniques that split original codes of length n into two codes of length n/2. These techniques are applied to Reed-Muller (RM) codes, their subcodes, and new code modifications. The basic procedure splits the RM code (r, m) into the two constituent RM codes (m - 1, r - 1) and (m - 1, r). Decoding is then relegated further to the shorter codes. In all intermediate steps, the decoder only recalculates the reliabilities of the newly defined symbols. Finally, fast optimum decoding is performed on the basic RM codes of the first order. For longer codes, this repetitive multilevel recursion increasingly outperforms other low-complexity algorithms, such as bounded distance decoding and majority decoding. The procedures are further enhanced by using very short lists of candidates taken in the intermediate steps of the recursion. Another enhancement uses subcodes of RM codes, for which tracking a few plausible candidates already gives near-maximum likelihood decoding. In particular, even short RM codes of length 128 achieve low output bit error rates (BER) at a signal-to-noise ratio (SNR) of 2.5 dB. Further research topics include: General study of recursive decoding algorithms. The goals are: (a) to estimate the output BER in each step of multilevel recursions; (b) to choose the most protected subcodes of RM codes; (c) to evaluate the output BER in recursive list decoding; (d) to design new criteria for choosing short lists of candidates. Design of new recursive algorithms. The goal is to design more advanced constructions that: a) split the original block into multiple subblocks with different levels of protection; (b) use the recursions with new constituent codes different from RM codes; (c) incorporate permutation techniques in recursive decoding; (d) achieve efficient decoding for blocks up to 1024 bits used at SNR of 1 to 2 dB.