Research And Implementation Of Polar Code Decoding Algorithms

The discovery of channel polarization and polar codes by Arikan is universally recognized as a major breakthrough in coding theory.Polar codes provably achieve the theoretic capacity of memoryless symmetric channels,with low encoding and decoding complexity.In November 2016,the 3GPP identified Polar Code as Channel coding and decoding technique for control channels in the scenarios of enhanced Mobile Broadband in the Fifth Generation of mobile commucation systems.Firstly,the theory and the process of channel polarization were introduced in this thesis.Then,based on the theory of channel polarization,we discussed the channel capacity of each subchannel and the probability distribution of channel capacity after channel polarization.Based on the theory of channel polarization,the structure of Polar Code coding and the construction of different rate polar codes are summarized.And the decoding performance of Polar Code with different code rates in the length of 1024 is simulated in Matlab.Then,we compared the decoding performance and complexity of Polar Codes with the Turbo Code and LDPC code,which are used in the current commucation systems predominantly.Secondly,the thesis introduced the SC decoding algorithm in details.As for the high complexity of SC algorithm,we simplified this algorithm in logarithm domain,and further simplified the algorithm based on min-sum method,the computational complexity of the decoder have been reduced greatly.Since the high decoding latency of SC decoder,we design a low-latency SC decoder.Compared to the original SC algorithm that output 1 bit serially,the proposed algorithm can determine 2 bits in one cycle.As a result,the entire decoding latency can be reduced from(2n-2)cycles to(1.5n-2)cycles without any performance loss for code-length n polar codes.Then,we designed the parallel SC decoder for polar codes.The parallel decoder was composed of mM = 2(m ?1)component decoders working in parallel,each component decoder decodes a block size of 1 / M of the original Polar code.Therefore the parallel decoder has M times faster decoding speed.Because the SC decoding algorithm can cause the problem of error diffusion,the decoding performance is only suboptimal.Thus,this thesis also focuses on the SCL algorithm,and the thesis designed the CRC-SCL decoding algorithm based on CRC,which made the decoding performance significantly improved compared with SC algorithm.Due to the high lantency of SCL algorithm,this thesis introduced the parallel SCL algorithm,which have M times faster decoding speed and was almost no performance loss than the origin SCL algorithm.Then,a multi-bit decision algorithm,namely 2kb-SCL algorithm,is proposed for general SC list decoding cases.This new algorithm can determine k2 bits at the same time without any performance loss for arbitrary K.As a result,the entire decoding latency can be reduced from 3n-2 to n/2k-2-2 cycles.And we implement the 2b-SCL decoder and a low-complexity SCL decoder on FPGA.Finally,this thesis focus on the Belief Propagation decoding algorithm of polar codes,which solved the problem of high latency and low throughput due to the serial decoding algorithms,such as SC algorithm and SCL algorithm.Since BP decoder didn't need a lot of iterations in high SNR,this thesis proposed three criteria for iteration termination,which can effectively reduce the time complexity of BP decoding algorithm.