161-A2.1

• Activity: Source Coding
• Instructions: In this activity, you are tasked to
  • Walk through the examples.
  • Write a short program to compress and decompress a redundant file.
• Should you have any questions, clarifications, or issues, please contact your instructor as soon as possible.

Uniquely Decodable Codes

Let us try to encode a source with just four symbols in its alphabet, i.e. $A=\{a_{1},a_{2},a_{3},a_{4}\}$, with probability distribution $P=\{0.5,0.25,0.125,0.125\}$. We can calculate the entropy of this source as:

$H\left(S\right)=0.5\log _{2}\left({\frac {1}{0.5}}\right)+0.25\log _{2}\left({\frac {1}{0.25}}\right)+0.125\log _{2}\left({\frac {1}{0.125}}\right)+0.125\log _{2}\left({\frac {1}{0.125}}\right)=1.75\,\mathrm {bits}$

(1)

Let us look at a few bit sequence assignments and see if they are uniquely decodable or not.

Symbol	Probability	Code 1	Code 2	Code 3	Code 4	Code 5
$a_{1}$	0.5	0	0	0	0	00
$a_{2}$	0.25	0	1	10	01	01
$a_{3}$	0.125	1	00	110	011	10
$a_{4}$	0.125	10	11	111	0111	11
Average Code Length:		1.125	1.25	1.75	1.875	2