(X) p(x)[logMp(x)-logM(AMogA (8.12) = D(p||AM-1) logm A. In the above development, we have introduced the constant A = 1/-((x) which makes the function AM-1(x) a probability distribution. Thus D(p||AM-1(x)) is a Kullback-Leibler distance, which, from Chapter 5, we know to be always nonnega- tive. Because of the Kraft-McMillan inequality, we also have A > 1, or logM > 0. The conclusion is that we always have A > 0, which leads to Shannon's source-coding 16 Namely, a = 1/(u In M), which comes from substituting the result M-1(x) = p(x)/(2 In M) into the con- straint C(l) = M-1(x) : u, and using Exp(x) = 1. This leads to p(x) = M-1(x) /u, from which we obtain 1(x) 3 lopt(x) = -logm p(x) - logMu Information coding theorem: L(X) H HM(X) (8.13) The theorem translates into the following: The mean codeword length cannot be shorter than the source entropy: equality is achieved when the codeword lengths are chosen such that 1(x) = l*(x) = logM P(x) In the general case, there is no reason for l*(x) to be an integer. In this case, a compromise is to take the smallest integer value greater than or equal to l*(x), which is noted [l*(x)]. Such a realistic code assignment is called a Shannon code, which is also known as Shannon-Fano code. We, thus, have l*(x) = [l*(x)] - E(x), with < 1. This relation gives the realistic minimal value of the mean codeword length, which we shall call here L**, and define according to: (8.14) = HM(X)+(E)X. Since 0() < 1, it immediately follows that H(X)L**(X)<HM(X)+ 1, (8.15) which represents another fundamental property of minimal-length codes (or Shannon- Fano codes). The result can be restated as follows: There exists a code whose mean codeword length falls into the interval [HM, HM + 1]; it is equal to the source entropy HM if the distribution l* = -logM p has integer values (dyadic source). This source-coding theorem was the first to be established by Shannon, which explains its other appellation of Shannon's first theorem. By definition, we call redundancy the difference p=L-H.1 - We call Pbou