Codes That Achieve Capacity on Symmetric Channels

Transmission of information reliably and efficiently across channels is one of the fundamental goals of coding and information theory. In this respect, efficiently decodable deterministic coding schemes which achieve capacity provably have been elusive until as recent as 2008, even though schemes which come close to it in practice existed. This survey tries to give the interested reader an overview of the area. Erdal Arikan came up with his landmark polar coding shemes which achieve capacity on symmetric channels subject to the constraint that the input codewords are equiprobable. His idea is to convert any B-DMC into efficiently encodable-decodable channels which have rates 0 and 1, while conserving capacity in this transformation. An exponentially decreasing probability of error which independent of code rate is achieved for all rates lesser than the symmetric capacity. These codes perform well in practice since encoding and decoding complexity is O(N log N). Guruswami et al. improved the above results by showing that error probability can be made to decrease doubly exponentially in the block length. We also study recent results by Urbanke et al. which show that 2-transitive codes also achieve capacity on erasure channels under MAP decoding. Urbanke and his group use complexity theoretic results in boolean function analysis to prove that EXIT functions, which capture the error probability, have a sharp threshold at 1-R, thus proving that capacity is achieved. One of the oldest and most widely used codes - Reed Muller codes are 2-transitive. Polar codes are 2-transitive too and we thus have a different proof of the fact that they achieve capacity, though the rate of polarization would be better as found out by Guruswami.


Introduction
Communication is a fundamental need of our lives. In modern times even though the need for communication and the (ever-the-more sophisticated) tools available with us have increased, communication is something which we humans have been doing for a long time. Inherently, we have error correcting capabilities built into us, which help us understand our fellow humans even when there is corruption due to say, speech defects, physical mediums, etc. We want our communication systems to do the same for us, but unfortunately there are fundamental questions which we have not been able to answer, and things don't look that easy.
We, as people studying computer science like to abstract things out and work with appropriate models. In this pursuit, Alice and Bob come to our rescue, as always.
Suppose Alice and Bob want to communicate with each efficiently other over a 'noisy' physical transmission medium which corrupts the information. We abstract out the possible scheme of corruptions into something which we shall call a ′ channel ′ .

Definition 1. Communication Channel
We define a discrete channel to be a system consisting of the following : • An input alphabet χ • An output alphabet Υ • A conditional probability transition matrix P (y|x) The conditional probability distribution expresses the probability of observing the output symbol y given that we send the symbol x. The channel is said to be memoryless if the probability distribution of the output depends only on the input at that particular time and is independent of the previous channel inputs or outputs. We would be talking about binary memoryless channels in the rest of this article.
Let's quickly define the information theoretic functions that we would be using in the course of this article.

Definition 2. Entropy of a random variable
The entropy H(X) of a discrete random variable X is defined by

Definition 3. Mutual information between two random variables
The mutual information I(X;Y) between two random variables X and Y is defined to be I(X; Y ) = x∈χ y∈Υ p(x, y) log p(x,y) p(x)p(y) Definition 4. (Shannon)Capacity of Channel The "information" channel capacity of a discrete memoryless channel is defined as Observe that the capacity of a channel is completely characterized once we specify the input output conditional probability distribution.
Let us look at a few frequently occuring discrete channels.
Observe that in all channels except the noiseless channel we cannot decode correctly unless we use encoding and decoding schemes. Intuitively it is clear that if we add some amount of redundancy in the code, it would be easier for us to correct errors. But this leads to transmission of more bits than the message actually contains. The fundamental question in Information and Coding Theory is the tradeoff between redundancy and the number of errors that can be corrected.
We shall formalize the notion of redundancy in a code.
Definition 9. Rate of Code The rate of a code is defined to be equal to dimension block length Claude Shannon gave an operational definition of the channel capacity, which implies that it is the maximum rate at which we can transmit information across a channel reliably, with error going to zero in the limit of the block length going to infinity.
Theorem 1. Shannon's coding theorem Given a noisy channel with channel capacity C and information transmission rate R, then if R ¡ C there exist codes that allow the probability of error at the receiver to be made arbitrarily small, and the converse is also true.
Shannon's used a random coding approach in his landmark paper. But this random coding approach is not something which satisfies theoretical computer science people like us and we want to lay our hands on a particular coding scheme which does the above for us reliably. We also want to be able to decode it efficiently.
In other words, we want an efficiently decodable capacity achieving deterministic coding scheme.
We would like to analyze how bad our coding scheme is, by looking at the error probability when a trivial decoding scheme is used -ML / MAP decoding, which looks at the codeword closest to the one received and outputs it. In doing so we would require a parameter defined as follows :

Channel Polarization
It can be observed that it very easy to code two types of channels -the perfect and the useless channel. The main idea behind Arikan's technique is that it manufactures out of N independent copies of a given BDM 1 W, a second set of channels which is polarized i.e. consisting of only perfect and useless (a channel in which the output is independent of the input) channels and this transformation also conserves capacity. This operation goes through two parts : combining and splitting.
Let's look at these operations in detail.

• Channel combining
We take N =2 n channels, each denoted by W, and manufacture a vector channel W N : χ N −→ Υ N recursively.
In general, 2 copies of WN 2 are combined to produce W N so that the the input u N 1 to W N is first transformed to s N 1 where For the 0-th level of recursion (n=0) we set W 1 W The first level of recursion combines to copies of W and obtains the channel W 2 where W 2 (y 1 , y 2 |u 1 , u 2 ) = W (y 1 |u 1 ⊕ u 2 )W (y 2 |u 2 ) as and so on. At each level of recursion, it should be observed that the mapping from 2). Inductively, it can be proved that the mapping from u N 1 −→ x N 1 which takes the input from W N to W N channel is also linear and can be denoted by x N 1 = u N 1 G N . We can thus relate the transition probabilities of the 2 channels W N and W N by the following equation : for appropriately defined alphabets on either side.
We shall talk about the implementations of this transformation and the encoding complexity later in this article.

• Channel splitting
As mentioned earlier, we need to split W N back into a set of N channels. We call them virtual channels and denote them individually as W (i) N : χ −→ Υ N χ i−1 , 1 ≤ i ≤ N and define them as : This definition goes hand in hand with the successive cancellation decoder used in polar coding as we describe below. Let's say that we are trying to decode the i-th bit and we are given the correctly decoded estimates for the first i-1 bits. We use this vector of the i-1 estimates and the vector of observations y N 1 to get the i-th bit. We assume that the inputs u N 1 are uniformly distributed. Note that even if we tranform this vector into different vectors during the encoding process, the fact that the bits are uniform still holds because the transformations are permutations and are linear too. This uniformity dictates a factor of 1 2 N−1 in the term.
Let us observe a few properties of the virtual channels we get after the above transformation. To make things easy, we shall see what happens when the channel is a BEC(ǫ) with uniform input. Since we are talking about uniform input, the capacity is I(W ).
Observe that at every level of recursion, we get one channel which has capacity 2 better than the original one and one which has capacity worse than the original one.
In order to analyse what happens for the general channel, we would like to see what happens locally to the above quantities. For doing this we would like to have the transtition probabilites of each of the virtual channels to be related to the original individual channels directly, instead of being related block by block.
We want to map the independent copies of channel W to the channels we get after In more general terms, in the following proposition we map (W

Proposition 2. Recursive channel transformations
For any n ≥ 0, N = 2 n , 1 ≤ i ≤ N, We are ready to talk about how the capacity and the reliability 3 change through a local transformation as above.
2 the capacity of these channels is I(W) because the channel has uniform inputs 3 The Bhattacharya parameter As we have seen in the erasure channel, we get one channel which is good and another which is bad 4 . the following proposition formalizes this notation Proposition 3. Local transformation of rate and reliability is the local transformation, then the following statements are true From the above proposition, we can see that , which goes with our intuition that we have one good and one bad channel. Also Z(W ′ ) + Z(W ′′ ) ≤ 2Z(W ), which means that the reliability parameter can only improve with our transformation. Note that equality for the above is when we have perfect or useless channels.
We apply these results to the recursive formulations in the previous proposition.
We sketch the recursive transformations as a binary tree, in which every node gives birth to a good and a bad channel. The root is the original channel W and the channel W (i) 2 n is located at the n-th level and i-th node from top. We can label the nodes in this tree in a natural way -one in which each node is labelled with the path taken from the root ( 1 means up and 0 means down). If we do this operation many number of times, we expect that most of the obtained channels have capacities near zero or one. In other words, the channel becomes significantly polarized after a few iterations. The following theorem formalizes our intuition.

Proof :
The sequence of random variables I n defined as the capacity of the channel obtained by starting at the node and taking the path n, is a martingale, because it is memoryless and E[I n+1 |path n] = 1 2 I(W pathn,0 ) + 1 2 I(W pathn,1 ) = I n . Also, the sequence of random variables Z n is a supermartingale because it is memoryless and Both the martingales are uniformly integrable and hence converge, by the martingale convergence theorem.
We can thus see that polar codes indeed achieve capacity in the limit of the blocklength going to infinity.

Rate of Polarization
Until now we have said that ploar codes with sufficiently high blocklengths acheives capacity. We would to know how fast this happens and the error probability for a particular block length. This section tries to address the above questions. This question was answered by Arikan in his paper and is outlined in the following theorem. Guruswami improved upon the result in his paper and the result shall be mentioned later.
The above theorem essentially says that there exists a subset of the set of virtual channels which are 'good' and capacity does not decrease. This process also involves that the reliability factor goes down exponentially in the blocklength.

Polar Coding
We have seen in the earlier sections that the synthetic channels are sufficiently polarized. We need a way to access the 'good' channels -channels W because it is a linear transformation. We have three parameters here -A, u A and u A c and hence we talk about (N, K, A, u A c ) codes. A is interpreted as the 'information set', the set of indices which coincide with 'good' channels and A c as the set of 'bad' channels. u A c are the 'f rozen bits' and we leave u A to be free variables. We need to give a rule for selecting the information set A. As we shall see later, the way we choose the frozen bits does not have any effect on how well the coding scheme performs over symmetric channels.
We shall briefly talk about the decoder for polar codes, because that will give us insights on how we could possibly choose the information set and the frozen bits.

The Successive Cancellation Decoder
We shall be considering a (N,K,A,u A c ) G N -coset code in which u N 1 has been encoded into a codeword x N 1 and sent over the channel W N . The decoder's task is to generate an estimateû N 1 of u N 1 , given the knowledge of A, u A c and the channel output y N 1 . An obvious way to decode the A c bits is to setû A c = u A c . We need a way to decode u A c . We do this by exploiting the structure of polar codes, a way which uses the bits we have already decoded and which treats the bits which are not decoded until now, as noise. We call this a successive cancellation decoder. Let's formalize this : Our SC decoder outputs decisionsû i in order from i=1 to n such that,

1, otherwise
These functions are similar to the ML decoding functions, but differ in that they assume the bits which we have not seen yet as noise, in other words as RVs. We need to analyse the probability of error in this SCD framework. The error probabilities are denoted in a natural way.
Definition 11. The probability of block error for a (N,K,A,u A c ) assuming that each vector u A is sent uniformly is We also denote the average of the above error probability over all choices of u A c by P e (N, K, A). We claim that the reliability still stays an upper bound on this error probability.  The proof easily follows from theorem 4 and the relation between block and bit error for SC decoder.
Note that the above can be viewed as an existential result, in the sense that there exists a way of setting the frozen bits so that the error probability goes down exponentially. We have stronger results when the channel is symmetric. Let's observe a few properties of symmetric channels.
Proposition 5. If a BDMC W is symmetric, then W N , W N and W (i) N are also symmetric.
The symmetries of the channel dictate proposition 4 is true for any way of setting the frozen bits.  The idea used in the proof is that the events -making an error in the block and choosing the vector of frozen bits are independent events and thus we can freeze the bits ( to say 0 N 1 ) without affecting the probability of error.

Encoding and Decoding Complexity
Polar codes are quite remarkable in the sense that both coding and decoding are polynomial in the block length; to be more precise, both take O(N log N) time steps on a sequential machine. It would be good to note that the structure of the encoding matrix can help us do it faster than the above on a parallel machine( O(log N) time).
As for the encoding compexity, G N , which is an involutory permutation matrix can be written in terms of tensor products and we can also exploit its relation to Fast Fourier Transforms. The O(N log N) time obtained is due to the bit-indexing methods frequently used in FFTs.
It can be easily observed that the decoding complexity is O(N log N) because we check the ML like function recursively using log N many levels, each taking O(N) time.
We can thus see that polar coding is not just capacity achieving, but also something which is quite implementable in practice owing to the low encoding and decoding complexities.

Reed Muller Codes
Reed-Muller codes are one of the oldest families of error correcting codes and use concepts from algebra for the encoding and decoding process. The idea is to look at the message as the coefficients of a polynomial in a suitable degree and pass the suitable Definition 12. Reed Solomon Codes We view a message of k symbols as the coefficients of a univariate polynomial f(X) of degree k-1. We encode the message as the evaluations of this polynomial at n different points in the underlying field (or in a subset S which the code designer is left to choose).
We should talk about how we are getting these evaluations across. We define a special matrix to make representation easier to work with.
Definition 13. The Vandermonde matrix RS codes are good in the sense that their distance is huge, but on the downside they require that the underlying field should be sufficiently large -at least of order n. To address this difficulty, we talk about Reed Muller codes. They are generalizations of Reed Solomon codes in the sense that we would be using multivariate polynomials instead.
Definition 14. Reed Muller Codes Given a field size q and a number m of variables, and a total degree bound r, the RM q,m,r code is the linear code over F q defined by the encoding map

Find polynomials E(x) and N(x) such that :
• E is not identically zero • E(x) has degree at most e and N(x) has degree at most e+k-1 We write the constraints for the polynomials E(x) and N(x) and then find them using the above algorithm. It can be proved that any solution for the constraints satisfies the conditions and gives us the correct generator polynomial. If unique decoding is not possible, then we can do list decoding till a particular fraction of errors after which the list size becomes exponential in size. This is done using the even more magical Guruswami-Sudan algorithm, which uses the same idea of fitting the bad points in a curve and then finding them out.
Proposition 8. Reed Solomon codes are 2-transitive Proof : As we have seen before, RS codes are generated by the Vandermonde matrix G. The input m N 1 is transformed to the codeword y N 1 using the matrix G, which is eventually sent over the channel.  Same holds for the vector y N 1 , because the π matrix does not care about the actual values of the vector it is multiplied with (for it is a permutation matrix). It only permutes the indices to get another vector and will do the same for m N 1 . i.e. π N ×N * y 1 y 2 y 3 . . . . . . y n 1×N = y π(1) y π(2) y π(3) . . . . . . y π(n)
Proposition 9. Reed Muller codes are 2-transitive Proof is similar to the one given above, find any transformation which satisfies our constraints works.
Note that if we want our codes to satisfy these transitive properties, we must give evaluations of the polynomials on all points in the corresponding fields.
We shall see in the coming sections that RM codes have more interesting properties.

Reed Muller Codes Achieve Capacity on Erasure Channels
As recently as July 2015, Urbanke et. al. and Santhosh Kumar et. al. independently proved that RM codes achieve capacity on erasure channels. Let's us now build up the machinery required to prove the aforementioned result. We assume that the ith bit of the message is transmitted through an erasure channel with probability p i i.e. BEC(p i ). Let's denote this channel by BEC(p) 5 . In this setting we would like to analyze the probability that the MAP decoder is unable to decode the i-th bit and then try to get a bound on the probability of error for the block MAP decoder. We also assume that the input distribution is uniform.
Since we are talking about erasure channels and MAP decoding, we should define EXIT functions which we would use later to capture the decoding errors.
Definition 17. EXIT functions The vector EXIT function associated with the ith bit is defined to be We can define an average exit function, which we would use later.
Definition 18. Average EXIT function Average EXIT function is defined as We denote the bit MAP decoder's output for ith bit as D i . On receiving the sequence Y, if the ith bit X i can be recovered uniquely, then D i (Y) = X i . Otherwise, D i declares an erasure and returns *. We claim that the probability of the decoding failing to decode is equal to the ith EXIT function.
Whenever bit i can be recovered from a received sequence Y = y, H(X i Y = y) = 0. Otherwise, H(X i Y = y) = 1 because of the uniform codeword assumption.

p is the corresponding vector of erasure probabilities
Observe that the probability of being able to decode the ith bit, and hence the value of the ith EXIT function is either equal to zero or one; it cannot be anything between zero or one.
Proposition 11. The MAP exit function for the ith bit satisfies h i (p) = ∂H(X|Y (p)) ∂p i

Proof :
By chain rule of entropy H(X|Y (p)) = H(X i |Y (p)) + H(X ∼i |X i , Y (p)) Observe that the second term written in the above expansion is independent of The second entropy term is zero and the proposition thus follows.
The above proposition leads us to an important theorem in coding theory -the area theorem.
Theorem 8. The Area Theorem The average EXIT function satisfies the area theorem : 1 0 h(p)dp = K N . Proof : The above proposition gives us the derivative of the function. It follows that we can integrate from 0 to 1 on a fixed path (p, p, p, . . . p).
)dt H(X|Y (p)(1)) =H(X ) = K since it is uniform distribution and the encodings capture the same randomness as that of the original distribution.
We would like to look at the set of erasure patterns ( vectors Y ∼i from which we cannot decode the ith bit X i indirectly using MAP decoding. We claim that the following set correctly captures this notion and contains all the erasure patterns from which indirect recovery of the ith bit is not possible. Hence the measure of this set determines the probability of error which is what we eventually want.
Definition 19. The set of patterns 'bad' for bit i are contained in Ω i defined as From the above discussion, it is clear that the measure of the set is equal to the probability of error, which, in turn is equal to the ith exit function because of the uniform input assumption. We summarize this in the following proposition.
We claim that if the code C is 2-transitive, the set Ω i is 1-transitive.
Proposition 13. If C is 2-transitive then Ω i is 1-transitive Proof : Since the code is 2 transitive, there exists a permutation π such that π(i) = j for all i = j. We need to show that this permutation preserves membership in the corresponding Ωs. In other words, we need to show that if A ∈ Ω i then Observe that π(B ∪ i) = π(B) ∪ π(i) = π(B) ∪ j. Since π(B) ⊆ π(A), it follows that π(A) ∈ Ω j This is a bijection because we can do what we did above with the indices i and j interchanged.
Proposition 14. All EXIT functions are equal. Proof: Since the code is transitive, any two locations have a permutation between them. The corresponding Ωs have a bijection between them, and the EXIT function is equal to the measure of the corresponding set Ω. The proposition thus follows.
Note that all EXIT functions are equal to the average EXIT function and thus we are free to invoke the area theorem now.
Intuitively, if we have an erasure pattern which is 'bad', we will not be able to decode the patterns which are obtained after adding more erasures at places where there were no erasures before. The following propositon formalizes this.
Consider a codeword A. Since the code is 2-transitive, there exists a permutation π such that π(i) = i and π(j) = k and π(A) ∈ C . We need to prove that if A ∈ ∂ j Ω i then π(A) ∈ ∂ k Ω i .
If we were to interchange the indices j and k, a similar argument would hold. Hence there is a one-to-one correspondence between the two sets.
The measures of the sets ∂ j Ω i and ∂ k Ω i are equal since we prove that there is one to one correspondence between them.
Our quest to prove that the set Ω( and in turn the average EXIT function) has a sharp threshold, requires us to talk about the influences of the variables and invoke suitable results from boolean function analysis. Let's define a few terms first.

Definition 21. Influence of a variable
Let Ω be a monotone set and let ∂ j Ω {x ∈ {0, 1} N | Ω (x) = Ω (x (j) )}, where The influence of bit j ∈ [N] is defined by I Definition 22. Total Influence The total influence of a bunch of variables is defined as Let's look at a result which talks about the derivative of the measure of monotone sets.

Lemma 1. Margulis -Russo Lemma
Let Ω be a monotone set, then d µp (Ω) dp The above result says that the derivative is lower bounded by a quantity ( which as we shall see, scales with N). But the value of the function has to sum up to one since it is a graph which plots the measure against the probability. This implies that the derivative cannot be high everywhere, and hence the function should have a sharp threshold. First we shall show how this is related to the problem at hand -how the influence of the EXIT functions is related to the measure of the set of pivotal bits.
Proof : We evaluate the partial derivative from the explicit evaluation of h i (p)) done in Proposition 6.
If we differentiate the above quantity with respect to p j and use the fact that Ω i is monotone, we get the above result.
We still need to show how these influences scale with N and tie up the loose ends, and the following theorem, which we state without proof helps us in doing so.
Let Ω be a montone set and suppose that, for all 0 ≤ p ≥ 1, the influences of all bits are equal I 1. There exists an universal constant C ≥ 1 which is independent of p, Ω and N, such that d µp (Ω) dp ≥ C(log N)(µ p (Ω))(1 − µ p (Ω)) 2. For any 0 < ǫ ≤ 1 2 , ≥ t} is the inverse function for the average EXIT function 6 .
It is important to note that for the above theorem to hold, the influences have to be spread quite uniformly. Let's see why this is intuitively true. Say there is a (dictator)function which has N variables and only one bit is influential ( output depends only on this particular bit), the total influence is p (the success). The derivative of this with respect to p is 1 and it does not scale with N as the RHS of the first expression is supposed to.
Observe that the second statement implies that the set has a sharp threshold because p 1−ǫ − p ǫ −→ 0 as N −→ ∞ We have considered bit-MAP decoding for the above result. This result also implies that the channel is capacity achieving under block-MAP decoding, if we consider the following proposition which is quite elementary in itself.
Proposition 18. Relation between the error probabilities of the bit MAP and block MAP decoder where d min is the minimum distance of the code.
We can see that if P bit−M AP −→ 0 with sufficient speed, then P block−M AP −→ 0 as well and thus can summarize the result in the following theorem.
Theorem 10. 2-transitive codes achieve capacity on erasure channel under MAP decoding.
Corollary. Reed Muller codes achieve capacity on erasure channels.
Theorem 11. Polar codes are 2-transitive Proof : The proof is exactly similar to the one given while proving that RS codes are 2-transitive. As we have seen before, polar codes are G N -coset codes in which the input u N 1 is transformed to the codeword x N 1 using the matrix G N , which is eventually sent over the channel.
x N 1 = u N 1 G N We are given four locations in the code -say a, b, c and d ∈ [N] such that a = b and c = d and we need to give a permutation π : [N] −→ [N] such that π(a) = c and π(b) = d and also preserves membership in the code.
For the moment, pick any permutation which satisfies the above constraints -we shall see why it does not matter. Observe that this permutation is a N × N 0,1 permutation matrix. π N ×N * u 1 u 2 u 3 . . . . . . u n 1×N = u π(1) u π(2) u π(3) . . . . . . u π(n) Same holds for the vector x N 1 , because the π matrix does not care about the actual values of the vector it is multiplied with (for it is a permutation matrix). It only permutes the indices to get another vector and will do the same for u N 1 . i.e. π N ×N * x 1 x 2 x 3 . . . . . . x n 1×N = x π(1) x π(2) x π(3) . . . . . . x π(n)
Corollary. Polar codes acheive capacity on erasure channels under MAP decoding.
It should be noted that the rate of polarization in Guruswami's paper on 'Speed of Polarization' would be faster than the above proof would give us.