uncertain). Since the codeword lengths must be integer numbers, the optimal condi- tion l*(x) = -logm p(x) can only be approximately satisfied in the general case. The codeword lengths must then be chosen as the integer number greater than but closest to l*(x). The above demonstration does not prove that the choice of codeword length l*(x) minimizes the mean codeword length L. We don't know, either, if the difference A is positive or negative in the general case. To establish both properties, we must use the so-called Kraft-McMillan inequality, which is demonstrated in Appendix F. This inequality, which applies to prefix codes,15 : (8.7) Let's prove first that l*(x) is the minimum mean codeword length. For this, we apply the Lagrange-multipliers method, which we have already used in Chapters 4 and 6 to As it turns out, the Kraft inequality also applies to the greater class of uniquely decodable codes (McMillan inequality), hence the name Kraft-McMillan inequality. 8.6 Shannon's source-coding theorem maximize the entropy of discrete and continuous sources. To recall, this method makes it possible to find the function lopt(x) for which any function L(1) is minimized (or maximized), given the constraint that C(1) = U, where L, C are any derivable functions of l and U is a constant. Formally, one first defines: (8.8) where L(1) = p(x)l(x) and C(1) = M-1(x) = M = U. The derivation of Eq. (8.8) with respect to 1(x) leads to px)-M(x (8.9) al(x) Setting the result in Eq. (8.9) to zero, we obtain the parameter A, which, with the constraint, yields the optimum function lopt(x) : 16 lopt(x)=-logmp(x)-logM U. (8.10) Since by definition < 1, the smallest codeword-length for any X is given by (x) = logm p(x), (8.11) which we had previously found in Eq. (8.6) to be the function for which L(X) = H(X). The above demonstration proves that the codeword length distribution l* (x) yields the shortest mean codeword length L(X). We can now prove that the source entropy H(X) represents an absolute lower bound for L(X). Indeed, 1=L(X)-HM