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

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

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.