Math 480, Fall 2016, Assignment 10
From cartan.math.umb.edu
The moving power of mathematical invention is not reasoning but the imagination.
- - Augustus de Morgan
Carefully state the following theorems (you do not need to prove them):[edit]
- Compression bound (relating the minimum average word length for a uniquely decodable code to the entropy of the source).
Solve the following problems:[edit]
- Consider a binary source that emits zeros with probability $1/2$ and ones with probability $1/2$. Devise a prefix-free code with minimal average word length, and compare its word length to the entropy of the source. Then devise an optimal block code with block length two, and compare its average word length per source character to the entropy of the source. How much compression is possible for this source?
- Repeat the problem above, but with a source that emits zeros with probability $1$ and ones with probability $0$. How much compression is possible?
