Shannon's source coding theorem is a fundamental result in information theory, established by Claude Shannon in his groundbreaking 1948 paper "A Mathematical Theory of Communication." The theorem provides a formal framework for understanding how to optimally encode information in a way that minimizes the average length of the code while still allowing for perfect reconstruction of the original data.
Articles by others on the same topic
For a finite-alphabet memoryless classical information source with information entropy , every uniquely decodable code for blocks of source symbols has expected binary length at least . This follows from Kraft inequality for uniquely decodable codes and the entropy lower bound for prefix codes.
If at least two source symbols have positive probability, give each positive-probability block Shannon length . These lengths satisfy Kraft inequality, so a prefix code exists, and independence givesThus coding longer blocks approaches the information entropy in expected bits per source symbol. This is an average-length statement: rare blocks can have long codewords.
For a source with only one possible symbol, a one-bit codeword for each length- block gives rate when positive codeword lengths are required. The limiting theorem therefore remains true, although the strict one-block bound needs the nontrivial-alphabet assumption. Countably infinite alphabets require additional care about finite information entropy and the chosen code construction.