Past exam question: 2076 Ashwin, Q8(a)
Open in the Padhaiko appQuestion
Design a Binary Shannon-Fano code with a six symbol source with probability assignment as .
Solution
Principles of Binary Shannon-Fano Coding Algorithm:
- Arrange source symbols in descending order of probabilities.
- Divide the sorted set of symbols into two subsets whose accumulated probability sums are as nearly equal as possible.
- Assign binary digit
0to the first subset and binary digit1to the second subset. - Recursively repeat the partitioning and bit-assignment process for each subset until each sub-group contains exactly one symbol.
Sorting and Recursive Partitioning: Source symbols sorted in descending probability order:
- :
- :
- :
- :
- :
- :
Total probability .
Iteration 1:
- Partition into two subsets of near-equal probability:
- Subset A: with Assign
0 - Subset B: with Assign
1(Note: Splitting between and yields difference . Splitting () vs remainder () gives difference , so Subset A is ). - is isolated Codeword for =
0.
- Subset A: with Assign
Iteration 2 (Partitioning Subset B):
- Group:
- Subset B1: with Append
0 - Subset B2: with Append
1 - Perfect split ()!
- is isolated Codeword for =
10.
- Subset B1: with Append
Iteration 3 (Partitioning Subset B2):
- Group: (Total )
- Subset B2a: with (or with vs with : )
- Split () Append
0 - Split () Append
1
Iteration 4:
- For :
- () Append
01100 - () Append
11101
- () Append
- For :
- () Append
01110 - () Append
11111
- () Append
Assigned Shannon-Fano Codewords Table:
| Symbol | Probability | Stage 1 | Stage 2 | Stage 3 | Stage 4 | Final Codeword | Codeword Length () |
|---|---|---|---|---|---|---|---|
0 | — | — | — | 0 | 1 | ||
1 | 0 | — | — | 10 | 2 | ||
1 | 1 | 0 | 0 | 1100 | 4 | ||
1 | 1 | 0 | 1 | 1101 | 4 | ||
1 | 1 | 1 | 0 | 1110 | 4 | ||
1 | 1 | 1 | 1 | 1111 | 4 |
Answer:
The Binary Shannon-Fano code assignments are:
- ():
0(length 1) - ():
10(length 2) - ():
1100(length 4) - ():
1101(length 4) - ():
1110(length 4) - ():
1111(length 4)