On The Investigation And Application Of Decoding Algorithms Of Polar Codes

Since the proof of Shannon’s channel coding theorem, a large number of channel coding techniques have been proposed and developed. Algebraic coding, including Hamming codes and BCH (Bose-Chaudhuri-Hocquenghem) codes, etc., dominated the first several decades, while modern coding theory was also developed during the recent years, and has attracted a lot of at-tention, including Turbo codes and LDPC (Low Density Parity Check Code) codes, etc. Polar codes, a recently introduced coding technique which are based on the channel polarization, have determined encoding and decoding structure like algebraic coding. By implementing both chan-nel combining and splitting process, the split channels can be obtained, and as the block-length increases, they turn out to be either completely noisy channels or completely clean channels. Based on this technique, polar codes can be proved to achieve the symmetric capacity of any binary-input discrete memoryless channel. Compared with other channel codes, the channel po-larization process adopted by polar codes is quite different, and thus they have attracted a lot of attention. However, the Successive Cancellation (SC) decoder used for polar codes is stil-1 considered to have high algorithmic complexity and decoding latency, and to further reduce the decoding complexity and latency, we investigate how to implement simplified SC decoding algorithm for polar codes with arbitrary block-length N=ln. As an improved version of SC de-coding, Successive Cancellation List (SCL) decoding also has high complexity. By analyzing the splitting behavior of different paths, we propose a Split-Reduced Successive Cancellation List decoder, and good trade-off between decoding performance and complexity can be achieved by adjusting the corresponding parameters. Finally, we consider the problem of designing punctur-ing patterns for polar codes. We establish a framework to investigate how the puncturing patterns may affect the split channels, and an efficient scheme to design puncturing patterns is proposed.In this dissertation, we focus on the investigation of decoding and designing puncturing patterns for polar codes. The contents of this dissertation are listed as follows.Firstly, we consider the problem of implementing simplified SC decoding for polar codes with arbitrary block-length N=ln. For N=2n, as the generator matrix is unique and has a determined structure, the simplified SC decoding algorithm can be derived explicitly for this special case. However, for a more general case N=ln,1≥3, the generator matrix does not have a unique or explicit formula, and thus the proof used in N=2n case can not be applied. To solve this problem, we adopt the decoder graph to build a general framework to analyze the simplified SC decoding for polar codes. By implementing simplified SC decoding, a significant reduction of algorithmic complexity and decoding latency can be achieved, while retaining exactly the same performance as SC decoding.Secondly, SCL decoder will inspect both options for the estimate of any unfrozen bit ui and update the metric of the current path, instead of directly making hard-decisoion like SC decoding. By storing multiple paths, SCL decoder can achieve better performance. However, the decoding complexity and storage requirements increase as the list size becomes larger. Thus, we consider how to further reduce the complexity while only leading to a slight loss in performance. Suppose that the hard-decision is sufficiently reliable, then it is straightforward to directly make hard-decisions rather than splitting the path, which may not degrade the performance too much. Based on this intuition, we introduce a threshold, and the path splits only if the reliability does not exceed it. Then, we analyze the splitting behavior of different paths, and introduce another threshold, which counts the number of stages that a path survives without splitting. Once some path exceeds this threshold, all the other paths are pruned. Finally, we prove that for any polar codes there exists a specific unfrozen bit, after which the splitting can be completely avoided and SCL decoding can be replaced with conventional SC decoding.Thirdly, we investigate how to design puncturing patterns for polar codes. As the channel state varies, puncturing serves as a common technique to design rate-compatible codes. Different puncturing patterns may have different effect on the performance, and thus we consider how to find the optimal puncturing pattern for polar codes. Starting from the polarization process, we analyze how a given puncturing pattern can affect the split channels. Based on this, we establish a mapping relation between puncturing patterns of codeword and those of information sequence. Finally, we propose a heuristic algorithm, which first designs a puncturing pattern for the information sequence and then derives an equivalent puncturing pattern for the codeword. According to the simulation results, this heuristic algorithm can achieve performance that is quite close to the optimal puncturing pattern, which is selected by exhaustive search.