文档介绍：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 ................ '; ..... . xi
1 Probability . . . . . . 1
and functions 1
COllnting . . .. .... 5
Prdiminary idea..'i of probability 8
More formal view of probability 13
Random variables, expected values, variance 20
Markov's inequality, Chebysheff's inequality 27
Law of Large Numbers . . . . . . . . . 27
2 Information 33
Uncertainty, acquisition of information 33
Definition of entropy . . . '. . . . . 37
3 , Noiseless Coding ....... . 44
Noiseless coding . . . . . . . 44
Kraft and McMillan inequalities 48
Noiseless coding th<,'orem 51
Huffman encoding 54
4 Noisy Coding . . . ~' . . . 61
Noisy chaimels 61
Bxample; par~ty cheeks 63
Decoding from a noisy channel 66
Chanuel capacity 67
Noisy eoding theorem 71
5 Cyclic Redundancy Checks .... 82
The finite field with 2 elements 82
Polynomials over GF(2). .'. . 83
Cyclic redundancy checks '(CRCs) 86
What errors docs a CRC catch? 88
vii
viii Contents
6 The Integers ..... . 93
The reduction algorithm 93
Divisibility 96
Factorization into primes 99
A failure of unique factorization 103
The Euclidean Algorithm 105
Equivalence relations 108
The integers modulo m 111
The finite field Zip for p prime 115
Fermat's Little Theorem 117
Euler's theorem 118
Facts about primitive roots 120
Euler's criterion' 121
Fast modular exponentiation 122
Sun-Ze's theorem. 124
Euler's phi-function. 128
7 Permutations and Interleavers 134
Permutations of sets 134
ShufHes 139
. Block iIiterleavers 141
8 Groups 145
Groups 145
Subgroups