#
Channel Coding at Low Capacity111A brief version of this paper has been
presented in 2019 IEEE Information Theory Workshop (ITW) [1].

Mohammad Fereydounian
University of Pennsylvania
3401 Walnut St, Philadelphia, PA 19104
<EMAIL_ADDRESS>
Hamed Hassani
University of Pennsylvania
3401 Walnut St, Philadelphia, PA 19104
<EMAIL_ADDRESS>
Mohammad Vahid Jamali
University of Michigan
1301 Beal Avenue, Ann Arbor, MI 48109
<EMAIL_ADDRESS>
Hessam Mahdavifar
University of Michigan
1301 Beal Avenue, Ann Arbor, MI 48109
<EMAIL_ADDRESS>

###### Abstract

Low-capacity scenarios have become increasingly important in the technology of
the Internet of Things (IoT) and the next generation of mobile networks. Such
scenarios require efficient and reliable transmission of information over
channels with an extremely small capacity. Within these constraints, the
performance of state-of-the-art coding techniques is far from optimal in terms
of either rate or complexity. Moreover, the current non-asymptotic laws of
optimal channel coding provide inaccurate predictions for coding in the low-
capacity regime. In this paper, we provide the first comprehensive study of
channel coding in the low-capacity regime. We will investigate the fundamental
non-asymptotic limits for channel coding as well as challenges that must be
overcome for efficient code design in low-capacity scenarios.

##  1 Introduction

Low-capacity scenarios have become increasingly important in the technology of
the Internet of Things (IoT) and the next generation of mobile networks. In
particular, these scenarios have emerged in two extremes of wireless
communications: narrowband and wideband communications. The former is widely
considered for deploying IoT in cellular networks where a massive number of
users need to be served [2], and the latter models the communication in the
millimeter-Wave (mmWave) band which is one of the key innovations of the next
generation of cellular networks (5G) [3]. From the channel modeling
perspective, it turns out that users operating in these two different
applications typically experience very low signal-to-noise ratios (SNRs).
Therefore, studying fundamental limits as well as practical code construction
is required to address the challenges of wireless system design for these
emerging applications.

The Third Generation Partnership Project (3GPP) has introduced new features
into the Long-Term Evolution (LTE) standard to IoT into the cellular network.
These new features, called Narrow-Band IoT (NB-IoT) and enhanced Machine-Type
Communications (eMTC), have been introduced in the release 13 of LTE.
Consequently, it is expected that the total number of IoT devices supported
through cellular networks will reach 1.5 billion by 2021 [2]. To ensure high
coverage, the standard has to support coupling losses as large as $170$ dB for
these applications, which is approximately $20$ dB higher than that of the
legacy LTE. As stated in [2, 4], tolerating such coupling losses requires
reliable detection for a typical $-13$ dB of effective SNR, translated to
capacity $\approx 0.03$ bits/transmission. To enable reliable communication in
such low-SNR regimes, LTE has adopted a legacy Turbo code of rate $1/3$ in
eMTC and NB-IoT (uplink) as the mother code together with many repetitions.
The standard allows up to 2048 repetitions to enable the maximum coverage
requirements, thereby supporting effective code rates as low as $1.6\times
10^{-4}$ [2]. However, from a channel coding perspective, repeating a high-
rate code to enable low-rate communication can be very sub-optimal.

Surprisingly, a similar situation arises in wideband scenarios, and in
particular in the mmWave band. In the simplest model for a wideband channel,
transmission takes place over an additive white Gaussian noise (AWGN) channel
with the capacity $C=B\log(1+{P}/{(N_{0}B)})$, where $P$ is the signal power,
$N_{0}$ is the noise variance, and $B$ is the allocated bandwidth. Assuming a
limited transmission power $P$ and high bandwidth $B\rightarrow\infty$, we
operate in the low-capacity regime–in terms of the underlying channel code
rate per symbol. Note that this is not in contrast with the high data rates,
in terms of bits per second, of wideband applications. In other words, as $B$
grows large, we can transmit a growing number of symbols in a fixed time
interval. However, these symbols experience a vanishing SNR when the total
power is fixed. More specifically, we have $SNR\rightarrow 0$ as
$B\rightarrow\infty$.

Most of classical channel coding theory is centered on the designs of point-
to-point error-correcting codes, assuming an underlying channel with a certain
capacity $C>0$. However, since $C$ is only asymptotically achievable, recently
there has been a large body of work to study the _finite-length_ performance:
given a fixed block error probability $p_{e}$, what is the maximum achievable
rate $R$ in terms of the blocklength $n$? This question has been of interest
to information theorists since the early years of information theory [5, 6],
and a precise characterization is provided in [7] as
$R=C-\sqrt{{V}/{n}}Q^{-1}(p_{e})+\mathcal{O}\left({\log n}/{n}\right),$ where
$Q(\cdot)$ is the tail probability of the standard normal distribution, and
$V$ is a characteristic of the channel referred to as channel dispersion. In
recent years, this non-asymptotic law is specified up to the third and later
to the fourth-order for particular channels including BEC, BSC, and AWGN (see
[8, Theorems 41,44], [9, 10, 11, 12, 13]).

Such non-asymptotic laws have steered optimal code design for channels with
moderate values of $C$. However, very little is known about optimal code
design in the low-capacity regime, where channel capacity $C$ could be
extremely small (e.g. as small as $\mathcal{O}(1/n)$) and hence, the first-
order and the second-order terms of the law could be as small as the third-
order and the fourth-order terms. In other words, for a given $C$, the
prediction based on normal approximation, e.g., [7], after discarding the
$\mathcal{O}(1)$ term, becomes more and more accurate as $n$ grows large where
the $\mathcal{O}(1)$ term becomes less and less relevant. However, when $C$ is
extremely small, even at moderate blocklengths, from coding application
perspective, e.g., $C=0.01$ and $n$ being between $1000$ and $10000$, the
$\mathcal{O}(1)$ term is still well comparable even with the first-order term
$nC$ leading to imprecise predictions by the normal approximation. Optimal
code design in the low-capacity regime, defined explicitly in Section 3,
requires addressing various theoretical and practical challenges.

From the theoretical standpoint, channel variations in the low-capacity regime
may be better approximated by different probabilistic laws rather than the
ones used for typical channels. For instance, consider transmission over
BEC($\epsilon$) with blocklength $n$. When the erasure probability $\epsilon$
is not very close to $1$ (e.g., $\epsilon=0.5$), the number of non-erased bits
will be governed by the central limit theorem and behaves as
$nC+\sqrt{n\epsilon(1-\epsilon)}Z$, where $Z$ is the standard normal random
variable. However, in the low-capacity regime, when the capacity
$C=1-\epsilon$ is very small, although $n$ is large, the number of channel
non-erasures will not be large since a non-erasure occurs with small
probability $1-\epsilon$. In other words, the average number of non-erased
bits is $n(1-\epsilon)$ which can be a constant or a number much smaller than
$n$. Hence, the number of non-erasures will be best approximated by the law of
rare events or the so-called Poisson convergence theorem rather than the
central limit theorem.

From the design standpoint, we need to construct efficient codes with
extremely low rates. Such constraints render the state-of-the-art codes and
their advantages, in terms of decoding complexity and latency, inapplicable.
For instance, it is well known that low-rate iterative codes have highly dense
Tanner graphs which significantly deteriorates the performance (as there are
many short cycles) as well as the computational complexity. Polar codes [14]
can naturally be adapted to the low-rate regime, however, the current
implementation of these codes suffers from relatively high computational
complexity and latency. Note that there is a subtle difference between the
low-rate regime and the moderate-rate regime when characterizing the behavior
of complexity and latency of decoders. These parameters are often described as
functions of code blocklength $n$ and, in the moderate-rate regime, result in
the same expression if we replace $n$ by the number of information bits $k$
which scales linearly with $n$. However, this does not necessarily hold for
the low-rate regime as $k$ is significantly smaller than $n$. For instance,
the decoding complexity and latency of polar codes are known to be
$\mathcal{O}(n\log n)$ and $\mathcal{O}(n)$, respectively [14]. While this is
reasonable when $k$ scales linearly with $n$, it becomes inefficient when $k$
is a sub-linear function of $n$. We essentially need low-latency decoders, in
terms of $k$, in order to provide high data rates, in terms of bits per second
(b/s), in wideband applications. We also need low-complexity decoders to
provide low device unit cost and low power consumption for narrowband
applications. In practice, the proposed solution for NB-IoT code design is
simply to apply many repetitions on an underlying code such as a Turbo code or
a polar code. Even though this approach leads to efficient implementations,
the rate loss through many repetitions will result in codes with mediocre
performance.

This paper provides the first comprehensive study of channel coding in the
low-capacity regime. In Section 2, we will provide the necessary background.
In Section 3, we will formally define the low-capacity regime and provide
fundamental non-asymptotic laws of channel coding for a diverse set of
channels with practical significance: the binary erasure channel, the binary
symmetric channel, and the additive white Gaussian channel. Section 4
considers various approaches to practical code design in the low-capacity
regime with numerical comparisons with the non-asymptotic bounds derived in
Section 3 as well as the codes used in the NB-IoT standard.

##  2 Preliminaries

In this section, we will review the main concepts of channel coding in the
non-asymptotic regime along with a brief review of previous works.222For more
details, we refer the reader to [15] for an excellent review on this topic.
For an input alphabet $\mathcal{X}$ and an output alphabet $\mathcal{Y}$, a
channel $W$ can be defined as a conditional distribution on $\mathcal{Y}$
given $\mathcal{X}$. An $(M,p_{e})$-code for the channel $W$ is characterized
by a message set $\mathcal{M}=\\{1,2,\cdots,M\\}$ , an encoding function
$f_{enc}:\mathcal{M}\rightarrow\mathcal{X}$ and a decoding function
$f_{dec}:\mathcal{Y}\rightarrow\mathcal{M}$ such that the _average_
probability of error does not exceed $p_{e}$, that is333In this paper we only
consider the average probability of error. Similar results can be obtained for
maximum probability of error.

$\frac{1}{M}\sum_{m\in\mathcal{M}}W\left(\mathcal{Y}\setminus
f_{dec}^{-1}(m)\,\big{|}\,f_{enc}(m)\right)\leq p_{e}.$

Accordingly, an $(M,p_{e})$-code for the channel $W$ over $n$ _independent
channel uses_ can be defined by replacing $W$ with $W^{n}$ in the definition.
The blocklength of the code is defined as the number of channel uses and is
similarly denoted by $n$. For the channel $W$, the maximum code size
achievable with a given error probability $p_{e}$ and blocklength $n$ is
denoted by

$M^{*}(n,p_{e})=\max\left\\{M\mid\exists(M,p_{e})\text{-code for
}W^{n}\right\\}.$

In this paper, we consider three classes of channels that vary in nature:

  * •

BEC($\epsilon$): binary erasure channel with erasure probability $\epsilon$.

  * •

BSC($\delta$): binary symmetric channel with crossover probability $\delta$.

  * •

AWGN($\eta$): additive white Gaussian noise channel with signal-to-noise ratio
(SNR) $\eta$.

Let us further clarify our description of coding over the AWGN channel. We
consider $n$ uses of the channel in which the input $X_{i}$ and the output
$Y_{i}$ at each $i=1,\dots,n$ are related as $Y_{i}=X_{i}+Z_{i}$. Here, the
noise term $\left\\{Z_{i}\right\\}_{i=1}^{n}$ is a memoryless, stationary
Gaussian process with zero mean and unit variance. Given an $(M,p_{e})$-code
for $W^{n}$, where $W$ is the AWGN channel, a cost constraint on the codewords
must be applied. The most commonly used cost is

$\forall
m\in\mathcal{M}:\quad\left\|f_{enc}(m)\right\|_{2}^{2}=\sum_{i=1}^{n}\left(f_{enc}(m)\right)_{i}^{2}\leq\eta\,n,$

where $\eta$, with a slight abuse of notation, refers to SNR. Since,
characterization of the code depends on the SNR $\eta$, we denote an
$(M,p_{e})$-code and $M^{*}(n,p_{e})$ by $(M,p_{e},\eta)$-code and
$M^{*}(n,p_{e},\eta)$, respectively. For each of the channels considered
above, from the channel coding and strong converse theorem due to [16, 17], we
know that

$\lim_{n\rightarrow\infty}\frac{1}{n}\log_{2}M^{*}(n,p_{e})=C.$

Thus the first order term in the non-asymptotic expansion of $M^{*}(n,p_{e})$
is $nC$. The higher order terms in the non-asymptotic expansion of
$M^{*}(n,p_{e})$ is given as [7, 18]

$\log_{2}M^{*}(n,p_{e})=nC-\sqrt{nV}Q^{-1}(p_{e})+\mathcal{O}(\log_{2}n),$ (1)

where $V$ is the channel dispersion and $Q^{-1}(.)$ is the inverse of
Q-function where Q-function is defined as

$Q(\alpha)=\frac{1}{\sqrt{2\pi}}\int_{\alpha}^{\infty}e^{-\frac{x^{2}}{2}}dx.$

The third and higher order terms in the non-asymptotic expansion of
$M^{*}(n,p_{e})$, however, depends on the particular channel under discussion
(See [8, Theorem 41, 44, 73], [10, 11, 12, 13]). More specifically, for
BEC($\epsilon$), we have $C=1-\epsilon$, $V=\epsilon(1-\epsilon)$ and the
third order term is $\mathcal{O}(1)$. For BSC($\delta)$, we have
$C=1-h_{2}(\delta)$, $V=\delta(1-\delta)\log_{2}^{2}({(1-\delta)}/{\delta})$,
and the third order term is $1/2\log_{2}n+\mathcal{O}(1)$. For AWGN($\eta$),
we have $C=1/2\log_{2}(1+\eta)$,
$V=\eta(\eta+2)/\left(2(\eta+1)^{2}\ln^{2}2\right)$, and the third order term
is bounded between $\mathcal{O}(1)$ and $1/2\log_{2}n+\mathcal{O}(1)$, i.e.,
the third order term is $\mathcal{O}(\log_{2}n)$.

In this paper, we investigate code design over channels with very low
capacity. Even though the formula (1) can still be used in the low-capacity
regime, it provides a very loose approximation as (i) the channel variations
in the low-capacity regime are governed by different probabilistic laws than
the ones used to derive (1), and (ii) some of the terms hidden in
$\mathcal{O}(\log n)$ will have significantly higher values and are comparable
to the first and second terms. In the next section, we will provide non-
asymptotic laws for the low-capacity regime.

##  3 Fundamental Limits

The Low-Capacity Regime. Consider the transmission over a channel $W$ with a
capacity $C$. Let $k$ denote the number of information bits to be sent and $n$
denote the blocklength of tfhe code. In _informal_ terms, the low-capacity
regime refers to scenarios in which the channel capacity $C$ is very small.
Indeed, to reliably communicate $k$ bits, we clearly must have $n\geq k/C$ and
thus $n$ is a fixed and finite number but fairly large.

For instance, consider the narrowband and wideband applications discussed in
Section 1, where the number of information bits $k$ varies between a few tens,
in narrowband, to a few thousand, in wideband, and the channel capacity $C$ is
typically below $0.05$. This makes $n$ to vary between a few thousand to
several tens of thousands. For instance, if $k=50$ and $C=0.02$, then the
blocklength $n$ is at least $2500$.

A practical situation for the low-capacity regime is illustrated next.
Consider a wideband AWGN channel with the channel capacity given as
$C=B\log(1+{P}/{(N_{0}B)})$ with a fixed total power $P$ and large bandwidth
$B$. A wideband user wishes to communicate $k$ bits over this channel in a
fixed time frame of duration $T$ seconds. In this scenario, by Nyquist-Shannon
sampling theorem, $2BT$ symbols can be transmitted in the given time frame.
Suppose that a simple binary phase-shift keying (BPSK) modulation is deployed.
Hence, the length of the transmitted codeword is $n=2BT$ which is finite but
large. As a result, each bit is transmitted through a channel with capacity
${1}/{2}\log(1+\text{SNR})=\mathcal{O}({1}/{n})$ and the user wishes to
transmit $k=\mathcal{O}(1)$ bits over this channel (note that
$\text{SNR}={P}/{(N_{0}B)}=\mathcal{O}({1}/{n})$). This implies that the
wideband user is operating in an extreme case of the low-capacity regime.

In order to proceed with a _formal_ and _general_ definition of the low-
capacity regime, we need to provide a formal characterization of the term
“low” in the non-asymptotic setting where all the parameters such as $C$ and
$n$ are assumed to be fixed and finite quantities.

######  Definition 1.

Suppose $f:\mathbb{N}\rightarrow\mathbb{R}_{+}$ is a decreasing positive real-
valued function on positive integers such that
$\lim_{n\rightarrow\infty}f\left(n\right)=0$ and let $C$ and $n$ be given
fixed quantities. Then the transmission over a channel $W$ with capacity $C$
and blocklength $n$ is called to be in an $f$-based low-capacity regime if
$C<f(n)$.

######  Remark 1.

Note that the low-capacity regime introduced in Definition 1, does not
consider a variant capacity or blocklength but rather quantifies how _low_ the
capacity is with respect to the blocklength telling us which terms can be
neglected in the analysis. However, sweeping among values of $n$ determines
corresponding acceptable values of $C$. As a result, considering $C$ and $n$
as variables, we can now relate them using the $\mathcal{O}(.)$ or $o(.)$
notations. Therefore, the first purpose of Definition 1 is to formalize the
term _low_ before using the $\mathcal{O}(.)$ (or $o(.)$) notation to clarify
and emphasize that the setting is not variant. The second purpose of such a
definition is to introduce a general and flexible platform so that it can be
applicable to various analytical and practical applications. This achieved by
considering a general $f$. However, specific range of $f$ works well enough
for most practical settings.

######  Remark 2.

Throughout this paper, we define $\kappa:=nC$ and consider $n$ and $C$ as
”variables” which can take any given fixed values. Having this, any relation
between $n$ and $C$ can be translated as a relation between $n$ and $\kappa$.
In the BEC case, the inequalities are valid for any range of $\kappa$ and thus
the results are valid for any $f$-based low-capacity regime.
In the BSC case, we consider a low-capacity regime in which
$\kappa\sqrt{\kappa}=o(n)$ (the justification of using the $o(.)$ notation is
explained in Remark 1). This condition is equivalent to $C=o(n^{-1/3})$ and
some examples are $C=\mathcal{O}(1/n)$ (equivalently, $\kappa=\mathcal{O}(1)$)
and $C=\mathcal{O}(1/\sqrt{n})$ (equivalently,
$\kappa=\mathcal{O}(\sqrt{n})$). Moreover, an equivalent formal condition that
matches Definition 1 is to consider $f$-based low-capacity regimes where $f$
belongs to the following class of functions:
$\left\\{f:\mathbb{N}\rightarrow\mathbb{R}_{+}\mid
f(n)=n^{s},s<-1/3\right\\}$.
Further, we omit the term ”$f$-based” and simply use ”low-capacity regime” for
the rest of this paper.

Why the laws should be different in the low-capacity regime? Let us now
explain why the current non-asymptotic laws of channel coding provided in (1)
are not applicable in the low-capacity regime. Consider transmission over
BEC($\epsilon$) with blocklength $n$. When the erasure probability $\epsilon$
is not so large (e.g., $\epsilon=0.5$), the number of channel non-erasures
will be governed by the central limit theorem and behaves as
$nC+\sqrt{n\epsilon(1-\epsilon)}Z$, where $Z$ is the standard normal random
variable. However, in the low-capacity regime, where the capacity
$C=1-\epsilon$ is very small, the number of channel non-erasures will not be
large, as the probability of non-erasure is very small. In other words, the
expected number of non-erasures is $\kappa=n(1-\epsilon)$ which is much
smaller than $n$. In this case, the number of non-erasures is best
approximated by the Poisson convergence theorem (i.e., the law of rare events)
rather than the central limit theorem. Such behavioral differences in the
channel variations will lead to totally different non-asymptotic laws, as we
will see below.

Another reason for (1) being loose is that some of the terms that are
considered as $\mathcal{O}(1)$ become significant in the low-capacity regime.
E.g., we have $1/(\sqrt{n}C)\\!=\\!\sqrt{n}/(nC)\\!=\\!\\!\sqrt{n}/\kappa$
which cannot be considered as $o(1)$ as $\kappa$ is usually much smaller than
$n$. As we will see, such terms can be captured by using sharper tail bounds.

Our approach. Note that extremely tight converse and achievability bounds for
BEC and BSC have existed prior to [8, 7] and stated as [8, Corollary 42,
Theorem 43] for BEC and [8, Corollary 39, Theorem 40] for BSC. These bounds
are in a raw implicit form. The novel contribution of [8, 7] is using normal
approximations and probability tail bounds to convert these implicit forms
into explicit ones directly relating $\log_{2}M^{*}(n,p_{e})$ to $n$, $p_{e}$.
This procedure works well for moderate values of $C$ with respect to $n$ but
fails to provide accurate estimates in the low-capacity setting considered in
this paper. In order to provide an accurate estimate, we need novel
probabilistic laws which are, in some cases such as the BEC, totally different
than what has been used before. Our approach can be summarized as follows: our
starting points are the same as [8, 7], i.e., we start with [8, Corollary 42,
Theorem 43] for BEC and [8, Corollary 39, Theorem 40] for BSC, but our
analysis is based on Poisson approximations (for BEC) and much tighter
probability tail bounds (for BSC) which are specifically suitable for the low-
capacity regime but not necessary for moderate values of $C$. These novel
approaches in analysis lead to the low-capacity coding bounds for BEC and BSC
stated in the following subsections. Proofs of the theorems together with
related lemmas are provided in the Appendix.

###  3.1 The Binary Erasure Channel

As discussed earlier, the behavior of channel variations for the BEC in the
low-capacity regime can be best approximated through the Poisson convergence
theorem for rare events. This will lead to different (i.e., more accurate)
non-asymptotic laws. The following theorem provides lower and upper bounds for
the best achievable rate in terms of $n$, $p_{e}$, $\epsilon$, and
$\kappa:=n(1-\epsilon)$. We use $\mathcal{P}_{\lambda}(x)$ to denote the
Poisson cumulative distribution function, i.e.,

$\mathcal{P}_{\lambda}(x)=\text{Pr}\left\\{X<x\right\\},\qquad\text{where
}X\sim\text{Poisson}(\lambda).$ (2)

######  Theorem 1 (Non-Asymptotic Coding Bounds for Low-Capacity BEC).

Consider transmission over ${\rm{BEC}}(\epsilon)$ in low-capacity regime and
let $\kappa=n(1-\epsilon)$. Then,

$M_{1}\leq M^{*}(n,p_{e})\leq M_{2},$

where $M_{1}$ is the solution of

$\mathfrak{P}_{1}(M_{1})+\alpha\sqrt{\mathfrak{P}_{1}(M_{1})}-p_{e}=0,$ (3)

and $M_{2}$ is the solution of

$\mathfrak{P}_{2}(M_{2})-\alpha\sqrt{\mathfrak{P}_{2}(M_{2})}-\alpha\sqrt{\mathcal{P}_{\kappa}(\log_{2}M_{2})}-p_{e}=0,$
(4)

and

$\displaystyle\mathfrak{P}_{1}(M_{1})$
$\displaystyle=\mathcal{P}_{\kappa}(\log_{2}M_{1})+M_{1}e^{-\kappa/2}\left(1-\mathcal{P}_{\kappa/2}(\log_{2}M_{1})\right),$
$\displaystyle\mathfrak{P}_{2}(M_{2})$
$\displaystyle=\mathcal{P}_{\kappa}(\log_{2}M_{2})-\frac{e^{\kappa}}{M_{2}}\,\mathcal{P}_{2\kappa}\left(\log_{2}M_{2}\right),$
$\displaystyle\alpha$
$\displaystyle=\frac{\sqrt{2}}{\epsilon^{3/2}}\left(1+2\sqrt{\frac{3}{\epsilon\kappa}}\right)\left(\sqrt{e}-1\right)(1-\epsilon).$

###### Proof.

See Section 5.1 in the Appendix. ∎

The bounds in Theorem 1 are tight and can be computed accurately (see Section
5.2). The bounds are expressed merely in terms of $\kappa:=n(1-\epsilon)$
rather than $n$. This agrees with the intuition that the rate should depend on
the amount of “information” passed through $n$ usages of the channel rather
than the number of channel uses $n$. Typically, the value of $\kappa$ in low-
capacity applications varies between a few tens to few hundred. In such a
range, no simple, closed-form approximation of the Poisson distribution with
mean $\kappa$ exists. As a result, the lower and upper bounds in Theorem 1
cannot be simplified further. Also, one can turn these bounds into bounds on
the shortest (optimal) lengths $n^{*}$ needed for transmitting $k$ information
bits with error probability $p_{e}$ over a low-capacity BEC. In Section 4.3 we
numerically evaluate the lower and upper bounds predicted by Theorem 1 and
compare them with the prediction obtained from Formula (1) [7]. It is observed
that our predictions are significantly more precise compared to the prediction
obtained from Formula (1) and they become even more precise as the capacity
approaches zero.

###  3.2 The Binary Symmetric Channel

Unlike BEC, the non-asymptotic behavior of coding over BSC can be well
approximated in low-capacity regime by the central limit theorem (e.g., Berry-
Essen theorem). To briefly explain the reason, consider transmission over
BSC($\delta$) where the value of $\delta$ is close to $0.5$. The capacity of
this channel is $1-h_{2}(\delta)$, where
$h_{2}(x):=-x\log_{2}(x)-(1-x)\log_{2}(1-x)$, and we denote
$\kappa=n(1-h_{2}(\delta))$. Note that when $\delta\to 0.5$ one can write
$\delta\approx 0.5-\sqrt{{\kappa}/{n}}$ by using the Taylor expansion of the
function $h_{2}(x)$ around $x=0.5$. Transmission over BSC($\delta$) can be
equivalently modeled as follow: (i) With probability $2\delta$ we let the
output of the channel be chosen according to Bernoulli($0.5$), i.e., the
output is completely random and independent of the input, and (ii) with
probability $1-2\delta$ we let the output be exactly equal to the input. In
other words, the output is completely noisy with probability $2\delta$ (call
it the noisy event) and completely noiseless with probability $1-2\delta$
(call it the noiseless event). As $\delta\to 0.5$, then the noiseless event is
a _rare event_. Now, assuming $n$ transmissions over the channel, the expected
number of noiseless events is $n(1-2\delta)\approx\sqrt{n\kappa}$. Similar to
BEC, the number of rare noiseless events follows a Poisson distribution with
mean $n(1-2\delta)$ due to the Poisson convergence theorem. However, as the
value of $n(1-2\delta)\approx\sqrt{n\kappa}$ is large, the resulting Poisson
distribution can also be well approximated by the Gaussian distribution due to
the central limit theorem (note that Poisson$(m)$ can be written as the sum of
$m$ independent Poisson$(1)$ random variables).

As mentioned earlier, central limit laws are the basis for deriving the laws
of the form (1) which are applied to the settings where the capacity is not
small. However, for the low-capacity regime, considerable extra effort is
required in terms of sharper arguments and tail bounds to work out the
constants correctly.

######  Theorem 2 (Non-Asymptotic Coding Bounds for Low-Capacity BSC).

Consider transmission over BSC($\delta$) in low-capacity regime and let
$\kappa=n(1-h_{2}(\delta))$. Then,

$\log_{2}M^{*}(n,p_{e})=\kappa-2\sqrt{\frac{2\delta(1-\delta)}{\ln
2}}\cdot\sqrt{\kappa}\,Q^{-1}\left(p_{e}\right)+\frac{1}{2}\log_{2}\kappa-\log_{2}p_{e}+\mathcal{O}\left(\log\log\kappa\right).$
(5)

###### Proof.

See Section 5.3 in the Appendix. ∎

We remark that the $\mathcal{O}(\log\log\kappa)$ term contains some other
terms such as $\mathcal{O}(\sqrt{-\log p_{e}}/\log\kappa)$. For practical
scenarios, the term $\mathcal{O}(\log\log\kappa)$ will be dominant.444We
always include only the dominant term inside $\mathcal{O}(\cdot)$. We also
note that, similar to the BEC case, all terms in (5) are expressed in terms of
$\kappa$ rather than $n$. This agrees with the intuition that the rate should
depend on the amount of “information” passed through $n$ usages of the channel
rather than the number of channel uses $n$.

######  Corollary 1.

Consider transmission of $k$ information bits over a low-capacity
BSC($\delta$). Then, the optimal blocklength $n^{*}$ for such a transmission
is

$n^{*}=\frac{1}{1-h_{2}(\delta)}\left(k+2\sqrt{\frac{2\delta(1-\delta)}{\ln
2}}Q^{-1}(p_{e})\cdot\sqrt{k}+\frac{4\delta(1-\delta)}{\ln
2}Q^{-1}(p_{e})^{2}+\log_{2}p_{e}+\mathcal{O}(\log k)\right).$

###### Proof.

See Section 5.3 in the Appendix. ∎

###  3.3 The Additive White Gaussian Channel

Similar to BSC, the channel variations in low-capacity AWGN channels are best
approximated by the central limit theorem. The following theorem is obtained
by using the ideas in [8, Theorem 73] with slight modifications. It turns out
that coding bounds for AWGN in the low-capacity regime can be obtained as a
limiting case of the-state-of-the-art bounds in the moderate-capacity regime.
The following theorem and corollary are resulted simply by repeating the same
argument in a manner that remains valid for these limiting cases. This needs a
tiny analysis refinemrnt which is done in the Appendix.

######  Theorem 3 (Non-Asymptotic Coding Bounds for Low-Capacity AWGN).

Consider transmission over AWGN($\eta$) in low-capacity regime and let
$\kappa=\frac{n}{2}\log_{2}(1+\eta)$. Then,

$\log_{2}M^{*}(n,p_{e},\eta)=\kappa-\frac{\sqrt{\eta+2}}{(\eta+1)\sqrt{\ln
2}}\cdot\sqrt{\kappa}\,Q^{-1}(p_{e})+\mathcal{E},$ (6)

where

$\mathcal{O}(1)\leq\mathcal{E}\leq\frac{1}{2}\log_{2}\kappa-\log_{2}p_{e}+\mathcal{O}\left(\frac{1}{\sqrt{-\log
p_{e}}}\right).$

###### Proof.

See Section 5.4 in the Appendix. ∎

Same considerations about $\mathcal{O}(.)$ notation, as discussed earlier,
should be taken into account here. Also note that as for BEC and BSC, the
optimal blocklength for AWGN channel can be expressed in terms of other
parameters in the low-capacity regime which is stated in the following
corollary.

######  Corollary 2.

Consider transmission of $k$ information bits over a low-capacity
AWGN($\eta$). Then, the optimal blocklength $n^{*}$ for such transmission is

$\displaystyle
n^{*}=\frac{2}{\log_{2}(1+\eta)}\left(k+\frac{\sqrt{\eta+2}}{(\eta+1)\sqrt{\ln
2}}Q^{-1}(p_{e})\cdot\sqrt{k}+\mathcal{O}\left(\log_{2}\frac{1}{p_{e}}\right)\right).$

###### Proof.

See Section 5.4 in the Appendix. ∎

##  4 Practical Code Designs and Simulation Results

As we need to design codes with extremely low rates, some of the state-of-the-
art codes may not be directly applicable. A notable instance is the class of
iterative codes, e.g., Turbo or LDPC codes. It is well known that decreasing
the design rate of iterative codes results in denser decoding graphs which
further leads to highly complex iterative decoders with poor performance.
E.g., an $(l,r)$-regular LDPC code with design rate $R=0.01$ requires $r,l\geq
99$. Hence, the Tanner graph will have a minimum degree of at least $99$ and
even for codelengths of order tens of thousands, the Tanner graph will have
many short cycles. To circumvent this issue, the current practical designs,
e.g., the NB-IoT code design, use repetition coding. I.e., a low rate
repetition code is concatenated with a powerful moderate-rate code. For
example, an iterative code of rate $R$ and length $n/r$ can be repeated $r$
times to construct a code of length $n$ with rate $R/r$. In Section 4.1, we
will discuss the pros and cons of using repetition schemes along with trade-
offs between the number of repetitions and performance of the code. As we will
see, although repetition leads to efficient implementations, the rate loss
through many repetitions will result in codes with mediocre performance.

Unlike iterative codes, polar codes and most algebraic codes (e.g., BCH or
Reed-Muller codes) can be used without any modification for low-rate
applications. In Section 4.2, we will study the behavior of polar coding on
low-capacity channels. As we will see, polar coding is advantageous in terms
of distance, performance and implicit repetition, however, its encoding and
decoding algorithms have to be carefully adjusted to reduce complexity and
latency for practical applications.

Throughout this section, we will consider code design for the class of binary
memoryless symmetric (BMS) channels. A BMS channel $W$ has binary input and,
letting $W(y\mid x)$ denotes the transition matrix, there exists a permutation
$\pi$ on the output alphabet such that $W(y\mid 0)=W(\pi(y)\mid 1)$. Notable
exemplars of this class are BEC, BSC, and BAWGN channels.555For a relevant
study of code design at a low-SNR scenario see [19, 20]

###  4.1 How Much Repetition is Needed?

As mentioned above, repetition is a simple way to design practical low-rate
codes that exploit the power of state-of-the-art designs. Let $r$ be a divisor
of $n$, where $n$ denotes the length of the code. Repetition coding consists
in designing first a smaller outer code of length $n/r$ and repeat each of its
code bits $r$ times (i.e., the inner code is repetition). The length of the
final code is $n/r\cdot r=n$. This is equivalent to transmitting the outer
code over the _$r$ -repetition channel_, $W^{r}$, which takes a bit as the
input and outputs an $r$-tuple which is the result of passing $r$ copies of
the input bit independently through the original channel $W$. E.g., if $W$ is
BEC($\epsilon$) then its corresponding $r$-repetition channel is
$W^{r}=\text{BEC}(\epsilon^{r})$.

The main advantage of repetition coding is the reduction in computational
complexity (especially if $r$ is large). This is because the encoding/decoding
complexity is effectively reduced to that of the outer code, i.e., once the
outer code is constructed, at the encoding side, we just need to repeat each
of its code bits $r$ times, and at the decoding side the log-likelihood of an
$r$-tuple consisting of $r$ independent transmissions of a bit is equal to sum
of the log-likelihoods of the individual channel outcomes. The computational
latency of the encoding and decoding algorithms is reduced to that of the
outer code in a similar way.

The outer code has to be designed for reliable communication over the channel
$W^{r}$. If $r$ is sufficiently large, then the capacity of $W^{r}$ will not
be low anymore. In this case, the outer code can be picked from off-the-shelf
practical codes designed for channels with moderate capacity values (e.g.,
iterative or polar codes). While this looks promising, one should note that
the main drawback of repetition coding is the loss in capacity. In general, we
have $C(W^{r})\leq rC(W)$ and the ratio vanishes by growing $r$. As a result,
if $r$ is very large then repetition coding might suffer from an unacceptable
rate loss. Thus, the main question that we need to answer is: how large $r$
can be made such that the rate loss is still negligible?

We note that the overall capacity corresponding to $n$ channel transmissions
is $nC(W)$. With repetition coding, the capacity will be reduced to $n/r\cdot
C(W^{r})$ since we transmit $n/r$ times over the channel $W^{r}$. For any
$\beta\in[0,1]$, we ask what is the largest repetition size $r_{\beta}$ such
that

$\frac{n}{r_{\beta}}C(W^{r_{\beta}})\geq\beta nC(W).$ (7)

Let us first assume that transmission takes place over BEC($\epsilon$). We
thus have $W^{r}=\text{BEC}(\epsilon^{r})$. If $\epsilon$ is not close to $1$,
then even $r=2$ would result in a considerble rate loss, e.g., if
$\epsilon=0.5$, then $C(W^{2})=0.75$ whereas $2C(W)=1$. However, when
$\epsilon$ is close to $1$, then at least for small values of $r$ the rate
loss can be negligible, e.g., for $r=2$, we have
$C(W^{2})=1-\epsilon^{2}\approx 2(1-\epsilon)=2C(W)$. The following theorem
provides lower and upper bounds for the largest repetition size, $r_{\beta}$,
that satisfies (7).

######  Theorem 4 (Maximum Repetition Length for BEC).

If $W=\text{BEC}(\epsilon)$, then for the largest repetition size,
$r_{\beta}$, that satisfies (7), we have

$\frac{n(1-\epsilon)\ell}{2\left(1-\frac{\beta}{\ell}\right)}\cdot\left(\frac{\beta}{\ell}\right)^{2}\leq\frac{n}{r_{\beta}}\leq\frac{n(1-\epsilon)\ell}{2\left(1-\frac{\beta}{\ell}\right)},$
(8)

where $\ell=-\frac{\ln\epsilon}{1-\epsilon}$. Equivalently, assuming
$\kappa=n(1-\epsilon)$, (8) becomes

$\frac{\kappa}{2\left(1-\beta\right)}\cdot\beta^{2}(1+\mathcal{O}(1-\epsilon))\leq\frac{n}{r_{\beta}}\leq\frac{\kappa}{2\left(1-\beta\right)}(1+\mathcal{O}(1-\epsilon)).$

###### Proof.

See Section 5.5 in the Appendix. ∎

######  Remark 3.

Going back to the results of Theorem 1, in order to obtain similar non-
asymptotic guarantees with repetition-coding, a necessary condition is that
the total rate loss due to repetition is $\mathcal{O}(1)$, i.e.,

$\frac{n}{r_{\beta}}C(W^{r_{\beta}})=nC(W)+\mathcal{O}(1).$

If $W=\text{BEC}(\epsilon)$ and $\kappa=n(1-\epsilon)$, then the necessary
condition implies plugging $\beta=1-\mathcal{O}(1/(\kappa)$ into (7).
Moreover, from Theorem 4 we can conclude that, when $\epsilon$ is close to
$1$, the maximum allowed repetition size is
$\mathcal{O}\left(n/\kappa^{2}\right)$. Equivalently, the size of the outer
code can be chosen as $\mathcal{O}(\kappa^{2})$.

A noteworthy conclusion from the above remark is that as having negligible
rate loss implies the repetition size to be at most
$\mathcal{O}(n/\kappa^{2})$, then the outer code has to be designed for a BEC
with erasure probability at least
$\epsilon^{\mathcal{O}(n/\kappa^{2})}=1-\mathcal{O}(1/\kappa)$. This means
that the outer code should still have a low rate even if $\kappa$ is as small
as few tens. Thus, the idea of using e.g., iterative codes as the outer code
and repetition codes as the inner code will lead to an efficient low-rate
design only if we are willing to tolerate non-negligible rate loss. We refer
to Section 4.3 for a numerical case study on repetition coding. In contrast,
the polar coding construction has implicitly a repetition block of optimal
size $\mathcal{O}(n/\kappa^{2})$ as we will see in the next section.

It turns out that the binary erasure channel has the smallest rate loss due to
repetition among all the BMS channels. This property has been used in the
following theorem to provide an upper bound on $r_{\beta}$ for any BMS
channel.

######  Theorem 5 (Upper Bound on Repetition Length for any BMS).

Among all BMS channels with the same capacity, BEC has the largest repetition
length $r_{\beta}$ that satisfies (7). Hence, for any BMS channel with
capacity $C$ and $\kappa=nC$, we have

$\frac{n}{r_{\beta}}\geq\frac{\kappa}{2(1-\beta)}\beta^{2}(1+\mathcal{O}(1-C)).$

###### Proof.

See Section 5.5 in the Appendix. ∎

######  Remark 4.

Similar to Remark 3, we can conclude that for any BMS channel with low
capacity, in order to have the total rate loss of order $\mathcal{O}(1)$, the
repetition size should be at most $\mathcal{O}(n/\kappa^{2})$.

###  4.2 Polar Coding at Low Capacity

We show in this section that polar construction provides several coding
advantages, in terms of both performance and complexity, in the low-capacity
regime. We will describe such advantages together with supporting analytical
and numerical evidence. We also show later in this section that, in order to
make polar codes a suitable candidate for practice, we need to carefully adapt
their encoding and decoding operations.

Polar codes were introduced by Arıkan in the seminal work of [14]. Polar codes
are the first family of codes for the class of binary-input symmetric discrete
memoryless channels that are provable to be capacity-achieving with low
encoding and decoding complexity [14]. Polar codes and polarization phenomenon
have been successfully applied to a wide range of problems including data
compression [21, 22], broadcast channels [23, 24], multiple access channels
[25, 26], physical layer security [27, 28], and coded modulations [29]. A
brief description of polar codes to set up notations and the basics is
provided next.

Basics of Polar Coding [14]. The basis of channel polarization consists in
mapping two identical copies of the channel $W:\mathcal{X}\to\mathcal{Y}$ into
the pair of channels $W^{0}:\mathcal{X}\to\mathcal{Y}^{2}$ and
$W^{1}:\mathcal{X}\to\mathcal{X}\times\mathcal{Y}^{2}$, defined as

$\displaystyle W^{0}(y_{1},y_{2}\mid x_{1})$
$\displaystyle=\sum_{x_{2}\in\mathcal{X}}\frac{1}{2}W(y_{1}\mid x_{1}\oplus
x_{2})W(y_{2}\mid x_{2}),$ (9) $\displaystyle W^{1}(y_{1},y_{2},x_{1}\mid
x_{2})$ $\displaystyle=\frac{1}{2}W(y_{1}\mid x_{1}\oplus x_{2})W(y_{2}\mid
x_{2}).$ (10)

Then, $W^{0}$ is a worse channel in the sense that it is degraded with respect
to $W$, hence it is less reliable than $W$; and $W^{1}$ is a better channel in
the sense that it is upgraded with respect to $W$, hence more reliable than
$W$. In the polar coding literature, the operation in (9) is also known as the
_check_ or _minus_ operation and the operation in (10) is also known as the
_variable_ or _plus_ operation.

By iterating this operation $n$ times, we map $n=2^{m}$ identical copies of
the transmission channel $W$ into the synthetic channels
$\\{W_{m}^{(i)}\\}_{i\in\\{0,\ldots,n-1\\}}$. More specifically, given
$i\in\\{0,\ldots,n-1\\}$, let $(b_{1},b_{2},\ldots,b_{m})$ be its binary
expansion over $m$ bits, where $b_{1}$ is the most significant bit and $b_{m}$
is the least significant bit, i.e.,

$i=\sum_{k=1}^{m}b_{k}2^{m-k}.$

Then, we define the synthetic channels
$\\{W_{m}^{(i)}\\}_{i\in\\{0,\ldots,n-1\\}}$ as

$W_{m}^{(i)}=(((W^{b_{1}})^{b_{2}})^{\cdots})^{b_{m}}.$

######  Example 1 (Synthetic Channel).

Take $m=4$ and $i=10$. Then, the synthetic channel
$W_{16}^{(10)}=(((W^{1})^{0})^{1})^{0}$ is obtained by applying first (10),
then (9), then (10), and finally (9).

The polar construction is polarizing in the sense that the synthetic channels
tend to become either completely noiseless or completely noisy. Thus, in the
encoding procedure, the $k$ information bits are assigned to the positions
(indices) corresponding to the best $k$ synthetic channels. Here, the quality
of a channel is measured by some reliability metric such as the Bhattacharyya
parameter of the channel. The remaining positions are “frozen” to predefined
values that are known at the decoder. As a result, the generator matrix of
polar codes is based on choosing the $k$ rows of the matrix

$G_{n}\ =\
\left[\begin{array}[]{@{\hspace{0.50ex}}c<EMAIL_ADDRESS>2.15277pt\lx@intercol\hfil 1\hfil\hskip 4.32709pt&0\hfil\hskip 2.15277pt\\\
\hskip 2.15277pt\lx@intercol\hfil 1\hfil\hskip 4.32709pt&1\hfil\hskip
2.15277pt\\\ \end{array}\right]^{\otimes m},$

which correspond to the best $k$ synthetic channels. It is worth noting that
for an index $i$ with binary expansion $(b_{1},b_{2},\cdots,b_{m})$ the
Hamming weight of the $i$-th row of $G_{n}$ is $2^{\sum_{j=1}^{m}b_{i}}$,
i.e., the Hamming weight of the $i$-th row, which corresponds to the $i$-th
synthetic channel, is exponentially related with the number of plus operations
in the construction of the $i$-th synthetic channel.

High Minimum Distance at Low-Capacity. If the channel $W$ has a low capacity,
then clearly any good (i.e., noiseless) synthetic channel requires a lot of
plus operations. As a result, for all the $k$ best synthetic channels the
Hamming weight of the corresponding row in $G_{n}$ is very high. Hence, the
resulting polar code will have a high minimum distance. Table 1 provides the
minimum distance of the polar code for various channels and lengths. The
channels are BAWGN, BEC, and BSC all with capacity $0.02$. We have constructed
polar codes for these channels with $k=40$. For the range of $n$ shown in the
table, we have observed that the set of synthetic indices for all the three
channels were identical. This would suggest the _universality_ of polar codes
in the low-rate regime (this should only hold when $k<<n$).666Note that polar
codes are not universal in general [30], but universal polar-like
constructions exist [31, 32]. As the table shows, the minimum distance keeps
increasing linearly with $n$.

$n$ | $1024$ | $2048$ | $4096$ | $8192$ | $16364$
---|---|---|---|---|---
$d_{\rm min}(d_{\rm min}/n)$ | $128\,(1/8)$ | $256\,(1/8)$ | $512\,(1/8)$ | $1024\,(1/8)$ | $2048\,(1/8)$
Table 1: Minimum distance of a polar code constructed for $k=40$ over various
channels with capacity $0.02$.

Polar Coding Does Optimal and Implicit Repetition at Low-Capacity. We have
shown in Section 4.1 that the maximum allowed repetition size to have
negligible capacity loss is $\mathcal{O}(n/\kappa^{2})$. We will show in this
section that at low-capacity, the polar construction is enforced to have
$\mathcal{O}(n/\kappa^{2})$ repetitions. In other words, the resulting polar
code is equivalent to a smaller polar code of size $\mathcal{O}(\kappa^{2})$
followed by repetitions. Consequently, the encoder and decoder of the polar
code could be implemented with much lower complexity taking into account the
implicit repetitions. That is, the encoding complexity can be reduced to
$n+\mathcal{O}(\kappa^{2}\log\kappa)$ and the decoding complexity using the
list successive cancellation (SC) decoder with list size $L$ is reduced to
$n+\mathcal{O}(L\kappa^{2}\log\kappa)$. Recall that the original
implementation of polar codes requires $n\log n$ encoding complexity and
$\mathcal{O}(Ln\log n)$ decoding complexity. Moreover, as the repetition steps
can all be done in parallel, the computational _latency_ of the encoding and
decoding operations can be reduced to $\mathcal{O}(\kappa^{2}\log\kappa)$ and
$\mathcal{O}(L\kappa^{2}\log\kappa)$, respectively. To further reduce the
complexity, the simplified SC decoder [33] or relaxed polar codes [34] can be
invoked. Such complexity reductions are important for making polar codes a
suitable candidate for practice. In a related work, designing low-rate codes
for BSCs by concatenating high rate polar codes together with repetitions is
considered [35].

######  Theorem 6.

Consider using a polar code of length $n=2^{m}$ for transmission over a BMS
channel $W$. Let $m_{0}=\log_{2}(4\kappa^{2})$ where $\kappa=nC(W)$. Then any
synthetic channel $W_{n}^{(i)}$ whose Bhattacharyya value is less than
$\frac{1}{2}$ has at least $m_{0}$ plus operations in the beginning. As a
result, the polar code constructed for $W$ is equivalent to the concatenation
of a polar code of length (at most) $2^{m_{0}}$ followed by $2^{m-m_{0}}$
repetitions.

###### Proof.

See Section 5.6 in the Appendix. ∎

######  Remark 5.

Note that from Theorem 6, polar codes automatically perform repetition coding
with $\mathcal{O}(n/\kappa^{2})$ repetitions, where $\kappa=nC$. This matches
the necessary (optimal) number of repetitions given in Remark 3 and 4.

###  4.3 Simulation Results

For the BEC, we have compared in Figure 1, the lower and upper bounds obtained
from Theorem 1 with the predictions of Formula (1). We have also plotted the
performance of polar codes. The setting considered in Figure 1 is as follows:
We intend to send $k=40$ information bits over the BEC$(\epsilon$). The
desired error probability is $p_{e}=10^{-2}$. For erasure values between
$0.96$ and $1$, Figure 1 plots bounds on the smallest (optimal) blocklength
$n$ needed for this scenario as well as the smallest length required by polar
codes. Note that in order to compute e.g., a lower bound on the shortest
length from Theorem 1, we should fix $M^{*}(n,p_{e})$ to $k=40$ and search for
the smallest $n$ that satisfies equation 4 with $\kappa=n(1-\epsilon)$ and
$p_{e}=0.01$.

0.9650.970.9750.980.9850.990.995$2{,}000$$4{,}000$$6{,}000$$8{,}000$Erasure
probability$n$upper bound from Theorem 1lower bound from Theorem 1upper bound
from Theorem 10lower bound from Theorem 9prediction from (1) [8, Theorem
44]polar-CRC (L=16)

0.9650.970.9750.980.9850.990.995$0.8$$1$$1.2$$1.4$Erasure
probabilityNormalized $n$

Figure 1: Comparison for low-capacity BEC. The number of information bits is
$k=40$ and the target error probability is $p_{e}=10^{-2}$. For the right
plot, with the same legend entries as the left plot, all the blocklengths $n$
in the left plot are normalized by the value of the lower bound, obtained from
Theorem 1.

As we see in Figure 1, the lower and upper bounds predicted from Theorem 1 are
very close to each other. The precise version of Formula (1) for BEC is given
in [8, Theorem 44]. Recall that both Theorem 1 and [8, Theorem 44] are
estimating the raw upper and lower bounds from Theorem 10 and Theorem 9. As
expected, the prediction obtained from Formula (1) is not precise in the low-
capacity regime and it becomes worse as the capacity approaches zero. On the
other hand, the estimated bounds from Theorem 1 converges to the original raw
bounds of Theorem 10 and Theorem 9 as the capacity approaches zero. Also, the
performance of the polar code is shown in Figure 1. The polar code is
concatenated with cyclic redundancy check (CRC) code of length $6$, and is
decoded with the list-SC algorithm [36] with list size $L=16$.

Figure 2 considers the scenario of sending $k=40$ bits of information over a
low-capacity BSC with target error probability $p_{e}=10^{-2}$. We have
compared in Figure 2, the predictions from Theorem 2 and Formula (1) (we used
precise version of Formula (1) for BSC given in [8, Theorem 41]) together with
the upper and lower bounds which are directly computed from Theorem 13 and
Theorem 14, respectively. Note that the true value of $n$ lies between Theorem
13 and Theorem 14. Now, in order to estimate this true value, Theorem 2 and
Formula (1) are both estimating the bounds in Theorem 13 and Theorem 14. In
both cases, the estimation of upper and lower bounds coincide which leads to a
single prediction. Therefore, none of them may lie between the original bounds
from Theorem 13 and Theorem 14. In this way, Figure 2 shows that, as we
expected, the prediction from Formula (1) is quite imprecise in the low-
capacity regime particularly in comparison to the prediction from Theorem 2
which is exact up to $\mathcal{O}(\log\log\kappa)$ terms. The performance of
polar codes is also plotted in Figure 2. An interesting problem is to analyze
the finite-length scaling of polar codes in the low-capacity regime [37, 38,
39, 40, 41].

0.360.380.40.420.440.46$0$$2{,}000$$4{,}000$$6{,}000$$8{,}000$Crossover
probability$n$upper bound from Theorem 13lower bound from Theorem 14prediction
from Theorem 2prediction from [8, Theorem 41]polar-CRC (L=16)

0.360.380.40.420.440.46$0.6$$0.8$$1$$1.2$$1.4$Crossover probabilityNormalized
$n$

Figure 2: Comparison for low-capacity BSC. The number of information bits is
$k=40$ and the target error probability is $p_{e}=10^{-2}$. For the right
plot, with the same legend entries as the left plot, all the blocklengths $n$
in the left plot are normalized by lower bound given by Theorem 14.

Figure 3 compares the performance of polar codes with repeated LTE Turbo codes
over the binary-input additive white Gaussian channel. Here, we intend to send
$k=40$ information bits. The polar-CRC code has length $8192$, and the Turbo-
repetition scheme has the $(120,40)$ mother code of rate $1/3$ as the outer
code which is repeated $68$ times (the total length is $68\times 120=8160$).
In the considered $(8192,40)$ polar code, a repetition factor of $4$ is
implicitly enforced by the construction, as predicted by Theorem 6. Hence, the
polar coding scheme is actually a $(2048,40)$ polar code with $4$ repetitions.
We note from Section 1 that repetition of the LTE code for the data channel,
in this case, the Turbo code of rate $1/3$, is the proposed code design in the
eMTC and NB-IoT (uplink) standards. For these two choices of code designs, the
block error probability is plotted with respect to $E_{b}/N_{0}$ in Figure 3.
As we see from the figure, the waterfall region of Turbo-repetition is almost
$1$ dB away from that of the polar code. This is mainly due to the many
repetitions that must be invoked in the repeated Turbo code to provide a low
rate design. Consequently, this results in capacity loss and significantly
degrades the performance of Turbo-repetition scheme compared to a code
carefully designed, both in terms of construction as well as the number of
repetitions, for the total length $8192$, such as the considered polar
code.777We can also use Reed-Muller with successive decoding [42].

$-3$$-2$$-1$$0$$1$$2$$3$$4$$10^{-4}$$10^{-3}$$10^{-2}$$10^{-1}$$10^{0}$SNR
($E_{b}/N_{0}$) [dB]Block error rateTurbo-repetitionPolar-CRCShannon limit
Figure 3: Comparison for low-capacity BAWGN. The number of information bits is
$k=40$. The polar-CRC has length $8192$, is constructed using $6$ CRC bits,
and is decoded using the SC-list decoder with $L=16$. The Turbo-repetition has
an underlying $(120,40)$ Turbo code which is repeated $68$ times (total length
$=8160$) and is decoded with $6$ iterations. The Shannon limit for this
setting is $-1.57$ dB.

##  5 Appendix: Proofs

###  5.1 Proofs for BEC

In this section, we prove the converse and achievability bounds of Theorem 1.
In the proofs, we will be using Theorems 7–10 which are stated at the end of
this section. For the results in coding theory, we generally refer to [8] as
it has well collected and presented the corresponding proofs. See also [15],
[43], [44], [45], and [46].

###### Proof of Theorem 1. Achievability Bound..

Consider $n$ transmissions over the BEC($\epsilon$) which are indexed by
$i=1,\cdots,n$. For the $i$-th transmission, we let $X_{i}$ be a Bernoulli
random variable which is $0$ if the output of the $i^{\text{th}}$ channel is
an erasure and is $1$ otherwise, i.e., $\text{Pr}\\{X_{i}=1\\}=1-\epsilon$.
Suppose $S_{n}=\sum_{i=1}^{n}X_{i}$ and denote $\kappa=n(1-\epsilon)$. We will
use the result of Theorem 10 and show that if a number $M_{1}$ satisfies (3),
then it will dissatisfy the inequality in (28). As a result, we obtain
$M_{1}\leq M^{*}(n,p_{e})$. Now, by considering (28), we define

$\displaystyle I_{1}$
$\displaystyle=\sum_{r\,<\,\log_{2}M_{1}}\binom{n}{r}\epsilon^{n-r}(1-\epsilon)^{r},$
$\displaystyle I_{2}$
$\displaystyle=\sum_{\log_{2}M_{1}\,\leq\,r\,\leq\,n}\binom{n}{r}\epsilon^{n-r}(1-\epsilon)^{r}\frac{M_{1}}{2^{r}}.$

We have $I_{1}=\text{Pr}\left\\{S_{n}<\log_{2}M_{1}\right\\}$. Suppose
$X\sim\text{Poisson}(\kappa)$, then we can write

$\displaystyle I_{1}$
$\displaystyle\leq\text{Pr}\left\\{X<\log_{2}M_{1}\right\\}+\bigg{|}\text{Pr}\left\\{S_{n}<\log_{2}M_{1}\right\\}-\text{Pr}\left\\{X<\log_{2}M_{1}\right\\}\bigg{|},$
$\displaystyle I_{2}$
$\displaystyle=\sum_{\log_{2}M_{1}\,\leq\,r\,\leq\,n}\text{Pr}\left\\{S_{n}=r\right\\}\frac{M_{1}}{2^{r}}$
$\displaystyle\leq\sum_{\log_{2}M_{1}\,\leq\,r\,\leq\,n}\text{Pr}\left\\{X=r\right\\}\frac{M_{1}}{2^{r}}+\sum_{\log_{2}M_{1}\,\leq\,r\,\leq\,n}\bigg{|}\text{Pr}\left\\{X=r\right\\}-\text{Pr}\left\\{S_{n}=r\right\\}\bigg{|}\frac{M_{1}}{2^{r}}$
$\displaystyle\leq\sum_{\log_{2}M_{1}\,\leq\,r\,<\,\infty}\text{Pr}\left\\{X=r\right\\}\frac{M_{1}}{2^{r}}+\sum_{\log_{2}M_{1}\,\leq\,r\,<\,\infty}\bigg{|}\text{Pr}\left\\{X=r\right\\}-\text{Pr}\left\\{S_{n}=r\right\\}\bigg{|}\frac{M_{1}}{2^{r}}.$

Putting these together, we obtain

$\displaystyle
I_{1}+I_{2}\leq\mathbb{E}\bigg{[}\mathbf{1}\left(X<\log_{2}M_{1}\right)+\mathbf{1}\left(X\geq\log_{2}M_{1}\right)\frac{M_{1}}{2^{X}}\bigg{]}+J_{1}+J_{2},$
(11)

where

$\displaystyle J_{1}$
$\displaystyle=\bigg{|}\text{Pr}\left\\{S_{n}<\log_{2}M_{1}\right\\}-\text{Pr}\left\\{X<\log_{2}M_{1}\right\\}\bigg{|},$
$\displaystyle J_{2}$
$\displaystyle=\sum_{\log_{2}M_{1}\,\leq\,r\,<\,\infty}\bigg{|}\text{Pr}\left\\{X=r\right\\}-\text{Pr}\left\\{S_{n}=r\right\\}\bigg{|}\frac{M_{1}}{2^{r}}.$

Using Theorem 7, we have

$\displaystyle J_{1}=$
$\displaystyle\bigg{|}\text{Pr}\left\\{S_{n}<\log_{2}M_{1}\right\\}-\text{Pr}\left\\{X<\log_{2}M_{1}\right\\}\bigg{|}\leq\alpha_{1}\sqrt{\text{Pr}\left\\{X<\log_{2}M_{1}\right\\}},$
(12)
$\displaystyle\bigg{|}\text{Pr}\left\\{X=r\right\\}-\text{Pr}\left\\{S_{n}=r\right\\}\bigg{|}\leq\alpha_{2}\sqrt{\text{Pr}\left\\{X\leq
r\right\\}},$ (13)

where

$\displaystyle\alpha_{1}$
$\displaystyle=\frac{\sqrt{2}}{\epsilon^{3/2}}\left(\sqrt{e}-1\right)(1-\epsilon),$
$\displaystyle\alpha_{2}$
$\displaystyle=\frac{\sqrt{6}}{\epsilon^{2}\sqrt{\kappa}}\left(\sqrt{e}-1\right)(1-\epsilon).$

We now upper-bound $J_{2}$ using (13), as follows:

$\displaystyle J_{2}$
$\displaystyle=2\sum_{\log_{2}M_{1}\,\leq\,r\,<\,\infty}\frac{M_{1}}{2^{r+1}}\bigg{|}\text{Pr}\left\\{X=r\right\\}-\text{Pr}\left\\{S_{n}=r\right\\}\bigg{|}$
$\displaystyle\leq
2\alpha_{2}\sum_{\log_{2}M_{1}\,\leq\,r\,<\,\infty}\frac{M_{1}}{2^{r+1}}\sqrt{\text{Pr}\left\\{X\leq
r\right\\}}$ $\displaystyle\leq
2\alpha_{2}\sqrt{\sum_{\log_{2}M_{1}\,\leq\,r\,<\,\infty}\frac{M_{1}}{2^{r+1}}\text{Pr}\left\\{X\leq
r\right\\}}.$ (14)

For obtaining the last part, note that $\sqrt{x}$ is a concave function and

$\sum_{\log_{2}M_{1}\,\leq\,r\,<\,\infty}\frac{M_{1}}{2^{r+1}}=1.$

Thus, (14) follows from Jensen inequality for $\sqrt{x}$, that is,
$\mathbb{E}\left[\sqrt{Z}\right]\leq\sqrt{\mathbb{E}\left[Z\right]}$. Also
consider

$\displaystyle\sum_{\log_{2}M_{1}\,\leq\,r\,<\,\infty}\frac{M_{1}}{2^{r+1}}\text{Pr}\left\\{X\leq
r\right\\}$
$\displaystyle=\sum_{\log_{2}M_{1}\,\leq\,r\,<\,\infty}\frac{M_{1}}{2^{r+1}}\sum_{i=0}^{r}e^{-\kappa}\frac{\kappa^{i}}{i!}$
$\displaystyle=\sum_{i=0}^{\infty}e^{-\kappa}\frac{\kappa^{i}}{i!}\left(\mathbf{1}\left(i<\log_{2}M_{1}\right)+\frac{\mathbf{1}\left(i\geq\log_{2}M_{1}\right)}{2^{i-\log_{2}M_{1}}}\right)$
$\displaystyle=\sum_{i<\log_{2}M_{1}}e^{-\kappa}\frac{\kappa^{i}}{i!}+M_{1}\sum_{i\geq\log_{2}M_{1}}e^{-\kappa}\frac{\kappa^{i}}{i!}\frac{1}{2^{i}}$
$\displaystyle=\mathcal{P}_{\kappa}(\log_{2}M_{1})+M_{1}e^{-\kappa/2}\sum_{i\geq\log_{2}M_{1}}e^{-\kappa/2}\frac{(\kappa/2)^{i}}{i!}$
$\displaystyle=\mathcal{P}_{\kappa}(\log_{2}M_{1})+M_{1}e^{-\kappa/2}\left(1-\mathcal{P}_{\kappa/2}(\log_{2}M_{1})\right).$
(15)

From (14) and (15), we get

$\displaystyle J_{2}$ $\displaystyle\leq
2\alpha_{2}\sqrt{\mathcal{P}_{\kappa}(\log_{2}M_{1})+M_{1}e^{-\kappa/2}\left(1-\mathcal{P}_{\kappa/2}(\log_{2}M_{1})\right)}.$
(16)

Also, considering the notation in (2), we can write

$\displaystyle\mathbb{E}\bigg{[}\mathbf{1}\left(X<\log_{2}M_{1}\right)+\mathbf{1}\left(X\geq\log_{2}M_{1}\right)\frac{M_{1}}{2^{X}}\bigg{]}$
$\displaystyle\qquad\qquad\qquad=\mathbb{E}\bigg{[}\mathbf{1}\left(X<\log_{2}M_{1}\right)\bigg{]}+\mathbb{E}\bigg{[}\frac{M_{1}}{2^{X}}\bigg{]}-\mathbb{E}\bigg{[}\left(X<\log_{2}M_{1}\right)\frac{M_{1}}{2^{X}}\bigg{]}$
$\displaystyle\qquad\qquad\qquad=\mathcal{P}_{\kappa}(\log_{2}M_{1})+\sum_{r}e^{-\kappa}\frac{\kappa^{r}}{r!}\cdot\frac{M_{1}}{2^{r}}-\sum_{r\,<\,\log_{2}M_{1}}e^{-\kappa}\frac{\kappa^{r}}{r!}\cdot\frac{M_{1}}{2^{r}}$
$\displaystyle\qquad\qquad\qquad=\mathcal{P}_{\kappa}(\log_{2}M_{1})+M_{1}e^{-\kappa/2}\sum_{r}e^{-\kappa/2}\frac{(\kappa/2)^{r}}{r!}-M_{1}e^{-\kappa/2}\sum_{r\,<\,\log_{2}M_{1}}e^{-\kappa/2}\frac{(\kappa/2)^{r}}{r!}$
$\displaystyle\qquad\qquad\qquad=\mathcal{P}_{\kappa}(\log_{2}M_{1})+M_{1}e^{-\kappa/2}-M_{1}e^{-\kappa/2}\mathcal{P}_{\kappa/2}(\log_{2}M_{1}).$
(17)

Now, (11), (12), (16), and (17) together result in

$\displaystyle I_{1}+I_{2}$
$\displaystyle\leq\mathcal{P}_{\kappa}(\log_{2}M_{1})+M_{1}e^{-\kappa/2}\left(1-\mathcal{P}_{\kappa/2}(\log_{2}M_{1})\right)$
$\displaystyle+\alpha_{1}\sqrt{\mathcal{P}_{\kappa}(\log_{2}M_{1})}+2\alpha_{2}\sqrt{\mathcal{P}_{\kappa}(\log_{2}M_{1})+M_{1}e^{-\kappa/2}\left(1-\mathcal{P}_{\kappa/2}(\log_{2}M_{1})\right)}$
$\displaystyle\leq\mathfrak{P}_{1}(M_{1})+\alpha\sqrt{\mathfrak{P}_{1}(M_{1})}$
$\displaystyle=p_{e},$ (18)

where

$\displaystyle\mathfrak{P}_{1}(M_{1})$
$\displaystyle=\mathcal{P}_{\kappa}(\log_{2}M_{1})+M_{1}e^{-\kappa/2}\left(1-\mathcal{P}_{\kappa/2}(\log_{2}M_{1})\right),$
$\displaystyle\alpha$
$\displaystyle=\alpha_{1}+2\alpha_{2}=\frac{\sqrt{2}}{\epsilon^{3/2}}\left(1+2\sqrt{\frac{3}{\epsilon\kappa}}\right)\left(\sqrt{e}-1\right)(1-\epsilon).$

Note that (18) holds by the definition of $M_{1}$ in (3). Hence, we showed

$\displaystyle\sum_{r=0}^{n}\binom{n}{r}\epsilon^{r}(1-\epsilon)^{n-r}2^{-[r-\log_{2}(M_{1}-1)]^{+}}\leq
I_{1}+I_{2}\leq p_{e},$

which means $M_{1}$ dissatisfies the inequality in (28). Hence, $M_{1}\leq
M^{*}(n,p_{e})$. ∎

###### Proof of Theorem 1. Converse Bound.

Consider $n$ transmissions over the BEC($\epsilon$) which are indexed by
$i=1,\cdots,n$. For the $i$-th transmission, we let $X_{i}$ be a Bernoulli
random variable which is $0$ if the output of the $i^{\text{th}}$ channel is
an erasure and is $1$ otherwise, i.e., $\text{Pr}\\{X_{i}=1\\}=1-\epsilon$.
Suppose $S_{n}=\sum_{i=1}^{n}X_{i}$ and denote $\kappa=n(1-\epsilon)$. We will
use the result of Theorem 9 and show that if a number $M_{2}$ satisfies (4),
then it will dissatisfy the inequality in (27). As a result, we obtain
$M^{*}(n,p_{e})\leq M_{2}$. Now, by considering (27), we define

$\displaystyle I_{1}$
$\displaystyle=\sum_{r\,<\,\log_{2}M_{2}}\binom{n}{r}\epsilon^{n-r}(1-\epsilon)^{r},$
$\displaystyle I_{2}$
$\displaystyle=\sum_{r\,<\,\log_{2}M_{2}}\binom{n}{r}\epsilon^{n-r}(1-\epsilon)^{r}\frac{2^{r}}{M_{2}}.$

We have $I_{1}=\text{Pr}\left\\{S_{n}<\log_{2}M_{2}\right\\}$. Suppose
$X\sim\text{Poisson}(\kappa)$, then we can write

$\displaystyle I_{1}$
$\displaystyle\geq\text{Pr}\left\\{X<\log_{2}M_{2}\right\\}-\bigg{|}\text{Pr}\left\\{S_{n}<\log_{2}M_{2}\right\\}-\text{Pr}\left\\{X<\log_{2}M_{2}\right\\}\bigg{|},$
$\displaystyle I_{2}$
$\displaystyle=\sum_{r\,<\,\log_{2}M_{2}}\text{Pr}\left\\{S_{n}=r\right\\}\frac{2^{r}}{M_{2}}$
$\displaystyle\leq\sum_{r\,<\,\log_{2}M_{2}}\text{Pr}\left\\{X=r\right\\}\frac{2^{r}}{M_{2}}+\sum_{r\,<\,\log_{2}M_{2}}\bigg{|}\text{Pr}\left\\{X=r\right\\}-\text{Pr}\left\\{S_{n}=r\right\\}\bigg{|}\frac{2^{r}}{M_{2}}.$

Putting these together, we obtain

$\displaystyle
I_{1}-I_{2}\geq\mathbb{E}\bigg{[}\mathbf{1}\left(X<\log_{2}M_{2}\right)\left(1-\frac{2^{X}}{M_{2}}\right)\bigg{]}-J_{1}-J_{2},$
(19)

where

$\displaystyle J_{1}$
$\displaystyle=\bigg{|}\text{Pr}\left\\{S_{n}<\log_{2}M_{2}\right\\}-\text{Pr}\left\\{X<\log_{2}M_{2}\right\\}\bigg{|},$
$\displaystyle J_{2}$ $\displaystyle=\sum_{r\,<\,\log
M_{2}}\bigg{|}\text{Pr}\left\\{X=r\right\\}-\text{Pr}\left\\{S_{n}=r\right\\}\bigg{|}\frac{2^{r}}{M_{2}}.$

Using Theorem 7, we have

$\displaystyle J_{1}=$
$\displaystyle\bigg{|}\text{Pr}\left\\{S_{n}<\log_{2}M_{2}\right\\}-\text{Pr}\left\\{X<\log_{2}M_{2}\right\\}\bigg{|}\leq\alpha_{1}\sqrt{\text{Pr}\left\\{X<\log_{2}M_{2}\right\\}}$
(20)
$\displaystyle\bigg{|}\text{Pr}\left\\{X=r\right\\}-\text{Pr}\left\\{S_{n}=r\right\\}\bigg{|}\leq\alpha_{2}\sqrt{\text{Pr}\left\\{X\leq
r\right\\}},$ (21)

where

$\displaystyle\alpha_{1}$
$\displaystyle=\frac{\sqrt{2}}{\epsilon^{3/2}}\left(\sqrt{e}-1\right)(1-\epsilon),$
$\displaystyle\alpha_{2}$
$\displaystyle=\frac{\sqrt{6}}{\epsilon^{2}\sqrt{\kappa}}\left(\sqrt{e}-1\right)(1-\epsilon).$

We now upper-bound $J_{2}$ using (21), as follows:

$\displaystyle J_{2}$ $\displaystyle=\sum_{r\,<\,\log
M_{2}}\frac{2^{r}}{M_{2}}\bigg{|}\text{Pr}\left\\{X=r\right\\}-\text{Pr}\left\\{S_{n}=r\right\\}\bigg{|}$
$\displaystyle\leq\alpha_{2}\sum_{r\,<\,\log
M_{2}}\frac{2^{r}}{M_{2}}\sqrt{\text{Pr}\left\\{X\leq r\right\\}}$
$\displaystyle\leq\alpha_{2}\sqrt{\sum_{r\,<\,\log
M_{2}}\frac{2^{r}}{M_{2}}\text{Pr}\left\\{X\leq r\right\\}}.$ (22)

For obtaining the last part, note that $\sqrt{x}$ is a concave function and

$\sum_{r\,<\,\log M_{2}}\frac{2^{r}}{M_{1}}\leq 1.$

Thus, (22) follows from Jensen inequality for $\sqrt{x}$, that is,
$\mathbb{E}\left[\sqrt{Z}\right]\leq\sqrt{\mathbb{E}\left[Z\right]}$. Also
consider

$\displaystyle\sum_{r\,<\,\log M_{2}}\frac{2^{r}}{M_{2}}\text{Pr}\left\\{X\leq
r\right\\}$ $\displaystyle=\sum_{r\,<\,\log
M_{2}}\frac{2^{r}}{M_{2}}\left(1-\text{Pr}\left\\{X>r\right\\}\right)$
$\displaystyle=1-\frac{1}{M_{2}}-\sum_{r\,<\,\log
M_{2}}\frac{2^{r}}{M_{2}}\sum_{i=r+1}^{\infty}e^{-\kappa}\frac{\kappa^{i}}{i!}$
$\displaystyle=1-\frac{1}{M_{2}}-\sum_{i=0}^{\infty}e^{-\kappa}\frac{\kappa^{i}}{i!}\left(\mathbf{1}\left(i\geq\log_{2}M_{2}\right)+\mathbf{1}\left(i<\log_{2}M_{2}\right)\frac{2^{i}-1}{M_{2}}\right)$
$\displaystyle=1-\frac{1}{M_{2}}-\left(1-\mathcal{P}_{\kappa}(\log_{2}M_{2})+\frac{e^{\kappa}}{M_{2}}\sum_{i\,<\,\log
M_{2}}e^{-2\kappa}\frac{(2\kappa)^{i}}{i!}-\frac{\mathcal{P}_{\kappa}(\log_{2}M_{2})}{M_{2}}\right)$
$\displaystyle=\mathcal{P}_{\kappa}(\log_{2}M_{2})-\frac{e^{\kappa}}{M_{2}}\,\mathcal{P}_{2\kappa}\left(\log_{2}M_{2}\right)-\frac{1-\mathcal{P}_{\kappa}(\log_{2}M_{2})}{M_{2}}$
$\displaystyle\leq\mathcal{P}_{\kappa}(\log_{2}M_{2})-\frac{e^{\kappa}}{M_{2}}\,\mathcal{P}_{2\kappa}\left(\log_{2}M_{2}\right).$
(23)

From (22) and (23), we obtain

$\displaystyle J_{2}$
$\displaystyle\leq\alpha_{2}\sqrt{\mathcal{P}_{\kappa}(\log_{2}M_{2})-\frac{e^{\kappa}}{M_{2}}\,\mathcal{P}_{2\kappa}\left(\log_{2}M_{2}\right)}.$
(24)

Also, considering the notation in (2), we can write

$\displaystyle\mathbb{E}\bigg{[}\mathbf{1}\left(X<\log_{2}M_{2}\right)\left(1-\frac{2^{X}}{M_{2}}\right)\bigg{]}$
$\displaystyle=\mathbb{E}\bigg{[}\mathbf{1}\left(X<\log_{2}M_{2}\right)\bigg{]}-\mathbb{E}\bigg{[}\left(X<\log_{2}M_{2}\right)\frac{2^{X}}{M_{2}}\bigg{]}$
$\displaystyle=\mathcal{P}_{\kappa}(\log_{2}M_{2})-\sum_{r\,<\,\log_{2}M_{2}}e^{-\kappa}\frac{\kappa^{r}}{r!}\cdot\frac{2^{r}}{M_{2}}$
$\displaystyle=\mathcal{P}_{\kappa}(\log_{2}M_{2})-\frac{e^{\kappa}}{M_{2}}\sum_{r\,<\,\log_{2}M_{2}}e^{-2\kappa}\frac{(2\kappa)^{r}}{r!}$
$\displaystyle=\mathcal{P}_{\kappa}(\log_{2}M_{2})-\frac{e^{\kappa}}{M_{2}}\,\mathcal{P}_{2\kappa}\left(\log_{2}M_{2}\right).$
(25)

Now, (19), (20), (24), and (25) together result in

$\displaystyle I_{1}-I_{2}$
$\displaystyle\geq\mathcal{P}_{\kappa}(\log_{2}M_{2})-\frac{e^{\kappa}}{M_{2}}\,\mathcal{P}_{2\kappa}\left(\log_{2}M_{2}\right)-\alpha_{1}\sqrt{\mathcal{P}_{\kappa}(\log_{2}M_{2})}-\alpha_{2}\sqrt{\mathcal{P}_{\kappa}(\log_{2}M_{2})-\frac{e^{\kappa}}{M_{2}}\,\mathcal{P}_{2\kappa}\left(\log_{2}M_{2}\right)}$
$\displaystyle\geq\mathfrak{P}_{2}(M_{2})-\alpha\sqrt{\mathfrak{P}_{2}(M_{2})}-\alpha\sqrt{\mathcal{P}_{\kappa}(\log_{2}M_{2})}$
$\displaystyle=p_{e},$ (26)

where

$\displaystyle\mathfrak{P}_{2}(M_{2})$
$\displaystyle=\mathcal{P}_{\kappa}(\log_{2}M_{2})-\frac{e^{\kappa}}{M_{2}}\,\mathcal{P}_{2\kappa}\left(\log_{2}M_{2}\right),$
$\displaystyle\alpha$
$\displaystyle=\alpha_{1}+2\alpha_{2}=\frac{\sqrt{2}}{\epsilon^{3/2}}\left(1+2\sqrt{\frac{3}{\epsilon\kappa}}\right)\left(\sqrt{e}-1\right)(1-\epsilon).$

Note that (26) holds by the definition of $M_{2}$ in (4). Hence, we showed

$\displaystyle\sum_{r\,<\,\log_{2}M_{2}}\binom{n}{r}\epsilon^{n-r}(1-\epsilon)^{r}\bigg{(}1-\frac{2^{r}}{M_{2}}\bigg{)}=I_{1}-I_{2}\geq
p_{e},$

which means $M_{2}$ dissatisfies the inequality in (27). Hence,
$M^{*}(n,p_{e})\leq M_{2}$. ∎

######  Theorem 7 (Strong Poisson Convergence).

For $1\leq i\leq n$, let $X_{i}$’s be independent random variables with
$P(X_{i}=1)=1-P(X_{i}=0)=p_{i}$. Define $S_{n}=\sum_{i=1}^{n}X_{i}$ . Also
define $\lambda_{k}=\sum_{i=1}^{n}p_{i}^{k}$ and let $\lambda=\lambda_{1}$ and
$\theta=\lambda_{2}/\lambda_{1}$. Then,

$\displaystyle\bigg{|}\text{Pr}\\{S_{n}\leq m\\}-\text{Pr}\\{X\leq
m\\}\bigg{|}\leq\frac{\sqrt{2}\,(\sqrt{e}-1)\,\theta}{(1-\theta)^{3/2}}\sqrt{\psi(m)},$

and

$\bigg{|}\text{Pr}\\{S_{n}=m\\}-\text{Pr}\\{X=m\\}\bigg{|}\leq\frac{\sqrt{6}\,(\sqrt{e}-1)\,\theta}{(1-\theta)^{2}\sqrt{\lambda}}\sqrt{\psi(m)},$

where $X\sim\text{Poisson}(\lambda)$ and the quantity $\psi(m)$ is

$\displaystyle\psi(m)=\min\bigg{\\{}\text{Pr}\\{X\leq
m\\},\text{Pr}\\{X>m\\}\bigg{\\}}.$

###### Proof.

See [47, Theorem 3.4, Lemma 3.7]. ∎

######  Theorem 8 (Poisson Convergence).

For $1\leq i\leq n$, let $X_{i}$’s be independent random variables with
$P(X_{i}=1)=1-P(X_{i}=0)=p_{i}$. Define $S_{n}=\sum_{i=1}^{n}X_{i}$ and
$\lambda_{k}=\sum_{i=1}^{n}p_{i}^{k}$. Let $\mu_{n}$ be the distribution of
$S_{n}$ and $\nu_{n}$ be the Poisson distribution with mean $\lambda_{1}$.
Then the following holds.

$\sup_{A}\bigg{|}\mu_{n}(A)-\nu_{n}(A)\bigg{|}\leq\frac{\lambda_{2}}{\lambda_{1}}$

###### Proof.

See [48, page 89]. ∎

######  Theorem 9 (Converse Bound for BEC).

For any $(M,p_{e})$-code over the BECn($\epsilon$), we have

$p_{e}\geq\sum_{r\,\,<\log_{2}M}\binom{n}{r}\epsilon^{n-r}(1-\epsilon)^{r}\bigg{(}1-\frac{2^{r}}{M}\bigg{)}.$
(27)

###### Proof.

See [8, Theorem 43]. ∎

######  Theorem 10 (RCU Achievability Bound for BEC).

There exists an $(M,p_{e})$-code over BECn($\epsilon$) such that

$p_{e}\leq\sum_{r=0}^{n}\binom{n}{r}\epsilon^{n-r}(1-\epsilon)^{r}2^{-[r-\log_{2}(M-1)]^{+}}.$
(28)

###### Proof.

See [8, Corollary 42]. ∎

###  5.2 How to Compute the Bounds in Theorem 1

The problem essentially boils down to accurate computation of the
probabilities $\rm{Pr}(X=s)$ when $X$ is a Poisson random variable with
average $\kappa$. We have ${\rm{Pr}}(X=s)=e^{-\kappa}\kappa^{s}/s!$. The value
of $s!$ can be approximated using the refined Ramanujan’s formula [49]:

$s!=\sqrt{\pi}\left(\frac{s}{e}\right)^{s}\left(8s^{3}+4s^{2}+s+\frac{\theta(s)}{30}\right)^{\frac{1}{6}},$

where

$\theta_{1}(s):=1-\frac{11}{8s}+\frac{79}{112s^{2}}\leq\theta(s)\leq\theta_{2}(s):=1-\frac{11}{8s}+\frac{79}{112s^{2}}+\frac{20}{33s^{3}}.$

By plugging-in the lower bound for $s!$ from the above formula (for $s\leq 10$
we can use the exact value of $s!$) we obtain

${\rm
Pr}(X=s)=\frac{e^{s-\kappa+s\ln(\kappa/s)}}{\sqrt{\pi}\left(8s^{3}+4s^{2}+s+\frac{\theta_{1}(s)}{30}\right)^{\frac{1}{6}}}.$

Note that this formula is exact up to a multiplicative factor of $1+s^{-6}$
which for $s\geq 10$ gives us a $(1+10^{-6})$-approximation. Moreover, if we
are obsessed with obtaining “bounds”, we can use the lower and upper bound
approximations for $s!$ to bound the Poisson probability from above and below
and hence obtain bounds for $M_{1},M_{2}$ in Theorem 1.

Once the Poisson probabilities are approximated (or bounded) suitably, we can
compute values of $M_{1}$ and $M_{2}$ up to any precision by truncating the
expectation and using the bisection method to solve the equations.

###  5.3 Proofs for BSC

In this section, we prove the converse and achievability bounds of Theorem 2.
In the proofs we will be using Theorems 11–14 as well as Lemmas 1–4 which are
stated at the end of this section. For the results in coding theory, we
generally refer to [8] as it has well collected and presented the
corresponding proofs. See also [15], [43], [44], [45], and [46].

###### Proof of Theorem 2. Achievability Bound.

Define $T$ and $S$ as follows:

$\displaystyle T$
$\displaystyle=n\delta+\sqrt{n\delta(1-\delta)}Q^{-1}\bigg{(}p_{e}-\frac{p_{e}}{\sqrt{\kappa}}-\frac{c_{1}}{\sqrt{n}}\bigg{)},$
(29) $\displaystyle S$
$\displaystyle=\sum_{r\,\leq\,T}\binom{n}{r}\delta^{r}(1-\delta)^{n-r}S_{n}^{r},$
(30)

where $c_{1}=\frac{3(2\delta^{2}-2\delta+1)}{\sqrt{\delta(1-\delta)}}$ is a
constant. Suppose that we choose some $M$ to satisfy

$M\leq\frac{p_{e}}{\sqrt{\kappa}\,S}.$ (31)

Now define

$\displaystyle I_{1}$
$\displaystyle=\sum_{r\,\leq\,T}\binom{n}{r}\delta^{r}(1-\delta)^{n-r}MS_{n}^{r},$
$\displaystyle I_{2}$
$\displaystyle=\sum_{T<\,r\leq\,n}\binom{n}{r}\delta^{r}(1-\delta)^{n-r}.$

From (30) and (31), we have

$I_{1}=MS\leq\frac{p_{e}}{\sqrt{\kappa}}.$ (32)

For $1\leq i\leq n$, define $V_{i}$ to be a Bernoulli random variable with
$\text{Pr}\\{V_{i}=1\\}=1-\text{Pr}\\{V_{i}=0\\}=\delta$. Then define

$\mu=\mathbb{E}\left[V_{i}\right]=\delta,\quad\sigma^{2}=\mathbb{V}ar[V_{i}]=\delta(1-\delta),\quad\rho=\mathbb{E}\left[\left|V_{i}-\mu\right|^{3}\right]=\delta(1-\delta)\left(2\delta^{2}-2\delta+1\right).$

Now, using Theorem 11, we can write

$I_{2}=\text{Pr}\left\\{\sum_{i=1}^{n}V_{i}>T\right\\}\leq
Q\bigg{(}\frac{T-n\mu}{\sigma}\bigg{)}+\frac{3\rho}{\sigma^{3}\,\sqrt{n}}=Q\bigg{(}\frac{T-n\delta}{\sqrt{n\delta(1-\delta)}}\bigg{)}+\frac{c_{1}}{\sqrt{n}}\overset{(\ref{a0})}{=}p_{e}-\frac{p_{e}}{\sqrt{\kappa}}.$
(33)

Therefore, (32) and (33) together give

$\displaystyle I_{1}+I_{2}\leq
p_{e}-\frac{p_{e}}{\sqrt{\kappa}}+\frac{p_{e}}{\sqrt{\kappa}}=p_{e}.$

Now, we can write

$\displaystyle\sum_{r=0}^{n}\binom{n}{r}\delta^{r}(1-\delta)^{n-r}\min\bigg{\\{}1,(M-1)S_{n}^{r}\bigg{\\}}\
\leq\sum_{r=0}^{n}\binom{n}{r}\delta^{r}(1-\delta)^{n-r}\min\bigg{\\{}1,MS_{n}^{r}\bigg{\\}}\leq
I_{1}+I_{2}\leq p_{e}.$

Thus, $M$ dissatisfies the inequality in (48) and as a result,
$M^{*}(n,p_{e})\geq M$. Note that $M$ was arbitrarily chosen to satisfy (31),
This means for any $M$ satisfying (31), we have $M^{*}(n,p_{e})\geq M$. Hence,

$M^{*}(n,p_{e})\geq\sup\left\\{M:M\leq\frac{p_{e}}{\sqrt{\kappa}\,S}\right\\}=\frac{p_{e}}{\sqrt{\kappa}\,S}.$
(34)

Now, in order to find a lower bound for $M^{*}(n,p_{e})$, it suffices to find
an upper bound for $S$. This is our main goal for the rest of the proof. Note
that due to Lemma 3, there exists a constant $\theta$ such that

$\binom{n}{r}\delta^{r}(1-\delta)^{n-r}\leq\frac{\theta}{\sqrt{n}}.$ (35)

Also note that $S_{n}^{r}$ is increasing with respect to $r$. Define

$\beta=\frac{1}{4}\sqrt{\frac{\ln
2}{2}}\cdot\frac{\log_{2}\kappa}{\sqrt{\kappa}}.$

With this choice of $\beta$, we continue as follows:

$\displaystyle S$
$\displaystyle=\sum_{r\,\leq\,T-\beta\sqrt{n}}\binom{n}{r}\delta^{r}(1-\delta)^{n-r}S_{n}^{r}+\sum_{T-\beta\sqrt{n}\,<\,r\,\leq\,T}\binom{n}{r}\delta^{r}(1-\delta)^{n-r}S_{n}^{r}$
$\displaystyle\leq
S_{n}^{T-\beta\sqrt{n}}\sum_{r\,\leq\,T-\beta\sqrt{n}}\binom{n}{r}\delta^{r}(1-\delta)^{n-r}+S_{n}^{T}\sum_{T-\beta\sqrt{n}\,<\,r\,\leq\,T}\binom{n}{r}\delta^{r}(1-\delta)^{n-r}$
$\displaystyle\overset{(\ref{theta})}{\leq}S_{n}^{T-\beta\sqrt{n}}+S_{n}^{T}\beta\theta.$
(36)

In order to find an upper bound for $S$, it then suffices to find an upper
bound for the right hand side in (36). For $1\leq i\leq n$, let $Y_{i}\sim$
Bernoulli($\frac{1}{2}$) and $X_{i}=\frac{1}{2}-Y_{i}$. Note that
$\mathbb{E}[X_{i}]=0$, $\mathbb{V}ar[X_{i}]=\frac{1}{4}$ and
$\left|X_{i}\right|\leq\frac{1}{2}$. Then Theorem 12 implies

$\displaystyle S_{n}^{r}$ $\displaystyle=\Pr\left\\{\sum_{i=1}^{n}Y_{i}\leq
r\right\\}=\Pr\left\\{\sum_{i=1}^{n}X_{i}\geq\frac{n}{2}-r\right\\}\leq\bigg{(}\frac{1}{2\sqrt{2\pi}}\cdot\frac{\sqrt{n}}{\frac{n}{2}-r}+\frac{\gamma}{\sqrt{n}}\bigg{)}e^{-nH(\frac{1}{4},\frac{1}{2},\frac{1}{2}-\frac{r}{n})}.$

A simple calculation shows that
$H(\frac{1}{4},\frac{1}{2},\frac{1}{2}-\frac{r}{n})=\left(1-h_{2}\left(\frac{r}{n}\right)\right)\ln
2$. Thus,

$S_{n}^{r}\leq\bigg{(}\frac{1}{2\sqrt{2\pi}}\cdot\frac{1}{\frac{\sqrt{n}}{2}-\frac{r}{\sqrt{n}}}+\frac{\gamma}{\sqrt{n}}\bigg{)}2^{-n\left(1-h_{2}\left(\frac{r}{n}\right)\right)}.$
(37)

Due to part (i) of Lemma 1 and part (ii) of Lemma 2, the first term in the
right hand side of (37), when $r=T$, can be written as

$\displaystyle\left(\frac{\sqrt{n}}{2}-\frac{T}{\sqrt{n}}\right)^{-1}$
$\displaystyle=\left(\sqrt{n}\left(\frac{1}{2}-\delta\right)-\sqrt{\delta(1-\delta)}Q^{-1}\left(p_{e}-\frac{p_{e}}{\sqrt{\kappa}}-\frac{c_{1}}{\sqrt{n}}\right)\right)^{-1}$
$\displaystyle=\left(\sqrt{\frac{\ln
2}{2}\,\kappa}+\mathcal{O}\left(\frac{\kappa\sqrt{\kappa}}{n}\right)-\sqrt{\delta(1-\delta)}Q^{-1}\left(p_{e}-\frac{p_{e}}{\sqrt{\kappa}}-\frac{c_{1}}{\sqrt{n}}\right)\right)^{-1}$
$\displaystyle=\left(\sqrt{\frac{\ln
2}{2}\,\kappa}\right)^{-1}+\mathcal{O}\left(\frac{\sqrt{\kappa}}{n}\right)+\mathcal{O}\left(\frac{\sqrt{-\log
p_{e}}}{\kappa}\right)$ $\displaystyle=\left(\sqrt{\frac{\ln
2}{2}\,\kappa}\right)^{-1}+\mathcal{O}\left(\frac{\sqrt{-\log
p_{e}}}{\kappa}\right).$ (38)

Note that to use Lemma 1, we need to have $\kappa\sqrt{\kappa}=o(n)$. This is
given due to our criterion for being in the low-capacity regime for BSC that
is expressed in Remark 2. This condition is also used for further
simplification of order terms. Similarly, when $r=T-\beta\,\sqrt{n}$, we have

$\displaystyle\left(\frac{\sqrt{n}}{2}-\frac{T-\beta\sqrt{n}}{\sqrt{n}}\right)^{-1}=\left(\frac{\sqrt{n}}{2}-\frac{T}{\sqrt{n}}+\beta\right)^{-1}=\left(\sqrt{\frac{\ln
2}{2}\,\kappa}\right)^{-1}+\mathcal{O}\left(\frac{\sqrt{-\log
p_{e}}}{\kappa}\right).$ (39)

Now, the goal is to estimate the term $n\left(1-h_{2}(\frac{r}{n})\right)$ in
the right hand side of (37) for $r=T$ and $r=T-\beta\sqrt{n}$. Using the third
order estimation of $h_{2}(.)$ gives

$\displaystyle
h_{2}\left(\frac{T}{n}\right)=h_{2}(\delta)+\left(\log_{2}\frac{1-\delta}{\delta}\right)\sqrt{\frac{\delta(1-\delta)}{n}}Q^{-1}\left(p_{e}-\frac{p_{e}}{\sqrt{\kappa}}-\frac{c_{1}}{\sqrt{n}}\right)-\frac{1}{n\ln
2}Q^{-1}\left(p_{e}\right)^{2}+\mathcal{O}\left(\frac{1}{n\sqrt{\kappa}}\right).$

Therefore, by the definition of $\kappa$ and part (ii) of Lemma 1, we obtain

$\displaystyle
n\left(1-h_{2}\left(\frac{T}{n}\right)\right)=\kappa-2\sqrt{\frac{2\delta(1-\delta)}{\ln
2}}\cdot\sqrt{\kappa}\,Q^{-1}\left(p_{e}-\frac{p_{e}}{\sqrt{\kappa}}-\frac{c_{1}}{\sqrt{n}}\right)+\frac{1}{\ln
2}Q^{-1}\left(p_{e}\right)^{2}+\mathcal{O}\left(\frac{1}{\sqrt{\kappa}}\right).$

Note that

$\frac{d}{dx}Q^{-1}(x)=-\sqrt{2\pi}\,e^{\frac{Q^{-1}(x)^{2}}{2}}.$

Thus, by applying Taylor expansion of $Q^{-1}(.)$, and using parts (i) and
(ii) of Lemma 2, we then conclude that

$\displaystyle
n\left(1-h_{2}\left(\frac{T}{n}\right)\right)=\kappa-2\sqrt{\frac{2\delta(1-\delta)}{\ln
2}}\cdot\sqrt{\kappa}\,Q^{-1}\left(p_{e}\right)+\mathcal{E}_{1},$ (40)

where

$\mathcal{E}_{1}=\frac{1}{\ln
2}Q^{-1}\left(p_{e}\right)^{2}+\mathcal{O}\left(\frac{1}{\sqrt{-\log
p_{e}}}\right)+\mathcal{O}\left(\frac{1}{\sqrt{\kappa}}\right)=\frac{1}{\ln
2}Q^{-1}\left(p_{e}\right)^{2}+\mathcal{O}\left(\frac{1}{\sqrt{-\log
p_{e}}}\right).$ (41)

Exploiting the same analogy leads to the following result for
$r=T-\beta\sqrt{n}$ :

$\displaystyle n\left(1-h_{2}\left(\frac{T-\beta\sqrt{n}}{n}\right)\right)$
$\displaystyle=\kappa-2\sqrt{\frac{2\delta(1-\delta)}{\ln
2}}\cdot\sqrt{\kappa}\,Q^{-1}\left(p_{e}\right)+2\sqrt{\frac{2}{\ln
2}}\cdot\beta\sqrt{\kappa}+\mathcal{E}_{1}$
$\displaystyle=\kappa-2\sqrt{\frac{2\delta(1-\delta)}{\ln
2}}\cdot\sqrt{\kappa}\,Q^{-1}\left(p_{e}\right)+\frac{1}{2}\log_{2}\kappa+\mathcal{E}_{1}.$
(42)

Now, (37), (38), and (40) together imply

$\displaystyle S_{n}^{T}\leq\frac{1}{2\sqrt{\pi\kappa\ln
2}}2^{-\left(\kappa-2\sqrt{\frac{2\delta(1-\delta)}{\ln
2}}\cdot\sqrt{\kappa}\,Q^{-1}\left(p_{e}\right)+\mathcal{E}_{1}\right)}+\mathcal{O}\left(\frac{\sqrt{-\log
p_{e}}}{\kappa\,2^{\kappa}}\right).$ (43)

Similarly, (37), (39), and (5.3) together imply

$\displaystyle S_{n}^{T-\beta\sqrt{n}}\leq\frac{1}{2\sqrt{\pi\kappa\ln
2}}2^{-\left(\kappa-2\sqrt{\frac{2\delta(1-\delta)}{\ln
2}}\cdot\sqrt{\kappa}\,Q^{-1}\left(p_{e}\right)+\frac{1}{2}\log_{2}\kappa+\mathcal{E}_{1}\right)}+\mathcal{O}\left(\frac{\sqrt{-\log
p_{e}}}{\kappa\,2^{\kappa}}\right).$ (44)

As a result, from (43), (44), and (36), we have

$\displaystyle S$ $\displaystyle\leq
S_{n}^{T-\beta\sqrt{n}}+S_{n}^{T}\beta\theta$
$\displaystyle\leq\frac{1}{2\sqrt{\pi\ln
2}}\cdot\frac{1}{\kappa}\,\left(1+\theta\log_{2}\kappa\right)2^{-\left(\kappa-2\sqrt{\frac{2\delta(1-\delta)}{\ln
2}}\cdot\sqrt{\kappa}\,Q^{-1}\left(p_{e}\right)+\mathcal{E}_{1}\right)}+\mathcal{O}\left(\frac{\sqrt{-\log
p_{e}}}{\kappa\,2^{\kappa}}\right).$

Now, taking the logarithm of both sides gives

$\displaystyle-\log_{2}S\geq\kappa-2\sqrt{\frac{2\delta(1-\delta)}{\ln
2}}\cdot\sqrt{\kappa}\,Q^{-1}\left(p_{e}\right)+\mathcal{E}_{1}+\log_{2}\kappa-\log_{2}\frac{1+\theta\log_{2}\kappa}{2\sqrt{\pi\ln
2}}+\mathcal{O}\left(\frac{\sqrt{-\log p_{e}}}{\log\kappa}\right).$

Therefore, by replacing $\mathcal{E}_{1}$ from (41), we find

$\displaystyle-\log_{2}S\geq\kappa-2\sqrt{\frac{2\delta(1-\delta)}{\ln
2}}\cdot\sqrt{\kappa}\,Q^{-1}\left(p_{e}\right)$
$\displaystyle+\log_{2}\kappa+\frac{1}{\ln 2}Q^{-1}\left(p_{e}\right)^{2}$
$\displaystyle+\mathcal{O}\left(\log\log\kappa\right)+\mathcal{O}\left(\frac{1}{\sqrt{-\log
p_{e}}}\right)+\mathcal{O}\left(\frac{\sqrt{-\log p_{e}}}{\log\kappa}\right).$

Comparing the orders, then results in

$\displaystyle-\log_{2}S\geq\kappa-2\sqrt{\frac{2\delta(1-\delta)}{\ln
2}}\cdot\sqrt{\kappa}\,Q^{-1}\left(p_{e}\right)+\log_{2}\kappa+\frac{1}{\ln
2}Q^{-1}\left(p_{e}\right)^{2}+\mathcal{O}\left(\log\log\kappa\right).$ (45)

Finally, from (34) and (45), we conclude that

$\displaystyle\log_{2}M^{*}(n,p_{e})$
$\displaystyle\geq\log_{2}p_{e}-\frac{1}{2}\log_{2}\kappa-\log_{2}S$
$\displaystyle\geq\kappa-2\sqrt{\frac{2\delta(1-\delta)}{\ln
2}}\cdot\sqrt{\kappa}\,Q^{-1}\left(p_{e}\right)+\frac{1}{2}\log_{2}\kappa+\log_{2}p_{e}+\frac{1}{\ln
2}Q^{-1}\left(p_{e}\right)^{2}+\mathcal{O}\left(\log\log\kappa\right).$

Note that by part (ii) of Lemma 2, we have

$\frac{1}{\ln 2}Q^{-1}\left(p_{e}\right)^{2}=-2\log_{2}p_{e}+\mathcal{O}(1).$

Hence,

$\displaystyle\log_{2}M^{*}(n,p_{e})$
$\displaystyle\geq\kappa-2\sqrt{\frac{2\delta(1-\delta)}{\ln
2}}\cdot\sqrt{\kappa}\,Q^{-1}\left(p_{e}\right)+\frac{1}{2}\log_{2}\kappa-\log_{2}p_{e}+\mathcal{O}\left(\log\log\kappa\right).$

∎

###### Proof of Theorem 2. Converse Bound.

Let $X\sim$ Bernoulli($\frac{1}{2}$) and $Y$ be the input and output of the
BSC($\delta$), respectively. Also suppose $P_{X}$, $P_{Y}$, and $P_{XY}$ are
distributions of $X$, $Y$, and the joint distribution of $(X,Y)$,
respectively. Define $P=P_{XY}$ and $Q=P_{X}P_{Y}$, and then define $P^{n}$
and $Q^{n}$ in terms of $P$ and $Q$ as they are in Lemma 4. Also consider
$\beta_{1-p_{e}}(P^{n},Q^{n})$ as in (53). Under these choices of $P$ and $Q$,
it can be verified that $\beta_{1-p_{e}}^{n}$ defined in (49), is a piecewise
linear approximation of $\beta_{1-p_{e}}(P^{n},Q^{n})$ based on discrete
values of error probabilities. Therefore, from (49), we can write

$\displaystyle\log_{2}M^{*}(n,p_{e})\leq-\log_{2}\beta_{1-p_{e}}(P^{n},Q^{n}).$

Now, using Lemma 4 for any $\gamma>0$, we have

$\displaystyle\log_{2}M^{*}(n,p_{e})\leq
nD-\sqrt{nV}Q^{-1}\left(p_{e}+\gamma+\frac{B}{\sqrt{n}}\right)-\log_{2}\gamma.$
(46)

Under the specific values of $P$ and $Q$ given above, the quantities
$D$,$V$,$T$, and $B$ in Lemma 4 can be computed as follows:

$\displaystyle D$ $\displaystyle=1-h_{2}(\delta),$ $\displaystyle V$
$\displaystyle=\delta(1-\delta)\left(\log_{2}\frac{1-\delta}{\delta}\right)^{2},$
$\displaystyle T$
$\displaystyle=\delta(1-\delta)\left(\log_{2}\frac{1-\delta}{\delta}\right)^{3}\left(2\delta^{2}-2\delta+1\right),$
$\displaystyle B$
$\displaystyle=\frac{2\delta^{2}-2\delta+1}{\sqrt{\delta(1-\delta)}}.$

Replacing these quantities and using Lemma 1, we can rewrite (46) as the
following:

$\displaystyle\log_{2}M^{*}(n,p_{e})\leq\kappa-2\sqrt{\frac{2\delta(1-\delta)}{\ln
2}}\cdot\sqrt{\kappa}\,Q^{-1}\left(p_{e}+\gamma+\frac{B}{\sqrt{n}}\right)-\log_{2}\gamma+\mathcal{O}\left(\frac{\kappa\sqrt{-\kappa\log_{2}p_{e}}}{n}\right).$

Note that to use Lemma 1, we need to have $\kappa\sqrt{\kappa}=o(n)$. This is
given due to our criterion for being in the low-capacity regime for BSC that
is expressed in Remark 2. This condition is also used for further
simplification of order terms. We then continue as follows.

$\frac{d}{dx}Q^{-1}(x)=-\sqrt{2\pi}\,e^{\frac{Q^{-1}(x)^{2}}{2}}.$

Therefore, by choosing $\gamma=\frac{p_{e}}{\sqrt{\kappa}}$, applying the
Taylor expansion of $Q^{-1}(.)$, and using parts (i) and (ii) of Lemma 2, we
can conclude that

$\displaystyle\log_{2}M^{*}(n,p_{e})\leq\kappa-2\sqrt{\frac{2\delta(1-\delta)}{\ln
2}}\cdot\sqrt{\kappa}\,Q^{-1}\left(p_{e}\right)-\log_{2}\frac{p_{e}}{\sqrt{\kappa}}+\mathcal{O}\left(\frac{\kappa\sqrt{-\kappa\log_{2}p_{e}}}{n}\right)+\mathcal{O}\left(\frac{1}{\sqrt{-\log
p_{e}}}\right).$

Hence, by comparing the orders, we have

$\displaystyle\log_{2}M^{*}(n,p_{e})$
$\displaystyle\leq\kappa-2\sqrt{\frac{2\delta(1-\delta)}{\ln
2}}\cdot\sqrt{\kappa}\,Q^{-1}\left(p_{e}\right)+\frac{1}{2}\log_{2}\kappa-\log_{2}p_{e}+\mathcal{O}\left(\frac{1}{\sqrt{-\log
p_{e}}}\right).$

∎

###### Proof of Corollary 1.

In order to obtain the optimal blocklength $n^{*}$ for transmission of $k$
information bits over a low-capacity BSC($\delta$), it suffices to replcae
$M^{*}(n^{*},p_{e})=k$. Then $n^{*}$ can be computed by solving (5). Replace
$M^{*}(n^{*},p_{e})=k$ and $\kappa=n^{*}C$ in (5), where $C=1-h_{2}(\delta)$,
to obtain

$\displaystyle k=n^{*}C-2\sqrt{\frac{2\delta(1-\delta)}{\ln
2}}\cdot\sqrt{n^{*}C}\,Q^{-1}\left(p_{e}\right)-\log_{2}p_{e}+\mathcal{O}(\log\kappa).$

Define $x=\sqrt{n^{*}C}$, $a=\sqrt{\frac{2\delta(1-\delta)}{\ln
2}}Q^{-1}\left(p_{e}\right)$ and $b=k+\log_{2}p_{e}+\mathcal{O}(\log\kappa)$.
Thus, we have

$x^{2}-2ax-b=0.$

Note that the answer will be $x=a+\sqrt{a^{2}+b}$. Therefore,

$\sqrt{n^{*}C}=a+\sqrt{a^{2}+b}.$

More simplifications are as follows:

$\displaystyle n^{*}$
$\displaystyle=\frac{1}{C}\left(a+\sqrt{a^{2}+b}\right)^{2}$
$\displaystyle=\frac{1}{C}\left(2a^{2}+b+2a\left(\sqrt{k}+\mathcal{O}\left(\frac{-\log
p_{e}}{k}\right)+\mathcal{O}\left(\frac{\log\kappa}{k}\right)\right)\right)$
$\displaystyle=\frac{1}{C}\left(k+2a\sqrt{k}+2a^{2}+\log_{2}p_{e}+\mathcal{O}(\log\kappa)\right).$
(47)

Note that in low-capacity regime, under optimal blocklength,
$\log\kappa\approx\log k$. Therefore, by substituting the values of $C$ and
$a$ in (47), we obtain

$n^{*}=\frac{1}{1-h_{2}(\delta)}\left(k+2\sqrt{\frac{2\delta(1-\delta)}{\ln
2}}Q^{-1}(p_{e})\cdot\sqrt{k}+\frac{4\delta(1-\delta)}{\ln
2}Q^{-1}(p_{e})^{2}+\log_{2}p_{e}+\mathcal{O}(\log k)\right).$

∎

######  Theorem 11 (Berry-Esseen).

For $1\leq i\leq n$, let $X_{i}$’s be i.i.d. random variables with
$\mu=\mathbb{E}[X_{i}]$, $\sigma^{2}=\mathbb{V}ar[X_{i}]$, and
$\rho=\mathbb{E}\left[\left|X_{i}-\mu\right|^{3}\right]<\infty$. Then,

$\left|\Pr\bigg{\\{}\sum_{i=1}^{n}\frac{X_{i}-\mu}{\sigma\sqrt{n}}>x\bigg{\\}}-Q(x)\right|\leq\frac{3\rho}{\sigma^{3}\sqrt{n}}.$

###### Proof.

See [50, Theorem 3.4.9]. ∎

######  Theorem 12 (A Sharp Tail Inequality).

For $1\leq i\leq n$, let $X_{i}$ be independent centered random variables such
that $\left|X_{i}\right|\leq b$. Define
$\sigma^{2}=\mathbb{V}ar\bigg{[}\sum_{i=1}^{n}X_{i}\bigg{]}$. Then, for $0\leq
t\leq\frac{\sigma}{\gamma b}$, we have

$\Pr\bigg{\\{}\sum_{i=1}^{n}X_{i}\geq
t\bigg{\\}}\leq\bigg{(}\frac{1}{\sqrt{2\pi}}\frac{\sigma}{t}+\gamma\frac{b}{\sigma}\bigg{)}e^{-nH(\frac{\sigma^{2}}{n},b,\frac{t}{n})},$

where

$H(\nu,b,x)=\bigg{(}1+\frac{bx}{\nu}\bigg{)}\frac{\nu}{b^{2}+\nu}\ln\bigg{(}1+\frac{bx}{\nu^{2}}\bigg{)}+\bigg{(}1-\frac{x}{b}\bigg{)}\frac{b^{2}}{b^{2}+\nu}\ln\bigg{(}1-\frac{x}{b}\bigg{)}.$

###### Proof.

See [51, Theorem 1.1]. ∎

######  Theorem 13 (RCU Achievability Bound for BSC).

There exists an $(M,p_{e})$-code over BSCn($\delta$) such that

$p_{e}\leq\sum_{r=0}^{n}\binom{n}{r}\delta^{r}(1-\delta)^{n-r}\min\bigg{\\{}1,(M-1)S_{n}^{r}\bigg{\\}},$
(48)

where

$S_{n}^{r}=\sum_{s=0}^{r}\binom{n}{s}2^{-n}.$

###### Proof.

See [8, Corollary 39]. ∎

######  Theorem 14 (Converse Bound for BSC).

For any $(M,p_{e})$-code over the BECn($\delta$), we have

$M\leq\frac{1}{\beta_{1-p_{e}}^{n}}.$ (49)

where $\beta_{\alpha}^{n}$ for a real $\alpha\in[0,1]$ is defined below based
on values of $\beta_{\ell}$ where $\ell$ is an integer:

$\displaystyle\beta_{\alpha}^{n}$
$\displaystyle=(1-\lambda)\beta_{L}+\lambda\beta_{L+1},$
$\displaystyle\beta_{\ell}$
$\displaystyle=\sum_{r=0}^{\ell}\binom{n}{r}2^{-n},$

such that $\lambda\in[0,1)$ and integer $L$ satisfy the following:

$\displaystyle\alpha$
$\displaystyle=(1-\lambda)\alpha_{L}+\lambda\alpha_{L+1},$
$\displaystyle\alpha_{\ell}$
$\displaystyle=\sum_{r=0}^{\ell-1}\binom{n}{r}\delta^{r}(1-\delta)^{n-r}.$

###### Proof.

See [8, Theorem 40]. ∎

######  Lemma 1.

Consider transmission over BSC($\delta$) in low-capacity regime and let
$\kappa=n(1-h_{2}(\delta))$. Then the following hold:

  1. i)

$\sqrt{n}\left(\frac{1}{2}-\delta\right)=\sqrt{\frac{\ln
2}{2}\,\kappa}+\mathcal{O}\left(\frac{\kappa\sqrt{\kappa}}{n}\right).$

  2. ii)

$\sqrt{n}\,\log_{2}\frac{1-\delta}{\delta}=2\sqrt{\frac{2}{\ln
2}\,\kappa}+\mathcal{O}\left(\frac{\kappa\sqrt{\kappa}}{n}\right).$

###### Proof.

  1. i)

Taylor expansion of $h_{2}(\delta)$ around $\frac{1}{2}$ is given by

$h_{2}(\delta)=1-\frac{1}{2\ln
2}\sum_{n=1}^{\infty}\frac{(1-2\delta)^{2n}}{n(2n-1)}.$

Thus, the estimation of $h_{2}(\delta)$ up to the third order will be the
following:

$h_{2}(\delta)=1-\frac{1}{2\ln 2}(1-2\delta)^{2}-\frac{1}{2\ln
2}\cdot\frac{1}{6}(1-2\delta)^{4}+\mathcal{O}\left((1-2\delta)^{6}\right).$

Therefore,

$C=1-h_{2}(\delta)=\frac{1}{2\ln 2}(1-2\delta)^{2}+\frac{1}{2\ln
2}\cdot\frac{1}{6}(1-2\delta)^{4}+\mathcal{O}\left((1-2\delta)^{6}\right).$

Now assuming $x=(1-2\delta)^{2}$ leads to the following equation:

$\frac{x^{2}}{6}+x-2C\ln 2=0.$

Solving this equation gives

$x=3\left(-1+\sqrt{1+\frac{4}{3}C\ln 2}\right)=2C\ln
2+\mathcal{O}\left(C^{2}\right).$

Therefore,

$\frac{1}{2}-\delta=\frac{\sqrt{x}}{2}=\sqrt{\frac{\ln
2}{2}C}+\mathcal{O}\left(C^{\frac{3}{2}}\right).$

Finally,

$\sqrt{n}\left(\frac{1}{2}-\delta\right)=\sqrt{\frac{\ln
2}{2}nC}+\mathcal{O}\left(nC^{\frac{3}{2}}\right).$

Note that $\kappa=nC$. As a result,

$\sqrt{n}\left(\frac{1}{2}-\delta\right)=\sqrt{\frac{\ln
2}{2}\kappa}+\mathcal{O}\left(\frac{\kappa\sqrt{\kappa}}{n}\right).$ (50)

  2. ii)

The first order estimation of the function $\log_{2}({1-\delta})/{\delta}$
around $1/2$ is

$\sqrt{n}\,\log_{2}\frac{1-\delta}{\delta}=\frac{4}{\ln
2}\left(\frac{1}{2}-\delta\right)+\mathcal{O}\left(\left(\frac{1}{2}-\delta\right)^{2}\right).$

Hence, using (50), we arrive at

$\sqrt{n}\,\log_{2}\frac{1-\delta}{\delta}=2\sqrt{\frac{2}{\ln
2}\kappa}+\mathcal{O}\left(\frac{\kappa\sqrt{\kappa}}{n}\right).$

∎

######  Lemma 2.

Suppose $0<p<Q(1)\approx 0.16$.888Note that similar results can be obtained
when $0<p<1$ but taking the assumption $0<p<Q(1)\approx 0.16$ into account
leads to a very simple format for bounds and will not cause any conflict
because we are interested in small bit and block error probabilities. More
specifically, typical values of $p$ would be around $10^{-3}-10^{-6}$. Then
the following hold:

  1. (i)

$\sqrt{2\pi}\,p\,Q^{-1}(p)<e^{-\frac{Q^{-1}(p)^{2}}{2}}<\sqrt{2\pi}\,p\,\left(Q^{-1}(p)+1\right).$

  2. (ii)

$\sqrt{8\pi+2-2\ln p}-2\sqrt{2\pi}<Q^{-1}(p)<\sqrt{-\ln 2\pi-2\ln p}.$

###### Proof.

  1. i)

For $x>0$, it is well known that

$\frac{\phi(x)}{x+\frac{1}{x}}=\left(\frac{x}{1+x^{2}}\right)\phi(x)<Q(x)<\frac{\phi(x)}{x}.$
(51)

Note that for $x>1$, (51) becomes

$\frac{\phi(x)}{x+1}<Q(x)<\frac{\phi(x)}{x}.$ (52)

Now, define $p=Q(x)$. Thus, $x=Q^{-1}(p)>1$. Therefore,

$\frac{e^{-\frac{Q^{-1}(p)^{2}}{2}}}{\sqrt{2\pi}\,\left(Q^{-1}(p)+1\right)}<p<\frac{e^{-\frac{Q^{-1}(p)^{2}}{2}}}{\sqrt{2\pi}\,Q^{-1}(p)}.$

Simplify to get

$\sqrt{2\pi}\,p\,Q^{-1}(p)<e^{-\frac{Q^{-1}(p)^{2}}{2}}<\sqrt{2\pi}\,p\,\left(Q^{-1}(p)+1\right).$

  2. ii)

From (52), for $x>1$ we have

$Q(x)<\frac{e^{-\frac{x^{2}}{2}}}{\sqrt{2\pi}}.$

Therefore,

$x<\sqrt{-2\ln\left(\sqrt{2\pi}Q(x)\right)}.$

Put $x=Q^{-1}(p)$ to get

$Q^{-1}(p)<\sqrt{2\ln\frac{1}{\sqrt{2\pi}\,p}}=\sqrt{-\ln 2\pi-2\ln p}.$

For the other side, note that from (52), for $x>1$, we also have

$Q(x)>\frac{\phi(x)}{2x}=\frac{e^{-\frac{x^{2}}{2}}}{2x\sqrt{2\pi}}.$

Assume $p=Q(x)$. As a result,

$\frac{x^{2}}{2}+2\sqrt{2\pi}\,x+\ln p-1>0.$

Hence,

$Q^{-1}(p)=x>-2\sqrt{2\pi}+\sqrt{8\pi+2-2\ln p}.$

∎

######  Lemma 3.

Suppose $0<\delta<1$ such that $n\delta$ is an integer. Then, for all $0\leq
r\leq n$, we have

$\binom{n}{r}\delta^{r}(1-\delta)^{n-r}\leq\frac{\theta}{\sqrt{n}}.$

where

$\theta=\frac{e}{2\pi\sqrt{\delta(1-\delta)}}.$

###### Proof.

For $0\leq r\leq n$ define

$A(r)=\binom{n}{r}\delta^{r}(1-\delta)^{n-r},$

and

$r^{*}=\arg\max_{0\leq r\leq n}A(r).$

First of all, note that from the Mode of Binomial distribution, we know that
$r^{*}=\lfloor(n+1)\delta\rfloor=n\delta$. Also from Stirling formula, for any
integer $n$, we have

$\sqrt{2\pi n}\left(\frac{n}{e}\right)^{n}\leq n!\leq
e\sqrt{n}\left(\frac{n}{e}\right)^{n}.$

Therefore,

$\displaystyle A(r^{*})$
$\displaystyle=\binom{n}{n\delta}\delta^{n\delta}(1-\delta)^{n-n\delta}=\frac{n!\,\delta^{n\delta}(1-\delta)^{n-n\delta}}{n\delta!\,(n-n\delta)!}$
$\displaystyle\leq\frac{e\sqrt{n}\left(\frac{n}{e}\right)^{n}\delta^{n\delta}(1-\delta)^{n-n\delta}}{\sqrt{2\pi
n\delta}\left(\frac{n\delta}{e}\right)^{n\delta}\sqrt{2\pi
n(1-\delta)}\left(\frac{n(1-\delta)}{e}\right)^{n(1-\delta)}}$
$\displaystyle=\frac{e}{2\pi\sqrt{\delta(1-\delta)}}\cdot\frac{1}{\sqrt{n}}.$

∎

######  Definition 2.

Consider the following binary hypothesis test:

$\displaystyle H_{0}:X\sim P,$ $\displaystyle H_{1}:X\sim Q,$

where $P$ and $Q$ are two probability distributions on the same space
$\mathcal{X}$. Suppose a continuous decision rule $\zeta$ as a mapping from
observation space $\mathcal{X}$ to $[0,1]$ with $\zeta(x)\approx 0$
correspoding to reject $H_{1}$ and $\zeta(x)\approx 1$ correspoding to reject
$H_{0}$. Now, define the smallest type-II error in this binary hypothesis test
given that type-I error is not greater than $p_{e}$ as the following:

$\beta_{1-p_{e}}(P,Q)=\inf_{\zeta:\mathcal{X}\rightarrow[0,1]}\bigg{\\{}\mathbf{E}_{Q}[1-\zeta(X)]:\mathbf{E}_{P}[\zeta(X)]\leq
p_{e}\bigg{\\}}.$ (53)

######  Lemma 4.

Consider two discrete probability distributions $P$ and $Q$ on $\mathcal{X}$.
Define the product distributions $P^{n}$ and $Q^{n}$ as

$P^{n}(\mathbf{x})=\prod_{i=1}^{n}P(x_{i}),\qquad
Q^{n}(\mathbf{x})=\prod_{i=1}^{n}Q(x_{i}),$

where $\mathbf{x}=(x_{1},\dots,x_{n})\in\mathcal{X}^{n}$. Then, for
$p_{e}\in(0,1)$ and any $\gamma$, we have

$\log_{2}\beta_{1-p_{e}}(P^{n},Q^{n})\geq-
nD+\sqrt{nV}Q^{-1}\left(p_{e}+\gamma+\frac{B}{\sqrt{n}}\right)+\log_{2}\gamma,$

where

$\displaystyle D$ $\displaystyle=D(P\|Q),$ $\displaystyle V$
$\displaystyle=\int_{\mathcal{X}}\left(\log_{2}\frac{dP(x)}{dQ(x)}-D\right)^{2}dP(x),$
$\displaystyle T$
$\displaystyle=\int_{\mathcal{X}}\left|\log_{2}\frac{dP(x)}{dQ(x)}-D\right|^{3}dP(x),$
$\displaystyle B$ $\displaystyle=\frac{T}{V^{\frac{3}{2}}}.$

###### Proof.

In the proof of [8, Lemma 14], put
$\alpha=1-p_{e},\Delta=\gamma\sqrt{n},P_{i}=P,Q_{i}=Q$ and consider the
logarithm in base $2$. ∎

###  5.4 Proofs for AWGN Channel

In this section, we prove the converse and achievability bounds of Theorem 3.
In the proofs, we will be using Theorems 15–16 as well as Lemma 5 which are
stated at the end of this section. For the results in coding theory, we
generally refer to [8] as it has well collected and presented the
corresponding proofs. See also [15], [43], [44], [45], and [46].

###### Proof of Theorem 3. Converse Bound.

Let $X$ and $Y$ be a uniform input and the corresponding output of an
AWGN($\eta$) channel. Under the notation of Theorem 15, define $P=P_{XY}$ and
$Q=P_{X}P_{Y}$. Therefore, we have

$M^{*}(n,p_{e})\leq\frac{1}{\beta_{1-p_{e}}\left(P^{n},Q^{n}\right)}.$ (54)

Also from Lemma 4, we obtain

$\log_{2}\beta_{1-p_{e}}(P^{n},Q^{n})\geq-
nD+\sqrt{nV}Q^{-1}\left(p_{e}+\gamma+\frac{B}{\sqrt{n}}\right)+\log_{2}\gamma,$
(55)

where $\gamma>0$ and in order to compute the quantities $D$, $V$ and $B$,
consider the random variable $H_{n}=\log_{2}\frac{dP^{n}(z)}{dQ^{n}(z)}$. It
can be verified that $H_{n}=\sum_{i=1}^{n}h_{i}$, where

$\displaystyle
h_{i}=\frac{1}{2}\log_{2}\left(1+\eta\right)+\frac{\eta}{2(1+\eta)\ln
2}-\frac{1}{2(1+\eta)\ln 2}\left(\eta Z_{i}^{2}-2\sqrt{\eta}\,Z_{i}\right),$

assuming that $Z_{i}$’s are independent standard normal random variables.
Thus, a simple calculation shows that for all
$i\in\left\\{1,\dots,n\right\\}$, we have

$\displaystyle D$
$\displaystyle=\mathbb{E}[h_{i}]=\frac{1}{2}\log_{2}\left(1+\eta\right),$
$\displaystyle V$
$\displaystyle=\mathbb{V}ar[h_{i}]=\frac{\eta(\eta+2)}{2(\eta+1)^{2}\ln^{2}2},$
$\displaystyle T$
$\displaystyle=\mathbb{E}\left[\left|h_{i}-D\right|^{3}\right],$
$\displaystyle B$ $\displaystyle=\frac{T}{V^{\frac{3}{2}}}.$

As we will see in the rest of the proof, computing $T$ and $B$ are not
necessary as they will appear in terms which vanish compared to other terms.
Now, by replacing the values computed above, (54) together with (55) yields

$\displaystyle\log_{2}M^{*}(n,p_{e})\leq\frac{n}{2}\log_{2}\left(1+\eta\right)-\frac{\sqrt{n\eta(\eta+2)}}{\sqrt{2}(\eta+1)\ln
2}Q^{-1}\left(p_{e}+\gamma+\frac{B}{\sqrt{n}}\right)-\log_{2}\gamma.$

Now, by setting $\gamma=\frac{p_{e}}{\sqrt{\kappa}}$ and plugging in Lemma 5,
and then using part (ii) of Lemma 2 together with the definition of $\kappa$,
we conclude that

$\displaystyle\log_{2}M^{*}(n,p_{e})\leq\kappa-\frac{\sqrt{\kappa(\eta+2)}}{(\eta+1)\sqrt{\ln
2}}Q^{-1}\left(p_{e}+\frac{p_{e}}{\sqrt{\kappa}}+\frac{B}{\sqrt{n}}\right)-\log_{2}\frac{p_{e}}{\sqrt{\kappa}}+\mathcal{O}\left(\frac{\kappa^{2}\sqrt{-\log
p_{e}}}{n}\right).$

Note that

$\frac{d}{dx}Q^{-1}(x)=-\sqrt{2\pi}\,e^{\frac{Q^{-1}(x)^{2}}{2}}.$

Therefore, by applying the Taylor expansion of $Q^{-1}(.)$, and using parts
(i) and (ii) of Lemma 2, we achieve

$\displaystyle\log_{2}M^{*}(n,p_{e})\leq\kappa-\frac{\sqrt{\eta+2}}{(\eta+1)\sqrt{\ln
2}}\cdot\sqrt{\kappa}\,Q^{-1}\left(p_{e}\right)-\log_{2}\frac{p_{e}}{\sqrt{\kappa}}+\mathcal{O}\left(\frac{\kappa^{2}\sqrt{-\log_{2}p_{e}}}{n}\right)+\mathcal{O}\left(\frac{1}{\sqrt{-\log
p_{e}}}\right).$

Hence, comparing the orders results in

$\displaystyle\log_{2}M^{*}(n,p_{e})$
$\displaystyle\leq\kappa-\frac{\sqrt{\eta+2}}{(\eta+1)\sqrt{\ln
2}}\cdot\sqrt{\kappa}\,Q^{-1}\left(p_{e}\right)+\frac{1}{2}\log_{2}\kappa-\log_{2}p_{e}+\mathcal{O}\left(\frac{1}{\sqrt{-\log
p_{e}}}\right).$

∎

###### Proof of Theorem 3. Achievability Bound.

The proof of Theorem 16 is still valid in low-capacity regime. As a result,
using Theorem 16 together with Lemma 5 and part (ii) of Lemma 2 results in

$\displaystyle\log_{2}M^{*}(n,p_{e},\eta)$
$\displaystyle\geq\kappa-\frac{\sqrt{\eta+2}}{(\eta+1)\sqrt{\ln
2}}\cdot\sqrt{\kappa}\,Q^{-1}(p_{e})+\mathcal{O}(1)+\mathcal{O}\left(\frac{\kappa\sqrt{-\kappa\log
p_{e}}}{n}\right)$
$\displaystyle=\kappa-\frac{\sqrt{\eta+2}}{(\eta+1)\sqrt{\ln
2}}\cdot\sqrt{\kappa}\,Q^{-1}(p_{e})+\mathcal{O}(1).$

∎

###### Proof of Corollary 2.

In order to obtain the optimal blocklength $n^{*}$ for transmission of $k$
information bits over a low capacity AWGN($\eta$), it suffices to replcae
$M^{*}(n^{*},p_{e},\eta)=k$. Then $n^{*}$ can be computed by solving (6).
Substitute $M^{*}(n^{*},p_{e})=k$ and $\kappa=n^{*}C$ in (6), where
$C=\frac{1}{2}\log_{2}\left(1+\eta\right)$, to obtain

$\displaystyle k=n^{*}C-\frac{\sqrt{\eta+2}}{(\eta+1)\sqrt{\ln
2}}\cdot\sqrt{n^{*}C}\,Q^{-1}\left(p_{e}\right)+\mathcal{E}.$

Define $x=\sqrt{n^{*}C}$, $a=\frac{\sqrt{\eta+2}}{2(\eta+1)\sqrt{\ln
2}}Q^{-1}\left(p_{e}\right)$ and $b=k-\mathcal{E}$. Thus, we have

$x^{2}-2ax-b=0.$

Note that the answer is $x=a+\sqrt{a^{2}+b}$. Therefore,

$\sqrt{n^{*}C}=a+\sqrt{a^{2}+b}.$

More simplifications are as follows:

$\displaystyle n^{*}$
$\displaystyle=\frac{1}{C}\left(a+\sqrt{a^{2}+b}\right)^{2}$
$\displaystyle=\frac{1}{C}\left(2a^{2}+b+2a\left(\sqrt{k}+\mathcal{O}\left(\frac{-\log
p_{e}}{k}\right)+\mathcal{O}\left(\frac{\log\kappa}{k}\right)\right)\right)$
$\displaystyle=\frac{1}{C}\left(k+2a\sqrt{k}+2a^{2}-\mathcal{E}+\mathcal{O}\left(\frac{(-\log
p_{e})^{3/2}}{k}\right)\right).$ (56)

Note that in low-capacity regime, under optimal blocklength,
$\log\kappa\approx\log k$. Therefore, by substituting the values of $C$ and
$a$ in (56) and comparing the orders, we obtain

$n^{*}=\frac{2}{\log_{2}(1+\eta)}\left(k+\frac{\sqrt{\eta+2}}{(\eta+1)\sqrt{\ln
2}}Q^{-1}(p_{e})\cdot\sqrt{k}+\frac{\eta+2}{2(\eta+1)^{2}\ln
2}Q^{-1}(p_{e})^{2}+\mathcal{O}\left(\log_{2}\frac{1}{p_{e}}\right)\right).$

Applying part (ii) of Lemma 2 then results in

$n^{*}=\frac{2}{\log_{2}(1+\eta)}\left(k+\frac{\sqrt{\eta+2}}{(\eta+1)\sqrt{\ln
2}}Q^{-1}(p_{e})\cdot\sqrt{k}+\mathcal{O}\left(\log_{2}\frac{1}{p_{e}}\right)\right).$

∎

######  Theorem 15 (General Converse Bound).

Consider $n$ independent uses of a channel with input alphabet $\mathcal{X}$
and output alphabet $\mathcal{Y}$. Let $P_{X}$, $P_{Y}$, and $P_{XY}$ be
distributions on $\mathcal{X}$, $\mathcal{Y}$, and
$\mathcal{X}\times\mathcal{Y}$, respectively, and suppose $P_{X}^{n}$,
$P_{Y}^{n}$, and $P_{XY}^{n}$ are their product distributions over $n$
independent trials. Then the following holds:

$M^{*}(n,p_{e})\leq\sup_{P_{X}}\inf_{P_{Y}}\frac{1}{\beta_{1-p_{e}}\left(P_{XY}^{n},P_{X}^{n}P_{Y}^{n}\right)}.$

where $\beta_{1-p_{e}}$ is defined as (53).

###### Proof.

See [8, Theorem 29]. ∎

######  Theorem 16 (Achievability Bound for AWGN).

There exists an $(M,p_{e},\eta)$-code over AWGNn($\eta$) such that

$\log_{2}M^{*}(n,p_{e},\eta)\geq nC-\sqrt{nV}\,Q^{-1}(p_{e})+\mathcal{O}(1),$

where

$\displaystyle C$ $\displaystyle=\frac{1}{2}\log_{2}\left(1+\eta\right),$
$\displaystyle V$ $\displaystyle=\frac{\eta(\eta+2)}{2(\eta+1)^{2}\ln^{2}2}.$

###### Proof.

See the achievability bound in [8, Theorem 73]. ∎

######  Lemma 5.

Consider transmission over AWGN($\eta$) in low-capacity regime where by
definition $\kappa=\frac{n}{2}\log_{2}(1+\eta)$. Then we have

$n\eta=2\,\kappa\ln 2+\mathcal{O}\left(\frac{\kappa^{2}}{n}\right).$

###### Proof.

Consider $C=\frac{1}{2}\log(1+\eta)$. Thus, by using Taylor expansion of
$\log(1+x)$ up to the second order, we arrive at

$C=\frac{1}{2\ln 2}\ln(1+\eta)=\frac{1}{2\ln
2}\left(\eta-\frac{\eta^{2}}{2}\right)+\mathcal{O}\left(\eta^{3}\right).$

which leads to solving

$\eta^{2}-2\eta+4C\ln 2=0.$

As a result,

$\displaystyle\eta=1-\sqrt{1-4C\ln 2}=2\,C\ln
2+\mathcal{O}\left(C^{2}\right).$

Now, considering $\kappa=nC$, results in

$n\eta=2\,nC\ln 2+\mathcal{O}\left(nC^{2}\right)=2\,\kappa\ln
2+\mathcal{O}\left(\frac{\kappa^{2}}{n}\right).$

∎

###  5.5 Proofs For Repetition Sufficiency

###### Proof of Theorem 4.

Let $m$ be the number of repeated blocks of size $r$, i.e., $m=\frac{n}{r}$
and consequently, $m_{\beta}=\frac{n}{r_{\beta}}$. Note that the maximum
achievable rate in this setting is
$\frac{1-\epsilon^{r}}{r}=\frac{m}{n}\left(1-\epsilon^{\frac{n}{m}}\right)$.
Thus, $m_{\beta}$ is the solution of the following problem:

minimize $\displaystyle m$ subject to $\displaystyle
m\left(1-\epsilon^{\frac{n}{m}}\right)\geq\beta n(1-\epsilon).$

It can be easily verified that the answer of this problem $m_{\beta}$ indeed
satisfies

$m_{\beta}\left(1-\epsilon^{\frac{n}{m_{\beta}}}\right)=\beta n(1-\epsilon).$

Now putting $\kappa=n(1-\epsilon)$ gives

$m_{\beta}\left(1-\epsilon^{\frac{\kappa}{(1-\epsilon)m_{\beta}}}\right)=\beta\kappa.$

Define $x=\frac{\kappa}{m_{\beta}}$ to get

$1-\epsilon^{\frac{x}{1-\epsilon}}=\beta x.$

Therefore,

$1-\beta
x=\epsilon^{\frac{x}{1-\epsilon}}=e^{\frac{\ln\epsilon}{1-\epsilon}\,x}=e^{-x\ell},$

where $\ell=-\frac{\ln\epsilon}{1-\epsilon}$. Now, let $z=x\ell$. Thus,

$1-\frac{\beta}{\ell}z=e^{-z}.$

Finally, define $\gamma=\frac{\beta}{\ell}$ to get

$1-\gamma z=e^{-z}.$ (57)

Then by using part (ii) of Lemma 6, we can write

$\displaystyle 1-\gamma z$ $\displaystyle=e^{-z}\leq 1-z+\frac{z^{2}}{2},$
$\displaystyle-\gamma$ $\displaystyle\leq-1+\frac{z}{2},$ $\displaystyle
2(1-\gamma)$ $\displaystyle\leq z.$ (58)

Taking logarithm of both sides of (57), gives

$-z=\ln(1-\gamma z).$

Now use part (iii) of Lemma 6 to obtain

$-z=\ln(1-\gamma z)\leq-\gamma z-\frac{(\gamma z)^{2}}{2}.$

Therefore,

$z\leq 2(1-\gamma)\frac{1}{\gamma^{2}}.$ (59)

Note that (58) together with (59) yields

$2(1-\gamma)\leq z\leq 2(1-\gamma)\frac{1}{\gamma^{2}}.$

Remember $z=x\ell=\frac{\kappa\ell}{m_{\beta}}$ . Hence,

$\frac{\kappa\ell}{2(1-\gamma)}\cdot\gamma^{2}\leq
m_{\beta}\leq\frac{\kappa\ell}{2(1-\gamma)}.$

Now, replacing $\gamma=\frac{\beta}{\ell}$, $\kappa=n(1-\epsilon)$, and
$m_{\beta}=\frac{n}{r_{\beta}}$ result in

$\frac{n(1-\epsilon)\ell}{2\left(1-\frac{\beta}{\ell}\right)}\cdot\left(\frac{\beta}{\ell}\right)^{2}\leq\frac{n}{r_{\beta}}\leq\frac{n(1-\epsilon)\ell}{2\left(1-\frac{\beta}{\ell}\right)}.$

∎

###### Proof of Theorem 5.

We use extremes of information combining. Consider two BMS channels
$W_{1},W_{2}$ with capacity $C_{1},C_{2}$ respectively. Note that
$\text{BEC}(1-C_{1})$ has capacity $C_{1}$ and $\text{BEC}(1-C_{2})$ has
capacity $C_{2}$. Then we know from extremes of information combining [52,
Chapter 4] that

$C(W_{1}\circledast W_{2})\leq
C\left(\text{BEC}(1-C_{1})\circledast\text{BEC}(1-C_{2})\right),$ (60)

where $W_{1}\circledast W_{2}$ is the BMS channel whose output is formed as
the union of the output of $W_{1}$ and $W_{2}$, i.e., we send the input bit
once through $W_{1}$ and once through $W_{2}$ and the resulting outcomes
together will be the outcome of $W_{1}\circledast W_{2}$.

Now, it is clear that for any BMS channel $W$ we have

$W^{r}=\underbrace{W\circledast\cdots\circledast W}_{r\text{ times}}.$

Thus, assuming $C(W)=C$, then by using (60) $r$ times we obtain $C(W^{r})\leq
C(\text{BEC}(1-C)^{r})$. ∎

######  Lemma 6.

Suppose $z\geq 0$. Then,

  1. i)

$e^{-z}\geq 1-z$.

  2. ii)

$e^{-z}\leq 1-z+\frac{z^{2}}{2}$.

  3. iii)

If $0<z<1$, then $\ln(1-z)\leq-z-\frac{z^{2}}{2}$.

###### Proof.

  1. i)

Define $f(z)=e^{-z}-1+z$. Note that $f^{\prime}(z)=-e^{-z}+1\geq 0$ for $z\geq
0$. This means $f$ is increasing over $z\geq 0$. Thus, if $z\geq 0$, then
$f(z)\geq f(0)=0$.

  2. ii)

Define $g(z)=e^{-z}-1+z-\frac{z^{2}}{2}$. Note that
$g^{\prime}(z)=-e^{-z}+1-z\leq 0$ for $z\geq 0$ due to part (i). This means
$g$ is decreasing over $z\geq 0$. Thus, if $z\geq 0$, then $g(z)\leq g(0)=0$.

  3. iii)

$\ln(1-z)=-\sum_{i=1}^{\infty}\frac{z^{i}}{i}\leq-z-\frac{z^{2}}{2}$ for
$0<z<1$.

∎

###  5.6 Proof of Theorem 6

Let $i\in[n]$ be an arbitrary index. Recall that in order to construct the
$i$-th sub-channel for a polar code of length $n=2^{m}$ on channel $W$, which
is denoted by $W_{n}^{(i)}$, we proceed as follows: (i) Consider the binary
expansion $i=b_{1}b_{2}\cdots b_{m}$. (ii) Start with $W_{0}=W$. (iii) For
$j\in\left\\{1,\dots,m\right\\}$, let $W_{j}=W_{j-1}\circledast W_{j-1}$ if
$b_{j}=1$, and otherwise, let $W_{j}=W_{j-1}\,\leavevmode\hbox to6.23pt{\vbox
to6.06pt{\pgfpicture\makeatletter\hbox{\hskip 3.1165pt\lower-3.0297pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}}{}{}{}{}{}
{{}\pgfsys@moveto{2.9165pt}{2.8297pt}\pgfsys@lineto{-2.9165pt}{2.8297pt}\pgfsys@lineto{-2.9165pt}{-2.8297pt}\pgfsys@lineto{2.9165pt}{-2.8297pt}\pgfsys@closepath\pgfsys@moveto{-2.9165pt}{-2.8297pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{0.5}{0.0}{0.0}{0.5}{-1.25pt}{-1.1632pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$\ast$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}\,W_{j-1}$. (iv) The
channel $W_{m}$ is the sub-channel corresponding to the $i$-th index. Also
recall that for any BMS channel $W$, we have (see [53, Lemma 3.16], [54])

$Z(W\circledast W)=Z(W)^{2}\,\,\,\text{ and }\,\,\,Z(W\,\leavevmode\hbox
to6.23pt{\vbox to6.06pt{\pgfpicture\makeatletter\hbox{\hskip
3.1165pt\lower-3.0297pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}}{}{}{}{}{}
{{}\pgfsys@moveto{2.9165pt}{2.8297pt}\pgfsys@lineto{-2.9165pt}{2.8297pt}\pgfsys@lineto{-2.9165pt}{-2.8297pt}\pgfsys@lineto{2.9165pt}{-2.8297pt}\pgfsys@closepath\pgfsys@moveto{-2.9165pt}{-2.8297pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{0.5}{0.0}{0.0}{0.5}{-1.25pt}{-1.1632pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$\ast$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}\,W)\geq\sqrt{1-(1-(1-Z(W))^{2})^{2}},$

which by simple manipulations will be simplified to

$1-Z(W\circledast W)\leq 2(1-Z(W))\,\,\,\text{ and
}\,\,\,1-Z(W\,\leavevmode\hbox to6.23pt{\vbox
to6.06pt{\pgfpicture\makeatletter\hbox{\hskip 3.1165pt\lower-3.0297pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}}{}{}{}{}{}
{{}\pgfsys@moveto{2.9165pt}{2.8297pt}\pgfsys@lineto{-2.9165pt}{2.8297pt}\pgfsys@lineto{-2.9165pt}{-2.8297pt}\pgfsys@lineto{2.9165pt}{-2.8297pt}\pgfsys@closepath\pgfsys@moveto{-2.9165pt}{-2.8297pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{0.5}{0.0}{0.0}{0.5}{-1.25pt}{-1.1632pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$\ast$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}\,W)\leq
4*(1-Z(W))^{2}.$ (61)

Now, for an integer $t\leq m$ let $i_{t}$ be such that in the binary expansion
$i_{t}=b_{1}b_{2}\cdots b_{m}$, all the bits $b_{j}$ are equal to $1$ except
for $b_{t}$ which is $0$ (i.e., $i_{t}=2^{m}-2^{m-t}-1$). Using the bounds in
(61), we can write

$1-Z(W_{n}^{(i_{t})})\leq 2^{m-t+2}\left(2^{t-1}(1-Z(W))\right)^{2}.$

Thus, if $i_{t}$ is a good sub-channel, then we must have
$Z(W_{m}^{(i_{t})})\leq\frac{1}{2}$ which by using the above inequality gives
us

$2^{m-t+2}\left(2^{t-1}(1-Z(W))\right)^{2}\geq\frac{1}{2}\Longrightarrow
2^{t}\geq\frac{1}{2^{m+1}(1-Z(W))^{2}}.$

Note also that for any BMS channel, we have $C(W)\geq 1-Z(W)$, and thus the
above inequality implies

$2^{t}\geq\frac{1}{2^{m+1}C(W)^{2}}\Longrightarrow 2^{m-t+1}\leq
4(2^{m}C(W))^{2}=4(n(c(W)))^{2}.$ (62)

Now, recalling the fact that the binary expansion of index $i_{t}$ has only
one position with zero value (the $t$-th position), we can conclude that for
any other good index $i$, we must have the following: The first $t-1$ bits of
the binary expansion of $i-1$ should be $1$, and $t$ is lower bounded from
(62). This means that the polar code corresponding to $W$ will have at least
$2^{t-1}$ repetitions in the beginning.

## References

  * [1] M. Fereydounian, M. V. Jamali, H. Hassani, and H. Mahdavifar, “Channel coding at low capacity,” in _Proc. 2019 IEEE Inf. Theory Workshop (ITW)_ , Aug 2019, pp. 1–5.
  * [2] R. Ratasuk, N. Mangalvedhe, Y. Zhang, M. Robert, and J.-P. Koskinen, “Overview of narrowband IoT in LTE Rel-13,” in _Proc. IEEE Conf. Standard Commun. Netw. (CSCN)_ , Berlin, Germany, Oct./Nov. 2016, pp. 1–7.
  * [3] “5G; Study on scenarios and requirements for next generation access technologies,” 3GPP TR 38.913 version 14.3.0 Release 14, 2017.
  * [4] R. Ratasuk, B. Vejlgaard, N. Mangalvedhe, and A. Ghosh, “NB-IoT system for M2M communication,” in _Proc. IEEE Wireless Commun. Netw. Conf._ , Apr. 2016, pp. 1–5.
  * [5] R. Dobrushin, “Mathematical problems in the Shannon theory of optimal coding of information,” in _Proc. 4th Berkeley Symp. Math., Statist., and Probability_ , vol. 1, 1961, pp. 211–252.
  * [6] V. Strassen, “Asymptotische abschätzungen in Shannon’s informationstheorie,” _in Trans. 3rd Prague Conf. Inf. Theory_, pp. 689–723, Prague, 1962.
  * [7] Y. Polyanskiy, H. V. Poor, and S. Verdú, “Channel coding rate in the finite blocklength regime,” _IEEE Trans. Inf. Theory_ , vol. 56, no. 5, pp. 2307–2359, 2010.
  * [8] Y. Polyanskiy, “Channel coding: non-asymptotic fundamental limits,” Ph.D. dissertation, Prinston University, 11 2010.
  * [9] V. Y. F. Tan and M. Tomamichel, “The third-order term in the normal approximation for the AWGN channel,” _IEEE Trans. Inf. Theory_ , vol. 61, no. 5, pp. 2430–2438, May 2015.
  * [10] T. Erseghe, “Coding in the finite-blocklength regime: Bounds based on laplace integrals and their asymptotic approximations,” _IEEE Trans. Inf. Theory_ , vol. 62, no. 12, pp. 6854–6883, Dec 2016.
  * [11] P. Moulin, “The log-volume of optimal codes for memoryless channels, asymptotically within a few nats,” _IEEE Trans. Inf. Theory_ , vol. 63, no. 4, pp. 2278–2313, April 2017.
  * [12] J. Scarlett, A. Martinez, and A. G. i. Fabregas, “Mismatched decoding: Error exponents, second-order rates and saddlepoint approximations,” _IEEE Trans. Inf. Theory_ , vol. 60, no. 5, pp. 2647–2666, 2014.
  * [13] W. Yang, A. Collins, G. Durisi, Y. Polyanskiy, and H. V. Poor, “Beta–Beta bounds: Finite-blocklength analog of the golden formula,” _IEEE Trans. Inf. Theory_ , vol. 64, pp. 6236–6256, 2018.
  * [14] E. Arikan, “Channel polarization: A method for constructing capacity-achieving codes for symmetric binary-input memoryless channels,” _IEEE Trans. Inf. Theory_ , vol. 55, no. 7, pp. 3051–3073, 2009.
  * [15] V. Y. F. Tan, “Asymptotic estimates in information theory with non-vanishing error probabilities,” _arXiv:1504.02608v1 [cs.IT]_.
  * [16] C. E. Shannon, “A mathematical theory of communication,” _Bell System Tech. Journal_ , no. 27, pp. 379–423, 1948.
  * [17] J. Wolfowitz, “Notes on a general strong converse,” _Inf. Contr._ , pp. 1–4, 1968.
  * [18] M. Hayashi, “Information spectrum approach to second-order coding rate in channel coding,” _IEEE Trans. Inf. Theory_ , vol. 55, no. 11, pp. 4947–4966, 2009.
  * [19] E. C. Posner, “Properties of error-correcting codes at low signal-to-noise ratios,” _SIAM J. Appl. Math._ , vol. 15, no. 4, pp. 775–798, 1967.
  * [20] Chi-Chao Chao, R. J. McEliece, L. Swanson, and E. R. Rodemich, “Performance of binary block codes at low signal-to-noise ratios,” _IEEE Trans. Inf. Theory_ , vol. 38, no. 6, pp. 1677–1687, Nov 1992.
  * [21] E. Arıkan, “Source polarization,” in _Proc. 2010 IEEE Int. Symp. Inf. Theory (ISIT)_ , 2010, pp. 899–903.
  * [22] E. Abbe, “Polarization and randomness extraction,” in _Proc. 2011 IEEE Int. Symp. Inf. Theory (ISIT)_ , 2011, pp. 184–188.
  * [23] M. Mondelli, S. H. Hassani, I. Sason, and R. L. Urbanke, “Achieving Marton’s region for broadcast channels using polar codes,” _IEEE Trans. Inf. Theory_ , vol. 61, no. 2, pp. 783–800, 2015.
  * [24] N. Goela, E. Abbe, and M. Gastpar, “Polar codes for broadcast channels,” _IEEE Trans. Inf. Theory_ , vol. 61, no. 2, pp. 758–782, 2015.
  * [25] E. Şaşoğlu, E. Telatar, and E. Yeh, “Polar codes for the two-user binary-input multiple-access channel,” _IEEE Trans. Inf. Theory_ , vol. 59, no. 10, pp. 6583–6592, 2013.
  * [26] H. Mahdavifar, M. El-Khamy, J. Lee, and I. Kang, “Achieving the uniform rate region of general multiple access channels by polar coding,” _IEEE Trans. Commun._ , vol. 64, no. 2, pp. 467–478, 2016.
  * [27] H. Mahdavifar and A. Vardy, “Achieving the secrecy capacity of wiretap channels using polar codes,” _IEEE Trans. Inf. Theory_ , vol. 57, no. 10, pp. 6428–6443, 2011.
  * [28] M. Andersson, V. Rathi, R. Thobaben, J. Kliewer, and M. Skoglund, “Nested polar codes for wiretap and relay channels,” _IEEE Commun. Lett._ , vol. 14, no. 8, pp. 752–754, 2010.
  * [29] H. Mahdavifar, M. El-Khamy, J. Lee, and I. Kang, “Polar coding for bit-interleaved coded modulation,” _IEEE Trans. Veh. Technol._ , vol. 65, no. 5, pp. 3115–3127, 2015.
  * [30] S. H. Hassani, S. B. Korada, and R. Urbanke, “The compound capacity of polar codes,” in _Proc. 47th Annu. Allerton Conf. Commun., Control, and Comput._ IEEE, 2009, pp. 16–21.
  * [31] E. Şaşoğlu and L. Wang, “Universal polarization,” _IEEE Trans. Inf. Theory_ , vol. 62, no. 6, pp. 2937–2946, 2016.
  * [32] S. H. Hassani and R. Urbanke, “Universal polar codes,” in _Proc. 2014 IEEE Int. Symp. Inf. Theory (ISIT)_. IEEE, 2014, pp. 1451–1455.
  * [33] A. Alamdar-Yazdi and F. R. Kschischang, “A simplified successive-cancellation decoder for polar codes,” _IEEE Commun. Lett._ , vol. 15, no. 12, pp. 1378–1380, 2011.
  * [34] M. El-Khamy, H. Mahdavifar, G. Feygin, J. Lee, and I. Kang, “Relaxed polar codes,” _IEEE Trans. Inf. Theory_ , vol. 63, no. 4, pp. 1986–2000, 2017\.
  * [35] I. Dumer, “Polar codes with a stepped boundary,” in _Proc. 2017 IEEE Int. Symp. Inf. Theory (ISIT)_. IEEE, 2017, pp. 2613–2617.
  * [36] I. Tal and A. Vardy, “List decoding of polar codes,” _IEEE Trans. Inf. Theory_ , vol. 61, no. 5, pp. 2213–2226, 2015.
  * [37] S. H. Hassani, K. Alishahi, and R. L. Urbanke, “Finite-length scaling for polar codes,” _IEEE Trans. Inf. Theory_ , vol. 60, no. 10, pp. 5875–5898, 2014.
  * [38] M. Mondelli, S. H. Hassani, and R. L. Urbanke, “Unified scaling of polar codes: Error exponent, scaling exponent, moderate deviations, and error floors,” _IEEE Trans. Inf. Theory_ , vol. 62, no. 12, pp. 6698–6712, 2016\.
  * [39] D. Goldin and D. Burshtein, “Improved bounds on the finite length scaling of polar codes,” _IEEE Trans. Inf. Theory_ , vol. 60, no. 11, pp. 6966–6978, 2014.
  * [40] V. Guruswami and P. Xia, “Polar codes: Speed of polarization and polynomial gap to capacity,” _IEEE Trans. Inf. Theory_ , vol. 61, no. 1, pp. 3–16, 2015\.
  * [41] H. Mahdavifar, “Fast polarization for non-stationary channels,” in _Proc. 2017 IEEE Int. Symp. Inf. Theory (ISIT)_. IEEE, 2017, pp. 849–853.
  * [42] I. Dumer and K. Shabunov, “Recursive list decoding for Reed-Muller codes,” _ArXiv_ , vol. abs/1703.05304, 2017.
  * [43] J. Wolfowitz, _Coding Theorems of Information Theory_ , 3rd ed. New York: Springer-Verlag, 1978.
  * [44] R. G. Gallager, _Information Theory and Reliable Communication_. New York: Wiley, 1968.
  * [45] H. V. Poor, _An Introduction to Signal Detection and Estimation_. New York: Springer-Verlag, 1994.
  * [46] P. Elias, “Coding for two noisy channels,” in _Proc. 3d London Symp. Inf. Theory. Washington, DC_ , Sep. 1955, pp. 61–76.
  * [47] V. Zacharovas and H.-K. Hwang, “A Charlier–Parseval approach to Poisson approximation and its applications,” _Lithuanian Math. J._ , no. 1, pp. 88–119, 2010.
  * [48] C. Stein, _Approximate Computation of Expectations_. Inst. of Mathematical Statistic, 1987.
  * [49] M. D. Hirschhorn and M. B. Villarino, “The missing factor in Hoeffding’s inequalities,” _The Ramanujan J._ , no. 34, pp. 73–81, 2014.
  * [50] R. Durrett, _Probability: Theory and Examples_. Cambridge University Press, 2010.
  * [51] M. Talagrand, “The missing factor in Hoeffding’s inequalities,” _Annales de l’I.H.P. Probabilités et statistiques_ , no. 4, pp. 689–702, 1995.
  * [52] T. Richardson and R. Urbanke, _Modern Coding Theory_. Cambridge University Press, 2008.
  * [53] S. B. Korada, “Polar codes for channel and source coding,” Ph.D. dissertation, Ecole Polytechnique Federale de Lausanne, 7 2009.
  * [54] S. H. Hassani, “Polarization and spatial coupling: Two techniques to boost performance,” Ph.D. dissertation, Ecole Polytechnique Federale de Lausanne, 9 2013.