Error Detecting Codes General Theory And Their Application in Feedba
Error detecting codes are very popular for error control in practical systems for two reasons. First, such codes can be used to provide any desired reliability of communication over any noisy channel. Second, implementation is usually much simpler than fo
- PDF / 16,246,138 Bytes
- 257 Pages / 439.37 x 666.142 pts Page_size
- 93 Downloads / 340 Views
ERROR DETECTING CODES General Theory And Their Application In Feedback Communication Systems
Torleiv KL0VE Department of Informatics, University of Bergen Bergen, Norway
•
Valery I. KORZHIK St. Petersburg University of Telecommunications St. Petersburg, Russia
SPRINGER SCIENCE+BUSINESS MEDIA, LLC
ISBN 978-1-4613-5976-0
ISBN 978-1-4615-2309-3 (eBook)
DOI 10.1007/978-1-4615-2309-3
Library of Congress Cataloging-in-Publication Data A C.I.P. Catalogue record for this book is available from the Library of Congress.
Copyright © 1995 by Springer Science+Business Media New York Originally published by Kluwer Academic Publishers, New York in 1995 Softcover reprint of the hardcover 1st edition 1995 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, mechanical, photo-copying, recording, or otherwise, without the prior written permission of the publisher, Springer Science+Business Media, LLC
Printed on acid-free paper.
To Marit and Marina
CONTENTS
PREFACE 1
CHANNEL MODELS 1.1 Introduction 1.2 Channels Without Memory 1.3 Channels With Memory 1.4 Channel Transforms 1.5 Comments and References
2
BASICS ON ERROR CONTROL 2.1 2.2 2.3 2.4 2.5
3
ABC on Linear Codes Weight Distributions Principles of Error Detection Combined Correction and Detection Comments and References
ERROR DETECTING CODES FOR THE BSC 3.1 3.2 3.3 3.4 3.5 3.6 3.7 3.8 3.9 3.10
Basic Formulas and Bounds Finding the Average The Worst-Case Error Probability Pue for a Linear Code and its Dual General Bounds Optimal Codes New Codes from Old Combined Correction and Detection Complexity of Computing Pue(C,p) Particular Codes
xi
1 1 2 3 13 16 17 17 28 37 42 43 45 45 56 65 72 74 85 91 98 103 104
viii
ERROR DETECTING CODES
3.10.1 Perfect Codes 3.10.2 Reed-Muller Codes 3.10.3 BCH Codes 3.10.4 MDS and Almost MDS codes 3.10.5 Cyclic Codes 3.10.6 Cyclic Redundancy Check (CRC) Codes 3.10.7 Z4-linear Codes 3.10.8 Some Other Classes of Codes 3.11 How to Find the Code You Need 3.12 Comments and References
4
CODES FOR OTHER CHANNELS 4.1 4.2 4.3 4.4
5
PROTOCOLS 5.1 5.2 5.3 5.4 5.5 5.6 5.7
6
Introduction. The Main Criteria of FS Efficiency Basic Protocols for Decision Feedback Systems Protocols With Information Feedback Conclusions Appendix: Signal Flow Graphs for Protocol Analysis Comments and References
CODE OPTIMIZATION 6.1 6.2 6.3 6.4 6.5 6.6
7
The Z-channel Channels With Memory Conclusions Comments and References
Basic Criteria for Optimization Channels Without Memory Channels With Memory Iterative and Concatenated Codes Optimization of Protocols Comments and References
CONCLUDING REMARKS
104 106 107 108 109 109 113 114 115 118 121 121 122 138 140 143 143 145 150 190 192 195 201 203 203 204 211 217 221 224 227
Contents
IX
REFERENCES
229
INDEX
245
PREFACE
There are two basic methods of error control for communication, both involve coding of the messages. The differences lay in the way the codes are utilized. The codes used are block codes, whi
Data Loading...
