E-Book Overview
This book makes a very accessible introduction to a very important contemporary application of number theory, abstract algebra, and probability. It contains numerous computational examples throughout, giving learners the opportunity to apply, practice, and check their understanding of key concepts. KEY TOPICS Coverage starts from scratch in treating probability, entropy, compression, Shannon¿s theorems, cyclic redundancy checks, and error-correction. For enthusiasts of abstract algebra and number theory.
E-Book Content
Copyright ©2004 by Pearson Education The Mathematics of Coding Theory by Paul Garrett ISBN 0-13-101967-8 Copyright © 2004 by Prentice-Hall. Inc. Ali right reserved. Contents Preface 1 2 . . . . . . . . . . . . . . . . '; . . . . . . Probability . . . . . . 1.1 Set.s and functions 1.2 COllnting . . . . .... 1.3 Prdiminary idea..'i of probability 1.4 More formal view of probability 1.5 Random variables, expected values, variance 1.6 Markov's inequality, Chebysheff's inequality 1.7 Law of Large Numbers . . . . . . . . . 5 8 13 20 27 27 Information 2.1 Uncertainty, acquisition of information Definition of entropy . . . '. . . . . 2.2 33 33 37 3 , Noiseless Coding ....... . 3.1 Noiseless coding . . . . . . . 3.2 Kraft and McMillan inequalities 3.3 Noiseless coding th. If the intersection is not empty, then we may say that the two sets meet. The union of two sets A, B is the collection of all elements which lie in one or the other of the two sets, and is denoted A U B. Note that, for example, 1 i {I}, and {{I}} -:f:. {I}. That is, the set {a} with sole element a is not the same thing as the item a itself. An ordered pair (x, y) is just that, a list of two things in which there is a first thing, here x, and a second thing, here y. Two ordered pairs (x, y) and (x', y') are equal if and only if x = x' and y = y'. The (cartesian) product of two sets A, B is the set of ordered pairs (a, b) where a E A and b E B. It is denoted A x B. Thus, while {a, b} = {b, a} might be thought of as an unordered pair, for ordered pairs (a, b) =f (b, a) unless by chance a=b. In case A = B, the cartesian power A x B is often denoted A 2 • More generally, for a fixed positive integer n, the nth cartesian power An of a set is the set of ordered n-tuples (aI, a2,"" an) of elements ai of A. Some very important examples of cartesian powers are those of R or Q or C, . which arise in other contexts as well: for example, R 2 is the collection of ordered 1.1 Sets and functions 3 pairs of real numbers, which we use to describe points in the plane. And R3 is the collection of ordered triples of real numbers, which we use to describe points in three-space. The power set of a set S is the set 01 subsets of S. This is sometimes denoted. by PS. Thus, P¢> = {¢>} P{I,2} = {¢>, {I}, {2}, {I, 2}} Intuitively, a function 1 from one set A to another se\ B is supposed to be a--!rule' which assigns to each element a E A an element b = f(a) E B. This is written as although the latter notation gives no information about the nature of 1 in any detail. More rigorously, but less intuitively, we can define a function by really telling its graph: the formal definition is that a function 1 : A - B is a subset of the product A x B with the property that for every a E A there is a unique b E B so that (a, b) E I. Then we would write I(a) = b. This formal definition is worth noting at least because it should make clear that there is absolutely no requirement that a function be described by any recognizable or simple 'formula'. Map and mapping are common synonyms for function. As a silly example of the formal definition of function, let 1 : {I,3} - {2,6} be the function 'multiply-by-two', so that 1(1) = 2 and 1(3) = 6. Then the 'official' definiti