Past exam question: 2079 Ashwin (Back), Q7
Open in the Padhaiko appIllustrate the importance of Huffman algorithm in data communication over the network using the following string. Also generate Huffman code.
Solution
Importance of Huffman Algorithm in Network Data Communication:
- Bandwidth Conservation: Network bandwidth is a costly, finite physical resource. Huffman coding is an optimal variable-length, lossless prefix coding algorithm that assigns shorter binary codes to frequently occurring symbols and longer codes to rarer symbols, drastically reducing the total number of transmitted bits.
- Reduced Transmission Latency: The serialization transmission delay over a network link is (where is the message length in bits and is link data rate in bps). Compressing the message directly shortens transmission and queuing delays across intermediate routers.
- Prefix-Free Property (Instantaneous Decoding): No assigned codeword is a prefix of any other codeword. The receiving network node can instantaneously decode the continuous bitstream sequentially without needing delimiters, escape sequences, or lookahead buffering.
- Lossless Integrity: Critical network payloads (text, executable code, telemetry data) cannot tolerate lossy compression; Huffman guarantees 100% exact bit-level reconstruction.
Frequency Analysis of the Given String: Input String:
Total character count . Counting the frequencies of distinct symbols:
A: occurs 5 times (indices 2, 3, 4, 8, 10)B: occurs 3 times (indices 0, 11, 12)C: occurs 3 times (indices 1, 7, 9)D: occurs 2 times (indices 5, 6)
Total frequency verification: .
Huffman Tree Construction:
- Initial sorted nodes:
- Combine lowest two ( and ):
- Create parent node with frequency .
- Left child = , Right child = .
- Active nodes:
- Combine next lowest two ( and ):
- Create parent node with frequency .
- Left child = , Right child = .
- Active nodes:
- Combine final two ( and ):
- Create root node with frequency .
- Left child = , Right child = .
Codeword Generation and Encoded Output: Assigning binary 0 to left branches and 1 to right branches:
Root (13)
/ \
0 / \ 1
A (5) N2 (8)
/ \
0 / \ 1
C (3) N1 (5)
/ \
0 / \ 1
D (2) B (3)
Codeword Assignment Table:
| Symbol | Frequency () | Huffman Code | Codeword Length () | Total Bits () |
|---|---|---|---|---|
A | 5 | 0 | 1 bit | |
C | 3 | 10 | 2 bits | |
D | 2 | 110 | 3 bits | |
B | 3 | 111 | 3 bits | |
| Total | 13 | — | — | 26 bits |
Encoded Bitstream of "BCAAADDACACBB":
Bitstream: 11110000110110010010111111 (length = 26 bits).
Quantitative Network Bandwidth Savings Analysis:
- Standard Uncompressed 8-bit ASCII:
- Fixed-Length Encoding (4 symbols bits/char):
- Huffman Compressed Stream:
- Bandwidth Reduction compared to 8-bit ASCII:
Transmitting 75% fewer bits across the network reduces channel utilization and speeds up packet delivery fourfold.
For the string "BCAAADDACACBB":
- Generated Huffman Codes:
A:0(length 1)C:10(length 2)D:110(length 3)B:111(length 3)
- Total Compressed Size: (encoded as
11110000110110010010111111). - Network Impact: Reduces payload from 104 bits (standard ASCII) to 26 bits, achieving a 75% bandwidth reduction with instantaneous prefix-free decoding.