# Introduction

Polar codes were introduced by Erdal Arıkan in 2009 and they provide the first deterministic construction of capacity-achieving codes for binary memoryless symmetric (BMS) channels.

Notice that there is only one channel to transmission data, in order to facilitate the understanding, we logically separate one channel to two channel.

In particular, consider a setup where $(U_1, U_2)$ are two equiprobable bits that are encoded into $(X_1, X_2) = (U_1 ⊕ U_2, U_2)$. Then, $(X_1, X_2)$ are mapped to $(Y_1, Y_2)$ by two independent BMS channels with transition probabilities $P(Y_1 = y | X_1 = x) = P(Y_2 = y | X_2 = x) = W(y|x)$. Since the mapping from $(U_1, U_2)$ to $(X_1, X_2)$ is invertible, one finds that

$$I(U_1,U_2;Y_1,Y_2) = I(X_1,X_2;Y_1,Y_2) = I(X_1; Y_1) + I(X_2;Y_2) = 2I(W)$$

where $C = I(X_1; Y_1) = I(W)$ is the capacity of symmetric BMS channel because $X_1$ is equiprobable and

$$I(W) \triangleq \displaystyle\sum_y W(y|0)log_{2}[{W(y|0)/({\frac{1}{2}}W(y|0) + \frac{1}{2}W(y|1))}] = I(X_1;Y_1)$$

Thus, the transformation $(X_1, X_2) = (U_1 ⊕ U_2, U_2)$ preserves the sum capacity of the system.

Also, the chain rule decomposition

$$I(U_1, U_2; Y_1, Y_2) = I(U_1; Y_1, Y_2) + I(U_2; Y_1, Y_2|U_1) = 2I(W)$$

implies that one can also achieve the rate $2I(W)$ using two steps. First, information is transmitted through the first virtual channel $W^- : U_1 → (Y_1, Y_2)$. By coding over multiple channel uses, one can achieve any rate up to $I(U_1; Y_1, Y_2)$. If all the $U_1$’s are known from the first stage, then one can decode the information transmitted through the second virtual channel $W^+ : U_2 → (Y_1, Y_2, U_1)$. Again, coding allows one to achieve any rate up to $I(U_2; Y_1, Y_2|U_1)$.

If one chooses convolutional codes with sequential decoding, however, the expected decoding-complexity per bit becomes unbounded for rates above the computational cutoff rate

$$R_0(W) = 1 - log_{2}{(1 + Z(W))}$$

where

$$Z(W) \triangleq \displaystyle\sum_y \sqrt{W(y|0)W(y|1) }$$

is the Bhattacharyya parameter of the channel . Arıkan’s key observation was that, while the sum capacity of the two virtual channels is preserved, the sum cutoff rate satisfies

$$R_0(W^+) + R_0(W^-) ≥ 2R_0(W)$$

with equality $R_0(W) ∈ {0, 1}$. Thus, repeated transformations of this type cause the implied virtual channels to polarize into extremal channels whose capacities approach 0 or 1. But, for these extremal channels, coding is trivial and one either sends an information bit or a dummy bit. From a theoretical point of view, polar codes are beautifully simple. Practically, they approach capacity rather slowly as their blocklength increases. Still, based on recent advances, they have been chosen as the short-block codes for the 5G standard.

# Information Theory Primer

# Discrete Random variables

A discrete random variable $X$ is completely defined by the set of values it can take, $\mathcal{X} $ , which we assume to be a finite set, and its probability distribution $\left \{p(x) \right \}_{x \in \mathcal{X} }$ .

Definition. The value $p(x)$ is the probability that the random variable $X$ takes the value $x$. The probability distribution p : $\mathcal{X} → [0, 1]$ must satisfy the normalization condition:

$$\displaystyle\sum_{x \in \chi} p(x) = 1$$

We shall denote by $\mathbb{P}(A)$ the probability of an event $A \subseteq \mathcal{X} $, so that $p(x) = \mathbb{P}(X=x)$

# Self-information

Claude Shannon's definition of self-information was chosen to meet several axioms:

1. An event with probability 100% is perfectly unsurprising and yields no information.
2. The less probable an event is, the more surprising it is and the more information it yields.
3. If two independent events are measured separately, the total amount of information is the sum of the self-informations of the individual events.

The units of information in follow formula is 'bit':

$$I(x) = \log_{2}({1 \over p(x)}) = -\log_{2}({p(x)})$$

The concept of self-information is associated with variable values based on the observation of an information source. Consequently, multiple different values will be used to describe the same source.In order to avoid this situation, we introduce the concept of entropy.

# Entropy

Definition . The entropy (unit: bit/sig) of a discrete random variable $X$ with probability distribution $p(x)$ is denoted

$$H(X) \triangleq \displaystyle\sum_{x \in \chi} p(x) \log_{2}{1\over p(x)} = \mathbb{E} [\log_{2}{1\over p(x)}]$$

The unit of entropy is determined by the base of the logarithm with base-2 resulting in “bits” and the natural log (i.e., base-e) resulting in “nats”.

The understanding of entropy：

1. Refers to the mathematical expectation of the self-information of various messages output by the information source, which is the average self-information of the source.
2. Describe the average uncertainty of the information source $X$
3. Describe the average amount of information carried by each source symbol

# joint entropy

Definition . The joint entropy (in bits) of a pair of $(X, Y) \backsim p_{X, Y}(x, y)$ is denoted

$$H(X, Y) \triangleq \displaystyle\sum_{(x, y) \in \mathcal{X\times Y} } p_{XY}(x, y) \log_{2}{1\over p_{XY}(x, y)} = \mathbb{E} [\log_{2}{1\over p_{XY}(x, y)}]$$

Notice that this is identical to $H (Z)$ with $Z = (X, Y)$.

# conditional entropy

For a pair of $(X, Y ) \backsim p_{X,Y} (x, y)$, the conditional entropy (in bits) of $Y$ given $X$ is denoted

$$H(Y|X) \triangleq p_{X,Y}(x,y)log_{2}{1 \over p_{Y|X}(y|x)} = \mathbb{E}[log_{2}{1 \over p_{Y|X}(y|x)}]$$

conditional entropy $H(Y|X)$ means the uncertainty of the $Y$ when the $X$ is known.

# mutual information

Definition . For a pair of $(X, Y ) \backsim p_{X,Y} (x, y)$, the mutual information (in bits) between $X$ and $Y$ is denoted

$$I(X;Y) \triangleq \displaystyle\sum_{(x,y) \in \mathcal{X\times Y}}p_{X,Y}(x,y)log_{2}{p_{X,Y}(x,y) \over P_X(x)p_Y(y)} = \mathbb{E}[log_{2}{p_{X,Y}(x,y) \over P_X(x)p_Y(y)}]$$

# Lemma

Lemma . Basic properties of joint entropy and mutual information:

1. (chain rule of entropy) $H (X, Y) = H (X) + H (Y|X)$. If $X$ and $Y$ are independent, $H(X, Y) = H(X) + H(Y)$.
2. The mutual information satisfies $I(X; Y) = I(Y ; X)$ and

$$I(X;Y) = H(X) + H(Y) - H(X,Y) = H(X) -H(X|Y) = H(Y) - H(Y|X)$$

# References

• https://zh.wikipedia.org/wiki/ 極化碼
• http://pfister.ee.duke.edu/courses/ecen655/polar.pdf