For a finite source alphabet with probabilities and binary prefix code lengths , the expected length satisfiesTo see this, let by Kraft inequality and put . Direct calculation givesusing nonnegativity of relative entropy. Thus the information entropy measures the unavoidable average description length, rather than the length of every individual message.
If at least two symbols have positive probability, the Shannon lengths are positive, satisfy Kraft inequality, and obey . For a one-symbol source, ; if codewords must have positive length, a one-bit codeword has expected length , so the strict upper bound requires that separate convention or a nontrivial alphabet.
For a complete binary prefix code with lengths , the Kraft inequality is an equality: . Put . The difference between expected codeword length and Shannon entropy isThe Kullback-Leibler divergence is nonnegative and vanishes exactly when . Hence a complete code is entropy-tight exactly for its dyadic matching source. For example, lengths match probabilities . Being an optimal prefix code among symbol-by-symbol codes is a weaker condition and does not imply this equality.
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.
Articles by others on the same topic
There are currently no matching articles.