content_image/392438.jpg content_image/392439.jpg content_image/392440.jpg content_image/392441.jpg content_image/392442.jpg content_image/392443.jpg content_image/392444.jpg
the encoder does not require knowledge of the realization of Y N to implement this scheme.) 

Decoding: Having received u$_{E}$$_{X}$$_{|}$$_{Y}$ and observed the real- ization Y N = y $^{N}$, the decoder sequentially builds an estimate ˆ u N of u N by the rule 

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

where 

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

is a likelihood ratio, which can be computed recursively using the formulas: 

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

and 

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

where u 2 i − 2 o and u 2 i − 2 e denote, respectively, the parts of u 2 i − 2 with odd and even indices, and δ$_{i}$ equals 1 or -1 according to u$_{2}$$_{i}$$_{−}$$_{1}$ being 0 or 1, respectively. Having constructed ˆ u $^{N}$, the decoder outputs ˆ x N = ˆ u $^{N}$G − 1 N as the estimate of x $^{N}$. (It is easy to verify that G − 1 N = G$_{N}$ .) 

Performance: The performance of the decoder is measured by the probability of error 

which can be upper-bounded by standard (union-bound) tech- niques as 

The following is a simple corollary to Theorem 2 and (7). 

Theorem 3. For any fixed R > H ( X | Y ) and β < 1 $_{2}$, the probability of error for the above polar source coding method is bounded as P$_{e}$ = O (2 − N $^{β}$) . 

Complexity: The complexity of encoding and that of decod- ing are both O ( N log N ) . 

## IV. APPLICATION TO CHANNEL CODING: DUALITY 

The above source coding scheme can be used to design a capacity-achieving code for any binary-input memoryless channel. Let such a channel be defined by the transition probabilities W ( y | x ) , x ∈ X = { 0 , 1 } and y ∈ Y . Consider the block coding scheme shown in Fig. 3, where signals flow from right to left. Here, N = 2 $^{n}$, n ≥ 1 , is the code block length; U N denotes the message vector, X N = U $^{N}$G$_{N}$ the channel input vector, and Y N the channel output vector. Due 

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

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

to memorylessness, W $^{N}$( y $^{N}$| x $^{N}$) = ∏ N i $_{=1}$W ( y$_{i}$ | x$_{i}$ ) for any x N ∈ X $^{N}$, y N ∈ Y $^{N}$. We turn the triple ( U $^{N}$,X$^{N}$,Y $^{N}$) into a joint ensemble 

of random vectors by assigning the probabilities Pr( X N = x $^{N}$) = 2 − N for all x N ∈ { 0 , 1 } $^{N}$. Under this assignment, ( X $^{N}$,Y $^{N}$) may be regarded as independent samples from a source ( X,Y ) ∼ Q ( x ) W ( y | x ) where Q is the uniform distribution on { 0 , 1 } . We let I ( W ) = I ( X ; Y ) denote the symmetric channel capacity and fix R < I ( W ) . This implies that 1 − R > H ( X | Y ) . Let E$_{X}$$_{|}$$_{Y}$ = E$_{X}$$_{|}$$_{Y}$ ( N, 1 − R ) denote a high-entropy set of rate (1 − R ) for the source ( X,Y ) . The following coding scheme achieves reliable communication at rate R over the channel W . N 

Encoding: Prepare a binary source vector U as follows. 

Pick the pattern U$_{E}$$_{X}$$_{|}$$_{Y}$ at random from the uniform distri- bution and make it available to the decoder ahead of the session. In each round, fill U$_{E}$ c X | Y with uniformly chosen data bits. (Thus, ⌊ NR ⌋ bits are sent in each round, for a data transmission rate of roughly R .) Encode U N into a channel codeword by computing X N = U $^{N}$G$_{N}$ and transmit X N over the channel W . 

Decoding: Having received Y $^{N}$, use the source decoder of the previous section to produce an estimate ˆ U$_{E}$ c X | Y of the data bits U$_{E}$ c X | Y . 

Analysis: The error probability Pr( ˆ U$_{E}$ c X | Y ̸ = U$_{E}$ c X | $_{Y}$) is bounded as O (2 − N $^{β}$) for any fixed β < 1 2 since the source coding rate is 1 − R > H ( X | Y ) . The complexity of the scheme is bounded as O ( N log N ) . 

Remark. The above argument reduces the channel coding problem for achieving the symmetric capacity I ( W ) of a binary-input channel W to a source coding problem for a source ( X,Y ) ∼ QW where Q is uniform on { 0 , 1 } . This reduction exploits the duality of the two problems. This dual approach provides an alternative proof of the channel coding results of [1]. It also complements the duality arguments in [2] and [3], where the source coding problem for a Ber ( p ) source was reduced to a channel coding problem for a binary symmetric channel with cross-over probability p . 

The above source coding method can be easily extended to the Slepian-Wolf setting [5]. Suppose { ( X$_{i}$,Y$_{i}$ ) } ∞ i =1 are independent samples from a source ( X,Y ) where both X and Y are binary RVs. In the Slepian-Wolf scenario, there are two encoders and one decoder. Fix a block-length N = 2 $^{n}$, n ≥ 1 , and rates R$_{x}$ and R$_{y}$ for the two encoders. Encoder 1 observes X N only and maps it to an integer i$_{x}$ ∈ [1 , 2 $^{NR$_{x}$}$] , encoder 2 observes Y N only and maps it to an integer i$_{y}$ ∈ [1 , 2 $^{NR$_{y}$}$] . The decoder in the system observes ( i$_{x}$,i$_{y}$ ) 

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

## V. SLEPIAN-WOLF CODING 

