Stack decoding of polar codes
K.Niu and K.Chen
A successive cancellation stack (SCS)decoding algorithm is proposed to improve the performance of polar codes.Unlike the conventional successive cancellation decoder which determines the bits successively with a local optimal strategy,the SCS algorithm stores a number of candidate partial paths in an ordered stack and tries to find the global optimal estimation by searching along the best path in the stack.Simulation results in the binary-input additive white Gaussian noise channel show that the SCS algorithm has the same performance as the successive cancellation list (SCL)algorithm and can approach that of the maximum likelihood algorithm.Moreover,the time complexity of the SCS decoder is much lower than that of the SCL and can be very close to that of the SC in the high SNR regime.
Introduction:Polar codes (PCs)have been proved to achieve the capacity of symmetric binary input discrete memoryless channels (B-DMCs)under a successive cancellation (SC)decoding [1].However the finite-length performance under SC is not satisfactory.The belief propagation (BP)decoding algorithm can improve the performance [2,3],whereas the optimal scheduling of messages in BP is hard to know.In [4],a linear programming (LP)decoder is introduced;unfortunately,it cannot work on channels other than the binary erasure channel (BEC).Moreover,there is a gap between the BP /LP algorithm and the maximum likelihood (ML)algorithm.The successive-cancellation list (SCL)decoder [5]can approach the performance of the ML decoder for a moderate list size L .Nevertheless,the time complexity of the SCL decoder is fixed and slightly high.Inspired by the stack decoding of the convolutional code [6],we propose an alternative decoding strategy called the successive cancellation stack (SCS)algorithm.Compared with the SCL decoder,the SCS algorithm can achieve the same performance and has lower time complexity.
Polar coding:In this Letter,we apply the same notation defined in [1].We assume communication over a symmetric B-DMC W :{0,1} R .
Let N =2n denote the code length.After channel combining,we get a vector channel W N (y N 1|u N 1)= N i =1W (y i |x i ),where x N 1=u N
1G N ,G N is
the generator matrix defined in [1],u N 1,x N
1[{0,1}N are the source and code block,respectively,y N 1
[R N
is the received signal and W (y i |x i )is the channel transition probability of W .By applying channel splitting,the transition probability of the polarised subchannel W (i )
N
can be defined as W (i )N
(y N
1,u i −11|u i )=
12N −1
u N i +1
W N (y N 1|u N
1)(1)
where
u i −11,u N i +1are the subvectors of u N 1.
Moreover,the transition probabilities in (1)can be easily calculated by a recursive structure [1].After using Bhattacharyya parameters to calculate the reliability,the information bits u A are assigned to the more reliable subchannels,A #{1,2,...,N }.Frozen bits u A c are transmitted through the others,where A c is the complement set of A .Without loss of generality,the frozen bits can be set to zeros when the channels are symmetric.Decoding:In [1],the successive cancellation (SC)algorithm is used to decode polar codes with low complexity O (N log N ).Let the estimation
vector of transmitted bits be ˆu N 1=(ˆu
decoder1,ˆu 2,···,ˆu N ).If bit i is frozen,then ˆu
i =0.Otherwise,the decoding rule is as follows:ˆu i =0,W (i )N (y N 1,ˆu i −11|u i =0)≥W (i )N (y N 1,ˆu i −11|u i =1)1,otherwise  (2)
where i [A .A code tree of polar codes can be constructed by this suc-cessive bit determination procedure.A decoding path d i 1=(d 1,d 2,...,d i ),i [{1,2,...,N }is composed of i branches in the tree.Along the path,the branch in the level-i denotes the corresponding bit taking the value of d i .SC decoding can be seen as a greedy search algorithm in the code tree and in each level only the one of two branches with larger probability is selected for further processing.Once a decision error occurs,there is no chance to correct it in the later procedure.
Theoretically,the performance of ML decoding can be obtained by traversing all the N -length paths in the code tree.But the time complex-ity of this brute-force search is exponential.As a width-first search algorithm,SCL doubles the number of decision paths and selects the
L best paths from the candidate paths in each decoding step [5].All the candidate paths in the list are extended simultaneously and all of them have the same length.The time complexity of the SCL algorithm is O (LN log N ).The SCL decoder has to use a considerable size of list to achieve similar p
erformance as the ML decoder.We can reduce list size L to lower the complexity.But the performance degradation caused by decreasing L depends on the specific channel condition.So,it is difficult to determine the optimal size of the list.
In contrast,the SCS decoder always searches along the best candidate path in the stack and the candidates no longer have the same length.Fig.1gives an example of a code tree with four levels.The paths with solid branches stand for the candidates in the stack.These paths are sorted by path metrics in descending order,where the one at the top of the stack has the largest metric.
level 4
paths in stack
T B Fig.1Example of code tree and decoding paths in stack of SCS
Initially,the metric for the null path f is M (f )=log 1.0=0.When extending a path d i −11to length i ,the updated rule of the metric is:if the extended bit is a frozen bit,the metric remains unchanged:
M (d i 1)=M (d i −11),
i [A c
(3)
Otherwise,if the extended bit is an information bit,the path metric should be updated by calculating
M (d i 1)=log W (i )N (y N
1,d i −11|d i ),i [A
(4)
This metric can also be recursively calculated by the structure of polar
codes.
In the SC decoder,the information bits are decided step by step,whereas in the SCS decoder,the bits in the path are only tentative values and probabilities of a certain information bit taking values 0and 1are both stored for further decoding.Let S denote the set of the paths in the stack.When the path with the largest metric in the stack has reached the length N ,the decoding procedure stops and the decision
sequence ˆu N 1is
M (d N 1=ˆu N 1)≥M (d i 1),∀d i
1[S
(5)
Unlike the sequential decoding algorithm of convolutional code,it is no
longer necessary to add a bias in the path metric of SCS decoding,since the metric in (4)has already included the path length information.Let D and T be the maximal and instantaneous depth of the stack,respectively.The successive cancellation stack algorithm can be summar-ised as follows:
A Initialisation:Set stack depth T =0.Compute the associated metric M (f )of the single-node path that contains only the root node (no branches)of the code tree.Push this null path into the stack and increase the stack depth T =T +1.
B Popping:Pop the path d i 1from top of the stack and decrease the stack depth T =T −1.
C Expansion:If the decoding bit u i +1is a frozen bit,simply extend the current path by d i +11=(d 1,d 2,...,d i ,0);otherwise,if u i +1is an infor-mation bit,extend the current path to two new paths (d 1,d 2,...,d i ,0)and (d 1,d 2,...,d i ,1).Then calculate the new metric(s)by (3)and (4).
D Pushing:For the information bit u i +1,if T .D −2,delete the path from the bottom of the stack and set T =T −1.Push the two extended paths into the stack and set T =T +2.Otherwise,for frozen u i +1,push d i +11=(d i 1,0)into the stack and set T =T +1.
E Sorting:Reorder paths in stack from top to bottom in descending metric.
F Decision:If the top path in the stack reaches the leaf node of the code tree,the algorithm stops and outputs the top path as the decision sequence;otherwise go to step B.
Similar to the conventional stack algorithm for convolutional codes,the time complexity of the SCS algorithm is variable depending on
ELECTRONICS LETTERS 7th June 2012Vol.48No.12
the channel state.Furthermore,the same method in [5]can also be uti-lised in the SCS decoder to reduce the unnecessary path copy operations and memory occupation.Thus the space complexity of the SCS algor-ithm is O (DN )which is D times that of the SC algorithm and dominated by the maxim
al depth of the stack.
Results:Fig.2gives the BLER performance comparison of different decoding algorithms of (256,128)polar code under the BI-AWGN channel.The iteration number of the BP algorithm is set to 100.The list size of the SCL decoder is fixed to L =20.The maximal depth of the stack in the SCS decoder is D =100.The lower bound on the ML algorithm is obtained by performing SCS decoding and counting the number of times the decoded codeword is more likely than the transmitted one.We can see that the performance of the SCS algorithm is far better than that of the SC or BP algorithms.Compared with SC decoding,the SCS algorithm can obtain a prominent performance improvement of 0.7dB.Moreover,the SCS decoder has almost the same performance as the SCL and both of them can approach the ML bound.
10
10
10
10
10
10
E b /N 0, dB
B L E R
Fig.2Performance comparison of SC,BP,SCL,SCS algorithms and ML bound of (256,128)polar code under BI-AWGN channel
To analyse the complexity of the decoders,times of recursive probability /metric calculating in trellis /tree are counted.So,the time complexity of SC decoding of (256,128)polar code is calculated as 256
×8=2048.The complexities of SCL and SCS are simulated over 105codewords.Table 1shows the average complexity comparison of the SC,SCL and SCS decoding algorithms of (256,128)polar code under BI-AWGN channels with different bit SNR.The complexity of the SCS is variable and decreases with the increasing SNR.
Specifically,it is far below that of the SCL decoder and very close to SC when E b /N 0is 4.0dB.
Table 1:Average complexity comparison of SC,SCL and SCS
Conclusion:The successive cancellation stack (SCS)decoding algo-rithm is proposed to improve the performance of polar codes.The SCS decoder has very low time complexity and its performance is very close to that of the ML decoder.Hence,it can achieve better trade-off between complexity and performance than other decoding algorithms.The only cost is that the space complexity becomes slightly larger.
Acknowledgments:This work is supported by the National Natural Science Foundation of China (61171099)and the Qualcomm Corporation.#The Institution of Engineering and Technology 201226April 2012
doi:10.1049/el.2012.1459
One or more of the Figures in this Letter are available in colour online.K.Niu and K.Chen (Key Laboratory of Universal Wireless Communications,Beijing University of Posts and Telecommunications,Beijing 100876,People’s Republic of China )E-mail:niukai@bupt.edu References
1Arıkan,E.:‘Channel polarization:a method for constructing capacity achieving codes for symmetric binary-input memoryless channels’,IEEE Trans.Inf.Theory ,2009,55,pp.3051–3073
2Arıkan,E.:‘A performance comparison of polar codes and Reed-Muller codes’,IEEE Commun.Lett.,2008,12,pp.447–449
3Hussami,N.,Korada,S.B.,and Urbanke,R.:‘Performance of polar codes for channel and source coding’.Proc.of IEEE Information Theory,Seoul,South Korea,July 2009
4Goela,N.,Korada,S.B.,and Gastpar,M.:‘On LP decoding of polar codes’.Information Theory Workshop (ITW),August–September 20105Tal,I.,and Vardy,A.:‘List decoding of polar codes’.Information Theory Proc.(ISIT),St Petersburg,Russia,2011,pp.1–5
6Jelinek,F.:‘A fast sequential decoding algorithm using a stack’,IBM J.Res.Dev.,1969,13,pp.675–685
ELECTRONICS LETTERS 7th June 2012Vol.48No.12

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。