A Golden Decade of Polar Codes: From Basic Principle to 5G Applications

Kai Niu,Ping Zhang,Jincheng Dai,Zhongwei Si,Chao Dong

1 The Key Laboratory of Universal Wireless Communications,Ministry of Education,Beijing University of Posts and Telecommunications,Beijing 100876,China

2 The State Key Laboratory of Networking and Switching Technology,Beijing University of Posts and Telecommunications,Beijing 100876,China

3 Department of Broadband Communication,Peng Cheng Laboratory,Shenzhen 518055,China

Abstract: After the pursuit of seventy years,the invention of polar codes indicates that we have found the first capacity-achieving coding with low complexity construction and decoding,which is the great breakthrough of the coding theory in the past two decades.In this survey,we retrospect the history of polar codes and summarize the advancement in the past ten years.First,the primary principle of channel polarization is investigated such that the basic construction,coding method and the classic successive cancellation (SC)decoding are reviewed.Second,in order to improve the performance of the finite code length,we introduce the guiding principle and conclude five design criteria for the construction,design and implementation of the polar code in the practical communication system based on the exemplar schemes in the literature.Especially,we explain the design principle behind the concatenated coding and rate matching of polar codes in 5G wireless system.Furthermore,the improved SC decoding algorithms,such as SC list (SCL) decoding and SC stack(SCS)decoding etc.,are investigated and compared.Finally,the research prospects of polar codes for the future 6G communication system are explored,including the optimization of short polar codes,coding construction in fading channels,polar coded modulation and HARQ,and the polar coded transmission,namely polar processing.Predictably,as a new coding methodology,polar codes will shine a light on communication theory and unveil a revolution in transmission technology.

Keywordst:polar codes;channel polarization;successive cancellation decoding; polar coded modulation;polar processing

I.INTRODUCTION

Channel coding,also named as error control coding,is not only the basic theory of modern information science,but also the core technique of modern communication system.

In 1948,C.E.Shannon[1]discovered that there exist some channel codes that can be decoded reliably when the code rate is no more than channel capacity whereas he did not provide the constructive coding schemes.In the past seventy years,pursuit of approaching capacity with practical en/decoding complexity is a central challenge in coding theory [2].In 1990s,Turbo codes[3]and LDPC codes[4]were discovered to dramatically improve the error performance of digital communication and approach the channel capacity,which are a big progress of coding theory.However,there is still a non-zero gap between the achievable rate of these codes and the channel capacity.

Figure 1.Roadmap of channel coding in wireless communication systems.

In 2008,Arıkan[5]invented polar codes1to achieve the capacity of the symmetric channels,which is a great theoretic breakthrough.Polar codes are coined by the concept of channel polarization.That is to say,by using the channel combining and splitting,a group ofNidentical binary-input discrete memoryless channels(B-DMC)can be transformed into a group of polarized channels,some of which become noiseless and the capacity tends to one (good channels) and others get noisy and the capacity goes to zero(bad channels).When the channel number,that is code length,tends to infinity,the ratio of the number of good channels to that of total channels will approach the capacity of original channel.Unlike the traditional channel codes,such as Turbo/LDPC codes,polar codes introduces a novel idea for the coding design.

For the practical application,channel coding is the key technology in the reliable transmission,especially in wireless communications.Figure 1 shows the roadmap of channel codes application in 3G∼5G wireless systems.It follows that low-latency and high reliable transmission are the main trend of the wireless communication in the past twenty years.Lowlatency requires the short code length and high reliability demands a low error rate.In pre3G wireless system,Reed-Solomon and convolutional concatenated(RS/CC) codes are applied to achieve high reliability(99.9%) with a very long code length (105∼106).Then in 3G and 4G systems,turbo codes are utilized to approach the same performance with a long length (104) and a low latency in terms of 10ms ∼100ms.The 5G systems propose more rigor requirements for the transmission latency(1ms)and reliability(99.999%)and tubo codes cannot meet this severe challenging.Due to the capacity-approaching feature,it seems that the classic polar codes can be used as the candidate of 5G channel coding.

However,the theoretic advantage of polar codes can not be transformed into the superiority of practice application.The error performance of the classic polar codes is not satisfied in the case of the finite code length.In order to improve the performance of polar codes,in the past decade,many advanced polar coding schemes and high performance decoding algorithms have been proposed.Specifically,cyclic redundancy check(CRC)concatenated polar codes and CRC aided decoding algorithms demonstrate the outstanding error performance in the short to medium code length[6][7][8]and outperform the performance of Turbo/LDPC codes.One highlighted merit of CRCpolar code is that it has no error floor due to the algebraic coding structure [9].On the contrary,both turbo and LDPC codes demonstrate the error floor effect at the high signal-to-noise ratio (SNR) region.Since the CRC-polar codes fulfill the requirement of high-reliability transmission,polar codes have been accepted as the coding standard in 5G wireless communication system[10].

In the previous survey papers[6][11],the basic principle of polar coding were briefly introduced.In 2019,IEEE communication society published the best readings of polar coding online[12].In this best readings,the polar coding theory,the construction and decoding of practical polar codes,as well as practical implementations are summarized and the exemplary works are selected from the literature.The interesting reader can also refer to the book of polar codes [9] for the further understanding.

In this paper,we retrospect the history of polar codes from birth to the present so as to review the development of this new direction.The remainder of the paper is organized as follows.Section II presents the basic principle of polar codes,including channel polarization,encoding and successive cancellation decoding.Then Section III describes the design criteria of polar codes with finite code length.We explain the design concerns behind the 5G polar codes.In Section IV,the construction algorithms,the encoding structure of concatenated polar codes and rate compatible methods are discussed from the view point of practice application.On the other hand,we address the improved decoding algorithms of polar codes in Section V,including successive cancellation list(SCL)decoding,successive cancellation stack(SCS)decoding and CRC-aided SCL/SCS decoding etc.Simulation results show the superiority of polar codes compared to Turbo/LDPC codes.Then the future direction of polar coded technique is discussed in Section VI.Finally,Section VII concludes the paper.

II.BASIC PRINCIPLE OF POLAR CODES

In this section,we first explain the channel polarization,that is,the core concept of polar codes.Then,the encoding and construction of polar codes and the classic SC decoding algorithm are presented.

Figure 2.Channel polarization scheme.

2.1 Channel Polarization

As stated in [5],channel polarization is an interesting phenomenon between the source block and the received sequence which can be explained by using the chain rule of the mutual information.Briefly,this phenomenon can be recursively implemented by transforming multiple independent uses of a given B-DMC into a set of successive uses of synthesized binary input channels.

Figure 2 illustrates the process of channel polarization.Given one binary erasure channel (BEC)Wwith the input bitxand the output signalyin Figure 2(a),the erasure probability of this BEC is 0.5 and the corresponding capacity isI(W)=0.5.By using one modulo-2 operation between the two independent BECs,i.e.x1=u1⊕u2,as shown in Figure 2(b),an equivalent compound channel can be obtained which has two input bitsu1,u2and two output bitsy1,y2,as well as the associated capacity isI(u1,u2;y1,y2).Furthermore,by applying the chain rule of mutual information,this compound channel can be decomposed into two synthesized channels:channelW−(indicated by the green line with the input bitu1and the output signalsy1andy2) and channelW+(indicated by the pink line with the input bitu2and the output signalsy1,y2,andu1).The mutual information relationship in this process can be expressed asI(u1,u2;y1,y2)=I(u1;y1,y2)+I(u2;y1,y2|u1)=I(W−)+I(W+).

Such operation is named as the single-step(or twochannel) polarization,which means two independent BECs with the same reliability are transformed into two polarized channels and the sum capacity of two channels is unchangeable,i.e.,I(u1,u2;y1,y2)=2I(W).In [5],Arıkan proved that the bad channelW−has a smaller capacity than the given BECWwhereas the good channelW+has a larger capacity,i.e.,I(W−)< I(W)< I(W+).Specifically,in this example,given the capacity of BECI(W)=0.5,the capacities of two polarized channels areI(W−)=0.25 andI(W+)=0.75,respectively.

The single-step polarization transform can be extended to four independent BECs,as shown in Figure 2(c).Two good channelsW+can be further transformed into two polarized channelsW+−andW++.Similarly,two bad channelsW−can also be converted into two channelsW−−andW−+.Obviously,the polarization effect is further strengthened.

In this way,the polarization transform can be recursively performed overN=2nindependent uses of a given BEC.As shown in Figure 2(d),when the code lengthNis increased from 20to 28,the polarization effect demonstrates more and more prominent,i.e.,the capacities of all the polarized channels tend to either 1(good/noiseless channels marked by pink lines) or 0(bad/noisy channels marked by dashed blue lines)except a vanishing fraction.

Theoretically,by using of martingale property,Arıkan proved the stochastic convergence behaviour of symmetric capacities of polarized channels in [5].That is to say,given a fixed constantδ ∈(0,1),as the number of channels (code lengthN) becomes infinity,the proportion of the noiseless channels is exactly equal to the symmetric capacity of the original B-DMCW.This limitation can be formally expressed as follows,

Remark 1.Channel polarization is a new methodology for the channel code design.We can assign the information bits on the noiseless channels and the fixed bits on the noisy channels so as to construct the polar codes.It is well known that the joint asymptotic equipartition property(AEP)plays a central role in the proof of Channel Coding Theorem [13].As pointed out by Niuet al.in [6],channel polarization can be regarded as an analog of joint AEP.For the noiseless channels,the transmitted codeword and the received sequence forms a jointly typical mapping and about2NI(W)codewords can be reliably transmitted over these channels.On the other hand,the jointly typical probability between a random vector and the received sequence is approximately2−NI(W)tending to zero with the increasing of code length.So we can conclude that channel polarization provides a constructive proof for the channel capacity achieving.

2.2 Basic Construction and Encoding

In order to construct polar codes,we should evaluate the reliability of each polarized channel in the channel polarization and select the high reliability channels to carry the information bits.Initially,Arıkan proposed a construction based on the Bhattacharyya parameter.Given a B-DMC channelW:X →Ywith the input bit setX={0,1},the output alphabetYand the transition probabilitiesW(y|x),x ∈X,y ∈Y,the corresponding Bhattacharyya parameter is defined as

Specifically,suppose a BECWwith the Bhattacharyya parametersis given and the Bhattacharyya parameters of polarized channelshave been obtained,the Bhattacharyya parameters ofNchannels can be easily recursively calculated as follows

Thus we can sort the Bhattacharyya parametersand select a channel index set with high reliability as the information setA.Although this construction is a low complexity method byO(Nlog2N),it is only accurate for the coding construction in a BEC.In other B-DMCs such as the binary symmetric channel(BSC)and the binary input additive white Gaussian noise (BI-AWGN) channel,exact calculation needs highly complicated Monte Carlo integration,while approximate iterative calculations result in the performance loss.Therefore,the Bhattacharyya parameter based method is a basic reference for the construction of polar codes.

Now we explain the encoding of polar codes.Given the code lengthN,the information lengthKand code rateR=K/N,the indices set of polarized channels can be divided into two subsets: one setA,called information set,which carries information bits and the other complement setAc,which is assigned the fixed binary sequence consisting of frozen bits.A message block consisting ofK=|A|bits is transmitted over the most reliable channelswith indicesi ∈A,while other channels are assigned the frozen bits.Therefore,a binary source blockuN1consisting ofKinformation bits andN −Kfrozen bits can be encoded into a codewordxN1by

where GN=BNFNis theN-dimensional generator matrix,BNis the bit-reversal permutation matrix,FN=F⊗n2denotes the channel transformation matrix,F2=[] is a 2×2 kernel matrix and “⊗n”denotes then-th Kronecker product.

Figure 3 shows an encoder example of polar code withN=8,K=4,andR=1/2.According to the reliability order,the information set isA={4,6,7,8}and the frozen set isAc={1,2,3,5}.So the information bits{u4,u6,u7,u8}are assigned to the polarized channels in setAwhile the frozen bits are deployed in setAc.Intuitively,each row of the generation matrix is associated with a polarized channel.

Figure 3.An example of polar coding for N=8,K=4.

Furthermore,one butterfly unit is also depicted in Figure 3,which transform two input bits (a,b) into two output bits(a⊕b,a).This operation is designated by the kernel matrix F2and related to the 2-channel polarization.For this example with the code lengthN=8,the polar encoder includes one bit-reversion and three stages of butterfly operations.In each stage,there are four butterfly units.

Generally,given the code lengthN=2n,the polar encoder containsn=log2Nstages and each stage hasN/2 butterfly units.Thus,the encoding complexity of polar codes isO(Nlog2N).Since the bitreversal matrix BNis a symmetric and permutated matrix,it satisfies BTN=BNand B−1N=BN.So the generator matrix GNhas two equivalent expressions and the polar encoding can be written as two forms,

and

The polar encoder implemented by(4)is named as the bit-reversal order encoder and that by(5)is the natural order encoder.

Figure 4.Trellis of the(8,4)polar code.

2.3 Successive Cancellation Decoding

Successive cancellation (SC) decoding,proposed by Arıkan [5],is the basic decoding algorithm of polar codes.Essentially,SC decoding is a greedy algorithm with the bit-wise soft-message calculation and hardmessage decision.Hence,this decoding can be regarded as a soft/hard message passing algorithm over the trellis or code tree of polar codes.

The trellis of polar codes is a regular structure withnstages andNlevels.Each stage includesN/2 butterfly units and each one includes a pair of check and variable node.Figure 4 shows an example of trellis for the(8,4)polar code.The soft and hard messages are calculated and passed over the variable nodes in the trellis,denoted bysi,j,1≤i ≤N,1≤j ≤n+1.The corresponding soft messages are the logarithmic likelihood ratios (LLRs) denoted byLi,j=L(si,j).Similarly,the hard messagesBi,jare the bits associated to the nodessi,j.Specially,in the left side of the trellis,the soft messages of the variable are designated asLi,1=L(),where=si,1are the estimated values of the source block.Similarly,in the right side of the trellis,the associated LLRs are denoted byLi,n+1=whereyiare the received signals.

The soft/hard message update and decision rule can be summarized as follows.

1.Soft message updated rule

wherei=1,2,···,N,j=1,2,···,n,⎿·」is the floor function,tanh(·)and artanh(·)are the hyperbolic tangent function and the inverse function respectively.The soft message at the check node labeled by the index⎿(i −1)/2j−1」mod 2=0(the even number node) is updated by using the first formula of (6) and the message at the variable node(the odd number node)is designated by the second equation.

2.Hard message updated rule

where⊕is the modulo-2 operation.In the even number node,the hard message is calculated by the first formula of (7) and in the odd number node,the message is referred to the second equation.

3.Decision rule

When the soft message is obtained in stage 1,the bit decision rule is written as

Therefore,for an information bit,the bit value associated to the node is decided by using the soft message and for a frozen bit,it can be simply set to a pre-defined value,i.e.,=0.

The computational complexity of SC decoding is mainly determined by the soft message calculations in the butterfly units.Since the trellis consists ofN/2 log2Nbutterfly units,the time complexity of the SC decoder isO(Nlog2N).Intuitively,the SC decoder needsNlog2Nmemory units to store the LLRs.However,this memory consumption can be reduced toNunits using the memory sharing mechanism.

Given an (N,K) polar code with the information setA,the block error rate(BLER)under SC decoding can be upper bounded by[5]

When the code lengthNgoes to infinity,the asymptotic BLER trends toothat is to say,the block error probability of polar codes will exponentially decay with the square root of the code length[14].

In a word,the theoretical advantages of polar codes can be summarized as follows.

1.Channel capacity achieving

Polar codes are a class of constructive channel codes achieving the symmetric capacity of the binary-input discrete memoryless channels.It firstly reveals the coding process approaching the channel capacity and equivalently provides a constructive proof of the channel coding theorem.

2.Low complexity en/decoding

By using the Walsh-Hardamard transform,the encoding complexity of polar codes isO(Nlog2N).Correspondingly,using SC algorithm,the decoding complexity of polar codes is alsoO(Nlog2N).Both the encoding and decoding have low complexity.

3.Error floor free

Due to the algebraic structure of polar codes,the block error probability under SC decoding exponentially decreases with the square root of the code length.Such algebraic property determines the polar codes have no error floor.On the contrary,both turbo and LDPC codes have the error floor phenomenon.

4.Channel polarization universality

Channel polarization is a universal phenomenon in the communication scenario rather than a specific technique in coding system.So it provides a novel idea and methodology to design and optimize the communication systems.

Figure 5.Major contributions to the polar coding.

Unfortunately,polar codes with finite length have some critical drawbacks.From the viewpoint of practical application,we list the main problems of the original polar codes should be solved.

Figure 6.The design framework of finite length polar codes.

1.Channel dependent construction

The initial construction based on Bhattacharyya parameter is a channel dependent algorithm and not precise for a general B-DMC.So it is important to precisely evaluate the reliability of polarized channels for any B-DMC.Furthermore,constructing a polar code independent of the channel condition is desirable for practical application.

2.Small minimum-Hamming distance

In the case of finite length,the minimum Hamming distance of polar codes is very small and inferior to some famous algebra codes,such as Reed-Muller (RM) codes or BCH codes.This drawback leads the performance of polar codes under maximum likelihood (ML) decoding is worse than RM/BCH codes.Hence,it is significant to improve the minimum-Hamming distance of polar codes by using algebraic coding techniques.

3.Coding length constraint

Due to the structure constraint of generator matrix of polar codes,the code length is restricted to the power of two,such asN=210=1024.However,in the data transmission,the code length is required to be arbitrary and flexible,i.e.,N=800,1000,etc.Hence,this constraint limits the application of polar codes in communication systems.We should design a rate compatible polar code to fulfill the practice requirements.

4.Poor error performance of SC decoding

The SC decoding is a suboptimal algorithm since the calculation and decision bit-by-bit may result in the error propagation.So the error performance of SC decoding is worse than that of turbo/LDPC codes.This is a big barrier for the polar code applying in communication systems.We should design a more powerful decoding algorithm to improve the error performance of polar codes.

In the next sections,we will explain the design rules of finite length polar codes,especially for the design principle behind the 5G polar codes.

III.DESIGN CRITERIA OF FINITE LENGTH POLAR CODES

In the past decade,many works were proposed to overcome the problems of the polar codes with finite length.Figure 5 shows the main contributions to the polar coding.Considering the requirements of practical communications,the performance of polar codes with finite length can be improved by jointly designing the encoding structure and decoding algorithm.Thus,we can summarize the en/decoding design framework of polar codes as shown in Figure 6.

The concatenated coding consists of the inner polar code and the outer code(e.g.cyclic redundancy check(CRC)code)is the main form of powerful polar codes with finite length.In this framework,the outer codes play double roles.At the side of the encoder,suitable outer codes can raise the minimum Hamming distance to improve the performance of the concatenated codes.Furthermore,we should solve the problems of construction,encoding,and rate compatibility.on the other hand,at the side of the decoder,the outer codes can be used to check the survivor paths and select the correct codeword whereby dramatically enhance the error performance.Therefore,powerful decoding algorithms and hardware implementation are the main concerns.Guided by this framework,the design criteria of polar codes with finite length can be summarized as follows.

Criterion 1.Polar codes should be constructed by high-precise,low-complexity and channelindependent methods.

The existing construction methods of polar codes can be mainly divided into three categories: (1)channel dependent construction,(2) channel independent construction,(3) weight distribution based construction.

In the first category,some channel parameters,e.g.,signal-to-noise ratio (SNR) in binary-input AWGN channel,are utilized to evaluate the reliability of the polarized channel based on the recursive structure of the polar coding.Recall that the Bhattacharyya parameter based construction is accurate only for the coding construction in a BEC yet approximate for other B-DMCs.Subsequently,Moriet al.[15] designed a density evolution (DE) algorithm to track the distribution of LLR and calculate error probability under the successive cancellation (SC) decoding with a complexity ofO(Nξlogξ).But high theoretical accuracy will need large number of samplesξ.Afterward,Trifonov[16]advocated the use of Gaussian approximation (GA) construction with a complexity ofO(N).Tal and Vardy [17] proposed an iterative algorithm to evaluate the upper/lower bound on error probability of each polarized channel with a complexity ofO(Nµ2logµ),whereµis a fixed integer called the fidelity parameter.GA can approach the Tal-Vardy method with a lower complexity.Then Dai and Niuet al.[18] proposed an improved GA algorithm for the polar codes with the long code length to further increase the accuracy of the GA construction.

In the second category,the reliability of the polarized channel can be ordered based on some channelindependent characteristics of polar codes.This construction is desirable for the practical implementation.Sch¨urchet al.[19] introduced the concept of partial order(PO)to indicate the invariant reliable order of a part of polarized channels.Furthermore,Heet al.[20]proposed the polarized weight (PW) algorithm.Although PW is an empirical construction,it can amazingly achieve almost the same performance as those constructed by the GA algorithm.In fact,the polar codes adopted in 5G standard[10]are constructed through a fixed reliability sequence of polarized channels obtained by a computer searching[21].

In the third category,distance spectrum or weight distribution is considered to thoroughly interpret the behavior of polar codes and deduce the construction of polar codes.Valipour and Yousefi[22] designed a probabilistic method to estimate the weight distribution of polar codes whereas the computational complexity is very high.Then,by using successive cancellation listing algorithm,[8] and [23] proposed the methods to enumerate and calculate the distance spectrum of polar codes.Recently,Niuet al.[24] introduced a new theoretical tool,named polar spectrum,to analyze and construct the polar codes.Polar spectrum provides a new insight to understand the algebraic property and has the potential value for the design of polar codes.

Criterion 2.Concatenated coding is a powerful coding scheme to improve the error performance of polar codes.

In the case of finite length,increasing the minimum Hamming weight is the core idea to enhance the error performance of polar codes.According to the classic coding theory,concatenated coding is a suitable method to fulfill this aim.As shown in Figure 6,the compound encoder consists of the inner polar encoder and the outer encoder.In the literature,Niu and Chen [7] firstly proposed the cyclic redundancy check concatenated polar(CRC-polar)codes to improve the error performance of short to medium length,which is a typical example of concatenated coding.Since CRC-polar codes increase the minimum Hamming distance and weight distribution,the corresponding performance can dramatically outperform that of turbo/LDPC codes.As a high efficiency and low complexity coding scheme,CRC-polar code was cited by 5G proposal[25]and accepted as the basic coding in 5G standard[10].Furthermore,Zhanget al.[26]investigated the optimization of CRC generator polynomials.

Trifonov and Miloslavskaya [27][28] proposed a dynamic-frozen coding scheme by combining the eBCH codes and polar codes whereas this scheme is not flexible for arbitrary coding configurations.Guided by the idea of concatenated coding,Huawei corporation proposed a parity check concatenated polar (PC-polar) codes [29] and the corresponding coding scheme was incorporated into 5G standard [10].An similar concept and initial coding were also introduced in[30].Chenet al.[31]designed the hash-polar code to improve the performance of polar codes under the SCL decoding.Recently,Zhouet al.[32] proposed a genetic algorithm to construct the polar codes so as to obtain the performance gain for SCL decoding.

As a representative coding scheme,CRC-polar codes guide a new direction to improve the performance of polar codes.In the next section,we will explain the technical details

Criterion 3.Rate matching is the critical requirement for the application of polar codes.

For the original polar code [5],the code lengthNis limited to the power of two,i.e.,N=2n.Consequently,designing good rate-compatible polar (RCP)codes,also named rate matching,to flexibly support an arbitrary code length and code rate becomes the key issue to practical application of the polar codes,which usually falls into two categories:puncturing and shortening.

For the puncturing mode,Shinet al.[33] advocated the use of a reduced generator matrix for efficiently improving the error performance of the RCP codes under the successive cancellation (SC) decoding yet searching good polarizing matrices is a timeconsuming process.Niuet al.[34] proposed an efficiently universal puncturing scheme,named quasiuniform puncturing algorithm(QUP)and the resulting RCP codes outperform the turbo codes used in 3G/4G wireless systems.Due to the high-performance and flexibility,this scheme was cited by 5G proposal[25]and used as the basic puncturing scheme of polar codes in 5G standard[10].

On the other hand,for the shortening mode,Wanget al.[35]devised a simple method by shortening the columns with weight 1 which is the same as the reversal quasi-uniform shortening (RQUS) algorithm proposed in[36].Such simple and high efficient scheme is also accepted as the basic shortening scheme in 5G standard [10].Meanwhile,Miloslavskaya [37] exploited the structure of polar codes and jointly optimized the shortening patterns and the source-bit assignment whereas the searching complexity is still very high and the shortening pattern is not universal.

Criterion 4.Designing the high-performance andlow-complexity algorithms is the key issue of polar decoding.

In the past decade,polar decoding algorithms were deeply investigated based on multiple mechanisms and viewpoints.Generally,the decoding algorithms can be mainly divided into four categories: (1)SC enhanced decoding,(2)soft output decoding,(3)SC flipping decoding,and(4)decoding for short code.

In the first category,we mainly simplify or enhance the SC decoding over the trellis or code tree.Alamdar-Yazdi and Kschischang [38] proposed a simplified successive-cancellation(SSC)decoder to decrease the redundant calculations in SC decoding without affecting the error performance.For the improved SC decoding algorithms,the most important algorithm is the successive cancellation list(SCL)decoding,which was independently proposed by two groups,Chen-Niu[39][40] and Tal-Vardy [41][42].Unlike SC only decodes one path at each level,Chen and Niu [39][40]realized that the greedy search of SC on the code tree can be extended to a width-first search.So a maximum ofLcandidate paths are reserved as the survivor path list and the final decision can be selected from the list.Tal and Vardy [41][42] proposed the similar mechanism and designed a so-called “lazy-copy” operation to reduce the memory overhead of path copy.Thanks to the algebraic structure of polar codes,with a small list size(e.g.L=32)at the medium length(e.g.N=1024),the BLER performance of SCL decoding can approach that of ML decoding.Meanwhile,the complexity of SCL isO(LNlog2N).SCL decoding is a great step to improve the performance of polar codes.Then Balatsoukas-Stimminget al.[43]designed the SCL decoder based on LLR calculation in order to facilitate the hardware implementation.Afterward,Zhanget al.[44]proposed the split reduced SCL decoder to further reduce the average decoding complexity.

On the other hand,Niu and Chen[45]realized that polar decoding can also performed a depth-first search on the code tree and proposed the successive cancellation stack (SCS) decoding.This algorithm uses an ordered stack to store the candidate paths and dramatically decrease the computational complexity down toO(Nlog2N) approaching that of SC decoding.Lately,based on the similar idea,Trifonovet al.[46]proposed the sequential decoding and the path metric is optimized in [47] to further efficiently reduce the algorithm complexity.

Combining the principles of SCL and SCS,Chen and Niuet al.[48]proposed the successive cancellation hybrid(SCH)decoding so as to provide a flexible configuration when the time and space complexities are limited.Lately,Guan and Niuet al.[49]designed a successive cancellation priority (SCP) decoding to decrease the number of path sorting operations.Under proper configurations,all these improved SC algorithms(SCL/SCS/SCH/SCP)can approach the performance of ML decoding but with an acceptable complexity.

To further improve the performance of polar codes,Niu and Chen[7]proposed the CRC-aided SCL/SCS(CA-SCL/SCS)decoding schemes.In these schemes,the SCL/SCS decoder outputs the candidate paths into a CRC detector,and the check results are utilized to detect the correct codeword.To lower the time complexity of SCL decoding brought by a large list size,Liet al.[8]proposed an adaptive CRC-aided SCL decoder(aCA-SCL)by gradually increasing the list size.Specifically for short to medium code length,the CASCL/SCS decoding can substantially improve the performance of polar codes and outperform turbo/LDPC codes.This is the key advantage of polar codes that can be adopted in 5G standard.

In the second category,we mainly focus on improving the performance and throughput of the BP decoder.Arıkan [5] first pointed out that BP algorithm can be used to decode polar codes over the trellis.The computational complexity of BP decoding isO(ImaxNlog2N),whereImaxis the maximum number of iterations.Then,Hussamiet al.[50] designed the multiple trellis BP algorithm to improve the performance of standard BP.Yuan and Parhi [51] proposed the min-sum (MS) and scaled min-sum (SMS)algorithm to simplify the BP decoder.In addition,two early stopping criteria were investigated in [52]and [53] respectively in order to decrease the iterative number and lower the complexity of BP decoding.Furthermore,by using the soft information calculation based on SC-like scheduling,Fayyaz and Barry [54]introduced the low-complexity soft-output decoding,named soft cancellation (SCAN),to make a tradeoff between the performance and complexity.Unfortunately,all the above algorithms are inferior to the SCL decoding.Recently,Elkeleshet al.[55]proposed the belief propagation list(BPL)decoding,which can approach SCL at the cost of increasing the complexity.

In the third category,our primary concern is the successive cancellation flipping(SCF)decoding to approach the performance of SCL with a low complexity.Afisiadiset al.[56]first proposed the bit-flipping method to generate multiple decision attempts.Then Chandesriset al.[57]introduced the concept of high order bit flips and designed a dynamic SCFlip decoding to keep the balance between the error performance and the average complexity.Zhanget al.[58] constructed a critical-set tree search to build a progressive bit-flipping decoding to efficiently lower the average complexity.Although these SCF decoding algorithms have low average complexity,the computational complexity in the worst case is still very high.

In the fourth category,we pay attention to the(quasi)-maximum likelihood decoding of short polar codes.Goelaet al.[59]introduced the linear programming(LP)decoding for polar codes whereas this algorithm is only suitable for the BEC channel.Kahraman and Celebi[60]realized the lower triangle structure of the generator matrix and introduced the sphere decoding (SD).Niuet al.[61] simplified the standard SD based on the optimum path metrics.Lately,Guo and Fbregas [62] designed the fixed and dynamic bounds to further reduce the complexity of SD.Piao and Niuet al.[63] considered the structure of CRC-polar codes and designed the CRC-aided SD(CA-SD)in order to achieve the performance of ML decoding.In addition,Wuet al.[64]proposed the ordered statistic decoding(OSD)to approximate the ML decoding of short polar codes.Although SD or OSD decoding can approach the performance of ML decoding,the computational complexity of these algorithms is very high.Therefore,these algorithms are only applied for decoding polar codes with short block length.

Criterion 5.Designing the high-throughput and low-latency architecture is the key issue of hardware implementation.

For the hardware implementation,the SC and SCL decoder with high-throughput and low-latency are pursued by the practical application.Lerouxet al.proposed the pipelined-tree architecture in [65] and the semi-parallel architecture in [66] respectively to improve the throughput of SC decoder.Then Zhang and Parhi[67]designed the sequential and overlapped architecture to further reduce the decoding latency of SC decoder.In addition,Yuan and Parhi [68] introduced the multi-bit decision to improve the throughput of SC decoder.Specifically,Xu and Niu[69]designed an SC decoder based on stochastic computation which is a new architecture with high-throughput and low power assumption.

On the other hand,many works focus on the hardware implement of SCL decoder.Sarkiset al.[70]proposed a fast list decoder based on the idea of SSC to improve the throughput.Fanet al.[71]considered the path selective expansion and double threshold fastsorting method to reduce the computation and latency of SCL decoder.Recently,Xiaet al.[72] designed a high-throughput SCL decoder achieves the decoding throughput of 1.103 Gbps with the list sizeL=8.

Remark 2.In 5G wireless communication system,high-reliability is the basic requirement of the data transmission.The designing of 5G polar codes should keep the balance between the high performance and the implementation complexity.Although the DE/GA/Tal-Vardy constructions have high precision,the channel mapping sequence [10] is adopted in 5G standard due to the advantages of channelindependence and low complexity.Since the CRCpolar codes [7] have simple structure and excellent performance,they are utilized as the basic coding scheme in 5G standard.Meanwhile,PC-polar codes[29]are also adopted as the further supplement.Furthermore,in order to fulfill the requirement of flexible coding,the QUP [34] and RQUS [35][36] schemes are used as the rate matching methods in 5G standard.Certainly,behind all these design concerns,the CRC aided SCL/SCS decoding[7]is the most important factor whereby the polar codes can be applied in 5G.By now,CA-SCL/SCS decoding has become the most popular algorithm and the standard reference in the field of polar codes.

IV.CONSTRUCTION AND ENCODING OF POLAR CODES

In this section,we first investigate the efficient construction methods,such as GA and PW.Then the minimum distance and weight distribution of CRC-Polar codes are analyzed to reveal the advantage of concatenated coding.Finally,we briefly explain the basic principle of QUP and RQUS scheme.All these methods are the critical parts of the polar encoding in the case of finite length.

4.1 Efficient Construction Methods

Gaussian approximation (GA) construction [16] is suitable for the polar coding in the AWGN channel.Suppose the coded bits are modulated using binary phase shift keying (BPSK) and transmitted over the AWGN channel with noise varianceσ2.The transition probability is written asW(y|x)=wherex ∈{0,1}andy ∈R.The LLR of each receive signalyis denoted byL(y)=which obeys Gaussian distribution,that is,L(y)∼Due to the symmetry of polar codes,an all-zero codeword is assumed to transmit.

In GA construction,the LLR of each polarized channelis assumed to obey a Gaussian distribution,that is,whereis the LLR mean.Since the LLR mean indicates the reliability of each channel,we can trace these LLR means to select the good channels to carry the information bits.Suppose an initial LLR meanm(1)1=is given and the LLR means of polarized channelsi=1,2,...,N/2 have been calculated,the LLR means ofNchannels can be computed recursively as follows

where the functionϕ(·)is defined as

Obviously,the exact calculation of LLR means in check nodes involves complex integration at the cost of high computational complexity.Generally,in conventional GA construction,we can use the well known two-segment functionφ(t)to approximateϕ(t),

Since this two-segment functionφ(t) has calculation error compared to the functionϕ(t),the channel selection may be inaccurate when the code length becomes long.So in [18],this function is modified by the more precise approximations,such as the new twosegment function Ω2(t),three-segment function Ω3(t)and four segment function Ω4(t).They are defined as follows,

and

Using these modified approximation functions in the improved GA construction,the polar codes with the long code length(e.g.N=214∼218)can ensure the excellent performance in BI-AWGN channels.

Another typical construction is the polarization weight(PW)metric[20].Given the code lengthN=2n,by using the so-calledβexpansion,PW metric can be calculated as follows,

whereβis the weight factor and(i1,i2,···,in)is the binary expansion vector associate to the channel indexi,that is,i −1=When the code length is fall in the rangeN=16∼1024,the weight factor is optimized asβ=21/4≈1.1892.

Figure 7.CRC-polar encoder.

Obviously,by (16),PW is a channel-independent metric.The larger the metric,the more reliable the corresponding channel.On the basis of PW,after some adjustment by using the computer simulation,the mapping sequence of polar codes [10] is obtained in 5G standard.

4.2 CRC Concatenated Polar Codes

CRC-polar codes are the primary concatenated coding scheme of polar codes.As shown in Figure 7,CRC-polar encoder consists of the CRC encoder and the polar encoder.k-bit source blockck1is input into the CRC encoder and generates the coded blockuK1,whereK=k+mis the block length andmis the CRC bits.These coded bits are mapped into the information bit setA,i.e.,uK1=uA.Then the information bitsuAand frozen bitsucAare fed into the polar encoder and generates the final concatenated codewordxN1.So the entire code rate is defined asR=k/N.

Thus the encoding process of CRC-polar codes can be written as

where GCRCis the generator matrix of CRC codes.

The key reason that CRC-polar codes obtain the performance gain is CRC codes can significantly improve the minimum Hamming distance and the weight distribution of the polar codes.This principle can be intuitively depicted in Figure 8.When single polar code is encoded in Figure 8(a),the Hamming distance of neighbour codewords,i.e.,dminis small.On the contrary,when the concatenated coding is utilized,as shown in Figure 8(b),the minimum Hamming distance can be enlarged since the CRC check can exclude many neighbour candidates.

For the CRC-polar codes,the BLER probability can be upper bounded by the union bound[73],that is,

Figure 8.Minimum Hamming distance comparison between polar code and CRC-Polar code.

whereAwis the weight enumerator andis the bit SNR.We can find that the weight distribution{w,Aw},especially the minimum weightdminand the enumeratorAdminwill determine the performance of CRC-polar codes.

Given the code lengthN=128,256 and the code rateR=k/N=1/2,we compare the weight distribution of polar and CRC-polar codes as shown in Table 1 and Table 2.

In these two tables,the optimal CRC codes,such as CRC6-opt etc.,are selected from [26].In Table 1,the generator polynomials of CRC6 and CRC6-opt areg(x)=0x43 and 0x73.Similarly,in Table 2,the generator polynomials of CRC9,CRC9-opt,CRC10 and CRC10-opt areg(x)=0x2CF,0x269,0x633,and 0x75F.Here,we use the hexadecimal to present the generator polynomial.

We see that (128,64) polar code has the minimum Hamming weightdmin=8 and the weight enumeratorAdmin=432.When the CRC6-opt is applied,thedminof CRC-polar code is increased to 12 and the weight enumeratorA12=300 is also smaller than that of polar code,that is,A12=2304.Similar phenomena can also be observed in Table 2.When the CRC codes are used,the minimum Hamming distance will increase from 8 to 16.In a word,CRC concatenated coding is an efficient and powerful method to improve the performance of polar codes.

4.3 Rate Compatible Polar Codes

According to the availability of prior information,the rate-compatible polar codes can be divided into two modes.In the puncturing mode,some code bits are deleted in the encoder whereby these bits are unknown by the decoder and treated as the ones transmitting over zero-capacity channels.In the shortening mode,the values of deleted code bits are predetermined and known to both the encoder and decoder.Thus,the associated channels can be regarded as one-capacity channels.

Theoretically,the optimal puncturing table of rate compatible polar codes can be optimized by a bruteforce search of the distance spectrum(for ML decoding) or BLER bounds (for SC decoding).However,the exhausted search for all the puncturing/shortening patterns is difficult to be realized.

Quasi-uniform puncturing (QUP) [34] and reversal quasi uniform shortening (RQUS) [35][36] are two simple and high efficient schemes to achieve the optimal tradeoff between the error performance and implementation complexity of RCP codes.

Since the code length of classical polar codes is limited to a power of 2,in order to generate an arbitraryM-bit length RCP code,we should start from an extended code of lengthN=2n,withndetermined byn=「logM⏋.Then anN-bit codeword is shrunk toMbits by appropriately deletingQ=(N −M)bits from it.

Define the puncturing/shortening tableJN=(t1,t2,···,tN)whereti ∈{0,1}withti=0 meaning that the corresponding bitxiis deleted.For QUP scheme,theN-length tableJNis first initialized as all ones,and then set thefirst Qbits as zeros.After the bit-reversal permutation on the table,the indices of zero elements inJNshould be punctured.Similarly,for RQUS,tableJNis first initialized as all ones and set thelast Qbits as zeros.By the bit-reversal permutation,the indices of zero elements inJNshould be shortened.

Table 1.Weight distribution of Polar and CRC-Polar codes for N=128.

Table 2.Weight distribution of Polar and CRC-Polar codes for N=256.

Figures 9(a)and 9(b)show the process of QUP and RQUS.Note that,since the natural order coding (5)is used in 5G standard,the bit-reversal permutation is not necessary.Hence,QUP/RQUS scheme is equivalent to puncture (shorten) the first (last)Qbits in the original codeword as shown in these two subgraphs.Since QUP is suitable for low code rate and RQUS is suitable for high code rate,5G standard[10]specifies that QUP is applied in the case ofR ≤7/16 and RQUS is utilized in the case ofR>7/16.

Figures 9(c)and 9(d)give the examples of QUP and RQUS respectively.GivenN=8,M=5,Q=3,after bit-reversal permutation,the puncturing table isJ8=(0,1,0,1,0,1,1,1),that means the code bitsx1,x3,andx5should be punctured.Similarly,the shortening table isJ8=(1,1,1,0,1,0,1,0),that means the code bitsx4,x6,andx8should be shortened.

V.IMPROVED POLAR DECODING ALGORITHMS

In this section,we briefly describe the basic principle of improved decoding algorithms of polar codes,such as SCL,SCS,SCH and SCP decoding.Finally,we demonstrate the superior performance of CA-SCL decoding by comparing the 5G polar codes,turbo and LDPC codes.

5.1 Code Tree and SC Decoding

In [6],we introduced the compact-stage code tree to uniformly describe SC decoding and its improved algorithms,such as SCL/SCS/SCH/SCP decoding.Figure 10 gives an example of SC decoding over a compact-stage code tree,which is corresponding to the trellis of Figure 4 and consists of eight levels by compacting the stages.

In this code tree,except the leaf nodes and the frozen nodes,each node has two descendants and the corresponding branches are labeled with 0 and 1,respectively.The number written next to each node denotes the path metric from the root to that node,e.g.LLR or a posteriori probability (APP).A decoding path includes a series of branches from the root to one leaf node.In Figure 10,the black circles represent the nodes that are visited and the gray ones are those that are not visited in the search process.

Since at a certain level associated with an information bit only one of the two branches with the larger/better path metric is selected for further extension,the SC decoding can be regarded as a greedy search over the compact-stage code tree.Hence,if a decision error occurs,this error will propagate in the extended path.As shown in Figure 10,the SC decoding path“00000011”(marked by the red bold branches)is not optimal due to the level by level decision strategy.

5.2 Successive Cancellation List Decoding

Figure 9.QUP and RQUS scheme for rate compatible polar codes.

Figure 10.SC decoding example on the code tree.

Figure 11.SCL decoding example on the code trees.

In order to mitigate the error propagation effect and improve the performance of SC decoding,Chen and Niu [39][40],Tal and Vardy [41][42] independently proposed the SCL decoding.In fact,Dumer[74]proposed the similar idea in order to improve the performance of RM codes.

Unlike SC decoder only reserves one path at each level,SCL decoder can extend 2Lpaths at each level and selectLmost reliable paths as the survivors.In the end,the path with the largest metric is selected from the survivor list as the final decision.The time complexity of SCL decoding isO(LNlog2N)and the space complexity isO(LN).

Figure 11 depicts an example of SCL decoding with list sizeL=2.In each level,four paths are extended and the corresponding path metrics are calculated.After path sorting,two survivor paths (marked by blue and red bold edges) are selected and stored.Finally,two survivors are stored in the list.One path“00000011” with path metric 0.20 and the other path“00010000”with metric 0.36.Due to 0.36>0.20,the more reliable path “00010000” is found whereby the error propagation in SC can be efficiently weaken.

5.3 Successive Cancellation Stack Decoding

Figure 12.SCS decoding example on the code tree.

Figure 13.SCP decoding example on the code tree.

SCL decoding substantially improves the performance of finite length polar codes yet the computational complexity is also increased.In order to reduce the decoding complexity,Niuet al.[45] proposed the SCS algorithm by using the depth-first search over the code tree.The SCS decoder goes along the code tree and uses a stack to sort and store the candidate paths.First,the top path is extended.Then,the succeeded paths are sorted and inserted into the stack.Until the top path with the largest metric reaches a leaf node,the decoding process stops and this path is output as the optimal decision.The main difference between SCL and SCS is that the candidate path of the former has the same length whereas the path of the latter has distinct length.Since SCS decoder only extends and calculates the necessary path nodes,its time complexity is far bellow that of SCL decoder even close to SC decoder.On the other hand,in order to achieve the same performance as SCL decoder,SCS needs a large stack depthDand the space overhead isO(DN).In the worst case,the space complexity is up toO(LN2)withD=LN.

Figure 12 gives a simple example of SCS decoding.In the stack,the top path (marked by red bold edges)has the largest metric 0.36 and the second candidate(marked by blue bold edges) has the second largest metric 0.3.Obviously,the top path“00010000”is output as the optimal decision,which is the same as the decoding result of SCL.However,the length of the top path is 8 and that of the second path is 6.Therefore,the number of the visiting nodes in SCS is small than that in SCL.So the time complexity of SCS is lower than that of SCL.

In order to make a tradeoff between the time complexity and the space overhead,Chen and Niuet al.devised the successive cancellation hybrid (SCH) decoding in[48]by combining SCL and SCS.This algorithm can achieve the same performance as SCL and SCS with a lower time and space complexity.

5.4 Successive Cancellation Priority Decoding

Guan and Niuet al.[49]proposed another algorithm,named successive cancellation priority (SCP) decoding,to reduce the time complexity of SCL.The SCP decoder performs priority-first decoding by interacting the priority queue with the trellis iteratively.On one hand,the priority information is stored in the priority queue so as to guide the extension of the candidate path.On the other hand,the trellis calculates and stores the intermediate results.Due to reducing most of the unnecessary path extensions by using the priority queue,the time complexity of the SCP decoder is much lower than the standard SCL decoder.

An example of SCP decoding is illustrated in Figure 13.In the priority queue,the survivor path(marked by red bold edges)has the largest metric 0.36 and ranked at the queue head.According to the priority information,the trellis calculates and extends the candidate paths.Hence,the survivor path “00010000” is also output as the optimal decision.However,since only the candidate paths in the queue are extended in the trellis,the time complexity of SCP is lower than that of standard SCL.

We summarize the characteristics of the four improved SC algorithms in Table 3.All the four algorithms can approach the performance of ML decoding.SCL is the baseline to improve the performance of SC decoding with a computational complexityO(LNlog2N).SCS is the counterpart to achieve the same performance with a low computational complexityO(Nlog2N)in high SNR yet high space complexityO(LN2).As a hybrid decoding,SCH can keep a good balance between the computational and space complexity.Finally,SCP presents another technique to achieve a good tradeoff.

Figure 14.Performance comparison of SC,CA-SCL,CASCS and CA-SCP decoding for(1024,512)CRC-polar code in AWGN channel.

All these improved SC decoding algorithms can be applied in CRC-polar codes.In this case,the SCL/SCS/SCH/SCP decoder outputs the candidate paths into a CRC detector,and the check results are utilized to detect the correct codeword.Using these CRCaided decoding schemes,the performance of CRCpolar codes can substantially outperforms that of turbo/LDPC codes.

We compare the BLER performance of SC,CASCL,CA-SCS and CA-SCP decoding for (1024,512)CRC-polar code under the AWGN channel in Figure 14.The polar code is constructed by GA algorithm and CRC8 codes is used with the generator polynomialg(x)=0x9F.We can see that the SC decoding has the worst performance.When the search widthPin CA-SCP is configured as the same as the list sizeLin CA-SCL,these two decoders achieve the same performance.Furthermore,when the CA-SCS decoder is set to a large depth stack(e.g.D=1024),it can also approach the same performance as CA-SCL or CASCP.

5.5 Performance Evaluation of 5G Polar Codes

In 5G standard,CRC concatenated rate-compatible polar codes (constructed by QUP or RQUS algorithms)are the basic schemes of polar codes.Next we compare the performance of 5G polar codes,turbo and LDPC codes under the AWGN channel.The BLER curves vsEs/N0with the information lengthK=400 and code rateR=1/5∼8/9 are shown in Figure 15.5G polar codes are constructed from the parent code with the code lengthN=1024 by QUP or RQUS schemes.The CA-SCL decoding algorithm is employed with the list sizeL=32 and a CRC8 code with the generator polynomialg(x)=0x9F is used.An eight-state turbo code in 3GPP LTE standard[75]is used as a reference.The LDPC codes proposed by Qualcomm corporation in the 5G standard proposal of channel coding[76]are applied.The logarithmic maximum a posterior (Log-MAP) algorithm is applied in turbo decoding and the maximum number of iterations isImax=8.And the belief propagation (BP) algorithm is applied in LDPC decoding and the maximum number of iterations isImax=50.

In most cases,polar codes can achieve additional coding gains relative to turbo or LDPC codes.In the region of low code rateR=1/5∼1/2,as shown in Figure 15,the polar codes punctured by QUP can achieve the same or slightly better performance than those turbo or LDPC codes.Especially for the code rateR=1/5,polar codes can outperform the turbo codes by 0.5∼1dB.Compared with turbo or LDPC codes,polar codes are a kind of powerful channel codes at the short to medium code length and the performance gain can be further improved by increasing the list size.

In the region of high code rateR=2/3∼8/9,compared to turbo codes,a maximum 1∼1.2 dB additional gains can be obtained at the code rateR=8/9.On the other hand,compared to LDPC codes,a maximum 0.8dB performance gain can be attained at the code rate 8/9.In contrast to the case of low code rate,the RQUS scheme can generate better polar codes in this case.In addition,both turbo and LDPC codes show an error floor phenomenon with the increasing SNR.On the contrary,CRC-polar codes have no such effect.

Table 3.Summary of improved SC algorithms.

Figure 15.BLER performance comparison of RCP codes(punctured by QUP and RQUS algorithms),LTE turbo codes and LDPC codes with information length K=400 and various code rates.

Remark 3.In 5G standard[10],either the downlink(downlink control indicator(DCI)or broadcast channel(BCH))or uplink(uplink control indicator(UCI))message bits are encoded by the CRC-polar codes and QUP/RQUS rate matching schemes.Accordingly,these control singling or channels are dictated the CASCL decoding[7]as the channel decoder algorithm to provide high reliability.As commented by Matlab 5G toolbox[77],“it is well known that CA-SCL decoding can outperform turbo or LDPC codes and this was one of the major factors in the adoption of polar codes by 3GPP”.

VI.POLAR CODING IN THE FUTURE

In the future 6G system,ultra-high reliable transmission,high spectrum efficiency and large system capacity are the primary requirements of wireless communications.In this section,we mainly discuss the polar coding to fulfill these requirements.First,we briefly introduce the limited performance of short polar code to satisfy the reliable transmission.Second,the code construction methods are investigated to improve the performance of polar codes under the fading channels.Third,polar coded modulation and polar coded HARQ are discussed in order to increase the spectrum efficiency.In the end,we design the framework of polar processing to jointly optimize the wireless transmission systems.

6.1 Optimal Short Polar Codes

Low-latency (100µs) and ultra-high reliability(BLER<10−6∼10−7) are the key performance metrics of 6G wireless transmission [78].These requirements become the serious challenges for the short channel codes.

In 2019,Arıkan [79] proposed the polarizationadjusted convolutional (PAC) codes with the Reed-Muller design rule to improve the ML performance of short polar codes.PAC codes have excellence performance and approach the normal approximation (NA)of the finite blocklength capacity in[80].However,the code rate is not flexibly configured and the complexity of sequential decoding is very high when the code rate approaches the capacity.

Table 4.Optimal generator polynomials of CRC-Polar codes with code length N=128.

Figure 16.CA-HD decoding for CRC-polar codes.

Piao and Niuet al.[81]found that the simple CRCpolar codes by the optimization of encoding and decoding can also approach the normal approximation.First,they used the sphere constraint based enumeration methods[82]to analyze the minimum weight distribution of CRC-polar codes.In fact,in the case of short code length,the generator polynomial of CRC codes is very significant to affect the performance of CRC-polar codes.Table 4 gives the optimal generator polynomials of CRC codes for short CRC-polar codes with code lengthN=128.Given the code rateR=1/3,1/2,2/3 and the CRC bit lengthm=20,24,16,the optimal polynomialsg(x) (indicated by hexadecimal) listed in this table are obtained after the bruteforce searching by calculating the minimum weight distribution,wheredminis the minimum Hamming distance andAdminis the corresponding enumerator.

Then,they designed a new CRC-aided hybrid decoding (CA-HD) for the CRC-polar codes by combining the CA-SCL and CA-SD algorithm.Figure 16 shows the diagram of CA-HD decoding,which includes two decoding modes: Adaptive CA-SCL mode and CA-SD mode.

Figure 17.The performance comparison of CRC-polar codes with various decoding algorithms and PAC codes at the code length N=128.

As shown in Figure 16,the adaptive CA-SCL decoding is first started to estimate the transmitted codeword.If the list size is smaller than the maximum sizeLmaxand the decision results can pass the CRC check,then the decoding is terminated.Otherwise,when the list size reaches the maximum size and the decoding is failed,CA-SD decoding is activated.In order to reduce the searching radius of sphere decoding,the CRC bits are re-encoded and input into the SD decoder.In the end,the result of SD decoding is output as the final decision.CA-SCL decoding has low complexity but the performance is inferior to the ML decoding.On the contrary,CA-SD decoding is identical to the ML decoding whereas the complexity is very high.Therefore,by elaborately integrating CA-SCL and CA-SD,the CA-HD decoding can achieve the optimal tradeoff between the performance and complexity.

We investigate the performance of CRC-polar codes with the code lengthN=128 and code rateR=1/3,1/2,and 2/3(configured parameters are selected from Table 4) under various algorithms,such as ADSCL(the maximum list sizeLmax=1024),CA-SCL(the fixed list sizeL=32) and CA-HD (Lmax=1024).Figure 17 depicts the BLER performance of CRCpolar codes.Furthermore,the BLER performance of(128,64)PAC code,LDPC code and the NA bound are also illustrated in Figure 17.Here,the performance of LDPC code is evaluated based on the construction of 5G NR LDPC code with the base graph 2(BG2).and the belief propagation(BP)decoding algorithm by 50 iterations.

We observe that the CRC-polar code under CASCL and ADSCL can achieve better performance than LDPC code.Furthermore,the performance under CAHD decoding significantly outperform that under CASCL and ADSCL and approach the NA bound.Especially,for the(128,64)code,the CRC-polar code is superior to PAC code and LDPC code and very close to the NA bound with a small gap of 0.025 dB.We can conclude from these results that CRC-polar codes with the optimized generator polynomial and CA-HD decoding can almost approach the finite blocklength capacity.Therefore these optimal CRC-polar codes can be regarded as the important candidate to provide the low-latency and ultra-high reliability transmission in the 6G wireless system.

On the other hand,for the medium blocklength,the performance of CRC-polar codes is evaluated and compared with turbo/LDPC codes in [6].For an example,given the code lengthN=1024 and the code rateR=,the CRC-polar code can achieve 0.5∼1 dB performance gain over the turbo/LDPC code at the BLER of 10−4.Generally,for the moderate to long blocklength,polar codes under the SCL decoding with a large list size will reach a similar or better performance than the turbo/LDPC codes.In addition,CRCpolar codes show no sign of error floors in the high SNR regime,which is a significant advantage over the turbo/LDPC codes.

6.2 Construction in Fading Channels

The construction of polar codes in the fast or block fading channels is an important direction for the practical application and has been attracted wide attentions.For the fast Rayleigh fading channel,Trifonov[83] first presented an iterative algorithm to calculate and track the diversity order and noise variance of the polarized channels.Lately,Zhou and Niuet al.[84]designed two algorithms to find a capacity-equivalent BI-AWGN channel of the Rayleigh channel and constructed the polar codes by using the GA algorithm.Recently,Niu and Li [85] established a systematic framework in term of the polar spectrum to analyze and construct polar codes in various fast fading channels,such as Rician,Rayleigh and Nakagami channels,which explicitly reveals the relationship between the diversity order and the codeword weight.

On the other hand,for the block fading channel,Bravo-Santos[86]proposed a recursive calculation of Bhattacharyya parameter yet with a time-consumption Monte-Carlo computation.Subsequently,Siet al.[87]designed a two-stage polar coding over channel uses and fading blocks.However the construction still depends on the recursive calculation of Bhattacharyya parameter.Niu and Li [88] systematically analyzed the error performance of polar codes by introducing the new concept,named split polar spectrum.The upper bound on the error probability of polarized channel is derived to explicitly reveal the relationship between the diversity orderLand the block-wise weight distribution of the codeword.

In a word,the polar codes constructed based on polar spectrum [85][88] can achieve similar or better error performance than those constructed by conventional construction.Due to the advantages of low complexity and high performance,these methods are suitable for the construction of polar codes in wireless communications.

6.3 Polar Coded Modulation and HARQ

In order to fulfill the high spectrum efficiency requirement of 6G wireless communications,extending the concept of channel polarization and designing the polar coded modulation (PCM) and polar coded hybrid automatic repeat request(PC-HARQ)system become the key technologies in wireless data transmission.

Seidlet al.[89] first established the framework of polar-coded modulation,which includes two-stage channel polarization transform,such as coding polarization and modulation polarization.The PCM framework can be designed based on two coded-modulation schemes,i.e.,the bit-interleaved polar-coded modulation (BIPCM) and multi-level polar coded modulation (MLPCM).Figure 18 shows the system architectures of two schemes.For the MLPCM,multiple polar encoders are utilized and a tuple of coded bits is directly mapped to a modulated symbol.On the other hand,for the BIPCM,a single polar encoder is used and the coded bit sequence is interleaved and mapped to the modulated symbol.Generally,the bitto-symbol mapping is very important for the PCM design in order to enhance the polarization effect.Gray mapping and set partition mapping are suitable for BIPCM and MLPCM respectively.Furthermore,ratematching(e.g.QUP scheme)and coding construction(e.g.GA algorithm)are also critical techniques in the PCM design.

Figure 18.System architecture of PCM.

For the MLPCM,Zhou and Niuet al.[90] extended the PW metric and presented a universal construction for MLPCM to facilitate the practical implementation.Then Khoshneviset al.[91] established the throughput maximization scheme by using the setpartition (SP) mapping and the rate matching algorithm.Furthermore,Daiet al.[92] introduced the spatial coupled structure among multiple coded blocks and designed the asynchronous polar-coded modulation scheme to improve the transmission reliability of MLPCM.

On the other hand,for the BIPCM,Shinet al.[93]found the mapping patterns for the pulse-amplitude modulation (PAM) with Gray labeling whereas the search complexity is very high.Then,using the constellation symmetry,Chen and Niuet al.[94] proposed an efficient search algorithm to find the optimal mapping of BIPCM.In order to improve the performance of BIPCM,Tianet al.[95]designed a joint successive cancellation decoding algorithm by combining the demapping and deinterleaving into SC decoder.Mahdavifaret al.[96] considered the multi-channel model of BICM and constructed the compound polar code.Muet al.[97] investigated the BIPCM with iterative detection/decoding(BIPCM-ID)and demonstrated that the error performance of designed BIPCM can outperform that of LDPC or Turbo coded BICM.

Hybrid automatic repeat request (HARQ) is another key technology to enhance the link reliability and throughput in practical wireless systems.Chen and Niu first proposed two types of the polar-coded HARQ schemes,such as incremental redundancy(IR)PC-HARQ[98]and chase combining(CC)PC-HARQ[99].By using the QUP scheme,the original IR-PCHARQ scheme [98] can achieve the same or higher throughput than turbo/LDPC code HARQ but its latency is slightly high.On the other hand,the CC-PCHARQ[99]is easy to implement while the system performance is limited due to small coding gain.

Lately,Liet al.[100] proposed the incremental freezing (IF) scheme so as to achieve coding gain at retransmissions.Further,an adaptive IR scheme based on the polarizing matrix extension (PME) was proposed in [101].By using QUP method,the PME based PC-HARQ scheme constructs a longer length polar code with multiple transmissions.Compared with the IF scheme,the PME scheme can obtain additional coding gain with enhanced polarization effect.

In summary,polar coded modulation and HARQ will become the key supports of the 6G wireless transmission.Considering the practical application,the construction method,rate-matching and mapping pattern are needed to be further explored in the future.

6.4 Polar Processing

Polarization effects exist in almost every unit of the communication system rather than only in the coding module.Theoretically,when the code length goes to infinite,polar coding can achieve the corresponding limitation of various communication scenario,such as loss/lossy source coding,multiple access,broadcasting,relay and distributed communication.As stated in [102],Korada pointed out that polarization is almost optimal for everything.From the viewpoint of practical application,Niuet al.[103] proposed the framework of the polar coded transmission,name polar processing,as a new design methodology to fulfill the high spectrum efficiency of 6G wireless system.Figure 19 illustrates the system architecture of polar processing.The architecture consists of three-stage polarization: coding polarization,modulation polarization and signal polarization.In the first stage,i.e.,signal polarization,many signal processing techniques have a general polarization effect.For an example,in the multiple-input-multiple-output(MIMO)system,different antenna link has distinct channel reliability.Similarly,in non-orthogonal multiple access(NOMA)system,different user undergoes diverse channel condition.In multi-carrier system,similar phenomenon can be observed.Therefore,individual antenna/user/-carrier can be regarded as the general polarized channel and the reliability distinction in each channel reveals the polarization in signal space.In the second stage,i.e.,modulation polarization,one signal streaming is further decomposed into many modulated bit subchannels with different reliability.Finally,in the third stage,i.e.,coding polarization,we use the one or multiple polar codes to match each modulated-bit polarized channels.

By using the three-stage polarization method,the polar processing transmitter glues the coding,modulation and signal processing into a joint polarization architecture so as to dramatically improve the system performance.Meanwhile,the polar processing forms a joint successive cancellation structure whereby CASCL decoding,soft demodulation and soft signal detection can be integrated into a low complexity compounded SCL receiver rather than the complex iterative calculation in turbo processing.

Under the framework of polar processing,Dai and Niuet al.[104] designed the polar-coded MIMO(PC-MIMO)system by the bit/symbol/antennal polarization.Then they [105] proposed the polar-coded NOMA (PC-NOMA) system by the bit/symbol/user polarization.Lately,Li and Niuet al.[106] investigated the polar-coded generalized frequency division multiplexing (GFDM) systems by the similar methods.Recently,Piao and Niuet al.[107] considered the polar-coded precoding system by designing a unitary finite-feedback transmit precoder.

Give different configurations of MIMO(1×1,2×2,4×4,8×8)and 64 QAM modulation,in the case of BLER=10−4,we evaluate the spectrum efficiency of three coded MIMO systems,that is,PC-MIMO,Turbo coded MIMO (TC-MIMO) and LDPC coded MIMO(LC-MIMO) in Figure 20.The polar codes are constructed by using the method in [104] and CA-SCL decoding is used.Turbo codes are referred to LTE standard[75]and the decoding is the Log-MAP algorithm.LDPC codes are utilized from 5G standard[10]and the BP decoding is applied.

Figure 19.System architecture of polar processing.

Figure 20.Performance comparison of PC-MIMO,TCMIMO and LC-MIMO.

As shown in Figure 20,for all the MIMO configurations,PC-MIMO can achieve 1∼2 dB performance gain over TC-MIMO or LC-MIMO.Since the polar processing jointly polarized the entire communication system,PC-MIMO can significantly improve the spectrum efficiency.Therefore,it follows that PC-MIMO is a powerful candidate technology to fulfill the high efficiency transmission requirement of 6G system.

Remark 4.By now,polar codes have been adopted as the coding standard of control channels in 5G wireless system.Due to the constraints of the control channels,the concatenated coding,construction and rate-matching of polar codes are standardized whileother advanced techniques are still open.The application in 5G is only a start point of polar codes in practical implementation.Look to the future,the polar coded transmission,or equivalently polar processing,will uncover a universal and powerful methodology to optimize the communication system.Due to the double advantages of performance and implementation,we believe that polar codes and polar processing will become more popular in the 6G wireless system,satellite communication system,microwave communication system,etc.

VII.TAO AND POLARIZATION: THE TRADITIONAL AND THE MODERN

In this paper,we review the basic principle of polar codes,the application in 5G standard and the promising directions in the future.As a great breakthrough of theory,the invention of polar codes is an important milestone of information theory and channel coding to uncover the constructive method approaching the channel capacity.For the practical application,polar codes with concatenated coding and CA-SCL decoding fulfill the high reliability requirement of 5G wireless system at the short to medium code length.In the future,polar processing may guide a revolution of system design and open a new era of communication technology.

When we retrospect the Chinese traditional culture,we find the fantastic correspondence between the polarization and Tao.In the famous work of Taoism,I Ching[108],it explains the principle of change.That is to say,Tai Chi gives rise to Liang Yi,Liang Yi give rises to four phenomena (Si Xiang),Si Xiang give rises to Eight Trigrams,and the understanding of auspiciousness through Eight Trigrams.According to legend,the ancient Chinese figure of Fu Xi invented the eight diagrams.The modern binary number system,the basis for binary code,was invented by Gottfried Leibniz in 1689.He encountered the I Ching and noted that similar presentation between the binary numbers and the eight trigrams [109].Recently,we find the 1-1 mapping relationship between the eight trigrams and the code tree of polar codes as shown in Figure 21.

Figure 21.The eight trigrams and code tree.

We observe that Tai Chi is mapped to the root node and Yin Yi and Yang Yi are associated to the polarized channelsW(1)2andW(2)2respectively.Furthermore,four phenomena,such as,Greater Yin,Shao Yang,Lesser Yin and Greater Yin,are corresponding to four polarized channelsW4(i),i=1,2,3,4.Finally,eight trigrams are 1-1 mapped to eight polarized channelW8(i),i=1,2,···,8.The eight trigrams indicate everything in the world and have distinct manifestation.On the other hand,the polarized channels have different reliabilities due to the channel polarization.It seems that I Ching provides an interesting interpretation of channel polarization.If we deeply explore the idea of Taoism,such ancient Chinese philosophical thought may guide a new insight into the design and optimization of the polar codes.

Passing through 3,000 years,the traditional Taoism and the modern coding contrast finely with each other.This is an amazing orchestration between the classic philosophy and modern technology!

ACKNOWLEDGEMENT

This work is supported in part by the Key Program of National Natural Science Foundation of China(No.92067202),in part by the National Natural Science Foundation of China (No.62071058),and in part by the Major Key Project of PCL(PCL2021A15).

NOTES

1In fact,Stole[110]also independently found the construction method of polar codes whereas the proof of polarization phenomenon and capacity-achieving should be first credited to Arıkan.