Study On Construction And Decoding Algorithms For Polar Codes

Polar codes, which is proposed based on the phenomenon of channel polarization, is the first class of provable capacity-achieving codes for binary symmetric channels when the code length goes to infinity. The channel polarization theorem states that the polarized channels converge to one of the two kinds when the code length is infinity. One is the noiseless channel whose capacity is 1 while the other is the pure noise channel whose capacity is 0. And the fraction of the noiseless channel equal to the capacity of the original channel. However, when the code length is finite, sub-channels cannot be polarized efficiently. Thus, there exist sub-channels whose capacity lower than 1. If a bit is transmitted over such a channel, decoding error may occur. Hence, the performance of finite length polar codes is not satisfied compared with well-designed LDPC codes and Turbo codes. Besides, polar codes are channel related, and the construction of polar codes for channels other than binary erasure channel is complex. To solve these problems, the works of this dissertation focus on the construction and decoding of finite length polar codes, including construction and decoding for binary polar codes and the rate assignment and decoding for non-binary polar codes. The study mainly focuses on the following four parts.Based on the Gaussian approximation theorem of LDPC codes, a construction method for polar codes over additive white Gaussian channel is proposed. The Gaussian approximation method is used to estimate the error probability of each sub-channel under successive cancellation decoding to obtain the block error rate of a polar code. To minimize the block error rate, the construction method is proposed. The complexity analysis shows that the Gaussian approximation method has a complexity lower than the methods available in other references. The simulation results show that the estimated block error rate is identical with the simulation results.The ordered statistic decoding (OSD) which is a simplified version of maximum likelihood decoding is conidered to decoding short polar codes. Since the conventional ordered statistic decoding has to test a number of codewords to achieve a better performance, the complexiy is high. To solve this problem, a threshold based decoding which never flip the most important bits with high confidence is proposed. By doing so, the deminsion of the tested codewords is reduced, and the complexity is also reduced. By analysing the compelxity and the performance, the expected number of tested codewords and block error rate performance in high signal-to-noise ratio can be estimated. The simulation results show that the performance of threshold based ordered statistic decoding is almost the same as that of list decoding for short polar codes. For codes with moderate or long code length, a higher order ordered statistic decoder is needed to achieve better performance. As to the CRC-aided ordered statistic decoding, the performace of CRC-aided OSD outperforms CRC-aided list decoding when the code rate is high. For codes with low rate, the result inverses.A segment CRC scheme is proposed to improve the performance of CRC-aided list decoding. The segment CRC scheme divides the information sequence into multiple sub-sequences firstly. And each sub-sequence is checked by a CRC code. By doing so, the decoder can remove the paths which cannot pass the CRC from the list timely to make the branches of the paths which can pass the CRC preserved as more as possible. Thus, the performance can be improved. The analysis and simulation results show that the proposed segment CRC scheme can improve the block error rate performance, as well as reduce the complexity with the cost of a slighting higher undetected probability.A rate assignment algorithm is proposed for multi-level polarized non-binary polar codes. To minimize the block error rate of the rate assigned non-binary polar codes, the expression of block error rate of a multi-level polar code is provided firstly. And then, instead of exhaustive searching algorithm whose complexity grows exponently with code length, an element-wise exchange (EWEX) algorithm whose complexity grows linearly with the code length is used to search the rate assignment scheme. Although the EWEX method cannot be proved to be able to find the global optimal solution, the simulation results show that the results that the EWEX provides is the same as that of the exhaustive searching method. Besides, the decoding of multi-level polarized channel is also studied. And the successive cancellation decoding for binary polar codes is generalized to non-binary polar codes.