Data Loading...
FOR SALE IN INDIA, BANGLADESH, BHUTAN, MALDIVES, NEPAL, PAKISTAN AND SRI LANKA ONLY
San Ling and Chaoping Xing
Coding Theory A First Course
9 780521 529 Restricted South Asia Edition This edition is licensed for sale in India, Bangladesh, Bhutan, Maldives, Nepal, Pakistan and Sri Lanka only. This edition is not authorized for export outside these territories. Circulation of this edition outside these territories is unauthorized and illegal.
Coding Theory A First Course Coding theory is concerned with successfully transmitting data through a noisy channel and correcting errors in corrupted messages. It is of central importance for many applications in computer science or engineering. This book gives a comprehensive introduction to coding theory whilst only assuming basic linear algebra. It contains a detailed and rigorous introduction to the theory of block codes and moves on to more advanced topics such as BCH codes, Goppa codes and Sudan’s algorithm for list decoding. The issues of bounds and decoding, essential to the design of good codes, feature prominently. The authors of this book have, for several years, successfully taught a course on coding theory to students at the National University of Singapore. This book is based on their experiences and provides a thoroughly modern introduction to the subject. There is a wealth of examples and exercises, some of which introduce students to novel or more advanced material.
Coding Theory A First Course SAN LING CHAOPING XING National University of Singapore
314 to 321, 3rd Floor, Plot No.3, Splendor Forum, Jasola District Centre, New Delhi 110025, India Cambridge University Press is part of the University of Cambridge. It furthers the University’s mission by disseminating knowledge in the pursuit of education, learning and research at the highest international levels of excellence. www.cambridge.org Information on this title: www.cambridge.org/9780521821919 © Cambridge University Press 2004 This publication is in copyright. Subject to statutory exception and to the provisions of relevant collective licensing agreements, no reproduction of any part may take place without the written permission of Cambridge University Press. First published 2004 First South Asia edition 2019 This South Asia edition is based on San Ling,Chaoping Xing/ Coding Theory: A First Course/ 9780521821919/ 2004 A catalogue record for this publication is available from the British Library ISBN 978-1-108-71754-0 Paperback Cambridge University Press has no responsibility for the persistence or accuracy of URLs for external or third-party internet websites referred to in this publication, and does not guarantee that any content on such websites is, or will remain, accurate or appropriate.
To Mom and Dad and my beloved wife Bee Keow S. L.
To my wife Youqun Shi and my children Zhengrong and Menghong C. P. X.
Contents
Preface
page xi
1
Introduction Exercises
1 4
2 2.1 2.2 2.3 2.4 2.5
Error detection, correction and decoding Communication channels Maximum likelihood decoding Hamming distance Nearest neighbour/minimum distance decoding Distance of a code Exercises
5 5 8 8 10 11 14
3 3.1 3.2 3.3 3.4
Finite fields Fields Polynomial rings Structure of finite fields Minimal polynomials Exercises
17 17 22 26 30 36
4 4.1 4.2 4.3 4.4 4.5 4.6 4.7 4.8
Linear codes Vector spaces over finite fields Linear codes Hamming weight Bases for linear codes Generator matrix and parity-check matrix Equivalence of linear codes Encoding with a linear code Decoding of linear codes
39 39 45 46 48 52 56 57 59
vii
viii
Contents
4.8.1 Cosets 4.8.2 Nearest neighbour decoding for linear codes 4.8.3 Syndrome decoding Exercises
59 61 62 66
5 5.1 5.2 5.2.1 5.2.2 5.3 5.3.1 5.3.2 5.3.3 5.3.4 5.4 5.5 5.6 5.6.1 5.6.2 5.6.3 5.6.4 5.7 5.8
Bounds in coding theory The main coding theory problem Lower bounds Sphere-covering bound Gilbert–Varshamov bound Hamming bound and perfect codes Binary Hamming codes q-ary Hamming codes Golay codes Some remarks on perfect codes Singleton bound and MDS codes Plotkin bound Nonlinear codes Hadamard matrix codes Nordstrom–Robinson code Preparata codes Kerdock codes Griesmer bound Linear programming bound Exercises
75 75 80 80 82 83 84 87 88 92 92 95 96 98 98 99 99 100 102 106
6 6.1 6.2 6.3
Constructions of linear codes Propagation rules Reed–Muller codes Subfield codes Exercises
113 113 118 121 126
7 7.1 7.2 7.3 7.4 7.5
Cyclic codes Definitions Generator polynomials Generator and parity-check matrices Decoding of cyclic codes Burst-error-correcting codes Exercises
133 133 136 141 145 150 153
Contents
ix
8 8.1 8.1.1 8.1.2 8.1.3 8.2 8.3
Some special cyclic codes BCH codes Definitions Parameters of BCH codes Decoding of BCH codes Reed–Solomon codes Quadratic-residue codes Exercises
159 159 159 161 168 171 175 183
9 9.1 9.2 9.3 9.4 9.4.1 9.4.2
Goppa codes Generalized Reed–Solomon codes Alternant codes Goppa codes Sudan decoding for generalized RS codes Generation of the (P, k, t)-polynomial Factorization of the (P, k, t)-polynomial Exercises
189 189 192 196 202 203 205 209
References Bibliography Index
215 217 219
Preface
In the seminal paper ‘A mathematical theory of communication’ published in 1948, Claude Shannon showed that, given a noisy communication channel, there is a number, called the capacity of the channel, such that reliable communication can be achieved at any rate below the channel capacity, if proper encoding and decoding techniques are used. This marked the birth of coding theory, a field of study concerned with the transmission of data across noisy channels and the recovery of corrupted messages. In barely more than half a century, coding theory has seen phenomenal growth. It has found widespread application in areas ranging from communication systems, to compact disc players, to storage technology. In the effort to find good codes for practical purposes, researchers have moved beyond block codes to other paradigms, such as convolutional codes, turbo codes, space-time codes, low-density-parity-check (LDPC) codes and even quantum codes. While the problems in coding theory often arise from engineering applications, it is fascinating to note the crucial role played by mathematics in the development of the field. The importance of algebra, combinatorics and geometry in coding theory is a commonly acknowledged fact, with many deep mathematical results being used in elegant ways in the advancement of coding theory. Coding theory therefore appeals not just to engineers and computer scientists, but also to mathematicians. It has become increasingly common to find the subject taught as part of undergraduate or graduate curricula in mathematics. This book grew out of two one-semester courses we have taught at the National University of Singapore to advanced mathematics and computer science undergraduates over a number of years. Given the vastness of the subject, we have chosen to restrict our attention to block codes, with the aim of introducing the theory without a prerequisite in algebra. The only mathematical prerequisite assumed is familiarity with basic notions and results in
xi
xii
Preface
linear algebra. The results on finite fields needed in the book are covered in Chapter 3. The design of good codes, from both the theoretical and practical points of view, is a very important problem in coding theory. General bounds on the parameters of codes are often used as benchmarks to determine how good a given code is, while, from the practical perspective, a code must admit an efficient decoding scheme before it can be considered useful. Since the beginning of coding theory, researchers have done much work in these directions and, in the process, have constructed many interesting families of codes. This book is built pretty much around these themes. A fairly detailed discussion on some well known bounds is included in Chapter 5, while quite a number of decoding techniques are discussed throughout this book. An effort is also made to introduce systematically many of the well known families of codes, for example, Hamming codes, Golay codes, Reed–Muller codes, cyclic codes, BCH codes, Reed–Solomon codes, alternant codes, Goppa codes, etc. In order to stay sufficiently focused and to keep the book within a manageable size, we have to omit certain well established topics or examples, such as a thorough treatment of weight enumerators, from our discussion. Wherever possible, we try to include some of these omitted topics in the exercises at the end of each chapter. More than 250 problems have been included to help strengthen the reader’s understanding and to serve as an additional source of examples and results. Finally, it is a pleasure for us to acknowledge the help we have received while writing this book. Our research work in coding theory has received generous financial assistance from the Ministry of Education (Singapore), the National University of Singapore, the Defence Science and Technology Agency (Singapore) and the Chinese Academy of Sciences. We are thankful to these organizations for their support. We thank those who have read through the drafts carefully and provided us with invaluable feedback, especially Fangwei Fu, Wilfried Meidl, Harald Niederreiter, Yuansheng Tang (who has also offered us generous help in the preparation of Section 9.4), Arne Winterhof and Sze Ling Yeo, as well as the students in the classes MA3218 and MA4261. David Chew has been most helpful in assisting us with problems concerning LATEX, and we are most grateful for his help. We would also like to thank Shanthi d/o Devadas for secretarial help.
1
Introduction
Information media, such as communication systems and storage devices of data, are not absolutely reliable in practice because of noise or other forms of introduced interference. One of the tasks in coding theory is to detect, or even correct, errors. Usually, coding is defined as source coding and channel coding. Source coding involves changing the message source to a suitable code to be transmitted through the channel. An example of source coding is the ASCII code, which converts each character to a byte of 8 bits. A simple communication model can be represented by Fig. 1.1. Example 1.0.1 Consider the source encoding of four fruits, apple, banana, cherry, grape, as follows: apple → 00,
banana → 01,
cherry → 10,
grape → 11.
Suppose the message ‘apple’, which is encoded as 00, is transmitted over a noisy channel. The message may become distorted and may be received as 01 (see Fig. 1.2). The receiver may not realize that the message was corrupted. This communication fails. The idea of channel coding is to encode the message again after the source coding by introducing some form of redundancy so that errors can be detected or even corrected. Thus, Fig. 1.1 becomes Fig. 1.3.
message source ↓ source encoder
−→
channel
Fig. 1.1.
1
−→
receiver ↑ source decoder
2
Introduction
apple ↓ 00
−→
channel ↑ noise
−→
banana ↑ 01
Fig. 1.2.
message source ↓ source encoder ↓ channel encoder
−→
channel
−→
receiver ↑ source decoder ↑ channel decoder
Fig. 1.3.
Example 1.0.2 In Example 1.0.1, we perform the channel encoding by introducing a redundancy of 1 bit as follows: 00 → 000,
01 → 011,
10 → 101,
11 → 110.
Suppose that the message ‘apple’, which is encoded as 000 after the source and channel encoding, is transmitted over a noisy channel, and that there is only one error introduced. Then the received word must be one of the following three: 100, 010 or 001. In this way, we can detect the error, as none of 100, 010 or 001 is among our encoded messages. Note that the above encoding scheme allows us to detect errors at the cost of reducing transmission speed as we have to transmit 3 bits for a message of 2 bits. The above channel encoding scheme does not allow us to correct errors. For instance, if 100 is received, then we do not know whether 100 comes from 000, 110 or 101. However, if more redundancy is introduced, we are able to correct errors. For instance, we can design the following channel coding scheme: 00 → 00000,
01 → 01111,
10 → 10110,
11 → 11001.
Suppose that the message ‘apple’ is transmitted over a noisy channel, and that there is only one error introduced. Then the received word must be one of the following five: 10000, 01000, 00100, 00010 or 00001. Assume that 10000 is received. Then we can be sure that 10000 comes from 00000 because there are
3
Introduction
apple ↓ 00 ↓ 00000
−→
channel ↑ noise
−→
apple ↑ 00000 ↑ 10000
Fig. 1.4.
at least two errors between 10000 and each of the other three encoded messages 01111, 10110 and 11001. Note that we lose even more in terms of information transmission speed in this case. See Fig. 1.4 for this example. Example 1.0.3 Here is a simple and general method of adding redundancy for the purpose of error correction. Assume that source coding has already been done and that the information consists of bit strings of fixed length k. Encoding is carried out by taking a bit string and repeating it 2r + 1 times, where r ≥ 1 is a fixed integer. For instance, 01 −→ 0101010101 if k = 2 and r = 2. In this special case, decoding is done by first considering the positions 1, 3, 5, 7, 9 of the received string and taking the first decoded bit as the one which appears more frequently at these positions; we deal similarly with the positions 2, 4, 6, 8, 10 to obtain the second decoded bit. For instance, the received string 1100100010 is decoded to 10. It is clear that, in this special case, we can decode up to two errors correctly. In the general case, we can decode up to r errors correctly. Since r is arbitrary, there are thus encoders which allow us to correct as many errors as we want. For obvious reasons, this method is called a repetition code. The only problem with this method is that it involves a serious loss of information transmission speed. Thus, we will look for more efficient methods. The goal of channel coding is to construct encoders and decoders in such a way as to effect: (1) fast encoding of messages;
FOR SALE IN INDIA, BANGLADESH, BHUTAN, MALDIVES, NEPAL, PAKISTAN AND SRI LANKA ONLY
9 780521 529 Coding theory is concerned with successfully transmitting data through a noisy channel and correcting errors in corrupted messages. It is of central importance for many applications in computer science or engineering. This book gives a comprehensive introduction to coding theory whilst only assuming basic linear algebra. It contains a detailed and rigorous introduction to the theory of block codes and moves on to more advanced topics such as BCH codes, Goppa codes and Sudan’s algorithm for list decoding. The issues of bounds and decoding, essential to the design of good codes, feature prominently. The authors of this book have, for several years, successfully taught a course on coding theory to students at the National University of Singapore. This book is based on their experiences and provides a thoroughly modern introduction to the subject. There is a wealth of examples and exercises, some of which introduce students to novel or more advanced material.
Cover designed by Zoe Naylor
Restricted South Asia Edition This edition is licensed for sale in India, Bangladesh, Bhutan, Maldives, Nepal, Pakistan and Sri Lanka only. This edition is not authorized for export outside these territories. Circulation of this edition outside these territories is unauthorized and illegal.