Importance of source encoder; Huffman algorithm

Importance of source encoder

The source encoder converts the source symbols into binary code words with the minimum average number of bits by removing redundancy.

• It reduces the average code length toward the entropy ($\bar L \to H$), so the bit rate, bandwidth and power needed are reduced.
• It gives short code words to frequent symbols and long ones to rare symbols (variable-length coding).
• It produces uniquely decodable (prefix) codes, so the receiver can decode without separators.
• It saves storage space and makes room for channel coding redundancy.

Huffman coding algorithm

1. Sort: list all source symbols in decreasing order of probability.
2. Merge: combine the two symbols of lowest probability into one new symbol whose probability is the sum of the two.
3. Reorder: insert the new probability into the list in its proper place (as high as possible among equal values); the list now has one fewer entry.
4. Repeat steps 2–3 until only one entry (probability 1) is left.
5. Assign bits: at each merge, give 0 to one branch (upper) and 1 to the other (lower).
6. Read codes: trace each symbol's path from the final stage back to its original position; the bits along the path form its code word.
7. Evaluate: $\bar L = \sum p_i l_i$, $H = \sum p_i\log_2(1/p_i)$, efficiency $\eta = H/\bar L$.

Short example: $P = \{0.5, 0.25, 0.125, 0.125\}$ → merge 0.125 + 0.125 = 0.25, then 0.25 + 0.25 = 0.5, then 0.5 + 0.5 = 1. Codes: 0, 10, 110, 111; $\bar L = 1.75 = H$, $\eta = 100\%$.