Editing Shannon–Fano coding (section)

===Shannon's algorithm===

Shannon's method starts by deciding on the lengths of all the codewords, then picks a prefix code with those word lengths.

Given a source with probabilities <math>p_1, p_2, \dots, p_n</math> the desired codeword lengths are <math>l_i = \lceil -\log_2 p_i \rceil</math>. Here, <math>\lceil x \rceil</math> is the [[Floor and ceiling functions|ceiling function]], meaning the smallest integer greater than or equal to <math>x</math>.

Once the codeword lengths have been determined, we must choose the codewords themselves. One method is to pick codewords in order from most probable to least probable symbols, picking each codeword to be the lexicographically first word of the correct length that maintains the prefix-free property.

A second method makes use of cumulative probabilities. First, the probabilities are written in decreasing order <math>p_1 \geq p_2 \geq \cdots \geq p_n</math>. Then, the cumulative probabilities are defined as
:<math>c_1 = 0, \qquad c_i = \sum_{j=1}^{i-1} p_j \text{ for }i \geq 2 , </math>
so <math>c_1 = 0, c_2 = p_1, c_3 = p_1 + p_2</math> and so on.
The codeword for symbol <math>i</math> is chosen to be the first <math>l_i</math> binary digits in the [[binary number|binary expansion]] of <math>c_i</math>.