Research On Encoding And Decoding Algorithms For Polar Codes

Channel coding,as an important part of modern communication systems,can significantly improve the capacity and performance of the communication system.Since Shannon proposed the Noisy-Channel Coding Theorem,the researchers have been looking for a coding scheme that can achieve the Shannon limit.Eventually,more than half a century later in2009,Polar Codes,proposed by Arikan,become the first practical coding scheme that theoretically achieves the Shannon limit.The key point of the polar codes is the idea of channel polarization:(1)a group of independent and identical channels are repeatedly manipulated by the process of channel combining and channel splitting.(2)the capacity of part of them tends to be 1,that of the others tends to be 0.(3)only the channels with high reliability are used to transmit the information bits.The successive cancellation decoding is an algorithm proved to be able to achieve the Shannon limit in the case of infinite code length,while the performance of polar codes under finite code length is not satisfactory.Hence,by improving the successive cancellation algorithm which in fact is a greedy depth first search method,the list decoding becomes an excellent decoding algorithm.While the sorting module,the most time-consuming part,becomes the bottleneck of the practical application of the list decoding algorithm.In this paper,the study mainly focuses on the following four aspects:1.The polarization theory.Firstly,the channel combining,the channel splitting and the calculation of channel reliability are introduced.Then,the encoding and time complexity of polar codes are given by the detailed theoretical derivation.The serial cancellation algorithm is introduced based on log likelihood ratio.Finally,the time complexity and spatial complexity of decoding algorithm are analyzed.2.The high-performance decoding algorithm of polar codes.Firstly,the list decoding algorithm is introduced by extending the greedy depth search of the successive cancellation algorithm to the finite width first search.Then several simplified algorithm including simplified successive cancellation decoding(SSC),maximum-likelihood SSC(ML-SSC),Fast-SSC are introduced.Finally,the Fast-List decoding is introduced by combining the list decoding and simplification schemes.Theoretical analysis and simulation results show that the list decoding can achieve the performance of the maximum likelihood decoding,and that the Fast-List algorithm has great advantage on both decoding speed and performance.3.The art-of-the-state of sorters of the list decoder.First,the dependency of path metrics is clarified to provide the theoretical basis of sorter optimization.Then,we introduce the bitonic sorter,the bubble sorter and their simplification,followed by the odd-even sorter which divides the odd and even indices of the metrics.Finally,the quantitative analysis of each sorter is carried out by comparing the number of compare-and-select units and the number of sorting stages.4.The radix selector.Firstly,the blind area in the sorter design is pointed out by summarizing the characteristics of the existing sorter.Then,a radix selector based on the finite state machine is proposed by exploiting the radix sorting algorithm.The proposed method has linear time complexity and can be easily parallelized.The selector maintains four sets of metrics: the processed/unprocessed metrics,the marked/unmarked metrics.For the commonly used fixed-point number representation of path metrics in the hardware implementation,the selector dynamically changes the four collections by comparing the bits from the most significant to the least significant bit.This process ends until the best L metrics is selected.In this scheme,the process of adjusting the elements within the set is designed as parallel bit vector operation by using two fixed-length bit vectors marking elements in different sets.The simulation results and theoretical analysis show that the proposed scheme can greatly reduce the delay and resource consumption compared to the existing sequencer,especially for large list decoding of short polar codes.