Codes for Error Detection, Vol. 2 (2007)(en)(201s)

Torleiv Klove9789812705860, 981-270-586-4

There are two basic methods of error control for communication, both involving coding of the messages. With forward error correction, the codes are used to detect and correct errors. In a repeat request system, the codes are used to detect errors and, if there are errors, request a retransmission. Error detection is usually much simpler to implement than error correction and is widely used. However, it is given a very cursory treatment in almost all textbooks on coding theory. Only a few older books are devoted to error detecting codes.This book begins with a short introduction to the theory of block codes with emphasis on the parts important for error detection. The weight distribution is particularly important for this application and is treated in more detail than in most books on error correction. A detailed account of the known results on the probability of undetected error on the q-ary symmetric channel is also given.

---

Table of contents :
Contents……Page 10
Preface……Page 8
1.1.1 Basic notations and terminology……Page 14
1.1.3 Support of a set of vectors……Page 15
1.1.7 Systematic codes……Page 16
1.1.9 New codes from old……Page 17
1.1.10 Cyclic codes……Page 18
1.2.2 The simplex codes and the Hamming codes……Page 19
1.2.4 New linear codes from old……Page 20
1.2.5 Cyclic linear and shortened cyclic linear codes……Page 23
1.3.2 The MacWilliams transform……Page 26
1.3.3 Binomial moment……Page 29
1.3.4 Distance distribution of complementary codes……Page 33
1.4.1 Weight distribution……Page 35
1.4.3 MacWilliams’s theorem……Page 36
1.4.5 Linear codes over larger fields……Page 37
1.4.6 Weight distribution of cosets……Page 38
1.4.7 Counting vectors in a sphere……Page 40
1.4.8 Bounds on the number of code words of a given weight……Page 42
1.6.1 Pure detection……Page 43
1.6.2 Combined correction and detection……Page 44
1.7 Comments and references……Page 45
2.1.2 Probability of undetected error……Page 48
2.1.3 The threshold……Page 55
2.1.4 Alternative expressions for the probability of undetected error……Page 57
2.2 Pue for a code and its MacWilliams transform……Page 58
2.3.1 How to determine if a polynomial has a zero……Page 60
2.3.3 Necessary conditions for a code to be good or satisfactory……Page 62
2.3.4 Suffcient conditions for a code to be proper……Page 70
2.3.5 Large codes are proper……Page 73
2.4.1 General results on the average……Page 79
2.4.2 The variance……Page 80
2.4.3 Average for special classes of codes……Page 81
2.4.4 Average for systematic codes……Page 85
2.5 The worst-case error probability……Page 92
2.6.1 Lower bounds……Page 97
2.6.2 Upper bounds……Page 102
2.6.3 Asymptotic bounds……Page 108
2.8 New codes from old……Page 110
2.8.1 The -operation……Page 111
2.8.2 Shortened codes……Page 114
2.8.4 Repeated codes……Page 115
2.9 Probability of having received the correct code word……Page 116
2.10.1 Using a single code for correction and detection……Page 118
2.10.2 Concatenated codes for error correction and detec- tion……Page 121
2.11 Complexity of computing Pue(C; p)……Page 122
2.12.1 Perfect codes……Page 123
2.12.2 MDS and related codes……Page 125
2.12.3 Cyclic codes……Page 127
2.12.4 Two weight irreducible cyclic codes……Page 128
2.13 How to nd the code you need……Page 129
2.14 The local symmetric channel……Page 131
2.15 Comments and references……Page 137
3.1 A condition that implies “good”……Page 142
3.2 Binary optimal codes for small dimensions……Page 145
3.3.1 Adding/removing a parity bit……Page 149
3.4 Binary cyclic redundancy check (CRC) codes……Page 150
3.5.1 Reed-Muller codes……Page 153
3.5.2 Binary BCH codes……Page 156
3.5.3 Z4-linear codes……Page 157
3.5.4 Self-complementary codes……Page 160
3.5.5 Self-dual codes……Page 161
3.6.1 The codes m n……Page 162
3.6.3 Lower bounds……Page 164
3.7 Comments and references……Page 165
4.1.1 The Z-channel……Page 166
4.1.2 Codes for the q-ary asymmetric channel……Page 169
4.1.3 Diversity combining on the Z-channel……Page 172
4.2 Coding for a symmetric channel with unknown charac- teristic……Page 175
4.2.1 Bounds……Page 176
4.2.2 Constructions……Page 177
4.3.1 ST codes……Page 178
4.3.2 ISBN……Page 183
4.3.3 IBM code……Page 184
4.3.4 Digital codes with two check digits……Page 185
4.3.5 Barcodes……Page 186
4.4 Error detection for runlength-limited codes……Page 188
4.5 Comments and references……Page 191
Bibliography……Page 194
Index……Page 212