In Chapter 25 we present the hard direction of the rate-distortion theorem: the random coding construction of a quantizer. This method is extended to the development of a covering lemma and soft-covering lemma, which lead to the sharp result of Cuff showing that the fundamental limit of channel simulation is given by Wyner’s common information. We also derive (a strengthened form of) Han and Verdú’s results on approximating output distributions in Kullback–Leibler.

So far our discussion of channel coding was mostly following the same lines as the M-ary hypothesis testing (HT) in statistics. In Chapter 18 we introduce a key departure from this: The principal and most interesting goal in information theory is the design of the encoder mapping an input message to the channel input. Once the codebook is chosen, the problem indeed becomes that of M-ary HT and can be tackled by standard statistical tools. However, the task of choosing the encoder has no exact analogs in statistical theory (the closest being design of experiments). It turns out that the problem of choosing a good encoder will be much simplified if we adopt a suboptimal way of testing M-ary HT, based on thresholding information density.