General coders/decoders for IID sources

Question

I'm trying to understand the following theorem and its proof: It's taken from the MIT course. Here is my understanding of the theorem: Fix the integer $n\ge 1$. We want to compute $$\text{Pr}\{D_n\le n[H[X]-\nu]\}$$Because $D_n$ is a natural number, this probability is same as $$\text{Pr}\{D_n\le \lfloor n[H[X]-\nu]\rfloor\}$$ Now let $m = \lfloor n[H[X]-\nu]\rfloor$. Since $n$ is fixed, $m$ is also determined and fixed. So the probability of interest is $$\text{Pr}\{D_n\le m\}$$ In words, we want to compute the probability that the number of bits at which the decoder can correctly decode $X_1,X_2,\dots,X_n$ is less than or equal $m$. The randomness of $D_n$ comes from the fact that $X_1,X_2,\dots,X_n$ is random and each different sequence $x_1,x_2,\dots,x_n$ leads to different value for $D_n$. If the sequence of RVs is determined, then $D_n$ is determined. So we should compute the probability of occurring certain sequences. The length of encoded binary strings for these sequences should be less than or equal $m$. Is my understanding correct? Assuming that this understanding is correct, I can't follow the proof because the decoder seems to have no role here. We should only be concerned with the binary strings that encoder generates.

Answer 1

That is correct since you are defining the decoder based only on how it performs on input strings. This is an abstract decoder to demonstrate what performance is possible via probabilistic bounds and relate its performance to entropy.

Its or other decoders' efficient practical implementation is another matter, especially for large blocklengths. That topic would normally be covered later on in the course or in a course on digital communications or coding theory.

If you approach the decoder design problem from a probabilistic point of view you study LDPCs, Polar Codes, Convolutional Codes.

If you approach the problem algebraically, the codes are Hamming Codes, Reed Solomon Codes, Reed Muller codes.

For modern channels, especially over wireless with fading and moving transmitter/receiver, the probabilistic approach dominates.

For more stationary channels [e.g., satellite communications, or storage channels] the algebraic codes play a larger part.