Author: Torleiv Kløve

Published in: World Scientific

ISBN: 978-981-270-586-0

File Type: pdf

File Size:  1 MB

Language: English

Description of Codes for Error Detection

There are two basic methods of error control for communication, both involving coding of the messages. The differences lay in the way the codes are utilized. The codes used are block codes, which are the ones treated in CODES FOR ERROR DETECTION book, or convolutional codes. Often the block codes used are linear codes. 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 re-transmission. Usually it is a much more complex task to correct errors than merely detect them. Detecting errors has the same complexity as encoding, which is usually linear in the length of the code words. Optimal error correcting decoding is in general an NP-hard problem, and efficient decoding algorithms are known only for some classes of codes. This has generated much research into finding new classes of codes with efficient decoding as well as new decoding algorithms for known classes of codes.
There are a number of books on error control, some are listed in the bibliography at the end of CODES FOR ERROR DETECTION book. The main theme of almost all these books is error correcting codes. Error detection tends to be looked upon as trivial and is covered in a few pages at most. What is then the reason behind the following book which is totally devoted to error detecting codes? The reason is, on the one hand, that error detection combined with repeat requests is a widely used method of error control, and on the other hand, that the analysis of the reliability of the information transmission system with error detection is usually quite complex. Moreover, the methods of analysis are often not sufficiently known, and simple rules of the thumb are used instead.
The main parameter of a code for error detection is its probability of error detection, and this is the main theme of CODES FOR ERROR DETECTION book. There are many papers devoted to the study of the probability of undetected error, both for symmetric channels and other channels, with or without memory. They are spread over many journals and conference proceedings. In Kløve and Korzhik (1995), which was published twelve years ago, we collected the results then known, mainly for linear codes on the binary symmetric channel, and presented them in a unified form. We also included a number of new results. In the last twelve years a number of significant new results have been published (in approximately one hundred new papers). In the present book, we have included all the important new results, and we also include some new unpublished results. As far as possible, the results are given for both linear and non-linear codes, and for general alphabet size. Many results previously published for binary codes or for linear codes (or both) are generalized.
Similar Books