Decoding Algorithms And Implementations For Polar Codes

Due to the existence of unreliable noisy channels,channel coding is an indispensable and important part of mobile communication systems,which effectively protects information from noise interference by introducing redundant bits into the transmitted information stream.Since Shannon proposed the landmark channel coding theorem in 1948,pioneer coding theorists have dedicated sixty years to finding error-correcting codes that can achieve the channel capacity,and they gave birth to a series of error-correcting codes,such as Hamming codes,cyclic codes,convolutional codes,low-density parity-check(LDPC)codes,and Turbo codes.During this evolution,channel coding has realized a great leap from algebraic coding to probability coding.Sixty years after Shannon’s theorem,Ar?kan invented polar codes in 2008,which results in the first provably capacity-achieving error-correcting codes with an efficient construction scheme.The development of research on polar codes has gone through two stages,and the first stage is from2008 to 2015 when polar codes were at a young age.During the first stage,theorists focused on the chan-nel polarization theory,coding scheme,and the optimization of the polar construction scheme,meanwhile a few hardware groups published the circuit design for primary polar decoding algorithms.In 2011,the cyclic redundancy check(CRC)-aided sequential cancellation list(SCL)decoding algorithm was proposed for po-lar codes,which enabled polar codes to be competitive with LDPC codes and Turbo codes in terms of error correction performance.In 2015,the circuit design of the log-likelihood ratio(LLR)-based SCL decoding algorithm brought hope for the practical application-specific integrated circuit(ASIC)design of polar de-coders,which potentially promoted polar codes being ratified as 5G new radio(NR)standard codes in 2016.Hereafter,the research on polar codes entered the second stage,during which the scholars took the crucial requirements of 5G communication scenarios as the optimization goal to improve the corresponding perfor-mance of the polar decoding algorithms and circuits.With the evolution of the 5G NR standard and the rise of emerging communication scenarios,different communication system requirements bring new challenges to the design of polar decoders.Therefore,the classical method for co-design of polar decoding algorithms and implementations becomes more difficult to meet the stringent requirements of the ultra-high peak rate,ultra-low latency,ultra-high reliability,and ultra-low energy consumption in future communication systems.Also,the joint baseband signal processing in future communication systems requires a high-performance soft-output polar decoder.Choosing a suitable decoding algorithm and designing a high-performance decoder to meet different communication scenarios is the main task of this thesis.As advanced linear block codes,polar codes can be decoded by the Bayesian network-based belief prop-agation(BP)algorithm.When the resulting BP decoding adopts different message-passing mechanisms and a-priori information assignment,BP decoding alters into classic successive cancellation(SC)decoding and soft cancellation(SCAN)decoding.In this thesis,the relationship between the three decoding algorithms is illustrated through the factor graph model.Based on these three Bayesian theory-derived decoding algo-rithms,a series of joint optimization schemes on decoding algorithms and implementations are proposed for different communication scenarios,including the following four innovative studies.The first work is the algorithm optimization and circuit design of SCL decoding for 5G enhanced mobile broadband(e MBB)scenarios.In this thesis,the de-facto standard decoding algorithm for 5G e MBB control channels,the SCL decoding algorithm,has been optimized at both algorithm and circuit levels.A general node-based SCL(SR-SCL)decoding algorithm is proposed to reduce the latency of SCL decoding,and a dynamic SCL flip(SCLF)decoding algorithm is proposed to further improve the error correction performance.At the algorithm level,the proposed SR-SCL decoding adopts a smart division strategy for an SR node,and employs different fast decoding schemes for bit sequences with low code rate and rate one,thus improving the parallelism of the decoder.Combinined with the proposed path expansion strategies and rate matching adaptation strategy,SR-SCL decoding significantly reduces the latency of the SCL decoder.In addition,the proposed dynamic SCLF decoding supports a high-order bit-flip and CRC-based early stop strategies,and it accurately deduces the probability that the first path selection error occurs at each information bit.As a result,a dynamic SCLF decoder with a list size of 4 and only 3 additional decoding attempts can achieve the SCL decoding performance with a list size of 8,which can effectively balance the area,latency,and computational complexity of SCL decoding.At the circuit level,the first node-based SCL decoder that adapts to the 5G NR standard is implemented,with an integration of multiple optimizations on decoder units.Based on STM28 nm FD-SOI technology,the ASIC synthesis results show that for 5G NR uplink polar codes with length1024,the proposed SR-SCL decoder with a list size of 8 achieves a coded throughput of 2.532 Gbps and an area efficiency of 4.165 Gbps/mm~2.The second work is the algorithm and circuit design of the parallel-concatenated BP decoding and ordered statistics decoding(OSD)for 5G ultra-reliable and low-latency communication(u RLLC)scenarios.For such short-length scenarios,OSD is promising with superior error correction performance.At the algorithm level,a BP-OSD parallel concatenation scheme is proposed,which improves the decoding performance without increasing the latency of OSD.At the circuit level,the ASIC decoder for OSD is implemented with a highly parallel Gaussian elimination unit design.The novel Gaussian elimination design significantly reduces the required number of clock cycles compared with the state-of-the-art,and it can efficiently cooperate with other hardware units with flexible configurations of parallelism to adapt to different hardware indicators.Based on the SMIC 65 nm CMOS technology,the synthesis results that for 5G NR uplink polar codes with length128 and information length 105,the proposed decoder for OSD achieves a coded throughput of 865.88 Mbps and an area efficiency of 503.42 Mbps/mm~2,which surpasses the error correction performance of an SCL decoder with a list size of 8.The third work is the algorithm optimization and circuit design of BP flip decoding for future ultra-high peak rate scenarios.For such scenarios,highly-parallel BP decoding is the most promising among all polar decoding algorithms,which can achieve a multi-Gbps throughput.At the algorithm level,a generalized BP flip(GBPF)decoding algorithm is proposed,and a series of optimized flip set generation methods are proposed thereafter.For the polar construction scheme based on polarized channel reliability,an enhanced BP flip decoding algorithm is proposed,which effectively reduces the range of LLR sorting and the decoder area.For the polar construction scheme that only provides information bit distribution,the propagation structures of BP decoding errors are thoroughly discussed through the factor graph model.For the detected errors and undetected error cases,the targeted flip set construction methods are proposed respectively,and they are combined into a flip set with a constant size,which results in the novel GBPF-MS decoding algorithm.At the circuit level,the first hardware BP decoder that can achieve SCL decoding performance is designed,which innovatively implements the flip unit based on the binary domain and allows it to perform with the core BP decoding unit in a pipeline.Therefore,the flip unit does not introduce extra decoding latency.Based on TSMC 40 nm CMOS technology,the synthesis results show that for polar codes with length 1024 and information length 512,the proposed GBPF-MS decoder with additional 64 decoding attempts can achieve the performance of an SCL decoder with a list size of 8,which achieves a coded throughput 3.97 Gbps and an area efficiency of 4.19 Gbps/mm~2at 2.5 d B.The fourth work is the algorithm design and general-purpose processor(CPU)-based soft implementation of soft output list(SOL)decoding for future joint baseband signal processing requirements.At the algorithm level,this thesis achieves the polar list decoder that enables output soft information output at the coded bits.The proposed SOL decoder can not only surpass the SCL decoding performance of the same list size with the increase of iterations,can also be applied in iterative detection decoding(IDD)to provide reliable soft information for massive-input massive-output(MIMO)detection and then iteratively improve system error-rate performance.In addition,the node-based SOL decoding algorithm is proposed,which employs fast list decoding schemes for three special nodes,thus reducing the decoding latency.At the implementation level,considering the application prospect of cloud-based radio access network technology,this thesis designs a software SOL decoder based on CPU and uses single instruction multiple data(SIMD)instructions to realize an implementation with a parallelism of 32.Based on a single Intel i7-4790K CPU core,the implementation results show that for polar codes with length 2048 and information length 1723,the proposed software SOL decoder with a list size of 8 achieves an average latency of 192μs at 4 d B.When the iteration reaches 20times,the SOL decoder can further achieve the performance of the hybrid soft-output decoder with a list size of 16 at the advantage of a 2.4×throughput.