CIF: Small: Low Complexity Maximum-Likelihood Decoding Through Serial List Decoding

错误控制代码无处不在，保护数据和控制消息的可靠性，因为它们被传送到移动电话或当数据被存储在存储设备中。解码错误控制代码所需的计算通常比编码所需的计算复杂得多。解码器应该从所有有效码字中识别出最可能的那个，即最接近接收信号的那个——这被称为“最大似然解码”。在实践中，一些提供出色可靠性的错误控制码没有被使用，因为它们的解码器的复杂性在时间、成本或能量上令人望而却步。其他代码用次优解码器解码以管理复杂性。这个项目极大地降低了最大似然解码的平均复杂性，适用于广泛的常用代码。该项目增加了通过实践本科研究经验继续研究生院的工程本科生的数量，特别注意扩大妇女在工程研究和研究生教育中的参与。这个项目的目标代码描述的生成器多项式，包括循环码和卷积码。该方法将循环码的生成多项式分解为卷积码部分和循环冗余校验（CRC）部分。串行列表解码应用于描述卷积码部分的相对简单的网格，当找到一个同样通过CRC检查的卷积码字时终止。这种方法可以应用于任何复合循环码，包括流行的Bose-Chaudhuri-Hocquenghem （BCH）码，如Reed-Solomon码和二进制BCH码。初步的示例表明，最大似然解码的复杂度是解码描述分组代码的最小网格所需复杂度的平方根或立方根。这种新方法产生了新的组合码，其特征是网格码或卷积码与crc相结合，旨在最大限度地提高串行列表解码下组合码的可靠性。该项目分析了所提出的解码方法的复杂性，并创建了新的循环码和新的复合卷积码和网格码的最佳分解，这些编码提供了出色的可靠性和实用的解码器复杂性。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Error control codes are ubiquitous, protecting the reliability of data and control messages as they are communicated to a mobile phone or while data is being stored in a memory device. The computation required to decode an error control code typically requires far more complexity than is required for encoding. The decoder should identify, from among all valid codewords, the one that is most likely, i.e., the one that is closest to the received signal -- this is called 'maximum likelihood decoding'. In practice, some error control codes that provide excellent reliability are not used because the complexity of their decoder is prohibitive in time, cost or energy. Other codes are decoded with sub-optimal decoders to manage complexity. This project dramatically lowers the average complexity of maximum-likelihood decoding for a wide range of commonly used codes. The project increases the number of undergraduates in engineering who continue to graduate school through hands-on undergraduate research experiences, with particular attention to broadening the participation of women in engineering research and graduate education.This project targets codes described by generator polynomials, including cyclic codes and convolutional codes. The new approach decomposes the generator polynomial of a cyclic code into a convolutional code part and a cyclic redundancy check (CRC) part. Serial list decoding is applied to the relatively simple trellis describing the convolutional code part, terminating when a convolutional codeword is found that also passes the CRC check. This approach can be applied to any composite cyclic code, including popular Bose-Chaudhuri-Hocquenghem (BCH) codes such as Reed-Solomon and binary BCH codes. Preliminary examples show that maximum-likelihood decoding can be achieved with complexity that is the square root or cube root of the complexity required to decode the minimal trellis describing the block code. The new approach leads to new composite codes featuring trellis codes or convolutional codes combined with CRCs that are designed to maximize the reliability of the composite code under serial list decoding. This project analyzes the complexity of the proposed decoding approach and creates new optimal decompositions of cyclic codes and new composite convolutional and trellis codes that provide excellent reliability with practical decoder complexity.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.