# Performance and Complexity of the Sequential Successive Cancellation
Decoding Algorithm

Peter Trifonov

###### Abstract

Simulation results illustrating the performance and complexity of the
sequential successive cancellation decoding algorithm are presented for the
case of polar subcodes with Arikan and large kernels, as well as for extended
BCH codes. Performance comparison with Arikan PAC and LDPC codes is provided.
Furthermore, complete description of the decoding algorithm is presented.

###### Index Terms:

Polar codes, polar subcodes, large kernels, sequential decoding.

##  I Introduction

Polar codes are a novel class of error correcting codes, which was already
adopted for use in 5G systems [1]. The development of polar codes started from
the analysis of sequential decoding [2]. It appears that the sequential
decoding techniques can be applied to decoder polar codes as well [3, 4, 5, 6,
7]. In this memo we present some performance and complexity results for the
sequential decoding algorithm introduced in [5] and later refined in [6].
Furthermore, we present a complete description of this algorithm. Although the
algorithm was originally introduced in the context of Arikan polar codes, it
can be used for decoding of polar codes with large kernels. The algorithm can
also naturally handle codes with dynamic frozen symbols, so it can be used for
decoding of polar subcodes and extended BCH codes.

##  II Background

An $(n=l^{m},k)$ polar code is a linear block code generated by $k$ rows of
matrix $G_{m}=K^{\otimes m}$, where $\otimes m$ is $m$-fold Kronecker product
of matrix with itself, $K$ is a kernel, and
$[l]=\left\\{{0,\dots,l-1}\right\\}$. The encoding scheme is given by
$c_{0}^{n-1}=u_{0}^{n-1}G_{m}$, where $u_{i},i\in\mathcal{F}$ are set to some
pre-defined values, e.g. zero (frozen symbols), $|\mathcal{F}|=n-k$, and the
remaining values $u_{i}$ are set to the payload data.

More general construction is obtained by allowing some frozen symbols to be
equal to linear combinations of other symbols, i.e.

$u_{i_{j}}=\sum_{s=0}^{i_{j}-1}u_{s}V_{js},0\leq j<n-k,$ (1)

where $V$ is a constraint matrix, such that last non-zero elements of its rows
are located in distinct columns $i_{j}$. The constraint matrix can be
constructed using both algebraic and randomized techniques [8, 9, 10, 11]. The
symbols, where the right hand side of (1) is non-zero are also known as
dynamic frozen [4] or parity check frozen symbols [12].

In particular, the constraint matrix can be obtained as

$V=QHG_{m}^{T},$ (2)

where $H$ is a check matrix of some linear block code of length $l^{m}$, and
$Q$ is a suitable invertible matrix. This allows one to apply the techniques
developed for decoding of polar codes to other codes. Extended primitive
narrow sense BCH codes were shown to be particularly well suited for this
approach [8].

Decoding of polar (sub)codes can be implemented by the successive cancellation
(SC) algorithm. It is convenient to describe the SC algorithm in terms of
probabilities
$W_{m}^{(i)}\left\\{{U_{0}^{i}=v_{0}^{i}|\mathbf{Y}=y_{0}^{n-1}}\right\\}=W_{m}^{(i)}\left\\{{v_{0}^{i}|y_{0}^{n-1}}\right\\}$
of transmission of various vectors $v_{0}^{n-1}G_{m}$ with given values
$v_{0}^{i}$, provided that the receiver observes a noisy vector $y_{0}^{n-1}$,
i.e.

$\displaystyle
W_{m}^{(i)}\left\\{{v_{0}^{i}|y_{0}^{n-1}}\right\\}=\frac{W_{m}^{(i)}(y_{0}^{n-1},v_{0}^{i-1}|v_{i})}{2W(y_{0}^{n-1})}$
$\displaystyle=$
$\displaystyle\sum_{v_{i+1}^{n-1}}W_{m}^{(n-1)}\left\\{{v_{0}^{n-1}|y_{0}^{n-1}}\right\\}=\sum_{v_{i+1}^{n-1}}\prod_{j=0}^{n-1}W\left\\{{(v_{0}^{n-1}G_{m})_{j}|y_{j}}\right\\},$
(3)

where $W_{m}^{(i)}(y_{0}^{n-1},v_{0}^{i-1}|v_{i})$ is the transition
probability function for the $i$-th subchannel induced by the polarizing
transformation $G_{m}$.

At phase $i$ the SC decoder makes decision

$\widehat{u}_{i}=\begin{cases}\arg\max_{v_{i}\in\operatorname{\mathbb{F}}_{2}}W_{m}^{(i)}\left\\{{\widehat{u}_{0}^{i-1}.v_{i}|y_{0}^{n-1}}\right\\},&i\not\in\mathcal{F}\\\
\sum_{s=0}^{i_{j}-1}\hat{u}_{s}V_{js},&\text{otherwise},\end{cases}$

where $a.b$ denotes a vector obtained by appending $b$ to $a$.

The SC decoder is known to be highly suboptimal. Much better performance can
be obtained with the successive cancellation list (SCL) algorithm [13], which
considers at each phase $i$ at most $L$ most probable paths $v_{0}^{i}$
satisfying freezing constraints.

##  III Sequential decoding

In this section we review of the sequential decoding algorithm introduced in
[6].

The SC algorithm does not provide maximum likelihood decoding. A successive
cancellation list (SCL) decoding algorithm was suggested in [13], and shown to
achieve substantially better performance with complexity $O(Ln\log n)$. large
values of $L$ are needed to implement near-ML decoding of polar subcodes and
polar codes with CRC. This makes practical implementations of such list
decoders very challenging.

In practice one does not need to obtain a list of codewords, but just a single
most probable one. The Tal-Vardy algorithm for polar codes with CRC examines
the elements in the obtained list, and discards those with invalid checksums.
This algorithm can be easily tailored to process the dynamic freezing
constraints used in the construction of polar subcodes [8] before the decoder
reaches the last phase, so that the output list contains only valid codewords.
However, even in this case $L-1$ codewords are discarded from the obtained
list, so most of the work performed by the Tal-Vardy decoder is just wasted.

This problem was addressed in [3], where a generalization of the stack
algorithm to the case of polar codes was suggested. It provides lower average
decoding complexity compared to the Tal-Vardy algorithm. In this paper we
revise the stack decoding algorithm for polar (sub)codes, and show that its
complexity can be substantially reduced.

###  III-A Stack decoding algorithm

Let $u_{0}^{n-1}$ be the input vector used by the transmitter. Given a
received noisy vector $y_{0}^{n-1}$, the proposed decoding algorithm
constructs sequentially a number of partial candidate information vectors
$v_{0}^{\phi-1}\in\operatorname{\mathbb{F}}_{2}^{\phi},\phi\leq n$, evaluates
how close their continuations $v_{0}^{n-1}$ may be to the received sequence,
and eventually produces a single codeword, being a solution of the decoding
problem.

The stack decoding algorithm [14, 15, 3, 5] employs a priority queue111A PQ is
commonly called ”stack” in the sequential decoding literature. However, the
implementation of the considered algorithm relies on Tal-Vardy data structures
[13], which make use of the true stacks. Therefore, we employ the standard
terminology of computer science. (PQ) to store paths together with their
scores. A PQ is a data structure, which contains tuples $(M,v_{0}^{\phi-1})$,
where $M=M(v_{0}^{\phi-1},y_{0}^{n-1})$ is the score of path $v_{0}^{\phi-1}$,
and provides efficient algorithms for the following operations [16]:

  * •

push a tuple into the PQ;

  * •

pop a tuple $(M,v_{0}^{\phi-1})$ with the highest $M$;

  * •

remove a given tuple from the PQ.

We assume here that the PQ may contain at most $D$ elements.

In the context of polar codes, the stack decoding algorithm operates as
follows:

  1. 1.

Push into the PQ the root of the tree with score $0$. Let $t_{0}^{n-1}=0$.

  2. 2.

Extract from the PQ a path $v_{0}^{\phi-1}$ with the highest score. Let
$t_{\phi}\leftarrow t_{\phi}+1$.

  3. 3.

If $\phi=n$, return codeword $v_{0}^{n-1}A_{m}$ and terminate.

  4. 4.

If the number of valid (i.e. those satisfying freezing constraints) children
$v_{0}^{\phi}$ of path $v_{0}^{\phi-1}$ exceeds the amount of free space in
the PQ, remove from it the element with the smallest score.

  5. 5.

Compute the scores $M(v_{0}^{\phi},y_{0}^{n-1})$ of valid children
$v_{0}^{\phi}$ of the extracted path, and push them into the PQ.

  6. 6.

If $t_{\phi}\geq L$, remove from PQ all paths $v_{0}^{j-1},j\leq\phi$.

  7. 7.

Go to step 2.

In what follows, one iteration means one pass of the above algorithm over
steps 2–7. Variables $t_{\phi}$ are used to ensure that the worst-case
complexity of the algorithm does not exceed that of a list SC decoder with
list size $L$.

The parameter $L$ has the same impact on the performance of the decoding
algorithm as the list size in the Tal-Vardy algorithm, since it imposes an
upper bound on number of paths $t_{\phi}$ considered by the decoder at each
phase $\phi$. Step 6 ensures that the algorithm terminates in at most $Ln$
iterations. This is also an upper bound on the number of entries stored in the
PQ. However, the algorithm can work with PQ of much smaller size $D$. Step 4
ensures that this size is never exceeded.

###  III-B Score function

There are many possible ways to define a score function for sequential
decoding. In general, this should be done so that one can perform meaningful
comparison of paths $v_{0}^{\phi-1}$ of different length $\phi$. The classical
Fano metric for sequential decoding of convolutional codes is given by the
probability

$P\left\\{{\mathcal{M}|y_{0}^{n-1}}\right\\}=\frac{P\left\\{{\mathcal{M},y_{0}^{n-1}}\right\\}}{\prod_{i=0}^{n-1}W(y_{i})},$

where $\mathcal{M}$ is a variable-length message (i.e. a path in the code
tree), and $W(y_{i})$ is the probability measure induced on the channel output
alphabet when the channel inputs follow some prescribed (e.g. uniform)
distribution [17]. In the context of polar codes, a straightforward
implementation of this approach would correspond to score function

$M_{1}(v_{0}^{\phi-1},y_{0}^{n-1})=\log
W_{m}^{(\phi-1)}\left\\{{v_{0}^{\phi-1}|y_{0}^{n-1}}\right\\}.$

This is exactly the score function used in [3]. However, there are several
shortcomings in such definition:

  1. 1.

Although the value of the score does depend on all $y_{i},0\leq i<n$, it does
not take into account freezing constraints on symbols
$u_{i},i\in\mathcal{F},i\geq\phi$. As a result, there may exist incorrect
paths $v_{0}^{\phi-1}\neq u_{0}^{\phi-1}$, which have many low-probability
continuations
$v_{0}^{n-1},v_{\phi}^{n-1}\in\operatorname{\mathbb{F}}_{2}^{n-\phi}$, such
that the probability

$W_{m}^{(\phi-1)}\left\\{{v_{0}^{\phi-1}|y_{0}^{n-1}}\right\\}=\sum_{v_{\phi}^{n-1}}W_{m}^{(n-1)}\left\\{{v_{0}^{n-1}|y_{0}^{n-1}}\right\\}$

becomes high, and the stack decoder is forced to expand such a path. This is
not a problem for convolutional codes, where the decoder may recover after an
error burst, i.e. obtain a codeword identical to the transmitted one, except
for a few closely located symbols.

  2. 2.

Due to freezing constraints, not all vectors $v_{0}^{\phi-1}$ correspond to
valid paths in the code tree. This does not allow one to fairly compare the
probabilities of paths of different lengths with different number of frozen
symbols.

  3. 3.

Computing probabilities
$W_{m}^{(\phi-1)}\left\\{{v_{0}^{\phi-1}|y_{0}^{n-1}}\right\\}$ involves
expensive multiplications and is prone to numeric errors.

The first of the above problems can be addressed by considering only the most
probable continuation of path $v_{0}^{\phi-1}$, i.e. the score function can be
defined as

$M_{2}(v_{0}^{\phi-1},y_{0}^{n-1})=\max_{v_{\phi}^{n-1}\in\operatorname{\mathbb{F}}_{2}^{n-\phi}}\log
W_{m}^{(n-1)}\left\\{{v_{0}^{n-1}|y_{0}^{n-1}}\right\\}.$

Observe that maximization is performed over last $n-\phi$ elements of vector
$v_{0}^{n-1}$, while the remaining ones are given by $v_{0}^{\phi-1}$. Let us
further define

$\mathbf{V}(v_{0}^{\phi-1},y_{0}^{n-1})=\arg\max_{\begin{subarray}{c}w_{0}^{n-1}\in\operatorname{\mathbb{F}}_{2}^{n}\\\
w_{0}^{\phi-1}=v_{0}^{\phi-1}\end{subarray}}\log
W_{m}^{(n-1)}\left\\{{w_{0}^{n-1}|y_{0}^{n-1}}\right\\},$

i.e. $M_{2}(v_{0}^{\phi-1},y_{0}^{n-1})=\log
W_{m}^{(n-1)}\left\\{{\mathbf{V}(v_{0}^{\phi-1},y_{0}^{n-1})|y_{0}^{n-1}}\right\\}.$

As shown below, employing such score function already provides significant
reduction of the average number of iterations at the expense of a negligible
performance degradation. Furthermore, it turns out that this score is exactly
equal to the one used in the min-sum version of the Tal-Vardy list decoding
algorithm [18], i.e. it can be computed in a very simple way.

To address the second problem, we need to evaluate the probabilities of
vectors $v_{0}^{n-1}$ under freezing conditions. To do this, consider the set
$C(\phi)$ of valid length-$\phi$ prefixes of the input vectors of the
polarizing transformation, i.e. vectors $v_{0}^{\phi-1}$ satisfying the
corresponding freezing constraints. Let us further define the set of their
most likely continuations, i.e.

$\overline{C}(\phi)=\left\\{{\mathbf{V}(v_{0}^{\phi-1},y_{0}^{n-1})|v_{0}^{\phi-1}\in
C(\phi)}\right\\}.$

For any $v_{0}^{n-1}\in\overline{C}(\phi)$ the probability of transmission of
$v_{0}^{n-1}A_{m}$, under condition of $v_{0}^{\phi-1}\in C(\phi)$ and given
the received vector $y_{0}^{n-1}$, equals

$\displaystyle{\mathbb{W}\left\\{{v_{0}^{n-1}|y_{0}^{n-1},C(\phi)}\right\\}=}\frac{W_{m}^{(n-1)}\left\\{{U_{0}^{n-1}=v_{0}^{n-1}|y_{0}^{n-1}}\right\\}}{W_{m}^{(n-1)}\left\\{{U_{0}^{n-1}\in\overline{C}(\phi)|y_{0}^{n-1}}\right\\}}.$

Hence, an ideal score function could be defined as

$\mathbb{M}(v_{0}^{\phi-1},y_{0}^{n-1})=\log\mathbb{W}\left\\{{\mathbf{V}(v_{0}^{\phi-1},y_{0}^{n-1})|y_{0}^{n-1},C(\phi)}\right\\}.$

Observe that this function is defined only for vectors $v_{0}^{\phi-1}\in
C(\phi)$, i.e. those satisfying freezing constraints up to phase $\phi$.

Unfortunately, there is no simple and obvious way to compute
$\pi(\phi,y_{0}^{n-1})=W_{m}^{(n-1)}\left\\{{U_{0}^{n-1}\in\overline{C}(\phi)|y_{0}^{n-1}}\right\\}$.
Therefore, we have to develop an approximation. It can be seen that

$\displaystyle\pi(\phi,y_{0}^{n-1})=$ $\displaystyle
W_{m}^{(n-1)}\left\\{{\mathbf{V}(u_{0}^{\phi-1})|y_{0}^{n-1}}\right\\}+$
$\displaystyle\underbrace{\sum_{\begin{subarray}{c}v_{0}^{\phi-1}\in
C(\phi)\\\
v_{0}^{\phi-1}\neq{u_{0}^{\phi-1}}\end{subarray}}W_{m}^{(n-1)}\left\\{{\mathbf{V}(v_{0}^{\phi-1})|y_{0}^{n-1}}\right\\}}_{\mu(u_{0}^{\phi-1},y_{0}^{n-1})}.$
(4)

Observe that
$p=\mathbf{E}_{{\mathbf{Y}}}\left[{\frac{\mu(u_{0}^{n-1},\mathbf{Y})}{\pi(\phi,\mathbf{Y})}}\right]$
is the total probability of incorrect paths at phase $\phi$ of the min-sum
version of the Tal-Vardy list decoding algorithm with infinite list size,
under the condition of all processed freezing constraints being satisfied. We
consider decoding of polar (sub)codes, which are constructed to have low list
SC decoding error probability even for small list size in the considered
channel $W(y|c)$. Hence, it can be assumed that $p\ll 1$. This implies that
with high probability $\mu(u_{0}^{\phi-1},y_{0}^{n-1})\ll
W_{m}^{(n-1)}\left\\{{\mathbf{V}(u_{0}^{\phi-1})|y_{0}^{n-1}}\right\\}$, i.e.
$\pi(\phi,y_{0}^{n-1})\approx
W_{m}^{(n-1)}\left\\{{U_{0}^{n-1}=\mathbf{V}(u_{0}^{\phi-1})|y_{0}^{n-1}}\right\\}$.

However, a real decoder cannot compute this value, since the transmitted
vector $u_{0}^{n-1}$ is not available at the receiver side. Therefore, we
propose to further approximate the logarithm of the first term in (III-B) with
its expected value over $\mathbf{Y}$, i.e.

$\log\pi(\phi,y_{0}^{n-1})\approx\Psi(\phi)=\mathbf{E}_{{\mathbf{Y}}}\left[{\log
W_{m}^{(\phi-1)}\left\\{{\mathbf{V}(u_{0}^{\phi-1})|\mathbf{Y}}\right\\}}\right]$
(5)

Observe that this value depends only on $\phi$ and underlying channel
$W(Y|C)$, and can be pre-computed offline.

Hence, instead of the ideal score function
$\mathbb{M}(v_{0}^{\phi-1},y_{0}^{n-1})$, we propose to use an approximate one

$M_{3}(v_{0}^{\phi-1},y_{0}^{n-1})=M_{2}(v_{0}^{\phi-1},y_{0}^{n-1})-\Psi(\phi).$
(6)

Observe that for the correct path $v_{0}^{\phi-1}=u_{0}^{\phi-1}$ one has
$\mathbf{E}_{{\mathbf{Y}}}\left[{M_{3}(v_{0}^{\phi-1},\mathbf{Y})}\right]=0$.

###  III-C Computing the score function

Consider computing

$\displaystyle R_{m}^{(\phi-1)}(v_{0}^{\phi-1},y_{0}^{n-1})=$ $\displaystyle
M_{2}(v_{0}^{\phi-1},y_{0}^{n-1})$ $\displaystyle=$
$\displaystyle\max_{\begin{subarray}{c}w_{0}^{n-1}\in\operatorname{\mathbb{F}}_{2}^{n}\\\
w_{0}^{\phi-1}=v_{0}^{\phi-1}\end{subarray}}\log
W_{m}^{(n-1)}\left\\{{w_{0}^{n-1}|y_{0}^{n-1}}\right\\},$

Let the modified log-likelihood ratios be defined as

$S_{m}^{(\phi)}(v_{0}^{\phi-1},y_{0}^{n-1})=R_{m}^{(\phi)}(v_{0}^{\phi-1}.0,y_{0}^{n-1})-R_{m}^{(\phi)}(v_{0}^{\phi-1}.1,y_{0}^{n-1}).$
(7)

It can be seen that

$\displaystyle R_{m}^{(\phi)}(v_{0}^{\phi},y_{0}^{n-1})=$ $\displaystyle
R_{m}^{(\phi-1)}(v_{0}^{\phi-1},y_{0}^{n-1})$
$\displaystyle+\tau(S_{m}^{(\phi)}(v_{0}^{\phi-1},y_{0}^{n-1}),v_{\phi}),$ (8)

where

$\tau(S,v)=\begin{cases}0,&\text{if $\operatorname{sgn}(S)=(-1)^{v}$}\\\
-|S|,&\text{otherwise.}\end{cases}$

is the penalty function. Indeed, let
$\tilde{v}_{0}^{n-1}=\mathbf{V}(v_{0}^{\phi-1})$. If
$v_{\phi}=\tilde{v}_{\phi}$, then the most probable continuations of
$v_{0}^{\phi-1}$ and $v_{0}^{\phi}$ are identical. Otherwise,
$-\left|S_{m}^{(\phi)}(v_{0}^{\phi-1},y_{0}^{n-1})\right|$ is exactly the
difference between the log-probability of the most likely continuations of
$v_{0}^{\phi-1}$ and $v_{0}^{\phi}$.

The initial value for recursion (8) is given by

$R_{m}^{(-1)}(y_{0}^{n-1})=\log\prod_{i=0}^{n-1}W\left\\{{C=\hat{c}_{i}|Y=y_{i}}\right\\},$

where $\hat{c}_{i}$ is the hard decision corresponding to $y_{i}$. However,
this value can be replaced with $0$, since it does not affect the selection of
paths in the stack algorithm.

Efficient techniques for computing modified LLRs
$S_{m}^{(\phi)}(v_{0}^{\phi-1},y_{0}^{n-1})$ for some kernels were derived in
[19].

###  III-D Modified LLRs for Arikan kernel

Since $R_{m}^{(\phi-1)}(v_{0}^{\phi-1},y_{0}^{n-1})$ is obtained by
maximization of $W_{m}^{(n-1)}\left\\{{v_{0}^{n-1}|y_{0}^{n-1}}\right\\}$ over
$v_{\phi}^{n-1}$, it can be seen that

$\displaystyle R_{\lambda}^{(2i)}(v_{0}^{2i},y_{0}^{N-1})=$
$\displaystyle\max_{v_{2i+1}}\left(R_{\lambda-1}^{(i)}\left(v_{0,e}^{2i+1}\oplus
v_{0,o}^{2i+1},y_{0}^{\frac{N}{2}-1}\right)+R_{\lambda-1}^{(i)}\left(v_{0,o}^{2i+1},y_{\frac{N}{2}}^{N-1}\right)\right),$
$\displaystyle R_{\lambda}^{(2i+1)}(v_{0}^{2i+1}|y_{0}^{N-1})=$
$\displaystyle\quad\quad\quad R_{\lambda-1}^{(i)}\left(v_{0,e}^{2i+1}\oplus
v_{0,o}^{2i+1},y_{0}^{\frac{N}{2}-1}\right)+R_{\lambda-1}^{(i)}\left(v_{0,o}^{2i+1},y_{\frac{N}{2}}^{N-1}\right),$

where $N=2^{\lambda},$ $0<\lambda\leq m$, and initial values for these
recursive expressions are given by $R_{0}^{(0)}(b,y_{j})=\log
W_{0}^{(0)}\left\\{{b|y_{j}}\right\\}$, $b\in\left\\{{0,1}\right\\}$. From (7)
one obtains

$\displaystyle S_{\lambda}^{(2i)}(v_{0}^{2i-1}|y_{0}^{2^{\lambda}-1})=$
$\displaystyle\max(J(0)+K(0),J(1)+K(1))-$
$\displaystyle\max(J(1)+K(0),J(0)+K(1))$ $\displaystyle=$
$\displaystyle\max(J(0)-J(1)+K(0)-K(1),0)-$
$\displaystyle\max(K(0)-K(1),J(0)-J(1))$ $\displaystyle
S_{\lambda}^{(2i+1)}(v_{0}^{2i},y_{0}^{2^{\lambda}-1})=$ $\displaystyle
J(v_{2i})+K(0)-J(v_{2i}+1)-K(1)$

where $J(c)=R_{\lambda-1}^{(i)}((v_{0,e}^{2i-1}\oplus
v_{0,o}^{2i-1}).c|y_{0}^{2^{\lambda-1}-1})$,
$K(c)=R_{\lambda-1}^{(i)}(v_{0,o}^{2i-1}.c|y_{2^{\lambda-1}}^{2^{\lambda}-1})$.
Observe that

$J(0)-J(1)=a=S_{\lambda-1}^{(i)}(v_{0,e}^{2i-1}\oplus
v_{0,o}^{2i-1},y_{0}^{2^{\lambda-1}-1})$

and

$K(0)-K(1)=b=S_{\lambda-1}^{(i)}(v_{0,o}^{2i-1},y_{2^{\lambda-1}}^{2^{\lambda}-1})$

It can be obtained from these expressions that the modified log-likelihood
ratios are given by

$\displaystyle S_{\lambda}^{(2i)}(v_{0}^{2i-1},y_{0}^{2^{\lambda}-1})=$
$\displaystyle
Q(a,b)=\operatorname{sgn}(a)\operatorname{sgn}(b)\min(|a|,|b|),$ (9)
$\displaystyle S_{\lambda}^{(2i+1)}(v_{0}^{2i},y_{0}^{2^{\lambda}-1})=$
$\displaystyle P(v_{2i},a,b)=(-1)^{v_{2i}}a+b.$ (10)

The initial values for this recursion are given by
$S_{0}^{(0)}(y_{i})=\log\frac{W\left\\{{0|y_{i}}\right\\}}{W\left\\{{1|y_{i}}\right\\}}$.
These expressions can be readily recognized as the min-sum approximation of
the list SC algorithm[18]. However, these are also the exact values, which
reflect the probability of the most likely continuation of a given path
$v_{0}^{\phi-1}$ in the code tree.

###  III-E The bias function

The function $\Psi(\phi)$ is equal to the expected value of the logarithm of
the probability of a length-$\phi$ part of the correct path, i.e. the path
corresponding to the vector $u_{0}^{n-1}$ used by the encoder. Employing this
function enables one to estimate how far a particular path $v_{0}^{\phi-1}$
has diverted from the expected behaviour of a correct path. The bias function
can be computed offline under the assumption of zero codeword transmission.

In the case of Arikan kernels the cumulative density functions
$F_{\lambda}^{(i)}(x)$ of $S_{\lambda}^{(i)}$ are given by [20]

$\displaystyle
F_{\lambda}^{(2i)}(x)=\begin{cases}2F_{\lambda-1}^{(i)}(x)(1-F_{\lambda-1}^{(i)}(-x)),&x<0\\\
2F_{\lambda-1}^{(i)}(x)-(F_{\lambda-1}^{(i)}(-x))^{2}-(F_{\lambda-1}^{(i)}(x))^{2},&x\geq
0\end{cases}$ $\displaystyle
F_{\lambda}^{(2i+1)}(x)=\int_{-\infty}^{\infty}F_{\lambda-1}^{(i)}(x-y)dF_{\lambda-1}^{(i)}(y),$

where $F_{0}^{(0)}(x)$ is the CDF of the channel output LLRs. Hence,

$\Psi(\phi)=-\sum_{i=0}^{\phi-1}\int_{-\infty}^{0}F_{m}^{(i)}(x)dx.$ (11)

No simlpe expressions are available for computing the CDF of LLRs in the case
of large kernels. Hence, the score function for such kernels can be computed
by simulating genie-aided SC decoder, and averaging the score
$M_{2}(u_{0}^{\phi-1},y_{0}^{n-1})$ for the correct path $u_{0}^{n-1}$.

The bias function $\Psi(\phi)$ depends only on $m$ and channel properties, so
it can be used for decoding of any polar (sub)code of a given length.

###  III-F Complexity analysis

The algorithm presented in Section III-A extracts from the PQ length-$\phi$
paths at most $L$ times. At each iteration it needs to calculate the LLR
$S_{m}^{(\phi)}(v_{0}^{\phi-1},y_{0}^{n-1})$. Intermediate values for these
calculations can be reused in the same way as in [13]. Hence, LLR calculations
require at most $O(Ln\log n)$ operations. However, simulation results
presented below suggest that the average complexity of the proposed algorithm
is substantially lower, and at high SNR approaches $O(n\log n)$, the
complexity of the SC algorithm.

##  IV Implementation

In this section we present implementation details of the sequential decoding
algorithm for the case of polar codes with Arikan kernel. We follow [5, 21].

Decode$(y_{0}^{n-1},L,D)$
---
1 | $\ignorespaces\mbox{\sc InitializeDataStructures}(D)$
2 | $\ignorespaces l\leftarrow\mbox{\sc AssignInitialPath}()$
3 | $\ignorespaces\tilde{S}\leftarrow\mbox{\sc GetArrayPointerS\\_W}(l,0,0)$
4 | $\ignorespaces\tilde{S}[0..n-1]\leftarrow y_{0}^{n-1}$
5 | $\ignorespaces R_{l}\leftarrow 0$
6 | $\ignorespaces\mbox{\sc Push}(l,0)$
7 | $\ignorespaces\mbox{\bf while\ }true$
8 | do $(M,l)\leftarrow\mbox{\sc PopMax}()$
9 | if $\phi_{l}=n$
10 | then $\mbox{\bf return\ }{\mbox{\sc GetArrayPointerC\\_R}(l,0,0)}$
11 | $\ignorespaces q_{\phi_{l}}\leftarrow q_{\phi_{l}}+1$
12 | $\ignorespaces\mbox{\sc IterativelyCalcS}(l,m,\phi_{l})$
13 | if $\phi_{l}\in\mathcal{F}$
14 | then $\mbox{\sc ContinuePathFrozen}(l)$
15 | else  if $P\geq D-1$
16 | then  Let $l_{0}$ be the path with the smallest score $M_{0}$
17 | $\ignorespaces\mbox{\sc KillPath}(l_{0})$
18 |  Remove $(M_{0},l_{0})$ from the PQ
19 | $\ignorespaces\mbox{\sc ContinuePathUnfrozen}(l)$
20 | if $q_{\phi_{l}-1}\geq L$
21 | then for  All paths $l^{\prime}$ stored in the PQ
22 | do if $\phi_{l}^{\prime}\leq\phi_{l}$
23 | then $\mbox{\sc KillPath}(l^{\prime})$
24 |  Remove $l^{\prime}$ from the PQ
Figure 1: The sequential decoding algorithm

ContinuePathFrozen$(l)$
---
1 | $\ignorespaces v\leftarrow\mbox{\sc EvaluateDynFrozen}(l,\phi_{l})$
2 | $\ignorespaces S\leftarrow\mbox{\sc GetArrayPointerS\\_R}(l,m)$
3 | $\ignorespaces C\leftarrow\mbox{\sc GetArrayPointerC\\_W}(l,m)$
4 | $\ignorespaces C[0]\leftarrow v$
5 | $\ignorespaces\mbox{\sc UpdateDynFrozen}(l,v)$
6 | if $(-1)^{v}S[0]<0$
7 | then $R_{l}\leftarrow R_{l}-|S[0]|$
8 | if $\phi_{l}\equiv 1\bmod 2$
9 | then $\mbox{\sc IterativelyUpdateC}(l,m,\phi_{l})$
10 | $\ignorespaces\phi_{l}\leftarrow\phi_{l}+1$
11 | $\ignorespaces\mbox{\sc Push}(l,R_{l}-\Psi(\phi_{l}))$
(a) Frozen symbols

ContinuePathUnfrozen$(l)$
---
1 | $\ignorespaces S\leftarrow\mbox{\sc GetArrayPointerS\\_R}(l,m)$
2 | $\ignorespaces C\leftarrow\mbox{\sc GetArrayPointerC\\_W}(l,m)$
3 | $\ignorespaces C[0]\leftarrow S<0$
4 | $\ignorespaces\mbox{\sc UpdateDynFrozen}(l,C[0])$
5 | $\ignorespaces l^{\prime}\leftarrow\mbox{\sc ClonePath}(l)$
6 | $\ignorespaces C^{\prime}\leftarrow\mbox{\sc GetArrayPointerC\\_W}(l^{\prime},m)$
7 | $\ignorespaces C^{\prime}[0]=1-C[0]$
8 | $\ignorespaces\mbox{\sc UpdateDynFrozen}(l^{\prime},C^{\prime}[0])$
9 | $\ignorespaces R_{l^{\prime}}\leftarrow R_{l}-|S[0]|$
10 | if $\phi_{l}\equiv 1\bmod 2$
11 | then $\mbox{\sc IterativelyUpdateC}(l,m,\phi_{l})$
12 | $\ignorespaces\mbox{\sc IterativelyUpdateC}(l^{\prime},m,\phi_{l})$
13 | $\ignorespaces\phi_{l}\leftarrow\phi_{l}+1;\phi_{l^{\prime}}\leftarrow\phi_{l}$
14 | $\ignorespaces\mbox{\sc Push}(l,R_{l}-\Psi(\phi_{l}))$
15 | $\ignorespaces\mbox{\sc Push}(l^{\prime},R_{l^{\prime}}-\Psi(\phi_{l^{\prime}}))$
(b) Unfrozen symbols

Figure 2: Path update procedures

IterativelyCalcS$(l,\lambda,\phi)$
---
1 | $\ignorespaces d\leftarrow\max\left\\{{0\leq d^{\prime}\leq\lambda-1|\phi\mbox{ is divisible by $2^{d^{\prime}}$ }}\right\\}$
2 | $\ignorespaces\lambda^{\prime}\leftarrow\lambda-d$
3 | $\ignorespaces S^{\prime}\leftarrow\mbox{\sc GetArrayPointerS\\_R}(l,\lambda^{\prime}-1)$
4 | $\ignorespaces N\leftarrow 2^{m-\lambda^{\prime}}$
5 | if  $\phi 2^{-d}$ is odd
6 | then $\tilde{C}\leftarrow\mbox{\sc GetArrayPointerC\\_R}(l,\lambda^{\prime})$
7 | $\ignorespaces S^{\prime\prime}\leftarrow\mbox{\sc GetArrayPointerS\\_W}(l,\lambda^{\prime})$
8 | $\ignorespaces S^{\prime\prime}[\beta]\leftarrow\mbox{\sc P}(\tilde{C}[\beta],S^{\prime}[\beta],S^{\prime}[\beta+N]),0\leq\beta<N$
9 | $\ignorespaces S^{\prime}\leftarrow S^{\prime\prime};\lambda^{\prime}\leftarrow\lambda^{\prime}+1;N\leftarrow N/2$
10 | $\ignorespaces\mbox{\bf while\ }\lambda^{\prime}\leq\lambda$
11 | do $S^{\prime\prime}\leftarrow\mbox{\sc GetArrayPointerS\\_W}(l,\lambda^{\prime})$
12 | $\ignorespaces S^{\prime\prime}[\beta]\leftarrow\mbox{\sc Q}(S^{\prime}[\beta+N],S^{\prime}[\beta]),0\leq\beta<N$
13 | $\ignorespaces S^{\prime}\leftarrow S^{\prime\prime};\lambda^{\prime}\leftarrow\lambda^{\prime}+1;N\leftarrow N/2$
(a) Computing $S_{\lambda}^{(\phi)}(v_{0}^{\phi-1},y_{0}^{N-1})$

IterativelyUpdateC$(l,\lambda,\phi)$
---
1 | $\ignorespaces\delta\leftarrow\max\left\\{{d|\phi+1\mbox{ is divisible by $2^{d}$ }}\right\\}$
2 | $\ignorespaces\tilde{C}\leftarrow\mbox{\sc GetArrayPointerC\\_W}(l,\lambda-\delta,0)$
3 | $\ignorespaces N\leftarrow 2^{m-\lambda};\tilde{C}=\tilde{C}+N(2^{\delta}-2);C^{\prime\prime}\leftarrow\tilde{C}+N;$
4 | $\ignorespaces\lambda^{\prime}\leftarrow\lambda-\delta$
5 | $\ignorespaces\mbox{\bf while\ }\lambda>\lambda^{\prime}$
6 | do $C^{\prime}\leftarrow\mbox{\sc GetArrayPointerC\\_R}(l,\lambda)$
7 | $\ignorespaces\tilde{C}[\beta]\leftarrow C^{\prime}[\beta]\oplus C^{\prime\prime}[\beta],0\leq\beta<N$
8 | $\ignorespaces N\leftarrow 2N;C^{\prime\prime}\leftarrow\tilde{C};\tilde{C}\leftarrow\tilde{C}-N$
9 | $\ignorespaces\lambda\leftarrow\lambda-1$
(b) Updating $C$ arrays

Figure 3: Computing LLRs and partial sums

Figure 1 presents the sequential decoding algorithm. Its input values are the
received noisy values $y_{0}^{n-1}$, maximal number of visits per phase $L$,
and priority queue size $D$. It makes use of modified Tal-Vardy data
structures [13], which are discussed below. Here $l$ denotes path index,
$\phi_{l}$ is the phase (i.e. length) of the $l$-th path, $q_{j}$ is the
number of times the decoder has extracted a path of length $j$, and $R_{l}$ is
the accumulated penalty of the $l$-th path, given by (8).

After initialization of the data structures, the received LLRs are loaded into
the $0$-th layer of Tal-Vardy data structures222Technically, one needs to
compute LLRs $S_{0}^{(0)}(y_{i})=\ln\frac{W(0|y_{i})}{W(1|y_{i})},0\leq i<n$.
However, one can scale appropriately the bias function, and avoid this
calculation., and the initial path is pushed into the priority queue. At each
iteration of the algorithm the index $l$ of a path $v_{0}^{\phi_{l}-1}$ with
the maximal score $M$ is obtained. If its length is equal $n$, decoding
terminates and the corresponding codeword is extracted at line 10. Otherwise,
phase visit counter is updated at line 11, and
$S_{m}^{(\phi_{l})}(v_{0}^{\phi_{l}-1},y_{0}^{n-1})$ is computed on line 12.
If $\phi_{l}$ corresponds to a frozen symbol, then the path is appropriately
extended on line 14. Otherwise, we need to ensure that there is sufficient
amount of free space in the priority queue. If this is not the case, the worst
path is removed at lines 17–18. The path is cloned to obtain
$v_{0}^{\phi_{l}-1}.0$ and $v_{0}^{\phi_{l}-1}.1$ at line 19. If the decoder
exceeds the allowed number of visits per phase $L$, then all paths shorter
than $\phi_{l}$ are eliminated at lines 23–24.

Procedures for extending the paths are shown in Figure 3(b). These procedures
obtain pointer $S$ to the computed LLR
$S_{m}^{(\phi_{l})}(v_{0}^{\phi_{l}-1},y_{0}^{n-1})$, pointer to the extension
symbol $C$ (and $C^{\prime}$), and put there appropriate values. For odd
phases, the partial sum values are propagated to the lower layers via calls to
$IterativelyUpdateC$. The functions update the accumulated penalty values, and
push the paths into the priority queue with appropriate score values.

Here a call to $EvaluateDynFrozen$ corresponds to evaluation of (1). Some
provisions are done for efficient evaluation of dynamic frozen symbols by
calling $UpdateDynFrozen$. Since for most practical codes the number of non-
trivial dynamic freezing constraints (i.e. rows of matrix $V$ of weight more
than 1) is small, in a software implementation one can store for each path a
bitmask, so that each bit in it corresponds to a dynamic frozen symbol. The
values of the bits are updated by $UpdateDynFrozen$ on the phases
corresponding to non-zero values in the $V$ matrix.

Figures 3(a) and 3(b) present iterative algorithms for computing
$S_{l,\lambda}[\beta]$ and $C_{l,\lambda}[\beta]$. These algorithms resemble
the recursive ones given in [13]. However, the proposed implementation avoids
costly array dereferencing operations. Each path is associated with arrays of
intermediate LLRs $S_{l,\lambda}[\beta],0\leq l<D,0\leq\lambda\leq
m,0\leq\beta<2^{m-\lambda},$ where $D$ is the maximal number of paths
considered by the decoder (i.e. the maximal size of the PQ).

It was suggested in [13] to store the arrays of partial sum tuples
$C_{l,\lambda}[\beta][\phi\bmod 2]$. We propose to rename these arrays to
$C_{l,\lambda,\phi\bmod 2}[\beta]$. By examining the RecursivelyUpdateC
algorithm presented in [13], one can see that $C_{l,\lambda,1}[\beta]$ is just
copied to $C_{l,\lambda-1,\psi}[2\beta+1]$ for some
$\psi\in\left\\{{0,1}\right\\}$, and this copy operation terminates on some
layer $\lambda^{\prime}$. Observe that $\lambda-\lambda^{\prime}$ is equal to
the maximal integer $d$, such that $\phi+1$ is divisible by $2^{d}$.
Therefore, we propose to co-locate $C_{l,\lambda,1}[\beta]$ with
$C_{l,\lambda_{0},0}[\beta]$. In this case the corresponding pointers are
given by
$C_{l,\lambda,1}=C_{l,\lambda_{0},0}+2^{m-\lambda}(2^{\lambda-\lambda^{\prime}}-1)$.
This not only results in the reduction of the amount of data stored by a
factor of two, but also enables one to avoid ”copy on write” operation (see
line 6 of Algorithm 9 in [13]). Therefore, we write $C_{l,\lambda_{0}}$
instead of $C_{l,\lambda_{0},0}$ in what follows.

We use the array pointer mechanism suggested in [13] to avoid data copying.
However, we distinguish the case of read and write data access. Retrieving
read-only pointers is performed by functions GetArrayPointerC_R$(l,\lambda)$
and GetArrayPointerS_R$(l,\lambda)$ shown in Figure 5. Retrieving writable
pointers is performed by function GetArrayPointerW$(T,l,\lambda)$, where
$T\in\left\\{{{}^{\prime}C^{\prime},^{\prime}S^{\prime}}\right\\}$ shown in
Figure 4. This function implements reference counting mechanism similar to
that proposed in [13].

Many paths considered by the proposed algorithm share common values of
$S_{l,\lambda}[\beta]$ and $C_{l,\lambda}[\beta]$, similarly to SCL decoding.
To avoid duplicate calculations one can use the same shared memory data
structures. That is, for each path $l$ and for each layer $\lambda$ we store
the index of the array containing the corresponding values
$S_{l,\lambda}[\beta]$ and $C_{l,\lambda}[\beta]$. This index is given by
$p=$PathIndex2ArrayIndex$[l,\lambda]$, so that the corresponding data can be
accessed as
ArrayPointer$[T][p],T\in\left\\{{{}^{\prime}S^{\prime},^{\prime}C^{\prime}}\right\\}$.
Furthermore, for each integer $p$ we maintain the number of references to this
array ArrayReferenceCount$[p]$. If the decoder needs to write the data into an
array, which is referenced by more than one path, a new array needs to be
allocated. Observe that there is no need to copy anything into this array,
since it will be immediately overwritten. This is an important advantage with
respect to the implementation described in [13]. However, the sequence of
array read/write and stack push/pop operations still satisfies the validity
assumptions introduced in [13], so the proposed algorithm can be shown to be
well-defined by exactly the same reasoning as the original SCL.

GetArrayPointerW$(T,l,\lambda)$
---
1 | $\ignorespaces p\leftarrow PathIndex2ArrayIndex[l,\lambda]$
2 | if $p=-1$
3 | then $p\leftarrow\mbox{\sc Allocate}(\lambda)$
4 | else  if $ArrayReferenceCount[p]>1$
5 | then $ArrayReferenceCount[p]--$
6 | $\ignorespaces p\leftarrow\mbox{\sc Allocate}(\lambda)$
7 | $\ignorespaces\mbox{\bf return\ }ArrayPointer[T][p]\ $

GetArrayPointerS_W$(l,\lambda)$
---
1 | $\ignorespaces\mbox{\bf return\ }\mbox{\sc GetArrayPointerW}(^{\prime}S^{\prime},l,\lambda)$

GetArrayPointerC_W$(l,\lambda,\phi)$
---
1 | $\ignorespaces\delta\leftarrow\max\left\\{{d|\phi+1\mbox{ is divisible by $2^{d}$ }}\right\\}$
2 | $\ignorespaces C\leftarrow\mbox{\sc GetArrayPointerW}(^{\prime}C^{\prime},l,\lambda-\delta)$
3 | if $\phi\equiv 1\bmod 2$
4 | then $C\leftarrow C+2^{m-\lambda}(2^{\delta}-1)$
5 | $\ignorespaces\mbox{\bf return\ }C$

Figure 4: Write access to the data

GetArrayPointerS_R$(l,\lambda)$
---
1 | $\ignorespaces\mbox{\bf return\ }\ ArrayPointer[^{\prime}S^{\prime}][PathIndex2ArrayIndex[l,\lambda]]$

GetArrayPointerC_R$(l,\lambda)$
---
1 | $\ignorespaces\mbox{\bf return\ }\ ArrayPointer[^{\prime}C^{\prime}][PathIndex2ArrayIndex[l,\lambda]]$

Figure 5: Read-only access to the data

The procedures $ClonePath$ and $KillPath$ operate in exactly the same way as
in [13], except that they additionally keep track of the number $P$ of active
paths.

The Tal-Vardy data structures need to be initialized to accomodate up to $D$
paths. This is implemented in $InitializeDataStructures$. This function
additionally resets counters $q_{0}^{n-1}$.

An efficient implementation of the priority queue is given in [22].

##  V Simulation results

Figure 6 presents the performance of some codes of length $64$. We consider
optimized polar subcodes [11], extended BCH codes, represented via (2), and
Arikan PAC codes, reproduced from [23]. For comparison, we present also normal
approximation333For $k=29$ the normal approximation appears to be rather
imprecise. for Polyanskiy-Poor-Verdu lower bound [24]

Figure 6: Performance of codes of length 128

List size for the sequential decoder was set to $L=2^{16}$, so that almost no
paths are killed.

(a) Average number of sequential decoder iterations

(b) Average number of arithmetic operations

Figure 7: Decoding complexity for codes of length 128

Figure 7(a) presents the associated decoding complexity.

It can be seen that extended BCH codes provide better performance compared to
PAC codes. However, their average decoding comlpexity is rather high.
Optimized polar subcodes provide performance extremely close to that of PAC
codes, but have much lower average decoding complexity. Observe that in the
latter case the average number of iterations performed by the sequential
decoder is much less compared to the average number of nodes visited by the
decoder considered in [23]. Figure 7(b) presents the same results in terms of
the number of arithmetic operations. Observe that the sequential decoding
algorithm uses only summation and comparison operations. It can be seen that
their average number converges to $n\log_{2}n+C$, where $C$ is a small value
corresponding to the cost of priority queue operations.

Figure 8: Performance and decoding complexity of $(128,64)$ codes

Figure 8 presents the performance and complexity of sequential decoder with
$L=128$ and PAC decoder with maximal number of node visits set to $16384$
[23]. It can be seen that the sequential decoder has much lower average
complexity. Observe also that at high SNR the average number of iterations
performed by the sequential decoder converges to $n$, the length of the code,
while the average number of node visits for PAC decoder converges to a higher
value.

Figure 9: Performance and decoding complexity of $(2048,1024)$ codes

Figure 9 presents performance and average decoding complexity of a
$(2048,1024)$ optimized polar subcode, as well as CCSDS LDPC code under
shuffled BP decoding [25]. It can be seen that even with $L=32$ the sequential
decoding algorithm provides performance close to that of shuffled BP decoder
with 200 iterations. Further 0.15 dB gain is obtained by setting $L=512$. Even
in the latter case the sequential decoder requires in average less operations
than the shuffled BP decoder for $E_{b}/N_{0}>1.3$ dB. Observe also that
shuffled BP decoder requires computing $\log\tanh(.)$ function444Replacing it
with some approximations may result in performance degradation, while the
sequential decoder uses only summation and comparison operations. Hence, the
considered polar subcode under sequential decoding provides both better
performance AND lower decoding complexity compared to the LDPC code.

Observe also, that increasing the number of iterations in the shuffled BP
decoder does not provide any noticeable improvement. However, it is possible
to obtain further 0.1 dB gain with polar subcode by setting $L=2048$ in the
sequential decoder. In this case the complexity of the sequential decoder
becomes lower than the complexity of the shuffled BP decoder for
$E_{b}/N_{0}>1.7$ dB. Even for $L=2048$ no maximum likelihood decoding errors
were observed in sequential decoder simulations, so further performance
improvement can be obtained by increasing decoding complexity.

Figure 10: Performance and decoding complexity of $(4096,2048)$ codes

Figure 10 presents performance and decoding complexity of randomized
$(4096,2048)$ polar subcodes with Arikan kernel and $16\times 16$ kernel
$K_{2}$ reported in [19]. It can be seen that the code with large kernel
requires $L=64$ to achieve the same performance as the code with Arikan kernel
and $L=256$. However, the code with the large kernel requires much lower
number of iterations in average. Observe that decoding of both codes requires
only summation and comparison operations.

##  VI Conclusions

In this memo performance and complexity results for polar subcodes and
sequential successive cancellation decoding algorithm were presented. It was
shown that optimized polar subcodes provide performance close to PAC codes of
length 128, while extended BCH codes do outperform them. The average
complexity of sequential decoding of optimized polar subcodes is much less
compared to PAC and extended BCH codes. It was shown that $(2048,1024)$
randomized polar subcode under sequential decoding provides both better
performance and lower decoding complexity compared to the CCSDS LDPC code.
Furthemore, $(4096,2048)$ polar subcode with the large kernel was shown to
have lower sequential decoding complexity compared to the one with Arikan
kernel.

## Acknowledgements

The author thanks G. Trofimiuk for providing an implementation of the decoder
for polar codes with $K_{2}$ kernel, and N. Iakuba for his help with
implementation of the sequential decoder.

## References

  * [1] E. Arıkan, “Channel polarization: A method for constructing capacity-achieving codes for symmetric binary-input memoryless channels,” _IEEE Transactions on Information Theory_ , vol. 55, no. 7, pp. 3051–3073, July 2009.
  * [2] E. Arikan, “On the origin of polar coding,” _IEEE Journal On Selected Areas In Communications_ , vol. 34, no. 2, February 2016.
  * [3] K. Niu and K. Chen, “Stack decoding of polar codes,” _Electronics Letters_ , vol. 48, no. 12, pp. 695–697, June 2012.
  * [4] P. Trifonov and V. Miloslavskaya, “Polar codes with dynamic frozen symbols and their decoding by directed search,” in _Proceedings of IEEE Information Theory Workshop_. Sevilla, Spain: IEEE, September 2013, pp. 1 – 5.
  * [5] V. Miloslavskaya and P. Trifonov, “Sequential decoding of polar codes,” _IEEE Communications Letters_ , vol. 18, no. 7, pp. 1127–1130, 2014.
  * [6] P. Trifonov, “A score function for sequential decoding of polar codes,” in _Proceedings of IEEE International Symposium on Information Theory_ , Vail, USA, 2018.
  * [7] V. Miloslavskaya and P. Trifonov, “Sequential decoding of polar codes with arbitrary binary kernel,” in _Proceedings of IEEE Information Theory Workshop_. Hobart, Australia: IEEE, 2014, pp. 377–381.
  * [8] P. Trifonov and V. Miloslavskaya, “Polar subcodes,” _IEEE Journal on Selected Areas in Communications_ , vol. 34, no. 2, pp. 254–266, February 2016\.
  * [9] P. Trifonov and G. Trofimiuk, “A randomized construction of polar subcodes,” in _Proceedings of IEEE International Symposium on Information Theory_. Aachen, Germany: IEEE, 2017, pp. 1863–1867.
  * [10] P. Trifonov, “On construction of polar subcodes with large kernels,” in _Proceedings of IEEE International Symposium on Information Theory_ , Paris, France, 2019.
  * [11] ——, “Randomized polar subcodes with optimized error coefficient,” _IEEE Transactions on Communications_ , vol. 68, no. 11, pp. 6714–6722, November 2020.
  * [12] T. Wang, D. Qu, and T. Jiang, “Parity-check-concatenated polar codes,” _IEEE Communications Letters_ , vol. 20, no. 12, December 2016.
  * [13] I. Tal and A. Vardy, “List decoding of polar codes,” _IEEE Transactions On Information Theory_ , vol. 61, no. 5, pp. 2213–2226, May 2015.
  * [14] K. S. Zigangirov, “Some sequential decoding procedures,” _Problems of Information Transmission_ , vol. 2, no. 4, pp. 1–10, 1966, in Russian.
  * [15] R. Johannesson and K. Zigangirov, _Fundamentals of Convolutional Coding_. IEEE Press, 1998.
  * [16] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, _Introduction to Algorithms_ , 2nd ed. The MIT Press, 2001\.
  * [17] J. Massey, “Variable-length codes and the Fano metric,” _IEEE Transactions on Information Theory_ , vol. 18, no. 1, pp. 196–198, January 1972\.
  * [18] 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, October 2015.
  * [19] G. Trofimiuk and P. Trifonov, “Reduced complexity window processing of binary polarization kernels,” in _Proceedings of IEEE International Symposium on Information Theory_ , Paris, France, July 2019.
  * [20] D. Kern, S. Vorkoper, and V. Kuhn, “A new code construction for polar codes using min-sum density,” in _Proceedings of International Symposium on Turbo Codes and Iterative Information Processing_ , 2014, pp. 228–232.
  * [21] G. Trofimiuk, N. Iakuba, S. Rets, K. Ivanov, and P. V. Trifonov, “Fast block sequential decoding of polar codes,” _IEEE Transactions on Vehicular Technology_ , vol. 69, no. 10, pp. 10 988–10 999, October 2020.
  * [22] N. Iakuba and P. Trifonov, “Multilevel buckets for sequential decoding of polar codes,” in _Proceedings of IEEE International Symposium on Personal, Indoor, Mobile and Radio Communications_. IEEE, 2015.
  * [23] M. Moradi, A. Mozammel, K. Qin, and E. Arikan, “Performance and complexity of sequential decoding of pac codes,” 2020, arXiv:2012.04990v1.
  * [24] Y. Polyanskiy, H. V. Poor, and S. Verdu, “Channel coding rate in the finite block length regime,” _IEEE Transactions On Information Theory_ , vol. 56, no. 5, May 2010.
  * [25] J. Zhang and M. P. Fossorier, “Shuffled iterative decoding,” _IEEE Transactions on Communications_ , vol. 53, no. 2, February 2005.