Efficient decoding of polar codes

Polar Codes are the first mathematically provable capacity achieving error correcting codes which have low complexity encoding and decoding algorithms. For the decoding of polar codes, as a preliminary decoding algorithm, the successive cancellation (SC) decoding algorithm is used. SC algorithm is a sequential decoding algorithm which suffers from error propagation. For this reason, SC algorithm does not show good performance for moderate codeword lengths. Polar codes with SC decoding show worse performance than that of the modern channel codes, such as LDPC and turbo codes. To improve the performances of the polar codes improved versions of SC algorithm such as SC list (SCL) and SC stack are introduced in the literature, and these algorithms show much better performance than that of the classical SC decoding algorithm although they have larger complexity compared to SC. Besides, cyclic redundancy check codes are concatenated with polar codes which are decoded using the SCL algorithm, and such a concatenated system shows better performance than the other modern channel codes. In this thesis, we first propose a tree structure for the successive cancelation (SC) decoding of polar codes. The proposed structure is easy to implement in hardware and suitable for parallel processing operations. Next, using the proposed tree structure, we propose a technique for the fast decoding of polar codes. With the proposed method, it is possible to decode all the information bits simultaneously at the same time, i.e., in parallel. Lastly, we introduce and improved version of the proposed high-speed decoding algorithm. The proposed high-speed decoding approach and its improved version are simulated on computer environment, and their BER performances are compared to the performance of the classical successive cancelation method. Furthermore, we introduce a new approach to the successive cancelation of polar codes. The proposed approach uses the soft likelihood ratios of the predecessor information bits for the determination of successor information bits. The proposed method can be considered for the construction of joint iterative communication systems exchanging soft likelihoods. It is shown that the proposed soft decoding approach shows better performance than the classical successive cancelation algorithm introduced in Arikan's original work. As we know, polar codes are decoded in a sequential manner using successive cancelation algorithm introduced by Arikan. The sequential nature of the decoding process suffers from error propagation. We inspect the effects of error propagation on the performance of polar codes and propose some methods to alleviate the degrading effects of error propagation on the code performance for short and long frame lengths.