Source Polarization Erdal Arıkan Bilkent University, Ankara, Turkey Abstract —The notion of source polarization is introduced and investigated. This complements the earlier work on channel polar- ization. An application to Slepian-Wolf coding is also considered. The paper is restricted to the case of binary alphabets. Extension of results to non-binary alphabets is discussed briefly. Index Terms —Polar codes, source polarization, channel polar- ization, source coding, Slepian-Wolf coding. We introduce the notion of “source polarization” which complements “channel polarization” that was studied in [1] . One immediate application of source polarization is the design of polar codes for lossless source coding. Lossless source coding using polar codes has already been considered ex- tensively in the pioneering works [2] and [3], which reduced this problem to one of channel polarization using the duality between the two problems. The approach in this paper is direct and offers an alternative (primal) viewpoint. This paper is restricted mostly to binary memoryless sources. We indicate in the end briefly the possible gener- alizations to non-binary sources. We use the notation of [1]. In particular, we write u N to denote a vector ( u$_{1}$,...,u$_{N}$ ) and u j i to denote the sub-vector ( u$_{i}$,...,u$_{j}$ ) for any 1 ≤ i ≤ j ≤ N . If j < i , u j i is the null vector. The logarithm is to the base 2 unless otherwise indicated. We write X ∼ Ber ( p ) to denote a Bernoulli random variable (RV) with values in { 0 , 1 } and P$_{X}$ (1) = p . The entropy H ( X ) of such a RV is denoted sometimes as H ( p ) = − p log p − (1 − p ) log(1 − p ) . Let ( X,Y ) ∼ P$_{X,Y}$ be an arbitrary pair of random variables over X × Y with X = { 0 , 1 } and Y an arbitrary countable set. Throughout this section, we regard ( X,Y ) as a memoryless source, with X as the part to be compressed and Y in the role of “side-information” about X . We consider a sequence { ( X$_{i}$,Y$_{i}$ ) } ∞ i =1 of independent drawings from ( X,Y ) and write ( X $^{N}$,Y $^{N}$) to denote the first N elements of this sequence, for any integer N ≥ 1 . The basic idea of source polarization is contained in the transformation shown in Fig. 1, where “ ⊕ ” denotes addition mod-2. The operation ( X$_{1}$,X$_{2}$ ) → ( U$_{1}$,U$_{2}$ ) performed by the circuit preserves entropy, i.e., It is easy to show that equalities hold here if and only if H ( X | Y ) equals 0 or 1. Thus, unless the entropies at the input of the circuit are already perfectly polarized, the entropies at the output will polarize further. but is polarizing in the sense that Using the chain rule, we may split the output entropy as Note that the variables U 4 are assigned to the output terminals of the circuit in Fig. 2 in a shuffled order. This is motivated by the observation that, with this ordering, the pair ( U$_{1}$,U$_{2}$ ) is obtained from two i.i.d. RVs, namely, ( S$_{1}$,S$_{2}$ ) , by the same two-by-two construction as in Fig. 1. A similar remark applies to the relationship between ( U$_{3}$,U$_{4}$ ) and ( R$_{1}$,R$_{2}$ ) . These observations lead to the the following inequalities, which are special cases of those in (2). H ( U $^{4}$| Y $^{4}$) = 4 ∑ i =1 H ( U$_{i}$ | Y $^{4}$,U i − $^{1}$) . H ( U$_{1}$ | Y $^{4}$) ≥ H ( S$_{1}$ | Y 2 1 ) = H ( S$_{2}$ | Y 4 3 ) ≥ H ( U$_{2}$ | Y $^{4}$,U$^{1}$) , Fig. 1. Basic source transformation. Fig. 2. Four-by-four source transformation. Figure 2 shows the recursive continuation of the construc- tion to the case where four independent copies of ( X,Y ) are processed. The entropy conservation law states that H ( U $^{4}$| Y $^{4}$) = H ( X $^{4}$| Y $^{4}$) = 4 H ( X | Y ) . II. POLARIZATION OF BINARY MEMORYLESS SOURCES WITH SIDE INFORMATION I. INTRODUCTION H ( U$_{1}$,U$_{2}$ | Y$_{1}$,Y$_{2}$ ) = H ( X$_{1}$,X$_{2}$ | Y$_{1}$,Y$_{2}$ ) = 2 H ( X | Y ) , (1) H ( U$_{1}$ | Y$_{1}$,Y$_{2}$ ) ≥ H ( X | Y ) ≥ H ( U$_{2}$ | Y$_{1}$,Y$_{2}$,U$_{1}$ ) . (2) + + + + X$_{4}$ X$_{3}$ X$_{2}$ X$_{1}$ U$_{4}$ U$_{2}$ U$_{3}$ U$_{1}$ R$_{2}$ S$_{2}$ R$_{1}$ S$_{1}$ + X$_{2}$ X$_{1}$ U$_{2}$ U$_{1}$ = X$_{1}$ ⊕ X$_{2}$ arXiv:1001.3087v2 [cs.IT] 28 Apr 2010