Codes For Error Detection

by Torleiv Klove

Overview

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.

Product Details

ISBN-13:	9789812705860
Publisher:	World Scientific Publishing Company, Incorporated
Publication date:	04/26/2007
Series:	Series On Coding Theory And Cryptology , #2
Pages:	216
Product dimensions:	6.20(w) x 9.00(h) x 0.80(d)

Table of Contents

Preface     vii
Basics on error control     1
ABC on codes     1
Basic notations and terminology     1
Hamming weight and distance     2
Support of a set of vectors     2
Extending vectors     3
Ordering     3
Entropy     3
Systematic codes     3
Equivalent codes     4
New codes from old     4
Cyclic codes     5
Linear codes     6
Generator and check matrices for linear codes     6
The simplex codes and the Hamming codes     6
Equivalent and systematic linear codes     7
New linear codes from old     7
Cyclic linear and shortened cyclic linear codes     10
Distance distribution of codes     13
Definition of distance distribution     13
The MacWilliams transform     13
Binomial moment     16
Distance distribution of complementary codes     20
Weight distribution of linear codes     22
Weight distribution     22
Weight distribution of *-extended codes     23
MacWilliams's theorem     23
A generalized weightdistribution     24
Linear codes over larger fields     24
Weight distribution of cosets     25
Counting vectors in a sphere     27
Bounds on the number of code words of a given weight     29
The weight hierarchy     30
Principles of error detection     30
Pure detection     30
Combined correction and detection     31
Comments and references     32
Error detecting codes for the q-ary symmetric channel     35
Basic formulas and bounds     35
The q-ary symmetric channel     35
Probability of undetected error     35
The threshold     42
Alternative expressions for the probability of undetected error     44
Relations to coset weight distributions     45
P[subscript ue] for a code and its MacWilliams transform     45
Conditions for a code to be satisfactory, good, or proper     47
How to determine if a polynomial has a zero     47
Sufficient conditions for a code to be good     49
Necessary conditions for a code to be good or satisfactory     49
Sufficient conditions for a code to be proper     57
Large codes are proper     60
Results on the average probability     66
General results on the average     66
The variance     67
Average for special classes of codes     68
Average for systematic codes     72
The worst-case error probability     79
General bounds     84
Lower bounds     84
Upper bounds     89
Asymptotic bounds     95
Optimal codes     97
The dual of an optimal code     97
Copies of the simplex code     97
New codes from old     97
The *-operation     98
Shortened codes     101
Product codes     102
Repeated codes     102
Probability of having received the correct code word     103
Combined correction and detection     105
Using a single code for correction and detection     105
Concatenated codes for error correction and detection     108
Probability of having received the correct code word after decoding     109
Complexity of computing P[subscript ue](C,p)     109
Particular codes     110
Perfect codes     110
MDS and related codes     112
Cyclic codes      114
Two weight irreducible cyclic codes     115
The product of two single parity check codes     116
How to find the code you need     116
The local symmetric channel     118
Comments and references     124
Error detecting codes for the binary symmetric channel     129
A condition that implies "good"     129
Binary optimal codes for small dimensions     132
Modified codes     136
Adding/removing a parity bit     136
Even-weight subcodes     137
Binary cyclic redundancy check (CRC) codes     137
Particular codes     140
Reed-Muller codes     140
Binary BCH codes     143
Z[subscript 4]-linear codes     144
Self-complementary codes     147
Self-dual codes     148
Binary constant weight codes     149
The codes [Characters not reproducible]     149
An upper bound     151
Lower bounds     151
Comments and references     152
Error detecting codes for asymmetric and other channels     153
Asymmetric channels     153
The Z-channel     153
Codes for the q-ary asymmetric channel      156
Diversity combining on the Z-channel     159
Coding for a symmetric channel with unknown characteristic     162
Bounds     163
Constructions     164
Codes for detection of substitution errors and transpositions     165
ST codes     165
ISBN     170
IBM code     171
Digital codes with two check digits     172
Barcodes     173
Error detection for runlength-limited codes     175
Comments and references     178
Bibliography     181
Index     199