TABLE OF CONTENTS We present here Shannon's first theorem, which concerns optimal source coding and the transmission of its information on a non-perturbed channel, while also giving limits to the compression rate which can be expected. We first introduce several basic concepts.
Here, we attempt to determine the conditions of existence required for an optimal coding scheme, i.e. a code having maximum efficiency.
Let S be a memoryless stationary source [ S] = [ s 1, s 2, , s k], generating k codewords [ C] = [ c 1, c 2, , c k], of average length 
.
We have seen previously that efficiency is maximized when 
, and is obtained when H( ?) is maximum, i.e. H( ?) = log l. This value is reached when all the l letters of the alphabet have the same occurrence probability:
Assuming these letters are independent, we have:
Now, ? k i=1 p( s i) = 1, and so:
From here we can conclude that, given an alphabet, with a known number of letters and words, an optimal coding scheme can be designed, provided relation (5.34) holds.
This result is only a special case of the McMillan inequality, which states:
and which expresses a necessary and sufficient condition for the existence of irreducible codes.
McMillan inequality. We consider a code with k words...
