Near-Maximum-Likelihood Decoding Techniques with Reduced Complexity

新的编码应用往往受到最佳可能的最大似然（ML）解码所需的巨大解码复杂度的限制。最近设计的次优算法将ML解码的复杂度指数降低了沿着，同时在解码错误概率上增加了任意小的增加。该项目解决了设计更先进算法的问题，这些算法可以进一步降低ML解码的复杂度指数5到7倍。 我们将研究以下主题。 次优算法的一般性研究。目标是：（a）获得近ML解码的复杂度和性能之间的显式折衷，（B）将近ML解码推广到实际上重要的信道，（c）将新的近ML解码技术与传统的网格解码联合收割机组合。 设计用于近ML解码的新算法。目标是：（a）开发新的预分类过程，其将ML解码的复杂性指数降低到三倍，（B）设计新的随机搜索算法，其将ML解码的复杂性指数降低到五倍。 级联NML解码算法的设计。目标是：（a）发展级联码的级联近ML译码，并将ML译码的复杂度指数降低到原来的七倍。（B）将级联设计应用于突发和衰落信道。 所设计算法的实时软件实现。我们的目标是开发快速的软件算法的长度为50至100的信道上使用的信号噪声比约为1分贝的代码。

New coding applications are often limited by the huge decoding complexity required by the best possible maximum-likelihood (ML) decoding. Recently designed sub-optimal algorithms reduce the complexity exponent of ML decoding two times along with an arbitrarily small increase in decoding error probability. The project addresses the problem of designing more advanced algorithms that can further reduce the complexity exponent of ML decoding five to seven times. We are going to investigate the following topics. General study of sub-optimal algorithms. The goals are: (a) to obtain the explicit trade-offs between complexity and performance of near-ML decoding, (b) to generalize near-ML decoding for practically important channels, (c) to combine new near-ML decoding techniques with conventional trellis decoding. Design of new algorithms for near-ML decoding. The goals are: (a) to develop new presorting procedures which reduce the complexity exponent of ML decoding up to three times, (b) to design new random-search algorithms which reduce the latter exponent up to five times. Design of cascaded NML decoding algorithms. The goals are: (a) to develop cascaded near-ML decoding for concatenated codes, and to reduce the complexity exponent of ML decoding up to seven times, (b) to apply cascaded design for bursty and fading channels. Real-time software implementation of designed algorithms. The goal is to develop fast software algorithms for codes of lengths 50 to 100 used over the channels with a signal-to-noise ratio of about 1 dB.