On page 168 of MacKay's Information Theory, Inference, and Learning Algorithms (http://www.inference.org.uk/mackay/itila/book.html), which is talking about communication (with errors) above capacity, he claims that an encoding scheme (let's call this "auxiliary") for the binary symmetric channel with transition probability $q$ can be reversed so that the decoder becomes a lossy compressor. Specifically, from the perspective of the auxiliary encoding scheme, "the optimal decoder of the code... typically maps a received vector of length $N'$ to a transmitted vector differing in $qN'$ bits from the received vector".

Capacity-achieving encoding scheme ($\text{rate} = \frac{K}{N}\approx C$): Encoder_1 -> Noisy channel -> Decoder_1

Auxiliary encoding scheme ($\text{rate} = \frac{K}{N'}\approx 1-H_2(q)$): Encoder_2 -> BSC -> Decoder_2

Patched encoding scheme ($\text{rate}\approx \frac{C}{1-H_2(q)}$): Decoder_2 -> Encoder_1 -> Noisy channel -> Decoder_1 -> Encoder_2

However, from the perspective of Decoder_2 patched on to the noisy channel, it needs to handle all kinds of $N'$-bit inputs, not just typical ones. My question then, is how do we prove that the bit error probability of this final patched scheme is less than $q$ as required?


1 Answer 1


Your question essentially is the following (just to help other readers not familiar with McKay's textbook and/or the context of the question):

Consider an encoder that maps source codewords $x\in \{0,1\}^K$ to channel codewords $y \in \{0,1\}^{N'}$ (with $K/N' < 1$), and its corresponding decoder, which maps a codeword $r \in \{0,1\}^{N'}$ to a source codeword $\hat{x}\in \{0,1\}^K$. Assume that this coding scheme is able to correctly decode codewords at the output of a BSC with transition probability $q$ (therefore, by the Shannon theorem it must hold $K/N'\leq 1-H(q)$). Now consider the "reverse" operation:

  • An arbitrary (uniformly distributed) codeword $r \in \{0,1\}^{N'}$ is input to the decoder, which, by definition, outputs a codeword $\hat{x}\in \{0,1\}^K$.
  • The codeword $\hat{x}$ is then input to the encoder, which, by definition, will output a codeword $y \in \{0,1\}^{N'}$

What is the (error) probability that a certain bit of $y$ differs from the corresponding one of $r$?

First, lets consider in detail how the decoder operates when the encoder/decoder are used "as normal". As stated in the same section of McKay's book, when the maximum possible rate $K/N'=1-H(q)$ is employed, the received (noisy) codeword $r$ that is input to the decoder is uniformly distributed over $\{0,1\}^{N'}$ (see edit below). Now, the decoder takes the received codeword $r$ and essentially determines the most probable (typical) noise sequence $n \in \{0,1\}^{N'}$ for which $r=\hat{y}\oplus n$, where $\hat{y} \in \{0,1\}^{N'}$ is a valid codeword, and returns the estimate $\hat{x}$ as the unique source codeword corresponding to $\hat{y}$. Note that, for sufficiently large $N'$, the noise codeword $n$ will "typically" consist of $qN'$ ones and $(1-q)N'$ zeros, i.e., $\hat{y}$ and $r$ "typically" differ at $qN'$ positions (bits).

Now, consider the "reverse operation", again with $K/N'=1-H(q)$. A uniformly distributed codeword $r$ is provided at the input of the decoder. Note that this codeword is distributed exactly the same as the codewords at the input of the decoder under "normal" operation, i.e., $r$ is with high probability equal to the sum of a (valid) codeword plus a (typical) noise sequence. The decoder will generate, as described above, a codeword $\hat{x}$ which will have a one-to-one correspondence to a valid codeword $\hat{y}$. When the codeword $\hat{x}$ is provided at the input of the encoder, the encoder will generate the one-to-one map to the codeword $y=\hat{y}$, which, as stated above, differs from $r$ at "typically" $qN'$ positions. This implies that the error probability is $q$.

P.S.: The above arguments (as well as McKay's) are informal and non-rigorous. A rigorous approach requires consideration of rate-distortion theory aspects.

edit: the uniform distribution of the output of the channel follows since the capacity of the binary symmetric channel is achieved when its output is uniformly distributed and a capacity achieving code is considered.

  • $\begingroup$ Thanks! And I believe we can deduce that it is close to uniformly distributed by some mutual information argument? The rate is nearly capacity with low error probability, so Fano's inequality nearly has equality. $\endgroup$ Commented Aug 8, 2017 at 1:39
  • $\begingroup$ @user1537366 Recall the proof of the capacity of the BSC($q$). If $X$ is the input symbol and $Y$ the output symbol (per channel use), it holds $I(X;Y) = H(Y) - H(q)$. The right-hand side is maximized when the output of the channel ($Y$) is uniform, i.e., $C=1-H(q)$, achieved when $X$ is also uniform. In the setting above, since we consider a capacity achieving coding scheme, it follows that each bit of the channel output $r$ must be uniformly distributed. $\endgroup$
    – Stelios
    Commented Aug 8, 2017 at 8:01

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .