Skip to main content

Source coding; Huffman for five symbols (0.3, 0.25, 0.2, 0.15, 0.1)

Short answer

Source coding represents symbols with minimal average bits. Huffman coding assigns S0=00, S1=10, S2=11, S3=010, S4=011, giving average length 2.25 bits and efficiency 99.03%.

What is source coding? Develop Huffman coding of a 5 symbol source with probabilities: S0 = 0.3, S1 = 0.25, S2 = 0.2, S3 = 0.15, S4 = 0.1. And also calculate Coding efficiency.

Source coding

Source coding is the process of representing the symbols of an information source by binary code words with the least average number of bits, by removing redundancy, so that the average code length approaches the source entropy (e.g. Huffman, Shannon–Fano coding).

Huffman code

PP: S0 = 0.3, S1 = 0.25, S2 = 0.2, S3 = 0.15, S4 = 0.1.

Reduction (sum of two lowest moved up as high as possible):

StageProbabilities (descending)Combined
10.3, 0.25, 0.2, 0.15, 0.10.15 + 0.1 = 0.25
20.3, 0.25, 0.25, 0.20.25 + 0.2 = 0.45
30.45, 0.3, 0.250.3 + 0.25 = 0.55
40.55, 0.450.55 + 0.45 = 1
Symbolpip_iHuffman codelil_i
S00.3002
S10.25102
S20.2112
S30.150103
S40.10113

Coding efficiency

Symbolpip_ilog⁡2(1/pi)\log_2(1/p_i)pilog⁡2(1/pi)p_i\log_2(1/p_i)
S00.31.73700.5211
S10.252.00000.5000
S20.22.32190.4644
S30.152.73700.4105
S40.13.32190.3322
Total12.2282
H=2.2282 bits/symbolLˉ=0.3(2)+0.25(2)+0.2(2)+0.15(3)+0.1(3)=2.25 bits/symbolη=HLˉ=2.22822.25=99.03%\begin{aligned} H &= 2.2282\ \text{bits/symbol} \\ \bar L &= 0.3(2)+0.25(2)+0.2(2)+0.15(3)+0.1(3) = 2.25\ \text{bits/symbol} \\ \eta &= \frac{H}{\bar L} = \frac{2.2282}{2.25} = 99.03\% \end{aligned}

Answer: S0, S1, S2 get 2-bit codes and S3, S4 get 3-bit codes; efficiency 99.03 %.

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Communication Systems chapter 6 questions →