Improved Successive Cancellation Flip Decoding of
Polar Codes Based on Error Distribution
Carlo Condo, Furkan Ercan, Warren J. Gross

arXiv:1711.11096v2 [] 23 Jan 2018

Department of Electrical and Computer Engineering, McGill University, Montréal, Québec, Canada
Email: carlo.condo@mcgill.ca, furkan.ercan@mail.mcgill.ca, warren.gross@mcgill.ca

Abstract—Polar codes are a class of linear block codes that
provably achieves channel capacity, and have been selected as
a coding scheme for 5th generation wireless communication
standards. Successive-cancellation (SC) decoding of polar codes
has mediocre error-correction performance on short to moderate
codeword lengths: the SC-Flip decoding algorithm is one of the
solutions that have been proposed to overcome this issue. On
the other hand, SC-Flip has a higher implementation complexity
compared to SC due to the required log-likelihood ratio (LLR)
selection and sorting process. Moreover, it requires a high number
of iterations to reach good error-correction performance. In this
work, we propose two techniques to improve the SC-Flip decoding algorithm for low-rate codes, based on the observation of
channel-induced error distributions. The first one is a fixed index
selection (FIS) scheme to avoid the substantial implementation
cost of LLR selection and sorting with no cost on error-correction
performance. The second is an enhanced index selection (EIS)
criterion to improve the error-correction performance of SCFlip decoding. A reduction of 24.6% in the implementation cost
of logic elements is estimated with the FIS approach, while
simulation results show that EIS leads to an improvement on
error-correction performance improvement up to 0.34 dB at a
target FER of 10−4 .

I. I NTRODUCTION
Polar codes [1] are error-correcting codes proven to achieve
channel capacity with infinite code length. They have been
selected as a coding scheme in the 5th generation wireless systems standards (5G), within the enhanced mobile broadband
communication scenario (eMBB), and are being considered
for both ultra-reliable low-latency communications (URLLC)
and massive machine-type communications (mMTC) [2]. The
variety of system parameters foreseen in 5G demand improved
decoding algorithms with a focus on reliable communications
and low power consumption.
In [1], the successive-cancellation (SC) decoding of polar
codes was proposed. It is able to achieve channel capacity
when the code length tends to infinite, but its error-correction
performance degrades at shorter lengths. To overcome this limitation, the SC-List decoding algorithm was introduced in [3].
The improved error-correction performance comes at the cost
of longer latency and higher complexity: various contributions
have improved speed and reduced implementation cost [4]–[6].
Successive-cancellation flip (SC-Flip) decoding [7] takes
a different approach to the improvement of SC, relying on
an implementation complexity lower than that of SC-List,
mainly sacrificing average decoding latency, and providing
error-correction performance comparable to that of SC-List
with a list size of 2. SC-Flip relies on multiple subsequent

applications of SC, and on the identification of the most likely
points in which the SC algorithm made a wrong decision. This
operation is based on the magnitude of logarithmic likelihood
ratios (LLRs) associated to the estimated codeword bits, and
it is costly to implement. Modifications proposed in [8], [9]
have shown that the error identification and correction process
of SC-Flip can be greatly improved. A decoding approach
similar to [5] has been recently proposed for SC-Flip in [10],
reducing latency at no cost in error-correction performance,
but substantially increasing the implementation complexity of
the decoder.
In this work, we propose two techniques to improve SCFlip decoding, based on the distribution of the first wrong
estimation incurred by SC. The first method simplifies the
wrong estimation identification process without degrading
the error-correction performance, leading to substantial complexity reduction, while the second method uses the error
distribution to restrict the search space to the bit indices most
likely to incur errors. Simulation results show the effectiveness
of the proposed techniques for low-rate polar codes, over a
wide range frame error rate (FER) intervals.
The remainder of this work is organized as follows: in
Section II polar codes and their decoding algorithms are
introduced. In Section III the proposed techniques are detailed,
and simulation results, together with comparison with the state
of the art, are presented in Section IV. Conclusions are drawn
in Section V.
II. P RELIMINARIES
A. Polar Codes
A polar code P C(N, K) of code length N and rate R =
K/N is a linear block code that divides N = 2n , n ∈ Z+
bit-channels in K reliable ones and N − K unreliable ones.
Information bits are transmitted through the reliable channels,
whereas unreliable channels are fixed to a value known by
both transmitter and receiver, and are thus called frozen bits.
Polar codes are encoded through the following matrix
multiplication:
−1
−1 ⊗n
xN
= uN
G ,
(1)
0
0
−1
where xN
= {x0 , x1 , . . . , xN −1 } represents the encoded
0
N −1
vector, u0
= {u0 , u1 , . . . , uN −1 } is the input vector, and
the generator matrix G⊗n is obtained as the n-th Kronecker
product of the polarization matrix G = [ 11 01 ]. Due to the
recursive nature of the encoding process, an N -length polar

S=3

α
β

S=2

αr

l

α
l

β

S=1

βr

S=0
û0

û1

û2

û3

û4

û5

û6

û7

Fig. 1. Successive-cancellation decoding tree for a P C(8, 5) code.

code can be interpreted as the concatenation of two polar codes
of length N/2.
The scheduling of operations required by the SC decoding
algorithm allows to see its process as a binary tree search,
where the tree is explored depth-first, with priority given to
the left branch. Fig. 1 portrays an example of SC decoding
tree, for P C(8, 5). Each node receives from its parent a vector
of LLRs α = {α0 , α1 , . . . , α2S −1 }. Each node at stage S
computes the left αl = {αl0 , αl1 , . . . , αl2S−1 −1 } and right αr =
{αr0 , αr1 , . . . , αr2S−1 −1 } LLR vectors sent to child nodes as
αli = sgn(αi ) sgn(αi+2S−1 ) min(|αi |, |αi+2S−1 |),

(2)

αri = αi+2S−1 + (1 − 2βil )αi .

(3)

The LLRs at the root node are initialized as the channel LLR
−1
yN
. Nodes receive the partial sums β from their left β l =
0
l
{β0 , β1l , . . . , β2l S−1 −1 } and right β r = {β0r , β1r , . . . , β2rS−1 −1 }
child node:
 l
βi ⊕ βir , if i ≤ 2S−1
βi =
(4)
otherwise.
βir ,
where ⊕ is the bitwise XOR operation, and 0 ≤ i < 2S . At
−1
leaf nodes, the β value and the estimated bit vector ûN
are
0
computed as

0, when αi ≥ 0 or i ∈ Φ;
βi =
(5)
1, otherwise.
The SC-List decoding algorithm [3] improves the errorcorrection performance of SC by relying on L parallel SC
decoding paths. Each path is associated to a metric, that helps
deciding which of the L paths is more likely to be correct.
B. Successive-Cancellation Flip Decoding
To improve the error-correction performance of SC, in [7]
the SC-Flip decoding algorithm was proposed. It is based on
the observation that a failed SC decoding process is due to
either an incorrect bit estimation caused by noise introduced by
the channel or, due to the sequential nature of SC, to a previous
incorrect bit estimation. Thus, the first wrong estimation is
always caused by the channel noise. To evaluate the impact
of wrong estimations, a genie-like decoder called SC-Oracle
was created: using foreknowledge of the transmitted codeword,
it identifies the channel-induced errors and ensures that SC
estimates the bit correctly. SC-Oracle shows that avoiding all

wrong decisions caused by the channel noise results in significantly improved SC error-correction performance. Moreover,
simulations with SC-Oracle have shown that a failed SC
decoding is mostly due to a single wrong decision caused by
channel noise, an event that denote as E1 .
The SC-Flip algorithm attempts the identification and correction of E1 events. A cyclic redundancy check (CRC) code
with a C-bit remainder is used to encode the information
bits. If the CRC check passes at the end of SC decoding, the
estimated codeword is assumed correct. In case the CRC check
detects an error, the Tmax LLRs with the smallest magnitude,
representing the bit estimations with lowest reliability, are
stored and sorted. The bit associated to the smallest LLR
is flipped, and SC is is applied to the part of the decoding
tree that follows it. This process is repeated for all the Tmax
indices, or until the CRC passes.
In general, increasing Tmax improves the error-correction
performance of SC-Flip, bringing it ever closer to that of SCOracle. In fact, the performance gap between SC-Flip and
SC-Oracle is due to two possible cases: either the estimated
codeword with a correct CRC check still contains errors, or
the decoding stopped after reaching the maximum number of
iterations Tmax without being successful.
Further improvements for SC-Flip decoding algorithm have
been recently proposed in [8] and [9], where a generalized
SC-Flip algorithm uses nested flips to correct more than one
erroneous decision with a single CRC, with a simulationbased scaling metric also introduced to help the baseline SCFlip decoder detect the erroneous bit indices more accurately.
Simulation results show an improvement of 0.4 dB when
Tmax = 10 with respect to SC-Flip. The implementation of
this method requires parallel decoders similar to SC-List.
III. I MPROVED S UCCESSIVE -C ANCELLATION F LIP
D ECODING
We propose two new techniques to improve the errorcorrection performance of SC-flip decoding, and to reduce the
implementation complexity of SC-Flip decoders.
A. Fixed Index Selection
In [7], it was shown that the average number of iterations for
SC-Flip decoding converges to that of a single SC decoder at
moderate to high Eb /N0 . However, a single iteration of SCFlip requires additional operations with respect to SC. The
standard SC-Flip decoding algorithm decides which bits to flip
by identifying the Tmax least reliable bit estimations among
the non-frozen indices. Since the estimation reliability is
directly associated to the magnitude of its LLR value (5), they
correspond to the Tmax LLRs with the smallest magnitude.
The associated bits are flipped in ascending order starting from
the one with she smallest |α|: thus, the construction of the
list requires the Tmax LLRs to be not only selected, but also
sorted. This operation results in substantial implementation
cost, that is the main contributor to the additional hardware
complexity of SC-Flip decoders with respect to SC decoders.

Eb /N0 = 2.5 dB

Normalized E1 Occurrence

1

Eb /N0 = 3.0 dB

0.8

0.6

0.4

0.2

0
0

10

20

30

40

50

60

70

80

90

100

110

120

130

140

150

160

170

180

190

Non-frozen indices

In Fig. 2 it is shown the normalized distribution of E1
occurrence over the non-frozen bit indices for P C(1024, 170),
with C = 32, obtained simulating 5 × 105 frames, for
two Eb /N0 points. It can be noticed that bits have different
probability of E1 , with a select few having a higher probability
of E1 than the remaining ones, and the majority of them
not incurring any error. The height and position of the error
distribution spikes can be used to determine, off-line, which
bits to flip and in which order. In the provided example for
Eb /N0 = 3.0 dB, considering the non-frozen bits indexed
from 0 to K +C −1, the first flipped bit would be that at index
29, corresponding to the highest E1 occurrence, followed by
those at index 2, 35, 7, and so on, in descending probability of
E1 occurrence order, until Tmax attempts have been reached
or the CRC check passes. Determining which bits to flip
off-line allows to avoid the LLR selection and sorting logic.
Thus, the resulting SC-Flip decoder has an implementation
cost negligibly different from that of an SC decoder.
B. Enhanced Index Selection
It is possible to use the error distribution information to
increase the effectiveness of the standard LLR-based bit flipping selection scheme of SC-Flip. In its original formulation
[7], SC-Flip chooses which Tmax bits to flip among all the
K + C non-frozen bits in the code. However, from Fig. 2 we
can see that the majority of information bits have very low
error probability, that can be considered negligible depending
on the target FER. Consequently, it is possible to restrict the
LLR selection to the set of bit indices corresponding to high
enough probability of E1 .
This can improve the error-correction performance by increasing the chance of the wrong estimation to be included
within a limited number of Tmax indices, automatically excluding LLRs that have an averagely low magnitude, but
correspond to indices with low error probability. Let us in
fact observe Fig. 3, that shows the average LLR magnitude
for each information bit index for P C(1024, 170), C = 32,

Normalized average LLR magnitude

Fig. 2. Normalized distribution of E1 occurrence for P C(1024, 170), C = 32, 5 × 105 simulated frames.

1

0.8

0.6

0.4

0.2

0
0

20

40

60

80

100

120

140

160

180

Non-frozen indices
Fig. 3. Normalized average LLR magnitude at each non-frozen bit index for
P C(1024, 170) at Eb /N0 = 2.5 dB and C = 32. Indices highlighted in
red correspond to the non-zero occurrence of E1 shown in Fig. 2.

at Eb /N0 = 2.5 dB . It can be seen that the average LLR
magnitude |α| can vary quite a lot depending on the bit.
Highlighted in red are the LLRs whose indices correspond to
the non-zero occurrences of E1 shown in Fig. 2: many LLRs
of comparable or even smaller average magnitude are instead
associated to indices with very low probability of E1 . These
LLRs can feature among the Tmax with the smallest absolute
value and be selected by the standard SC-Flip algorithm, but
correspond to the erroneous bit in a negligible number of cases.
On the other hand, their being taken in account can force the
actual wrong estimation out of the Tmax flipped indices.
The error distribution as shown in Fig. 2 depends on the
number of simulated frames we are considering. With enough
frames, every information bit index is associated with a nonzero E1 occurrence: the zero error probability in Fig. 2 means
that no errors were encountered over the 5 × 105 simulated

2

b /N0

100

100

10−1

10−1

10−2

FER

FER

10−2
10−3

10−3

10−4
10−4
10−5
10−5

10−6
1

1.5

2

2.5

3

3.5

Eb /N0 [dB]

2.5

SC
SC-Flip - FIS
SC-List (L = 2)
SC-Oracle

3

SC-Flip
SC-Flip - EIS
SC-List (L = 4)

3.5

Fig. 4. FER curves for for P C(1024, 170), C = 32, Tmax = 10 with

different decoding approaches.
[dB]

frames. Given a target FER, it is possible to exclude from the
considered indices all those associated to error probabilities
lower than a certain threshold, in order to maximize the
chances of identifying the wrong estimation within Tmax
attempts. Moreover, to take in account the relative probability
of E1 occurrence, before sorting LLRs are scaled with respect
to the the associated E1 occurrence (see Fig. 2).
IV. S IMULATION R ESULTS
The error-correction performance of the proposed methods
has been evaluated and compared against the state of the
art. Fig. 4 and Fig. 5 show the FER for P C(1024, 170)
and P C(1024, 256) respectively, with C = 32. Both codes
have been constructed targeting a signal-to-noise ratio of
2.5 dB, and simulations have been run on AWGN channel
and BPSK modulation. Along with standard SC, curves are
plot for SC-Flip [7], SC-List [3], SC-Oracle, and SC-Flip with
the proposed fixed index selection (FIS) and enhanced index
selection (EIS). The maximum number of iterations has been
set to Tmax = 10 for all flip-based algorithms.
The FER of SC is the highest among all considered
algorithms, since all incarnations of SC-Flip substantially
improve on its error correction performance. On the other
hand, the SC-Oracle curve represents the case in which all
E1 occurrences are successfully corrected, and thus can be
interpreted as the lower bound of flip-based FER. The SC-Flip
decoding algorithm significantly improves the error-correction
performance of SC, but in both Fig. 4 and Fig. 5 a substantial
gap from the SC-Oracle bound can be observed, consisting of
0.38 dB for P C(1024, 170) and of 0.47 dB for P C(1024, 256)
at FER=10−4 .
SC-Flip with FIS is shown to perform slightly better than
standard SC-Flip for P C(1024, 170) in Fig. 4, with a gain of

1

1.5

2

2.5

3

3.5

Eb /N0 [dB]
SC
SC-Flip - FIS
SC-List (L = 2)
SC-Oracle

SC-Flip
SC-Flip - EIS
SC-List (L = 4)

Fig. 5. FER curves P C(1024, 256), C = 32, Tmax = 10 with different
decoding approaches.

0.08 dB at FER=10−4 . In case of P C(1024, 256), the FER
curves match. The Tmax = 10 indices considered by the
method are those corresponding to the highest probabilities
of E1 . This technique allows to substantially reduce the
implementation complexity of an SC-Flip decoder. The second
column of Table I reports the number and type of operations
required by a standard SC-Flip decoder, assuming a semiparallel structure similar to [11], and omitting the memory
requirements. The complexity is divided among the three main
operations that an SC-Flip decoder has to perform: F (2), G (3),
C (4), and the sorting and selection of the Tmax indices to flip.
Basic modules as comparators, XORs, multiplexers, adders
and registers are used to approximate the implementation
complexity; the number of parallel processing elements P e,
along with the LLR quantization bits Q, also affect the total
cost. It can be seen that FIS allows to completely avoid the
logic cost of the sorter function. To get a sense of its impact on
the total logic complexity, we consider the XOR block having
a cost of 1, the multiplexer a cost of 3, the adder and the
comparator a cost of 5 and the register a cost of 4. Supposing
an architecture with P e = 32, Q = 6 and Tmax = 10, the
sorter accounts for 24.6% of the total logic complexity.
Compared to SC-Flip, the EIS approach allows for 0.29 dB
and 0.34 dB gain for P C(1024, 170) and P C(1024, 256)
respectively. In Fig. 4, a total of 26 indices are considered,
while 45 are taken in account for the higher rate case portrayed
in Fig. 5. Compared to SC-List, for P C(1024, 170), the FER
of SC-Flip with EIS sits close to the curve obtained with list
size L = 4, outperforming the L = 2 curve of approximately
0.31 dB. For P C(1024, 256), the error-correction performance
of the EIS approach matches that of SC-List with L = 2. It
was shown in [12] that while an outer CRC code improves the

SC-Flip
Pe × Q × Comparator
2 × Pe × XOR
Pe × Q × MUX
Pe × Q × Sum
Pe × MUX
Pe × MUX
Tmax × Q × D-FF
Tmax × Q × Comparator
2 × Tmax × Q × MUX

F
G
C
Sorter

SC-Flip - FIS
Pe × Q × Comparator
2 × Pe × XOR
Pe × Q × MUX
Pe × Q × Sum
Pe × MUX
Pe × MUX
N/A

3

Average number of iterations

TABLE I
I MPLEMENTATION LOGIC COST BREAKDOWN FOR SC-F LIP AND
SC-F LIP - FIS.

2.5

2

1.5

1
1

100

1.5

2

2.5

3

3.5

Eb /N0 [dB]
SC
SC-Flip - FIS
SC-Flip - EIS 20 indices

10−1

FER

10−2

SC-Flip
SC-Flip - EIS 26 indices
SC-Flip - EIS 17 indices

Fig. 7. Average number of iterations for P C(1024, 256), C = 32, Tmax =
10 with different decoding approaches.

10−3

10−4

10−5

10−6
1

1.5

2

2.5

3

3.5

Eb /N0 [dB]
SC-Flip
SC-Flip - EIS 26 indices
SC-Flip - EIS 17 indices

2

2.5

3

SC-Flip - EIS 36 indices
SC-Flip - EIS 20 indices
SC-Oracle

3.5

Fig. 6. FER curves for P C(1024, 170), C = 32, Tmax = 10 with different
decoding approaches and number of indices considered by SC-Flip - EIS.

Eb /N0 [dB]

error-correction performance of SC-List decoding significantly
at medium to high code rates, at low code rates the CRC is
detrimental. Thus, for a fair comparison, we did not consider
any CRC in the SC-List curves. The indices used by EIS have
been found simulating a total of 1 × 106 frames, and selecting
those with the higher probability of E1 . The impact of different
number of considered indices in EIS is shown in Fig. 6 for
P C(1024, 170): it can be seen that decreasing it tends to
degrade the error-correction performance, while increasing it
does not bring substantial advantage. This remains true as long
as the number of indices considered by EIS is substantially
lower than K + C, at which point the FER will degrade to the
same obtained by standard SC-Flip.
As the code rate increases, the error correction performance
of both FIS and EIS starts degrading if Tmax is not increased.
This is due to the fact that as the number of information bits in
the code rises, the distribution of E1 occurrence spreads over
more bit indices. This results in a higher number of indices that
need to be considered by the proposed method: a higher Tmax
is thus needed to maintain the error-correction performance.

Fig. 7 depicts the average number of iterations for different
decoding approaches, where an iteration is defined as an
application of the SC algorithm over the N codeword bits.
It can be observed that at low Eb /N0 points, SC-Flip with the
FIS technique has up to 50% higher average iterations with
respect to standard SC-Flip [7], while the use of EIS entails an
increment of up to 25%. Both EIS and FIS reduce the number
of cases in which SC-Flip reaches the Tmax attempts, lowering
the average number of iterations. For example, the SC-Flip
decoding algorithm with P C(1024, 170) at Eb /N0 = 1 dB is
not able to find the correct codeword 40% of the time, with
Tmax = 10 and C = 32. With the FIS criterion, this failure
rate drops by 15%, while with EIS, it drops by 25%. However,
this positive contribution is offset by the position of the indices
with high probability of E1 occurrence, as shown in Fig. 23. The majority of these indices are in fact found towards
the beginning of the codeword: thus, each additional decoding
attempt requires almost a full iteration. On the contrary, in
standard SC-Flip there are no constraints on which indices to
consider, and at low Eb /N0 , the channel noise causes most
LLRs to have very low magnitude. Consequently, the Tmax
indices can be spread out over the whole codeword, leading to
standard SC-Flip having a lower average number of iterations.
At higher Eb /N0 , where the FER is of interest, the average
number of iterations quickly converges to 1 for all methods.
V. C ONCLUSION
In this work, we have proposed two techniques to reduce
the implementation complexity and reduce the FER of the
SC-Flip decoding algorithm. They are based on the identification of the bit indices where a channel-induced error is
most likely to occur. The proposed techniques have shown
significant improvement over SC-Flip when applied to low-

rate polar codes. The fixed index selection method has shown
an estimated 24.6% implementation complexity reduction at
no cost in error-correction performance, while the enhanced
index selection has been observed to bring up to 0.34 dB gain
in FER.
R EFERENCES
[1] E. Arıkan, “Channel polarization: A method for constructing capacityachieving codes for symmetric binary-input memoryless channels,” IEEE
Transactions on Information Theory, vol. 55, no. 7, pp. 3051–3073, July
2009.
[2] “Final report of 3GPP TSG RAN WG1 #87 v1.0.0,”
http://www.3gpp.org/ftp/tsg ran/WG1 RL1/TSGR1 87/Report/Final \Minutes report RAN1%2387 v100.zip,
Reno, USA, November 2016.
[3] I. Tal and A. Vardy, “List decoding of polar codes,” IEEE Transactions
on Information Theory, vol. 61, no. 5, pp. 2213–2226, May 2015.
[4] A. Balatsoukas-Stimming, M. B. Parizi, and A. Burg, “LLR-based
successive cancellation list decoding of polar codes,” IEEE Transactions
on Signal Processing, vol. 63, no. 19, pp. 5165–5179, Oct 2015.
[5] S. A. Hashemi, C. Condo, and W. J. Gross, “Fast and flexible successivecancellation list decoders for polar codes,” CoRR, vol. abs/1703.08208,
2017. [Online]. Available: http://arxiv.org/abs/1703.08208
[6] S. A. Hashemi, C. Condo, F. Ercan, and W. J. Gross, “Memory-efficient
polar decoders,” IEEE Journal on Emerging and Selected Topics in
Circuits and Systems, vol. PP, no. 99, pp. 1–1, 2017.
[7] O. Afisiadis, A. Balatsoukas-Stimming, and A. Burg, “A low-complexity
improved successive cancellation decoder for polar codes,” in Asilomar
Conference on Signals, Systems and Computers, Nov 2014, pp. 2116–
2120.
[8] L. Chandesris, V. Savin, and D. Declercq, “An improved SCFlip decoder for polar codes,” in IEEE Global Communications Conference
(GLOBECOM), Dec 2016, pp. 1–6.
[9] L. Chandesris, V. Savin, and D. Declercq, “Dynamic-SCFlip decoding
of polar codes,” CoRR, vol. abs/1703.04414, 2017. [Online]. Available:
http://arxiv.org/abs/1703.04414
[10] P. Giard and A. Burg, “Fast-SSC-Flip Decoding of Polar Codes,” IEEE
Wireless Communications and Networking Conference, 2018, to appear.
[Online]. Available: http://arxiv.org/abs/1712.00256
[11] A. J. Raymond and W. J. Gross, “A scalable successive-cancellation
decoder for polar codes,” IEEE Transactions on Signal Processing,
vol. 62, no. 20, pp. 5339–5347, Oct 2014.
[12] S. A. Hashemi, C. Condo, F. Ercan, and W. Gross, “On the performance
of polar codes for 5G eMBB control channel,” in Asilomar Conference
on Signals, Systems and Computers, 2017, to appear.

