1

Fast and Flexible Successive-Cancellation List
Decoders for Polar Codes

arXiv:1703.08208v2 [] 29 Aug 2017

Seyyed Ali Hashemi, Student Member, IEEE, Carlo Condo, Warren J. Gross, Senior Member, IEEE

Abstract—Polar codes have gained significant amount of attention during the past few years and have been selected as
a coding scheme for the next generation of mobile broadband standard. Among decoding schemes, successive-cancellation
list (SCL) decoding provides a reasonable trade-off between
the error-correction performance and hardware implementation
complexity when used to decode polar codes, at the cost of
limited throughput. The simplified SCL (SSCL) and its extension
SSCL-SPC increase the speed of decoding by removing redundant calculations when encountering particular information and
frozen bit patterns (rate one and single parity check codes),
while keeping the error-correction performance unaltered. In this
paper, we improve SSCL and SSCL-SPC by proving that the
list size imposes a specific number of path splitting required to
decode rate one and single parity check codes. Thus, the number
of splitting can be limited while guaranteeing exactly the same
error-correction performance as if the paths were forked at each
bit estimation. We call the new decoding algorithms Fast-SSCL
and Fast-SSCL-SPC. Moreover, we show that the number of
path forks in a practical application can be tuned to achieve
desirable speed, while keeping the error-correction performance
almost unchanged. Hardware architectures implementing both
algorithms are then described and implemented: it is shown that
our design can achieve 1.86 Gb/s throughput, higher than the
best state-of-the-art decoders.
Index Terms—polar codes, successive-cancellation decoding,
list decoding, hardware implementation.

I. I NTRODUCTION
Polar codes are the first family of error-correcting
codes with provable capacity-achieving property and a
low-complexity encoding and decoding process [2]. The
successive-cancellation (SC) decoding is a low-complexity
algorithm with which polar codes can achieve the capacity of a
memoryless channel. However, there are two main drawbacks
associated with SC. Firstly, SC requires the decoding process
to advance bit by bit. This results in high latency and low
throughput when implemented in hardware [3]. Second, polar
codes decoded with SC only achieve the channel capacity
when the code length tends toward infinity. For practical
polar codes of moderate length, SC falls short in providing
a reasonable error-correction performance.
The first issue is a result of the serial nature of SC. In
order to address this issue, the recursive structure of polar
codes construction and the location of information and parity
(frozen) bits were utilized in [4], [5] to identify constituent
This work has been published in parts in the IEEE Wireless Communications and Networking Conference Workshops (WCNCW), 2017 [1].
S. A. Hashemi, C. Condo, and W. J. Gross are with the Department of Electrical and Computer Engineering, McGill University, Montréal, Québec, Canada. e-mail: seyyed.hashemi@mail.mcgill.ca,
carlo.condo@mail.mcgill.ca, warren.gross@mcgill.ca.

polar codes. In particular, rate zero (Rate-0) codes with all
frozen bits, rate one (Rate-1) codes with all information bits,
repetition (Rep) codes with a single information bit in the most
reliable position, and single parity-check (SPC) codes with a
single frozen bit in the least reliable position, were shown to
be capable of being decoded in parallel with low-complexity
decoding algorithms. This in turn increased the throughput and
reduced the latency significantly. Moreover, the simplifications
in [4], [5] did not introduce any error-correction performance
degradation with respect to conventional SC.
The second issue stems from the fact that SC is suboptimal
with respect to maximum-likelihood (ML) decoding. The
decoding of each bit is only dependent on the bits already
decoded. SC is unable to use the information about the bits
that are not decoded yet. In order to address this issue,
SC list (SCL) decoding advances by estimating each bit as
either 0 or 1. Therefore, the number of candidate codewords
doubles at each bit estimation step. In order to limit the
exponential increase in the number of candidates, only L
candidate codewords are allowed to survive by employing a
path metric (PM) [6]. The PMs were sorted and the L best
candidates were kept for further processing. It should be noted
that SCL was previously used to decoder Reed-Muller codes
[7]. SCL reduces the gap between SC and ML and it was
shown that when a cyclic redundancy check (CRC) code is
concatenated with polar codes, SCL can make polar codes
outperform the state-of-the-art codes to the extent that polar
codes have been chosen to be adopted in the next generation
of mobile broadband standard [8].
The good error-correction performance of SCL comes at
the cost of higher latency, lower throughput, and higher area
occupation than SC when implemented on hardware [9]. It
was identified in [10] that using the log-likelihood ratio (LLR)
values results in a SCL decoder which is more area-efficient
than the conventional SCL decoder with log-likelihood (LL)
values. In order to reduce the latency and increase the throughput associated with SCL, several attempts have been made to
reduce the number of required decoding time steps as defined
in [2]. It should be noted that different time steps might entail
different operations (e.g. a bit estimation or an LLR value
update), and might thus last a different number of clock cycles.
A group of M bits were allowed to be decoded together in [11],
[12]. [13] proposed a high throughput architecture based on
a tree-pruning scheme and further extended it to a multimode
decoder in [14]. The throughput increase in [13] is based
on code-based parameters which could degrade the errorcorrection performance significantly. Based on the idea in [5],
a fast list decoder architecture for software implementation

2

was proposed in [15] which was able to decode constituent
codes in a polar code in parallel. This resulted in fewer number
of time steps to finish the decoding process. However, the SCL
decoder in [15] is based on an empirical approach to decode
constituent Rate-1 and SPC codes and cannot guarantee the
same error-correction performance as the conventional SCL
decoder. Moreover, all the decoders in [13]–[15] require a large
sorter to select the surviving candidate codewords. Since the
sorter in the hardware implementation of SCL decoders has
a long and dominant critical path which is dependent on the
number of its inputs [10], increasing the number of PMs results
in a longer critical path and a lower operating frequency.
Based on the idea of list sphere decoding in [16], a
simplified SCL (SSCL) was proposed in [17] which identified
and avoided the redundant calculations in SCL. Therefore, it
required fewer number of time steps than SCL to decode
a polar code. The advantage of SSCL is that it not only
guarantees the error-correction performance preservation, but
also it uses the same sorter as in the conventional SCL
algorithm. To further increase the throughput and reduce the
latency of SSCL, the matrix reordering idea in [18] was used
to develop the SSCL-SPC decoder in [19]. While SSCL-SPC
uses the same sorter as in the conventional SCL, it provides
an exact reformulation for L = 2 and its approximations bring
negligible error-correction performance loss with respect to
SSCL.
While SSCL and SSCL-SPC are algorithms that can work
with any list size, they fail to address the redundant path
splitting associated with a specific list size. In this paper, we
first prove that there is a specific number of path splitting
required for decoding the constituent codes in SSCL and
SSCL-SPC for every list size to guarantee the error-correction
performance preservation. Any path splitting after that number
is redundant and any path splitting before that number cannot provably preserve the error-correction performance. Since
these decoders require fewer number of time steps than SSCL
and SSCL-SPC, we name them Fast-SSCL and Fast-SSCLSPC, respectively. We further show that in practical polar
codes, we can achieve similar error-correction performance to
SSCL and SSCL-SPC with even fewer number of path forks.
Therefore, we can optimize Fast-SSCL and Fast-SSCL-SPC
for speed. We propose hardware architectures to implement
both new algorithms: implementation results yield the highest
throughput in the state-of-the-art with comparable area occupation.
This paper is an extension to our work in [1] in which
the Fast-SSCL algorithm was proposed. Here, we propose the
Fast-SSCL-SPC algorithm and prove that its error-correction
performance is identical to that of SSCL-SPC. We further
propose speed-up techniques for Fast-SSCL and Fast-SSCLSPC which incur almost no error-correction performance loss.
Finally, we propose hardware architectures implementing the
aforementioned algorithms and show the effectiveness of the
proposed techniques by comparing our designs with state of
the art.
The remainder of this paper is organized as follows: Section II provides a background on polar codes and its decoding
algorithms. Section III introduces the proposed Fast-SSCL

α
β
l

α

l

β

û0

αr

û1

βr

û2

û3

û4

û5

û6

û7

Fig. 1: SC decoding on a binary tree for P(8, 4) and
{u0, u1, u2, u4 } ∈ F .

and Fast-SSCL-SPC algorithms and their speed optimization
technique. A decoder architecture is proposed in Section IV
and the implementation results are provided in Section V.
Finally, Section VI draws the main conclusions of the paper.

II. P RELIMINARIES
A. Polar Codes
A polar code of length N with K information bits is
represented by P(N, K) and can be constructed recursively
with two polar codes of length N/2. The encoding process
can be denoted as a matrix multiplication as x = uG N ,
where u = {u0, u1, . . . , u N −1 } is the sequence of input bits,
x = {x0, x1, . . . , x N −1 } is the sequence of coded bits, and
G N = B N G ⊗n is the generator matrix created by the product
of B N which is the bit-reversal permutation matrix, and G ⊗n
which is the n-th Kronecker product of the polarizing matrix
G = 11 01 .
The encoding process involves the determination of the K
bit-channels with the best channel characteristics and assigning
the information bits to them. The remaining N −K bit-channels
are set to a known value known at the decoder side. They are
thus called frozen bits with set F . Since the value of these bits
does not have an impact on the error-correction performance
of polar codes on a symmetric channel, they are usually set
to 0. The codeword x is then modulated and sent through the
channel. In this paper, we consider binary phase-shift keying
(BPSK) modulation which maps {0, 1} to {+1, −1}.

B. Successive-Cancellation Decoding
The SC decoding process can be represented as a binary tree
search as shown in Fig. 1 for P(8, 4). Thanks to the recursive
construction of polar codes, at each stage s of the tree, each
node can be interpreted as a polar code of length Ns = 2s .
Two kinds of messages are passed between the nodes, namely,
soft LLR values α = {α0, α1, . . . , α Ns −1 } which are passed
from parent to child nodes, and the hard bit estimates β =
{β0, β1, . . . , β Ns −1 } which are passed from child nodes to the
parent node.
The N2s elements of the left child node αl =
{α0l , α1l , . . . , αlN s }, and the right child node αr =
2

−1

3

{α0r , α1r , . . . , αrN s
2

−1

}, can be computed as [2]
α 



i

=2 arctanh tanh
tanh
2


αir =αi+ N s + 1 − 2βil αi ,
αil

α

i+ N2s

D. Simplified Successive-Cancellation List Decoding

,

2

(1)
(2)

2

whereas the Ns values of β are calculated by means of the left
child and right child node messages β l = {β0l , β1l , . . . , βlN s }
and β r = {β0r , β1r , . . . , βrN s
2

(
βi =

−1

2

} as [2]

βil ⊕ βir , if i < N2s ,
βr N s , otherwise,
i−

−1

(3)

2

where ⊕ is the bitwise XOR operation. At leaf nodes, the i-th
bit ûi can be estimated as
(
0, if i ∈ F or αi ≥ 0,
ûi =
(4)
1, otherwise.
Equation (1) can be reformulated in a more hardware-friendly
(HWF) version that has first been proposed in [3]:
αil = sgn(αi ) sgn(αi+ N s ) min(|αi |, |αi+ N s |).
2

(5)

2

C. Successive-Cancellation List Decoding
The error-correction performance of SC when applied to
codes with short to moderate length can be improved by the
use of SCL-based decoding. The SCL algorithm estimates a
bit considering both its possible values 0 and 1. At every estimation, the number of codeword candidates (paths) doubles: in
order to limit the increase in the complexity of this algorithm,
only a set of L codeword candidates is memorized at all times.
Thus, after every estimation, half of the paths are discarded.
To this purpose, a PM is associated to each path and updated
at every new estimation: it can be considered a cost function,
and the L paths with the lowest PMs are allowed to survive.
In the LLR-based SCL [10], the PM can be computed as
PMil =

i
Õ



ln 1 + e−(1−2û jl )α jl ,

(6)

j=0

where l is the path index and û jl is the estimate of bit j at
path l. A HWF version of Equation (6) has been proposed in
[10]:
PM−1l = 0,
(

PMi−1l +|αil |, if ûil , 12 1 − sgn αil ,
PMil =
PMi−1l ,
otherwise,
which can be rewritten as
i
1Õ
PMil =
sgn(α jl )α jl − (1 − 2û jl )α jl .
2 j=0

(7)

(8)

In case the hardware does not introduce bottlenecks and
both (2) and (5) can be computed in a single time step, the
number of time steps required to decode a code of length N
with K information bits in SCL is [10]
TSCL (N, K) = 2N + K − 2.

(9)

1) SSCL Decoding: The SSCL algorithm in [17] provides
efficient decoders for Rate-0, Rep, and Rate-1 nodes in SCL
without traversing the decoding tree while guaranteeing the
error-correction performance preservation. For example in
Fig. 1, the black circles represent Rate-1 nodes, the white circles represent Rate-0 nodes, and the white triangles represent
Rep nodes. The pruned decoding tree of SSCL for the example
in Fig. 1 is shown in Fig. 2a which consists of two Rep nodes
and a Rate-1 node.
Let us consider that the vectors αl and ηl = 1 − 2βl are
relative to the top of a node in the decoding tree. Rate-0 nodes
can be decoded as

NÕ
s −1




Exact,
(10a)
ln (1 + e−αil ) ,


 i=0

PM Ns −1l =
Ns −1



1 Õ


sgn αil αil − αil , HWF.
(10b)


 2 i=0

Rep nodes can be decoded as

NÕ
s −1




ln (1 + e−η N s −1l αil ) ,
Exact, (11a)


 i=0

PM Ns −1l =
Ns −1



1 Õ


sgn αil αil − η Ns −1l αil , HWF. (11b)


 2 i=0

where η Ns −1l represents the bit estimate of the information bit
in the Rep node. Finally, Rate-1 nodes can be decoded as

NÕ
s −1




ln (1 + e−ηil αil ) ,
Exact, (12a)


 i=0

PM Ns −1l =
Ns −1



1 Õ


sgn αil αil − ηil αil , HWF. (12b)


 2 i=0

It was shown in [19] that the time step requirements of
Rate-0, Rep, and Rate-1 nodes of length Ns in SSCL decoding
can be represented as
TSSCLRate-0 (Ns, 0) = 1,

(13)

TSSCLRep (Ns, 1) = 2,

(14)

TSSCLRate-1 (Ns, Ns ) = Ns .

(15)

While the SSCL algorithm reduces the number of required
time steps to decode Rate-1 nodes by almost a factor of three,
it fails to address the effect of list size on the maximum
number of required path forks. In Section III, we prove that
the number of required time steps to decode Rate-1 nodes
depends on the list size and that the new Fast-SSCL algorithm
is faster than both SCL and SSCL without incurring any errorcorrection performance degradation.
2) SSCL-SPC Decoding: In [19], a low-complexity approach was proposed to decode SPC nodes which resulted
in exact reformulations for L = 2 and its approximations for
other list sizes brought negligible error-correction performance
degradation. The pruned tree of SSCL-SPC for the same
example as in Fig. 1 is shown in Fig. 2b which consists of a
Rep node and a SPC node. The idea is to decode the frozen

4

III. FAST-SSCL D ECODING
Rep

Rep

Rep Rate-1

SPC

(b) SSCL-SPC

(a) SSCL

Fig. 2: (a) SSCL, and (b) SSCL-SPC decoding tree for P(8, 4)
and {u0, u1, u2, u4 } ∈ F .

bit in SPC nodes in the first step of the decoding process. In
order to do that, the PM calculations in the HWF formulation
were carried out by only finding the LLR value of the least
reliable bit and using the LLR values at the top of the polar
code tree in the SCL decoding algorithm for the rest of the
bits.
The least reliable bit in an SPC node of length Ns is found
as
imin = arg min(|αi |),
(16)
0≤i<Ns

and the parity of it is derived as

N
s −1 
Ê
1
γ=
(1 − sgn (αi )) .
2
i=0

(17)

To satisfy the even-parity constraint, γ is found for each path
based on (17). The PMs are then initialized as
(
PM−1 +|αimin |, if γ = 1,
PM0 =
(18)
PM−1 ,
otherwise.
In this way, the least reliable bit which corresponds to the
even-parity constraint is decoded first. For bits other than the
least reliable bit, the PM is updated as
(
PMi−1 +|αi | + (1 − 2γ)|αimin |, if ηi , sgn (αi ) ,
PMi =
PMi−1 ,
otherwise.
(19)
Finally, when all the bits are estimated, the least reliable bit
is set to preserve the even-parity constraint as
βimin =

N
s −1
Ê

βi .

(20)

i=0
i,imin

In [19], the time step requirements of SPC nodes of length
Ns in SSCL-SPC decoding was shown to be
TSSCL-SPCSPC (Ns, Ns − 1) = Ns + 1,

(21)

which consists of one time step for (18), Ns − 1 time steps for
(19), and one time step for (20).
The SSCL-SPC algorithm reduces the number of required
time steps to decode SPC nodes by almost a factor of three,
but as in the case of Rate-1 nodes, it fails to address the effect
of list size on the maximum number of required path forks. In
Section III, we prove that the number of required time steps to
decode SPC nodes depends on the list size and that the new
Fast-SSCL-SPC algorithm is faster than SSCL-SPC without
incurring any error-correction performance degradation.

In this section, we propose a fast decoding approach for
Rate-1 nodes and use it to develop Fast-SSCL. We further
propose a fast decoding approach for SPC nodes in SSCL-SPC
and use it to develop Fast-SSCL-SPC. To this end, we provide
the exact number of path forks in Rate-1 and SPC nodes
to guarantee error-correction performance preservation. Any
path splitting after that number is redundant and any path
splitting less than that number cannot guarantee the errorcorrection performance preservation. We further show that in
practical applications, this number can be reduced with almost
no error-correction performance loss. We use this phenomenon
to optimize Fast-SSCL and Fast-SSCL-SPC for speed.
A. Guaranteed Error-Correction Performance Preservation
The fast Rate-1 and SPC decoders can be summarized by
the following theorems.
Theorem 1. In SSCL decoding with list size L, the number
of path splitting in a Rate-1 node of length Ns required to get
the exact same results as the conventional SSCL decoder is
min (L − 1, Ns ) .

(22)

The proposed technique results in TFast-SSCLRate-1 (Ns, Ns ) =
min (L − 1, Ns ) which improves the required number of time
steps to decode Rate-1 nodes when L − 1 < Ns . Every bit after
the L −1-th can be obtained through hard decision on the LLR
as
(
0, if αil ≥ 0,
βil =
(23)
1, otherwise,
without the need for path splitting. On the other hand, in case
min (L − 1, Ns ) = Ns , all bits of the node need to be estimated
and the decoding automatically reverts to the process described
in [17]. The proof of the theorem is nevertheless valid for both
L − 1 < Ns and L − 1 ≥ Ns and is provided in [1].
The proposed theorem remains valid also for the HWF
formulation that can be written as
(

PMi−1l +|αil |, if ηil , sgn αil ,
PMil =
(24)
PMi−1l ,
otherwise.
The proof of the theorem in the HWF formulation case is also
presented in [1].
The result of Theorem 1 provides an exact number of path
forks in Rate-1 nodes for each list size in SCL decoding in
order to guarantee error-correction performance preservation.
The Rate-1 node decoder of [15] empirically states that
two path forks are required to preserve the error-correction
performance. The following remarks are the direct results of
Theorem 1.
Remark 1. The Rate-1 node decoder of [15] for L = 2 is
redundant.
Theorem 1 states that for a Rate-1 node of length Ns when
L = 2, the number of path splitting is min(L − 1, Ns ) = 1.
Therefore, there is no need to split the path after the least
reliable bit is estimated. [15] for L = 2 is thus redundant.

5

LLR values are more reliable and less likely to incur path
splitting. However, whether path splitting must occur or not
depends on the list size L. The proposed Rate-1 node decoder
is used in Fast-SSCL and Fast-SSCL-SPC algorithms and the
proposed SPC node decoder is used in Fast-SSCL-SPC, while
the decoders for Rate-0 and Rep nodes remain similar to those
used in SSCL [17] such that

100
10−1

10−3

BER

FER

10−2

10−4

10−6

10−5

10−7

10−9

10−8
3

4
Eb /N0

3

5

4

5

Eb /N0 [dB]

[dB]
[17]

[15]

Fig. 3: FER and BER performance comparison of SSCL [17]
and the empirical method of [15] for P(1024, 860) when L =
128. The CRC length is 32.
Remark 2. The Rate-1 node decoder of [15] falls short in
preserving the error-correction performance for higher rates
and larger list sizes.

TFast-SSCLRate-0 (Ns, 0) = TFast-SSCL-SPCRate-0 (Ns, 0) = 1,

(26)

TFast-SSCLRep (Ns, 1) = TFast-SSCL-SPCRep (Ns, 1) = 2.

(27)

It should be noted that the number of path forks is directly
related to the number of time steps required in the decoding
process [10]. Therefore, when L < Ns , the time step requirement of SPC nodes based on Theorem 2 is two time steps
more than the time step requirement of Rate-1 nodes as in
Theorem 1. However, if SPC nodes are not taken into account
as in Fast-SSCL decoding, the polar code tree needs to be
traversed to find Rep nodes and Rate-1 nodes as shown in
Fig. 2a. For a SPC node of length Ns , this will result in
additional time step requirements as
TFast-SSCLSPC (Ns, Ns − 1) =2 log2 Ns − 2 + TFast-SSCLRep (2, 1)
+

log2Õ
Ns −1

TFast-SSCLRate-1 (2i, 2i ).

i=1

For codes of higher rates, the number of Rate-1 nodes of
larger length increases [19]. Therefore, when the list size is
also large, min(L − 1, Ns )  2. The gap between the empirical
method of [15] and the result of Theorem 1 can introduce
significant error-correction performance loss. Fig. 3 provides
the frame error rate (FER) and bit error rate (BER) of decoding
a P(1024, 860) code with SSCL of [17] and the empirical
method of [15] when the list size is 128. It can be seen that
the error-correction performance loss reaches 0.25dB at FER
of 10−5 . In Section III-B, we show that the number of path
forks can be tuned for each list size to find a good tradeoff between the error-correction performance and the speed of
decoding.
Theorem 2. In SSCL-SPC decoding with list size L, the
number of path forks in a SPC node of length Ns required
to get the exact same results as the conventional SSCL-SPC
decoder is
min (L, Ns ) .
(25)
Following the time step calculation of SSCLSPC, the proposed technique in Theorem 2 results in
TFast-SSCL-SPCSPC (Ns, Ns − 1) = min (L, Ns ) + 1 which improves
the required number of time steps to decode SPC nodes when
L < Ns . Every bit after the L-th can be obtained through hard
decision on the LLR as in (23) without the need for path
splitting. In case min (L, Ns ) = Ns , the paths need to be split
for all bits of the node and the decoding automatically reverts
to the process described in [19]. The proof of the theorem is
nevertheless valid for both L < Ns and L ≥ Ns . We defer the
proof to Appendix A.
The effectiveness of hard decision decoding after the
min(L − 1, Ns )-th bit in Rate-1 nodes and the min(L, Ns )-th bit
in SPC nodes is due to the fact that the bits with high absolute

For example, for a SPC node of length 64, Fast-SSCL with
L = 4 results in TFast-SSCLSPC (64, 63) = 26, while Fast-SSCLSPC with L = 4 results in TFast-SSCL-SPCSPC (64, 63) = 5. Table I
summarizes the number of time steps required to decode each
node with different decoding algorithms.
In practical polar codes, there are many instances where
L − 1 < Ns for Rate-1 nodes and using the Fast-SSCL
algorithm can significantly reduce the number of required
decoding time steps with respect to SSCL. Similarly, there are
many instances where L < Ns for SPC nodes and using the
Fast-SSCL-SPC algorithm can significantly reduce the number
of required decoding time steps with respect to SSCL-SPC.
Fig. 4 shows the savings in time step requirements of a polar
code with three different rates. It should be noted that as the
rate increases, the number of Rate-1 and SPC nodes increases.
This consequently results in more savings by going from SSCL
(SSCL-SPC) to Fast-SSCL (Fast-SSCL-SPC).
B. Speed Optimization
The analysis in Section III-A provides exact reformulations
of SSCL and SSCL-SPC decoders without introducing any
error-correction performance loss. However, in practical polar
codes, there are fewer required path forks for Fast-SSCL
and Fast-SSCL-SPC in order to match the error-correction
performance of SSCL and SSCL-SPC, respectively.
Without loss of generality, let us consider L − 1 < Ns for
Rate-1 nodes and L < Ns for SPC nodes such that FastSSCL and Fast-SSCL-SPC result in higher decoding speeds
than SSCL and SSCL-SPC, respectively. Let us now consider
SRate-1 be the number of path forks in a Rate-1 node of
length Ns , and SSPC be the number of path forks in a SPC
node of length Ns where SRate-1 ≤ L − 1 and SSPC ≤ L. It

6

TABLE I: Time-Step Requirements of Decoding Different Nodes of Length Ns with List Size L.
Algorithm
SCL
SSCL
SSCL-SPC
Fast-SSCL
Fast-SSCL-SPC

Rate-0

Rep

Rate-1

2Ns − 2
1
1
1
1

2Ns − 1
2
2
2
2

3Ns − 2
Ns
Ns
min(L − 1, Ns )
min(L − 1, Ns )

SSCL-SPC

3Ns − 3
Ns + 2 log2 Ns − 2
Ns + 1
Ílog N −1
2 log2 Ns + i=12 s min(L − 1,
min(L, Ns ) + 1

Fast-SSCL

1200

1000

1000

1000

800

800

800

Time steps

1200

600

600
400

400

200

200

200

(a) P(1024, 256)

0
21 22 23 24 25 26 27 28 29
L
(b) P(1024, 512)

)

600

400

0
21 22 23 24 25 26 27 28 29
L

Ns
2i

Fast-SSCL-SPC

1200

Time steps

Time steps

SSCL

SPC

0
21 22 23 24 25 26 27 28 29
L
(c) P(1024, 768)

Fig. 4: Time-step requirements of SSCL, SSCL-SPC, Fast-SSCL, and Fast-SSCL-SPC decoding of (a) P(1024, 256), (b)
P(1024, 512), and (c) P(1024, 768).
should be noted that SRate-1 = L − 1 and SSPC = L result
in optimal number of path forks as presented in Theorem 1
and Theorem 2, respectively. The smaller the values of SRate-1
and SSPC , the faster the decoders of Fast-SSCL and FastSSCL-SPC. Similar to (22) and (25), the new number of
required path forks for Rate-1 and SPC nodes can be stated
as min(SRate-1, Ns ) and min(SSPC, Ns ), respectively.

values of SRate-1 = 3 and SSPC = 4 as shown in Fig. 8. As
illustrated in Fig. 9 for L = 8, the selection of SRate-1 = 2 and
SSPC = 4 provides similar FER and BER performance as the
optimal values of SRate-1 = 7 and SSPC = 8.

The definition of the parameters SRate-1 and SSPC provides a
trade-off between error-correction performance and speed of
Fast-SSCL and Fast-SSCL-SPC. Let us consider CRC-aided
Fast-SSCL decoding of P(1024, 512) with CRC length 16.
Fig. 5 shows that for L = 2, choosing SRate-1 = 0 results
in significant FER and BER error-correction performance
degradation. Therefore, when L = 2, the optimal value of
SRate-1 = 1 is used for Fast-SSCL. The optimal value of SRate-1
for L = 4 is 3. However, as shown in Fig. 6, SRate-1 = 1
results in almost the same FER and BER performance as the
optimal value of SRate-1 = 3. For L = 8, the selection of
SRate-1 = 1 results in ∼0.1 dB of error-correction performance
degradation at FER = 10−5 as shown in Fig. 7. However,
selecting SRate-1 = 2 removes the error-correction performance
gap to the optimal value of SRate-1 = 7. In the case of CRCaided Fast-SSCL-SPC decoding of P(1024, 512) with 16 bits
of CRC, selecting SRate-1 = 1 and SSPC = 3 for L = 4 results
in almost the same FER and BER performance as the optimal

To evaluate the impact of the proposed techniques on a
practical case, a SCL-based polar code decoder architecture
implementing Fast-SSCL and Fast-SSCL-SPC has been designed. Its basic structure is inspired to the decoders presented
in [9], [19], and it is portrayed in Fig. 10. The decoding flow
follows the one portrayed in Section II-C for a list size L. This
means that the majority of the datapath and of the memory
are replicated L times, and work concurrently on different
candidate codewords and the associated LLR values.
Starting from the tree root, the tree is descended by recursively computing (5) and (2) on left and right branches
respectively at each tree stage s, with a left-first rule. The
computations are performed by L sets of P processing elements (PEs), where each set can be considered a standalone
SC decoder, and P is a power of 2. In case 2s > 2P, (5) and (2)
require 2s /(2P) time steps to be completed, while otherwise
needing a single time step. The updated LLR values are stored
in dedicated memories.

IV. D ECODER A RCHITECTURE

7

100

100
10−1

10−1

10−1

10−2

10−1
10−2

10−3

10−3

BER

10−2

FER

BER

FER

10−2

10−3
10−4

10−3

10−4

1

2
Eb /N0

3

10−5

10−5

10−6

10−6

10−5

10−4

1

[dB]
SRate-1 = 0

2
Eb /N0

3

10−4

10−7
1

[dB]

2
Eb /N0

1

3

SRate-1 = 1

SRate-1 = 0
SRate-1 = 2

Fig. 5: FER and BER performance comparison of Fast-SSCL
decoding of P(1024, 512) for L = 2 and different values of
SRate-1 . The CRC length is 16.

2

3

Eb /N0 [dB]

[dB]

SRate-1 = 1
SRate-1 = 7

Fig. 7: FER and BER performance comparison of Fast-SSCL
decoding of P(1024, 512) for L = 8 and different values of
SRate-1 . The CRC length is 16.

100
10−1

100

10−2

10−1

10−1

10−1

10−2
10−2

BER

10−3

10−3

FER

FER

BER

10−2

10−4

10−3
10−4

10−5

10−5

10−6

10−4

10−4
1

2

3

1

Eb /N0 [dB]
SRate-1 = 0

2

3

Eb /N0 [dB]
SRate-1 = 1

SRate-1 = 3

Fig. 6: FER and BER performance comparison of Fast-SSCL
decoding of P(1024, 512) for L = 4 and different values of
SRate-1 . The CRC length is 16.

The internal structure of PEs is shown in Fig. 11. Each
PE receives as input two LLR values, outputting one. The
computations for both (5) and (2) are performed concurrently,
and the output is selected according to is , that represents the
s-th bit of the index i, where 0 ≤ i < N. The index i is
represented with smax = log2 N bits, and identifies the next
leaf node to be estimated, and can be composed by observing
the path from the root node to the leaf node. From stage smax
down to 0, for every left branch we set the corresponding bit
of i to 0, and to 1 for every right branch.
When a leaf node is reached, the controller checks Node
Sequence, identifying the leaf node as an information bit or a
frozen bit. In case of a frozen bit, the paths are not split, and
the bit is estimated only as 0. All the L path memories are
updated with the same bit value, as are the LLR memories and

10−3

10−5

10−5

10−6
1

2
Eb /N0

3

[dB]

SRate-1 = 1, SSPC = 2
SRate-1 = 3, SSPC = 4

1

2

3

Eb /N0 [dB]
SRate-1 = 1, SSPC = 3

Fig. 8: FER and BER performance comparison of Fast-SSCLSPC decoding of P(1024, 512) for L = 4 and different values
of SRate-1 and SSPC . The CRC length is 16.

the β memories. On the other hand, in case of an information
bit, both 0 and 1 are considered. The paths are duplicated
and the PMs are calculated for the 2L candidates according to
(8). They are subsequently filtered through the sorter module,
designed for minimum latency. Every PM is compared to every
other in parallel: dedicated control logic uses the resulting
signals to return the values of the PMs of the surviving paths
and the newly estimated bits they are associated with. The
latter are used to update the LLR memories, the β memories
and the path memories, while also being sent to the CRC
calculation module to update the remainder.
All memories in the decoder are implemented as registers:
this allows the LLR and β values to be read, updated by the

8

is

100
10−1

αi

10−1

αil

10−2

αiout

10−3
10−4

10−6

10−6

10−7
1

2
Eb /N0

3

Fig. 11: PE architecture.
LLR Memories
1

2
Eb /N0

[dB]

SRate-1
SRate-1
SRate-1
SRate-1

= 1,
= 1,
= 2,
= 7,

SSPC
SSPC
SSPC
SSPC

=2
=4
=3
=8

3

[dB]

SRate-1 = 1, SSPC = 3
SRate-1 = 2, SSPC = 2
SRate-1 = 2, SSPC = 4

High
..
Stage .
Memory

N

QLLR

Path . . .
Memory

Node Sequence

QLLR

.
β
..
Memory

PM . . .
Memory

L

L
1

Channel
Memory

L

L
QLLR × P

Fig. 9: FER and BER performance comparison of Fast-SSCLSPC decoding of P(1024, 512) for L = 8 and different values
of SRate-1 and SSPC . The CRC length is 16.

Controller

Low
..
Stage .
Memory

N

10−5

2

1

10−5

2P − 2

10−4

αir

αi+ N s

N −1

10−3

N/P − 2

BER

FER

10−2

1

L
QPM

CRC Unit
Fig. 12: Memory architecture.

PM Computation
and Sorting

SC Decoders

Memories

PE
..
.

···

PE
1

···

PE
..
.

1
..
.

PE

P

L

Channel LLRs
Fig. 10: Decoder architecture.

PEs, and written back in a single clock cycle. At the same time,
the paths are either updated, or split and updated (depending
on the constituent code), and the new PMs computed. In the
following clock cycle, in case the paths were split, the PMs
are sorted, paths are discarded and the CRC value updated.
In case paths were not split, the PMs are not sorted, and the
CRC update occurs in parallel with the following operation.
A. Memory Structure
The decoding flow described above relies on a number of
memories that are shown in Fig. 12. The channel memory
stores the N LLR values received from the channel at the
beginning of the decoding process. Each LLR value is quantized with QLLR bits, and represented with sign and magnitude.
The high and low stage memories store the intermediate α

computed in (5) and (2). The high stage memory is used
to store LLR values related to stages with nodes of size
greater than P. The number of PEs determines the number
of concurrent (5) or (2) that can be performed: for a node
in stage s, where 2s > 2P, a total of 2s /(2P) time steps
are needed to descend to the lower
level. The depth of
Í maxtree
−1
the high stage memory is thus sj=log
2 j /P = N/P − 2,
2 P+1
while its width is QLLR × P. On the other hand, the low stage
memory stores the LLR values for stages where 2s ≤ 2P: the
width of this memory is QLLR , while its depth is defined as
Ílog2 P−1
P/2 j = 2P − 2. Both high and low stage memory
j=0
words are reused by nodes belonging to the same stage s,
since once a subtree has been completely decoded, its LLR
values are not needed anymore. While high and low stage
memories are different for each path, the channel LLR values
are shared among the L datapaths. Table II summarizes the
memory read and write accesses for the aforementioned LLR
memories. When 2s = 2P, 2P LLR values are read from the
high stage memory, and the P resulting LLR values are written
in the low stage memory. The channel memory is read at smax
only.
Each of the L candidate codewords is stored in one of the
N-bit path memories, updated after every bit estimation. The β
memories hold the β values for each stage from 0 to smax − 1,
for a total of N − 1 bits each. Each time a bit is estimated,
all the β values it contributes to are concurrently updated.
When the decoding of the left half of the SC decoding tree has

9

TABLE II: LLR Memory Access.

TABLE IV: Node Sequence Input Information for Fast-SSCL
and Fast-SSCL-SPC.

Stage

READ

WRITE

s = smax
log2 P + 1 < s < smax
s = log2 P + 1
s < log2 P + 1

Channel
High Stage
High Stage
Low Stage

High Stage
High Stage
Low Stage
Low Stage

Node Type
RATE0
RATE1-1
RATE1-2
REP1
REP2
DESCEND
LEAF

TABLE III: Node Sequence Input Information for SSCL and
SSCL-SPC.
Node Type
RATE0
RATE1
REP1
REP2
DESCEND
LEAF
SPC1
SPC2
SPC3

Node Stage

Node Size

Frozen

s
s
s
s
Next Node
0

2s
2s
s
2 −1
1
Next Node
1

1
0
1
0
Next Node
0/1

s
s
s

1
2s − 1
2s

1
0
0

SPC1
SPC2-1
SPC2-2
SPC3

•

been completed, the β memories are reused for the right half.
Finally, the PM memories store the L PM values computed in
(8).
•

B. Special Nodes
The decoding flow and memory structure described before
implement the standard SCL decoding algorithm. The SSCL,
SSCL-SPC and the proposed Fast-SSCL and Fast-SSCL-SPC
algorithms demand modifications in the datapath to accommodate the simplified computations for Rate-0, Rate-1, Rep and
SPC nodes.
As with standard SCL, the pattern of frozen and information
bits is known a priori given a polar code structure, the same
can be said for special nodes. In the modified architecture,
the Node Sequence input in the controller (see Fig. 10) is not
limited to the frozen/information bit pattern, but it includes
the type of encountered nodes, their size and the tree stage in
which they are encountered. Table III summarizes the content
of Node Sequence depending on the type of node for SSCL
and SSCL-SPC, while in case of Fast-SSCL and Fast-SSCLSPC Node Sequence is detailed in Table IV. The node stage
allows the decoder to stop the tree exploration at the right level,
and the node type identifies the operations to be performed.
Each of the four node types is represented with one or more
decoding phases, each of which involves a certain number of
codeword bits, identified by the node size parameter. Finally,
the frozen bit parameter identifies a bit or set of bits as frozen
or not. To limit the decoder complexity, the maximum node
stage for special nodes is limited to s = log2 P, thus the
maximum node size is P. If the code structure identifies special
nodes with node size larger than P, they are considered as
composed by a set of P-size special nodes.
•

Rate-0 nodes are identified in the Node Sequence with a
single decoding phase. No path splitting occurs, and all

•

•

•

Node Stage

Node Size

Frozen

s
s
s
s
s
Next Node
0

2s
min(SRate-1, 2 s )
2 s − min(SRate-1, 2 s )
2s − 1
1
Next Node
1

1
0
0
1
0
Next Node
0/1

s
s
s
s

1
min(SSPC, 2 s )
2 s − min(SSPC, 2 s ) − 1
2s

1
0
0
0

the 2s node bits are set to 0. The PM update requires a
single time step, as discussed in [19].
Rate-1 nodes are composed of a single phase in both
SSCL and SSCL-SPC, in which paths are split 2s times.
In case of Fast-SSCL and Fast-SSCL-SPC, each Rate-1
is divided into two phases. The first takes care of the
min(SRate-1, 2s ) path forks, requiring as many time steps,
while the second sets the remaining 2s − min(SRate-1, 2s )
bits according to (23) and updates the PM according to
(24). This second phase takes a single time step.
Rep nodes are identified by two phases in the Node
Sequence, the first of which takes care of the 2s − 1
frozen bits similarly as Rate-0 nodes do, and the second
estimates the single information bit. Each of these two
phases lasts a single time step.
SPC nodes are split in three phases in the original SSCLSPC formulation. The first phase takes care of the frozen
bit, and computes both (16) and (17), initializing the PM
as (18) in a time step. The extraction of the least reliable
bit in (16) is performed through a comparison tree that
carries over both the index and the value of the LLR.
The second phase estimates the 2s − 1 information bits,
splitting the path as many times in as many time steps.
During this phase, each time a bit is estimated, it is
XORed with the previous β values: this operation is
useful to compute (20). The update of βimin is finally
performed in the third phase, that takes a single time step.
Moving to Fast-SSCL-SPC, the second SPC phase is split
in two, similarly to what happens to the Rate-1 node.
Descend is a non-existing node type that is inserted for
one clock cycle in Node Sequence for control purposes
after every special node. The node size and stage associated with this label are those of the following node. The
Descend node type is used by the controller module.
Leaf nodes identify all nodes that can be found at s = 0,
for which the standard SCL algorithm applies.

The decoding of special nodes requires a few major changes
in the decoder architecture.
•

Path Memory: each path memory is an array of N
registers, granting concurrent access to all bits with a 1bit granularity. In SCL, the path update is based on the

10

0
û
sgn(α)
0
û
0
û
sgn(α)
βimin
û

RATE0
RATE1-1
RATE1-2
REP1
REP2
SPC1
SPC2-1
SPC2-2
SPC3
LEAF

Data in

•

Path
Memory

Node Type
i → i + 2s
i
i → i + 2 s − SRate-1
s
i →i+2 −1
i
i
i
s
i → i + 2 − SSPC − 1
imin
i

RATE0
RATE1-1
RATE1-2
REP1
REP2
SPC1
SPC2-1
SPC2-2
SPC3
LEAF

Address

Write Enable

Fig. 13: Path memory access architecture for Fast-SSCL-SPC.

•

combination of a write enable signal, the codeword bit
index i that acts as a memory address, and the value of
the estimated bit after the PMs have been sorted and the
surviving paths identified. Fig. 13 shows the path memory
access architecture for Fast-SSCL-SPC. Unlike SCL, the
path memory is not always updated with the estimated
bit û. Thus, the SCL datapath is bypassed according to
the node type. When Node Sequence identifies RATE0,
REP1 and SPC1 nodes that consider frozen bits, the path
memory is updated with 0 values. The estimated bit û is
chosen as input for RATE1-1, REP2, SPC2-2 and LEAF
nodes, where the path is split. RATE1-2 and SPC2-2
nodes estimate the bits through hard decision on the LLR
values, while in the SPC3 case the update considers the
result of (20). At the same time. whenever the estimated
bits are more than one, the corresponding bits in the path
memory must be concurrently updated. Thus, the address
becomes a range of addresses for RATE0, RATE1-2,
REP1 and SPC2-2.
β Memory: the update of this memory depends on the
value of the estimated bit. In order to limit the latency
cost of these computations, concurrently to the estimation
of û, the updated values of all the bits of the β memory
are computed assuming both û = 0 and û = 1. The actual
value of û is used as a selection signal to decide on
the two alternatives. The β memory in SCL, unlike the
path memory, already foresees the concurrent update of
multiple entries that are selected based on the bit index
i. Given an estimated leaf node, the β values of all the
stages that it affects are updated: in fact, since as shown
in (3) the update of β values is at most a series of XORs,
it is possible to distribute this operation in time. The same
can be said of multi-bit (3) updates. To implement FastSSCL-SPC, the β update selection logic must be modified
to foresee the special nodes, similar to that portrayed in

•

•

Fig. 13 for the path memory. For RATE0, REP1, and
SPC1, the û = 0 update is always selected. RATE1-1,
REP2, SPC2-1 and LEAF nodes maintain the standard
SCL selection based on the actual value of û. The update
for SPC3 case is based on βimin . For RATE1-2 and SPC12, the selection is based on the XORed sign bits of the
LLR values read from the memory.
PM Calculation: this operation is performed, in the
original SCL architecture and for leaf nodes in general
according to (8). The paths and associated PMs are split
and sorted every time an information bit is estimated,
while PMs are updated without sorting when frozen bits
are encountered. While the sorting architecture remains
the same, the implementation of the proposed algorithm
requires a different PM update structure for each special
node. Unlike with leaf nodes, the LLR values needed
for the PM update in special nodes are not the output
of PEs, and are read directly from the LLR memories.
Additional bypass logic is thus needed. For RATE0 and
REP1, (10b) and (11b) require a summation over up to P
values, while SPC1 nodes need to perform the minimum
α search (16): these operations are tackled through adder
and comparator trees. RATE1-1, REP2 and SPC2-1 PM
updates are handled similarly to the leaf node case, since
a single bit at a time is being estimated. RATE1-2, SPC22 and SPC3 do not require any PM to be updated.
CRC Calculation: the standard SCL architecture foresees
the estimation of a single bit at a time. Thus, the CRC is
computed sequentially. However, Rate-0 and Rep nodes
in SSCL and SSCL-SPC estimate up to P and P − 1
bits concurrently. Thus, for the CRC operation not to
become a latency bottleneck, the CRC calculation must be
parallelized by updating the remainder. Following the idea
presented in [20], it is possible to allow for variable input
sizes with a high degree of resource sharing and limited
overall complexity. The circuit is further simplified by the
fact that both Rate-0 and Rep nodes guarantee that the
estimated bit values are all 0. Fig. 14 shows the modified
CRC calculation module in case P = 64, where NCRC
represents the number of concurrently estimated bits: the
estimated bit can be different from 0 only in case of leaf
nodes and s = 1 Rep nodes, for which a single bit is
estimated in any case.
The Fast-SSCL and Fast-SSCL-SPC architectures follow
the same idea, but require additional logic. RATE1-2 and
SPC2-2 nodes introduce new degrees of parallelism, as
up to P − SRate-1 and P − SSPC bits are updated at the
same time. Moreover, it is not possible to assume that
these bits are 0 as with RATE0 and REP1. The value of
the estimated bit must be taken into account, leading to
increased complexity.
Controller: this module in the SCL architecture is tasked
with the generation of memory write enables, the update
of the codeword bit index i and the stage tracker s,
along with the LLR memory selection signals according
to Table II and path enable and duplication signals. It
implements a finite state machine that identifies the status
of the decoding process. The introduction of special nodes

11

Node Type
Node Size
NCRC = 64
NCRC = 63
NCRC = 32
NCRC = 31
NCRC = 16
Remainder

NCRC = 15
NCRC = 8
NCRC = 7
NCRC = 4
NCRC = 3
NCRC = 2

Estimated
bit

NCRC = 1

Fig. 14: CRC architecture for SSCL and SSCL-SPC.

demands that most of the control signal generation logic
is modified. Of particular importance is the fact that, in
the SCL architecture, the update of i is bound to having
reached a leaf node, i.e. s = 0. In Fast-SSCL-SPC, it is
instead linked to s being equal to the special node stage.
The index i is moreover incremented of the amount of
bits estimated in a single time step, depending on the
type of node. Memory write enables are also bound to
having reached the special node stage, and not only to
s = 0.
V. R ESULTS
A. Hardware Implementation
The architecture designed in Section IV has been described
in the VHDL language and synthesized in TSMC 65 nm
CMOS technology. Implementation results are provided in
Table V for different decoders: along with the Fast-SSCL and
Fast-SSCL-SPC described in this work, the SCL, SSCL and
SSCL-SPC decoders proposed in [19] are presented as well.
Each decoder has been synthesized with three list sizes (L =
2, 4, 8), while the Fast-SSCL and Fast-SSCL-SPC architectures
have been synthesized for considering different combinations
of SRate-1 and SSPC , as portrayed in Section III-B. Quantization
values are the same used in [19], i.e. 6 bits for LLR values
and 8 bits for PMs, with two fractional bits each. All memory
elements have been implemented through registers and the
area results include both net area and cell area. The reported
throughput is coded.
All Fast-SSCL and Fast-SSCL-SPC, regardless of the value
of SRate-1 and SSPC , show a substantial increase in area oc-

cupation with respect to SSCL and SSCL-SPC. The main
contributing factors to the additional area overhead are three:
• In SSCL and SSCL-SPC, the CRC computation needs to
be parallelized, since in Rep and Rate-0 nodes multiple
bits are updated at the same time. However, the bit
value is known at design time, since they are frozen
bits. This, along with the fact that 0 is neutral in the
XOR operations required by CRC calculation, limits the
required additional area overhead. On the contrary, in
Fast-SSCL and Fast-SSCL-SPC, Rate-1 and SPC nodes
update multiple bits within the same time step (SPC2-2
and RATE1-2 stages). In these cases, however, they are
information bits, whose values cannot be known at design
time: the resulting parallel CRC tree is substantially wider
and deeper than the ones for Rate-0 and Rep nodes.
Moreover, with increasing number of CRC trees, the
selection logic becomes more cumbersome.
• A similar situation is encountered for the β memory
update signal. As described in the previous section, the
β memory update values are computed assuming both
estimated values, and the actual value of û is used as a
selection signal. In SSCL and SSCL-SPC the multiplebit update does not constitute a problem since all the
estimated bits are 0 and the β memory content does not
need to be changed. On the contrary, in Fast-SSCL and
Fast-SSCL-SPC, the value of the estimated information
bits might change the content of the β memory. Moreover,
since β is computed as (3), the update of β bits depends
on previous bits as well as the newly estimated ones.
Thus, an XOR tree is necessary to compute the right
selection signal for every information bit estimated in
SPC2-2 and RATE1-2 stages.
• The aforementioned modifications considerably lengthen
the system critical path. In case of large code length, small
list size, or large P, the critical path starts in the controller
module, in particular in the high stage memory addressing
logic, goes through the multiplexing structure that routes
LLR values to the PEs, and ends after the PM update. In
case of large list sizes or short code length, the critical
path passes through the PM sorting and path selection
logic, and through the parallel CRC computation. Thus,
pipeline registers have been inserted to lower the impact
of critical path, at the cost of additional area occupation.
Fast-SSCL and Fast-SSCL-SPC implementations show consistent throughput improvements with respect to previously
proposed architectures. The gain is lower than what is shown
to be theoretically achievable in Fig. 4. This is due to the
aforementioned pipeline stages, that increase the number of
steps needed to complete the decoding of component codes.
B. Comparison with Previous Works
The Fast-SSCL-SPC hardware implementation presented in
this paper for P(1024, 512) and P = 64 is compared with
the state-of-the-art architectures in [11]–[14], [19] and the
results are provided in Table VI. The architectures presented
in [12]–[14] were synthesized based on 90 nm technology: for
a fair comparison, their results have been converted to 65 nm

12

TABLE V: TSMC 65 nm Implementation Results for P(1024, 512) and P = 64.
Implementation

L

SRate-1

SSPC

Area
[mm2 ]

Frequency
[MHz]

SCL

2
4
8

7
7
7

7
7
7

0.599
0.998
2.686

1031
961
722

389
363
272

SSCL

2
4
8

7
7
7

7
7
7

0.643
1.192
2.958

1031
961
722

1108
1033
776

SSCL-SPC

2
4
8

7
7
7

7
7
7

0.684
1.223
3.110

1031
961
722

1229
1146
861

Fast-SSCL

2
4
4
8
8

1
1
3
2
7

7
7
7
7
7

0.871
1.536
1.511
3.622
3.588

885
840
840
722
722

1579
1499
1446
1053
827

Fast-SSCL-SPC

2
4
4
8
8

1
1
3
2
7

2
3
4
4
8

1.048
1.822
1.797
3.975
3.902

885
840
840
722
722

1861
1608
1338
1198
959

technology using a factor of 90/65 for the frequency and a
factor of (65/90)2 for the area. The synthesis results in [11]
were carried out in 65 nm technology but reported in 90 nm
technology. Therefore, a reverse conversion was applied to
convert the results back to 65 nm technology.
The architecture in this paper shows 72% higher throughput
and 42% lower latency with respect to the multibit decision
SCL decoder architecture of [11] for L = 4. However, the
area occupation of [11] is smaller, leading to a higher area
efficiency than the design in this paper.
The symbol-decision SCL decoder architecture of [12]
shows lower area occupation than the design in this paper
for L = 4 but it comes at the cost of lower throughput and
higher latency. Our decoder architecture achieves 192% higher
throughput and 66% lower latency than [12] which resulted in
17% higher area efficiency.
The high throughput SCL decoder architecture of [13] for
L = 2 requires lower area occupation than our design but it
comes at the expense of lower throughput and higher latency.
Moreover, the design in [13] relies on parameters that need
to be tuned for each code, and it is shown in [13] that a
change of code can result in more than 0.2 dB error-correction
performance loss. For L = 4, our decoder not only achieves
higher throughput and lower latency than [13], but also it
occupies a smaller area. This in turn yields a 12% increase
in the area efficiency in comparison with [13].
The multimode SCL decoder in [14] relies on a higher
number of PEs than our design: nevertheless, it yields lower
throughput and higher latency than the architecture proposed
in this paper for L = 4. It should be noted that [14] is based on
the design presented in [13], whose code-specific parameters
may lead to substantial error-correction performance degradation. On the contrary, the design in this paper is targeted for

Throughput
[Mb/s]

speed and flexibility and can be used to decode any polar code
of any length.
Compared to our previous work [19], that has the same
degree of flexibility of the proposed design, this decoder
achieves 51% higher throughput and 34% lower latency for
L = 2, and 40% higher throughput and 28% lower latency for
L = 4. However, the higher area occupation of the new design
yields lower area efficiencies than [19] for L = {2, 4}. For
L = 8, the proposed design has 39% higher throughput and
29% lower latency than [19], which results in 9% increase in
area efficiency. The reason is that for L = 8, the sorter is quite
large and falls on the critical path. Consequently, the maximum
achievable frequency for the proposed design is limited by the
sorter and not by Rate-1 and SPC nodes as opposed to the
L = {2, 4} case. This results in the same maximum achievable
frequency for both designs, hence, higher throughput and area
efficiency.
Fig. 15 plots the area occupation against the decoding
latency for all the decoders considered in Table VI. For each
value of L, the design proposed in this work have the shortest
latency, shown by their leftmost position on the graph.
VI. C ONCLUSION
In this work, we have proven that the list size in polar
decoders sets a limit to the useful number of path forks in
Rate-1 and SPC nodes. We thus propose Fast-SSCL and FastSSCL-SPC polar code decoding algorithms that, depending
on L and the number of performed path forks, can reduce
the number of required time steps of more than 75% at no
error-correction performance cost. Hardware architectures for
the proposed algorithms have been described and implemented
in CMOS 65 nm technology. They have a very high degree
of flexibility and can decode any polar code, regardless of its

13

TABLE VI: Comparison with State-of-the-Art Decoders.
This work

[11]

[12]†

[14]†

[19]

L
P

2
64

4
64

8
64

4
64

4
64

2
64

4
64

4
256

2
64

4
64

8
64

Area [mm2 ]
Frequency [MHz]
Throughput [Mb/s]
Latency [µs]
Area Efficiency [Mb/s/mm2 ]

1.048
885
1861
0.55
1776

1.822
840
1608
0.64
883

3.975
722
1198
0.85
301

0.62
498
935
1.10
1508

0.73
692
551
1.86
755

1.03
586
1844
0.57
1790

2.00
558
1578
0.66
789

0.99
566
1515
0.69
1530

0.68
1031
1229
0.83
1807

1.22
961
1146
0.89
939

3.11
722
861
1.19
277

† The

results are originally based on TSMC 90 nm technology and are scaled to TSMC 65 nm technology.

paths min(L, Ns ) times while guaranteeing the same results as
in SSCL-SPC. Theorem 2 is consequently proven.


L=2
L=4
L=8

This work

100.6

[19]

R EFERENCES

100.4

Area [mm2 ]

[13]†

[13]

100.2

This work
[19]
This work

100

[13]

[14]
[12]

[19]
[11]

10−0.2
10−0.2

100

100.2

Latency [µs]

Fig. 15: Comparison with state-of-the-art decoders.

rate. The proposed decoder is the fastest SCL-based decoder
in literature: sized for N = 1024 and L = 2, it yields a 1.861
Gb/s throughput with an area occupation of 1.048 mm2 . The
same design, sized for L = 4 and L = 8, leads to throughputs
of 1.608 Gb/s and 1.198 Gb/s, and areas of 1.822 mm2 and
3.975 mm2 , respectively.
A PPENDIX A
P ROOF OF T HEOREM 2
Proof. In order to prove Theorem 2, we note that the first
step is to initialize the PMs based on (18). Therefore, the
least reliable bit needs to be estimated first. For the bits other
than the least reliable bit, the PMs are updated based on (19).
However, the term (1 − 2γ)|αimin | is constant for all the bit
estimations in the same path. Therefore, we can define a new
set of Ns − 1 LLR values as
αim = αi + sgn(αi )(1 − 2γ)|αimin |,

(28)

for i , imin and 0 ≤ im < Ns − 1, which results in
|αim | = |αi | + (1 − 2γ)|αimin |.

(29)

The problem is now reduced to a Rate-1 node of length Ns −
1 which, with the result of Theorem 1, can be decoded by
considering only min(L − 1, Ns − 1) path splitting. Adding the
bit estimation for imin , SPC nodes can be decoded by splitting

[1] S. A. Hashemi, C. Condo, and W. J. Gross, “Fast simplified successivecancellation list decoding of polar codes,” in IEEE Wireless Commun.
and Netw. Conf., March 2017, pp. 1–6.
[2] E. Arıkan, “Channel polarization: A method for constructing capacityachieving codes for symmetric binary-input memoryless channels,” IEEE
Trans. Inf. Theory, vol. 55, no. 7, pp. 3051–3073, July 2009.
[3] C. Leroux, A. Raymond, G. Sarkis, and W. Gross, “A semi-parallel
successive-cancellation decoder for polar codes,” IEEE Trans. Signal
Process., vol. 61, no. 2, pp. 289–299, January 2013.
[4] A. Alamdar-Yazdi and F. R. Kschischang, “A simplified successivecancellation decoder for polar codes,” IEEE Commun. Lett., vol. 15,
no. 12, pp. 1378–1380, December 2011.
[5] G. Sarkis, P. Giard, A. Vardy, C. Thibeault, and W. Gross, “Fast polar
decoders: Algorithm and implementation,” IEEE J. Sel. Areas Commun.,
vol. 32, no. 5, pp. 946–957, May 2014.
[6] I. Tal and A. Vardy, “List decoding of polar codes,” IEEE Trans. Inf.
Theory, vol. 61, no. 5, pp. 2213–2226, May 2015.
[7] I. Dumer and K. Shabunov, “Near-optimum decoding for subcodes of
Reed-Muller codes,” in IEEE Int. Symp. on Inform. Theory, 2001, p.
329.
[8] “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.
[9] A. Balatsoukas-Stimming, A. J. Raymond, W. J. Gross, and A. Burg,
“Hardware architecture for list successive cancellation decoding of polar
codes,” IEEE Trans. Circuits Syst. II, vol. 61, no. 8, pp. 609–613, August
2014.
[10] A. Balatsoukas-Stimming, M. Bastani Parizi, and A. Burg, “LLR-based
successive cancellation list decoding of polar codes,” IEEE Trans. Signal
Process., vol. 63, no. 19, pp. 5165–5179, October 2015.
[11] B. Yuan and K. K. Parhi, “LLR-based successive-cancellation list
decoder for polar codes with multibit decision,” IEEE Trans. Circuits
Syst. II, vol. 64, no. 1, pp. 21–25, January 2017.
[12] C. Xiong, J. Lin, and Z. Yan, “Symbol-decision successive cancellation
list decoder for polar codes,” IEEE Trans. Signal Process., vol. 64, no. 3,
pp. 675–687, February 2016.
[13] J. Lin, C. Xiong, and Z. Yan, “A high throughput list decoder architecture
for polar codes,” IEEE Trans. VLSI Syst., vol. 24, no. 6, pp. 2378–2391,
June 2016.
[14] C. Xiong, J. Lin, and Z. Yan, “A multimode area-efficient SCL polar
decoder,” IEEE Trans. VLSI Syst., vol. 24, no. 12, pp. 3499–3512,
December 2016.
[15] G. Sarkis, P. Giard, A. Vardy, C. Thibeault, and W. J. Gross, “Fast list
decoders for polar codes,” IEEE J. Sel. Areas Commun., vol. 34, no. 2,
pp. 318–328, February 2016.
[16] S. A. Hashemi, C. Condo, and W. J. Gross, “List sphere decoding
of polar codes,” in Asilomar Conf. on Signals, Syst. and Comput.,
November 2015, pp. 1346–1350.
[17] S. A. Hashemi, C. Condo, and W. J. Gross, “Simplified successivecancellation list decoding of polar codes,” in IEEE Int. Symp. on Inform.
Theory, July 2016, pp. 815–819.
[18] S. A. Hashemi, C. Condo, and W. J. Gross, “Matrix reordering for
efficient list sphere decoding of polar codes,” in IEEE Int. Symp. on
Circuits and Syst., May 2016, pp. 1730–1733.

14

[19] S. A. Hashemi, C. Condo, and W. J. Gross, “A fast polar code list
decoder architecture based on sphere decoding,” IEEE Trans. Circuits
Syst. I, vol. 63, no. 12, pp. 2368–2380, December 2016.
[20] C. Condo, M. Martina, G. Piccinini, and G. Masera, “Variable parallelism cyclic redundancy check circuit for 3GPP-LTE/LTE-Advanced,”
IEEE Signal Process. Lett., vol. 21, no. 11, pp. 1380–1384, November
2014.

Seyyed Ali Hashemi was born in Qaemshahr, Iran.
He received the B.Sc. degree in electrical engineering from Sharif University of Technology, Tehran,
Iran, in 2009 and the M.Sc. degree in electrical
and computer engineering from the University of
Alberta, Edmonton, AB, Canada, in 2011. He is
currently working toward the Ph.D. degree in electrical and computer engineering at McGill University,
Montréal, QC, Canada. He was the recipient of
a Best Student Paper Award at the 2016 IEEE
International Symposium on Circuits and Systems
(ISCAS 2016). His research interests include error-correcting codes, hardware architecture optimization, and VLSI implementation of digital signal
processing systems.

Carlo Condo received the M.Sc. degree in electrical and computer engineering from Politecnico
di Torino, Italy, and the University of Illinois at
Chicago, IL, USA, in 2010. He received the Ph.D.
degree in electronics and telecommunications engineering from Politecnico di Torino and Telecom
Bretagne, France, in 2014. Since 2015, he has been
a postdoctoral fellow at the ISIP Laboratory, McGill
University. His Ph.D. thesis was awarded a mention
of merit as one of the five best of 2013/2014 by
the GE association, and he has been the recipient of
two conference best paper awards (SPACOMM 2013 and ISCAS 2016). His
research is focused on channel coding, design and implementation of encoder
and decoder architectures, and digital signal processing.

Warren J. Gross (SM’10) received the B.A.Sc.
degree in electrical engineering from the University
of Waterloo, Waterloo, ON, Canada, in 1996, and
the M.A.Sc. and Ph.D. degrees from the University
of Toronto, Toronto, ON, Canada, in 1999 and 2003,
respectively. Currently, he is Professor and Associate
Chair (Academic Affairs) with the Department of
Electrical and Computer Engineering, McGill University, Montréal, QC, Canada. His research interests
are in the design and implementation of signal processing systems and custom computer architectures.
Dr. Gross served as Chair of the IEEE Signal Processing Society Technical
Committee on Design and Implementation of Signal Processing Systems. He
has served as General Co-Chair of IEEE GlobalSIP 2017 and IEEE SiPS
2017, and as Technical Program Co-Chair of SiPS 2012. He has also served
as organizer for the Workshop on Polar Coding in Wireless Communications
at WCNC 2017, the Symposium on Data Flow Algorithms and Architecture
for Signal Processing Systems (GlobalSIP 2014) and the IEEE ICC 2012
Workshop on Emerging Data Storage Technologies. Dr. Gross served as
Associate Editor for the IEEE Transactions on Signal Processing and currently
is a Senior Area Editor. Dr. Gross is a Senior Member of the IEEE and a
licensed Professional Engineer in the Province of Ontario.

