Shannon–Fano coding

In the field of <a href="/facts/Data_compression/gMFuY4FT">data compression</a>, Shannon–Fano coding, named after <a href="/facts/Claude_Shannon/EremsCws">Claude Shannon</a> and <a href="/facts/Robert_Fano/UvrpTDQK">Robert Fano</a>, is one of two related techniques for constructing a <a href="/facts/Prefix_code/461neBYx">prefix code</a> based on a set of symbols and their probabilities (estimated or measured).

<ul><li>Shannon's method chooses a prefix code where a source symbol 
 
 
 
 i
 
 
 {\displaystyle i}
 
 is given the codeword length 
 
 
 
 
 l
 
 i
 
 
 =
 ⌈
 −
 
 log
 
 2
 
 
 ⁡
 
 p
 
 i
 
 
 ⌉
 
 
 {\displaystyle l_{i}=\lceil -\log _{2}p_{i}\rceil }
 
. One common way of choosing the codewords uses the binary expansion of the cumulative probabilities. This method was proposed in Shannon's "<a href="/facts/A_Mathematical_Theory_of_Communication/Dze1Bnpo">A Mathematical Theory of Communication</a>" (1948), his article introducing the field of <a href="/facts/Information_theory/qNLH3U5P">information theory</a>.</li>
<li>Fano's method divides the source symbols into two sets ("0" and "1") with probabilities as close to 1/2 as possible. Then those sets are themselves divided in two, and so on, until each set contains only one symbol. The codeword for that symbol is the string of "0"s and "1"s that records which half of the divides it fell on. This method was proposed in a later (in print) <a href="/facts/Technical_report/wPoTJetR">technical report</a> by Fano (1949).</li></ul>
Shannon–Fano codes are <a href="/facts/Optimization_(mathematics)/oRn8Iv5I">suboptimal</a> in the sense that they do not always achieve the lowest possible expected codeword length, as <a href="/facts/Huffman_coding/dBgMBz48">Huffman coding</a> does. However, Shannon–Fano codes have an expected codeword length within 1 bit of optimal. Fano's method usually produces encoding with shorter expected lengths than Shannon's method. However, Shannon's method is easier to analyse theoretically.
Shannon–Fano coding should not be confused with <a href="/facts/Shannon%25E2%2580%2593Fano%25E2%2580%2593Elias_coding/22peHUzg">Shannon–Fano–Elias coding</a> (also known as Elias coding), the precursor to <a href="/facts/Arithmetic_coding/WU0H4oNu">arithmetic coding</a>.

Shannon–Fano coding open-in-new

Shannon–Fano coding