# On the Metric and Computation of PAC Codes

Mohsen Moradi The author is with the Department of Electrical-Electronics
Engineering, Bilkent University, Ankara TR-06800, Turkey (e-mail:
moradi@ee.bilkent.edu.tr).

###### Abstract

In this paper, we present an optimal metric function on average, which leads
to a significantly low decoding computation while maintaining the superiority
of the polarization-adjusted convolutional (PAC) codes’ error-correction
performance. With our proposed metric function, the PAC codes’ decoding
computation is comparable to the conventional convolutional codes (CC)
sequential decoding. Moreover, simulation results show an improvement in the
low-rate PAC codes’ error-correction performance when using our proposed
metric function. We prove that choosing the polarized cutoff rate as the
metric function’s bias value reduces the probability of the sequential decoder
advancing in the wrong path exponentially with respect to the wrong path
depth. We also prove that the upper bound of the PAC codes’ computation has a
Pareto distribution; our simulation results also verify this. Furthermore, we
present a scaling-bias procedure and a method of choosing threshold spacing
for the search-limited sequential decoding that substantially improves the
decoder’s average computation. Our results show that for some codes with a
length of 128, the search-limited PAC codes can achieve an error-correction
performance close to the error-correction performance of the polar codes under
successive cancellation list decoding with a list size of 64 and CRC length of
11 with a considerably lower computation.

###### Index Terms:

PAC codes, sequential decoding, metric, threshold spacing, bias, polar codes.

##  I Introduction

Short block length codes with low complexity and probability of error are of
concern from a practical perspective. Over binary-input additive white
Gaussian noise (BI-AWGN) channel, polarization-adjusted convolutional (PAC)
codes under sequential decoding [1] are shown to have an error-correction
performance close to the minimum block error dispersion approximation [2] for
a short block length.

It is beneficial to consider the PAC code as a convolutional code (CC) under
sequential decoding, which sees a polarized channel. In this way, the encoding
process of PAC codes can be presented by an irregular binary tree, and the
sequential decoding of PAC codes can be considered as a walk through a tree.
The decoder’s task is to find the correct path in this tree with a guide of a
metric functıon. Additionally, the channel polarization brings the bit-channel
cutoff rates $E_{0}(1,W_{N}^{(i)})$ close to the bit-channel capacities
$I(W_{N}^{(i)})$. We review efficient methods of calculating
$E_{0}(1,W_{N}^{(i)})$ and $I(W_{N}^{(i)})$ values in the next section. We
will propose an optimal metric on average, which, by using
$E_{0}(1,W_{N}^{(i)})$ or $I(W_{N}^{(i)})$ as the bias values, maintains the
superior error-correction performance of the PAC codes while requiring low
computation comparable with the computation of the sequential decoding of CCs.
Compared to the previously used fixed bias values for low code rates [3],
using either of these bias values improves error-correction performance while
keeping low computation of the PAC codes.

By using the metric bias values less than or equal to the bit-channel cutoff
rates, we derive an upper bound with Pareto distribution for the computation
of the PAC sequential decoder.

Due to the computation variable Pareto distribution, to decode a small
fraction of the codewords, the PAC sequential decoder requires high
computation. Search-limited PAC sequential decoding can be employed [3] to
address this drawback. We investigate the effect of the threshold spacing
$\Delta$ value on the error-correction performance and computation of the
search-limited PAC sequential decoder. Moreover, we propose a scaling method
for the bit-channel bias values, which allows employing a trade-off between
the error-correction performance and computation of the search-limited PAC
sequential decoder.

We obtain a good choice of the threshold spacing $\Delta$ value for unlimited
search both theoretically and practically. Furthermore, we examine the PAC
codes’ response to code rate to cutoff rate ratio ($R/R_{0}$). The simulation
results show that, unlike conventional CCs, the PAC codes’ computation depends
linearly on this ratio.

Simulation results show that using a fixed bias value in the PAC codes’
sequential decoding metric function will result in a satisfactory error
performance due to the channel polarization. Nevertheless, the computation of
the PAC codes’ sequential decoding is much higher than the computation of the
sequential decoding of CCs [3]. We will explain in detail why using a fixed
bias value can result in an exponentially high computation.

The decoding computation of the sequential decoder is a random variable. This
paper will represent this random variable by counting the number of nodes that
are visited during a single decoding session.

For sufficiently large simulation trials, we use the notion of the average
number of visits (ANV), which corresponds to the empirical average of the
number of visits. We also use the maximum number of visits (MNV) to denote the
maximum number of nodes the decoder is allowed to visit during a single
decoding session.

Throughout this paper, we will only consider the PAC codes with a codeword of
length 128. All the codes are over the binary Galois field
$\mathbb{F}_{2}=\\{0,1\\}.$ We use the boldface notation for the vectors and
for a vector $\mathbf{u}=(u_{1},u_{2},...,u_{N})\in\mathbb{F}_{2}^{N}$,
$\mathbf{u}^{i}$ denotes the subvector $(u_{1},u_{2},...,u_{i})$ and
$\mathbf{u}_{i}^{j}$ denotes the subvector $(u_{i},...,u_{j})$ for $i\leq j$.
For any subset of indices $\mathcal{A}\subset\\{1,2,...,N\\}$,
$\mathcal{A}^{c}$ denotes the complement of $\mathcal{A}$ and
$\mathbf{u}_{\mathcal{A}}$ represents the subvector $(u_{i}:i\in\mathcal{A})$.

The rest of this paper is organized as follows. In Section II, the calculation
of bit-channel mutual information and cutoff rate is explained, and the scheme
of the PAC codes is briefly reviewed. In Section III, the on average
optimality of metric used in the PAC sequential decoder is proved. In Section
IV, the behavior of the partial path (accumulated) metric function is analyzed
using different bias values. In Section V, it is demonstrated that both frozen
bits and information bits can be used in the decoding process. Moreover, in
this Section, it is shown that by using bit-channel capacity or cutoff rate as
the metric bias, PAC codes can have an excellent error-correction performance
with a constant computation. In Section VI and VII, the techniques for finding
the best bias and threshold spacing values both for the search-limited and
search-unlimited sequential decoding are proposed. In Section VIII and Section
IX, both with simulations and theoretically, it is proved that the computation
of the PAC codes has a Pareto distribution upper bound. Finally, Section X
concludes this paper with a brief and suggestions for future work. Appendix X
provides the proofs of the lemmas and theorems used in this paper.

##  II Preliminaries

This section will review the efficient methods of calculating bit-channel
mutual information and the bit-channel cutoff rate, which we will frequently
use in this paper.

###  II-A Bit-channel mutual information

Consider a BI-AWGN channel with binary phase-shift keying (BPSK) modulation.
If the channel input is a uniform random variable $X\in\\{-1,+1\\}$ and the
channel output is a random variable $Y\in\mathbb{R}$, the mutual information
between the input and the output is defined as

$\begin{split}I(W)&=I(X;Y)\\\ &:=\sum_{x=\pm
1}\int_{-\infty}^{+\infty}\frac{1}{2}P_{Y|X}(y|x)\log_{2}\frac{P_{Y|X}(y|x)}{P_{Y}(y)}dy\\\
&=\frac{1}{\sqrt{8\pi\sigma^{2}}}\int_{-\infty}^{+\infty}a\left(1-\log_{2}(\frac{b}{a}+1)\right)\
+\\\ &\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
b\left(1-\log_{2}(\frac{a}{b}+1)\right)dy,\end{split}$ (1)

where

$a:=e^{\frac{-(y-1)^{2}}{2\sigma^{2}}}\text{ and
}b:=e^{\frac{-(y+1)^{2}}{2\sigma^{2}}},$ (2)

and $\sigma^{2}$ is the noise variance of the BI-AWGN channel. Since $y=x+n$
has a Gaussian distribution, where $n$ is a Gaussian noise with zero mean and
variance $\sigma_{n}^{2}$, according to [4]

$I(X;Y)=J(\frac{2}{\sigma_{n}^{2}}),$ (3)

where

$J(t)=1-\frac{1}{\sqrt{2\pi
t^{2}}}\int_{-\infty}^{+\infty}e^{\frac{-(u-\frac{t^{2}}{2})^{2}}{2t^{2}}}\log_{2}(1+e^{-u})du.$
(4)

The monotonically increasing function $I(X;Y)=J(t)$ has a unique inverse
function $t=J^{-1}(I(X;Y)).$ An approximation for the function $J(t)$ and its
inverse is given in [5] as

$\begin{split}&J(t)=\left[1-2^{-0.3073t^{2\times 0.8935}}\right]^{1.1064},\\\
&J^{-1}(I(X;Y))=\\\ &\ \ \ \ \
\left[-\frac{1}{0.3073}\log_{2}(1-I(X;Y)^{\frac{1}{1.1064}})\right]^{\frac{1}{2\times
0.8935}}.\end{split}$ (5)

In every step of polarization process, independent copies of channel $W$ is
transformed into polarized binary input channels $W^{+}$ and $W^{-}$. If we
represent this operation by a tree with its root being initialized by (1), at
each node the mutual information is polarized using the left-branch operation
(parity operation) $f_{c}$ and the right-branch operation (node operation)
$f_{v}$, which are defined as

$\begin{split}&f_{c}(t)=1-J\left[\sqrt{2}J^{-1}(1-t)\right],\\\
&f_{v}(t)=J\left[\sqrt{2}J^{-1}(t)\right],\end{split}$ (6)

where the leaf nodes are the bit-channel mutual information $I(W_{N}^{(i)})$
for $i\in\\{1,...,N\\}.$ Fig. 1 plots the bit-channel mutual information for
length of 128 and rate of $1/2$ at $\text{SNR}=2.5$ dB. Information bit
locations are chosen according to Reed-Muller rate profile (rows with higher
weights) as explained in [1].

Figure 1: Bit-channel capacity for information bits (solid circles) and frozen
bits (hollow circles) at 2.5 dB SNR value.

Another important parameter of the channel $W$ is the Bhattacharyya parameter
which is defined as

$Z(W):=\sum_{y\in\mathcal{Y}}\sqrt{W(y|0)W(y|1)}.$ (7)

For a BI-AWGN channel, $Z(W)$ is

$Z(W)=e^{\frac{-1}{2\sigma^{2}}},$ (8)

where $\sigma^{2}$ is the noise variance of the BI-AWGN channel. The log-
likelihood ratio of the output of the channel $W$ has a Gaussian distribution
with mean $m_{0}^{(1)}=2/\sigma^{2}$ and variance $2m_{0}^{(1)}$. With
$m_{0}^{(1)}$ at the root of tree, the bit-channel means $m_{N}^{(i)}$ at the
leaf level of the tree can be calculated using the check-operations $f_{c}$
and bit-operation $f_{v}$ as [6]

$\begin{split}&f_{c}(t)=\phi^{-1}\Big{(}1-(1-\phi(t))^{2}\big{)},\\\
&f_{v}(t)=2\phi(t),\end{split}$ (9)

where

$\phi(t)=\begin{cases}1-\frac{1}{\sqrt{4\pi
t}}\int_{\mathbb{R}}\tanh(\frac{z}{2})e^{-\frac{(z-t)^{2}}{4t}}dz,&t>0,\\\
1,&t<0,\end{cases}$ (10)

and $\phi^{-1}(t)$ can be calculated numerically.

Finally, the bit-channel Bhattacharya parameters can be calculated as

$Z(W_{N}^{(i)})=e^{\frac{-1}{2(\sigma_{N}^{(i)})^{2}}},$ (11)

where $m_{N}^{(i)}=2/(\sigma_{N}^{(i)})^{2}$.

For a given B-DMC $W$ and any $\rho\geq 0$, the error exponent of the channel
$W$ with $q(x)$ distribution on the input is defined as [7]

$E_{0}(\rho,W)=-\log_{2}\sum_{y\in\mathcal{Y}}\left[\sum_{x\in\mathcal{X}}q(x)W(y|x)^{\frac{1}{1+\rho}}\right]^{1+\rho}.$
(12)

By substituting $\rho=1$ in (12), we can obtain the cutoff rate as

$R_{0}(W,q):=E_{0}(1,W).$ (13)

If the input distribution is uniform, the error exponent becomes

$E_{0}(1,W)=\log_{2}\frac{2}{1+Z(W)},$ (14)

which is a lower bound for $I(W).$ According to (14), polarization of $Z(W)$
results in the polarization of $E_{0}(1,W)$. We will refer to
$E_{0}(1,W_{N}^{(i)})$ as bit-channel cutoff rate. Fig. 2 compares the bit-
channel cutoff rate with bit-channel mutual information.

Figure 2: (solid circles) bit-channel cutoff rate and (hollow circles) bit-
channel mutual information.

In [8], it is also proven that the error exponent is polarized for any
arbitrary $\rho\geq 0$ as

$E_{0}(\rho,W^{-})+E_{0}(\rho,W^{+})\geq 2E_{0}(\rho,W).$ (15)

Figure 3: Flowchart of PAC coding scheme.

###  II-B PAC Coding Scheme

Fig. 3 shows a flow chart of the PAC coding scheme.
$\mathbf{d}=(d_{1},\ldots,d_{K})$ is the data generated uniformly at random
over all possible source words of length $K$ in a binary field. The rate
profile module maps these $K$ bits into a data carrier vector $\mathbf{v}$ in
accordance with the data set $\mathcal{A}$, thus inducing a code rate of
$R=K/N$. In this paper, the RM score function is employed to determine
$\mathcal{A}$ set. After $\mathbf{v}$ is obtained by
$\mathbf{v}_{\mathcal{A}}=\mathbf{d}$ and $\mathbf{v}_{\mathcal{A}^{c}}=0$, it
is sent to the convolutional encoder and encoded as
$\mathbf{u}=\mathbf{v}\mathbf{T}$, where $\mathbf{T}$ is an upper-triangular
Toeplitz matrix constructed with a connection polynomial $\mathbf{c}$. In all
of our simulations, we use the connection polynomial $\mathbf{c}=3211$ (in
octal form) which is introduced in [3]. Then $\mathbf{u}$ is transformed to
$\mathbf{x}$ with standard polar transformation $\mathbf{F}^{\otimes n}$,
where $\mathbf{F}^{\otimes n}$ is the kronecker power of the kernel matrix
$\mathbf{F}=\begin{bmatrix}1&0\\\ 1&1\end{bmatrix}$ with $n=\log_{2}N$. After
the polar transformation, $\mathbf{x}$ is sent through the BI-AWGN channel.
Polar demapper receives the channel output $\mathbf{y}$ and the previously
decoded bits and calculates the log-likelihood ratio (LLR) value of the
current bit $z_{i}$. Finally, the sequential decoder outputs an estimate of
the carrier word $\hat{\mathbf{v}}$, from which the $K$-bits data can be
extracted according to $\mathcal{A}$.

The channel that the sequential decoder of PAC codes sees is a polarized
channel with memory. For this reason, the metric used by the sequential
decoder must be compatible with the channel. In the following sections, we
will investigate the metric function. To implement the sequential decoder, we
use the Fano algorithm [9], which is modified to be compatible with the PAC
codes [10]. Two parameters of the Fano algorithms are the bias and the
threshold spacing. In the rest of this paper, we will investigate the effects
of bias and threshold spacing on error-correction performance and computation
of the PAC codes under search-limited and search-unlimited decoder both
theoretically and practically.

##  III Metric

The most commonly used metric for sequential decoding in a B-DMC is Fano
metric [9] and is defined as

$\gamma(x_{i};y_{i})=\log_{2}\frac{P(y_{i}|x_{i})}{P(y_{i})}-b,$ (16)

where $P(y_{i}|x_{i})$ is the channel transition probability, $P(y_{i})$ is
the channel output, and $b$ is a constant bias. Massey [11] shows that for a
B-DMC, the Fano metric is the optimum metric for comparing paths of different
lengths. But clearly, the polarized channel in PAC codes is a channel with
memory since, for a polarized channel, demapping of any bit requires the
values of all the previously decoded bits. The Fano metric needs to be
modified to be suitable for decoding an irregular tree code sent over a
channel with memory. By adopting the notation used in [12],[3] and recalling
that the rate one convolution operation and polar transform are one-to-one
transforms, the partial path metric for the first $i$ branches is given by

$\Gamma(\mathbf{u}^{i};\mathbf{y})=\log_{2}\left(\frac{P(\mathbf{y}|\mathbf{u}^{i})}{P(\mathbf{y})}\right)-B_{i},$
(17)

where $\mathbf{y}=(y_{1},y_{2},...,y_{N})$ is the channel output,
$\mathbf{u}^{i}=(u_{1},u_{2},...,u_{i})$ is the path vector from root of the
tree to the node $i$, and $B_{i}=\sum_{j=1}^{i}b_{j}$ is the partial path bias
value up to the $i$th bit, and $b_{j}$ is a design parameter.

Every time a new branch in the tree is being examined, it is more convenient
to calculate the branch metric rather than calculating the partial path metric
of (17). For decoding $u_{j}$, the decoder knows the channel output
$\mathbf{y}$ and the previous bits $u_{1}$ up to $u_{j-1}$. By defining
$\gamma(u_{j};\mathbf{y},\mathbf{u}^{j-1})$ as the $j$th branch metric,
equation (17) can be written as

$\Gamma(\mathbf{u}^{i};\mathbf{y})=\sum_{j=1}^{i}\gamma(u_{j};\mathbf{y},\mathbf{u}^{j-1}).$
(18)

By defining $b_{j}:=B_{j}-B_{j-1}$ we have

$\begin{split}&\gamma(u_{j};\mathbf{y},\mathbf{u}^{j-1})=\Gamma(\mathbf{u}^{i};\mathbf{y})-\Gamma(\mathbf{u}^{j-1};\mathbf{y})\\\
&=\left[\log_{2}\left(\frac{P(\mathbf{y}|\mathbf{u}^{i})}{P(\mathbf{y})}\right)-B_{j}\right]\\\
&\ \ \ \
-\left[\log_{2}\left(\frac{P(\mathbf{y}|\mathbf{u}^{j-1})}{P(\mathbf{y})}\right)-B_{j-1}\right]\\\
&=\log_{2}\left(\frac{P(\mathbf{y}|\mathbf{u}^{j})}{P(\mathbf{y}|\mathbf{u}^{j-1})}\right)-(B_{j}-B_{j-1})\\\
&=\log_{2}\left(\frac{P(\mathbf{y}|\mathbf{u}^{j})}{P(\mathbf{y}|\mathbf{u}^{j-1})}\right)-b_{j}=\log_{2}\left(\frac{P(\mathbf{y},\mathbf{u}^{j-1}|u_{j})}{P(\mathbf{y},\mathbf{u}^{j-1})}\right)-b_{j}.\end{split}$
(19)

For a binary input channel with uniform input distribution, $u_{j}$ can be
either 0 or 1. For $u_{j}=0$, (19) becomes

$\begin{split}&\gamma(u_{j}=0;\mathbf{y},\mathbf{u}^{j-1})=\log_{2}\left(\frac{P(\mathbf{y},\mathbf{u}^{j-1}|u_{j}=0)}{P(\mathbf{y},\mathbf{u}^{j-1})}\right)-b_{j}\\\
&=\log_{2}\left(\frac{P(\mathbf{y},\mathbf{u}^{j-1}|u_{j}=0)}{\frac{1}{2}\left[P(\mathbf{y},\mathbf{u}^{j-1}|u_{j}=0)+P(\mathbf{y},\mathbf{u}^{j-1}|u_{j}=1)\right]}\right)\\\
&\ \ \ -b_{j}.\end{split}$ (20)

Dividing the numerator and denominator of (20) by
$P(\mathbf{y},\mathbf{u}^{j-1}|u_{j}=0)$ and defining

$z_{j}:=\dfrac{P(\mathbf{y},\mathbf{u}^{j-1}|u_{j}=0)}{P(\mathbf{y},\mathbf{u}^{j-1}|u_{j}=1)}$
(21)

as the likelihood ratio of bit $u_{j}$, we can rewrite (20) as

$\gamma(u_{j}=0;\mathbf{y},\mathbf{u}^{j-1})=1-\log_{2}\left(1+\dfrac{1}{z_{j}}\right)-b_{j}.$
(22)

Similarly, we can obtain the $j$th branch metric for $u_{j}=1$ as

$\gamma(u_{j}=1;\mathbf{y},\mathbf{u}^{j-1})=1-\log_{2}\left(1+z_{j}\right)-b_{j}.$
(23)

In conclusion, the $j$th branch metric for an irregular tree code transmitted
over a polarized channel is calculated using

$\begin{split}&\gamma(u_{j};\mathbf{y},\mathbf{u}^{j-1})=\\\ &\ \ \ \
\begin{cases}1-\log_{2}\left(1+\dfrac{1}{z_{j}}\right)-b_{j},&\text{if
}u_{j}=0;\\\ 1-\log_{2}(1+z_{j})-b_{j},&\text{if
}u_{j}=1.\end{cases}\end{split}$ (24)

The following expectations mentioned in [12] are useful in the next section.
The expectation of (19) over the ensemble of input bit $u_{j}$ and the bit-
channel transition probability $P(\mathbf{y},\mathbf{u}^{j-1}|u_{j})$ is

$\begin{split}&\mathbb{E}_{u_{j},\left(\mathbf{y},\mathbf{u}^{j-1}\right)}[\gamma(u_{j};\mathbf{y},\mathbf{u}^{j-1})]\\\
&=\sum_{u_{j}}q(u_{j})\sum_{\mathbf{y},\mathbf{u}^{j-1}}P(\mathbf{y},\mathbf{u}^{j-1}|u_{j})\gamma(u_{j};\mathbf{y},\mathbf{u}^{j-1})\\\
&=\sum_{u_{j}}\sum_{\mathbf{y},\mathbf{u}^{j-1}}q(u_{j})P(\mathbf{y},\mathbf{u}^{j-1}|u_{j})\\\
&\ \ \ \
\left[\log_{2}\left(\frac{P(\mathbf{y},\mathbf{u}^{j-1}|u_{j})}{P(\mathbf{y},\mathbf{u}^{j-1})}\right)-b_{j}\right]\\\
&ذ=I(W_{N}^{(j)})-b_{j},\end{split}$ (25)

where $I(W_{N}^{(j)})$ is the symmetric capacity of the bit-channel. If the
expectation in (25) is positive, the average branch metric increment is always
positive. Choosing the bit-channel bias less than symmetric capacity of the
bit-channels would guarantee that the expectation in (25) is positive.

Now, assume that $\tilde{u}_{j}$ is an incorrect branch with a metric of
$\gamma(\tilde{u}_{j};\mathbf{y},\mathbf{u}^{j-1})$ on the decoding tree. By
taking the average on all incorrect choices we can obtain

$\begin{split}&\mathbb{E}_{u_{j},\tilde{u}_{j},\left(\mathbf{y},\mathbf{u}^{j-1}\right)}[\gamma(\tilde{u}_{j};\mathbf{y},\mathbf{u}^{j-1})]\\\
&=\sum_{\tilde{u}_{j}}q(\tilde{u}_{j})\sum_{u_{j}}q(u_{j})\sum_{\mathbf{y},\mathbf{u}^{j-1}}P(\mathbf{y},\mathbf{u}^{j-1}|u_{j})\gamma(\tilde{u}_{j};\mathbf{y},\mathbf{u}^{j-1})\\\
&=\sum_{\tilde{u}_{j}}q(\tilde{u}_{j})\sum_{\mathbf{y},\mathbf{u}^{j-1}}P(\mathbf{y},\mathbf{u}^{j-1})\gamma(\tilde{u}_{j};\mathbf{y},\mathbf{u}^{j-1})\\\
&=\sum_{\tilde{u}_{j}}\sum_{\mathbf{y},\mathbf{u}^{j-1}}q(\tilde{u}_{j})P(\mathbf{y},\mathbf{u}^{j-1})\left[\log_{2}\left(\frac{P(\mathbf{y},\mathbf{u}^{j-1}|\tilde{u}_{j})}{P(\mathbf{y},\mathbf{u}^{j-1})}\right)-b_{j}\right]\\\
&\leq\sum_{\tilde{u}_{j}}\sum_{\mathbf{y},\mathbf{u}^{j-1}}q(\tilde{u}_{j})P(\mathbf{y},\mathbf{u}^{j-1})\left[\frac{P(\mathbf{y},\mathbf{u}^{j-1}|\tilde{u}_{j})}{P(\mathbf{y},\mathbf{u}^{j-1})}-1\right]-b_{j}\\\
&=-b_{j}.\end{split}$ (26)

Note that for deriving (26), we used the property $\log_{2}(x)\leq x-1$. Since
the information bit bias value is positive, the above expectation shows that
the branch metric will decrease by a constant value for an incorrect branch on
average.

###  III-A Optimality of the Proposed Metric

In the $i$th step of decoding, given the channel output $\mathbf{y}$, the
optimal metric is obtained when $p(\mathbf{u}^{i}|\mathbf{y})$ is maximized.
This probability is calculated by

$p(\mathbf{u}^{i}|\mathbf{y})=\frac{p(\mathbf{y}|\mathbf{u}^{i})}{p(\mathbf{y})}p(\mathbf{u}^{i}).$
(27)

By taking the $\log_{2}$ function of both sides, the partial path metric from
root to node $i$ is defined as

$\Gamma(\mathbf{u}^{i};\mathbf{y}):=\log_{2}p(\mathbf{u}^{i}|\mathbf{y})=\log_{2}\frac{p(\mathbf{y}|\mathbf{u}^{i})}{p(\mathbf{y})}+\log_{2}p(\mathbf{u}^{i}).$
(28)

Note that, since $\log_{2}$ is a monotonically increasing function, it will
preserve maximality. The $j$th branch metric will become

$\begin{split}&\gamma(u_{j};\mathbf{y},\mathbf{u}^{j-1}):=\Gamma(\mathbf{u}^{i};\mathbf{y})-\Gamma(\mathbf{u}^{j-1};\mathbf{y})\\\
&=\log_{2}\frac{P(\mathbf{y}|\mathbf{u}^{i})}{P(\mathbf{y}|\mathbf{u}^{j-1})}+\log_{2}\frac{p(\mathbf{u}^{i})}{p(\mathbf{u}^{j-1})}\\\
&=\log_{2}\frac{P(\mathbf{y},\mathbf{u}^{j-1}|u_{j})}{P(\mathbf{y},\mathbf{u}^{j-1})}+\log_{2}\frac{p(\mathbf{u}^{i})}{p(\mathbf{u}^{j-1})}\\\
&=\log_{2}\frac{P(\mathbf{y},\mathbf{u}^{j-1}|u_{j})}{P(\mathbf{y},\mathbf{u}^{j-1})}+\log_{2}p(u_{j}),\end{split}$
(29)

where the last equality is obtained using the fact that convolution is a one-
to-one and deterministic. Defining the bias value as

$b_{j}=\log_{2}\frac{1}{p(u_{j})},$ (30)

$b_{j}$ would become the information provided about the event $u_{j}$, which
is $I(W_{N}^{(i)})$ on average. Note that due to the polarization effect, the
bit-channel capacities are polarized. For the PAC codes constructed using RM
rate profile, there are bit-channel capacities with large values for both
frozen and information sets. This paper aims to benefit from these capacities
by designing a proper rule for $b_{j}$.

##  IV Design rules for bias

This section will study the effect of the different possible bias values
feasible to use in the sequential decoding of the PAC codes. Various choices
of bias values can result in different error-correction performance and
computation.

We will use the notations $b_{i}^{(F)}$ and $b_{i}^{(I)}$ to represent the
bias values for the frozen and information bits, respectively. We will use
$b_{i}$ to indicate the bit-channel bias values whenever we do not specify
whether a bit is frozen or information.

For a sequential decoder, to have better error-correction performance and
lower computation, the codewords must have a distance that increases as early
as possible. An optimum choice of the bit-channel bias values may result in a
fair distance. As discussed in the last section, by taking an average for the
correct and wrong paths, we have:

$\begin{split}&\textit{Correct path:}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}b_{i}\leq
I(W_{N}^{(i)}),\\\ &\textit{Wrong path: }~{}~{}~{}~{}~{}~{}~{}-b_{i}\leq 0.\\\
\end{split}$ (31)

In the following subsections, we will discuss three different design rules for
the bit-channel bias values. All three rules keep the PAC codes’ superior
error performance, but their computation is entirely different.

###  IV-A Design rule 1

A metric with the bias values $b_{i}^{(F)}=0$ and fixed $b_{i}^{(I)}$ s.t.
$b_{i}^{(I)}>I(W_{N}^{(i)})$ is used in [12] and [3]. More specifically, [3]
uses $b_{i}^{(I)}$ of 1.4, 1.35, and 1.14 for K = 29, 64, 99, respectively.
Smaller $b_{i}^{(I)}$ values will sacrifice the PAC code’s error-correction
performance. On the other hand, larger $b_{i}^{(I)}$ values increase the
computation. Note that for $i\in\mathcal{A}^{c}$,
$b_{i}^{(F)}=0<I(W_{N}^{(i)})$ and hence both inequalities of (31) are
satisfied. As a result, the decoder can decode the frozen bits faster, and the
partial path metric becomes a positive value for the frozen bits. On the other
hand, by assigning a large value to the information-bit bias values (say
$b_{i}^{(I)}=1.35$ for $K=64$), since $b_{i}^{(I)}\nleq I(W_{N}^{(i)})$, the
decoder will have some difficulty to find the correct path, and the partial
path metric for the information bits becomes negative on average.

One drawback of choosing $b_{i}^{(I)}>I(W_{N}^{(i)})$ is that, if the code has
long consecutive information bits, the information bits’ partial path metric
will significantly fall. In [3], for $K=29,64,99$ fixed bias values for the
information bits are chosen as $b_{i}^{(I)}=1.4,1.35,1.14$, respectively. The
reason to choose smaller $b_{i}^{(I)}$ values for longer messages is to reduce
the effect of negative partial path metric; otherwise, the decoding would
require an exponentially larger computation. Fig. 4, 5, and 6 show the partial
path metric for these three aforementioned code rates with the corresponding
bias values. These figures demonstrate that the partial path metric will
increase for the frozen bits and will decrease for the information bits on
average by choosing a fixed $b_{i}^{(I)}>I(W_{N}^{(i)})$ and
$b_{i}^{(F)}=0<I(W_{N}^{(i)})$.

The advantage of choosing $b_{i}^{(F)}=0$ is that in this case, both
inequalities of (31) are satisfied for the frozen bits, and consequently, the
decoder can decode the frozen bits with lower computation. As long as
$I(W_{N}^{(i)})>b_{i}^{(F)}$, the partial path metric is positive on average.

Figure 4: 10 sample partial path metrics v. bit indices for K = 29 with
$b_{i}^{(I)}=1.4$ and $b_{i}^{(F)}=0$ at -1.5 dB SNR value. Figure 5: 10
sample partial path metrics v. bit indices for K = 64 with $b_{i}^{(I)}=1.35$
and $b_{i}^{(F)}=0$ at 2.5 dB SNR value. Figure 6: 10 sample partial path
metrics v. bit indices for K = 99 with $b_{i}^{(I)}=1.14$ and $b_{i}^{(F)}=0$
at 5.5 dB SNR value.

###  IV-B Design rule 2

In this part, without loss of generality, we will only discuss the $K=64$
case. For $K=64$, using the bias values $b_{i}^{(I)}=I(W_{N}^{(i)})$ and
$b_{i}^{(F)}=0.4$, the PAC decoder performs as good as the decoder using rule
1 but with exponentially higher computation. Since $b_{i}^{(F)}=0.4\nleq
I(W_{N}^{(i)})$, for frozen bits, the partial path metric becomes a negative
number on average and results in an exponential growth in the computation of
the sequential decoding. For the information bits,
$b_{i}^{(I)}=I(W_{N}^{(i)})$ and both inequalities of 31 are satisfied. Hence,
the metric growth value for the information bits will be zero on average. The
partial path metric of design rule 2 is shown in Fig. 7.

Figure 7: 10 sample partial path metrics v. bit indices for K = 64 with
$b_{i}^{(I)}=I(W_{N}^{(i)})$ and $b_{i}^{(F)}=0.4$ at 2.5 dB SNR value.

Computation wise, design rule 2 differs from design rule 1. Rule 1 requires a
high decoding effort for decoding the information bits. In contrast, rule 2
requires a high decoding effort for decoding the frozen bits. As we already
mentioned, to have a low computation sequential decoding, the decoder should
decode the first bits with low decoding effort. Since for PAC codes, the first
bits are generally frozen, rule 2 requires exponentially higher computation
compared to rule 1.

###  IV-C Design rule 3

Design rule 3 is motivated by the fact that the sequential decoding is a
greedy tree-search algorithm similar to the shortest path graph-search
Dijkstra algorithm. Dijkstra algorithm always finds the shortest path on a
graph when the edges have positive weights and may or may not succeed in
finding the shortest path when some edges have negative weight values. With
similar reasoning, both design rules mentioned in the previous subsections may
or may not work with a reasonable amount of decoding computations for a given
codeword. Both beforehand expressed rules present propitious error performance
for the PAC codes of length 128 but required exponentially high computation.

With choosing $b_{i}^{(I)}$ and $b_{i}^{(F)}$ both equal to the bit-channel
mutual information $I(W_{N}^{(i)})$, both of (31) inequalities are satisfied
and the partial path metric of each branch becomes zero on average. For all
the bits, as $-b_{i}=-I(W_{N}^{(i)})<0$, rule 3 will prevent the decoder from
going to a wrong path most of the times. As a fortiori, Fig. 8 demonstrates
that using the design rule number 3, the average partial path metrics at each
level is 0 in rule 3. Hence, by employing design rule 3, the decoder will
decode every bit with a lower computation than the design rule 1 and 2. Notice
that in this figure, the plots are almost flat in the bits that are nearly
error-free ($I(W_{N}^{(i)})\approx 1$) or completely noisy
($I(W_{N}^{(i)})\approx 0$).

Alternatively, using $b_{i}=E_{0}(1,W_{N}^{(i)})$ for the bit-channel bias
values satisfies both inequalities of (31) strictly. Hence, for these bias
values, the partial path metrics should become positive on average. Fig. 9
supports the latter statement. As a result, the computation with bias
$b_{i}=E_{0}(1,W_{N}^{(i)})$ should be somewhat lower than with bias
$b_{i}=I(W_{N}^{(i)})$ at a cost of negligible sacrifice of error performance.
The negligibility of error performance degradation and computation improvement
is because of the polarization effect on both $E_{0}(1,W_{N}^{(i)})$ and
$I(W_{N}^{(i)})$. Note that in the conventional CCs, choosing the bias value
greater than the cutoff rate and close to the capacity results in the
exponential growth of computation. In this figure, the plots are almost flat
in the nearly error-free bits or completely noisy bits, which supports that
bit-channel cutoff rates are completely polarized in these bits.

Figure 8: 10 sample partial path metric v. bit indices for K = 64 with a bias
value $I(W_{N}^{(i)})$ for all the bits at 2.5 dB SNR value. Figure 9: 10
sample partial path metric v. bit indices for K = 64 with a bias value
$E_{0}(1,W_{N}^{(i)})$ for all the bits at 2.5 dB SNR value.

##  V Computation and Error-correction performance results

Considering (31), only design rule 3 of the previous section satisfies both
the inequalities. To understand the effect of the information and the frozen
bits on error-correction performance and computation of the PAC codes
separately, we split the design rule 3 into two cases based on the information
bits and the frozen bits entitled item 1 and 2, respectively. Finally, in item
3, we investigate the error-correction performance and computation results
using design rule 3, which benefits from combining item 1 and item 2.

###  V-A Item 1: information bits

As the study of the design rule three suggests, choosing the bit-channel bias
values according to $E_{0}(1,W_{N}^{(i)})$ or $I(W_{N}^{(i)})$ can result in
low computational decoding. In this subsection, we consider the bit-channel
bias values of the information bits as $E_{0}(1,W_{N}^{(i)})$ and we fix the
bit-channel bias values of the frozen bits to zero. Fig. 10 compares this
choice with the PAC code using $b_{i}^{I}=1.35$ and $b_{i}^{F}=0$ bias values.
As we can observe from the figure, there is a significant improvement in the
computation when using $b_{i}^{I}=E_{0}(1,W_{N}^{(i)})$ and $b_{i}^{F}=0$ bias
values. Note that this well amount of decrease in the computation comes at the
cost of sacrificing the PAC codes’ error performance. Dispersion approximation
is also provided in this figure.

Figure 10: FER performance comparison of PAC codes with different bias values.

Moreover, Fig. 11 compares a PAC$(128,59)$ code using
$b_{i}^{I}=E_{0}(1,W_{N}^{(i)})$ and $b_{i}^{F}=0$ bias values with a
CC$(140,64)$. As the figure shows, there is a significant improvement in the
FER of the PAC code, whereas the ANV of the PAC sequential decoding is almost
the same as the ANV of the CC sequential decoding. This improvement of the PAC
code’s error-correction performance is due to the polarization effect on the
channel. Sequential decoding for both PAC and CC codes have almost the same
ANV result, and for both of them, the computation suffers from the cutoff rate
phenomenon (ANV value for both of them increases for the SNR values less than
$R_{0}\approx 2.0$). Note that to calculate the ANV for both codes, we count
the number of visits per codeword and divide it by 128.

Figure 11: FER performance comparison of PAC and CC codes under sequential
decoding.

###  V-B Item 2: frozen bits

This subsection studies the effect of the frozen bits on the error-correction
performance and computation of PAC codes by using
$b_{i}^{F}=E_{0}(1,W_{N}^{(i)})$ and $b_{i}^{I}=0$ bias values. Note that
these choices of bias values satisfy (31). The idea of using frozen bits for
decoding PAC codes is motivated by the fact that for the short-length codes,
the bit channels are not entirely polarized. Moreover, when using the RM
scoring rule in constructing PAC codes, the $E_{0}(1,W_{N}^{(i)})$ of the
frozen bits are not absolute zero as Fig. 12 illustrates.

Fig. 13 plots the error-correction performance and computation of a PAC code
employing $b_{i}^{F}=E_{0}(1,W_{N}^{(i)})$ and $b_{i}^{I}=0$. As expected,
since both inequalities of (31) are satisfied; the ANV is less than 1.5 on
average.

Recall that the crucial attribute of sequential decoding is that if the wrong
turns can be discovered early enough, the saving in the number of computations
(measured in terms of the number of branches explored) would be exponential.
Since in the PAC codes the first bits are generally frozen bits, the choice of
$b_{i}^{F}=E_{0}(1,W_{N}^{(i)})$ can result in an exponential reduction in
computation.

Figure 12: Polarized $E_{0}(1,W_{N}^{(i)})$ values of the frozen bits at 2.5
dB SNR value. Figure 13: FER performance of PAC when bias
$E_{0}(1,W_{N}^{(i)})$ is used just for the frozen bits.

###  V-C Item 3

In the sequential decoding of the conventional CCs, because of the gap between
the cutoff rate and the channel capacity, choosing the metric function bias
value close to the channel capacity will result in an exponential growth in
the computation. However, for PAC codes, because of the small gap between the
bit-channel cutoff rates $E_{0}(1,W_{N}^{(i)})$ and bit-channel capacities
$I(W_{N}^{(i)})$, there is a negligible difference in the decoding computation
and error-correction performance while using either of them as the bias value.

Fig. 14 plots a comparison of FER and ANV of a PAC$(128,64)$ code using the
bias values $b_{i}=I(W_{N}^{(i)})$ versus the bias values $b_{i}^{I}=1.35$ and
$b_{i}^{F}=0$. From this figure, we can conclude that both choices of bias
values result in the same error-correction performance with
$b_{i}=I(W_{N}^{(i)})$ having exponentially smaller computation.

Figure 14: Comparing FER performance of the PAC codes.

Moreover, Fig. 15 plots a comparison of FER and ANV of a PAC$(128,29)$ code
using the bit-channel bias values $b_{i}=I(W_{N}^{(i)})$ and
$b_{i}=E_{0}(1,W_{N}^{(i)})$ versus using the fix bias values $b_{i}^{I}=1.4$
and $b_{i}^{F}=0$. From this figure, we can conclude that choosing
$b_{i}=I(W_{N}^{(i)})$ or $b_{i}=E_{0}(1,W_{N}^{(i)})$ results in better
error-correction performance and comparable computation compared to the fix
bias values $b_{i}^{I}=1.4$ and $b_{i}^{F}=0$. The random-coding union (RCU)
bound and dispersion approximation are also provided in this figure [2].

Figure 15: FER performance comparison of PAC codes for K = 29.

Fig. 16 compares FER and ANV of PAC$(128,64)$ code using the bias values
$b_{i}=I(W_{N}^{(i)})$ versus $b_{i}=E_{0}(1,W_{N}^{(i)})$. This figure
strengthens our previous idea that since $E_{0}(1,W_{N}^{(i)})$ is slightly
lower than $I(W_{N}^{(i)})$, the computation due to using
$b_{i}=I(W_{N}^{(i)})$ would be higher. The performance improvement marginally
occurs only at the low SNR values (noisy channels).

Figure 16: FER performance of PAC codes with bias $I(W_{N}^{(i)})$ and
$E_{0}(1,W_{N}^{(i)})$.

##  VI Scaling bias values

In this section, we investigate the behavior of the error-correction
performance and the computation of search-limited and search-unlimited PAC
decoder using scaled bias values as $\alpha\times I(W_{N}^{(i)})$ or
$\alpha\times E_{0}(1,W_{N}^{(i)})$, where $\alpha$ is a constant value. We
will show that for a search-limited sequential decoder to achieve a better
error-correction performance, the bias value is required to be scaled down.

###  VI-A Search-unlimited PAC codes

In this part, we investigate the effect of bias scaling on the ANV and FER
performance of the PAC codes under no computation limit. Fig. 17 plots ANV of
the PAC decoder using bias of $\alpha\times I(W_{N}^{(i)})$ and $\alpha\times
E_{0}(1,W_{N}^{(i)})$ for various values of $\alpha$. As shown in this figure,
as $\alpha$ increases, the ANV increases as well for both choices of bias
values. Note that, for the choice of the bias value as $\alpha\times
I(W_{N}^{(i)})$, the slope of the ANV increases after $\alpha=1$, whereas for
$\alpha\times E_{0}(1,W_{N}^{(i)})$, the increase occurs after $\alpha=1.02$.

Fig. 18 plots the FER performance of the PAC decoders of Fig. 17. From this
figure, we notice that the best FER is achieved with the $\alpha$ values close
to 1 and 1.02 for $b_{i}=\alpha\times I(W_{N}^{(i)})$ and $b_{i}=\alpha\times
E_{0}(1,W_{N}^{(i)})$, and as $\alpha$ diverges from 1 and 1.02, the FER
drops, respectively. Simulation results recommend using $1.02\times
E_{0}(1,W_{N}^{(i)})$ instead of $1\times I(W_{N}^{(i)})$ to achieve a lower
ANV with almost the same error-correction performance.

Fig. 19 plots the FER and ANV versus $\alpha$ for the bias values as the bit-
channel cutoff rates for a noisy channel (SNR = 0.0 dB). From Fig. 16 we can
observe that there is a gap between the FER performance of using
$b_{i}=E_{0}(1,W_{N}^{(i)})$ and the dispersion approximation. To reduce this
gap, Fig. 19 suggest increasing $\alpha$ value, but as $\alpha$ increases, the
computation grows exponentially. To summarize, the FER performance of PAC
codes using $b_{i}=\alpha\times E_{0}(1,W_{N}^{(i)})$ can near the dispersion
approximation at noisy channels at a cost of extreme computation increase.

In the next section, we will show that the effect of bias scaling on ANV and
FER performance is more significant for the search-limited PAC decoder.

Figure 17: ANV v. $\alpha$ for a (128,64) PAC code with an unlimited-search
Fano decoding at 2.5 dB SNR value, delta = 2. Figure 18: FER v. $\alpha$ for a
(128,64) PAC code with an unlimited-search Fano decoding at 2.5 dB SNR value,
delta = 2. Figure 19: FER v. $\alpha$ for a (128,64) PAC code with an
unlimited-search Fano decoding at 0 dB SNR value (noisy channel), delta = 2.

###  VI-B Search-limited PAC codes

This subsection investigates the effect of bias scaling on the error-
correction performance and ANV of the search-limited PAC Fano decoder.
Throughout this paper, we use MNV $=2^{12}$ for the search-limited PAC
decoder.

Fig. 20 plots FER versus $\alpha$ for bias values of $\alpha\times
I(W_{N}^{(i)})$ and $\alpha\times E_{0}(1,W_{N}^{(i)})$. As we can see from
this figure, using $\alpha=0.72$ and $\alpha=0.76$ result in the best FER
values for $\alpha\times I(W_{N}^{(i)})$ and $\alpha\times
E_{0}(1,W_{N}^{(i)})$ bias values, respectively. In our simulations (not
reported here) we realised that when using the bias value equal to the
$\alpha\times I(W_{N}^{(i)})$ or $\alpha\times E_{0}(1,W_{N}^{(i)})$ for
$0\leq\alpha\leq 1$, for large MNV values, choosing $\alpha$ value close to 1
results in better FER performance, whereas for smaller MNV values, a good FER
performance can be obtained by choosing smaller $\alpha$ values.

Fig. 21 plots ANV versus $\alpha$ for bias values of $\alpha\times
I(W_{N}^{(i)})$ and $\alpha\times E_{0}(1,W_{N}^{(i)})$. In this figure, we
can observe that as $\alpha$ decreases, the ANV decreases as well.

Figure 20: FER v. $\alpha$ for an $(128,64)$ PAC code with $\alpha\times
E_{0}(1,W_{N}^{(i)})$ and $\alpha\times I(W_{N}^{(i)})$ bias values, MNV =
$2^{12}$ at 2.5 dB SNR value, and threshold spacing $\Delta=2$. Figure 21: ANV
v. $\alpha$ for an $(128,64)$ PAC code with $\alpha\times
E_{0}(1,W_{N}^{(i)})$ and $\alpha\times I(W_{N}^{(i)})$ bias values, MNV =
$2^{12}$ at 2.5 dB SNR value, and threshold spacing $\Delta=2$.

##  VII Threshold spacing

In this section, we study the impact of the threshold spacing $\Delta$ on the
error performance and computation of the PAC codes. Different values of
$\Delta$ will result in different FER and ANV values for both search-limited
and -unlimited sequential decoding of the PAC codes. Based on the ANV and FER
trade-off, deciding on the most suitable threshold spacing value is a matter
of great concern.

###  VII-A Search unlimited

Figure 22: FER v. threshold spacing $\Delta$. Figure 23: ANV v. threshold
spacing $\Delta$.

Fig. 22 shows the effect of $\Delta$ value on the error performance of a
PAC(128,64) code at $2.5$ dB SNR value, where the bit-channel bias values are
set to $I(W_{N}^{(i)})$. As the figure displays, the FER performance degrades
as the $\Delta$ value increases; $\Delta=0.5$ and $\Delta=2$ result in the
best FER, and $\Delta=10$ results in the worst FER for this range of threshold
spacing. The corresponding ANV values are plotted in Fig. 23. As the figure
exhibits, the ANV value decreases by increasing the $\Delta$ value. Combining
Fig. 22 and 23, we can conclude that $\Delta=2$ is a reasonable choice for
threshold spacing value to maintain a good trade-off between the FER
performance and computation.

###  VII-B Search limited

Figure 24: FER v. threshold spacing $\Delta$ parameter for a search limited
(128,64) PAC code. Figure 25: ANV v. threshold spacing $\Delta$ parameter for
a search limited (128,64) PAC code.

Search-limited PAC$(128,64)$ code with MNV $=2^{12}$ and bit-channel bias
values equal to $0.72\times I(W_{N}^{(i)})$ at $2.5$ dB SNR is considered in
this subsection. The error performance results of the search-limited PAC code
using different values of threshold spacing is plotted in Fig. 24. Threshold
spacing $\Delta=4$ results in the best FER value. Also, the corresponding ANV
values are plotted in Fig. 25. Above $\Delta=4$, the threshold spacing values
have almost the same ANV results. Based on both figures, $\Delta=4$ is a
reasonable choice for threshold spacing value to obtain a fair trade-off
between FER performance and ANV.

Finally, based on the sequential decoding parameters obtained above, in Fig.
26 we compare the error performance of the search-limited PAC code with MNV
$=2^{12},\alpha=0.72$, and $\Delta=4$ and SCL decoding of polar codes [13]
with list size of 64 and CRC length of 11. It is worth mentioning that for the
PAC code, the ANV values are less than 4 for all the SNR values, which is much
less than the list size of 64.

Figure 26: Search-limited PAC code with $\alpha=0.72$, $\Delta=4$, and MNV =
$2^{12}$ v. polar code with SCL decoding with list size 64 and CRC length of
11.

##  VIII Distribution of Computation

Figure 27: CCDF of the number of node visits of the correctly decoded
codewords.

In this part, we will study the distribution of the number of visits during
PAC codes’ decoding. We will only consider the correctly decoded codewords and
discard the visit values for the wrongly decoded codewords. The complementary
cumulative distribution function (CCDF) or survival function of Pareto
distribution is defined as

$\overline{P}(x):=P(X>L)=\left\\{\begin{array}[]{ll}\sigma_{m}^{\beta}L^{-\beta},&\text{if}~{}L\geq\sigma_{m},\\\
1,&\text{if}~{}L<\sigma_{m},\\\ \end{array}\right.$ (32)

where the scale parameter $\sigma_{m}>0$ is the minimum possible value of $L$,
and $\beta>0$ is the shape parameter. Smaller $\beta$ corresponds to more
values occurring at the tail of the distribution. Pareto distribution at first
employed for the distribution of wealth and became known for the 80/20 rule.
This rule says that, as an example, $80\%$ of the wealth is for $20\%$ of the
population. For the decoding computation of the PAC codes, this rule implies
that the decoding computation is typically low but can be high for a small
portion of codewords.

If the scale parameter is equal to $1$, the mean of the Pareto distribution is
equal to

$\mathbb{E}[X]=\left\\{\begin{array}[]{ll}\infty,&\text{if}~{}\beta\leq 1,\\\
\frac{\beta}{\beta-1},&\text{if}~{}\beta>1.\\\ \end{array}\right.$ (33)

Pareto distribution has a finite mean for $\beta>1$ and has a finite variance
for $\beta>2$. Let $C$ represents the total number of nodes that are visited
during a single decoding session. The CCDF $P(C>L)$ is the probability that
the number of visits of a correctly decoded codeword is more than a constant
$L$. For the sequential decoding of CCs, it is shown in [14] that the
distribution of computation required to advance any level is upper bounded by

$P(C_{i}>L)<AL^{-\beta},$ (34)

where $A$ and $\beta>0$ are constants, and the exact definition of $C_{i}$ is
given in the next section. This proves that the CCDF of the computation time
of sequential decoding has a Pareto distribution upper bound. For PAC decoding
with bias values $b_{i}=E_{0}(1,W_{N}^{(i)})$, the CCDF of the number of nodes
visited for the correctly decoded codewords are plotted in Fig. 27 for 1
million decoding trials for different SNR values. The results demonstrate that
$P(C>L)<L^{-1}$ for almost all SNR values, and consequently, the mean of the
upper bound distribution is finite. Notice that for the sequential decoding of
the CCs, the mean is finite only for the rates below the cutoff rate.

For the SNR values equal to 3.5 and 4 dB, we have $\beta>2$, which will result
in a finite variance. As an example, Fig. 27 shows that there is one percent
probability for a correctly decoded codeword to require more than ten visits
per branch at the SNR value of 3.0 dB (outage probability). The main
conclusion from this discussion is that the probability that the number of
visits for each codeword exceeds $L$ is going to zero as $L$ increases.

Moreover, for $0$ and $0.5$ dB SNR values, Fig. 27 shows waterfalling results,
which means that the outage probability for the low SNR values for a moderate
number of computations is small. At low SNR values, the PAC decoder finishes
the decoding process earlier compared to high SNR values. In contrast, for the
fixed bias values, PAC codes at low SNR values require exponentially high
computation.

Figure 28: The empirical average number of computations per bit decoded.

In Fig. 28, for the correctly decoded codewords, the ANV versus $R/R_{0}$ is
plotted, where $R_{0}$ is the channel cutoff rate. As shown in this figure, by
increasing $R/R_{0}$, the ANV increases as well. Note that around $R/R_{0}=1$,
this curve has a mild slope, whereas for the conventional CCs the ANV curve
has a sharp slope around $R/R_{0}=1$ [15].

##  IX Upper Bound on Distribution of Computation

We consider genie-aided sequential decoding of PAC codes. Let $\gamma_{i}$ and
$\tilde{\gamma}_{i}$ be the $i$th bit metric for the correct and wrong
branches, respectively. In computing $\gamma_{i}$ and $\tilde{\gamma}_{i}$, we
assume that the genie provides the correct bit-channel output
$(\mathbf{y},\mathbf{u}^{i-1})$. Accordingly, the branch metrics for correct
and wrong paths can be calculated as

$\gamma_{i}=\log_{2}\frac{P(\mathbf{y},\mathbf{u}^{i-1}|u_{i})}{P(\mathbf{y},\mathbf{u}^{i-1})}-b_{i}$
(35)

and

$\tilde{\gamma}_{i}=\log_{2}\frac{P(\mathbf{y},\mathbf{u}^{i-1}|\tilde{u}_{i})}{P(\mathbf{y},\mathbf{u}^{i-1})}-b_{i},$
(36)

respectively. By assuming a genie-aided sequential decoder, decoding the
current bit will be independent of what the decoder has decided before. After
decoding a bit (wrongly or correctly), the decoder will use the correct values
of the preceding and current bits provided by the genie to decode the next
bit. In consequence, the decision of every bit is independent of previously
decoded bits. If a codeword is not decoded correctly with a genie-aided
sequential decoder, it would be decoded wrongly without the help of the genie
as well. The genie reveals the actual value of a bit only after finishing the
decoding process of that bit. For this reason, the actual decoder will make
the same decoding errors as the genie-aided decoder. Hence,
$\gamma_{i}\\!\perp\\!\\!\\!\perp\gamma_{j}$ and
$\tilde{\gamma}_{i}\\!\perp\\!\\!\\!\perp\tilde{\gamma}_{j}$ for any $i$ and
$j$, and $i\neq j$, where $\\!\perp\\!\\!\\!\perp$ is used to represent
independency.

As Fig. 29a displays, we define $\tilde{C}_{i}$ as the set of extended nodes
in the $i$th incorrect subtree and $C_{i}$ as the number of computations
needed to decode the $i$th correct node. We have

$C_{i}=1+|\tilde{C}_{i}|.$ (37)

(a)  |  (b)  (c)
---|---
Figure 29: Correct path, wrong path, and incorrect subsets on code tree.

We use the notation $\Gamma_{\text{min}}$ as the minimum partial path metric
of the correct path and $T_{\text{min}}$ as the minimum threshold $T$. For the
Fano algorithm [15, p. 466],

$\Gamma_{\text{min}}<T_{\text{min}}+\Delta.$ (38)

We label nodes in an incorrect subset of Fig. 29a by an ordered pair $(l,m)$
and use $\tilde{\Gamma}_{l,m}$ for its corresponding partial path metric,
where $l$ is the depth of the node and $m$ is its vertical position with any
arbitrary order. When we refer to an arbitrary node in an incorrect set at
depth $l$, we use $\tilde{\Gamma}_{l}$ for its partial path metric. We use the
notation $\tilde{\Gamma}_{l,m,\theta}$ for the corresponding metric of node
$(l,m)$ in an incorrect set when it is visited for the $\theta$th time.
$\tilde{\Gamma}_{l,m}$ is the metric value when visit is for the first time.
$\tilde{\Gamma}_{l}$ is used as the partial path metric of the $l$th depth for
a given incorrect path.

A node $(l,m)$ is able to be extended by the Fano algorithm if its metric
satisfies the threshold ($\tilde{\Gamma}_{l,m}\geq T$). For any specific
threshold $T$, each node can be visited at most once. In any revisiting, the
threshold is always lower than the previous visit by a $\Delta$. In summary,
for a given $\tilde{\Gamma}_{l,m}$, the number of visits $\theta$ of a node
$(m,l)$ has upper bound

$\theta<\big{\lceil}\frac{\tilde{\Gamma}_{l,m}-T_{min}}{\Delta}\big{\rceil}\leq\frac{\tilde{\Gamma}_{l,m}-T_{min}}{\Delta}+1.$
(39)

From (38) and (39) we can conclude that a node $(l,m)$ can be visited for the
$\theta$th time if

$\tilde{\Gamma}_{l,m}>\Gamma_{min}+(\theta-2)\Delta.$ (40)

Consider a random variable $C_{l,m,\theta}$ with Bernoulli distribution which
takes value 1 if node $(m,l)$ is visited for the $\theta$th time ((40) is
satisfied). The number of visits $C_{1}$ has upper bound

$C_{1}\leq\sum_{l=1}^{\infty}\sum_{m}\sum_{\theta=1}^{\infty}C_{l,m,\theta},$
(41)

where $l$ is the depth number, $m$ is the vertical position, and $\theta$ is
the number of revisits of the node $(m,l)$. In the rest of the paper, we try
to obtain an upper bound on the probability of $C_{1}$ being more than a
constant value of $L$.

For a random variable $X$, the moment generating function (MGF) of $X$ is
defined as $g(r):=\mathbb{E}[2^{rX}]$ and the semi-invariant MGF of X is
defined as $h(r):=\log_{2}\big{\\{}\mathbb{E}[2^{rX}]\big{\\}}$. The following
three lemmas will provide upper bounds on the semi-invariant MGF for the bit-
channel metrics on the correct and wrong paths and their differences,
respectively. The proofs are provided in the Appendix.

######  Lemma 1.

Let $h(r_{0})$ be the semi-invariant MGF of the bit-channel metric on the
correct path. Then

$h(r_{0}):=\log_{2}\big{\\{}\mathbb{E}[2^{r\gamma_{i}}]\big{\\}}\leq-
r_{0}b_{i}-(1+r_{0})E_{0}(\frac{-r_{0}}{1+r_{0}},W_{N}^{(i)}),$ (42)

where $r_{0}$ is in $(-1,0)$ interval.

######  Lemma 2.

Let $\tilde{h}(r)$ be the semi-invariant MGF of the bit-channel metric on the
wrong path. We can obtain its upper bound by

$\tilde{h}(r):=\log_{2}\big{\\{}\mathbb{E}[2^{r\tilde{\gamma}_{i}}]\big{\\}}\leq-
rb_{i}-rE_{0}(\frac{1-r}{r},W_{N}^{(i)}),$ (43)

where $r$ is in $(0,1)$ interval.

######  Lemma 3.

The semi-invariant MGF of the difference of bit-channel metrics on the wrong
and the correct paths has an upper bound as

$\log_{2}\big{\\{}\mathbb{E}[2^{r(\tilde{\gamma}_{i}-\gamma_{i})}]\big{\\}}\leq-
rb_{i}-rE_{0}(\frac{1-r}{r},W_{N}^{(i)}),$ (44)

where $r$ is in $(0,1)$ interval, and it is assumed that the bias
$b_{i}\leq\frac{E_{0}(\delta,W_{N}^{(i)})}{\delta}$ for $0<\delta<1$.

With the help of Wald’s identity, we prove the following lemma. The lemma says
that the probability of $\Gamma_{\text{min}}$ being less than a constant value
goes exponentially fast to zero. A small value of $\Gamma_{\text{min}}$ will
result in the chance of the partial path metric on the wrong path being
greater than $\Gamma_{\text{min}}$, which means that the decoder will advance
further in the wrong directions.

######  Lemma 4.

The probability that the minimum partial path metric on the correct path is
less than a constant absorbing barrier $\mu$ is upper bounded as

$P(\Gamma_{\text{min}}\leq\mu)\leq 2^{-r_{0}\mu},$ (45)

where $r_{0}$ is in $(-1,0)$ interval and it is assumed that the bias
$b_{i}\leq\frac{E_{0}(\delta,W_{N}^{(i)})}{\delta}$ for $0<\delta<1$.

Suppose that the correct path segment is shorter than the wrong path segment
(i.e. $n<l$) as shown in Fig. 29b. The following lemma is useful to provide an
upper bound on the probability that the wrong path will be extended further
when $n<l$.

######  Lemma 5.

Assuming $n<l$, we have

$\begin{split}&P(\tilde{\Gamma}_{l}\geq\Gamma_{n}+\alpha)\leq
2^{-r\alpha}2^{-r\sum_{i=1}^{l}\left[E_{0}(\frac{1-r}{r},W_{N}^{(i)})+b_{i}\right]},\end{split}$
(46)

where $0<r<1$ and $b_{i}\leq\frac{E_{0}(\delta,W_{N}^{(i)})}{\delta}$ for
$0<\delta<1$. As an special case, assume that $\alpha=0$, $r=\frac{1}{2}$, and
$b_{i}=E_{0}(1,W_{N}^{(i)})$. Then, $P(\tilde{\Gamma}_{l}\geq\Gamma_{n})$ goes
exponentially to zero with an exponent equal to
$\sum_{i=1}^{l}E_{0}(1,W_{N}^{(i)})$.

Next assume that the correct path segment advances more than the wrong path
segment (i.e. $n\geq l$) as shown in Fig. 29c. The following lemma will
provide an upper bound on the probability that the wrong path will be extended
further when $n\geq l$.

######  Lemma 6.

By assuming that $n\geq l$, we have

$\begin{split}&P(\tilde{\Gamma}_{l}\geq\min_{n\geq
l}\\{\Gamma_{n}\\}+\alpha)\leq
2^{r_{0}\alpha}2^{r_{0}\sum_{i=1}^{l}(E_{0}(\frac{1+r_{0}}{-r_{0}},W_{N}^{(i)})+b_{i})},\end{split}$
(47)

where $r_{0}\in(-1,0)$ and $b_{i}\leq\frac{E_{0}(\delta,W_{N}^{(i)})}{\delta}$
for $0<\delta<1$. Similar to Lemma 5, as an special case, assume that
$\alpha=0$, $r_{0}=\frac{-1}{2}$, and $b_{i}=E_{0}(1,W_{N}^{(i)})$. Then,
$P(\tilde{\Gamma}_{l}\geq\min\\{\Gamma_{n}\\})$ goes exponentially to zero
with an exponent equal to $\sum_{i=1}^{l}E_{0}(1,W_{N}^{(i)})$.

Whenever the partial path metric of any incorrect path at a given depth is
above the $\Gamma_{\text{min}}$, the wrong direction finds the chance to
continue more. The following theorem finds an upper bound on the probability
that latter can happen.

######  Theorem 1.

The probability that the partial path metric of the wrong path is greater than
or equal to the minimum partial path of the correct path by a constant
$\alpha$ is upper bounded as

$\begin{split}&Pr\left[\tilde{\Gamma}_{l}\geq\Gamma_{\text{min}}+\alpha\right]\leq(l+1)2^{-r\alpha}2^{-r\sum_{i=1}^{l}\left[E_{0}(\frac{1-r}{r},W_{N}^{(i)})+b_{i}\right]},\end{split}$
(48)

where it is assumed that $r\in(0,1)$ and
$b_{i}<\frac{E_{0}(\delta,W_{N}^{(i)})}{\delta}$ for $0<\delta<1$. Similarly
for $\alpha=0$, $r=\frac{1}{2}$, and $b_{i}=E_{0}(1,W_{N}^{(i)})$, the upper
bound exponent is $\sum_{i=1}^{l}E_{0}(1,W_{N}^{(i)})$, and the chance of
advancing more than $l$ steps in the wrong path has upper bound which is a
linear function of $l$.

Suppose that the decoder is in the $(l,m)$th node of the decoding tree, where
out of the first $i$ depths $\lambda_{i}$ of them are information bits (the
nodes for which the tree branches) s.t. $1\leq i\leq l$. We define partial
rate as $R_{i}=\frac{\lambda_{i}}{i}$. We can easily see that
$2^{\lambda_{l}}=2^{lR_{l}}$ is an upper bound on the number of incorrect
nodes at depth $l$ of the tree.

Furthermore, assume that

$\sum_{i=1}^{l}R_{i}\leq
r\sum_{i=1}^{l}\left(E_{0}(\frac{1-r}{r},W_{N}^{(i)})+b_{i}\right)-\epsilon,$
(49)

where $\epsilon$ is a small positive number. We would like to mention that by
substituting the parameters used in our simulations, $r=\frac{1}{2}$ and
$b_{i}=E_{0}(1,W_{N}^{(i)})$, the inequality reduces to

$\sum_{i=1}^{l}R_{i}\leq\sum_{i=1}^{l}E_{0}(1,W_{N}^{(i)})-\epsilon.$ (50)

With the conditions mentioned above, the following theorem will give an upper
bound for the $\mathbb{E}[C_{1}],$ which corresponds to the average number of
computations needed to decode the first bit. The average is over data
sequence, the channel noise, and the ensemble of the PAC codes.

By (41), we have

$\begin{split}&\mathbb{E}[C_{1}]\leq\sum_{l=1}^{\infty}\sum_{m}\sum_{\theta=1}^{\infty}\mathbb{E}[C_{l,m,\theta}]\\\
&=\sum_{l=1}^{\infty}\sum_{m}\sum_{\theta=1}^{\infty}P(\tilde{\Gamma}_{l,m}>\Gamma_{min}+(\theta-2)\Delta),\end{split}$
(51)

where $C_{l,m,\theta}$ has a Bernoulli distribution with probability of being
one equal to $P(\tilde{\Gamma}_{l,m}>\Gamma_{min}+(\theta-2)\Delta)$.

######  Theorem 2.

The value $\Delta=\frac{1}{r}$ minimizes the upper bound of
$\mathbb{E}[C_{1}]$ to

$\mathbb{E}[C_{1}]\leq\frac{4}{(1-2^{-\epsilon})^{2}},$ (52)

where $\epsilon$ satisfies (54).

Ultimately, the following theorem gives an upper bound on the CCDF of the bit-
channel computations.

######  Theorem 3.

Suppose that $C_{n}$ is the number of computations required to decode the
$n$th bit. The probability that $C_{n}$ is greater than a constant value $L$
has a Pareto distribution upper bound as

$\begin{split}&P(C_{n}\geq
L)\leq\frac{\mathbb{E}[C_{n}^{\beta}]}{L^{\beta}}\leq\left(\frac{4}{L(1-2^{\frac{-\epsilon}{\beta}})^{2}}\right)^{\beta},\end{split}$
(53)

where $\beta>1$. To proof this we assume that
$b_{i}\leq\frac{E_{0}(\delta,W_{N}^{(i)})}{\delta}$ for $0<\delta<1$ and

$\sum_{i=1}^{l}R_{i}\leq
r\sum_{i=1}^{l}\left(E_{0}(\frac{1-r}{r},W_{N}^{(i)})+b_{i}\right)-\epsilon,$
(54)

where $0<r<1$ and $\epsilon>0$.

##  X Conclusion

In this paper, we derived an optimal metric function on average that uses the
bit-channel mutual information as the bias value, which results in a favorable
trade-off between the performance and the computation of the sequential
decoding of PAC codes. Moreover, we introduced a construction to find good
values of the threshold spacing and scaling parameter of the bias to improve
the error-correction and the computation trade-off for the search-limited and
-unlimited PAC codes. Finally, we proved that by using the bias values less
the bit-channel cutoff rates, the PAC codes’ sequential decoding has a Pareto
distribution upper bound on its computations; this proves the probability of
having a high computation in decoding goes to zero. Using the bit-channel
capacity or cutoff rate as the bit-channel bias values, simulation results
demonstrated that the PAC codes’ superior error-correction performance was
kept while benefiting from the sequential decoding’s low computation.

Finding a tight error-performance upper bound for the PAC codes is a future
study.

###  -A Proof of Lemma 1

$\begin{split}&g(r_{0}):=\mathbb{E}[2^{r_{0}\gamma_{i}}]=\mathbb{E}\left[2^{r_{0}\frac{P(\mathbf{y},\mathbf{u}^{i-1}|u_{i})}{P(\mathbf{y},\mathbf{u}^{i-1})}-r_{0}b_{i}}\right]\\\
&=\mathbb{E}\left[\left(\frac{P(\mathbf{y},\mathbf{u}^{i-1}|u_{i})}{P(\mathbf{y},\mathbf{u}^{i-1})}\right)^{r_{0}}2^{-r_{0}b_{i}}\right]\\\
&=\sum_{u_{i}}q(u_{i})\sum_{(\mathbf{y},\mathbf{u}^{i-1})}P(\mathbf{y},\mathbf{u}^{i-1}|u_{i})\left(\frac{P(\mathbf{y},\mathbf{u}^{i-1}|u_{i})}{P(\mathbf{y},\mathbf{u}^{i-1})}\right)^{r_{0}}2^{-r_{0}b_{i}}\\\
&=2^{-r_{0}b_{i}}\sum_{(\mathbf{y},\mathbf{u}^{i-1})}\underbrace{P(\mathbf{y},\mathbf{u}^{i})^{-r_{0}}}_{a}\underbrace{\sum_{u_{i}}q(u_{i})P(\mathbf{y},\mathbf{u}^{i-1}|u_{i})^{1+r_{0}}}_{b}.\end{split}$
(55)

By defining $s=-r_{0}$ and considering $-1<r_{0}<0$ and using the Cauchy-
Schwarz (CS) inequality

$\sum ab\leq\left(\sum a^{\frac{1}{s}}\right)^{s}\left(\sum
b^{\frac{1}{1-s}}\right)^{1-s},$ (56)

we have

$\begin{split}&g(r_{0})\overset{\text{CS}}{\leq}2^{-r_{0}b_{i}}\left[\underbrace{\sum_{(\mathbf{y},\mathbf{u}^{i-1})}P(\mathbf{y},\mathbf{u}^{i})}_{\text{=
1}}\right]^{s}\\\
&~{}~{}~{}~{}~{}~{}~{}~{}~{}\left[\sum_{(\mathbf{y},\mathbf{u}^{i-1})}\left[\sum_{u_{i}}q(u_{i})P(\mathbf{y},\mathbf{u}^{i-1}|u_{i})^{1-s}\right]^{\frac{1}{1-s}}\right]^{1-s}\\\
&=2^{-r_{0}b_{i}}2^{(1-s)\log_{2}\left[\sum_{(\mathbf{y},\mathbf{u}^{i-1})}\left[\sum_{u_{i}}q(u_{i})P(\mathbf{y},\mathbf{u}^{i-1}|u_{i})^{1-s}\right]^{\frac{1}{1-s}}\right]}\\\
&=2^{-r_{0}b_{i}-(1-s)E_{0}(\frac{s}{1-s},W_{N}^{(i)})}=2^{-r_{0}b_{i}-(1+r_{0})E_{0}(\frac{-r_{0}}{1+r_{0}},W_{N}^{(i)})}.\\\
\end{split}$ (57)

By taking $\log_{2}$ function, we conclude

$h(r_{0})\leq-r_{0}b_{i}-(1+r_{0})E_{0}(\frac{-r_{0}}{1+r_{0}},W_{N}^{(i)}).$
(58)

###  -B Proof of Lemma 2

Consider the MGF $g(\tilde{\gamma}_{i})$.

$\begin{split}&g(\tilde{\gamma}_{i})=\mathbb{E}[2^{r\tilde{\gamma}_{i}}]=\mathbb{E}\left[2^{r\frac{P(\mathbf{y},\mathbf{u}^{i-1}|\tilde{u}_{i})}{P(\mathbf{y},\mathbf{u}^{i-1})}-rb_{i}}\right]\\\
&=\mathbb{E}\left[\left(\frac{P(\mathbf{y},\mathbf{u}^{i-1}|\tilde{u}_{i})}{P(\mathbf{y},\mathbf{u}^{i-1})}\right)^{r}2^{-rb_{i}}\right]\\\
&=\sum_{\tilde{u}_{i}}\sum_{(\mathbf{y},\mathbf{u}^{i-1})}\underbrace{\sum_{u_{i}}q(u_{i})P(\mathbf{y},\mathbf{u}^{i-1}|u_{i})}_{\text{=
$P(\mathbf{y},\mathbf{u}^{i-1})$}}q(\tilde{u}_{i})\\\
&~{}~{}~{}~{}~{}\left(\frac{P(\mathbf{y},\mathbf{u}^{i-1}|\tilde{u}_{i})}{P(\mathbf{y},\mathbf{u}^{i-1})}\right)^{r}2^{-rb_{i}}\\\
&=2^{-rb_{i}}\sum_{(\mathbf{y},\mathbf{u}^{i-1})}\underbrace{P(\mathbf{y},\mathbf{u}^{i-1})^{1-r}}_{b}\underbrace{\sum_{\tilde{u}_{i}}q(\tilde{u}_{i})P(\mathbf{y},\mathbf{u}^{i-1}|\tilde{u}_{i})^{r}}_{a}.\end{split}$
(59)

For $0<r<1$, and using the Cauchy-Schwarz inequality as

$\sum ab\leq\left(\sum a^{\frac{1}{r}}\right)^{r}\left(\sum
b^{\frac{1}{1-r}}\right)^{1-r},$ (60)

we obtain

$\begin{split}&g(\tilde{\gamma}_{i})\leq
2^{-rb_{i}}\left[\underbrace{\sum_{(\mathbf{y},\mathbf{u}^{i-1})}P(\mathbf{y},\mathbf{u}^{i-1})}_{\text{=
1}}\right]^{1-r}\\\
&~{}~{}~{}~{}~{}~{}~{}~{}~{}\left[\sum_{(\mathbf{y},\mathbf{u}^{i-1})}\left[\sum_{\tilde{u}_{i}}q(\tilde{u}_{i})P(\mathbf{y},\mathbf{u}^{i-1}|\tilde{u}_{i})^{r}\right]^{\frac{1}{r}}\right]^{r}\\\
&=2^{-rb_{i}}2^{r\log_{2}\left\\{\sum_{(\mathbf{y},\mathbf{u}^{i-1})}\left[\sum_{\tilde{u}_{i}}q(\tilde{u}_{i})P(\mathbf{y},\mathbf{u}^{i-1}|\tilde{u}_{i})^{r}\right]^{\frac{1}{r}}\right\\}}\\\
&=2^{-rb_{i}-rE_{0}(\frac{1-r}{r},W_{N}^{(i)})}.\end{split}$ (61)

Finally, by taking the $\log_{2}$ function from both sides, the result becomes

$\tilde{h}(r)=\log_{2}g(\tilde{\gamma}_{i})\leq-
rb_{i}-rE_{0}(\frac{1-r}{r},W_{N}^{(i)}).$ (62)

###  -C Proof of Lemma 3

$\begin{split}&\mathbb{E}[2^{r(\tilde{\gamma}_{i}-\gamma_{i})}]=\sum_{u_{i}}\sum_{(\mathbf{y},\mathbf{u}^{i-1})}\sum_{\tilde{u}_{i}}q(u_{i})P(\mathbf{y},\mathbf{u}^{i-1}|u_{i})q(\tilde{u}_{i})\\\
&~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}2^{r(\tilde{\gamma}_{i}-\gamma_{i})}\\\
&=\sum_{u_{i}}\sum_{(\mathbf{y},\mathbf{u}^{i-1})}\sum_{\tilde{u}_{i}}q(u_{i})P(\mathbf{y},\mathbf{u}^{i-1}|u_{i})q(\tilde{u}_{i})\\\
&~{}~{}~{}~{}\left[\frac{P(\mathbf{y},\mathbf{u}^{i-1}|\tilde{u}_{i})}{\cancel{P(\mathbf{y},\mathbf{u}^{i-1})}}\right]^{r}\left[\frac{\cancel{P(\mathbf{y},\mathbf{u}^{i-1})}}{P(\mathbf{y},\mathbf{u}^{i-1}|u_{i})}\right]^{r}\\\
&=\sum_{u_{i}}\sum_{(\mathbf{y},\mathbf{u}^{i-1})}\sum_{\tilde{u}_{i}}q(u_{i})P(\mathbf{y},\mathbf{u}^{i-1}|u_{i})^{1-r}q(\tilde{u}_{i})P(\mathbf{y},\mathbf{u}^{i-1}|\tilde{u}_{i})^{r}\\\
&=\sum_{(\mathbf{y},\mathbf{u}^{i-1})}\underbrace{\sum_{u_{i}}q(u_{i})P(\mathbf{y},\mathbf{u}^{i-1}|u_{i})^{1-r}}_{\text{=
$a$}}\underbrace{\sum_{\tilde{u}_{i}}q(\tilde{u}_{i})P(\mathbf{y},\mathbf{u}^{i-1}|\tilde{u}_{i})^{r}}_{\text{=
$b$}}\\\
&\overset{\text{CS}}{\leq}\left[\sum_{(\mathbf{y},\mathbf{u}^{i-1})}\left[\sum_{u_{i}}q(u_{i})P(\mathbf{y},\mathbf{u}^{i-1}|u_{i})^{1-r}\right]^{\frac{1}{1-r}}\right]^{1-r}\\\
&~{}~{}~{}~{}\left[\sum_{(\mathbf{y},\mathbf{u}^{i-1})}\left[\sum_{\tilde{u}_{i}}q(\tilde{u}_{i})P(\mathbf{y},\mathbf{u}^{i-1}|\tilde{u}_{i})^{r}\right]^{\frac{1}{r}}\right]^{r}\\\
&=2^{(1-r)\log_{2}\left[\sum_{(\mathbf{y},\mathbf{u}^{i-1})}\left[\sum_{u_{i}}q(u_{i})P(\mathbf{y},\mathbf{u}^{i-1}|u_{i})^{1-r}\right]^{\frac{1}{1-r}}\right]}\\\
&~{}~{}~{}~{}2^{r\log_{2}\left[\sum_{(\mathbf{y},\mathbf{u}^{i-1})}\left[\sum_{\tilde{u}_{i}}q(\tilde{u}_{i})P(\mathbf{y},\mathbf{u}^{i-1}|\tilde{u}_{i})^{r}\right]^{\frac{1}{r}}\right]}\\\
&=2^{-(1-r)E_{0}(\frac{r}{1-r},W_{N}^{(i)})}2^{-rE_{0}(\frac{1-r}{r},W_{N}^{(i)})}.\end{split}$
(63)

Assume that the bias $b_{i}<\frac{1-r}{r}E_{0}(\frac{r}{1-r},W_{N}^{(i)})$ for
$0<r<1$ or equivalently $b_{i}<\frac{E_{0}(\delta,W_{N}^{(i)})}{\delta}$ for
$0<\delta=\frac{r}{1-r}<1$. As a result, we have

$\mathbb{E}[2^{r(\tilde{\gamma}_{i}-\gamma_{i})}]\leq
2^{-rb_{i}-rE_{0}(\frac{1-r}{r},W_{N}^{(i)})}.$ (64)

We can conclude the lemma by taking monotonically increasing $\log_{2}$
function from both sides of the inequality.

###  -D Proof of Lemma 4

By taking the derivative of the semi-invariant MGF $h(r_{0})$ we have

$h^{{}^{\prime}}(r_{0})=\frac{g^{{}^{\prime}}(r_{0})}{g(r_{0})}=\frac{\mathbb{E}[\gamma_{i}]}{g(r_{0})}.$
(65)

We know that $g(0)=1$, and at the origin we have that
$h^{{}^{\prime}}(0)=\mathbb{E}[\gamma_{i}]$. By taking the derivative of

$\begin{split}&g(r_{0})=\mathbb{E}[2^{r_{0}\gamma_{i}}]\\\
&=\sum_{u_{i}}q(u_{i})\sum_{(\mathbf{y},\mathbf{u}^{i-1})}P(\mathbf{y},\mathbf{u}^{i-1}|u_{i})\left(\frac{P(\mathbf{y},\mathbf{u}^{i-1}|u_{i})}{P(\mathbf{y},\mathbf{u}^{i-1})}\right)^{r_{0}}2^{-r_{0}b_{i}},\end{split}$
(66)

we have

$\begin{split}&g^{{}^{\prime}}(r_{0})=\sum_{u_{i}}q(u_{i})\sum_{(\mathbf{y},\mathbf{u}^{i-1})}P(\mathbf{y},\mathbf{u}^{i-1}|u_{i})\\\
&~{}~{}~{}~{}\log_{2}\left(\frac{P(\mathbf{y},\mathbf{u}^{i-1}|u_{i})}{P(\mathbf{y},\mathbf{u}^{i-1})}\right)\left(\frac{P(\mathbf{y},\mathbf{u}^{i-1}|u_{i})}{P(\mathbf{y},\mathbf{u}^{i-1})}\right)^{r_{0}}2^{-r_{0}b_{i}}\ln(2)\\\
&~{}~{}~{}~{}-\sum_{u_{i}}q(u_{i})\sum_{(\mathbf{y},\mathbf{u}^{i-1})}P(\mathbf{y},\mathbf{u}^{i-1}|u_{i})\\\
&~{}~{}~{}~{}\left(\frac{P(\mathbf{y},\mathbf{u}^{i-1}|u_{i})}{P(\mathbf{y},\mathbf{u}^{i-1})}\right)^{r_{0}}2^{-r_{0}b_{i}}b_{i}\ln(2).\\\
\end{split}$ (67)

As a result, for $r_{0}=0$ we have

$\begin{split}&g^{{}^{\prime}}(0)=\sum_{u_{i}}q(u_{i})\sum_{(\mathbf{y},\mathbf{u}^{i-1})}P(\mathbf{y},\mathbf{u}^{i-1}|u_{i})\\\
&~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\log_{2}\left(\frac{P(\mathbf{y},\mathbf{u}^{i-1}|u_{i})}{P(\mathbf{y},\mathbf{u}^{i-1})}\right)\ln(2)\\\
&~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}-\sum_{u_{i}}q(u_{i})\sum_{(\mathbf{y},\mathbf{u}^{i-1})}P(\mathbf{y},\mathbf{u}^{i-1}|u_{i})b_{i}\ln(2)\\\
&=I(W_{N}^{(i)})\ln(2)-b_{i}\ln(2).\end{split}$ (68)

A random variable has a negative drift when its expectation is negative and
has a positive drift when its expectation is positive. We see that
$h(0)=\log_{2}(g(0))=0$, and

$h^{{}^{\prime}}(0)=\mathbb{E}[\gamma_{i}]=g^{{}^{\prime}}(0)>0\ \ \ \ \
\text{iff}\ \ \ \ b_{i}<I(W_{N}^{(i)}).$ (69)

Using the upper bound derived in Lemma 1, it can be affirmed that for an
$-1<r_{0}<0$, the semi-invariant MGF $h(r_{0})$ becomes negative if and only
if

$h(r_{0})\leq-
r_{0}b_{i}-(1+r_{0})E_{0}(\frac{-r_{0}}{1+r_{0}},W_{N}^{(i)})<0,$ (70)

where this occurs if and only if

$b_{i}<\frac{1+r_{0}}{-r_{0}}E_{0}(\frac{-r_{0}}{1+r_{0}},W_{N}^{(i)}).$ (71)

So, we can conclude that $h(r_{0})<0$ if and only if

$b_{i}<\frac{E_{0}(\delta,W_{N}^{(i)})}{\delta}~{}~{}~{}~{}s.t.~{}~{}~{}\delta:=\frac{-r_{0}}{1+r_{0}},~{}~{}~{}0<\delta<1.$
(72)

Fig. 30 shows a typical behaviour of the semi-invariant MGF $h(r)$. Because
$P(\gamma_{i}>0)>0$ and $P(\gamma_{i}<0)>0$, obviously we can see that
$h(r)\longrightarrow\infty$ from both sides. We are now equipped to use Wald’s
identity [16, p. 434] to conclude the proof:

Figure 30: Semi-invariant MGF.

Wald’s identity. Let $\\{\gamma_{i};i\geq 1\\}$ be IID r.v’s and
$h(r)=\log_{2}\\{\mathbb{E}[2^{r\gamma_{i}}]\\}$ be the MGF of each
$\gamma_{i}$. Let
$\Gamma_{j}=\sum_{i=1}^{j}\gamma(u_{i};\mathbf{y},\mathbf{u}^{i-1})$ and
$\Gamma_{\text{min}}=\inf\Gamma_{j}$. Then for any $r_{0}<0$ s.t.
$h(r_{0})\leq 0$, and any absorbing barrier $\mu$,

$P(\Gamma_{min}<\mu)\leq 2^{-r_{0}\mu},$ (73)

where $\Gamma_{min}=\inf\Gamma_{L}$ is the infimum of the partial path metric
values on the correct path.

###  -E Proof of Lemma 5

It is assumed that $l>n$.

$\begin{split}&P(\tilde{\Gamma}_{l}\geq\Gamma_{n}+\alpha)=P(2^{r\tilde{\Gamma}_{l}}\geq
2^{r(\Gamma_{n}+\alpha)})\\\
&\overset{\text{CB}}{\leq}\mathbb{E}\left[2^{r\left[\sum_{i=1}^{l}\tilde{\gamma}_{i}-\sum_{i=1}^{n}\gamma_{i}-\alpha\right]}\right]\\\
&=2^{-r\alpha}\prod_{i=1}^{n}\mathbb{E}\left[2^{r(\tilde{\gamma}_{i}-\gamma_{i})}\right]\prod_{i=n+1}^{l}\mathbb{E}\left[2^{r\tilde{\gamma}_{i}}\right]\\\
&\leq
2^{-r\alpha}2^{-r\sum_{i=1}^{n}\left[E_{0}(\frac{1-r}{r},W_{N}^{(i)})+b_{i}\right]}2^{-r\sum_{i=n+1}^{l}\left[E_{0}(\frac{1-r}{r},W_{N}^{(i)})+b_{i}\right]}\\\
&=2^{-r\alpha}2^{-r\sum_{i=1}^{l}\left[E_{0}(\frac{1-r}{r},W_{N}^{(i)})+b_{i}\right]},\end{split}$
(74)

where the first inequality is by Chernoff-bound (CB), the second equality is
by the genie aided decoding assumption, and the second inequality is by Lemma
2 and 3.

###  -F Proof of Lemma 6

It is assumed that $l\leq n$. Furthermore, we define

$\Gamma_{l+1}^{n}:=\sum_{i=l+1}^{n}\gamma_{i}.$ (75)

when $n>l$, and $\Gamma_{l+1}^{n}=0$ when $n=l$. Then, in this case ($l\leq
n$), we have that

$\Gamma_{\text{min}}=\Gamma_{l}+\inf_{\forall n\geq l}\\{\Gamma_{l+1}^{n}\\}.$
(76)

Thereby,

$\begin{split}&P(\tilde{\Gamma}_{l}\geq\Gamma_{\text{min}}+\alpha)=P\left[\tilde{\Gamma}_{l}\geq\Gamma_{l}+\inf\\{\Gamma_{l+1}^{n}\\}+\alpha\right]\\\
&=P\left[\tilde{\Gamma}_{l}-\Gamma_{l}-\alpha-\inf\\{\Gamma_{l+1}^{n}\\}\geq
0\right]\\\
&=\sum_{\mu}P(\tilde{\Gamma}_{l}-\Gamma_{l}-\alpha=\mu)P(\inf\\{\Gamma_{l+1}^{n}\\}\leq\mu)\\\
&\leq\sum_{\mu}P(\tilde{\Gamma}_{l}-\Gamma_{l}-\alpha=\mu)2^{-r_{0}\mu}=\mathbb{E}\left[2^{-r_{0}(\tilde{\Gamma}_{l}-\Gamma_{l}-\alpha)}\right]\\\
&=2^{r_{0}\alpha}\prod_{i=1}^{l}\mathbb{E}\left[2^{-r_{0}(\tilde{\gamma}_{i}-\gamma_{i})}\right]\\\
&\leq
2^{r_{0}\alpha}\prod_{i=1}^{l}2^{r_{0}[E_{0}(\frac{1+r_{0}}{-r_{0}},W_{N}^{(i)})+b_{i}]}\\\
&=2^{r_{0}\alpha}2^{r_{0}\sum_{i=1}^{l}[E_{0}(\frac{1+r_{0}}{-r_{0}},W_{N}^{(i)})+b_{i}]},\end{split}$
(77)

where the first inequality is an application of Wald’s identity and the second
inequality is by Lemma 3.

###  -G Proof of Theorem 1

$\begin{split}&P\left[\tilde{\Gamma}_{l}\geq\Gamma_{\text{min}}+\alpha\right]\\\
&\leq\sum_{n=0}^{l-1}Pr\left[\tilde{\Gamma}_{l}\geq\Gamma_{n}+\alpha\right]+P\left[\tilde{\Gamma}_{l}\geq\Gamma_{l}+\inf\\{\Gamma_{l+1}^{n}\\}+\alpha\right]\\\
&\leq\sum_{n=0}^{l-1}2^{-r\alpha}2^{-r\sum_{i=1}^{l}\left[E_{0}(\frac{1-r}{r},W_{N}^{(i)})+b_{i}\right]}\\\
&~{}~{}~{}~{}+2^{r_{0}\alpha}2^{r_{0}\sum_{i=1}^{l}\left[E_{0}(\frac{1+r_{0}}{-r_{0}},W_{N}^{(i)})+b_{i}\right]}\\\
&=(l+1)2^{-r\alpha}2^{-r\sum_{i=1}^{l}\left[E_{0}(\frac{1-r}{r},W_{N}^{(i)})+b_{i}\right]}\end{split}$
(78)

where the first inequality is by the definition of $\Gamma_{\text{min}}$ and
Boole’s inequality. The second inequality is by Lemma 5 and 6. The last
equality is obtained by assuming $r=-r_{0}$.

###  -H Proof of Theorem 2

$\begin{split}&\mathbb{E}[C_{1}]\leq\sum_{l=1}^{\infty}\sum_{m}\sum_{\theta=1}^{\infty}\mathbb{E}[C_{l,m,\theta}]\\\
&=\sum_{l=1}^{\infty}\sum_{m}\sum_{\theta=1}^{\infty}P(\tilde{\Gamma}_{l,m}>\Gamma_{\text{min}}+(\theta-2)\Delta),\\\
&\leq\sum_{l=1}^{\infty}\sum_{m}\sum_{\theta=1}^{\infty}(l+1)2^{-r\alpha}2^{-r\sum_{i=1}^{l}\left[E_{0}(\frac{1-r}{r},W_{N}^{(i)})+b_{i}\right]}\\\
&=\sum_{l=1}^{\infty}\sum_{m}\sum_{\theta=1}^{\infty}(l+1)2^{-r\alpha}\prod_{i=1}^{l}2^{-r\left[E_{0}(\frac{1-r}{r},W_{N}^{(i)})+b_{i}\right]}\\\
&\leq\sum_{\theta=1}^{\infty}2^{-r\alpha}\sum_{l=1}^{\infty}(l+1)2^{lR_{l}}\prod_{i=1}^{l}2^{-(R_{i}+\epsilon)}\\\
&\leq\sum_{\theta=1}^{\infty}2^{-r\alpha}\sum_{l=1}^{\infty}(l+1)\left[2^{-\epsilon}\right]^{l}\leq\sum_{\theta=1}^{\infty}2^{-r\alpha}\frac{1}{(1-2^{-\epsilon})^{2}}\\\
&=\sum_{\theta=1}^{\infty}2^{-r(\theta-2)\Delta}\frac{1}{(1-2^{-\epsilon})^{2}}=\frac{2^{r\Delta}}{1-2^{-r\Delta}}\frac{1}{(1-2^{-\epsilon})^{2}},\end{split}$
(79)

for $\alpha=(\theta-2)\Delta$. The second inequality is by Theorem 1. The
third inequality is by (54) and the upper bound on the number of incorrect
nodes at depth $l$ of the decoding tree. The infinite sigma on the depth of
the tree $l$ is convergent if and only if $\epsilon$ is positive as we assumed
it.

The value $\Delta=\frac{1}{r}$ minimizes the upper bound. So we have

$\mathbb{E}[C_{1}]\leq\frac{4}{(1-2^{-\epsilon})^{2}}.$ (80)

###  -I Proof of Theorem 3

For $\beta>1$, probabilties $Q_{j}$, and a set of nonnegative numbers
$a_{jk}$, the Minkowski inequality (MI) is as

$\left[\sum_{j}Q_{j}\left(\sum_{k}a_{jk}\right)^{\beta}\right]^{1/\beta}\leq\sum_{k}\left(\sum_{j}Q_{j}a_{jk}^{\beta}\right)^{1/\beta}.$
(81)

By (51) and using Minkowski inequality we get the result of

$\begin{split}&(\mathbb{E}[C_{1}^{\beta}])^{1/\beta}\leq\left[\mathbb{E}\left(\left[\sum_{l=1}^{\infty}\sum_{m}\sum_{\theta=1}^{\infty}C_{l,m,\theta}\right]^{\beta}\right)\right]^{1/\beta}\\\
&\overset{\text{MI}}{\leq}\sum_{l=1}^{\infty}\sum_{m}\sum_{\theta=1}^{\infty}\left(\mathbb{E}\left[(C_{l,m,\theta})^{\beta}\right]\right)^{1/\beta}.\end{split}$
(82)

Because $C_{l,m,\theta}$ is a random variable with Bernoulli distribution,
$(C_{l,m,\theta})^{\beta}=C_{l,m,\theta}$. Similar to the proof of the
previous theorem we have

$\begin{split}&(\mathbb{E}[C_{1}^{\beta}])^{1/\beta}\leq\sum_{l=1}^{\infty}\sum_{m}\sum_{\theta=1}^{\infty}\left(\mathbb{E}\left[(C_{l,m,\theta})^{\beta}\right]\right)^{1/\beta}\\\
&=\sum_{l=1}^{\infty}\sum_{m}\sum_{\theta=1}^{\infty}P\left[\tilde{\Gamma}_{l}\geq\Gamma_{\text{min}}+(\theta-2)\Delta\right]^{1/\beta}\\\
&\leq\sum_{l=1}^{\infty}\sum_{m}\sum_{\theta=1}^{\infty}(l+1)^{1/\beta}2^{-\frac{r\alpha}{\beta}}2^{-\frac{r}{\beta}\sum_{i=1}^{l}\left[E_{0}(\frac{1-r}{r},W_{N}^{(i)})+b_{i}\right]}\\\
&=\sum_{l=1}^{\infty}\sum_{m}\sum_{\theta=1}^{\infty}(l+1)^{1/\beta}2^{-\frac{r\alpha}{\beta}}\prod_{i=1}^{l}2^{-\frac{r}{\beta}\left[E_{0}(\frac{1-r}{r},W_{N}^{(i)})+b_{i}\right]}\\\
&\leq\sum_{\theta=1}^{\infty}2^{-\frac{r\alpha}{\beta}}\sum_{l=1}^{\infty}(l+1)^{1/\beta}2^{lR_{l}}\prod_{i=1}^{l}2^{-(\frac{R_{i}+\epsilon}{\beta})}\\\
&\leq\sum_{\theta=1}^{\infty}2^{-\frac{r\alpha}{\beta}}\sum_{l=1}^{\infty}(l+1)^{1/\beta}\left[2^{\frac{-\epsilon}{\beta}}\right]^{l}\leq\sum_{\theta=1}^{\infty}2^{-\frac{r\alpha}{\beta}}\frac{1}{(1-2^{\frac{-\epsilon}{\beta}})^{2}}\\\
&=\sum_{\theta=1}^{\infty}2^{\frac{-r(\theta-2)\Delta}{\beta}}\frac{1}{(1-2^{\frac{-\epsilon}{\beta}})^{2}}=\frac{2^{\frac{r\Delta}{\beta}}}{1-2^{\frac{-r\Delta}{\beta}}}\frac{1}{(1-2^{\frac{-\epsilon}{\beta}})^{2}}.\end{split}$
(83)

The value of $\beta$ should be chosen such that the following condition is
satisfied.

$\beta lR_{l}\leq\sum_{i=1}^{l}R_{i}.$ (84)

The value of $\Delta=\frac{\beta}{r}$ threshold spacing will minimize the
upper bound and we can have

$(\mathbb{E}[C_{1}^{\beta}])^{1/\beta}\leq\frac{4}{(1-2^{\frac{-\epsilon}{\beta}})^{2}}.$
(85)

Due to the symmetry of the problem, the same bound is valid for any node.
Finally, using the generalized Chebyshev-inequality, we have

$P(C_{n}\geq L)\leq\frac{\mathbb{E}[C_{n}^{\beta}]}{L^{\beta}}.$ (86)

## References

  * [1] E. Arıkan, “From sequential decoding to channel polarization and back again,” _arXiv preprint arXiv:1908.09594_ , 2019.
  * [2] Y. Polyanskiy, H. V. Poor, and S. Verdú, “Channel coding rate in the finite blocklength regime,” _IEEE Transactions on Information Theory_ , vol. 56, no. 5, pp. 2307–2359, 2010.
  * [3] M. Moradi, A. Mozammel, K. Qin, and E. Arıkan, “Performance and complexity of sequential decoding of PAC codes,” _arXiv preprint arXiv:2012.04990_ , 2020.
  * [4] F. Brannstrom, L. K. Rasmussen, and A. J. Grant, “Convergence analysis and optimal scheduling for multiple concatenated codes,” _IEEE Transactions on Information Theory_ , vol. 51, no. 9, pp. 3354–3364, 2005.
  * [5] F. Brannstrom, “Convergence analysis and design of multiple concatenated codes.” 2004.
  * [6] H. Li and J. Yuan, “A practical construction method for polar codes in AWGN channels,” in _IEEE 2013 Tencon-Spring_. IEEE, 2013, pp. 223–226.
  * [7] R. G. Gallager, _Information Theory and Reliable Communication_. New York: Wiley, 1968\.
  * [8] M. Alsan and E. Telatar, “Polarization improves ${E}_{0}$,” _IEEE Transactions on Information Theory_ , vol. 60, no. 5, pp. 2714–2719, 2014.
  * [9] R. Fano, “A heuristic discussion of probabilistic decoding,” _IEEE Transactions on Information Theory_ , vol. 9, no. 2, pp. 64–74, 1963.
  * [10] A. Mozammel, “Hardware implementation of Fano decoder for PAC codes,” _arXiv preprint arXiv:2011.09819_ , 2020.
  * [11] J. Massey, “Variable-length codes and the Fano metric,” _IEEE Transactions on Information Theory_ , vol. 18, no. 1, pp. 196–198, 1972.
  * [12] E. Arıkan, “Polarization adjusted convolutional codes,” _submitted to IEEE Comm. Letters, 1 Oct._ , 2020.
  * [13] I. Tal and A. Vardy, “List decoding of polar codes,” _IEEE Transactions on Information Theory_ , vol. 61, no. 5, pp. 2213–2226, 2015.
  * [14] I. M. Jacobs and J. Wozencraft, “Principles of Communication Engineering.” 1965.
  * [15] J. M. Wozencraft, “Sequential decoding for reliable communication,” 1957.
  * [16] R. G. Gallager, _Stochastic Processes: Theory for Applications_. Cambridge University Press, 2013.