0
$\begingroup$

The book "elements of information theory" (Cover and Thomas) summarizes the relation between source coding and channel coding (bolded text is relevant, rest is background).

I am confused by the statement $R>H$. Here is their quote:

It is now time to combine the two main results that we have proved so far: data compression ($R >H$: Theorem 5.4.2) and data transmission ($R < C$: Theorem 7.7.1). Is the condition $H < C$ necessary and sufficient for sending a source over a channel? For example, consider sending digitized speech or music over a discrete memoryless channel. We could design a code to map the sequence of speech samples directly into the input of the channel, or we could compress the speech into its most efficient representation, then use the appropriate channel code to send it over the channel. It is not immediately clear that we are not losing something by using the two-stage method, since data compression does not depend on the channel and the channel coding does not depend on the source distribution.

For context, here are the relevant definitions and theorems:

Definition. The rate $R$ of an $(M, n)$ code is $$R = \frac {\log M} n$$ bits per transmission. [where $M$ is the amount of to-be-coded messages]

Definition. We define the “information” channel capacity of a discrete memoryless channel as $$C = \max\limits_{p(x)} I (X; Y)$$

Theorem 5.4.2. The minimum expected codeword length $L_n$ per symbol satisfies $$\frac {H(X_1,X_2, . . . , X_n)} n ≤ L_n < \frac {H(X_1,X_2, . . . , X_n)} n + \frac 1 n$$ Moreover, if $X_1,X_2, . . . , X_n$ is a stationary stochastic process, then $L^∗_n → H(X)$, where $H(\mathcal X)$ is the entropy rate of the process


My question: I cannot figure out why Cover and Thomas summarize theorem 5.4.2 as "$R>H$". I can interpret $H$ as $\frac {H(X_1,X_2, . . . , X_n)} n$, in which case we have $H<L_n$, which implies that they mean that $L=R$, but this I find very confusing, since it seems like $L$ and $R$ are almost the opposite of each other. ($L$ measures the amount of symbols needed in expectation to describe $X$, while $R$ the amount of $X$ we can distinguish with a given symbol. larger amount of symbols, everything else equal, should increase $L$ and decrease $R$).

So what is the idea behind the summary $R>H$?

$\endgroup$

1 Answer 1

1
$\begingroup$

To make the argument clearer let $R_s$ and $R$ denote the rate per sample and the rate per second respectively, and similarly let $C_s$ and $C$ denote the capacity per sample and the capacity per second.

$L_n$ denotes the minimum expected number of bits one needs to represent each realisation (i.e each sample) of a source. So naturally, in order to transmit the samples with an arbitrarily small error over a channel you would thus need a channel which is capable of transmitting information at a rate per sample of at least $L_n$ bits per sample. In other words you need a channel that can transmit samples at a rate of at least $R_s$ bits per sample, where $R_s > L_n$. The rate $R_s$ is limited by noise in the channel to being at most $C_s$ bits per sample and so $R_s < C_s$.

All Theorem 5.4.2 does is show that $L_n \rightarrow H(X)$. From the relation above it then follows that $R_s > H(X)$

What this means is that if you have a source that produces $f_s$ samples per second, with the expected length of each sample in bits being $H(X)$, then you will need to transmit the source at a rate per second of at least $R$ bits per second where $R = f_sR_s \implies R > f_sH(X)$. The rate $R$ is also limited by the capacity per second $C = f_s C_s \implies R < C$.

In conclusion

$(\text{Bits Generated Per Second}) < (\text{Transmission Rate Per Second}) < (\text{Maximum Achievable Transmission Rate Per Second})$

$f_sH(X) < f_sR_s < f_sC_s$

$\implies H(X) < R_s < C_s$

Update (Response To Comment):

If a channel is said to be able to achieve a rate of $R_s$ bits per sample, then the channel is able to transmit $2B$ samples a second with each sample having an entropy of $R_s$ bits. In other words, a channel which is said to be able to achieve a rate of $R_s$ bits per sample can transmit $2BR_s$ bits per second where $B$ is the bandwidth of the channel. This transmission rate is can't be higher than the theoretical maximum transmission rate on the channel which is $2BC_s$ bits per second, where $C_s$ is the capacity per sample.

A channel which is able to achieve a rate of $R_s$ bits per sample can thus transmit information from a source producing $2B$ samples per second only if the entropy of each sample outputted by the source ($H(X)$) is less than $R_s$. This is because the source will produce $2BH(X)$ bits per second so you need a channel that can operate at a rate of least that amount.

This means you need to have

$(\text{Bits Generated Per Second}) < (\text{Transmission Rate Per Second}) < (\text{Maximum Achievable Transmission Rate Per Second})$

$f_sH(X) < f_sR_s < f_sC_s$

$2BH(X) < 2BR_s < 2BC_s$

$\implies H(X) < R_s < C_s$

The fact that $f_s$ is limited to being at most $2B$ is due to the Nyquist sampling theorem which basically states that for the signal transmitted over the channel to have a bandwidth of at most $B$ the spacing between sampling should be at least $T = 1/2B$. This then limits the sampling frequency per second to being at most $f_s = 1/T = 2B$.

In the example given where the source produces samples of entropy $8$ bits, you would not be able to transmit $2B$ of those samples in a second over a channel that can only achieve a bit per sample rate of $1$ bit. If you were to transmit the source over the channel you would need to lower the rate at which you are sampling the source to $B/4$ samples per second.

$\endgroup$
2
  • $\begingroup$ "So naturally, in order to transmit the samples with an arbitrarily small error over a channel you would thus need a channel which is capable of transmitting information at a rate per sample of at least $L_n$ bits per sample". I'm confused about this, because surely we can just cut the samples into parts? If it takes 8 string symbols to describe a sample (e.g. an integer describing a color), but the rate of a channel is 1 bit, then we can just use the channel 8 times in a row? So we have H=L>R, but it still works $\endgroup$
    – user56834
    Sep 28, 2019 at 11:11
  • $\begingroup$ @user56834 See updated answer $\endgroup$
    – KillaKem
    Sep 29, 2019 at 11:57

You must log in to answer this question.

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