# Conditions to apply Source Coding Theorem

I was wondering what are the conditions to apply source coding theorem (SCT).

1. Is it applied only to uniform-length coding, what about variable-length coding, does it also satisfy SCT?

I was asking because in my lecture, SCT is only discussed in uniform coding section.

2. Is the result of SCT for uniquely decodable coding or is it for lossless coding?

In Wikipedia SCT, it's said $f$ is unique decodable code, then we have SCT. In my lecture, it gives me an impression that SCT is generally applied to all lossless coding.

• Uniquely decodable coding and lossless coding are the same thing. – Yuval Filmus Mar 14 '18 at 14:16
• Yep, if within the context of uniform encoding, then lossless is equivalent to uniquely decodable. While if not, these two gonna be different concepts. – Logan Mar 15 '18 at 0:57

1. It is an average in bits/symbol and does apply to all coding schemes.

2. You're correct, the number of bits/symbol needed is equal or larger than the entropy rate (asymptotically, though) of the source for any lossless code.

3. If you allow for lossy coding, then a generalization called rate-distortion function is needed to lower bound the rate required.

The source coding theorem is a statement about uniform-length coding. It tells you how long the uniform length should be in order to guarantee high success probability. It can be proved using variable-length coding, but the statement itself just doesn't concern variable-length coding. It is meaningless to ask whether variable-length coding "satisfies" the source coding theorem.

In more detail, suppose there is a source with entropy $H$. We want to encode $n$ i.i.d. samples of the source using as few bits as possible. Generally speaking, if you want to guarantee that the encoding always be decodable back to the original samples, then you cannot bound the length of the encoding (see the example below). Instead, we are content with a guarantee that the decoding will be successful with probability tending to 1. The source coding theorem states that such an encoding is possible using $nR$ bits if and only if $R>H$.

To see why error is necessary, consider a source which is distributed geometrically $G(1/2)$, that is, with probability $1/2$ it equals $1$, with probability $1/4$ it equals $2$, with probability $1/8$ it equals $3$, and so on. The entropy of this source is finite (in fact, 2 bits), but since there are infinitely many potential outcome, if we want to guarantee that decoding will be successful, we must allow a message of unbounded length.

One way to prove the if part of the theorem is using variable-length encoding. It is known that $m$ samples can be encoded as a prefix code using at most $mH+1$ bits in expectation. Taking $m = \sqrt{n}$, this shows that $n$ samples can be encoded using a variable-length encoding of length at most $nH + \sqrt{n}$ bits in expectation. If $R > H$ then for large $n$, $nH + \sqrt{n}$ will be much smaller than $nR$, and furthermore, it can be shown (using the law of large numbers) that it is highly likely that this variable-length encoding will use at most $nR$ bits. Therefore we can take as our uniform-length encoding the first $nR$ bits of this variable-length encoding (padding it arbitrarily if needed).

The only if part of the theorem does have a counterpart for variable-length codes: any prefix code for a source with entropy $H$ must have expected length at least $H$. This is a nice exercise.

As for your second question, lossless encoding is an encoding scheme which can be decoded exactly. This is in contrast to JPEG, for example, which is a lossy encoding – given an image, if you compress it to JPEG and then decompress it, you get a slightly different image.

In contrast, uniquely decodable encoding is a term used to describe variable-length codes with the property that the concatenation of several codewords can be segmented uniquely into codewords. Every uniform-length code is automatically uniquely decodable.

The two terms describe different aspects of the encoding. The first term states that the encoding aims to reconstruct the source exactly rather than approximately. The second term states that the encoding can be used to encode a sequence rather than just a single item.