Introduction

Consider a discrete memoryless source with source statistics p = (p0, p1, …, pr−1), that is, a sequence U1, U2, … of independent, identically distributed random variables with common distribution P{U = i} = pi, i = 0, 1, …, r − 1. According to the results of Chapter 3, it is in principle possible to represent this source faithfully using an average of bits per source symbol. In this chapter we study an attractive constructive procedure for doing this, called variable-length source coding.

To get the general idea (and the reader is warned that the following example is somewhat meretricious), consider the particular source p = (½, ¼ ⅛ ⅛), whose entropy is H2(½, ¼ ⅛ ⅛) = 1.75 bits. The source alphabet is AU = {0, 1, 2, 3}; now let us encode the source sequence U1, U2, … according to Table 11.1. For example, the source sequence 03220100 … would be encoded into 011111011001000 …. Clearly the average number of bits required per source symbol using this code is ½ · 1 + ¼ · 2 + ⅛ · 3 + ⅛ · 3 = 1.75, the source entropy. This fact in itself is not surprising, since we could, for example, get the average down to only one bit per symbol by encoding everything into 0! The remarkable property enjoyed by the code of Table 11.1 is that it is uniquely decodable, that is, the source sequence can be reconstructed perfectly from the encoded stream.

Introduction: The generator and parity-check matrices

We have already noted that the channel coding theorem (Theorem 2.4) is unsatisfactory from a practical standpoint. This is because the codes whose existence is proved there suffer from at least three distinct defects:

1. (a) They are hard to find (although the proof of Theorem 2.4 suggests that a code chosen “at random” is likely to be pretty good, provided its length is large enough).

2. (b) They are hard to analyze. (Given a code, how are we to know how good it is? The impossibility of computing the error probability for a fixed code is what led us to the random coding artifice in the first place!)

3. (c) They are hard to implement. (In particular, they are hard to decode: the decoding algorithm suggested in the proof of Theorem 2.4–search the region S(y) for codewords, and so on–is hopelessly complex unless the code is trivially small.)

In fact, virtually the only coding scheme we have encountered so far which suffers from none of these defects is the (7, 4) Hamming code of the Introduction. In this chapter we show that the Hamming code is a member of a very large class of codes, the linear codes, and in Chapters 7–9 we show that there are some very good linear codes which are free from the three defects cited above.

The idea of writing a book on all the areas of mathematics that appear in the evaluation of integrals occurred to us when we found many beautiful results scattered throughout the literature.

The original idea was naive: inspired by the paper “Integrals: An Introduction to Analytic Number Theory” by Lian Vardi (1988) we decided to write a text in which we would prove every formula in Table of Integrals, Series, and Products by I. S. Gradshteyn and I. M. Rhyzik (1994) and its precursor by Bierens de Haan (1867). It took a short time to realize that this task was monumental.

In order to keep the book to a reasonable page limit, we have decided to keep the material at a level accesible to a junior/senior undergraduate student. We assume that the reader has a good knowledge of one-variable calculus and that he/she has had a class in which there has been some exposure to a rigorous proof. At Tulane University this is done in Discrete Mathematics, where the method of mathematical induction and the ideas behind recurrences are discussed in some detail, and in Real Analysis, where the student is exposed to the basic material of calculus, now with rigorous proofs. It is our experience that most students majoring in mathematics will have a class in linear algebra, but not all (we fear, few) study complex analysis. Therefore we have kept the use of these subjects to a minimum. In particular we have made an effort not to use complex analysis.

The goal of the book is to present to the reader the many facets involved in the evaluation of definite integrals.