How to use the Shannon-Fano Coding Calculator
- 1. Enter the symbolsOne per line with a probability or count, or paste text to count characters.
- 2. Choose the tie ruleIf two split points are equally balanced, pick which one your book uses.
- 3. Read the codesSee the splitting steps, each code and length, average length, entropy, efficiency and Huffman's length.
How Shannon-Fano coding works
- Sort the symbols by probability, highest first.
- Split the list into two parts whose total probabilities are as close as possible.
- Give the top part 0 and the bottom part 1.
- Repeat on each part until every part has one symbol.
The result is a prefix code. Average length L = Σ pi li, entropy H = −Σ pi log2 pi, efficiency = H ÷ L and redundancy = 1 − H ÷ L. Shannon-Fano is not always optimal; Huffman coding never does worse.
Worked example
Symbols A, B, C, D, E with counts 15, 7, 6, 6, 5 (total 39).
- First split: {A, B} = 22 against {C, D, E} = 17 (difference 5, better than 15 against 24).
- {A, B} splits into A = 00 and B = 01. {C, D, E} splits into C = 10 and {D, E}, which gives D = 110 and E = 111.
Total bits = 15×2 + 7×2 + 6×2 + 6×3 + 5×3 = 89, so L = 2.28 bits per symbol. Entropy H ≈ 2.186, so efficiency ≈ 95.8%. Huffman coding of the same counts needs 87 bits, showing Shannon-Fano is not always optimal.
Frequently asked questions
Why do different books give different Shannon-Fano codes?
When two split points are equally balanced, books choose differently. Both are valid prefix codes, but the average length can differ. Use the tie option to match yours.
Is Shannon-Fano the same as Shannon coding?
No. Shannon coding gives each symbol a length of ⌈−log₂ p⌉ from cumulative probabilities. Shannon-Fano splits the sorted list into halves.
Can I use counts instead of probabilities?
Yes. The tool scales counts so they add up to 1, and also shows total bits for counts.