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

点击翻译按钮获取中文摘要

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.