High Performance Polar Decoders: Algorithm and Hardware Implementation

纠错码针对可能的错误提供数据可靠性，因此对于所有数字存储和通信系统都是必不可少的。极性码是纠错码理论的最新突破，是第一种在信道容量意义上渐近最优的实用纠错码。它们的渐近最优性能和低误码率使它们成为未来存储和通信系统的候选方案。然而，现有的极解码器存在有限长度误码性能差、译码延迟长、硬件实现效率低等问题。这些问题构成了在实践中采用极地码的重要障碍。结合这些相互影响的挑战，本研究从错误性能、复杂度、延迟和硬件实现的角度对极解码器进行了全面的研究，该研究基于一个综合框架，该框架利用了算法、其复杂性和延迟以及它们的硬件实现之间的复杂关系。该研究的目的是设计新的极解码器，其不仅具有优异的差错性能，而且具有更低的延迟、低复杂度和高效的硬件实现。为此，本文的研究目标包括：1)改进了极坐标译码算法的性能，降低了译码的复杂度和时延；2)极坐标译码的高效结构和硬件实现；3)对所提出的极坐标译码器进行了分析、数值和实验性能评估，包括一个现场可编程门阵列仿真平台。该研究解决了符号判决极坐标译码的误码性能分析、极坐标译码的置信度传播译码调度优化、过完备因子图上极坐标译码的置信度传播译码等几个关键的公开研究问题。该研究还将对符号判决极解码器的误码性能进行分析，从而为其未来的应用提供理论基础。所提出的现场可编程门阵列仿真平台不仅提供了对所提出的极解码器的快速性能评估，而且便于为各种折衷参数选择合适的值，所提出的研究具有理论和实践上的变革性。提出的极坐标译码算法和误码性能分析丰富了纠错码的理论。所提出的极性码译码器将会带来更好的误码性能，并且减少了译码时延和高效的硬件实现。这些因素使各种存储和通信系统(如数字电视、以太网、家庭网络和Wi-Fi)能够采用极性码。所提出的研究的集成设计方法、技术和结果可以外推到其他先进算法的实现，从而影响到广泛的通信和信号处理系统。综合教育计划加强和多样化了科学和工程劳动力，还弥合了先进的信号处理算法及其有效实施之间的差距，从而有助于保持国家的技术优势。

Error correction codes provide data reliability against possible errors, and hence are essential to all digital storage and communication systems. Polar codes, a recent breakthrough in the theory of error correction codes, are the first practical error correction codes that are asymptotically optimal in the sense of channel capacity. Their asymptotically optimal performance and low error floor make them promising candidates for future storage and communication systems. However, existing polar decoders suffer from inferior finite length error performance, long decoding delay, and inefficient hardware implementations. These issues form important obstacles to the adoption of polar codes in practice. Jointly addressing these interplaying challenges, the proposed research is a comprehensive investigation of polar decoders from the perspectives of error performance, complexity, delay, and hardware implementation, based on an integrated framework that harnesses the intricate relation between algorithms, their complexities and delays, and their hardware implementations.The proposed research aims to devise new polar decoders that not only achieve superior error performance but also have reduced delay, low complexities, and efficient hardware implementations. To this end, the objectives of the proposed research include: 1) New decoding algorithms for polar codes with improved performance and reduced complexity and delay; 2) Efficient architectures and hardware implementations of polar decoders; 3) Analytical, numerical and experimental performance evaluation of the proposed polar decoders, including a field-programmable gate array emulation platform. The proposed research tackles several key open research problems, such as error performance analysis of symbol-decision polar decoders, how to optimize the schedule of belief propagation decoding of polar codes, and belief propagation decoding of polar codes on over-complete factor graphs. The proposed research also will analytically characterize the error performance of symbol-decision polar decoders, thereby providing theoretical foundations for their future applications. The proposed field-programmable gate array emulation platform not only provides fast performance evaluation of proposed polar decoders, but also facilitates the selection of the appropriate values for various tradeoff parameters.The proposed research is transformative in both theory and practice. The proposed polar decoding algorithms as well as error performance analysis enrich the theory of error correction codes. The proposed decoders for polar codes will lead to better error performance, and have reduced decoding delay and efficient hardware implementations. These factors enable the adoption of polar codes to a wide variety of storage and communication systems, such as digital television, Ethernet, home networking, and Wi-Fi. The integrated design methodology, techniques, and results of the proposed research can be extrapolated to the implementation of other advanced algorithms, and hence impact a wide range of communication and signal processing systems. The integrated education program strengthens and diversifies the science and engineering workforce, and also bridges the gap between advanced signal processing algorithms and their efficient implementations, thus helping to maintain the nation's technological advantage.