权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

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

CIF：小：通过串行列表解码进行低复杂度最大似然解码

基本信息

批准号：
2008918
负责人：
Richard Wesel
金额：
$ 51.18万
依托单位：
University of California-Los Angeles
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2020
资助国家：
美国
起止时间：
2020-07-01 至 2024-12-31
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=2008918&HistoricalAwards=false
关键词：
CIF Small Low Complexity Maximum

项目摘要

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.

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