Am learning the concept of Coding Redundancy in image compression and am finding it hard to understand the table on page 3 of this document. All other explanations seem to follow the same symbols and methodology but don't explain the concept clearly.

In the first column, r1=1/7, r2=2/7 etc and r7 is 1. Why is that? According to the column "Code1", the Code1 is created based on the r value which should range from 0 to 7. Why then are there fractions like 1/7, 2/7 etc?

What is "Code2"? At least for Code1, when the value is 000, I know it is the binary representation of 0. But the same thing in Code2, is 11. I don't understand what and how they are trying to represent with Code2.

Even if 0 is represented by 11 and 6 is represented by 000001 in variable length encoding, how is the algorithm supposed to know which 0 starts where and which 1 ends where? For example, to represent 60, I'd have to encode it as 00000111. When decoding, how is the algorithm supposed to know that it's 60?

  • $\begingroup$ There should be one question per post. $\endgroup$ – Evil Nov 28 '17 at 12:08

In the first column, $r_k$ is the gray level. It ranges from 0 to 1, where 0 is 0% white (i.e., black) and 1 is 100% white. There are 8 gray levels arranged in regular intervals of 1/7.

Code 1 and Code 2 are two different ways of encoding the gray level. Code 1 is a fixed-length code (all codewords have the same length) whereas Code 2 is a variable-length code, specifically a prefix code, presumably a Huffman code for the distribution in the second column. Code 2 is better because the expected codeword length is 2.7 bits, which is smaller than the 3 bits that you get with Code 1.

Since Code 2 is a prefix code, decoding it is actually very simple, and requires no lookahead. (That's why prefix codes are sometimes called instantaneous codes.)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.