Proposition 2. For ( X,Y ) a source as above, the following inequalities hold There is no general inequality between H ( U$_{2}$ | Y $^{4}$,U$^{1}$) and H ( U$_{3}$ | Y $^{4}$,U$^{2}$) . The conclusion to be drawn is that polarization is enhanced further by repeating the basic construction. For any N = 2 $^{n}$, n ≥ 1 , the general form of the source polarization transformation is defined algebraically as Either both inequalities are strict or both hold with equality. For equality to hold, it is necessary and sufficient that X conditioned on Y is either deterministic or Ber ( 1 $_{2}$) . The proof is given in the appendix. These inequalities serve the purpose of showing that H ( X | Y ) is near 0 or 1 if and only if Z ( X | Y ) is near 0 or 1, respectively. Hence, the parameters { H ( U$_{i}$ | Y $^{N}$,Ui − $^{1}$) } N i =1 and { Z ( U$_{i}$ | Y $^{N}$,Ui − $^{1}$) } N i =1 polarize simultaneously. For coding theorems, it is important to have a rate of convergence result. where “ ⊗ $^{n}$” denotes the n th Kronecker power and B$_{N}$ is the “bit-reversal” permutation (see [1]). It is easy to check th at the transforms in Figures 1 and 2 conform to U N = X $^{N}$G$_{N}$ . The main result on source polarization for binary alphabets is the following. Definition 1. Let ( X,Y ) be a source as above, and let R > 0 . For N = 2 $^{n}$, n ≥ 1 , let E$_{X}$$_{|}$$_{Y}$ ( N,R ) denote a subset of { 1 ,...,N } such that | E$_{X}$$_{|}$$_{Y}$ ( N,R ) | = ⌈ NR ⌉ and Z ( U$_{i}$ | Y $^{N}$,Ui − $^{1}$) ≤ Z ( U$_{j}$ | Y $^{N}$,Uj − $^{1}$) for all i ∈ E$_{X}$$_{|}$$_{Y}$ ( N,R ) and j / ∈ E$_{X}$$_{|}$$_{Y}$ ( N,R ) . We refer to E$_{X}$$_{|}$$_{Y}$ ( N,R ) as a “high- entropy” (index) set of rate R and block-length N . For the special case where Y is absent or unavailable, we write E$_{X}$ ( N,R ) to denote the high-entropy set of X only. When N and R are clear from the context, we simplify the notation by writing E$_{X}$$_{|}$$_{Y}$ or E$_{X}$ . Theorem 1. Let ( X,Y ) be a source as above. For any N = 2 $^{n}$, n ≥ 1 , let U N = X $^{N}$G$_{N}$ . Then, for any δ ∈ (0 , 1) , as N → ∞ , and We omit the full proof but sketch the idea, which follows the proof of the channel polarization result in [1]. The firststep is to define a tree random process for tracking the evolution of the conditional entropy terms { H ( U$_{i}$ | Y $^{N}$,Ui − $^{1}$) } . The analysis is aided by an accompanying supermartingale based on the source Bhattacharyya parameters. For the basic source ( X,Y ) ∼ P$_{X,Y}$ , this parameter is defined as Theorem 2. Let ( X,Y ) be a source as above and R > H ( X | Y ) be fixed. Consider a sequence of high-entropy sets { E$_{X}$$_{|}$$_{Y}$ ( N,R ) : N = 2 $^{n}$,n ≥ 1 } . For any such sequence, any fixed β < 1 $_{2}$, and asymptotically in N , we have We omit the proof, which is covered by the results of [4]. Let ( X,Y ) be a source as in the previous section and ( X $^{N}$,Y $^{N}$) denote an output block of length N ≥ 1 produced by this source. Shannon’s lossless source coding theorem states that an encoder can compress ( X $^{N}$,Y $^{N}$) into a codeword of length roughly NH ( X | Y ) bits so that a decoder observing the codeword and Y N can recover X N reliably, provided N is sufficiently large. We now describe a method based on polarization that achieves this compression bound. In the absence of any side information Y $^{N}$, the method given here is algorithmically identical to the source coding method proposed in [2] and [3]; however, our viewpoint is different. Instead of reducing the source coding problem to a channel coding problem by exploiting a duality relationship between the two problems, we use direct arguments based solely on source polarization. Fix N = 2 n for some n ≥ 1 . Fix R > H ( X | Y ) and a high-entropy set E$_{X}$$_{|}$$_{Y}$ = E$_{X}$$_{|}$$_{Y}$ ( N,R ) . We omit the proof of this result since it is very similar to the proof of a similar inequality on channel Bhattacharyya parameters given in [1]. Thus, we have the inequality which is the basis of the Bhattacharyya supermartingale. Con- vergence results about the Bhattacharyya supermartingale may be translated into similar results for the entropy martingale through the following pair of inequalities. Encoding: Given a realization X N = x $^{N}$, compute u N = x $^{N}$G$_{N}$ and output u$_{E}$$_{X}$$_{|}$$_{Y}$ as the compressed word. (Note that The source Bhattacharyya parameters satisfy the following as they undergo the two-by-two polarization transformation. Proposition 1. Let ( X,Y ) be a source as above, and ( X$_{1}$,Y$_{1}$ ) and ( X$_{2}$,Y$_{2}$ ) two independent drawings from ( X,Y ) . Then, and III. LOSSLESS SOURCE CODING ∑ i ∈ E c X | $_{Y}$( N,R ) Z ( U$_{i}$ | Y $^{N}$,Ui − $^{1}$) = O (2 − N $^{β}$) . (6) Z ( X | Y ) = 2 ∑ y P$_{Y}$ ( y ) √ P$_{X}$$_{|}$$_{Y}$ (0 | y ) P$_{X}$$_{|}$$_{Y}$ (1 | y ) . Z ( X$_{1}$ ⊕ X$_{2}$ | Y $^{2}$) ≤ 2 Z ( X | Y ) − Z ( X | Y ) 2 Z ( X$_{2}$ | Y $^{2}$,X$_{1}$ ⊕ X$_{2}$ ) = Z ( X | Y ) $^{2}$. Z ( U$_{1}$ | Y $^{2}$) + Z ( U$_{2}$ | Y $^{2}$,U$^{1}$) ≤ 2 Z ( X | Y ) G$_{N}$ = [ 1 0 $_{1 1}$] ⊗ $^{n}$B$_{N}$ (3) Z ( X | Y ) 2 ≤ H ( X | Y ) (4) H ( X | Y ) ≤ log(1 + Z ( X | Y )) . (5) H ( U$_{3}$ | Y $^{4}$,U$^{2}$) ≥ H ( R$_{1}$ | Y 2 $_{1}$,S$_{1}$ ) = H ( R$_{2}$ | Y 4 $_{3}$,S$_{2}$ ) ≥ H ( U$_{4}$ | Y $^{4}$,U$^{3}$) . ∣ { i ∈ [1 ,N ]: H ( U$_{i}$ | Y $^{N}$,Ui − $^{1}$) ∈ (1 − δ, 1] }∣ ∣ N → H ( X | Y ) ∣ { i ∈ [1 ,N ]: H ( U$_{i}$ | Y $^{N}$,Ui − $^{1}$) ∈ [0 ,δ ) }∣ ∣ N → 1 − H ( X | Y ) .