Research On Low Complexity Decoding Algorithm Of Polar Codes

Polar codes are channel codes,which was proposed by Arikan based on channel polarization.They have been proven to achieve symmetric capacity of binary-input discrete memoryless channel and have a low encoding and decoding complexity.The common polar decoding algorithms include Successive Cancellation(SC)algorithm,Successive Cancellation List(SCL)algorithm and iterative algorithm(such as Belief-propogation(BP)algorithm and Soft Cancellation(SCAN)algorithm).The disertation does research on polar decoding algorithm,which has important theoretical significance and reference value.The main works and contributions are as follows:(1)The number of quantization bits has an important influence on the channel log-likelihood-ratio(LLR)memory and the internal LLR memory footprint in the SC decoder.A min-sum(MS)algorithm based on integer operation is proposed for SC decoding over BI-AWGN channel.The input values of the SC decoder is represented by 8-bit integers quantized uniformly from the channel receive values,and the MS rule is been used,the quantization operation is not needed in updating.The simulations show that the performance of the proposed algorithm is almost same as that of SC algorithm based on floating-point arithmetic when signal-to-noise ratio(SNR)is less than 4dB,since the quantization operation does not require a lookup table,the memory requirements are effectively reduced.(2)The check update of the polar decoding algorithm is called Box-Plus operation,involving hyperbolic function and inverse hyperbolic function.The method of reducing high computational complexity includes reducing the number of Box-Plus operations or using a low computational complexity check function instead of the Box-Plus operation.The thesis proposes a SC decoding algorithm based on a seven-segment piecewise linear function check update.By using only addition and multiplication operations,instead of the complex function of SC decoding Box-Plus operation,the proposed algirthm effectively reduces the computational complexity.Compared with the original SC algorithm,the check update using piecewise linear function SC decoding algorithm almost has the same decoding performance when the SNR is 1-3 dB;But the decoding performance is degraded,when the SNR is greater than 3dB.(3)The polar code can be regarded as a cascade of the constituent codes.By directly decoding the special constituent code,the time complexity of the SC decoding algorithm can be reduced.The paper proposes a latency reduction method based on the Fast Simplified SC(Fast-SSC)pruning tree,named Fast-ISSC algorithm.It utilizes the frozen bit check(FC)on the rate-other(R-other)nodes technique.In the proposed method,the constituent codes in the decoding tree are identified offline,and obtaining the Fast Simplified SC(Fast-SSC)pruning tree.During the decoding,the current node can be decoded directly,if it is a special constituent code;the R-other node that satisfies the FC is converted to the R-1 node online.The simulation results show that the frame error rate of the Fast-ISSC decoding algorithm is consistent with that of the SC algorithm,and the decoding latency is lower than the existing low-latency SC algorithm.(4)To reduce the high complexity of the Cyclic Redundancy Check Aided Successive Cancellation List(CA-SCL)decoding algorithm,the paper first proposes a low complexity CRC-Aided SCL decoding in systematical polar coding(SPC)format,based on the parallel processing of R-1 nodes.We call it as SPC-LC-CA-SCL algorithm,where the R-1 nodes select different update rules based on the parallel processing thresholds.Based on it,a low decoding latency and low computational complexity CA-SCL algorithm is further proposed by pruning the SC decoding tree and the number of list paths(referred to as R1-FC-CA-SCL algorithm).The simulation results show that,for the polar code(1024,512),the performance of the proposed SPC-LC-CA-SCL algorithm is almost the same in comparison with the SPC-CA-SCL algorithm,but the decoding latency is reduced by 6.35% when the threshold value of parallel processing for the R-1 node is set to 64.The performance of the R1-FC-CA-SCL algorithm is close to that of the CA-SCL algorithm,and it significantly reduces the decoding latency.Under the Binary Input Rayleigh Fading(BI-RF)channel with channel state information(CSI),the performance of the R1-FC-CA-SCL algorithm improves greatly as the number of lists increases.(5)The number of iterations of the BP decoding algorithm has an important influence on the time complexity.The paper propose an early stopping criteria for BP algorithm using CRC code(called BP-CRC).If the check performed on the source estimated value is satisfied,and the number of iterations is larger than the threshold,the iterations is stopped.For(1024,512)Polar codes over BI-AWGN channel,the simulations results show the performance of the BP-CRC algorithm is almost same as that of the original BP algorithm,and the average number of iterations is significantly reduced.As the SNR increases,the reduced number of average iterations becomes larger.(6)The SCAN algorithm has high decoding latency by SC serial scheduling.The paper proposes an improved Fast-SSC SCAN(I-FS-SCAN)decoding algorithm,where the special constituent codes and the R-other node satisfying the conditional FC can directly update the soft information output.For the BI-RF channel with CSI,the decoding performance of the I-FS-SCAN algorithm is close to that of the SC algorithm.The performance is changed little when the maximum number of iterations increase.The time-varying fading degrades the conditional FC effect.