A Constituent Codes Oriented Code Construction
Scheme for Polar Code-Aim to Reduce the
Decoding Latency

arXiv:1612.02545v3 [cs.IT] 20 Sep 2017

Tiben Che and Gwan Choi
Department of Electrical and Computer Engineering
Texas A&M University, College Station, Texas 77840
Email: {ctb47321, gwanchoi}@tamu.edu
Abstract—This paper proposes a polar code construction
scheme that reduces constituent-code related decoding latency.
Constituent codes are the sub-codewords with specific patterns.
They are used to accelerate the successive cancellation decoding
process of polar code with negligible performance degradation.
We modify the traditional construction approach to yield increased number of desirable constituent codes that speeds the
decoding process. For (n, k) polar code, instead of directly setting
the k best and (n−k) worst bits to the information bits and frozen
bits, respectively, we swap the locations of some information and
frozen bits carefully according to the qualities of their equivalent
channels. We conducted the simulation of 1024 and 2048 bits
length polar codes with multiple rates and analyzed the decoding
latency for various length codes. The numerical results show that
the proposed construction scheme generally is able to achieve at
least around 20% latency deduction with an negligible loss in
gain with carefully selected optimization threshold.

I.

I NTRODUCTION

Recently, polar code [1] attract more and more research
interests due to that it is the first code which provably achieves
the channel capacity and its low coding complexity. Such property makes it very promising for real scenario such as wireless
communication and storage. Successive cancellation (SC) [1],
list successive cancellation (LSC) [2] and belief propagation
(BP) [3] are the three most widely known decoding algorithms.
Among those, SC and LSC receive more attention due to their
simpler hardware complexity compared with that of BP. Due to
its serial property, SC decoder suffers from the high decoding
latency. LSC considered as an extension of SC, similarly, has
the same problem. The latency reduction of SC decoder is able
to benefit the LSC decoder as well. Thus, a lot of efforts have
been done on the SC decoder to reduce the latency from both
hardware and algorithm aspects.
C. Leroux [4] proposed both tree and line architecture
of SC decoder. For length n polar code, it takes (2n − 2)
clock cycles to decode. Later on, he [5] proposed a semiparallel architecture for both tree and line SC decoder, which
makes a trade-off between hardware complexity and latency.
C. Zhang [6] proposed a low latency SC decoder with precomputing and overlapped architecture. Pre-computing technology reduces the latency to (n − 1) clock cycles, and
the overlap scheme significantly the throughput with multiple
frame situation. B. Yuan [7] proposed an architecture with
applying the 2-bit decoding at the last stage and some gate
level optimizations, this further reduce the latency to (3/4n−1)
clock cycles. Alamdar-Yazdi [8] proposed the simplified SC

(SSC) which can significantly reduce the latency via some
certain pattern sub-codewords. These kinds of sub-codewords
are also called constituent codes. This is the first time the
concept of constituent codes has been mentioned. Inspired
by this, Sarkis [9] proposed the fast-SSC which can further
reduce the latency by exploring more kinds of constituent
codes. T. Che [10] proposed the hardware architecture of
constituent codes based polar codes decoder. It allows the
decoding processes are compatible with both conventional and
constituent codes based polar codes. P. Giard [11] proposed an
unrolled architecture with fast-SSC is able to achieve 237 Gbps
throughput. P. Giard [12] also proposed a low-complexity decoder for low rate polar code. In that work, he further utilized
the potential of constituent codes by changing the frozen and
information sets. Additionally, the idea of of constituent codes
also benefits other decoding algorithm. J. Xu [13] applied the
constituent concept to the BP decoding which significantly
reduces the computing complexity. G. Sarkis [14] proposed
an constituent codes based LSC decoding. T. Che [15] also
pointed that the constituent codes can benefit the overlapped
LSC architecture in term of hardware efficiency.
Introducing constituent code is an approach to reduce
decoding latency. Most of the aforementioned works stress on
the decoding sides. In this paper, we explore the potential of
constituent codes from an opposite angle. We stress on the construction scheme to make the codeword more constituent-codefriendly. By adjusting the traditional construction approach,
more expected types of constituent codes are manually produced for decoding. For (n, k) polar code, instead of directly
setting the k best and (n − k) worst bits to the information
bits and frozen bits, respectively, we thoughtfully swap the
locations of some information and frozen bits according to
the qualities of their equivalent channels. The constituent
codes oriented polar code construction algorithm is described.
We conducted the simulation of 1024 and 2048 length polar
codes with multiple rates and analyzed the decoding latency
for various length codes. The numerical result shows that
the proposed construction scheme typically achieves 4-20%
latency reduction with negligible loss in decoding performance
with carefully selected optimization threshold. Some relevant
discussions are also presented.
This paper is organized as follows. The relative background
is reviewed in section II. Then, the proposed construction
scheme are described in section III. After that, the numerical
results and relevant discussions are presented in section IV.
Finally, this paper is concluded in section V.

u1

x1

u2

x2

u3

x3

u4

x4

u5

x5

Stage
0 Stage
1
Stage
f
2 Stage
f
αl
3
g
βl
f
βr
f
α
g αr
β
g

Ɲ

0

f

x6

g

u7

x7

f

u8

x8

g

1

REP

Fig. 2.

SPC

Ɲ

(a)

f

u6

Ɲ

Ɲ

(b)

SC decoding tree simplified by constituent codes

g
g

(a)

(b)

Fig. 1. (a) Encoder of (8, 4) polar code, (b) Tree presentation of (8, 4) SC
decoder

II.

BACKGROUND

A. Polar code
As described by E. Arikan [1], a polar code is constructed
by successively performing channel polarization. Polar codes
are linear block codes of length n = 2m . The coded codeword
x , (x1 , x2 , · · · , xn ) is computed by x = uG where
G = F ⊗m, and F ⊗m is the m-th Kronecker power of
1 0
. Each row of G corresponds to an equivalent
F =
1 1
polarizing channel. For an (n, k) polar code, k bits that
carry source information are called information bits. They are
transmitted via the k best channels. While the rest n − k bits,
called frozen bits, are set to zeros and are placed at the n − k
worst channels. Fig. 1a shows an example of the construction
of 8-bit polar code, where information bits and frozen bits are
denoted by black nodes and white nodes on the most left side,
respectively.
Polar codes can be decoded by recursively applying successive cancellation to estimate ûi using the channel output
y0n−1 and the previously estimated bits ûi−1
0 . This method is
referred as successive cancellation (SC) decoding. Actually,
SC decoding can be regarded as a binary tree traversal as
described in Fig. 1b. The number of bits of one node in
stage m(m = 0, 1, 2...) is equal to 2m . α stands for the soft
reliability value, typically is log-likelihood ratio (LLR). Each
left and right child nodes can calculate the LLR for current
node via f and g functions, respectively [5]. However, in order
to compute g function, a feedback β l from left child of the
same parent node is needed. This kind of feedback is called
partial sum. Actually, this serial property of feedback operation
limits the throughput of SC decoding.
B. Constituent codes based SC decoding
The recursive processing of getting the partial sum from
each node significantly constrains the decoding speed. Thus,
in order to obtain partial sum directly without performing tree
traversal, constituent codes based SC decoding has been proposed [8], [9]. Certain patterns in the codewords allows us to
decode the sub-codewords and get their corresponding partial
sums immediately, which significantly reduces the partial-sumconstrained latency.
N 0 , N 1 , N SP C and N REP are the four most common
constituent codes. N 0 and N 1 only contain either frozen bits

or information bits, respectively. N SP C and N REP contain
both frozen bits and information bits. In the N SP C codes,
only the first bit is frozen. It makes the length n constituent
codes as a rate (n − 1)/n single parity check (SPC) code. In
the N REP codes, only the last bit is information bit. In this
case, all the corresponding partial sums should be the same
since they all are the reflections of the last information bit. All
the above four constituent codes can be decoded very quickly.
According to T. Che’s implementation [10], the latency of
length n constituent code can be reduced from 2n − 2 to 1, 1,
log2 n + 1 and log2 n for N 0 , N 1 , N SP C and N REP codes,
respectively. Fig. 2 shows an example of how constituent code
can simplify the SC decoding tree.
III.

P ROPOSED

CONSTRUCTION

S CHEME

As described before, constituent codes are decoded faster
than conventional polar codes. Thus, in order to reduce the decoding latency, we expect more constituents codes, especially
constituent codes with large length. According to the definition
of constituent codes, the initial distribution of constituent codes
is determined by the location of information and frozen bits. If
we can change the locations, we are able to manually produce
expected constituent codes. However, the location of frozen
and information bits are very sensitive, and random changes
may cause negative influence on the coding performance. Thus,
a thoughtful construction scheme to produce more expected
constituent code is on demand. The division of information
and frozen bits is decided by the qualities of the equivalent
channels which are corresponding to each bit. Based on
the channel model, the equivalent channel qualities can be
calculated accordingly [1] [16] [17] [18]. This gives us a
hint that if we swap some information and frozen bits those
with similar channel qualities, this might only incur a very
slight performance loss. The numerical simulation results in
the following section prove this idea. In this work, binary
erasure channel (BEC) is used as our channel model, and thus
Bhattacharyya parameter is used as the metric for equivalent
channel quality. This method can be extended to any other
kind of channel model.
Now, we have the idea about how to change the division
of constituent codes. Next, we need to consider what kind of
changes are desired. For any length n polar code, it can be
regarded as a combination of the following four types of subcodewords.
•

Type-I: All the bits are frozen bits. This is also N 0
constituent code.

•

Type-II:All the bits are information bits. This is also
N 1 constituent code.

Type-III
REP

REP

Ɲ

Ɲ

Ɲ

0

Type-III

Ɲ0

Type-IV

Ɲ1

(a)
Fig. 3.

(b)

Examples of constituent codes division optimization

•

Type-III: Only one bit is information bit, the rest are
frozen bits. This can be regarded as the combination
of one N REP and multiple N 0 constituent codes.

•

Type-IV: Only one bit is frozen bit, the rest are information bits. This can be regarded as the combination
of one N SP C and multiple N 1 constituent codes.

According to T. Che’s results [10], there is only one clock
cycle needed for decoding N 0 and N 1 node. Thus, it is
unnecessary to optimize type-I and type-II codes since they
are already fully optimized. Our target should be focused on
the type-III and type-IV. These two types are similar, they all
only have one node with different type with others. There are
two situations we need to deal with. The first situation is the
optimization for single type-III or type-IV sub-tree. We can
swap the different node with the first or last one to make it
a N SP C or N REP nodes for type-IV or type-III sub-tree,
respectively. The second situation is that the optimization for
a combination of type-III and type-IV sub-trees. For this case,
we can swap the different node between the two types to make
them became one type-I and one type-II sub-trees. For the first
situation, suppose we have one Type-III node at stage m + 1.
It consist of one N REP and one N 0 node at stage m. This is
shown in Fig 3a. Totally, it needs 1+log22m = m+1 to finish
decoding. If we move the place of the information bit to make
it a N REP constituent code, the new latency for decoding
should be log2 2m+1 = m+1. There is no change if we do this
modification. This is also similar to type-IV situation. For the
second situation, suppose we have one type-III and one typeIV nodes at stage m as shown in Fig. 3b, the totally latency
for decoding should be 2m + 1. If we swap the information
bit in type-III and frozen bit in type-IV, we get one N 0 and
one N 1 nodes. The total should be reduced to 2. This makes a
huge difference. Thus, our target should be the swap operation
between type-III and type-IV nodes.
Based on above discussion, the constituent code oriented
polar code construction algorithm is proposed in algorithm (1).
After we get the information and frozen bits positions using the
traditional way, we apply this algorithm to adjust the location
of some information and frozen bits to make more desired
constituent code. This is an enhancement to the traditional
construction method.
IV.

S IMULATION R ESULTS

AND

D ISCUSSIONS

Fig. 4 shows the simulation results of proposed construction scheme. They are the BER/FER vs Eb/N0 performance for
1024 and 2048 length at different rate with multiple optimization thresholds. The polar codes is constructed based on the

Algorithm 1 constituent code oriented polar code construction
Input: The set of Bhattacharyya parameter, ǫn ; the initial set
of bit property (frozen or information), L; the threshold
for bit swapping,Th.
Initialize: index = 1.
1: get the sub-codeword-type look up table T from L; this
table gives the sub-codeword type information and its
index
2: if T [index] is type-III sub-codeword then
3:
get the index i of the information bit in T [index],
search all the next type-IV sub-codewords and find the
one whose frozen bit’s Bhattacharyya parameter has the
minimum difference with ǫn [i]. Recode the index f of
that.
4:
if |ǫn [i] − ǫn [f ]| < Th then
5:
swap the property of L[i] and L[f ], update T .
6:
end if
7: end if
8: if T [index] is type-IV sub-codeword then
9:
get the index f of the frozen bit in T [index], search
all the next type-III sub-codewords and find the one
whose information bit’s Bhattacharyya parameter is has
the minimum difference with ǫn [f ]. Recode the index i
of that.
10:
if |ǫn [i] − ǫn [f ]| < Th then
11:
swap the property of L[i] and L[f ], update T .
12:
end if
13: end if
14: increase index by 1, repeat to 2, until to the end of T

BEC channel and with target erasure rate 0.3. Table I shows the
decoding latency for each threshold and the comparison with
constituent codes decoding without any optimization and other
state-of-the-art decoders. We even calculated the latencies for
the codes with very long length such as 16384.
According to Fig. 4 and Table I, we note that the proposed
construction scheme generally is able to achieve at least
around 20% latency reduction with an negligible gain loss.
For a certain code length, we can find that the acceptable
threshold is increasing along with the code rate. This is due
to the nature of channel polarization. There are more frozen
and information bits mixed in the front and middle part of
codeword for lower rate codes, which gives more flexibility
during the optimization. However, this does not indicate that
this coding scheme is not working well on high rate. The
interesting part is that the performance on high rate is as good
as the low rate according to Fig. 4. It’s possibly attributable to
the following two reasons. First is that the coding performance
of high rate itself is much worse than that of low rate. This
causes the difference after optimization is not so obvious. The
second reason is that the simulated code length is still not long
enough due to the limitation of simulation environment. This
is per coding theory that suggests the longer polar code will
generally yield higher polarization. For a certain code rate, we
can find the acceptable threshold is decreasing along with the
code length. Since the longer codes are more polarized, the
difference of each equivalent channel is becoming smaller and
smaller as the length is increasing. This works fine with low
and medium length but not so obvious with high length. This
also can be explained by the two reason presented before.

TABLE I.

decoder
lenght=1024,rate=0.3

0

rate

lenght=2048,rate=0.3

0

10

length

10

0.3

−1

10

−1

10

−2

10
−2

BER/FER

BER/FER

10

−3

10

ber no optimization
ber th=1e−13
ber th=5e−12
ber th=1e−11
fer no optimization
fer th=1e−13
fer th=5e−12
fer th=1e−11

−4

10

−5

10

−6

10

1

1.5

2

1024

−3

10

−4

10

ber no optimization
ber th=1e−18
ber th=1e−17
ber th=1e−16
fer no optimization
fer th=1e−18
fer th=5e−17
fer th=5e−17

−5

10

−6

10

−7

2.5

3

10

3.5

1

1.5

2

Eb/No

lenght=1024,rate=0.5

0

0.7

2.5

3

3.5

0.3

Eb/No

lenght=2048,rate=0.5

0

10

0.5

proposed

10

2048

0.5

−1

10

−1

10

−2

10
−2

0.7
BER/FER

BER/FER

10

−3

10

ber no optimization
ber th=1e−4
ber th=5e−4
ber th=1e−3
fer no optimization
fer th=1e−4
fer th=5e−4
fer th=1e−3

−4

10

−5

10

−6

10

1

1.5

2

−3

10

−4

10

ber no optimization
ber th=1e−6
ber th=5e−5
ber th=1e−4
fer no optimization
fer th=1e−6
fer th=5e−5
fer th=1e−4

−5

10

−6

10

−7

2.5

3

10

3.5

1

1.5

2

Eb/No

2.5

3

16384

3.5

Eb/No

lenght=1024,rate=0.7

0

0.3

lenght=2048,rate=0.7

0

10

0.7

10

−1

10

[7]

−1

BER/FER

BER/FER

10

ber no optimization
ber th=0.1
ber th=0.2
ber th=0.4
fer no optimization
fer th=0.1
fer th=0.2
fer th=0.4

−2

10

−3

10

1

1.5

2

Fig. 4.

ber no optimization
ber th=0.1
ber th=0.2
ber th=0.3
fer no optimization
fer th=0.1
fer th=0.2
fer th=0.3

−4

3

3.5

-

latency
303
288
260
234
266
255
218
197
172
165
137
126
576
549
519
493
493
487
436
323
297
269
248
228
3992
3661
3242
2721
3327
3187
2898
2465
1350
1260
1165
898
767
1535
12287

reduction(%)
4.9
14
22.7
4.1
18
21.8
4
20
23.6
4.6
9.9
14.4
1.2
10.5
33.6
9.4
16.5
23.2
8.3
18.8
31.8
4.2
12.9
25.9
6.6
13.7
33.4
-

−2

−3

2.5

1024
2048
16384

threshold
no optimization
1e-13
1e-12
1e-11
no optimization
1e-4
5e-4
1e-3
no optimization
0.1
0.2
0.4
no optimization
1e-18
1e-17
1e-16
no optimization
1e-6
1e-5
1e-4
no optimization
0.1
0.2
0.3
no optimization
1e-50
1e-45
1e-40
no optimization
1e-13
1e-12
1e-11
no optimization
0.1
0.2
0.4

10

10

Eb/No

0.5

L ATENCY REDUCTION

10

1

1.5

2

desirable constituent codes combination. The second difference
is that the construction algorithm is different.
2.5

3

Eb/No

The ber vs Eb/N0 performance for proposed construction scheme

We compared the latency of proposed design with the
decoder in [7]; this is the fastest non-constituent-codes-based
polar code decoder to the best of our knowledge. We can see
even constituent codes decoder without any optimization is
much faster than that. Our proposed construction scheme is
capable of achieving 20% or more latency reduction. This is
very significant especially for very long code lengths.
Compared with [12] in which also changes the frozen and
information sets to benefit the decoding, our work has two
main differences. The first one is that we target a different
decoder architecture, which results in different demanding of

3.5

V.

C ONCLUSION

This paper presented a novel polar code construction
scheme which reduces the decoding latency. The proposed
constituent codes oriented polar code construction algorithm
can automatically produce more types of constituent codes
which are desirable. The simulation results show that the
proposed construction scheme generally is able to achieve at
least around 20% latency deduction with negligible decoding
performance loss. Besides, compared with non-constituentcodes-based decoder, the constituent codes based decoder has
a measurable advantage in term of latency. Our construction
scheme is able to further enhance the timing performance.
R EFERENCES
[1] E. Arikan, “Channel polarization: A method for constructing capacityachieving codes for symmetric binary-input memoryless channels,”
Information Theory, IEEE Transactions on, vol. 55, no. 7, pp. 3051–
3073, 2009.
[2] I. Tal and A. Vardy, “List decoding of polar codes,” in Information
Theory Proceedings (ISIT), 2011 IEEE International Symposium on.
IEEE, 2011, pp. 1–5.

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]
[12]

[13]

[14]

[15]

[16]
[17]
[18]

N. Hussami, S. B. Korada, and R. Urbanke, “Performance of polar codes
for channel and source coding,” in Information Theory, 2009. ISIT 2009.
IEEE International Symposium on. IEEE, 2009, pp. 1488–1492.
C. Leroux, I. Tal, A. Vardy, and W. J. Gross, “Hardware architectures
for successive cancellation decoding of polar codes,” in 2011 IEEE
International Conference on Acoustics, Speech and Signal Processing
(ICASSP). IEEE, 2011, pp. 1665–1668.
C. Leroux, A. J. Raymond, G. Sarkis, and W. J. Gross, “A semi-parallel
successive-cancellation decoder for polar codes,” Signal Processing,
IEEE Transactions on, vol. 61, no. 2, pp. 289–299, 2013.
C. Zhang and K. Parhi, “Low-latency sequential and overlapped architectures for successive cancellation polar decoder,” Signal Processing,
IEEE Transactions on, vol. 61, no. 10, pp. 2429–2441, 2013.
B. Yuan and K. K. Parhi, “Low-latency successive-cancellation polar
decoder architectures using 2-bit decoding,” IEEE Transactions on
Circuits and Systems I: Regular Papers, vol. 61, no. 4, pp. 1241–1254,
April 2014.
A. Alamdar-Yazdi and F. R. Kschischang, “A simplified successivecancellation decoder for polar codes,” IEEE communications letters,
vol. 15, no. 12, pp. 1378–1380, 2011.
G. Sarkis, P. Giard, A. Vardy, C. Thibeault, and W. J. Gross, “Fast
polar decoders: Algorithm and implementation,” Selected Areas in
Communications, IEEE Journal on, vol. 32, no. 5, pp. 946–957, 2014.
T. Che, J. Xu, and G. Choi, “Tc: Throughput centric successive
cancellation decoder hardware implementation for polar codes,” in
2016 IEEE International Conference on Acoustics, Speech and Signal
Processing (ICASSP). IEEE, 2016, pp. 991–995.
P. Giard, G. Sarkis, C. Thibeault, and W. J. Gross, “A 237 gbps unrolled
hardware polar decoder,” arXiv preprint arXiv:1412.6043, 2014.
P. Giard, A. Balatsoukas-Stimming, G. Sarkis, C. Thibeault, and W. J.
Gross, “Fast low-complexity decoders for low-rate polar codes,” Journal
of Signal Processing Systems, pp. 1–11, 2016.
J. Xu, T. Che, and G. Choi, “Xj-bp: Express journey belief propagation
decoding for polar codes,” in 2015 IEEE Global Communications
Conference (GLOBECOM). IEEE, 2015, pp. 1–6.
G. Sarkis, P. Giard, A. Vardy, C. Thibeault, and W. J. Gross, “Fast
list decoders for polar codes,” IEEE Journal on Selected Areas in
Communications, vol. 34, no. 2, pp. 318–328, 2016.
T. Che, J. Xu, and G. Choi, “Overlapped list successive cancellation
approach for hardware efficient polar code decoder,” arXiv preprint
arXiv:1511.00577, 2015.
I. Tal and A. Vardy, “How to construct polar codes,” IEEE Transactions
on Information Theory, vol. 59, no. 10, pp. 6562–6582, 2013.
P. Trifonov, “Efficient design and decoding of polar codes,” IEEE
Transactions on Communications, vol. 60, no. 11, pp. 3221–3227, 2012.
H. Vangala, E. Viterbo, and Y. Hong, “A comparative study of
polar code constructions for the awgn channel,” arXiv preprint
arXiv:1501.02473, 2015.

