Shannon coding, also known as Shannon-Fano coding, is a technique for data compression and encoding based on the principles laid out by Claude Shannon, one of the founders of information theory. It aims to represent symbols of a dataset (or source) using variable-length codes based on the probabilities of those symbols. The primary goal is to minimize the total number of bits required to encode a message while ensuring that different symbols have uniquely distinguishable codes.
Articles by others on the same topic
For source probabilities , Shannon coding chooses binary lengths . They satisfy , so the Kraft inequality ensures that a binary prefix code with these lengths exists.
Its expected length obeys , where is the source entropy. For probabilities , the words achieve the lengths exactly. The construction rounds each information content up separately; Huffman coding can improve the expected length by optimizing the whole code tree.[ref]
A Mathematical Theory of Communication by Claude Shannon. Part I, discrete noiseless coding and codeword lengths