# A New Polar Code Design Based on
Reciprocal Channel Approximation

Hideki Ochiai, Kosuke Ikeya, and Patrick Mitran H. Ochiai and K. Ikeya are
with the Department of Electrical and Computer Engineering, Yokohama National
University, Yokohama, Japan. (email<EMAIL_ADDRESS>ikeya-kosuke-
fc@ynu.jp)P. Mitran is with the Department of Electrical and Computer
Engineering, University of Waterloo, ON, Canada<EMAIL_ADDRESS>
###### Abstract

This paper revisits polar code design for a binary-input additive white
Gaussian noise (BI-AWGN) channel when successive cancellation (SC) decoding is
applied at the receiver. We focus on the reciprocal channel approximation
(RCA), which is often adopted in the design of low-density parity-check (LDPC)
codes. In order to apply RCA to polar code design for various codeword
lengths, we derive rigorous closed-form approximations that are valid over a
wide range of SNR over an AWGN channel, for both the mutual information of
BPSK signaling and the corresponding reciprocal channel mapping. As a result,
the computational complexity required for evaluating channel polarization is
thus equivalent to that based on the popular Gaussian approximation (GA)
approach. Simulation results show that the proposed polar code design based on
RCA outperforms those based on GA as well as the so-called improved GA (IGA)
approach, especially as the codeword length is increased. Furthermore, the
RCA-based design yields a better block error rate (BLER) estimate compared to
GA-based approaches.

###### Index Terms:

Code construction, density evolution, Gaussian approximation, polar codes,
reciprocal channel approximation.

##  I Introduction

One of the most striking properties of polar codes [1] is their capacity
approaching behavior that is achievable with low-complexity successive
cancellation (SC) decoding. Specifically, for a codeword length of $N$ bits,
the decoding complexity is only $O(N\log N)$, which is significantly lower
than other known capacity approaching codes that are available in practice. As
a result of channel polarization, the design of polar codes is equivalent to
the identification of good channels and bad channels, where the former
channels are used for information transmission and the latter channels are
left unused (i.e., frozen). The main focus of this paper is on the design of
polar codes with various codeword lengths over a binary-input additive white
Gaussian noise (BI-AWGN) channel.

There have been various techniques proposed for polar code design over a BI-
AWGN channel. The most accurate analytical approach is the use of density
evolution [2, 3], originally developed for the design of low-density parity-
check (LDPC) codes, and its applicability to polar codes has been identified
in [4]. Density evolution tracks the probability distribution of the channel
or its log-likelihood ratio (LLR), and in order to improve its accuracy, it
should be computed with sufficient quantization and dynamic range. Therefore,
density evolution is highly demanding in terms of space and computational
complexity, especially when the codeword length increases. A more tractable
approach with limited space complexity was proposed in [5]. Nevertheless, the
approach involves quantization, and thus the overall complexity depends not
only on the codeword length but also on the required precision. On the other
hand, a significantly simpler approach is Gaussian approximation (GA) [6].
Also initially developed for the design of LDPC codes, its applicability to
polar code design has been well investigated [7]. It has been pointed out in
[8] that GA with the original approximation function developed in [6] may not
necessarily work accurately when the equivalent SNR values of the channels
after polarization become low. Consequently, a modified version, which will be
referred to as improved GA (IGA) in this work, has been proposed [8].
Furthermore, there have been various design approaches proposed in the recent
literature, targeting specific polar decoding algorithms. For example, in the
case of successive cancellation list (SCL) decoding [9] or belief propagation
(BP) decoding [10], learning-based approaches such as genetic algorithms and
reinforcement learning have been proposed in [11] and [12], respectively. The
major limitations of these approaches are their lack of flexibility and
scalability since computationally demanding training should be performed for
each given combination of the code parameters such as block length and code
rate.

In this work, we consider the application of the so-called reciprocal channel
approximation (RCA), introduced by Chung in [13], that is motivated by the
duality property of mutual information that holds between a repetition code
and parity-check code over a binary erasure channel (BEC) [14]. This approach
has been originally adopted in the design of LDPC and other related codes [13,
15, 16, 17, 18], and it was numerically demonstrated in [13, Chapter 7] that
it offers a better approximation for density evolution in the case of BI-AWGN
channels than the conventional GA. By numerical study and simulation, it will
be shown that polar codes designed based on RCA exhibit better performance
than those based on (improved) GA, and the gain becomes noticeable as the
block length increases. The superior performance improvement will be
demonstrated for polar codes with very long lengths (such as $N=2^{18}$ bits),
as is considered in practical optical communications [19]. (See, also [20],
where a polar code of length $2^{20}$ bits is considered.)

The design of polar codes based on RCA has been initially considered in [21]
as well as [22]. RCA-based designs make use of the mutual information of BPSK
signaling over an AWGN channel as well as its inverse function, which should
be calculated numerically. There are several closed-form approximations
available in the literature, and in [22] the two approximations developed in
[16] and [23] are compared, indicating the sensitivity of polar code
performance to the choice of approximation. For this reason, in this work we
introduce rigorous closed-form expressions for the mutual information
$C(\gamma)$ of BPSK as a function of SNR $\gamma$ as well as its inverse
function $C^{-1}(\cdot)$ that can be used for design of polar codes with long
codeword lengths.

The main contributions of this work are as follows:

  * •

We derive a closed-form piece-wise continuous mutual information expression
for BPSK signaling over AWGN channels with guaranteed convergence in the case
of high and low SNR based on the asymptotic analysis of the mutual information
function. This expression is exploited to design polar codes based on RCA
supporting a wide range of SNR after polarization.

  * •

We develop an explicit algorithm that identifies SNR after channel
polarization using only closed-form equations, which can thus be calculated
with low complexity.

  * •

By simulation, we demonstrate that the RCA-based design can achieve better
performance as well as offer a better block error rate (BLER) estimate
compared to GA-based approaches, especially as the block length increases and
the code rate is moderate (e.g., around $1/2$).

The remainder of the paper is organized as follows. Section II reviews the
principle of RCA from the viewpoint of polar code design and develops a
general algorithm. The key function $\Lambda(\xi)$ that corresponds to the
reciprocal channel mapping defined in [13] and that transforms SNR in the log
domain based on RCA, is introduced. Section III develops closed-form
expressions of the mutual information for BPSK signaling as well as its
inverse, and its accuracy is compared with two other formulas available in the
literature. Based on the developed mathematical tools, closed-form
approximations for the associated function $\Lambda(\xi)$ are derived in
Section IV, which completes the proposed algorithm. Simulation results as well
as the estimated BLER are compared in Section V, which reveals the
effectiveness of the RCA-based polar code design using the proposed algorithm.
Finally, concluding remarks are given in Section VI.

##  II Polar Codes and Reciprocal Channel Approximation

###  II-A Polar Codes

We start with the simplest binary polar code of codeword (or block) length
$N=2$ (Arıkan’s kernel) shown in Fig. 1, where the information bits
$u_{0},u_{1}\in{\mathbb{F}}_{2}$ and the coded bits
$x_{0},x_{1}\in{\mathbb{F}}_{2}$ are related by

$\displaystyle\begin{cases}x_{0}&=u_{0}+u_{1},\\\ x_{1}&=u_{1}.\end{cases}$
(1)

The coded bits $x_{0}$ and $x_{1}$ are modulated by BPSK and are transmitted
over AWGN channels, denoted by ${\sf W}_{0}$ and ${\sf W}_{1}$, where the SNRs
of the channels are $\gamma_{0}$ and $\gamma_{1}$, respectively, as
illustrated in Fig. 1, with the received symbols given by $y_{0}$ and $y_{1}$.

Assuming that $u_{0}$ is decoded first, since

$\displaystyle u_{0}$ $\displaystyle=x_{0}+x_{1},$ (2)

$u_{0}$ can be seen as a check node connected to $x_{0}$ and $x_{1}$ in the
Tanner graph. Once the estimate of $u_{0}$, denoted by
$\hat{u}_{0}\in{\mathbb{F}}_{2}$, is given, $u_{1}$ can be uniquely determined
by either of $x_{0}$ or $x_{1}$, i.e., $u_{1}$ is a variable node connected to
both $x_{0}$ and $x_{1}$.

Polar codes of length $N=2^{n}$ for an integer $n>1$ can be obtained by the
recursive application of the above kernel [1].

Figure 1: Polar encoder and associated notations for $N=2$.

###  II-B RCA

Following [18], we briefly describe the principle of RCA. Let us first
consider a BEC where the erasure probability is $e^{-s}$ and the non-erasure
probability $e^{-r}$, i.e., $e^{-s}+e^{-r}=1$, for $s,r>0$. Let $C(s)$ denote
the capacity of this channel, i.e., $C(s)=1-e^{-s}$. Then, it follows that
$C(s)+C(r)=1$. Let $s_{i}$ denote the above parameter $s$ for the bit $x_{i}$
transmitted over the corresponding BEC and let us define $r_{i}$ such that
$e^{-s_{i}}+e^{-r_{i}}=1$. For a variable node $u_{1}$ connected to $x_{0}$
and $x_{1}$, its erasure probability is given by
$e^{-s_{0}}e^{-s_{1}}=e^{-(s_{0}+s_{1})}$, i.e., it is characterized by the
sum of $s_{0}$ and $s_{1}$. For a check node $u_{0}$ connected to $x_{0}$ and
$x_{1}$, its corresponding non-erasure probability is given by
$(1-e^{-s_{0}})(1-e^{-s_{1}})=e^{-(r_{0}+r_{1})}$, i.e., it is also
characterized by the sum of $r_{0}$ and $r_{1}$. In other words, for BEC, the
parameter $s$ is additive for variable nodes, whereas the parameter $r$ is
additive for check nodes [18].

We now apply the above RCA concept to the binary-input AWGN (BI-AWGN) channel.
We define $C(\gamma)$ as the capacity of the BI-AWGN channel with the signal-
to-noise power ratio (SNR) given by $\gamma$. Similar to BEC, the additive
property holds for the parameter $\gamma$ in the case of the variable node as
long as all the connecting nodes are associated with mutually independent AWGN
channels. This stems from the fact that the LLR is additive at the variable
node, and both mean and variance of the LLR corresponding to BI-AWGN channels
are proportional to the channel SNR [8]. Let us now define the SNR parameter
$\lambda$ corresponding to the check node such that $C(\gamma)+C(\lambda)=1$,
and assume that the additive property also holds for the parameter $\lambda$
at the check node. Since this does not strictly hold for general BI-AWGN
channels, this is an approximation, which is thus referred to as the
reciprocal channel approximation (RCA) in [13, Section 7.4].

For a given channel SNR $\gamma$, the parameter $\lambda$ can be found by
solving

$\displaystyle C(\lambda)=1-C(\gamma),$ (3)

for $\lambda$. Since $C(\gamma)$ is a strictly increasing function for
$\gamma>0$, we can define its inverse function $C^{-1}(\cdot)$ and write

$\displaystyle\lambda=C^{-1}\left(1-C(\gamma)\right)\triangleq\Psi(\gamma).$
(4)

The above function corresponds to the reciprocal channel mapping introduced in
[13, Definition 7.3], also referred to as self-inverting reciprocal energy
function in [18], applied to BI-AWGN channels. Our goal is to find a suitable
expression for the function $\Psi(\gamma)$ that can support a wide range of
SNR value $\gamma$ with high accuracy. Note that since (3) holds with
$\lambda$ and $\gamma$ interchanged, one can easily verify that

$\displaystyle\Psi\left(\Psi\left(\gamma\right)\right)=\gamma,$ (5)

i.e., $\Psi(\gamma)$ is a self-inverse function satisfying
$\Psi(\gamma)=\Psi^{-1}(\gamma)$ [13].

If $\gamma_{0}$ and $\gamma_{1}$ are the SNRs of the channels where the bits
$x_{0}$ and $x_{1}$ are transmitted, respectively, then the SNR corresponding
to the variable node $u_{1}$, denoted by $\hat{\gamma}_{1}$, is expressed as

$\displaystyle\hat{\gamma}_{1}=\gamma_{0}+\gamma_{1}.$ (6)

On the other hand, the SNR corresponding to the check node $u_{0}$, denoted by
$\hat{\gamma}_{0}$, is similarly expressed based on the RCA principle [13,
Section 7.4] as

$\displaystyle\Psi\left(\hat{\gamma}_{0}\right)=\Psi\left(\gamma_{0}\right)+\Psi\left(\gamma_{1}\right),$
(7)

from which we obtain

$\displaystyle\hat{\gamma}_{0}=\Psi^{-1}\left(\Psi\left(\gamma_{0}\right)+\Psi\left(\gamma_{1}\right)\right)=\Psi\left(\Psi\left(\gamma_{0}\right)+\Psi\left(\gamma_{1}\right)\right).$
(8)

The above relationship between the pairs $(\gamma_{0},\gamma_{1})$ and
$(\hat{\gamma}_{0},\hat{\gamma}_{1})$ is illustrated in Fig. 1.

In what follows, we consider the case when $\gamma$ is extremely large or
small due to the polarization effect. From the viewpoint of numerical
evaluation and similar to [8], it would be convenient to express $\gamma$ in
the log domain. Therefore, we define $\xi\triangleq\ln\gamma$ and also
introduce the function

$\displaystyle\Lambda(\xi)\triangleq\ln\Psi\left(e^{\xi}\right).$ (9)

For the check node, the output $\hat{\xi}_{0}$ for a given pair of inputs
$\xi_{0}=\ln\gamma_{0}$ and $\xi_{1}=\ln\gamma_{1}$ can be expressed as

$\displaystyle\hat{\xi}_{0}$
$\displaystyle=\Lambda\left(\max\left(\Lambda\left(\xi_{0}\right),\Lambda\left(\xi_{1}\right)\right)+\ln\left(1+e^{-\left|\Lambda\left(\xi_{1}\right)-\Lambda\left(\xi_{0}\right)\right|}\right)\right).$
(10)

On the other hand, for the variable node, the output $\hat{\xi}_{1}$ is
expressed as

$\displaystyle\hat{\xi}_{1}$
$\displaystyle=\max(\xi_{0},\xi_{1})+\ln\left(1+e^{-\left|\xi_{0}-\xi_{1}\right|}\right).$
(11)

###  II-C General Algorithm

In the case of a binary polar code of length $N=2^{n}$, let
$\gamma_{0},\gamma_{1},\ldots,\gamma_{N-1}$ denote the channel SNRs of the
coded bits $x_{0},x_{1},\ldots,x_{N-1}$. Then the SNRs for the input bits
$u_{0},u_{1},\ldots,u_{N-1}$, denoted by
$\hat{\gamma}_{0},\hat{\gamma}_{1},\ldots,\hat{\gamma}_{N-1}$, can be obtained
by the well-known recursive procedure in [1]. The corresponding RCA algorithm
when each channel has a distinct SNR value is summarized in Algorithm 1. The
algorithm can be significantly simplified when all the channels have the same
SNR (or design SNR), i.e., $\gamma_{0}=\gamma_{1}=\cdots=\gamma_{N-1}$, which
is summarized in Algorithm 2.

The remaining questions are: how can one calculate the function $\Lambda(\xi)$
accurately with computational efficiency, i.e., without resorting to numerical
integration, and how well does the algorithm operate compared to other known
approaches of similar complexity? These will be addressed in the subsequent
sections.

Algorithm 1 Channel Polarization with RCA (for Distinct Channel SNRs).

0: $n=\log_{2}N$, $\xi[0],\xi[1],\ldots,\xi[N-1]$ as
$\ln\gamma_{0},\ln\gamma_{1},\ldots,\ln\gamma_{N-1}$.

0: $\xi[0],\xi[1],\ldots,\xi[N-1]$ as
$\ln\hat{\gamma}_{0},\ln\hat{\gamma}_{1},\ldots,\ln\hat{\gamma}_{N-1}$

1: for $i=1$ : $n$ do

2: $J\leftarrow 2^{i}$

3: for $k=0$ : $N/J-1$ do

4: for $j=0$ : $J/2-1$ do

5: $\xi_{0}\leftarrow\xi[kJ+j]$

6: $\xi_{1}\leftarrow\xi[kJ+j+J/2]$

7: $\Lambda_{0}\leftarrow\Lambda(\xi_{0})$

8: $\Lambda_{1}\leftarrow\Lambda(\xi_{1})$

9:
$\xi[kJ+j]\leftarrow\Lambda\left(\max(\Lambda_{0},\Lambda_{1})+\ln\left(1+e^{-\left|\Lambda_{0}-\Lambda_{1}\right|}\right)\right)$

10:
$\xi[kJ+j+J/2]\leftarrow\max(\xi_{0},\xi_{1})+\ln\left(1+e^{-\left|\xi_{0}-\xi_{1}\right|}\right)$

11: end for

12: end for

13: end for

14: return $\xi[0],\xi[1],\ldots,\xi[N-1]$

Algorithm 2 Channel Polarization with RCA (for Uniform Channel SNR).

0: $n=\log_{2}N$, $\xi[0]=\ln\gamma_{0}$

0: $\xi[0],\xi[1],\ldots,\xi[N-1]$ as
$\ln\hat{\gamma}_{0},\ln\hat{\gamma}_{1},\ldots,\ln\hat{\gamma}_{N-1}$

1: for $i=1$ : $n$ do

2: $J\leftarrow 2^{i}$

3: for $j=0$ : $J/2-1$ do

4: $\xi_{0}\leftarrow\xi[j]$

5: $\Lambda_{0}\leftarrow\Lambda(\xi_{0})$

6: $\xi[j]\leftarrow\Lambda\left(\Lambda_{0}+\ln 2\right)$

7: $\xi[j+J/2]\leftarrow\xi_{0}+\ln 2$

8: end for

9: end for

10: return $\xi[0],\xi[1],\ldots,\xi[N-1]$

##  III Capacity Expression

###  III-A Approximation for BI-AWGN Capacity

We start with the BI-AWGN capacity formula. Let $E_{s}$ denote the symbol
energy of BPSK and $N_{0}$ denote the variance of complex Gaussian noise. Let
us define the SNR parameter $\gamma$ as $\gamma\triangleq E_{s}/N_{0}$ in what
follows. To compute the mutual information $C(\gamma)$ between a BPSK input
and its corresponding output over an AWGN channel, the following equivalent
$J$-function (see [16]) is often adopted:

$\displaystyle J(x)$ $\displaystyle=1-\frac{1}{\sqrt{2\pi
x^{2}}}\int_{-\infty}^{\infty}e^{-\frac{\left(t-\frac{x^{2}}{2}\right)^{2}}{2x^{2}}}\log_{2}\left(1+e^{-t}\right)dt,$
(12)

where $x$ corresponds to the standard deviation of the LLR and thus is related
to $\gamma$ by $x=\sqrt{8\gamma}$. Then
$C(\gamma)=J\left(\sqrt{8\gamma}\right).$

According to [16], the function $J(x)$ is well approximated numerically by

$\displaystyle J(x)$
$\displaystyle\approx\begin{cases}a_{1}x^{3}+b_{1}x^{2}+c_{1}x,&0\leq x\leq
1.6363,\\\ 1-e^{a_{2}x^{3}+b_{2}x^{2}+c_{2}x+d},&1.6363<x\leq 10,\\\
1,&x>10,\end{cases}$ (13)

with

$\displaystyle a_{1}$
$\displaystyle=-0.0421061,\,\,b_{1}=0.209252,\,\,c_{1}=-0.00640081,$
$\displaystyle a_{2}$
$\displaystyle=0.00181491,\,\,b_{2}=-0.142675,\,\,c_{2}=-0.0822054,\,\,d=0.0549608.$

On the other hand, in [23], the approximation

$\displaystyle J(x)$
$\displaystyle\approx\left(1-2^{-H_{1}x^{2H_{2}}}\right)^{H_{3}},$ (14)

was proposed with $H_{1}=0.3073$, $H_{2}=0.8935$, and $H_{3}=1.1064$.

###  III-B New Approximation Formula

From (12) and $C(\gamma)=J\left(\sqrt{8\gamma}\right)$, we define

$\displaystyle U(\gamma)$ $\displaystyle\triangleq 1-C(\gamma)$
$\displaystyle=\frac{1}{4\sqrt{\pi\gamma}}\int_{-\infty}^{\infty}e^{-\frac{1}{16\gamma}\left(t-4\gamma\right)^{2}}\log_{2}\left(1+e^{-t}\right)dt.$
(15)

In what follows, we divide the range of $\gamma$, ${\cal
R}\triangleq(0,\infty)$, into the four sub-regions ${\cal R}_{1},{\cal
R}_{2},{\cal R}_{3},{\cal R}_{4}$, where ${\cal R}_{1}=(0,\Gamma_{1})$, ${\cal
R}_{2}=[\Gamma_{1},\Gamma_{2})$, ${\cal R}_{3}=[\Gamma_{2},\Gamma_{3})$, and
${\cal R}_{4}=[\Gamma_{3},\infty)$, with $\Gamma_{1},\Gamma_{2},\Gamma_{3}$
representing appropriate boundaries to be determined numerically.

####  III-B1 Low SNR Case

For the sub-region ${\cal R}_{1}$, i.e., when $\gamma\approx 0$, by Maclaurin
series expansion we obtain

$\displaystyle C(\gamma)$ $\displaystyle\approx\frac{1}{\ln
2}\left(\gamma-\gamma^{2}+\frac{4}{3}\gamma^{3}-\frac{10}{3}\gamma^{4}+\frac{208}{15}\gamma^{5}\right).$
(16)

By truncating up to the third order, we may approximate $U(\gamma)$ as

$\displaystyle U_{1}(\gamma)\triangleq 1-\frac{1}{\ln
2}\left(\gamma-\gamma^{2}+\frac{4}{3}\gamma^{3}\right),\quad\gamma<\Gamma_{1}.$
(17)

By setting the upper boundary as $\Gamma_{1}=0.04$, the value of $U(\gamma)$
at $\gamma=\Gamma_{1}$ is calculated by numerical integration as

$\displaystyle U(\Gamma_{1})\approx 0.9444880,$ (18)

whereas the corresponding approximation according to (17) is given by

$\displaystyle{\sf U}_{1}\triangleq U_{1}(\Gamma_{1})\approx 0.9444774.$ (19)

Therefore, the approximation error of $U(\gamma)$ by $U_{1}(\gamma)$ in the
region ${\cal R}_{1}$ is bounded by

$\displaystyle\left|U(\gamma)-U_{1}(\gamma)\right|<1.1\times
10^{-5},\quad\gamma<\Gamma_{1}.$ (20)

####  III-B2 High SNR Case

We next consider the sub-region ${\cal R}_{4}$, i.e., when $\gamma$ becomes
larger than some boundary $\Gamma_{3}$. By applying the series expansion of
the exponential function $e^{x}=\sum_{k=0}^{\infty}\frac{x^{k}}{k!}$ to
$U(\gamma)$ of (15), we obtain

$\displaystyle U(\gamma)$
$\displaystyle=\frac{e^{-\gamma}}{4\sqrt{\pi\gamma}}\sum_{k=0}^{\infty}\frac{(-1)^{k}}{k!\left(16\gamma\right)^{k}}c_{k}$
$\displaystyle=\frac{e^{-\gamma}}{4\sqrt{\pi\gamma}}\left\\{c_{0}-\frac{c_{1}}{16\gamma}+\frac{c_{2}}{2\cdot\left(16\gamma\right)^{2}}-\cdots\right\\},$
(21)

where

$\displaystyle
c_{k}\triangleq\int_{-\infty}^{\infty}e^{\frac{t}{2}}t^{2k}\log_{2}\left(1+e^{-t}\right)dt.$
(22)

The above expression agrees with [3, Problem 4.12]. Note that $c_{k}$ for
specific values of $k$ can be expressed in closed form, e.g.,

$\displaystyle c_{0}=\frac{2\pi}{\ln 2},\quad
c_{1}=\frac{2\pi\left(8+\pi^{2}\right)}{\ln 2},\quad
c_{2}=\frac{2\pi\left(384+48\pi^{2}+5\pi^{4}\right)}{\ln 2}.$ (23)

Although the approximation becomes tighter as we incorporate more terms in
(21), it becomes infeasible to find the corresponding inverse expression in
closed form. Therefore, we adopt the expression

$\displaystyle
U_{4}(\gamma)\triangleq\alpha\frac{e^{-\gamma}}{\sqrt{\gamma}},\quad\gamma>\Gamma_{3},$
(24)

where $\alpha$ and $\Gamma_{3}$ are appropriate constants to be determined. By
setting the boundary as $\Gamma_{3}=10$, the value at the boundary becomes

$\displaystyle{\sf U}_{3}\triangleq U(\Gamma_{3})\approx 1.667\times 10^{-5},$
(25)

from which we fix the constant $\alpha$ as

$\displaystyle\alpha\approx 1.16125142,$ (26)

such that $U(\Gamma_{3})\approx U_{4}(\Gamma_{3})$. Note that this is
different from the exact coefficient of the first term in (21), which is given
by

$\displaystyle\alpha_{0}\triangleq c_{0}/(4\sqrt{\pi})=\frac{\sqrt{\pi}}{2(\ln
2)}\approx 1.27856,$ (27)

and thus the exact asymptotic form for large $\gamma$ would be

$\displaystyle U(\gamma)\to\frac{\sqrt{\pi}}{2(\ln
2)}\frac{e^{-\gamma}}{\sqrt{\gamma}},$ (28)

as discussed in [3, 24]. As $\gamma$ increases, the use of $\alpha_{0}$ may
become more accurate eventually, but for our purpose, the use of (26) may be
more suitable as the piece-wise continuity of the approximate function can be
guaranteed.

####  III-B3 Moderate SNR Case

We first note that the main advantage of the capacity approximation form (14)
is that its inverse function can also be expressed in closed form. We thus
adopt this form for the remaining sub-regions ${\cal R}_{2}$ and ${\cal
R}_{3}$ and define the functions for the two adjacent regions as

$\displaystyle U_{2}(\gamma)$ $\displaystyle\triangleq
1-\left(1-e^{-H_{2,1}\gamma^{H_{2,2}}}\right)^{H_{2,3}},\quad\Gamma_{1}<\gamma<\Gamma_{2},$
(29) $\displaystyle U_{3}(\gamma)$ $\displaystyle\triangleq
1-\left(1-e^{-H_{3,1}\gamma^{H_{3,2}}}\right)^{H_{3,3}},\quad\Gamma_{2}<\gamma<\Gamma_{3},$
(30)

where the constants $H_{i,j}$ for $i\in\\{2,3\\}$ and $j\in\\{1,2,3\\}$ should
be determined appropriately depending on the boundary $\Gamma_{2}$. In what
follows, we fix the boundary as $\Gamma_{2}=1$ for simplicity of numerical
evaluation. Then the precise value of $U(\gamma)$ at the boundary is obtained
by numerical integration as

$\displaystyle{\sf U}_{2}\triangleq U(\Gamma_{2})\approx 0.2785484.$ (31)

Furthermore, in order to guarantee the piece-wise continuity of the
approximate function for $U(\gamma)$, it is required that

$\displaystyle U_{2}(\Gamma_{1})$ $\displaystyle={\sf U}_{1},\quad
U_{3}(\Gamma_{3})={\sf U}_{3}.$ (32)

Let us first consider the function $U_{2}(\gamma)$. By the relationships at
the boundaries, one may express

$\displaystyle H_{2,1}$ $\displaystyle=-\ln\left(1-\left(1-{\sf
U}_{2}\right)^{\frac{1}{H_{2,3}}}\right),$ (33) $\displaystyle H_{2,2}$
$\displaystyle=\left[\ln\left(\frac{\Gamma_{2}}{\Gamma_{1}}\right)\right]^{-1}\ln\left\\{\frac{\ln\left(1-\left(1-{\sf
U}_{2}\right)^{\frac{1}{H_{2,3}}}\right)}{\ln\left(1-\left(1-{\sf
U}_{1}\right)^{\frac{1}{H_{2,3}}}\right)}\right\\}.$ (34)

As a consequence, $U_{2}(\gamma)$ can be expressed as a function of $\gamma$
and $H_{2,3}$, which we explicitly write as $U_{2}(\gamma;H_{2,3})$. Based on
the minimization of $\infty$-norm, we may optimize the coefficients $H_{2,3}$
as

$\displaystyle{H}_{2,3}=\arg\min_{H}\max_{\Gamma_{1}<\gamma<\Gamma_{2}}\left|U_{2}(\gamma;{H})-U(\gamma)\right|,$
(35)

based on which we numerically obtain

$\displaystyle H_{2,1}=1.396634,\,H_{2,2}=0.872764,\,H_{2,3}=1.148562.$

Likewise, by denoting $U_{3}(\gamma)$ as a function of $H_{3,3}$, i.e.,
$U_{3}(\gamma;{H}_{3,3})$, since

$\displaystyle H_{3,1}$ $\displaystyle=-\ln\left(1-\left(1-{\sf
U}_{2}\right)^{\frac{1}{H_{3,3}}}\right),$ (36) $\displaystyle H_{3,2}$
$\displaystyle=\left[\ln\left(\frac{\Gamma_{3}}{\Gamma_{2}}\right)\right]^{-1}\ln\left\\{\frac{\ln\left(1-\left(1-{\sf
U}_{3}\right)^{\frac{1}{H_{3,3}}}\right)}{\ln\left(1-\left(1-{\sf
U}_{2}\right)^{\frac{1}{H_{3,3}}}\right)}\right\\},$ (37)

one may determine $H_{3,3}$ according to

$\displaystyle{H}_{3,3}=\arg\min_{H}\max_{\Gamma_{2}<\gamma<\Gamma_{3}}\left|U_{3}(\gamma;{H})-U(\gamma)\right|,$
(38)

and thus numerically obtain

$\displaystyle H_{3,1}=1.266967,\quad H_{3,2}=0.938175,\quad
H_{3,3}=0.986830.$

####  III-B4 Summary

We summarize the closed-form piece-wise continuous approximate function
$\hat{U}(\gamma)$ for $U(\gamma)$:

$\displaystyle\hat{U}(\gamma)$
$\displaystyle=\begin{cases}U_{1}(\gamma)=1-\frac{1}{\ln
2}\left(\gamma-\gamma^{2}+\frac{4}{3}\gamma^{3}\right),&\gamma<\Gamma_{1},\\\
U_{2}(\gamma)=1-\left(1-e^{-H_{2,1}\gamma^{H_{2,2}}}\right)^{H_{2,3}},&\Gamma_{1}\leq\gamma<\Gamma_{2},\\\
U_{3}(\gamma)=1-\left(1-e^{-H_{3,1}\gamma^{H_{3,2}}}\right)^{H_{3,3}},&\Gamma_{2}\leq\gamma<\Gamma_{3},\\\
U_{4}(\gamma)=\alpha\frac{e^{-\gamma}}{\sqrt{\gamma}},&\gamma\geq\Gamma_{3},\end{cases}$
(39)

where $\Gamma_{1}=0.04,\Gamma_{2}=1,\Gamma_{3}=10$. As a consequence, the
approximate formula of the capacity for the BI-AWGN channel,
$\hat{C}(\gamma)\triangleq 1-\hat{U}(\gamma)$, can be summarized as

$\displaystyle\hat{C}(\gamma)$ $\displaystyle=\begin{cases}\frac{1}{\ln
2}\left(\gamma-\gamma^{2}+\frac{4}{3}\gamma^{3}\right),&\gamma\in{\cal
R}_{1},\\\
\left(1-e^{-H_{2,1}\gamma^{H_{2,2}}}\right)^{H_{2,3}},&\gamma\in{\cal
R}_{2},\\\
\left(1-e^{-H_{3,1}\gamma^{H_{3,2}}}\right)^{H_{3,3}},&\gamma\in{\cal
R}_{3},\\\ 1-\alpha\frac{e^{-\gamma}}{\sqrt{\gamma}},&\gamma\in{\cal
R}_{4}.\end{cases}$ (40)

###  III-C Numerical Results

To investigate the accuracy of the developed approximation, we define the
error function as

$\displaystyle\epsilon(\gamma)\triangleq
U(\gamma)-\hat{U}(\gamma)=\hat{C}(\gamma)-C(\gamma).$ (41)

We calculate $C(\gamma)$ based on the numerical integration and compare with
the developed expression as well as (13) of [16] and (14) of [23]. In Fig. 2,
we plot the absolute value of the error function $\epsilon(\gamma)$ with
respect to $\gamma$ in dB. We observe that the absolute values of the
approximation error for all the three expressions are less than $10^{-3}$, and
monotonically decrease for higher and lower SNR regions. Nevertheless, the
most significant difference of the proposed expression is that the error
becomes much less than $10^{-5}$ as SNR decreases since we selected the
associated parameters such that the condition (20) holds. Also, since the
proposed expression $\hat{C}(\gamma)$ in (40) is designed to be piece-wise
continuous with respect to $\gamma$, we also observe that the error function
is piece-wise continuous as well. By comparison, as observed in Fig. 2, the
approximation based on (13) (introduced in [16]) exhibits discontinuities at
the boundaries corresponding to $x=1.6363$ and $x=10$, i.e., $\gamma=-4.7536$
dB and $\gamma=10.969$ dB, respectively.

Figure 2: Approximation error of the proposed expression. Those based on ten
Brink et al. [16] and Brännström et al. [23] are also shown for comparison.

##  IV Derivation of Closed-Form Expression for $\Lambda(\xi)$

Our next step is to find a suitable approximate expression for $\Lambda(\xi)$
introduced in (9). We first consider an approximation for its constituent
function $\Psi(\gamma)$. From (4), we have

$\displaystyle{\Psi}(\gamma)=C^{-1}\left(1-C(\gamma)\right)=C^{-1}\left(U(\gamma)\right).$
(42)

Therefore, it is necessary to find the inverse function for $\hat{C}(\gamma)$
defined in (40).

Let us first consider the case $\gamma\in{\cal R}_{1}$. From (40), the inverse
function for the equation $\hat{C}(\gamma)=c$ can be expressed as

$\displaystyle\hat{C}^{-1}(c)$
$\displaystyle=\frac{1}{4}\left(1-\frac{3}{A(c)}+A(c)\right),\quad c<{\sf
C}_{1},$ (43)

where ${\sf C}_{1}\triangleq 1-{\sf U}_{1}$ and

$\displaystyle A(c)$ $\displaystyle\triangleq\left(-5+24\left(\ln
2\right)c+2\sqrt{13+12\left(\ln 2\right)c(12\left(\ln
2\right)c-5)}\right)^{\frac{1}{3}}.$ (44)

On the other hand, when $\gamma\in{\cal R}_{2}$, we have

$\displaystyle\hat{C}^{-1}(c)$
$\displaystyle=\left[-\frac{1}{H_{2,1}}\ln\left(1-I^{\frac{1}{H_{2,3}}}\right)\right]^{\frac{1}{H_{2,2}}},\quad{\sf
C}_{1}<c<{\sf C}_{2},$ (45)

where ${\sf C}_{2}=1-{\sf U}_{2}$. The function $\hat{C}^{-1}(c)$ in the case
of $\gamma\in{\cal R}_{3}$ can be derived in a similar manner. Finally, in the
case of $\gamma\in{\cal R}_{4}$, we have

$\displaystyle\hat{C}^{-1}(c)$
$\displaystyle=\frac{1}{2}W_{0}\left(2\left(\frac{\alpha}{1-c}\right)^{2}\right),\quad
c>{\sf C}_{3},$ (46)

where ${\sf C}_{3}=1-{\sf U}_{3}$ and $W_{0}(x)$ is the corresponding Lambert
W function [25], i.e., the value of $w$ that satisfies $we^{w}=x$ for a given
$x>0$.

In summary, we have

$\displaystyle\hat{C}^{-1}(c)=\begin{cases}\frac{1}{4}\left(1-\frac{3}{A(c)}+A(c)\right),&c<{\sf
C}_{1}\approx 0.055523,\\\
\left[-\frac{1}{H_{2,1}}\ln\left(1-c^{\frac{1}{H_{2,3}}}\right)\right]^{\frac{1}{H_{2,2}}},&{\sf
C}_{1}\leq c<{\sf C}_{2}\approx 0.721452,\\\
\left[-\frac{1}{H_{3,1}}\ln\left(1-c^{\frac{1}{H_{3,3}}}\right)\right]^{\frac{1}{H_{3,2}}},&{\sf
C}_{2}\leq c<{\sf C}_{3}\approx 0.999983,\\\
\frac{1}{2}W_{0}\left(2\left(\frac{\alpha}{1-c}\right)^{2}\right),&c\geq{\sf
C}_{3}.\end{cases}$ (47)

By substituting $\hat{U}(\gamma)$ of (39) into $c$ of (47), we obtain the
approximate value of $\Psi(\gamma)=C^{-1}(U(\gamma))$ for a given $\gamma$,
which we denote by
$\hat{\Psi}(\gamma)\triangleq\hat{C}^{-1}(\hat{U}(\gamma))$.

In what follows, we derive simple asymptotic closed-form expressions of
$\hat{\Psi}(\gamma)$ and thus $\Lambda(\xi)$ when $\gamma$ becomes extremely
small or large in order to simplify the computation with negligible loss of
accuracy. Also, as we will see, it is not actually necessary to implement the
$W_{0}(\cdot)$ function for polar code construction.

###  IV-A For Small $\gamma$

We consider the case where $\gamma$ is small and satisfies
$\gamma\leq\Gamma_{0}$ for some boundary $\Gamma_{0}$ such that the condition
$c=\hat{U}(\gamma)\geq{\sf C}_{3}$ holds in (47). Then, it follows from (39)
that

$\displaystyle\hat{\Psi}(\gamma)=\frac{1}{2}W_{0}\left(2\left(\frac{\alpha}{\frac{1}{\ln
2}\left(\gamma-\gamma^{2}+\frac{4}{3}\gamma^{3}\right)}\right)^{2}\right),\quad\gamma<\min\left(\Gamma_{0},\Gamma_{1}\right),$
(48)

where $\Gamma_{0}$ corresponds to the value of $\gamma$ that satisfies
$\hat{U}(\gamma)={\sf C}_{3}$. By numerically solving the equation

$\displaystyle\frac{1}{\ln
2}\left(\Gamma_{0}-\Gamma_{0}^{2}+\frac{4}{3}\Gamma_{0}^{3}\right)={\sf
U}_{3},$ (49)

with respect to $\Gamma_{0}$, we obtain

$\displaystyle\Gamma_{0}\approx 1.21974\times 10^{-5},$ (50)

and thus we observe that $\Gamma_{0}\ll\Gamma_{1}$. By defining
$f(\gamma)\triangleq\gamma-\gamma^{2}+\frac{4}{3}\gamma^{3}$, we may express
(48) as

$\displaystyle\hat{\Psi}(\gamma)=\frac{1}{2}W_{0}\left(2\alpha^{2}\left(\ln
2\right)^{2}f^{-2}(\gamma)\right),\quad\gamma<\Gamma_{0}.$ (51)

Since the argument of the function $W_{0}(\cdot)$ in (51) becomes larger as
$\gamma$ decreases, we may invoke the following asymptotic form of $W_{0}(x)$
for large $x$ [25]:

$\displaystyle W_{0}(x)\approx\ln x-\ln\ln x+\frac{\ln\ln x}{\ln x}+\cdots.$
(52)

On applying (52) to (51), we note that

$\displaystyle\ln\left(2\alpha^{2}\left(\ln
2\right)^{2}f^{-2}(\gamma)\right)=\ln 2+2\ln(\ln
2)+2\ln\alpha-2\ln\gamma-2\ln\left(1-\gamma+\frac{4}{3}\gamma^{2}\right),$
(53)

where the last term in the right hand side turns out to be negligible in the
range of $\gamma<\Gamma_{0}$. Thus, by defining the dominant terms as

$\displaystyle B(\xi)\triangleq\ln 2+2\left(\ln\alpha+\ln\left(\ln
2\right)\right)-2\xi,$ (54)

where $\xi\triangleq\ln\gamma$, we may equivalently express
$\ln\hat{\Psi}(\gamma)$ with respect to $\xi$, denoted by $\Lambda(\xi)$, as

$\displaystyle\Lambda(\xi)\approx\ln\left(B(\xi)+\left(\frac{1}{B(\xi)}-1\right)\ln
B(\xi)\right)-\ln 2.$ (55)

The above approximation is valid in the range of $\gamma<\Gamma_{0}$, i.e.,

$\displaystyle\xi<\Xi_{0}\triangleq\ln\Gamma_{0}\approx-11.3143.$ (56)

###  IV-B For Large $\gamma$

When $\gamma\geq\Gamma_{3}$, i.e., $\gamma\in{\cal R}_{4}$, we observe from
(39) with (32) that $\hat{U}(\gamma)\leq{\sf U}_{3}$ and thus

$\displaystyle\hat{\Psi}(\gamma)=\frac{1}{4}\left(1-\frac{3}{A(c)}+A(c)\right),\quad
c=\alpha\frac{e^{-\gamma}}{\sqrt{\gamma}}.$ (57)

For $A(c)$ in (44) with small $c$, since

$\displaystyle\sqrt{13+12\left(\ln 2\right)c\left(12\left(\ln
2\right)c-5\right)}\approx\sqrt{13}-\frac{30}{\sqrt{13}}\left(\ln 2\right)c,$
(58)

we have

$\displaystyle A(c)$
$\displaystyle\approx\left(-5+2\sqrt{13}\right)^{\frac{1}{3}}\left(1+\frac{4}{\sqrt{13}}\left(\ln
2\right)c\right),$ (59)

and by substituting (59) into (57), we obtain

$\displaystyle\hat{\Psi}(\gamma)$ $\displaystyle\approx\left(\ln
2\right)c\left(1-2\frac{\sqrt{13}+1}{13+4\sqrt{13}\left(\ln
2\right)c}\left(\ln 2\right)c\right).$ (60)

Taking the logarithm of both sides, we have

$\displaystyle\ln\hat{\Psi}(\gamma)$ $\displaystyle\approx\ln c+\ln\left(\ln
2\right)+\ln\left(1-2\frac{\sqrt{13}+1}{13+4\sqrt{13}\left(\ln
2\right)c}\left(\ln 2\right)c\right).$ (61)

By substituting $c=\alpha\frac{e^{-\gamma}}{\sqrt{\gamma}}$ and noticing that
the third term in the right-hand side of (61) becomes negligible as $\gamma$
increases, we have

$\displaystyle\ln\hat{\Psi}(\gamma)$ $\displaystyle\approx\ln\alpha+\ln(\ln
2)-\gamma-\frac{1}{2}\ln\gamma,$ (62)

or in terms of $\xi$ as

$\displaystyle\Lambda(\xi)\approx\ln\alpha+\ln(\ln 2)-e^{\xi}-\frac{1}{2}\xi.$
(63)

Note that (62) indicates that $\hat{\Psi}(\gamma)$ becomes infinitesimal as
$\gamma$ increases.

###  IV-C Complete RCA Algorithm

In the previous section, the RCA algorithm was summarized as Algorithm 1 and
Algorithm 2, depending on the condition of the channel SNR. Based on the
mathematical derivations in this section, the calculation process of the
function $\Lambda(\xi)$ is summarized as Algorithm 3. Note that the complexity
of GA-based approaches generally involves the use of an inverse function that
cannot be described (or accurately approximated) using a closed form
expression, and thus should be performed by resorting to some iterative
algorithms (such as the bisection method). On the other hand, the proposed
approach does not require such numerical algorithms and thus computational
effort is in general lower than those based on GA (or IGA).

Algorithm 3 Calculating $\Lambda(\xi)$

0: $\xi=\ln\gamma$

0: $\Lambda(\xi)=\ln\Psi(\gamma)$

1:
$\alpha=1.16125,\,\Gamma_{1}=0.04,\,\Gamma_{2}=1,\,\Gamma_{3}=10,\,\Xi_{0}=-11.3143$

2: ${\sf C}_{1}=0.055523,\,{\sf C}_{2}=0.721452$

3: $H_{2,1}=1.396634,\,H_{2,2}=0.872764,\,H_{2,3}=1.148562$

4: $H_{3,1}=1.266967,\,H_{3,2}=0.938175,\,H_{3,3}=0.986830$

5: if $\xi<\Xi_{0}$ then

6: $B=\ln 2+2\ln(\ln 2)+2\ln\alpha-2\xi$

7: return $\ln\left(B+\left(\frac{1}{B}-1\right)\ln B\right)-\ln 2$

8: end if

9: $\gamma\leftarrow\exp(\xi)$

10: if $\gamma>\Gamma_{3}$ then

11: return $\ln\left(\ln 2\right)+\ln\alpha-\gamma-\xi/2$

12: else if $\gamma<\Gamma_{1}$ then

13: $U\leftarrow 1-\frac{1}{\ln 2}(\gamma-\gamma^{2}+\frac{4}{3}\gamma^{3})$

14: else if $\gamma<\Gamma_{2}$ then

15: $U\leftarrow 1-\left(1-e^{-H_{2,1}\gamma^{H_{2,2}}}\right)^{H_{2,3}}$

16: else

17: $U\leftarrow 1-\left(1-e^{-H_{3,1}\gamma^{H_{3,2}}}\right)^{H_{3,3}}$

18: end if

19: if $U<{\sf C}_{1}$ then

20: $A=\left(-5+24(\ln 2)U+2\sqrt{13+12(\ln 2)U(12(\ln
2)U-5)}\right)^{\frac{1}{3}}$

21: return $\ln\left(1-\frac{3}{A}+A\right)-2\ln 2$

22: else if $U<{\sf C}_{2}$ then

23: return
${\frac{1}{H_{2,2}}}\left[\ln\left(-\ln\left(1-U^{\frac{1}{H_{2,3}}}\right)\right)-\ln
H_{2,1}\right]$

24: else

25: return
${\frac{1}{H_{3,2}}}\left[\ln\left(-\ln\left(1-U^{\frac{1}{H_{3,3}}}\right)\right)-\ln
H_{3,1}\right]$

26: end if

##  V Simulation Results

In this section, we focus on the AWGN channels with BPSK, where the SNRs of
all the channels are identical and given by $\gamma_{0}=E_{s}/N_{0}$. We
estimate the SNRs of the polarized channels
$\hat{\gamma}_{0},\hat{\gamma}_{1},\ldots,\hat{\gamma}_{N-1}$ by applying
Algorithm 2 in Section II. Let us sort $\hat{\gamma}_{k}$ such that

$\displaystyle\hat{\gamma}_{I_{0}(\gamma_{0})}\geq\hat{\gamma}_{I_{1}(\gamma_{0})}\geq\cdots\geq\hat{\gamma}_{I_{N-1}(\gamma_{0})},$
(64)

where the subscript $I_{k}(\gamma_{0})$ corresponds to the index of the input
bit having the $k$th highest SNR (with $k=0$ representing the maximum), with
emphasis on the fact that the channel SNR is $\gamma_{0}$. Let us define the
index set ${\cal I}_{K}(\gamma_{0})$ consisting of the $K$ elements with
highest SNRs as

$\displaystyle{\cal
I}_{K}(\gamma_{0})\triangleq\\{I_{0}(\gamma_{0}),I_{1}(\gamma_{0}),\ldots,I_{K-1}(\gamma_{0})\\},$
(65)

where $R\triangleq K/N$ corresponds to the code rate.

Similar to the case of GA, we assume that the distribution of the LLR
corresponding to the $k$th input bit is modeled as Gaussian with SNR
$\hat{\gamma}_{k}$. Then, under the assumption that all the previous bits in
the SC decoding are correctly decoded, the error rate of the $k$th bit can be
estimated as

$\displaystyle P_{b,k}=Q\left(\sqrt{\frac{\hat{\gamma}_{k}}{2}}\right),$ (66)

with the $Q$-function defined as
$Q(x)=\frac{1}{2}{\rm{erfc}}\left(\frac{x}{\sqrt{2}}\right)=\frac{1}{\sqrt{2\pi}}\int_{x}^{\infty}e^{-\frac{t^{2}}{2}}dt$.
The resulting minimum estimated BLER can be defined as [8]

$\displaystyle P_{\rm BL}(K,\gamma_{0})$ $\displaystyle\triangleq
1-\prod_{k\in{\cal
I}_{K}(\gamma_{0})}\left(1-Q\left(\sqrt{\frac{\hat{\gamma}_{k}}{2}}\right)\right).$
(67)

Note that the above expression is a function of ${\cal I}_{K}(\gamma_{0})$
only, i.e., the $K$ largest estimated SNRs uniquely determines the BLER.
Therefore, if the code rate $R$ is low (i.e., the number of $K$ is small) and
estimation accuracy is good for low SNR region, the estimated BLER of (67)
should become tight compared to the true BLER, which may be estimated by time-
consuming simulations with a sufficiently large number of trials.

###  V-A Comparison for Short Polar Codes

We first compare the minimum estimated BLER based on (67) calculated for the
conventional GA, IGA of [8], and the proposed RCA as well as the corresponding
simulation results in the cases of $N=64$ and $1024$ with three different code
rates ($R=0.25,0.5,0.75$). The results are listed in Table I. Note that the
channel SNR (or design SNR) $\gamma_{0}$ is selected such that the resulting
BLER reaches around $10^{-2}$, and the same value of $\gamma_{0}$ is applied
for all three cases. Also, if the same polar code as IGA is constructed by any
of the other schemes, this is indicated in the table. In such a case, the
resulting code is the same and thus the simulation result for the BLER should
be identical to that reported in the IGA column.

Analogous to the observation in [13, Chap. 7.4.1], the performances are
similar for all the cases evaluated here. Note that the polar codes
constructed by the three different schemes are identical in the case of
$N=64$. With a length of $N=1024$ and for the cases of $R=0.25$ and $0.5$, the
codes constructed by RCA and IGA differ by only one bit position, and the
corresponding simulation results indicate that the code designed by RCA very
slightly outperforms that of IGA, whereas all the codes designed by the
conventional GA are the same as those by IGA even in this case.

TABLE I: Comparison of estimated BLER and simulation. $N$ | $R$ | $\gamma_{0}$ [dB] | BLER (RCA) | BLER (IGA) | BLER (GA)
---|---|---|---|---|---
Estimate | Simulation | Estimate | Simulation | Estimate | Simulation
$64$ | $0.25$ | $-2.53$ | $0.0100$ | = IGA | $0.0100$ | $0.0095$ | $0.0101$ | = IGA
$0.5$ | $0.65$ | $0.0100$ | = IGA | $0.0100$ | $0.0096$ | $0.0102$ | = IGA
$0.75$ | $3.26$ | $0.0101$ | = IGA | $0.0100$ | $0.0099$ | $0.0103$ | = IGA
$1024$ | $0.25$ | $-3.97$ | $0.0103$ | $0.0100$ | $0.0111$ | $0.0102$ | $0.0113$ | = IGA
$0.5$ | $-0.50$ | $0.0102$ | $0.0103$ | $0.0106$ | $0.0104$ | $0.0109$ | = IGA
$0.75$ | $2.33$ | $0.0104$ | = IGA | $0.0102$ | $0.0111$ | $0.0109$ | = IGA

The BLER performances of these three approaches with $N=2048$ bits are
compared in Fig. 3 for code rates of $R=0.25$ and $R=0.5$. Note that for all
the simulation results, the polar code is constructed for each given channel
SNR. We observe that in the case of low code rate ($R=0.25$) and low SNR
region ($E_{s}/N_{0}<-5.5\,{\rm dB}$), the performance degradation of GA
compared to IGA and RCA is noticeable, as the approximation error of the
conventional GA becomes significant with decreasing SNR as discussed in [8].
On the whole, however, the performance difference is almost negligible similar
to those reported in Table I, justifying the effectiveness of the conventional
GA as well as IGA for the polar codes with modest codeword lengths.
Nevertheless, it is worth mentioning that the simulation results match best
with the minimum estimated BLER calculated by the proposed RCA algorithm.

(a)

(b)

Figure 3: Simulated BLER of the polar codes with $N=2^{11}$ designed at each
channel SNR as well as the minimum estimated BLER: (a) $R=0.25$, (b) $R=0.5$.

###  V-B Comparison for Long Polar Codes

We now focus on the polar code performance with long block lengths ($N=2^{16}$
and $2^{18}$). Note that the performance of the conventional GA is not shown
in the remaining figures as it becomes significantly worse than that of IGA as
demonstrated in [8]. The cases with lower code rates ($R=1/8$ and $R=1/4$) are
compared in Fig. 4, whereas those with higher code rates ($R=1/2$ and $R=3/4$)
are shown in Fig. 5. We observe that for all the cases compared, the polar
codes designed based on the proposed RCA algorithms outperform those based on
IGA, and the gap is especially noticeable when the code rate is low. We also
notice that, similar to the results in Fig. 3, the minimum estimated BLER
values computed from (67) and those obtained by simulation are in general
closer when RCA is employed, indicating that the estimation accuracy of the
equivalent SNR obtained by RCA is higher than that of IGA. Therefore,
considering the fact that the computational complexity required for performing
GA, IGA, and RCA is almost the same, the proposed RCA may be preferable to GA-
based approaches, especially when polar codes with long block lengths and
moderate code rates should be designed under severe limitation of
computational resources.

(a)

(b)

Figure 4: Simulated BLER of the long polar codes with $N=2^{n}$ ($n=16$ and
$18$) designed at each channel SNR as well as the minimum estimated BLER: (a)
$R=0.125$, (b) $R=0.25$.

(a)

(b)

Figure 5: Simulated BLER of the long polar codes with $N=2^{n}$ ($n=16$ and
$18$) designed at each channel SNR as well as the minimum estimated BLER: (a)
$R=0.5$, (b) $R=0.75$.

##  VI Conclusions

In this work, we have proposed an explicit closed-form algorithm for polar
code design based on RCA. Simulation results have shown that polar code
designed based on the proposed RCA can outperform popular Gaussian
approximation (GA)-based approaches with no increase of computational
complexity. Moreover, the estimated BLER performances from RCA are closer to
those obtained by simulation compared to those based on GA, indicating the
accuracy of RCA compared to GA. The benefit of the proposed approach becomes
significant for polar codes with large block lengths and moderate code rates.

## References

  * [1] E. Arıkan, “Channel polarization: A method for constructing capacity-achieving codes for symmetric binary-input memoryless channels,” IEEE Trans. Inform. Theory, vol. 55, pp. 3051–3073, 2009.
  * [2] T. J. Richardson, M. A. Shokrollahi, and R. L. Urbanke, “Design of capacity-approaching irregular low-density parity-check codes,” IEEE Trans. Inform. Theory, vol. 47, pp. 619–637, Feb. 2001.
  * [3] T. J. Richardson and R. L. Urbanke, Modern Coding Theory.  Cambridge; New York: Cambridge University Press, 2008.
  * [4] R. Mori and T. Tanaka, “Performance of polar codes with the construction using density evolution,” IEEE Commun. Lett., vol. 13, pp. 519–521, July 2009\.
  * [5] I. Tal and A. Vardy, “How to construct polar codes,” IEEE Trans. Inform. Theory, vol. 59, pp. 6562–6582, Oct. 2013.
  * [6] S.-Y. Chung, T. Richardson, and R. Urbanke, “Analysis of sum-product decoding of low-density parity-check codes using a Gaussian approximation,” IEEE Trans. Inform. Theory, vol. 47, pp. 657–670, Feb. 2001.
  * [7] P. Trifonov, “Efficient design and decoding of polar codes,” IEEE Trans. Commun., vol. 60, pp. 3221–3227, Nov. 2012.
  * [8] H. Ochiai, P. Mitran, and H. V. Poor, “Capacity-approaching polar codes with long codewords and successive cancellation decoding based on improved Gaussian approximation,” IEEE Trans. Commun., vol. 69, pp. 31–43, Jan. 2021.
  * [9] I. Tal and A. Vardy, “List decoding of polar codes,” IEEE Trans. Inform. Theory, vol. 61, pp. 2213–2226, May 2015.
  * [10] E. Arıkan, “A performance comparison of polar codes and Reed-Muller codes,” IEEE Commun. Lett., vol. 12, pp. 447–449, June 2008.
  * [11] A. Elkelesh, M. Ebada, S. Cammerer, and S. ten Brink, “Decoder-tailored polar code design using the genetic algorithm,” IEEE Trans. Commun., vol. 67, pp. 4521–4534, July 2019.
  * [12] Y. Liao, S. A. Hashemi, J. M. Cioffi, and A. Goldsmith, “Construction of polar codes with reinforcement learning,” IEEE Trans. Commun., vol. 70, pp. 185–198, Jan. 2022.
  * [13] S.-Y. Chung, On the Construction of Some Capacity-Approaching Coding Schemes.  PhD thesis, MIT, 2000.
  * [14] A. Ashikhmin, G. Kramer, and S. ten Brink, “Extrinsic information transfer functions: Model and erasure channel properties,” IEEE Trans. Inform. Theory, vol. 50, pp. 2657–2673, Nov. 2004.
  * [15] S. ten Brink and G. Kramer, “Design of repeat-accumulate codes for iterative detection and decoding,” IEEE Trans. Signal Process., vol. 51, pp. 2764–2772, Nov. 2003.
  * [16] S. ten Brink, G. Kramer, and A. Ashikhmin, “Design of low-density parity-check codes for modulation and detection,” IEEE Trans. Commun., vol. 52, pp. 670–678, Apr. 2004.
  * [17] E. Sharon, A. Ashikhmin, and S. Litsyn, “EXIT functions for binary input memoryless symmetric channels,” IEEE Trans. Commun., vol. 54, pp. 1207–1214, July 2006.
  * [18] D. Divsalar, S. Dolinar, C. R. Jones, and K. Andrews, “Capacity-approaching protograph codes,” IEEE J. Select. Areas Commun., vol. 27, pp. 876–888, Aug. 2009.
  * [19] B. P. Smith, A. Farhood, A. Hunt, F. R. Kschischang, and J. Lodge, “Staircase codes: FEC for 100 Gb/s OTN,” J. Lightw. Technol., vol. 30, pp. 110–117, Jan. 2012.
  * [20] H. Mahdavifar and A. Vardy, “Achieving the secrecy capacity of wiretap channels using polar codes,” IEEE Trans. Inform. Theory, vol. 57, pp. 6428–6443, Oct. 2011.
  * [21] K. Vakilinia, D. Divsalar, and R. D. Wesel, “RCA analysis of the polar codes and the use of feedback to aid polarization at short blocklengths,” in Proc. 2015 IEEE Int. Symp. Inform. Theory (ISIT), pp. 1292–1296, June 2015.
  * [22] D. Dosio, Polar Codes For Error Correction: Analysis and Decoding Algorithms.  Laurea magistrale (master thesis), UniversitÃ di Bologna, 2016\.
  * [23] F. Brännström, L. Rasmussen, and A. Grant, “Convergence analysis and optimal scheduling for multiple concatenated codes,” IEEE Trans. Inform. Theory, vol. 51, pp. 3354–3364, Sept. 2005.
  * [24] A. Lozano, A. Tulino, and S. Verdu, “Optimum power allocation for parallel Gaussian channels with arbitrary input distributions,” IEEE Trans. Inform. Theory, vol. 52, pp. 3033–3051, July 2006.
  * [25] R. M. Corless, G. H. Gonnet, D. E. G. Hare, D. J. Jeffrey, and D. E. Knuth, “On the Lambert W function,” Adv. Comput. Math., vol. 5, pp. 329–359, Dec. 1996.