content_image/375508.jpg content_image/375509.jpg content_image/375510.jpg content_image/375501.jpg content_image/375502.jpg content_image/375503.jpg content_image/375504.jpg content_image/375505.jpg content_image/375506.jpg content_image/375507.jpg content_image/375500.jpg
<img src='content_image/375508.jpg'>

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 

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. 

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 → ∞ , 

<img src='content_image/375509.jpg'>

and 

<img src='content_image/375510.jpg'>

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 

<img src='content_image/375501.jpg'>

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 

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. 

<img src='content_image/375502.jpg'>

<img src='content_image/375503.jpg'>

<img src='content_image/375504.jpg'>

<img src='content_image/375505.jpg'>

Proposition 2. For ( X,Y ) a source as above, the following inequalities hold 

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. 

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 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 ) . N N 

Encoding: Given a realization X = x $^{N}$, compute u = x $^{N}$G$_{N}$ and output u$_{E}$$_{X}$$_{|}$$_{Y}$ as the compressed word. (Note that 

<img src='content_image/375506.jpg'>

<img src='content_image/375507.jpg'>

<img src='content_image/375500.jpg'>

## III. LOSSLESS SOURCE CODING 

