Successive-Cancellation Flip Decoding of Polar Codes Under Fixed Channel-Production Rate
Ilshat Sagitov Charles Pillet Pascal Giard


IEEEexample:BSTcontrol


awgnAWGNadditive white Gaussian noise
snrSNRsignal-to-noise ratio
ferFERframe-error rate
scSCsuccessive-cancellation
sclSCLsuccessive-cancellation list
scfSCFsuccessive-cancellation flip
dscfDSCFdynamic scf
crcCRCcyclic-redundancy check
llrLLRlog-likelihood ratio

VECA: Reliable and Confidential Resource Clustering for Volunteer Edge-Cloud ComputingThis material is based upon work supported by the National Science Foundation (NSF) under Award Number: OAC-2232889. Any opinions, findings, and conclusions or recommendations expressed in this publication are those of the authors and do not necessarily reflect the views of the NSF.
    

Hemanth Sai Yeddulapalli1,
Mauro Lemus Alarcon1,
Upasana Roy1,
Roshan Lal Neupane1, 

Durbek Gafurov1,
Motahare Mounesan2,
Saptarshi Debroy2,
Prasad Calyam1

1University of Missouri-Columbia, USA; 
2City University of New York, USA

Email: 
1{hygw7, lemusm, u.roy, neupaner, durbek.gafurov, calyamp}@missouri.edu;

2mmounesan@gradcenter.cuny.edu; 
2saptarshi.debroy@hunter.cuny.edu




    
=======================================================================================================================================================================================================================================================================================================================================================================================================



§ ABSTRACT 
Polar codes are a class of error-correcting codes that provably achieve the capacity of practical channels under the low-complexity scf decoding algorithm. 
However, the scf decoding algorithm has a variable execution time with a high (worst-case) decoding latency. This characteristic poses a challenge to the design of receivers that have to operate at fixed data rates. In this work, we propose a multi-threshold mechanism that restrains the delay of a scf decoder depending on the state of the buffer to avoid overflow. We show that the proposed mechanism provides better error-correction performance compared to a straightforward codeword-dropping mechanism at the cost of a small increase in complexity. In the region of interest for wireless communications, the proposed mechanism can prevent buffer overflow while operating with a fixed channel-production rate that is 1.125 times lower than the rate associated to a single decoding trial.





§ INTRODUCTION


Polar codes <cit.> are a type of linear error-correction codes that can achieve the channel capacity for practically relevant channels under sc decoding. However, at short to moderate block lengths, the sc algorithm provides an error-correction performance that is lacking for many practical applications. To address this, the scl decoding algorithm was proposed <cit.>. It provides great error-correction capability to the extent that polar codes were selected to protect the control channel in 3GPP's next-generation mobile-communication standard (5G), where scl serves as the error-correction performance baseline <cit.>.
However, the great error-correction performance of a scl decoder comes at the cost of high hardware implementation complexity and low energy efficiency <cit.>.

As an alternative to scl, the scf decoding algorithm was proposed <cit.>.
scf leads to an improved error-correction performance compared to sc, but still falls short of that of an scl decoder with a moderate list size. However, scf is more efficient than scl both in terms of computing resources and energy requirements <cit.>.

dscf decoding was proposed in <cit.>, where  modifications to scf were made to improve error-correction performance. With these modifications, the error-correction performance approaches that of a scl decoder with moderate list sizes at the cost of a minor increase of complexity compared to scf.
Preliminary results from a hardware implementation indicate that dscf decoders maintain a higher energy efficiency compared to scl decoders <cit.>.

Regardless of the variant, scf-based decoders exhibit a variable execution time by nature, with a latency much higher than the average execution time. 
Some efforts were made to reduce the variability of the execution time <cit.>, but this characteristic cannot be fully eliminated. 
This poses a challenge to the realization of receivers that have to operate at fixed data rates.
To compensate for the variable execution time of the decoder, words arriving from transmitter with a fixed time interval have to be stored in a buffer. Without any additional mechanisms, a fixed-size buffer may overflow even under reasonable conditions, e.g., when the channel-production rate is only slightly slower than the average decoder throughput. 
To avoid overflow, one of the straight-forward approaches would be to drop the received words when the buffer approaches overflow, i.e., applying a codeword-dropping mechanism. However, a codeword-dropping mechanism severely affects the error-correction performance.



  §.§.§ Contributions


In this work, we present a system model for operation under fixed channel-production rate that notably includes a controller for a scf-based decoder.
We propose a multi-threshold mechanism for that controller that modifies the maximum number of decoding trials by tracking the state of the input buffer. A codeword-dropping mechanism is used for reference. We provide a methodology for threshold selection. 
Simulation results are provided for various channel-production rates that are close to the rate associated to a single trial of scf decoding.
They show that both codeword-dropping and multi-threshold mechanisms can operate at fixed channel-production rates and prevent buffer overflow. 
We show that the multi-threshold mechanism provides a better error-correction performance than the codeword-dropping approach. 



  §.§.§ Outline
 

The remainder of this paper is organized as follows. <ref> provides a short introduction to polar codes and their construction, and briefly describes the sc and scf decoding algorithms. In <ref>, the system model is presented and the functionalities of each block of the model are described, with the exception of the controller. The controller is explained in <ref> along with the details on the codeword-dropping mechanism used for reference as well as the proposed multi-threshold mechanisms. In <ref>, the threshold-selection methodology for both mechanisms is provided. In <ref>, simulation results, in terms of the buffer-size variation and the error-correction performance, are provided and discussed. 
 <ref> concludes this work.



§ BACKGROUND




 §.§ Construction of Polar Codes

The central concept of polar codes is channel polarization. As the code length tends to infinity, bit locations either become completely reliable or completely unreliable. To construct a 𝒫(N,k) polar code, where N is the code length and k the number of information bits, the (N-k) least-reliable bits, called frozen bits, are set to predefined values, typically all zeros. The encoding is the linear transformation such that x=u× F^⊗ n, where x is the polar-encoded row vector, u is a row vector of length N that contains the k information bits in their predefined locations as well as the frozen-bit values, n=log_2 N, and F^⊗ n is the n^th Kronecker product ( ⊗) of the binary polar-code kernel F = [ [ 1 0; 1 1 ]]. The bit-location reliabilities depend on the channel type and conditions. In this work, the awgn channel is considered and the construction method used is that of Tal and Vardy <cit.>. 



 §.§ Successive-Cancellation Decoding

sc decoding is a natural way of decoding of polar codes as was introduced in the seminal paper <cit.>. The received vector (channel llr), denoted by {α_ch(0), … , α_ch(N-1)}, is used to estimate the bits of the polar-encoded word starting from the first bit û_0 <cit.>. The following bits {û_1,…, û_N-1} are estimated sequentially, i.e., in successive manner, by the same vector of channel llr and the estimations of the previous bits. Each information bit û_i is estimated by taking a hard decision on the corresponding decision llr, denoted by α_dec(i). Frozen bits are known to the decoder and are thus directly set to their corresponding value, typically zero. 




 §.§ SC-Flip Based Decoding


The scf decoding algorithm is introduced in <cit.>, where the authors observed that if the first erroneously-estimated bit could be detected and corrected before resuming sc decoding, the error-correction capability of the decoder would be significantly improved. In order to detect the decoding failure of the codeword, the information bits are concatenated with a r-bit crc being passed through the polar encoder. The code rate of the polar code is thus increased to R=(k+r)/N.

If the crc check indicates decoding failure at the end of the initial sc decoding pass, a list of bit-flipping candidates, denoted by ℒ_flip, is constructed. In the original scf decoding algorithm, ℒ_flip stores the bit indices that correspond to the non-frozen bits with the smallest absolute values α_dec.
A more accurate metric for constructing ℒ_flip is introduced in <cit.>. This metric takes in account the successive nature of the decoder, and its calculation for each non-frozen bit with an index i after the initial sc attempt is defined as:

    M_i = |α_dec(i)| + 1/c·∑_j ≤ i 
     j∈𝒜ln( 1 + e^( -c · |α_dec(j)|)) ,

where ln(·) denotes the natural logarithm, 𝒜 is the set of non-frozen bit indices, and  c is a constant optimized experimentally by way of simulation. The value c will vary in the range 0.0 < c≤ 1.0 depending on polar code parameters and channel conditions.

Regardless of the type of metric, for each new decoding trial the next bit index of ℒ_flip is selected and when this bit is estimated, the opposite decision is made, i.e., the estimated bit is flipped. Decoding then resumes until the last bit, following the sc algorithm. New scf trials are ran until the crc matches or until the maximum number of trials T_max is reached.
The maximum number of trials T_max∈ℕ^+ defines the decoding latency, and 1≤ T_max≤( k+r). Setting T_max to 1 renders the scf decoder equivalent to an sc decoder. If after T_max trials the crc check fails, decoding is stopped and the word is considered undecodable.

We note that in <cit.> the authors adapt the metric of (<ref>) to allow multiple bit flips per trial and name the resulting algorithm dscf decoding. Preliminary results of a hardware implementation of dscf decoding <cit.> show that a decoder that flips 2 
bits per trial is up to 5 times more area-efficient compared to state-of-the-art scl decoders while providing the same error-correction performance.

However, this comes at the cost of 11.5% lower throughput compared to scl. Without loss of generality, in this work, we do not apply multiple bit flips per trial. Thus, in the remainder of this work, the scf decoder with metric calculation of (<ref>) is applied.




 §.§ Execution time of scf-based Decoders


scf-based decoding algorithms have a variable execution time by nature. In this work, we assume that the latency of processing one decoding word under scf is an integer multiple of the execution time of one sc decoding pass. By denoting the latency of an sc pass as τ_sc, the execution time of one word under scf decoding is calculated as:

    τ_dec = t_req·τ_sc ,

where t_req is the required number of trials for a given codeword and 1≤ t_req≤ T_max, i.e., the required number of decoding trials either corresponds to the number of trials until the crc matches or to the maximum number of allowed trials. 







§ SYSTEM MODEL


In this work, we use a system model where the communication chain is simplified such that parts of the transmitter, the channel and the detector, are lumped into one block denoted as the channel. <ref> illustrates this simplified model, where the channel acts as a data generator to the remainder of the model that is the central part of this work, i.e., the buffer, the controller, and the decoder.



In the remainder of this section, we describe the general functionality of each block of the system model, with the exception of the controller that is described at greater length in its dedicated <ref>. 



 §.§ Channel

The channel block in our model acts as the generator that delivers incoming data blocks (words) to the decoder. The words are generated at a fixed time interval τ_ch  and stored in the buffer. The direction of the data write operation is illustrated by the arrow that is denoted by w in <ref>. We define the channel-production interval τ_ch as follows:

    τ_ch=υ_pr·τ_sc ,

where υ_pr∈ℝ^+ is an additional coefficient that we call the production coefficient and τ_sc corresponds to the latency of one sc decoding trial. 
The channel-production interval τ_ch cannot be lower than the latency of a single trial τ_sc , thus υ_pr≥ 1.
An increase of the production coefficient corresponds to an increase the data-production interval by the channel.

For convenience, throughout the paper, we often use the term channel-production rate, which corresponds to the inverse of the channel-production interval τ_ch . 



 §.§ Buffer

The buffer is used as memory to store words coming from the channel. The buffer is divided in slots, where each slot can accommodate one word. In this work, we consider a circular buffer. 
We denote the size of the buffer by the total number of slots B_tot, and the number of occupied slots is denoted by B_occ. One received word takes one slot in the buffer. The number of occupied slots B_occ is provided to the controller block. 



 §.§ Decoder

The decoder block reads the received words from the buffer. The reading event is illustrated by the arrow denoted by r in <ref>. The decoder implements the scf decoding algorithm, where, without loss of generality, the bit-flipping candidates are defined according to (<ref>). The decoder operates with a maximum number of trials T_max. However, the behavior of the block can change if the controller asserts its C_stop signal. When C_stop is True, the decoder immediately ceases the current decoding attempt, declares decoding failure, and starts processing the next word. Reading it from the buffer releases a memory slot, moving away from overflow. While C_stop is False, the decoder maintains its usual behavior, i.e., attempts up to T_max trials. The decoder provides the current number of fully applied trials t_cur to the controller. 




§ CONTROL MECHANISMS



As illustrated in <ref>, the controller is a key ingredient to our model. It regulates the decoder based on the number of available memory slots in the buffer. It aims to avoid buffer overflow while maximizing the error-correction performance.

During processing, the buffer has two critical states: buffer underflow and buffer overflow. Buffer underflow can easily be avoided, e.g., by suspending the decoder until the buffer is further filled with data. Furthermore, buffer underflow does not affect the error-correction performance. Buffer overflow is more challenging to deal with as it essentially requires to control the worst-case execution time of the decoder thus affecting the error-correction performance. Therefore, our work focuses on control mechanisms that cope with buffer overflow. 

In our model, the controller regulates the operation of the decoder by way of thresholds: as the number of occupied slots in the buffer gets closer to overflow, pre-defined thresholds are violated and the decoding delay is gradually restricted by lowering the maximum number of trials of the scf decoder.

In this work, the controller can implement two different mechanisms: codeword dropping or multi-threshold. <ref> illustrates the Gen_Ctrl_Sigs algorithm that generates the control signals. This algorithm covers both mechanisms that are considered. The inputs of the Gen_Ctrl_Sigs algorithm are the sets of buffer-size and trial-decoding thresholds, denoted by ℬ and 𝒯, respectively. The sets consist of multiple thresholds, where ℬ = {B_1,B_2, …, B_P} and 𝒯 =  {T_1,T_2,…, T_P} with P being the number of thresholds in each set. The set of thresholds ℬ is sorted in descending order while the set 𝒯 is sorted in ascending order. Once sorted, each threshold from ℬ corresponds to the threshold of 𝒯 located at the same position, i.e., they form a threshold pair according to their index.  

As illustrated by <ref>, the states of the buffer and of the decoder are obtained through the number of occupied buffer slots B_occ and the current number of decoding trials t_cur. The buffer state B_occ is compared to the elements B_i∈ℬ. When the first violation is detected, the decoder state t_cur is compared to the threshold T_i∈𝒯 of the corresponding index i. If a violation is detected, the controller stops the decoder. 






 §.§ Codeword-Dropping Mechanism



The codeword-dropping mechanism follows <ref> with the single threshold pair {B_1,T_1}. Note that the threshold-violation check loop is executed only once as P=1. 

As will be described in <ref>, the codeword-dropping mechanism only comes into play when the buffer is very close to overflow, i.e., B_1 is almost equal to B_tot. The trial-decoding threshold is set to T_1=0. This way, when B_occ>B_1, the decoder is immediately stopped regardless of how many trials have been attempted, i.e., the current codeword is dropped.



 §.§ Multi-Threshold Mechanism



The multi-threshold mechanism follows <ref> with sets of multiple thresholds. For simplicity, in this work, we propose to use sets composed of P=3 thresholds. The buffer-size thresholds satisfy B_3 < B_2 < B_1 < B_tot while the trial-decoding thresholds are T_1 < T_2 < T_3 ≤ T_max. The threshold pair {B_1, T_1} is the same as codeword dropping.

To obtain the best performance and tradeoff, the number of buffer-size thresholds and their values are expected to vary depending on code length and rate, channel condition, and T_max. The general goal remains the same: evenly set the buffer-size thresholds throughout the buffer to achieve gradual control. We propose to define the trial-decoding thresholds following the methodology provided in <ref>.






§ THRESHOLD-SELECTION METHODOLOGY



As mentioned in the previous section, the threshold T_1=0, and the buffer-size thresholds B_1,B_2,…,B_P are evenly distributed across the buffer.
Setting P to 3, only the thresholds T_2 and T_3 need to be derived.
The proposed threshold-selection methodology requires obtaining the balanced number of trials of scf decoding from offline simulations at the channel snr of interest and selecting the targeted production coefficient υ_pr.

The key metric for determining the balanced number of trials T_bal is the average number of decoding trials T_av derived from offline simulations.
Experiments have shown that our system model can operate with a fixed channel-production rate without buffer overflow if the average number of trials T_av of the decoder, restricted by T_max alone, does not exceed the production coefficient υ_pr. To establish a good tradeoff between error-correction performance and buffer-overflow prevention, we start by defining the balanced number of trials as T_bal=max(T_max)|T_av<υ_pr. 

Simulations of the scf decoder based on the setup described in <ref> are performed for the ideal case, i.e., T_max is the only decoding latency restriction.
<ref> shows examples of the average number of trials T_av for various T_max values. These results were obtained by running 10^6 random words for each T_max value considered and for a channel snr of 2.25 dB.

To illustrate, consider the two production coefficients υ_pr = 1.091 and υ_pr = 1.125 represented by the horizontal lines in <ref>, highlighted in solid green and dashed red, respectively.
In this example, the balanced number of trials is T_bal=2 for υ_pr = 1.091 whereas it is of 4 for υ_pr=1.125.


For our proposed multi-threshold mechanism, we suggest to set thresholds T_2 and T_3 as T_bal and T_bal+1, respectively. 
As mentioned in <ref>, the thresholds B_2 and B_3 are set to the middle and the head slots of the buffer. This way, the multi-threshold mechanism cuts off the high decoding trials exceeding T_3 once the buffer is filled up to B_3, and further restricts decoding to T_2 trials when the buffer is half full. As a further protection against buffer overflow, codeword dropping is activated when the buffer is full. The proposed methodology is applicable to other configurations, i.e., different N and k of the polar code, channel snr, and T_max. 
 
We highlight that applying data rates that are too high, i.e., too low υ_pr, will put too much pressure on the multi-threshold mechanism resulting in the equivalent of the codeword-dropping mechanism. Therefore, when possible, we recommend to select a data rate that results in a T_bal≥ 2.
On the other hand, if too low data rates are applied to the extent that T_bal=T_max, the multi-threshold mechanism is not necessary to avoid buffer overflow; T_2=T_3=…=T_P=T_max. 






§ SIMULATION RESULTS



We start this section with a description of our simulation methodology and continue by detailing the simulation algorithm.
The simulation results are then presented and discussed.



 §.§ Methodology



The simulation of the system model consists in a series of iterations with each iteration being a single unit of time. In order to represent the channel data-production interval with the production coefficient υ_pr, channel and decoder blocks need to perform their operations at particular loop iterations. 
For simplicity, we normalize the time by a latency equivalent to a single sc pass. For example, with a production coefficient υ_pr=1.125 and a decoding latency τ_sc of 8 units, the channel generates data every τ_ch=υ_pr·τ_sc=9 time units (<ref>). 

Before simulating our system model, we run simulations of the scf decoder within the ideal system, i.e., with the initial maximum number of trials as the only decoding latency restriction.
To illustrate the functionality of our proposed algorithm, the random blocks of data were encoded with a 𝒫(1024,512) polar code and a crc of r=16 bits with polynomial z^16+z^15+z^2+1 was used. The polar encoding algorithm is constructed for an approximate design snr of 2.365 dB. Binary phase-shift keying modulation is used over an awgn channel. Simulations were ran for S=10^6 random codewords at channel snr ranging from  1.75 to 2.5 dB. The scf decoding algorithm with a maximum number of trials T_max=11 was used, where the bit-flipping candidates are defined according to the metric of (<ref>). In <cit.>, the authors suggest adapting the constant c of the metric at each snr. Regardless, we use c=0.3 across all snr values to simplify analysis. 
For each decoding word, the required number of trials is stored in the list ψ_req. 
The frame-error flag, indicating whether the word was successfully decoded or not, is stored in the list of frame-error flags E. At the end of simulations, the lists ψ_req and E are saved and used for further analysis of the system model.

Then simulations are performed for the system model of <ref>, using the results obtained from the simulation of the ideal system. To illustrate our algorithm, the total size of the buffer is fixed to B_tot=100 memory slots. Both codeword-dropping and multi-threshold mechanisms are simulated. For the codeword-dropping mechanism, the thresholds B_1=99 and T_1=0 are set. For the multi-threshold mechanism, the set of the buffer-size thresholds is ℬ={99, 50, 10}. The set of corresponding trial-decoding thresholds is 𝒯={0, T_bal, T_bal+1} and varies depending on the specific channel snr and υ_pr. For the applied configurations, the sets of three thresholds result in the optimal tradeoff between complexity and error-correction performance.

In this work, we illustrate with production coefficients that are close to the bound of 1, i.e., υ_pr∈{1.091, 1.11, 1.125, 1.15, 1.2} are considered. We focus on υ_pr that are close to the bound to show that the mechanism maintains a fer near 10^-2 without running into a buffer overflow even with very aggressive channel-production rates. 

For all simulations, the resulting metrics are analyzed when the buffer is filled with substantial amount of words, i.e., when the system is at the steady-state, such that the comparison is fair for different values of υ_pr and snr.



 §.§ Simulation Algorithm


The simulation algorithm of our system model is summarized in <ref>. The algorithm contains a loop, where functions corresponding to each block of the system model are called at each iteration. Each iteration of the loop corresponds to one time unit, that is used as reference to all processes in the system. The function generating the channel data is denoted by Gen_Data, the function generating the controller signals is Gen_Ctrl_Sigs, and the decoder function is Decode. 

The functions of channel and decoder are passthrough functions with a behavior that depends on the state of their internal counters. Gen_Data will add a word to the buffer after every τ_ch iteration loops. Decode will read the word from the buffer at every τ_dec=t_req·τ_sc iteration loops (<ref>), where the required number of trials t_req for each decoding word s is read from the list ψ_req.

The word counter s is incremented when C_stop is raised, i.e., when either one of the thresholds is violated or when the decoder completed decoding according to t_req. At the same condition, the final current number of trials is saved to the list of resulting number of trials ψ_res. Simulation ends when all S decoding words are processed. The number of occupied buffer slots is stored in the list χ_occ at every loop iteration. 

At the end of simulation, Calc_fer_Impact calculates the binary list of resulting frame-error flags E^' indicating which words were successfully decoded and which were not. This list differs from the list of original frame-error flags E obtained from the simulation of the ideal system.
A decoding error is declared when the ideal system failed to decode the word or when there is an early decoder stoppage (ψ_res(s)<ψ_req(s)).






 §.§ State of the Buffer Over the Course of Simulation



<ref> shows the number of used buffer slots over the course of simulation, where the words come from the channel at a fixed rate that corresponds to a production coefficient υ_pr=1.125 and the channel snr is of 2.25 dB. The codeword-dropping mechanism is depicted in blue while the multi-threshold is in red. From the figure, we can see that both mechanisms effectively prevent buffer overflow, i.e., buffer occupied slots never reach B_tot=100 slots.





 §.§ Error-correction performance


<ref> shows the fer of the model, where the controller implements the codeword-dropping (blue) and multi-threshold mechanisms (red). 
Simulations are for various snr, but for a fixed channel-production rate corresponding to υ_pr=1.125. As such, the channel-production interval is close to the delay of a single scf trial.
The black curve is the ideal performance provided for reference.
The figure shows that, at low channel snr, both considered control mechanisms experience a degradation of the error-correction performance compared to the ideal case. This gap is reduced as the channel improves; the loss is virtually nonexistent at a snr of 2.375 dB. Across the range, we see that the multi-threshold mechanism either matches or outperforms the codeword-dropping mechanism. At the point of interest for wireless communication, a fer of 10^-2 is achieved by the scf decoder within the ideal system at approximately 2.25 dB. The codeword-dropping and the multi-threshold mechanisms show performance losses of approximately 0.1 dB and 0.0625 dB respectively.

<ref> also shows the fer of the model for both mechanisms, but for a fixed snr of 2.25 dB and various υ_pr .
scf with T_max=11 is applied for both mechanisms.
Although it cannot be sustained, the ideal performance for various T_max values are shown as horizontal lines for reference. From the figure, it can be seen that at lower production coefficients both codeword-dropping and multi-threshold mechanisms have a loss in error-correction performance compared to the ideal case with T_max=11. At υ_pr=1.091, the fer is even worse than the ideal case with T_max=3. The gap reduces as the production coefficient increases. The multi-threshold mechanisms fares better than codeword dropping across the whole range. At υ_pr=1.125, the fer of the multi-threshold mechanism reaches the ideal case for T_max=5. Both mechanisms match the ideal fer for T_max=11 at υ_pr=1.2. 








§ CONCLUSION


In this work, we proposed a control algorithm that adjusts the execution time of a scf-based decoder in realtime, allowing it to sustain operation without buffer overflow with a channel that produces data with a fixed rate that approaches that of a single decoding trial. By using multiple thresholds, the proposed mechanism is shown to allow an scf-based decoder to operate in a system with a fixed channel-production rate that is 1.125 times lower than the rate associated to a single decoding trial while preventing buffer overflow. In the region of interest for wireless communications, this at the cost of a small error-correction performance of approximately 0.0625 dB in comparison to the ideal but unsustainable case.





§ ACKNOWLEDGEMENT

The authors thank Tannaz Kalatian for helpful discussions. Work supported by NSERC Discovery Grant #651824.


IEEEtran


