English
Menu

Information Theory and Coding Basics

Which of the following correctly describes the relationship between lossless compression and the entropy of a source?

  1. AWith a good enough lossless compression algorithm, any file, whatever its contents, can always be made smaller than the original
  2. BEven for a source that emits symbols independently, a cleverly designed lossless code can make the average code length smaller than the entropy
  3. CThe average code length of a lossless code cannot be made smaller than the entropy, but coding symbols together brings it closer
Show answer and explanation

Answer: C. The average code length of a lossless code cannot be made smaller than the entropy, but coding symbols together brings it closer

For a source that emits symbols independently, the average code length per symbol of a lossless code is at least the entropy, and coding symbols together brings it arbitrarily close to the entropy (the source coding theorem). Moreover, there are 2ⁿ files of n bits, but only 2ⁿ − 1 bit strings shorter than that in total, so no lossless compression can shorten every file. Lossless compression shortens data with skew or repetition at the cost of making other data slightly longer.

  • A. By the pigeonhole principle, not every file can be shortened. Random data and data that are already compressed hardly shrink at all.
  • B. The entropy is the lower bound of the average code length. Trying to go below it produces a code that cannot be decoded in only one way.
  • C. Correct. The entropy sets the limit of lossless coding.
Practice this topic Back to topic

Books on Information Theory and Coding Basics Ad

As an Amazon Associate I earn from qualifying purchases.

More Information Theory and Coding Basics questions

  1. The 40-character string AAAAAAAAAAAABBBBCCCCCCCCCCCCCCCCCCCCDDDD (12 As, 4 Bs, 20 Cs and 4 Ds) is compressed with run-length encoding, which represents each run of the same character as a pair of "character (1 byte) and count (1 byte)". The original string uses 1 byte per character. Defining the compression ratio as "size after compression ÷ size before compression", which of the following is the compression ratio?
  2. Which of the following data is most likely to be made smallest by run-length encoding?
  3. Which of the following correctly describes the idea of the LZ77 method used in ZIP, gzip and similar tools?
  4. Data compressed with the LZ77 method are to be restored. The data consist of "character A", "character B" and "(distance 2, length 5)", in that order. (distance d, length L) means repeating L times, one character at a time, "copy the character d characters back from the end of the restored string to its end". Which of the following is the restored string?
  5. When compressing data, which of the following must use lossless compression rather than lossy compression?