The.Theory.of.Error-Correcting.Codes.pdf-资料库

weixin_44055020-10842654-16359647248530437460.pdf-第1页.png

第1页 / 共771页

weixin_44055020-10842654-16359647248530437460.pdf-第2页.png

第2页 / 共771页

weixin_44055020-10842654-16359647248530437460.pdf-第3页.png

第3页 / 共771页

weixin_44055020-10842654-16359647248530437460.pdf-第4页.png

第4页 / 共771页

weixin_44055020-10842654-16359647248530437460.pdf-第5页.png

第5页 / 共771页

weixin_44055020-10842654-16359647248530437460.pdf-第6页.png

第6页 / 共771页

weixin_44055020-10842654-16359647248530437460.pdf-第7页.png

第7页 / 共771页

weixin_44055020-10842654-16359647248530437460.pdf-第8页.png

第8页 / 共771页

North-Holland Mathematical Library Board of Advisory Editors: M. Artin, H. Bass, J. Eells, W. Feit, P. J. Freyd, F. W. Gehring, H. Halberstam, L. V. Horrnander, M. Kac, J. H. B. Kernperrnan, H. A. Lauwerier, W. A. J. Luxemburg, F. P. Peterson, I. M. Singer, and A. C. Zaanen VOLUME 16 north-holland publishing company arnsterdarn . new york * oxford

The Theory of Error-Correcting Codes F.J. MacWilliams N.J.A. Sloane Bell Laboratories Murray Hill NJ 07974 U. S. A. north-holland publishing company amsterdam . new york . oxford

@ North-Holland Publishing Company 1977 All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted, in any form or by any means, electronic, mechanical, photocopying, recording or otherwise, without the prior permission of the copyright owner. LCC Number: 76-41296 ISBN: 0 444 85009 0 0 444 85010 4 and Published by: North-Holland Publishing Company Amsterdam . New York . Oxford Sole distributors for the U.S.A. and Canada: Elsevier/North-Holland Inc. 52 Vanderbilt Avenue New York, NY 10017 Library of Congress Cataloging in Publication Data MacWilliams, Florence Jessie, 1917- The theory of error-correcting codes. 1 . Error-correcting codes (Information theory) joint author. I. Sloane, Neil James Alexander, 1939- 11. Title. QA268.M3 ISBN 0 444 85009 0 and 0 444 85010 4 5 19.4 76-4 1296 Second printing 197 8 Third printing 1981 PRINTED IN THE NETHERLANDS

P ref ace Coding theory began in the late 1940’s with the work of Golay, Hamming and Shannon. Although it has its origins in an engineering problem, the subject has developed by using more and more sophisticated mathematical techniques. It is our goal to present the theory of error-correcting codes in a simple, easily understandable manner, and yet also to cover all the important aspects of the subject. Thus the reader will find both the simpler families of codes - for example, Hamming, BCH, cyclic and Reed-Muller codes - dis- cussed in some detail, together with encoding and decoding methods, as well as more advanced topics such as quadratic residue, Golay, Goppa, alternant, Kerdock, Preparata, and self-dual codes and association schemes. Our treatment of bounds on the size of a code is similarly thorough. We discuss both the simpler results - the sphere-packing, Plotkin, Elias and Garshamov bounds - as well as the very powerful linear programming method and the McEliece-Rodemich-Rumsey-Welch bound, the best asymptotic result known. An appendix gives tables of bounds and of the best codes presently known of length up to 512. Having two authors has helped to keep things simple: by the time we both understand a chapter, it is usually transparent. Therefore this book can be used both by the beginner and by the expert, as an introductory textbook and as a reference book, and both by the engineer and the mathematician. Of course this has not resulted in a thin book, and so we suggest the following meilus: An elementary first course on coding theory for mathematicians: Ch. 1, Ch. 2 (06 up to Theorem 22), Ch. 3, Ch. 4 (§01-5), Ch. 5 (to Problem 5), Ch. 7 (not 007, 8), Ch. 8 (001-3), Ch. 9 (001, 4), Ch. 12 (§8), Ch. 13 (§§1-3), Ch. 14 (001-3). A second course for mathematicians: Ch. 2 (901-6, 8), Ch. 4 (0P6, 7 and part of 8), Ch. 5 (to Problem 6, and § § 3 , 4 , 5 , 7 ) , Ch. 6 (491-3, 10, omitting the

vi Preface proof of Theorem 331, Ch. 8 (005, 6), Ch. 9 (§§2,3,5), Ch. 10 (001-5,1 I), Ch. 11, Ch. 13 (004,5,9), Ch. 16 (§§1-6), Ch. 17 (47, up to Theorem 3 3 , Ch. 19 (001-3). An elementary first course on coding theory for engineers: Ch. 1, Ch. 3, Ch. 4 (901-5), Ch. 5 (to Problem 3, Ch. 7 (not 07), Ch. 9 (991, 4, 6), Ch. 10 (001, 2, 5, 6, 7, lo), Ch. 13 (001-3, 6, 7), Ch. 14 (001, 2, 4). A second course for engineers: Ch. 2 (001-6), Ch. 8 (001-3, 5, 6), Ch. 9 (402, 3, 5 ) , Ch. 10 (Qll), Ch. 12 (901-3, 8, 9), Ch. 16 (001, 2,4, 6,9), Ch. 17 (07, up to Theorem 35). There is then a lot of rich food left for an advanced course: the rest of Chapters 2, 6, 11 and 14, followed by Chapters 15, 18, 19, 20 and 21 - a feast! The following are the principal codes discussed: Alternant, Ch. 12; BCH, Ch. 3, 001, 3; Ch. 7, 06; Ch. 8, 05; Ch. 9; Ch. 21, 98; Chien-Choy generalized BCH, Ch. 12, 07; Concatenated, Ch. 10, 011; Ch. 18, 005, 8; Conference matrix, Ch. 2, 04; Cyclic, Ch. 7, Ch. 8; Delsarte-Goethals, Ch. 15, 95; Difference-set cyclic, Ch. 13, 08; Double circulant and quasi-cyclic, Ch. 16, 006-8; Euclidean and projective geometry, Ch. 13, 08; Goethals generalized Preparata, Ch. 15, 07; Golay (binary), Ch. 2, 06; Ch. 16, 02; Ch. 20; Golay (ternary), Ch. 16, 62; Ch. 20; Goppa, Ch. 12, 003-5; Hadamard, Ch. 2, 03; Hamming, Ch. 1, 97, Ch. 7, 03 and Problem 8; Irreducible or minimal cyclic, Ch. 8, 093, 4; Justesen, Ch. 10, 011; Kerdock, Ch. 2, 08; Ch. 15, 05; Maximal distance separable, Ch. 11; Nordstrom-Robinson, Ch. 2, 08; Ch. 15, 005, 6; Pless symmetry, Ch. 16, 08; Preparata, Ch. 2, 08; Ch. 15, 06; Ch. 18, 67.3; Product, Ch. 18, 002-6; Quadratic residue, Ch. 16; Redundant residue, Ch. 10, $9; Reed-Muller, Ch. 1, 09; Chs. 13-15; Reed-Solomon, Ch. 10;

Preface vii Self-dual, Ch. 19; Single-error-correcting nonlinear, Ch. 2 , 07; Ch. 18, 07.3; Srivastava, Ch. 12, 06. Encoding methods are given for: Linear codes, Ch. I , 02; Cyclic codes, Ch. 7, $8; Reed-Solomon codes, Ch. 10, 07; Reed-Muller codes, Ch. 13, 006, 7; Ch. 14, 04. Decoding methods are given for: Linear codes, Ch. 1, 093, 4; Hamming codes, Ch. 1, 47; BCH codes, Ch. 3, 03; Ch. 9, 06; Ch. 12, 09; Reed-Solomon codes, Ch. 10, 010; Alternant (including BCH, Goppa, Srivastava and Chien-Choy generalized BCH codes) Ch. 12, 09; Quadratic residue codes, Ch. 16, 09; Cyclic codes, Ch. 16, 09, while other decoding methods are mentioned in the notes to Ch. 16. When reading the book, keep in mind this piece of advice, which should be given in every preface: if you get stuck on a section, skip it, but keep reading! Don’t hesitate to skip the proof of a theorem: we often do. Starred sections are difficult or dull, and can be omitted on the first (or even second) reading. The book ends with an extensive bibliography. Because coding theory overlaps with so many other subjects (computers, digital systems, group theory, number theory, the design of experiments, etc.) relevant papers may be found almost anywhere in the scientific literature. Unfortunately this means that the usual indexing and reviewing journals are not always helpful. We have therefore felt an obligation to give a fairly comprehensive bi- bliography. The notes at the ends of the chapters give sources for the theorems, problems and tables, as well as small bibliographies for some of the topics covered (or not covered) in the chapter. Only block codes for correcting random errors are discussed; we say little about codes for correcting other kinds of errors (bursts or transpositions) or about variable length codes, convolutional codes or source codes (see the

Viii Preface Notes to Ch. 1). Furthermore we have often considered only binary codes, which makes the theory a lot simpler. Most writers take the opposite point of view: they think in binary but publish their results over arbitrary fields. There are a few topics which were includeh in the original plan for the book but have been reluctantly omitted for reasons of space: (i) Gray codes and snake-in-the-box codes-see Adelson et al. [5,61, Buchner [210], Cavior [253], Chien et al. [290], Cohn [299], Danzer and Klee 13281, Davies [335], Douglas [382,383], Even [413], Flores [432], Gardner [468], Gilbert [481], Guy [571], Harper [605], Klee [764-7671, Mecklenberg et al. [951], Mills [956], Preparata and Nievergelt [1083], Singleton [1215], Tang and Liu [1307], Vasil’ev [1367], Wyner [1440] and Yuen [1448,1449]. (ii) Comma-free codes - see Ball and Cummings [60,61], Baumert and Cantor [85], Crick et al. [316], Eastman [399], Golomb [523, pp. 118-1221, Golomb et al. [528], Hall [587, pp. 11-12], Jiggs [692], Miyakawa and Moriya [967], Niho [992] and Redinbo and Walcott [1102]. See also the remarks on codes for synchronizing in the Notes to Ch. 1. (iii) Codes with unequal error protection - see Gore and Kilgus [549], Kilgus and Gore [761] and Mandelbaum [901]. (iv) Coding for channels with feedback - see Berlekamp [124], Horstein [664] and Schalkwijk et al. [1153-11551. (v) Codes for the Gaussian channel-see Biglieri et al. [148-1511, Blake [l55, 156, 1581, Blake and Mullin 11621, Chadwick et al. 1256,2571, Gallager [464], Ingemarsson [683], Landau [791], Ottoson [1017], Shannon [1191], Slepian [ 1221-12231 and Zetterberg [1456]. (vi) The complexity of decoding - see Bajoga and Walbesser [59], Chaitin [257a-258a], Gelfand et a]. [471], Groth [564], Justesen [706], Kolmogorov [774a], Marguinaud [916], Martin-Lof [917a], Pinsker [ 1046a1, Sarwate [I 1451 and Savage [ 1149-1 152al. (vii) The connections between coding theory and the packing of equal spheres in n-dimensional Euclidean space - see Leech [803-8051, [807], Leech and Sloane [808-810] and Sloane [1226]. The following books and monographs on coding theory are our predeces- sors: Berlekamp [113,116], Blake and Mullin [162], Cameron and Van Lint [234], Golomb [522], Lin [834], Van Lint [848], Massey [922a], Peterson [1036a], Peterson and Weldon [1040], Solomon [1251] and Sloane [ 1227al; while the following collections contain some of the papers in the bibliography: Berlekamp [126], Blake [157], the special issues [377a, 678,6791, Hartnett [620], Mann [909] and Slepian [1224]. See also the bibliography [1022]. We owe a considerable debt to several friends who read the first draft very carefully, made numerous corrections and improvements, and frequently saved us from dreadful blunders. In particular we should like to thank I.F. Blake, P. Delsarte, J.-M. Goethals, R.L. Graham, J.H. van Lint, G. Longo, C.L. Mallows, J. McKay, V. Pless, H.O. Pollak, L.D. Rudolph, D.W. Sar- wate, many other colleagues at Bell Labs, and especially A.M. Odlyzko for

Preface ix their help. Not all of their suggestions have been followed, however, and the authors are fully responsible for the remaining errors. (This conventional remark is to be taken seriously.) We should also like to thank all the typists at Bell Labs who have helped with the book at various times, our secretary Peggy van Ness who has helped in countless ways, and above all Marion Messersmith who has typed and retyped most of the chapters. Sam Lomonaco has very kindly helped us check the galley proofs.

资料库

The.Theory.of.Error-Correcting.Codes.pdf

相关推荐

安全技术

热门标签

最新资料