Coding Theory  Algorithms, Architectures, and Applications
Andre Neubauer, Jurgen Freudenberger, Volker Kuhn
Coding Theory: Algorithms, Architectures and Applications provides a concise overview of channel coding theory and practice, as well as the accompanying signal processing architectures. The book is unique in presenting algorithms, architectures, and applications of coding theory in a unified framework. It covers the basics of coding theory before moving on to discuss algebraic linear block and cyclic codes, turbo codes and low density parity check codes and spacetime codes. Coding Theory provides algorithms and architectures used for implementing coding and decoding strategies as well as coding schemes used in practice especially in communication systems.
Feature of the book include:
 Unique presentationlike style for summarising main aspects
 Practical issues for implementation of coding techniques
 Sound theoretical approach to practical, relevant coding methodologies
 Covers standard coding schemes such as block and convolutional codes, coding schemes such as Turbo and LDPC codes, and space time codes currently in research, all covered in a common framework with respect to their applications.
This book is ideal for postgraduate and undergraduate students of communication and information engineering, as well as computer science students. It will also be of use to engineers working in the industry who want to know more about the theoretical basics of coding theory and their application in currently relevant communication systems
 Open in Browser
 Checking other formats...
 Convert to EPUB
 Convert to FB2
 Convert to MOBI
 Convert to TXT
 Convert to RTF
 Converted file can differ from the original. If possible, download the file in its original format.
 Please login to your account first

Need help? Please read our short guide how to send a book to Kindle
Please note: you need to verify every book you want to send to your Kindle. Check your mailbox for the verification email from Amazon Kindle.
You may be interested in Powered by Rec2Me
Most frequently terms
Ada Yg Bahasa indonesia Nya Gak
@bistcse Well now you can convert many pdf into epub and an epib of this book is also available. Just self help yourself and try hard to find
that epub.
@ridwan I have no words to comment on him
@nice guy Well this guys use "nice" word many times and I wonder if he really is nice.


Coding Theory Coding Theory Algorithms, Architectures, and Applications André Neubauer Münster University of Applied Sciences, Germany Jürgen Freudenberger HTWG Konstanz, University of Applied Sciences, Germany Volker Kühn University of Rostock, Germany Copyright 2007 John Wiley & Sons Ltd, The Atrium, Southern Gate, Chichester, West Sussex PO19 8SQ, England Telephone (+44) 1243 779777 Email (for orders and customer service enquiries): csbooks@wiley.co.uk Visit our Home Page on www.wileyeurope.com or www.wiley.com 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, scanning or otherwise, except under the terms of the Copyright, Designs and Patents Act 1988 or under the terms of a licence issued by the Copyright Licensing Agency Ltd, 90 Tottenham Court Road, London W1T 4LP, UK, without the permission in writing of the Publisher. Requests to the Publisher should be addressed to the Permissions Department, John Wiley & Sons Ltd, The Atrium, Southern Gate, Chichester, West Sussex PO19 8SQ, England, or emailed to permreq@wiley.co.uk, or faxed to (+44) 1243 770620. Designations used by companies to distinguish their products are often claimed as trademarks. All brand names and product names used in this book are trade names, service marks, trademarks or registered trademarks of their respective owners. The Publisher is not associated with any product or vendor mentioned in this book. All trademarks referred to in the text of this publication are the property of their respective owners. This publication is designed to provide accurate and authoritative information in regard to the subject matter covered. It is sold on the understanding that the Publisher is not engaged in rendering professional services. If professional advice or other expert assistance is required, the services of a competent professional should be sought. Other Wiley Editorial Ofﬁces J; ohn Wiley & Sons Inc., 111 River Street, Hoboken, NJ 07030, USA JosseyBass, 989 Market Street, San Francisco, CA 941031741, USA WileyVCH Verlag GmbH, Boschstr. 12, D69469 Weinheim, Germany John Wiley & Sons Australia Ltd, 42 McDougall Street, Milton, Queensland 4064, Australia John Wiley & Sons (Asia) Pte Ltd, 2 Clementi Loop #0201, Jin Xing Distripark, Singapore 129809 John Wiley & Sons Canada Ltd, 6045 Freemont Blvd, Mississauga, Ontario, L5R 4J3, Canada Wiley also publishes its books in a variety of electronic formats. Some content that appears in print may not be available in electronic books. Anniversary Logo Design: Richard J. Paciﬁco Library of Congress CataloginginPublication Data Neubauer, Andre. Coding theory : algorithms, architectures and applications / Andre Neubauer, Jürgen Freudenberger, Volker Kühn. p. cm. ISBN 9780470028612 (cloth) 1. Coding theory. I Freudenberger, Jrgen. II. Kühn, Volker. III. Title QA268.N48 2007 003 .54–dc22 British Library Cataloguing in Publication Data A catalogue record for this book is available from the British Library ISBN 9780470028612 (HB) Typeset in 10/12pt Times by Laserwords Private Limited, Chennai, India Printed and bound in Great Britain by Antony Rowe Ltd, Chippenham, Wiltshire This book is printed on acidfree paper responsibly manufactured from sustainable forestry in which at least two trees are planted for each one used for paper production. Contents Preface 1 Introduction 1.1 Communication Systems . . . . . . 1.2 Information Theory . . . . . . . . . 1.2.1 Entropy . . . . . . . . . . . 1.2.2 Channel Capacity . . . . . . 1.2.3 Binary Symmetric Channel 1.2.4 AWGN Channel . . . . . . 1.3 A Simple Channel Code . . . . . . ix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1 3 3 4 5 6 8 2 Algebraic Coding Theory 2.1 Fundamentals of Block Codes . . . . . . . . 2.1.1 Code Parameters . . . . . . . . . . . 2.1.2 Maximum Likelihood Decoding . . . 2.1.3 Binary Symmetric Channel . . . . . 2.1.4 Error Detection and Error Correction 2.2 Linear Block Codes . . . . . . . . . . . . . . 2.2.1 Deﬁnition of Linear Block Codes . . 2.2.2 Generator Matrix . . . . . . . . . . . 2.2.3 ParityCheck Matrix . . . . . . . . . 2.2.4 Syndrome and Cosets . . . . . . . . 2.2.5 Dual Code . . . . . . . . . . . . . . 2.2.6 Bounds for Linear Block Codes . . . 2.2.7 Code Constructions . . . . . . . . . 2.2.8 Examples of Linear Block Codes . . 2.3 Cyclic Codes . . . . . . . . . . . . . . . . . 2.3.1 Deﬁnition of Cyclic Codes . . . . . 2.3.2 Generator Polynomial . . . . . . . . 2.3.3 ParityCheck Polynomial . . . . . . . 2.3.4 Dual Codes . . . . . . . . . . . . . . 2.3.5 Linear Feedback Shift Registers . . . 2.3.6 BCH Codes . . . . . . . . . . . . . . 2.3.7 Reed–Solomon Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 14 16 19 23 25 27 27 27 30 31 36 37 41 46 62 62 63 67 70 71 74 81 . . . . . . . . . . . . . . . . . . . . . . . . . . . . vi CONTENTS 2.4 2.3.8 Algebraic Decoding Algorithm . . . . . . . . . . . . . . . . . . . . 84 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 3 Convolutional Codes 3.1 Encoding of Convolutional Codes . . . . . . . . . 3.1.1 Convolutional Encoder . . . . . . . . . . . 3.1.2 Generator Matrix in the Time Domain . . 3.1.3 State Diagram of a Convolutional Encoder 3.1.4 Code Termination . . . . . . . . . . . . . 3.1.5 Puncturing . . . . . . . . . . . . . . . . . 3.1.6 Generator Matrix in the DDomain . . . . 3.1.7 Encoder Properties . . . . . . . . . . . . . 3.2 Trellis Diagram and the Viterbi Algorithm . . . . 3.2.1 Minimum Distance Decoding . . . . . . . 3.2.2 Trellises . . . . . . . . . . . . . . . . . . . 3.2.3 Viterbi Algorithm . . . . . . . . . . . . . 3.3 Distance Properties and Error Bounds . . . . . . . 3.3.1 Free Distance . . . . . . . . . . . . . . . . 3.3.2 Active Distances . . . . . . . . . . . . . . 3.3.3 Weight Enumerators for Terminated Codes 3.3.4 Path Enumerators . . . . . . . . . . . . . . 3.3.5 Pairwise Error Probability . . . . . . . . . 3.3.6 Viterbi Bound . . . . . . . . . . . . . . . 3.4 Softinput Decoding . . . . . . . . . . . . . . . . 3.4.1 Euclidean Metric . . . . . . . . . . . . . . 3.4.2 Support of Punctured Codes . . . . . . . . 3.4.3 Implementation Issues . . . . . . . . . . . 3.5 Softoutput Decoding . . . . . . . . . . . . . . . . 3.5.1 Derivation of APP Decoding . . . . . . . 3.5.2 APP Decoding in the Log Domain . . . . 3.6 Convolutional Coding in Mobile Communications 3.6.1 Coding of Speech Data . . . . . . . . . . 3.6.2 Hybrid ARQ . . . . . . . . . . . . . . . . 3.6.3 EGPRS Modulation and Coding . . . . . . 3.6.4 Retransmission Mechanism . . . . . . . . 3.6.5 Link Adaptation . . . . . . . . . . . . . . 3.6.6 Incremental Redundancy . . . . . . . . . . 3.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 98 98 101 103 104 106 108 110 112 113 115 116 121 121 122 126 129 131 134 136 136 137 138 140 141 145 147 147 150 152 155 156 157 160 4 Turbo Codes 4.1 LDPC Codes . . . . . . . . . . . . . . . . . . . . 4.1.1 Codes Based on Sparse Graphs . . . . . . 4.1.2 Decoding for the Binary Erasure Channel 4.1.3 LogLikelihood Algebra . . . . . . . . . . 4.1.4 Belief Propagation . . . . . . . . . . . . . 4.2 A First Encounter with Code Concatenation . . . 4.2.1 Product Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163 165 165 168 169 174 177 177 CONTENTS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180 182 182 183 184 185 186 188 189 191 196 196 197 198 200 202 205 208 212 5 Space–Time Codes 5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.1.1 Digital Modulation Schemes . . . . . . . . . . . . . . 5.1.2 Diversity . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Spatial Channels . . . . . . . . . . . . . . . . . . . . . . . . 5.2.1 Basic Description . . . . . . . . . . . . . . . . . . . . 5.2.2 Spatial Channel Models . . . . . . . . . . . . . . . . 5.2.3 Channel Estimation . . . . . . . . . . . . . . . . . . 5.3 Performance Measures . . . . . . . . . . . . . . . . . . . . . 5.3.1 Channel Capacity . . . . . . . . . . . . . . . . . . . . 5.3.2 Outage Probability and Outage Capacity . . . . . . . 5.3.3 Ergodic Error Probability . . . . . . . . . . . . . . . 5.4 Orthogonal Space–Time Block Codes . . . . . . . . . . . . . 5.4.1 Alamouti’s Scheme . . . . . . . . . . . . . . . . . . . 5.4.2 Extension to More than Two Transmit Antennas . . . 5.4.3 Simulation Results . . . . . . . . . . . . . . . . . . . 5.5 Spatial Multiplexing . . . . . . . . . . . . . . . . . . . . . . 5.5.1 General Concept . . . . . . . . . . . . . . . . . . . . 5.5.2 Iterative APP Preprocessing and Perlayer Decoding . 5.5.3 Linear Multilayer Detection . . . . . . . . . . . . . . 5.5.4 Original BLAST Detection . . . . . . . . . . . . . . 5.5.5 QL Decomposition and Interference Cancellation . . 5.5.6 Performance of MultiLayer Detection Schemes . . . 5.5.7 Uniﬁed Description by Linear Dispersion Codes . . . 5.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215 215 216 223 229 229 234 239 241 241 250 252 257 257 260 263 265 265 267 272 275 278 287 291 294 4.3 4.4 4.5 4.6 4.7 4.2.2 Iterative Decoding of Product Codes Concatenated Convolutional Codes . . . . . 4.3.1 Parallel Concatenation . . . . . . . . 4.3.2 The UMTS Turbo Code . . . . . . . 4.3.3 Serial Concatenation . . . . . . . . . 4.3.4 Partial Concatenation . . . . . . . . . 4.3.5 Turbo Decoding . . . . . . . . . . . EXIT Charts . . . . . . . . . . . . . . . . . 4.4.1 Calculating an EXIT Chart . . . . . 4.4.2 Interpretation . . . . . . . . . . . . . Weight Distribution . . . . . . . . . . . . . . 4.5.1 Partial Weights . . . . . . . . . . . . 4.5.2 Expected Weight Distribution . . . . Woven Convolutional Codes . . . . . . . . . 4.6.1 Encoding Schemes . . . . . . . . . . 4.6.2 Distance Properties of Woven Codes 4.6.3 Woven Turbo Codes . . . . . . . . . 4.6.4 Interleaver Design . . . . . . . . . . Summary . . . . . . . . . . . . . . . . . . . vii . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viii CONTENTS A Algebraic Structures A.1 Groups, Rings and Finite Fields . A.1.1 Groups . . . . . . . . . . A.1.2 Rings . . . . . . . . . . . A.1.3 Finite Fields . . . . . . . A.2 Vector Spaces . . . . . . . . . . . A.3 Polynomials and Extension Fields A.4 Discrete Fourier Transform . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 295 295 295 296 298 299 300 305 B Linear Algebra 311 C Acronyms 319 Bibliography 325 Index 335 Preface Modern information and communication systems are based on the reliable and efﬁcient transmission of information. Channels encountered in practical applications are usually disturbed regardless of whether they correspond to information transmission over noisy and timevariant mobile radio channels or to information transmission on optical discs that might be damaged by scratches. Owing to these disturbances, appropriate channel coding schemes have to be employed such that errors within the transmitted information can be detected or even corrected. To this end, channel coding theory provides suitable coding schemes for error detection and error correction. Besides good code characteristics with respect to the number of errors that can be detected or corrected, the complexity of the architectures used for implementing the encoding and decoding algorithms is important for practical applications. The present book provides a concise overview of channel coding theory and practice as well as the accompanying algorithms, architectures and applications. The selection of the topics presented in this book is oriented towards those subjects that are relevant for information and communication systems in use today or in the near future. The focus is on those aspects of coding theory that are important for the understanding of these systems. This book places emphasis on the algorithms for encoding and decoding and their architectures, as well as the applications of the corresponding coding schemes in a uniﬁed framework. The idea for this book originated from a twoday seminar on coding theory in the industrial context. We have tried to keep this seminar style in the book by highlighting the most important facts within the ﬁgures and by restricting the scope to the most important topics with respect to the applications of coding theory, especially within communication systems. This also means that many important and interesting topics could not be covered in order to be as concise as possible. The target audience for the book are students of communication and information engineering as well as computer science at universities and also applied mathematicians who are interested in a presentation that subsumes theory and practice of coding theory without sacriﬁcing exactness or relevance with regard to realworld practical applications. Therefore, this book is well suited for engineers in industry who want to know about the theoretical basics of coding theory and their application in currently relevant communication systems. The book is organised as follows. In Chapter 1 a brief overview of the principle architecture of a communication system is given and the information theory fundamentals underlying coding theory are summarised. The most important concepts of information theory, such as entropy and channel capacity as well as simple channel models, are described. x PREFACE Chapter 2 presents the classical, i.e. algebraic, coding theory. The fundamentals of the encoding and decoding of block codes are explained, and the maximum likelihood decoding rule is derived as the optimum decoding strategy for minimising the word error probability after decoding a received word. Linear block codes and their deﬁnition based on generator and paritycheck matrices are discussed. General performance measures and bounds relating important code characteristics such as the minimum Hamming distance and the code rate are presented, illustrating the compromises necessary between error detection and error correction capabilities and transmission efﬁciency. It is explained how new codes can be constructed from already known codes. Repetition codes, paritycheckcodes, Hamming codes, simplex codes and Reed–Muller codes are presented as examples. Since the task of decoding linear block codes is difﬁcult in general, the algebraic properties of cyclic codes are exploited for efﬁcient decoding algorithms. These cyclic codes, together with their generator and paritycheck polynomials, are discussed, as well as efﬁcient encoding and decoding architectures based on linear feedback shift registers. Important cyclic codes such as BCH codes and Reed–Solomon codes are presented, and an efﬁcient algebraic decoding algorithm for the decoding of these cyclic codes is derived. Chapter 3 deals with the fundamentals of convolutional coding. Convolutional codes can be found in many applications, for instance in dialup modems, satellite communications and digital cellular systems. The major reason for this popularity is the existence of efﬁcient decoding algorithms that can utilise soft input values from the demodulator. This socalled softinput decoding leads to signiﬁcant performance gains. Two famous examples for a softinput decoding algorithm are the Viterbi algorithm and the Bahl, Cocke, Jelinek, Raviv (BCJR) algorithm which also provides a reliability output. Both algorithms are based on the trellis representation of the convolutional code. This highly repetitive structure makes trellisbased decoding very suitable for hardware implementations. We start our discussion with the encoding of convolutional codes and some of their basic properties. It follows a presentation of the Viterbi algorithm and an analysis of the error correction performance with this maximum likelihood decoding procedure. The concept of softoutput decoding and the BCJR algorithm are considered in Section 3.5. Softoutput decoding is a prerequisite for the iterative decoding of concatenated convolutional codes as introduced in Chapter 4. Finally, we consider an application of convolutional codes for mobile communication channels as deﬁned in the Global System for Mobile communications (GSM) standard. In particular, the considered hybrid ARQ protocols are excellent examples of the adaptive coding systems that are required for strongly timevariant mobile channels. As mentioned above, Chapter 4 is dedicated to the construction of long powerful codes based on the concatenation of simple convolutional component codes. These concatenated convolutional codes, for example the famous turbo codes, are capable of achieving low bit error rates at signaltonoise ratios close to the theoretical Shannon limit. The term turbo reﬂects a property of the employed iterative decoding algorithm, where the decoder output of one iteration is used as the decoder input of the next iteration. This concept of iterative decoding was ﬁrst introduced for the class of lowdensity paritycheck codes. Therefore, we ﬁrst introduce lowdensity paritycheck codes in Section 4.1 and discuss the relation between these codes and concatenated code constructions. Then, we introduce some popular encoding schemes for concatenated convolutional codes and present three methods to analyse the performance of the corresponding codes. The EXIT chart method PREFACE xi in Section 4.4 makes it possible to predict the behaviour of the iterative decoder by looking at the input/output relations of the individual constituent softoutput decoders. Next, we present a common approach in coding theory. We estimate the code performance with maximum likelihood decoding for an ensemble of concatenated codes. This method explains why many concatenated code constructions lead to a low minimum Hamming distance and therefore to a relatively poor performance for high signaltonoise ratios. In Section 4.6 we consider code designs that lead to a higher minimum Hamming distance owing to a special encoder construction, called the woven encoder, or the application of designed interleavers. The ﬁfth chapter addresses space–time coding concepts, a still rather new topic in the area of radio communications. Although these techniques do not represent errorcorrecting codes in the classical sense, they can also be used to improve the reliability of a data link. Since space–time coding became popular only a decade ago, only a few concepts have found their way into current standards hitherto. However, many other approaches are currently being discussed. As already mentioned before, we restrict this book to the most important and promising concepts. While classical encoders and decoders are separated from the physical channel by modulators, equalisers, etc., and experience rather simple hyperchannels, this is not true for space–time coding schemes. They directly work on the physical channel. Therefore, Chapter 5 starts with a short survey of linear modulation schemes and explains the principle of diversity. Next, spatial channel models are described and different performance measures for their quantitative evaluation are discussed. Sections 5.4 and 5.5 introduce two space–time coding concepts with the highest practical relevance, namely orthogonal space–time block codes increasing the diversity degree and spatial multiplexing techniques boosting the achievable data rate. For the latter approach, sophisticated signal processing algorithms are required at the receiver in order to separate superimposed data streams again. In the appendices a brief summary of algebraic structures such as ﬁnite ﬁelds and polynomial rings is given, which are needed for the treatment especially of classical algebraic codes, and the basics of linear algebra are brieﬂy reviewed. Finally, we would like to thank the Wiley team, especially Sarah Hinton as the responsible editor, for their support during the completion of the manuscript. We also thank Dr. rer. nat. Jens Schlembach who was involved from the beginning of this book project and who gave encouragement when needed. Last but not least, we would like to give special thanks to our families – Fabian, Heike, Jana and Erik, Claudia, Hannah and Jakob and Christiane – for their emotional support during the writing of the manuscript. André Neubauer Münster University of Applied Sciences Jürgen Freudenberger HTWG Konstanz University of Applied Sciences Volker Kühn University of Rostock 1 Introduction The reliable transmission of information over noisy channels is one of the basic requirements of digital information and communication systems. Here, transmission is understood both as transmission in space, e.g. over mobile radio channels, and as transmission in time by storing information in appropriate storage media. Because of this requirement, modern communication systems rely heavily on powerful channel coding methodologies. For practical applications these coding schemes do not only need to have good coding characteristics with respect to the capability of detecting or correcting errors introduced on the channel. They also have to be efﬁciently implementable, e.g. in digital hardware within integrated circuits. Practical applications of channel codes include space and satellite communications, data transmission, digital audio and video broadcasting and mobile communications, as well as storage systems such as computer memories or the compact disc (Costello et al., 1998). In this introductory chapter we will give a brief introduction into the ﬁeld of channel coding. To this end, we will describe the information theory fundamentals of channel coding. Simple channel models will be presented that will be used throughout the text. Furthermore, we will present the binary triple repetition code as an illustrative example of a simple channel code. 1.1 Communication Systems In Figure 1.1 the basic structure of a digital communication system is shown which represents the architecture of the communication systems in use today. Within the transmitter of such a communication system the following tasks are carried out: ● source encoding, ● channel encoding, ● modulation. Coding Theory – Algorithms, Architectures, and Applications 2007 John Wiley & Sons, Ltd André Neubauer, Jürgen Freudenberger, Volker Kühn 2 INTRODUCTION Principal structure of digital communication systems source FEC encoder encoder u channel FEC encoder encoder b moduFEC lator encoder FEC channel encoder source FEC decoder encoder û channel FEC decoder encoder r demoFEC dulator encoder ■ The sequence of information symbols u is encoded into the sequence of code symbols b which are transmitted across the channel after modulation. ■ The sequence of received symbols r is decoded into the sequence of information symbols û which are estimates of the originally transmitted information symbols. Figure 1.1: Basic structure of digital communication systems In the receiver the corresponding inverse operations are implemented: ● demodulation, ● channel decoding, ● source decoding. According to Figure 1.1 the modulator generates the signal that is used to transmit the sequence of symbols b across the channel (Benedetto and Biglieri, 1999; Neubauer, 2007; Proakis, 2001). Due to the noisy nature of the channel, the transmitted signal is disturbed. The noisy received signal is demodulated by the demodulator in the receiver, leading to the sequence of received symbols r. Since the received symbol sequence r usually differs from the transmitted symbol sequence b, a channel code is used such that the receiver is able to detect or even correct errors (Bossert, 1999; Lin and Costello, 2004; Neubauer, 2006b). To this end, the channel encoder introduces redundancy into the information sequence u. This redundancy can be exploited by the channel decoder for error detection or error correction by estimating the transmitted symbol sequence û. In his fundamental work, Shannon showed that it is theoretically possible to realise an information transmission system with as small an error probability as required (Shannon, 1948). The prerequisite for this is that the information rate of the information source be smaller than the socalled channel capacity. In order to reduce the information rate, source coding schemes are used which are implemented by the source encoder in the transmitter and the source decoder in the receiver (McEliece, 2002; Neubauer, 2006a). INTRODUCTION 3 Further information about source coding can be found elsewhere (Gibson et al., 1998; Sayood, 2000, 2003). In order better to understand the theoretical basics of information transmission as well as channel coding, we now give a brief overview of information theory as introduced by Shannon in his seminal paper (Shannon, 1948). In this context we will also introduce the simple channel models that will be used throughout the text. 1.2 Information Theory An important result of information theory is the ﬁnding that errorfree transmission across a noisy channel is theoretically possible – as long as the information rate does not exceed the socalled channel capacity. In order to quantify this result, we need to measure information. Within Shannon’s information theory this is done by considering the statistics of symbols emitted by information sources. 1.2.1 Entropy Let us consider the discrete memoryless information source shown in Figure 1.2. At a given time instant, this discrete information source emits the random discrete symbol X = xi which assumes one out of M possible symbol values x1 , x2 , . . . , xM . The rate at which these symbol values appear are given by the probabilities PX (x1 ), PX (x2 ), . . . , PX (xM ) with PX (xi ) = Pr{X = xi }. Discrete information source Information source X ■ The discrete information source emits the random discrete symbol X . ■ The symbol values x1 , x2 , . . . , xM appear with probabilities PX (x1 ), PX (x2 ), . . . , PX (xM ). ■ Entropy I (X ) = − M PX (xi ) · log2 (PX (xi )) i=1 Figure 1.2: Discrete information source emitting discrete symbols X (1.1) 4 INTRODUCTION The average information associated with the random discrete symbol X is given by the socalled entropy measured in the unit ‘bit’ I (X ) = − M PX (xi ) · log2 (PX (xi )) . i=1 For a binary information source that emits the binary symbols X = 0 and X = 1 with probabilities Pr{X = 0} = p0 and Pr{X = 1} = 1 − Pr{X = 0} = 1 − p0 , the entropy is given by the socalled Shannon function or binary entropy function I (X ) = −p0 log2 (p0 ) − (1 − p0 ) log2 (1 − p0 ). 1.2.2 Channel Capacity With the help of the entropy concept we can model a channel according to Berger’s channel diagram shown in Figure 1.3 (Neubauer, 2006a). Here, X refers to the input symbol and R denotes the output symbol or received symbol. We now assume that M input symbol values x1 , x2 , . . . , xM and N output symbol values r1 , r2 , . . . , rN are possible. With the help of the conditional probabilities PX R (xi rj ) = Pr{X = xi R = rj } and PRX (rj xi ) = Pr{R = rj X = xi } the conditional entropies are given by I (X R) = − M N PX ,R (xi , rj ) · log2 PX R (xi rj ) i=1 j =1 and I (RX ) = − N M PX ,R (xi , rj ) · log2 (PRX (rj xi )). i=1 j =1 With these conditional probabilities the mutual information I (X ; R) = I (X ) − I (X R) = I (R) − I (RX ) can be derived which measures the amount of information that is transmitted across the channel from the input to the output for a given information source. The socalled channel capacity C is obtained by maximising the mutual information I (X ; R) with respect to the statistical properties of the input X , i.e. by appropriately choosing the probabilities {PX (xi )}1≤i≤M . This leads to C= max {PX (xi )}1≤i≤M I (X ; R). If the input entropy I (X ) is smaller than the channel capacity C ! I (X ) < C, then information can be transmitted across the noisy channel with arbitrarily small error probability. Thus, the channel capacity C in fact quantiﬁes the information transmission capacity of the channel. INTRODUCTION 5 Berger’s channel diagram I (X R) I (X ) I (X ; R) I (R) I (RX ) ■ Mutual information I (X ; R) = I (X ) − I (X R) = I (R) − I (RX ) ■ (1.2) Channel capacity C= max {PX (xi )}1≤i≤M I (X ; R) (1.3) Figure 1.3: Berger’s channel diagram 1.2.3 Binary Symmetric Channel As an important example of a memoryless channel we turn to the binary symmetric channel or BSC. Figure 1.4 shows the channel diagram of the binary symmetric channel with bit error probability ε. This channel transmits the binary symbol X = 0 or X = 1 correctly with probability 1 − ε, whereas the incorrect binary symbol R = 1 or R = 0 is emitted with probability ε. By maximising the mutual information I (X ; R), the channel capacity of a binary symmetric channel is obtained according to C = 1 + ε log2 (ε) + (1 − ε) log2 (1 − ε). This channel capacity is equal to 1 if ε = 0 or ε = 1; for ε = 12 the channel capacity is 0. In contrast to the binary symmetric channel, which has discrete input and output symbols taken from binary alphabets, the socalled AWGN channel is deﬁned on the basis of continuous realvalued random variables.1 1 In Chapter 5 we will also consider complexvalued random variables. 6 INTRODUCTION Binary symmetric channel 1−ε X =0 ε R=0 ε X =1 1−ε ■ Bit error probability ε ■ Channel capacity R=1 C = 1 + ε log2 (ε) + (1 − ε) log2 (1 − ε) (1.4) Figure 1.4: Binary symmetric channel with bit error probability ε 1.2.4 AWGN Channel Up to now we have exclusively considered discretevalued symbols. The concept of entropy can be transferred to continuous realvalued random variables by introducing the socalled differential entropy. It turns out that a channel with realvalued input and output symbols can again be characterised with the help of the mutual information I (X ; R) and its maximum, the channel capacity C. In Figure 1.5 the socalled AWGN channel is illustrated which is described by the additive white Gaussian noise term Z. With the help of the signal power S = E X2 and the noise power N = E Z2 the channel capacity of the AWGN channel is given by 1 S C = log2 1 + . 2 N The channel capacity exclusively depends on the signaltonoise ratio S/N . In order to compare the channel capacities of the binary symmetric channel and the AWGN channel, we assume a digital transmission scheme using binary phase shift keying (BPSK) and optimal reception with the help of a matched ﬁlter (Benedetto and Biglieri, 1999; Neubauer, 2007; Proakis, 2001). The signaltonoise ratio of the realvalued output INTRODUCTION 7 AWGN channel + X R Z ■ Signaltonoise ratio ■ Channel capacity S N C= 1 S log2 1 + 2 N (1.5) Figure 1.5: AWGN channel with signaltonoise ratio S/N R of the matched ﬁlter is then given by S Eb = N N0 /2 with bit energy Eb and noise power spectral density N0 . If the output R of the matched ﬁlter is compared with the threshold 0, we obtain the binary symmetric channel with bit error probability Eb 1 ε = erfc . 2 N0 Here, erfc(·) denotes the complementary error function. In Figure 1.6 the channel capacities of the binary symmetric channel and the AWGN channel are compared as a function of Eb /N0 . The signaltonoise ratio S/N or the ratio Eb /N0 must be higher for the binary symmetric channel compared with the AWGN channel in order to achieve the same channel capacity. This gain also translates to the coding gain achievable by softdecision decoding as opposed to harddecision decoding of channel codes, as we will see later (e.g. in Section 2.2.8). Although information theory tells us that it is theoretically possible to ﬁnd a channel code that for a given channel leads to as small an error probability as required, the design of good channel codes is generally difﬁcult. Therefore, in the next chapters several classes of channel codes will be described. Here, we start with a simple example. 8 INTRODUCTION Channel capacity of BSC vs AWGN channel 1.5 C 1 0.5 AWGN BSC 0 Ŧ5 Ŧ4 Ŧ3 Ŧ2 Ŧ1 0 10 log10 ■ 1 2 3 4 5 Eb N0 Signaltonoise ratio of AWGN channel Eb S = N N0 /2 ■ (1.6) Bit error probability of binary symmetric channel 1 ε = erfc 2 Eb N0 (1.7) Figure 1.6: Channel capacity of the binary symmetric channel vs the channel capacity of the AWGN channel 1.3 A Simple Channel Code As an introductory example of a simple channel code we consider the transmission of the binary information sequence 00101110 over a binary symmetric channel with bit error probability ε = 0.25 (Neubauer, 2006b). On average, every fourth binary symbol will be received incorrectly. In this example we assume that the binary sequence 00000110 is received at the output of the binary symmetric channel (see Figure 1.7). INTRODUCTION 9 Channel transmission BSC 00101110 00000110 ■ Binary symmetric channel with bit error probability ε = 0.25 ■ Transmission w/o channel code Figure 1.7: Channel transmission without channel code Encoder Encoder 00101110 ■ Binary information symbols 0 and 1 ■ Binary code words 000 and 111 ■ Binary triple repetition code {000, 111} 000000111000111111111000 Figure 1.8: Encoder of a triple repetition code In order to implement a simple error correction scheme we make use of the socalled binary triple repetition code. This simple channel code is used for the encoding of binary data. If the binary symbol 0 is to be transmitted, the encoder emits the code word 000. Alternatively, the code word 111 is issued by the encoder when the binary symbol 1 is to be transmitted. The encoder of a triple repetition code is illustrated in Figure 1.8. For the binary information sequence given above we obtain the binary code sequence 000 000 111 000 111 111 111 000 at the output of the encoder. If we again assume that on average every fourth binary symbol is incorrectly transmitted by the binary symmetric channel, we may obtain the received sequence 010 000 011 010 111 010 111 010. This is illustrated in Figure 1.9. 10 INTRODUCTION Channel transmission 000000111000111111111000 BSC 010000011010111010111010 ■ Binary symmetric channel with bit error probability ε = 0.25 ■ Transmission with binary triple repetition code Figure 1.9: Channel transmission of a binary triple repetition code Decoder 010000011010111010111010 ■ Decoder 00101010 Decoding of triple repetition code by majority decision 000 → 000 001 → 000 010 → 000 011 → 111 .. . 110 → 111 111 → 111 Figure 1.10: Decoder of a triple repetition code The decoder in Figure 1.10 tries to estimate the original information sequence with the help of a majority decision. If the number of 0s within a received 3bit word is larger than the number of 1s, the decoder emits the binary symbol 0; otherwise a 1 is decoded. With this decoding algorithm we obtain the decoded information sequence 0 0 1 0 1 0 1 0. INTRODUCTION 11 As can be seen from this example, the binary triple repetition code is able to correct a single error within a code word. More errors cannot be corrected. With the help of this simple channel code we are able to reduce the number of errors. Compared with the unprotected transmission without a channel code, the number of errors has been reduced from two to one. However, this is achieved by a signiﬁcant reduction in the transmission bandwidth because, for a given symbol rate on the channel, it takes 3 times longer to transmit an information symbol with the help of the triple repetition code. It is one of the main topics of the following chapters to present more efﬁcient coding schemes. 2 Algebraic Coding Theory In this chapter we will introduce the basic concepts of algebraic coding theory. To this end, the fundamental properties of block codes are ﬁrst discussed. We will deﬁne important code parameters and describe how these codes can be used for the purpose of error detection and error correction. The optimal maximum likelihood decoding strategy will be derived and applied to the binary symmetric channel. With these fundamentals at hand we will then introduce linear block codes. These channel codes can be generated with the help of socalled generator matrices owing to their special algebraic properties. Based on the closely related paritycheck matrix and the syndrome, the decoding of linear block codes can be carried out. We will also introduce dual codes and several techniques for the construction of new block codes based on known ones, as well as bounds for the respective code parameters and the accompanying code characteristics. As examples of linear block codes we will treat the repetition code, paritycheck code, Hamming code, simplex code and Reed–Muller code. Although code generation can be carried out efﬁciently for linear block codes, the decoding problem for general linear block codes is difﬁcult to solve. By introducing further algebraic structures, cyclic codes can be derived as a subclass of linear block codes for which efﬁcient algebraic decoding algorithms exist. Similar to general linear block codes, which are deﬁned using the generator matrix or the paritycheck matrix, cyclic codes are deﬁned with the help of the socalled generator polynomial or paritycheck polynomial. Based on linear feedback shift registers, the respective encoding and decoding architectures for cyclic codes can be efﬁciently implemented. As important examples of cyclic codes we will discuss BCH codes and Reed–Solomon codes. Furthermore, an algebraic decoding algorithm is presented that can be used for the decoding of BCH and Reed–Solomon codes. In this chapter the classical algebraic coding theory is presented. In particular, we will follow work (Berlekamp, 1984; Bossert, 1999; Hamming, 1986; Jungnickel, 1995; Lin and Costello, 2004; Ling and Xing, 2004; MacWilliams and Sloane, 1998; McEliece, 2002; Neubauer, 2006b; van Lint, 1999) that contains further details about algebraic coding theory. Coding Theory – Algorithms, Architectures, and Applications 2007 John Wiley & Sons, Ltd André Neubauer, Jürgen Freudenberger, Volker Kühn 14 ALGEBRAIC CODING THEORY 2.1 Fundamentals of Block Codes In Section 1.3, the binary triple repetition code was given as an introductory example of a simple channel code. This speciﬁc channel code consists of two code words 000 and 111 of length n = 3, which represent k = 1 binary information symbol 0 or 1 respectively. Each symbol of a binary information sequence is encoded separately. The respective code word of length 3 is then transmitted across the channel. The potentially erroneously received word is ﬁnally decoded into a valid code word 000 or 111 – or equivalently into the respective information symbol 0 or 1. As we have seen, this simple code is merely able to correct one error by transmitting three code symbols instead of just one information symbol across the channel. In order to generalise this simple channel coding scheme and to come up with more efﬁcient and powerful channel codes, we now consider an information sequence u0 u1 u2 u3 u4 u5 u6 u7 . . . of discrete information symbols ui . This information sequence is grouped into blocks of length k according to u0 u1 · · · uk−1 uk uk+1 · · · u2k−1 u2k u2k+1 · · · u3k−1 · · · . block block block In socalled qnary (n, k) block codes the information words u0 u1 · · · uk−1 , uk uk+1 · · · u2k−1 , u2k u2k+1 · · · u3k−1 , .. . of length k with ui ∈ {0, 1, . . . , q − 1} are encoded separately from each other into the corresponding code words b0 b1 · · · bn−1 , bn bn+1 · · · b2n−1 , b2n b2n+1 · · · b3n−1 , .. . of length n with bi ∈ {0, 1, . . . , q − 1} (see Figure 2.1).1 These code words are transmitted across the channel and the received words are appropriately decoded, as shown in Figure 2.2. In the following, we will write the information word u0 u1 · · · uk−1 and the code word b0 b1 · · · bn−1 as vectors u = (u0 , u1 , . . . , uk−1 ) and b = (b0 , b1 , . . . , bn−1 ) respectively. Accordingly, the received word is denoted by r = (r0 , r1 , . . . , rn−1 ), whereas 1 For q = 2 we obtain the important class of binary channel codes. ALGEBRAIC CODING THEORY 15 Encoding of an (n, k) block code (u0 , u1 , . . . , uk−1 ) Encoder (b0 , b1 , . . . , bn−1 ) ■ The sequence of information symbols is grouped into words (or blocks) of equal length k which are independently encoded. ■ Each information word (u0 , u1 , . . . , uk−1 ) of length k is uniquely mapped onto a code word (b0 , b1 , . . . , bn−1 ) of length n. Figure 2.1: Encoding of an (n, k) block code Decoding of an (n, k) block code (r0 , r1 , . . . , rn−1 ) ■ Decoder (b̂0 , b̂1 , . . . , b̂n−1 ) The received word (r0 , r1 , . . . , rn−1 ) of length n at the output of the channel is decoded into the code word (b̂0 , b̂1 , . . . , b̂n−1 ) of length n or the information word û = (û0 , û1 , . . . , ûk−1 ) of length k respectively. Figure 2.2: Decoding of an (n, k) block code the decoded code word and decoded information word are given by b̂ = (b̂0 , b̂1 , . . . , b̂n−1 ) and û = (û0 , û1 , . . . , ûk−1 ) respectively. In general, we obtain the transmission scheme for an (n, k) block code as shown in Figure 2.3. Without further algebraic properties of the (n, k) block code, the encoding can be carried out by a table lookup procedure. The information word u to be encoded is used to address a table that for each information word u contains the corresponding code word b at the respective address. If each information symbol can assume one out of q possible values, 16 ALGEBRAIC CODING THEORY Encoding, transmission and decoding of an (n, k) block code ■ Information word u = (u0 , u1 , . . . , uk−1 ) of length k ■ Code word b = (b0 , b1 , . . . , bn−1 ) of length n ■ Received word r = (r0 , r1 , . . . , rn−1 ) of length n ■ Decoded code word b̂ = (b̂0 , b̂1 , . . . , b̂n−1 ) of length n ■ Decoded information word û = (û0 , û1 , . . . , ûk−1 ) of length k r b u Encoder Channel Decoder b̂ ■ The information word u is encoded into the code word b. ■ The code word b is transmitted across the channel which emits the received word r. ■ Based on the received word r, the code word b̂ (or equivalently the information word û) is decoded. Figure 2.3: Encoding, transmission and decoding of an (n, k) block code the number of code words is given by q k . Since each entry carries n qnary symbols, the total size of the table is n q k . The size of the table grows exponentially with increasing information word length k. For codes with a large number of code words – corresponding to a large information word length k – a coding scheme based on a table lookup procedure is inefﬁcient owing to the large memory size needed. For that reason, further algebraic properties are introduced in order to allow for a more efﬁcient encoder architecture of an (n, k) block code. This is the idea lying behind the socalled linear block codes, which we will encounter in Section 2.2. 2.1.1 Code Parameters Channel codes are characterised by socalled code parameters. The most important code parameters of a general (n, k) block code that are introduced in the following are the code rate and the minimum Hamming distance (Bossert, 1999; Lin and Costello, 2004; Ling and Xing, 2004). With the help of these code parameters, the efﬁciency of the encoding process and the error detection and error correction capabilities can be evaluated for a given (n, k) block code. ALGEBRAIC CODING THEORY 17 Code Rate Under the assumption that each information symbol ui of the (n, k) block code can assume q values, the number of possible information words and code words is given by2 M = qk. Since the code word length n is larger than the information word length k, the rate at which information is transmitted across the channel is reduced by the socalled code rate R= logq (M) n = k . n For the simple binary triple repetition code with k = 1 and n = 3, the code rate is R = k 1 n = 3 ≈ 0,3333. Weight and Hamming Distance Each code word b = (b0 , b1 , . . . , bn−1 ) can be assigned the weight wt(b) which is deﬁned as the number of nonzero components bi = 0 (Bossert, 1999), i.e.3 wt(b) = {i : bi = 0, 0 ≤ i < n} . Accordingly, the distance between two code words b = (b0 , b1 , . . . , bn−1 ) and b = (b0 , ) is given by the socalled Hamming distance (Bossert, 1999) b1 , . . . , bn−1 dist(b, b ) = i : bi = bi , 0 ≤ i < n . The Hamming distance dist(b, b ) provides the number of different components of b and b and thus measures how close the code words b and b are to each other. For a code B consisting of M code words b1 , b2 , . . . , bM , the minimum Hamming distance is given by d = min dist(b, b ). ∀b=b We will denote the (n, k) block code B = {b1 , b2 , . . . , bM } with M = q k qnary code words of length n and minimum Hamming distance d by B(n, k, d). The minimum weight of the block code B is deﬁned as min wt(b). The code parameters of B(n, k, d) are summarised ∀b=0 in Figure 2.4. Weight Distribution The socalled weight distribution W (x) of an (n, k) block code B = {b1 , b2 , . . . , bM } describes how many code words exist with a speciﬁc weight. Denoting the number of code words with weight i by wi = {b ∈ B : wt(b) = i} 2 In view of the linear block codes introduced in the following, we assume here that all possible information words u = (u0 , u1 , . . . , uk−1 ) are encoded. 3 B denotes the cardinality of the set B. 18 ALGEBRAIC CODING THEORY Code parameters of (n, k) block codes B(n, k, d) ■ Code rate R= ■ k n Minimum weight min wt(b) (2.2) d = min dist(b, b ) (2.3) ∀b=0 ■ (2.1) Minimum Hamming distance ∀b=b Figure 2.4: Code parameters of (n, k) block codes B(n, k, d) with 0 ≤ i ≤ n and 0 ≤ wi ≤ M, the weight distribution is deﬁned by the polynomial (Bossert, 1999) n wi x i . W (x) = i=0 The minimum weight of the block code B can then be obtained from the weight distribution according to min wt(b) = min wi . ∀b=0 i>0 Code Space A qnary block code B(n, k, d) with code word length n can be illustrated as a subset of the socalled code space Fnq . Such a code space is a graphical illustration of all possible qnary words or vectors.4 The total number of vectors of length n with weight w and qnary components is given by n n! (q − 1)w = (q − 1)w w w! (n − w)! with the binomial coefﬁcients n n! . = w! (n − w)! w The total number of vectors within Fnq is then obtained from n n (q − 1)w = q n . Fnq  = w w=0 4 In Section 2.2 we will identify the code space with the ﬁnite vector space Fn . For a brief overview of q algebraic structures such as ﬁnite ﬁelds and vector spaces the reader is referred to Appendix A. ALGEBRAIC CODING THEORY 19 Fourdimensional binary code space F42 4 0000 0 4 1 4 2 4 3 4 4 1100 1000 0010 0100 0001 0101 0110 0011 1010 1001 1110 1101 0111 1011 wt = 0 wt = 1 wt = 2 wt = 3 wt = 4 1111 ■ The fourdimensional binary code space F42 consists of 24 = 16 binary vectors of length 4. Figure 2.5: Fourdimensional binary code space F42 . Reproduced by permission of J. Schlembach Fachverlag The fourdimensional binary code space F42 with q = 2 and n = 4 is illustrated in Figure 2.5 (Neubauer, 2006b). 2.1.2 Maximum Likelihood Decoding Channel codes are used in order to decrease the probability of incorrectly received code words or symbols. In this section we will derive a widely used decoding strategy. To this end, we will consider a decoding strategy to be optimal if the corresponding word error probability perr = Pr{û = u} = Pr{b̂ = b} is minimal (Bossert, 1999). The word error probability has to be distinguished from the symbol error probability k−1 1 psym = Pr{ûi = ui } k i=0 20 ALGEBRAIC CODING THEORY Optimal decoder r ■ Decoder b̂(r) The received word r is decoded into the code word b̂(r) such that the word error probability (2.4) perr = Pr{û = u} = Pr{b̂ = b} is minimal. Figure 2.6: Optimal decoder with minimal word error probability which denotes the probability of an incorrectly decoded information symbol ui . In general, the symbol error probability is harder to derive analytically than the word error probability. However, it can be bounded by the following inequality (Bossert, 1999) 1 perr ≤ psym ≤ perr . k In the following, a qnary channel code B ∈ Fnq with M code words b1 , b2 , . . . , bM in the code space Fnq is considered. Let bj be the transmitted code word. Owing to the noisy channel, the received word r may differ from the transmitted code word bj . The task of the decoder in Figure 2.6 is to decode the transmitted code word based on the sole knowledge of r with minimal word error probability perr . This decoding step can be written according to the decoding rule r → b̂ = b̂(r). For harddecision decoding the received word r is an element of the discrete code space F nq . To each code word bj we assign a corresponding subspace Dj of the code space Fnq , the socalled decision nonoverlapping decision regions create the whole code region. These n and D ∩ D = ∅ for i = j as illustrated in Figure 2.7. If D = F space Fnq , i.e. M i j q j =1 j the received word r lies within the decision region Di , the decoder decides in favour of the code word bi . That is, the decoding of the code word bi according to the decision rule b̂(r) = bi is equivalent to the event r ∈ Di . By properly choosing the decision regions Di , the decoder can be designed. For an optimal decoder the decision regions are chosen such that the word error probability perr is minimal. The probability of the event that the code word b = bj is transmitted and the code word b̂(r) = bi is decoded is given by Pr{(b̂(r) = bi ) ∧ (b = bj )} = Pr{(r ∈ Di ) ∧ (b = bj )}. We obtain the word error probability perr by averaging over all possible events for which the transmitted code word b = bj is decoded into a different code word b̂(r) = bi with ALGEBRAIC CODING THEORY 21 Decision regions Fnq D1 Di ... Dj DM ■ Decision regions Dj with M j =1 Dj = Fnq and Di ∩ Dj = ∅ for i = j Figure 2.7: Nonoverlapping decision regions Dj in the code space Fnq i = j . This leads to (Neubauer, 2006b) perr = Pr{b̂(r) = b} = M Pr{(b̂(r) = bi ) ∧ (b = bj )} i=1 j =i = M Pr{(r ∈ Di ) ∧ (b = bj )} i=1 j =i = M Pr{r ∧ (b = bj )}. i=1 j =i r∈Di With the help of Bayes’ rule Pr{r ∧ (b = bj )} = Pr{b = bj r} Pr{r} and by changing the order of summation, we obtain perr = M Pr{r ∧ (b = bj )} i=1 r∈Di j =i = M i=1 r∈Di j =i Pr{b = bj r} Pr{r} 22 ALGEBRAIC CODING THEORY = M Pr{r} Pr{b = bj r}. j =i i=1 r∈Di The inner sum can be simpliﬁed by observing the normalisation condition M Pr{b = bj r} = Pr{b = bi r} + Pr{b = bj r} = 1. j =i j =1 This leads to the word error probability perr = M Pr{r} (1 − Pr{b = bi r}) . i=1 r∈Di In order to minimise the word error probability perr , we deﬁne the decision regions Di by assigning each possible received word r to one particular decision region. If r is assigned to the particular decision region Di for which the inner term Pr{r} (1 − Pr{b = bi r}) is smallest, the word error probability perr will be minimal. Therefore, the decision regions are obtained from the following assignment r ∈ Dj ⇔ Pr{r} 1 − Pr{b = bj r} = min Pr{r} (1 − Pr{b = bi r}) . 1≤i≤M Since the probability Pr{r} does not change with index i, this is equivalent to r ∈ Dj ⇔ Pr{b = bj r} = max Pr{b = bi r}. 1≤i≤M Finally, we obtain the optimal decoding rule according to b̂(r) = bj ⇔ Pr{b = bj r} = max Pr{b = bi r}. 1≤i≤M The optimal decoder with minimal word error probability perr emits the code word b̂ = b̂(r) for which the aposteriori probability Pr{b = bi r} = Pr{bi r} is maximal. This decoding strategy b̂(r) = argmax Pr{br} b∈B is called MED (minimum error probability decoding) or MAP (maximum aposteriori) decoding (Bossert, 1999). For this MAP decoding strategy the aposteriori probabilities Pr{br} have to be determined for all code words b ∈ B and received words r. With the help of Bayes’ rule Pr{br} = Pr{rb} Pr{b} Pr{r} and by omitting the term Pr{r} which does not depend on the speciﬁc code word b, the decoding rule b̂(r) = argmax Pr{rb} Pr{b} b∈B ALGEBRAIC CODING THEORY 23 Optimal decoding strategies r ■ Decoder b̂(r) For Minimum Error Probability Decoding (MED) or Maximum APosteriori (MAP) decoding the decoder rule is b̂(r) = argmax Pr{br} (2.5) b∈B ■ For Maximum Likelihood Decoding (MLD) the decoder rule is b̂(r) = argmax Pr{rb} (2.6) b∈B ■ MLD is identical to MED if all code words are equally likely, i.e. Pr{b} = 1 M. Figure 2.8: Optimal decoding strategies follows. For MAP decoding, the conditional probabilities Pr{rb} as well as the apriori probabilities Pr{b} have to be known. If all M code words b appear with equal probability Pr{b} = 1/M, we obtain the socalled MLD (maximum likelihood decoding) strategy (Bossert, 1999) b̂(r) = argmax Pr{rb}. b∈B These decoding strategies are summarised in Figure 2.8. In the following, we will assume that all code words are equally likely, so that maximum likelihood decoding can be used as the optimal decoding rule. In order to apply the maximum likelihood decoding rule, the conditional probabilities Pr{rb} must be available. We illustrate how this decoding rule can be further simpliﬁed by considering the binary symmetric channel. 2.1.3 Binary Symmetric Channel In Section 1.2.3 we deﬁned the binary symmetric channel as a memoryless channel with the conditional probabilities 1 − ε, ri = bi Pr{ri bi } = ε, ri = bi with channel bit error probability ε. Since the binary symmetric channel is assumed to be memoryless, the conditional probability Pr{rb} can be calculated for code word b = 24 ALGEBRAIC CODING THEORY (b0 , b1 , . . . , bn−1 ) and received word r = (r0 , r1 , . . . , rn−1 ) according to Pr{rb} = n−1 Pr{ri bi }. i=0 If the words r and b differ in dist(r, b) symbols, this yields n−dist(r,b) Pr{rb} = (1 − ε) Taking into account 0 ≤ ε < 1 2 εdist(r,b) = (1 − ε)n ε 1−ε and therefore b̂(r) = argmax Pr{rb} = argmax (1 − ε) b∈B n b∈B dist(r,b) ε . 1−ε < 1, the MLD rule is given by dist(r,b) ε = argmin dist(r, b), 1−ε b∈B i.e. for the binary symmetric channel the optimal maximum likelihood decoder (Bossert, 1999) b̂(r) = argmin dist(r, b) b∈B emits that particular code word which differs in the smallest number of components from the received word r, i.e. which has the smallest Hamming distance to the received word r (see Figure 2.9). This decoding rule is called minimum distance decoding. This minimum distance decoding rule is also optimal for a qnary symmetric channel (Neubauer, 2006b). We now turn to the error probabilities for the binary symmetric channel during transmission before decoding. The probability of w errors at w given positions within the ndimensional binary received word r is given by ε w (1 − ε)n−w . Since there are wn different possibilities Minimum distance decoding for the binary symmetric channel r ■ Decoder b̂(r) The optimal maximum likelihood decoding rule for the binary symmetric channel is given by the minimum distance decoding rule b̂(r) = argmin dist(r, b) b∈B Figure 2.9: Minimum distance decoding for the binary symmetric channel (2.7) ALGEBRAIC CODING THEORY 25 of choosing w out of n positions, the probability of w errors at arbitrary positions within an ndimensional binary received word follows the binomial distribution n w Pr{w errors} = ε (1 − ε)n−w w with mean n ε. Because of the condition ε < 12 , the probability Pr{w errors} decreases with increasing number of errors w, i.e. few errors are more likely than many errors. The probability of errorfree transmission is Pr{0 errors} = (1 − ε)n , whereas the probability of a disturbed transmission with r = b is given by Pr{r = b} = n n w=1 w εw (1 − ε)n−w = 1 − (1 − ε)n . 2.1.4 Error Detection and Error Correction Based on the minimum distance decoding rule and the code space concept, we can assess the error detection and error correction capabilities of a given channel code. To this end, let b and b be two code words of an (n, k) block code B(n, k, d). The distance of these code words shall be equal to the minimum Hamming distance, i.e. dist(b, b ) = d. We are able to detect errors as long as the erroneously received word r is not equal to a code word different from the transmitted code word. This error detection capability is guaranteed as long as the number of errors is smaller than the minimum Hamming distance d, because another code word (e.g. b ) can be reached from a given code word (e.g. b) merely by changing at least d components. For an (n, k) block code B(n, k, d) with minimum Hamming distance d, the number of detectable errors is therefore given by (Bossert, 1999; Lin and Costello, 2004; Ling and Xing, 2004; van Lint, 1999) edet = d − 1. For the analysis of the error correction capabilities of the (n, k) block code B(n, k, d) we deﬁne for each code word b the corresponding correction ball of radius as the subset of all words that are closer to the code word b than to any other code word b of the block code B(n, k, d) (see Figure 2.10). As we have seen in the last section, for minimum distance decoding, all received words within a particular correction ball are decoded into the respective code word b. According to the radius of the correction balls, besides the code word b, all words that differ in 1, 2, . . . , components from b are elements of the corresponding correction ball. We can uniquely decode all elements of a correction ball into the corresponding code word b as long as the correction balls do not intersect. This condition is true if < d2 holds. Therefore, the number of correctable errors of a block code B(n, k, d) with minimum Hamming distance d is given by (Bossert, 1999; Lin and Costello, 2004; Ling and Xing, 2004; van Lint, 1999)5 d −1 . ecor = 2 5 The term z denotes the largest integer number that is not larger than z. 26 ALGEBRAIC CODING THEORY Error detection and error correction correction balls b b d ■ If the minimum Hamming distance between two arbitrary code words is d the code is able to detect up to edet = d − 1 (2.8) errors. ■ If the minimum Hamming distance between two arbitrary code words is d the code is able to correct up to d −1 ecor = (2.9) 2 errors. Figure 2.10: Error detection and error correction For the binary symmetric channel the number of errors w within the ndimensional transmitted code word is binomially distributed according to Pr{w errors} = wn εw (1 − ε)n−w . Since an edet error detecting code is able to detect w ≤ edet = d − 1 errors, the remaining detection error probability is bounded by pdet ≤ n w=edet +1 edet n w n w n−w ε (1 − ε) ε (1 − ε)n−w . =1− w w w=0 If an ecor error correcting code is used with ecor = (d − 1)/2, the word error probability for a binary symmetric channel can be similarly bounded by perr ≤ n w=ecor +1 ecor n w n w ε (1 − ε)n−w = 1 − ε (1 − ε)n−w . w w w=0 ALGEBRAIC CODING THEORY 27 2.2 Linear Block Codes In the foregoing discussion of the fundamentals of general block codes we exclusively focused on the distance properties between code words and received words in the code space Fnq . If we consider the code words to be vectors in the ﬁnite vector space Fnq , taking into account the respective algebraic properties of vector spaces, we gain efﬁciency especially with regard to the encoding scheme.6 2.2.1 Deﬁnition of Linear Block Codes The (n, k) block code B(n, k, d) with minimum Hamming distance d over the ﬁnite ﬁeld Fq is called linear, if B(n, k, d) is a subspace of the vector space F nq of dimension k (Lin and Costello, 2004; Ling and Xing, 2004). The number of code words is then given by M = qk according to the code rate k . n Because of the linearity property, an arbitrary superposition of code words again leads to a valid code word of the linear block code B(n, k, d), i.e. R= α2 b1 + α2 b2 + · · · + αl bl ∈ B(n, k, d) with α1 , α2 , . . . , αl ∈ Fq and b1 , b2 , . . . , bl ∈ B(n, k, d). Owing to the linearity, the ndimensional zero row vector 0 = (0, 0, . . . , 0) consisting of n zeros is always a valid code word. It can be shown that the minimum Hamming distance of a linear block code B(n, k, d) is equal to the minimum weight of all nonzero code words, i.e. d = min dist(b, b ) = min wt(b). ∀b=b ∀b=0 These properties are summarised in Figure 2.11. As a simple example of a linear block code, the binary paritycheck code is described in Figure 2.12 (Bossert, 1999). For each linear block code an equivalent code can be found by rearranging the code word symbols.7 This equivalent code is characterised by the same code parameters as the original code, i.e. the equivalent code has the same dimension k and the same minimum Hamming distance d. 2.2.2 Generator Matrix The linearity property of a linear block code B(n, k, d) can be exploited for efﬁciently encoding a given information word u = (u0 , u1 , . . . , uk−1 ). To this end, a basis {g0 , g1 , . . . , gk−1 } of the subspace spanned by the linear block code is chosen, consisting of k linearly independent ndimensional vectors gi = (gi,0 , gi,1 , · · · , gi,n−1 ) 6 Finite ﬁelds and vector spaces are brieﬂy reviewed in Sections A.1 and A.2 in Appendix A. general, an equivalent code is obtained by suitable operations on the rows and columns of the generator matrix G which is deﬁned in Section 2.2.2. 7 In 28 ALGEBRAIC CODING THEORY Linear block codes ■ A linear qnary (n, k) block code B(n, k, d) is deﬁned as a subspace of the vector space Fnq . ■ The number of code words is given by M = q k . ■ The minimum Hamming distance d is given by the minimum weight min wt(b) = d. ∀b=0 Figure 2.11: Linear block codes B(n, k, d) Binary paritycheck code ■ The binary paritycheck code is a linear block code over the ﬁnite ﬁeld F2 . ■ This code takes a kdimensional information word u = (u0 , u1 , . . . , uk−1 ) and generates the code word b = (b0 , b1 , . . . , bk−1 , bk ) with bi = ui for 0 ≤ i ≤ k − 1 and bk = u0 + u1 + · · · + uk−1 = k−1 ui (2.10) i=0 ■ The bit bk is called the parity bit; it is chosen such that the resulting code word is of even parity. Figure 2.12: Binary paritycheck code with 0 ≤ i ≤ k − 1. The corresponding code word b = (b0 , b1 , . . . , bn−1 ) is then given by b = u0 g0 + u1 g1 + · · · + uk−1 gk−1 with the qnary information symbols ui ∈ Fq . If we deﬁne the k × n matrix g0,1 · · · g0,n−1 g0 g0,0 g1 g1,0 g1,1 · · · g1,n−1 G= . = . . .. .. .. .. .. . . gk−1 gk−1,0 gk−1,1 · · · gk−1,n−1 ALGEBRAIC CODING THEORY 29 Generator matrix ■ The generator matrix G of a linear block code is constructed by a suitable set of k linearly independent basis vectors gi according to g0,1 · · · g0,n−1 g0 g0,0 g1 g1,0 g1,1 · · · g1,n−1 G= . = (2.11) . . .. .. .. .. .. . . gk−1 gk−1,0 gk−1,1 · · · gk−1,n−1 ■ The kdimensional information word u is encoded into the ndimensional code word b by the encoding rule b = uG (2.12) Figure 2.13: Generator matrix G of a linear block code B(n, k, d) the information word u = (u0 , u1 , . . . , uk−1 ) is encoded according to the matrix–vector multiplication b = u G. Since all M = q k code words b ∈ B(n, k, d) can be generated by this rule, the matrix G is called the generator matrix of the linear block code B(n, k, d) (see Figure 2.13). Owing to this property, the linear block code B(n, k, d) is completely deﬁned with the help of the generator matrix G (Bossert, 1999; Lin and Costello, 2004; Ling and Xing, 2004). In Figure 2.14 the socalled binary (7, 4) Hamming code is deﬁned by the given generator matrix G. Such a binary Hamming code has been deﬁned by Hamming (Hamming, 1950). These codes or variants of them are used, e.g. in memories such as dynamic random access memories (DRAMs), in order to correct deteriorated data in memory cells. For each linear block code B(n, k, d) an equivalent linear block code can be found that is deﬁned by the k × n generator matrix G = Ik Ak,n−k . Owing to the k × k identity matrix Ik and the encoding rule b = u G = u u Ak,n−k the ﬁrst k code symbols bi are identical to the k information symbols ui . Such an encoding scheme is called systematic. The remaining m = n − k symbols within the vector u Ak,n−k correspond to m paritycheck symbols which are attached to the information vector u for the purpose of error detection or error correction. 30 ALGEBRAIC CODING THEORY Generator matrix of a binary Hamming code ■ The generator matrix G of a binary (7,4) Hamming code is given by 1 0 0 0 0 1 1 0 1 0 0 1 0 1 G= 0 0 1 0 1 1 0 0 0 0 1 1 1 1 ■ The code parameters of this binary Hamming code are n = 7, k = 4 and d = 3, i.e. this code is a binary B(7, 4, 3) code. ■ The information word u = (0, 0, 1, 1) is encoded into the code word 1 0 0 0 0 1 1 0 1 0 0 1 0 1 b = (0, 0, 1, 1) 0 0 1 0 1 1 0 = (0, 0, 1, 1, 0, 0, 1) 0 0 0 1 1 1 1 Figure 2.14: Generator matrix of a binary (7, 4) Hamming code 2.2.3 ParityCheck Matrix With the help of the generator matrix G = (Ik Ak,n−k ), the following (n − k) × n matrix – the socalled paritycheck matrix – can be deﬁned (Bossert, 1999; Lin and Costello, 2004; Ling and Xing, 2004) H = Bn−k,k In−k with the (n − k) × (n − k) identity matrix In−k . The (n − k) × k matrix Bn−k,k is given by Bn−k,k = −ATk,n−k . For the matrices G and H the following property can be derived H GT = Bn−k,k + ATk,n−k = 0n−k,k with the (n − k) × k zero matrix 0n−k,k . The generator matrix G and the paritycheck matrix H are orthogonal, i.e. all row vectors of G are orthogonal to all row vectors of H. Using the ndimensional basis vectors g0 , g1 , . . . , gk−1 and the transpose of the generator matrix GT = gT0 , gT1 , . . . , gTk−1 , we obtain H GT = H gT0 , gT1 , . . . , gTk−1 = H gT0 , H gT1 , . . . , H gTk−1 = (0, 0, . . . , 0) with the (n − k)dimensional allzero column vector 0 = (0, 0, . . . , 0)T . This is equivalent to H gTi = 0 for 0 ≤ i ≤ k − 1. Since each code vector b ∈ B(n, k, d) can be written as b = u G = u0 g0 + u1 g1 + · · · + uk−1 gk−1 ALGEBRAIC CODING THEORY 31 Paritycheck matrix ■ The paritycheck H of a linear block code B(n, k, d) with generator matrix matrix G = Ik Ak,n−k is deﬁned by H = −ATk,n−k In−k (2.13) ■ Generator matrix G and paritycheck matrix H are orthogonal H GT = 0n−k,k ■ (2.14) The system of paritycheck equations is given by H rT = 0 ⇔ r ∈ B(n, k, d) (2.15) Figure 2.15: Paritycheck matrix H of a linear block code B(n, k, d) with the information vector u = (u0 , u1 , . . . , uk−1 ), it follows that H bT = u0 H gT0 + u1 H gT1 + · · · + uk−1 H gTk−1 = 0. Each code vector b ∈ B(n, k, d) of a linear (n, k) block code B(n, k, d) fulﬁls the condition H bT = 0. Equivalently, if H rT = 0, the vector r does not belong to the linear block code B(n, k, d). We arrive at the following paritycheck condition H rT = 0 ⇔ r ∈ B(n, k, d) which amounts to a total of n − k paritycheck equations. Therefore, the matrix H is called the paritycheck matrix of the linear (n, k) block code B(n, k, d) (see Figure 2.15). There exists an interesting relationship between the minimum Hamming distance d and the paritycheck matrix H which is stated in Figure 2.16 (Lin and Costello, 2004). In Figure 2.17 the paritycheck matrix of the binary Hamming code with the generator matrix given in Figure 2.14 is shown. The corresponding paritycheck equations of this binary Hamming code are illustrated in Figure 2.18. 2.2.4 Syndrome and Cosets As we have seen in the last section, a vector r corresponds to a valid code word of a given linear block code B(n, k, d) with paritycheck matrix H if and only if the paritycheck equation H rT = 0 is true. Otherwise, r is not a valid code word of B(n, k, d). Based on 32 ALGEBRAIC CODING THEORY Paritycheck matrix and minimum Hamming distance ■ Let H be the paritycheck matrix of a linear block code B(n, k, d) with minimum Hamming distance d. ■ The minimum Hamming distance d is equal to the smallest number of linearly dependent columns of the paritycheck matrix H. Figure 2.16: Paritycheck matrix H and minimum Hamming distance d of a linear block code B(n, k, d) Paritycheck matrix of a binary Hamming code ■ The paritycheck matrix H of a binary (7,4) Hamming code is given by 0 1 1 1 1 0 0 H= 1 0 1 1 0 1 0 1 1 0 1 0 0 1 It consists of all nonzero binary column vectors of length 3. ■ Two arbitrary columns are linearly independent. However, the ﬁrst three columns are linearly dependent. The minimum Hamming distance of a binary Hamming code is d = 3. ■ The code word b = (0, 0, 1, 1, 0, 0, 1) fulﬁls the paritycheck equation 0 0 1 0 1 1 1 1 0 0 0 = 0 1 H bT = 1 0 1 1 0 1 0 0 1 1 0 1 0 0 1 0 0 1 Figure 2.17: Paritycheck matrix H of a binary Hamming code ALGEBRAIC CODING THEORY 33 Graphical representation of the paritycheck equations + b0 ■ b1 + b2 + b3 b4 b5 b6 The paritycheck equations of a binary (7,4) Hamming code with code word b = (b0 , b1 , b2 , b3 , b4 , b5 , b6 ) are given by b1 + b2 + b3 + b4 = 0 b0 + b2 + b3 + b5 = 0 b0 + b1 + b3 + b6 = 0 Figure 2.18: Graphical representation of the paritycheck equations of a binary (7, 4) Hamming code B(7, 4, 3) the algebraic channel model shown in Figure 2.19, we interpret r as the received vector which is obtained from r=b+e with the transmitted code vector b and the error vector e. The j th component of the error vector e is ej = 0 if no error has occurred at this particular position; otherwise the j th component is ej = 0. In view of the paritycheck equation, we deﬁne the socalled syndrome (Lin and Costello, 2004; Ling and Xing, 2004) s T = H rT which is used to check whether the received vector r belongs to the channel code B(n, k, d). Inserting the received vector r into this deﬁnition, we obtain sT = H rT = H (b + e)T = H bT + H eT = H eT . =0 Here, we have taken into account that for each code vector b ∈ B(n, k, d) the condition H bT = 0 holds. Finally, we recognize that the syndrome does exclusively depend on the error vector e, i.e. s T = H eT . 34 ALGEBRAIC CODING THEORY Algebraic channel model + b r e ■ The transmitted ndimensional code vector b is disturbed by the ndimensional error vector e. ■ The received vector r is given by r=b+e ■ (2.16) The syndrome s T = H rT exclusively depends on the error vector e according to (2.17) sT = H eT . Figure 2.19: Algebraic channel model Thus, for the purpose of error detection the syndrome can be evaluated. If s is zero, the received vector r is equal to a valid code vector, i.e. r ∈ B(n, k, d). In this case no error can be detected and it is assumed that the received vector corresponds to the transmitted code vector. If e is zero, the received vector r = b delivers the transmitted code vector b. However, all nonzero error vectors e that fulﬁl the condition H eT = 0 also lead to a valid code word.8 These errors cannot be detected. In general, the (n − k)dimensional syndrome sT = H eT of a linear (n, k) block code B(n, k, d) corresponds to n − k scalar equations for the determination of the ndimensional error vector e. The matrix equation s T = H eT does not uniquely deﬁne the error vector e. All vectors e with H eT = sT form a set, the socalled coset of the kdimensional subspace B(n, k, d) in the ﬁnite vector space Fnq . This coset has q k elements. For an errorcorrecting qnary block code B(n, k, d) and a given 8 This property directly follows from the linearity of the block code B(n, k, d). ALGEBRAIC CODING THEORY 35 syndrome s, the decoder has to choose one out of these q k possible error vectors. As we have seen for the binary symmetric channel, it is often the case that few errors are more likely than many errors. An optimal decoder implementing the minimum distance decoding rule therefore chooses the error vector out of the coset that has the smallest number of nonzero components. This error vector is called the coset leader (Lin and Costello, 2004; Ling and Xing, 2004). The decoding of the linear block code B(n, k, d) can be carried out by a table lookup procedure as illustrated in Figure 2.20. The (n − k)dimensional syndrome s is used to address a table that for each particular syndrome contains the corresponding ndimensional coset leader e at the respective address. Since there are q n−k syndromes and each entry carries n qnary symbols, the total size of the table is n q n−k . The size of the table grows exponentially with n − k. For codes with large n − k, a decoding scheme based on a table lookup procedure is inefﬁcient.9 By introducing further algebraic properties, more efﬁcient Syndrome decoding Syndrome Calculation r ■ s Table Lookup ê  + b̂ + The syndrome is calculated with the help of the received vector r and the paritycheck matrix H according to s T = H rT (2.18) ■ The syndrome s is used to address a table that for each syndrome stores the respective coset leader as the decoded error vector ê. ■ By subtracting the decoded error vector ê from the received vector r, the decoded code word b̂ is obtained b̂ = r − ê (2.19) Figure 2.20: Syndrome decoding of a linear block code B(n, k, d) with a table lookup procedure. Reproduced by permission of J. Schlembach Fachverlag 9 It can be shown that in general the decoding of a linear block code is NPcomplete. 36 ALGEBRAIC CODING THEORY decoder architectures can be deﬁned. This will be apparent in the context of cyclic codes in Section 2.3. 2.2.5 Dual Code So far we have described two equivalent ways to deﬁne a linear block code B(n, k, d) based on the k × n generator matrix G and the (n − k) × n paritycheck matrix H. By simply exchanging these matrices, we can deﬁne a new linear block code B ⊥ (n , k , d ) with generator matrix G⊥ = H and paritycheck matrix H⊥ = G as shown in Figure 2.21. Because of the orthogonality condition H GT = 0, each n = ndimensional code word b⊥ of B⊥ (n , k , d ) is orthogonal to every code word b of B(n, k, d), i.e. b⊥ bT = 0. The resulting code B⊥ (n , k , d ) is called the dual code or orthogonal code, (Bossert, 1999; Lin and Costello, 2004; Ling and Xing, 2004; van Lint, 1999). Whereas the original code B(n, k, d) with M = q k code words has dimension k, the dimension of the dual code is k = n − k. Therefore, it includes M ⊥ = q n−k code words, leading to M M ⊥ = q n = Fnq . By again exchanging the generator matrix and the paritycheck matrix, we end up with the original code. Formally, this means that the dual of the dual code is the original code ⊥ ⊥ B (n , k , d ) = B(n, k, d). A linear block code B(n, k, d) that fulﬁls B⊥ (n , k , d ) = B(n, k, d) is called selfdual. Dual code and MacWilliams identity ■ The dual code B⊥ (n , k , d ) of a linear qnary block code B(n, k, d) with paritycheck matrix H is deﬁned by the generator matrix G⊥ = H ■ (2.20) The weight distribution W ⊥ (x) of the qnary dual code B⊥ (n , k , d ) follows from the MacWilliams identity 1−x (2.21) W ⊥ (x) = q −k (1 + (q − 1) x)n W 1 + (q − 1) x Figure 2.21: Dual code B⊥ (n , k , d ) and MacWilliams identity ALGEBRAIC CODING THEORY 37 Because of the close relationship between B(n, k, d) and its dual B⊥ (n , k , d ), we can derive the properties of the dual code B⊥ (n , k , d ) from the properties of the original code B(n, k, d). In particular, the MacWilliams identity holds for the corresponding weight distributions W ⊥ (x) and W (x) (Bossert, 1999; Lin and Costello, 2004; Ling and Xing, 2004; MacWilliams and Sloane, 1998). The MacWilliams identity states that 1−x ⊥ −k n W (x) = q (1 + (q − 1) x) W . 1 + (q − 1) x For linear binary block codes with q = 2 we obtain W ⊥ (x) = 2−k (1 + x)n W 1−x 1+x . The MacWilliams identity can, for example, be used to determine the minimum Hamming distance d of the dual code B⊥ (n , k , d ) on the basis of the known weight distribution of the original code B(n, k, d). 2.2.6 Bounds for Linear Block Codes The code rate R = k/n and the minimum Hamming distance d are important parameters of a linear block code B(n, k, d). It is therefore useful to know whether a linear block code theoretically exists for a given combination of R and d. In particular, for a given minimum Hamming distance d we will consider a linear block code to be better than another linear block code with the same minimum Hamming distance d if it has a higher code rate R. There exist several theoretical bounds which we will brieﬂy discuss in the following (Berlekamp, 1984; Bossert, 1999; Ling and Xing, 2004; van Lint, 1999) (see also Figure 2.22). Block codes that fulﬁl a theoretical bound with equality are called optimal codes. Singleton Bound The simplest bound is the socalled Singleton bound. For a linear block code B(n, k, d) it is given by k ≤ n − d + 1. A linear block code that fulﬁls the Singleton bound with equality according to k = n − d + 1 is called MDS (maximum distance separable). Important representatives of MDS codes are Reed–Solomon codes which are used, for example, in the channel coding scheme within the audio compact disc (see also Section 2.3.7). Sphere Packing Bound The socalled sphere packing bound or Hamming bound can be derived for a linear ecor = (d − 1)/2error correcting qnary block code B(n, k, d) by considering the correction balls within the code space Fnq . Each correction ball encompasses a total of ecor n i=0 i (q − 1)i 38 ALGEBRAIC CODING THEORY Bounds for linear block codes B(n, k, d) ■ ■ Singleton bound k ≤n−d +1 Hamming bound ecor n i=0 (q − 1)i ≤ q n−k i (2.22) (2.23) with ecor = (d − 1)/2 ■ Plotkin bound qk ≤ for d > θ n with θ = 1 − ■ (2.24) (q − 1)i < q n−k (2.25) 1 q Gilbert–Varshamov bound d−2 n−1 i i=0 ■ d d −θn Griesmer bound n≥ k−1 d i=0 qi (2.26) Figure 2.22: Bounds for linear qnary block codes B(n, k, d) vectors in the code space Fnq . Since there is exactly one correction ball for each code word, we have M = q k correction balls. The total number of vectors within any correction ball of radius ecor is then given by qk ecor n i i=0 (q − 1)i . Because this number must be smaller than or equal to the maximum number Fnq  = q n of vectors in the ﬁnite vector space Fnq , the sphere packing bound qk ecor n i=0 i (q − 1)i ≤ q n ALGEBRAIC CODING THEORY 39 follows. For binary block codes with q = 2 we obtain ecor n ≤ 2n−k . i i=0 A socalled perfect code fulﬁls the sphere packing bound with equality, i.e. ecor n (q − 1)i = q n−k . i i=0 Perfect codes exploit the complete code space; every vector in the code space F nq is part of one and only one correction ball and can therefore uniquely be assigned to a particular code word. For perfect binary codes with q = 2 which are capable of correcting ecor = 1 error we obtain 1 + n = 2n−k . Figure 2.23 shows the parameters of perfect singleerror correcting binary block codes up to length 1023. Plotkin Bound Under the assumption that d > θ n with θ= 1 q −1 =1− q q Perfect binary block codes ■ The following table shows the parameters of perfect singleerror correcting binary block codes B(n, k, d) with minimum Hamming distance d = 3. n k m 3 7 15 31 63 127 255 511 1023 1 4 11 26 57 120 247 502 1013 2 3 4 5 6 7 8 9 10 Figure 2.23: Code word length n, information word length k and number of parity bits m = n − k of a perfect singleerror correcting code 40 ALGEBRAIC CODING THEORY the Plotkin bound states that qk ≤ d . d −θn For binary block codes with q = 2 and θ = 2k ≤ 2−1 2 = 1 2 we obtain 2d 2d − n for 2 d > n. The code words of a code that fulﬁls the Plotkin bound with equality all have the same distance d. Such codes are called equidistant. Gilbert–Varshamov Bound By making use of the fact that the minimal number of linearly dependent columns in the paritycheck matrix is equal to the minimum Hamming distance, the Gilbert–Varshamov bound can be derived for a linear block code B(n, k, d). If d−2 n−1 i=0 i (q − 1)i < q n−k is fulﬁlled, it is possible to construct a linear qnary block code B(n, k, d) with code rate R = k/n and minimum Hamming distance d. Griesmer Bound The Griesmer bound yields a lower bound for the code word length n of a linear qnary block code B(n, k, d) according to10 n≥ k−1 d i=0 qi d d =d+ . + ··· + q q k−1 Asymptotic Bounds For codes with very large code word lengths n, asymptotic bounds are useful which are obtained for n → ∞. These bounds relate the code rate R= k n and the relative minimum Hamming distance δ= d . n In Figure 2.24 some asymptotic bounds are given for linear binary block codes with q = 2 (Bossert, 1999). 10 The term z denotes the smallest integer number that is not smaller than z. ALGEBRAIC CODING THEORY 41 Asymptotic bounds for linear binary block codes 1 0.9 0.8 R = k/n 0.7 Singleton 0.6 0.5 0.4 0.3 0.2 GilbertŦ Varshamov Plotkin Hamming 0.1 0 0 ■ 0.1 0.2 0.3 0.4 0.5 0.6 0.7 δ = d/n 0.8 0.9 1 Asymptotic Singleton bound R 1−δ ■ Asymptotic Hamming bound δ R 1 + log2 2 ■ δ δ δ + 1− log2 1 − 2 2 2 (2.28) Asymptotic Plotkin bound R ■ (2.27) 1 − 2 δ, 0 ≤ δ ≤ 0, 1 2 1 2 <δ≤1 (2.29) Gilbert–Varshamov bound (with 0 ≤ δ ≤ 12 ) R 1 + δ log2 (δ) + (1 − δ) log2 (1 − δ) (2.30) Figure 2.24: Asymptotic bounds for linear binary block codes B(n, k, d) 2.2.7 Code Constructions In this section we turn to the question of how new block codes can be generated on the basis of known block codes. We will consider the code constructions shown in Figure 2.25 (Berlekamp, 1984; Bossert, 1999; Lin and Costello, 2004; Ling and Xing, 2004). Some of these code constructions will reappear in later chapters (e.g. code puncturing for convolutional codes in Chapter 3 and code interleaving for Turbo codes in Chapter 4). 42 ALGEBRAIC CODING THEORY Code constructions for linear block codes ■ ■ ■ ■ ■ Code shortening Code puncturing Code extension Code interleaving n = n − 1, k = k − 1, d = d (2.31) n = n − 1, k = k, d ≤ d (2.32) n = n + 1, k = k, d ≥ d (2.33) n = n t, k = k t, d = d (2.34) Plotkin’s (uv) code construction n = 2 max{n1 , n2 }, k = k1 + k2 , d = min{2 d1 , d2 } (2.35) Figure 2.25: Code constructions for linear block codes and their respective code parameters Code Shortening Based on a linear block code B(n, k, d) with code word length n, information word length k and minimum Hamming distance d, we can create a new code by considering all code words b = (b0 , b1 , . . . , bn−1 ) with bj = 0. The socalled shortened code is then given by B (n , k , d ) = (b0 , . . . , bj −1 , bj +1 , . . . , bn−1 ) : (b0 , . . . , bj −1 , bj , bj +1 , . . . , bn−1 ) ∈ B(n, k, d) ∧ bj = 0 . This shortened code B (n , k , d ) is characterised by the following code parameters11 n = n − 1, k = k − 1, d = d. If B(n, k, d) is an MDS code, then the code B (n , k , d ) is also maximum distance separable because the Singleton bound is still fulﬁlled with equality: d = n − k + 1 = (n − 1) − (k − 1) + 1 = n − k + 1 = d . 11 We exclude the trivial case where all code words b ∈ B(n, k, d) have a zero at the j th position. ALGEBRAIC CODING THEORY 43 Code Puncturing Starting from the systematic linear block code B(n, k, d) with code word length n, information word length k and minimum Hamming distance d, the socalled punctured code is obtained by eliminating the j th code position bj of a code word b = (b0 , b1 , . . . , bn−1 ) ∈ B(n, k, d) irrespective of its value. Here, we assume that bj is a paritycheck symbol. The resulting code consists of the code words b = (b0 , . . . , bj −1 , bj +1 , . . . , bn−1 ). The punctured code B (n , k , d ) = (b0 , . . . , bj −1 , bj +1 , . . . , bn−1 ) : (b0 , . . . , bj −1 , bj , bj +1 , . . . , bn−1 ) ∈ B(n, k, d) ∧ bj is paritycheck symbol is characterised by the following code parameters n = n − 1, k = k, d ≤ d. Code Extension The socalled extension of a linear block code B(n, k, d) with code word length n, information word length k and minimum Hamming distance d is generated by attaching an additional paritycheck symbol bn to each code word b = (b0 , b1 , . . . , bn−1 ) ∈ B(n, k, d). The additional paritycheck symbol is calculated according to bn = −(b0 + b1 + · · · + bn−1 ) = − n−1 bi . i=0 For a linear binary block code B(n, k, d) this yields bn = b0 + b1 + · · · + bn−1 = n−1 bi . i=0 We obtain the extended code B (n , k , d ) = (b0 , b1 , · · · , bn−1 , bn ) : (b0 , b1 , . . . , bn−1 ) ∈ B(n, k, d) ∧ b0 + b1 + · · · + bn−1 + bn = 0 with code parameters n = n + 1, k = k, d ≥ d. 44 ALGEBRAIC CODING THEORY In the case of a linear binary block code B(n, k, d) with q = 2 and an odd minimum Hamming distance d, the extended code’s minimum Hamming distance is increased by 1, i.e. d = d + 1. The additional paritycheck symbol bn corresponds to an additional paritycheck equation that augments the existing paritycheck equations H rT = 0 ⇔ r ∈ B(n, k, d) of the original linear block code B(n, k, d) with the (n − k) × n paritycheck matrix H. The (n − k + 1) × n paritycheck matrix H of the extended block code B (n , k , d ) is then given by 0 0 H .. . H = . 0 11 ···1 1 Code Interleaving Up to now we have considered the correction of independent errors within a given received word in accordance with a memoryless channel. In real channels, however, error bursts might occur, e.g. in fading channels in mobile communication systems. With the help of socalled code interleaving, an existing errorcorrecting channel code can be adapted such that error bursts up to a given length can also be corrected. Starting with a linear block code B(n, k, d) with code word length n, information word length k and minimum Hamming distance d, the code interleaving to interleaving depth t is obtained as follows. We arrange t code words b1 , b2 , . . . , bt with bj = (bj,0 , bj,1 , . . . , bj,n−1 ) as rows in the t × n matrix b1,0 b2,0 .. . b1,1 b2,1 .. . bt,0 bt,1 · · · b1,n−1 · · · b2,n−1 .. .. . . · · · bt,n−1 . The resulting code word b = b1,0 b2,0 · · · bt,0 b1,1 b2,1 · · · bt,1 · · · b1,n−1 b2,n−1 · · · bt,n−1 of length n t of the interleaved code B (n , k , d ) is generated by reading the symbols off the matrix columnwise. This encoding scheme is illustrated in Figure 2.26. The interleaved code is characterised by the following code parameters n = n t, k = k t, d = d. ALGEBRAIC CODING THEORY 45 Code interleaving of a linear block code ■ b1 b1,0 b1,1 ... b1,n−2 b1,n−1 b2 b2,0 b2,1 ... b2,n−2 b2,n−1 .. . .. . .. . .. .. . .. . bt−1 bt−1,0 bt−1,1 ... bt bt,0 bt,1 ... . bt−1,n−2 bt−1,n−1 bt,n−2 bt,n−1 Resulting code word of length n t b = b1,0 b2,0 · · · bt,0 b1,1 b2,1 · · · bt,1 · · · b1,n−1 b2,n−1 · · · bt,n−1 (2.36) Figure 2.26: Code interleaving of a linear block code B(n, k, d) Neither the code rate k k kt = =R = n nt n nor the minimum Hamming distance d = d are changed. The latter means that the error detection and error correction capabilities of the linear block code B(n, k, d) with respect to independent errors are not improved by the interleaving step. However, error bursts consisting of burst neighbouring errors within the received word can now be corrected. If the linear block code B(n, k, d) is capable of correcting up to ecor errors, the interleaved code is capable of correcting error bursts up to length R = burst = ecor t with interleaving depth t. This is achieved by spreading the error burst in the interleaved code word b onto t different code words bj such that in each code word a maximum of ecor errors occurs. In this way, the code words bj can be corrected by the original code B(n, k, d) without error if the length of the error burst does not exceed ecor t. 46 ALGEBRAIC CODING THEORY For practical applications it has to be observed that this improved correction of error bursts comes along with an increased latency for the encoding and decoding steps. Plotkin’s (uv) Code Construction In contrast to the aforementioned code constructions, the (uv) code construction originally proposed by Plotkin takes two linear block codes B(n1 , k1 , d1 ) and B(n2 , k2 , d2 ) with code word lengths n1 and n2 , information word lengths k1 and k2 and minimum Hamming distances d1 and d2 . For simpliﬁcation, we ﬁll the code words of the block code with smaller code word length by an appropriate number of zeros. This step is called zero padding. Let u and v be two arbitrary code words thus obtained from the linear block codes B(n1 , k1 , d1 ) and B(n2 , k2 , d2 ) respectively.12 Then we have b1 0, . . . , 0 , n1 < n2 u= b1 , n1 ≥ n2 and v= b2 , b2 0, . . . , 0 , n1 < n2 n1 ≥ n2 with the arbitrarily chosen code words b1 ∈ B(n1 , k1 , d1 ) and b2 ∈ B(n2 , k2 , d2 ). We now identify the code words u and v with the original codes B(n1 , k1 , d1 ) and B(n2 , k2 , d2 ), i.e. we write u ∈ B(n1 , k1 , d1 ) and v ∈ B(n2 , k2 , d2 ). The code resulting from Plotkin’s (uv) code construction is then given by B (n , k , d ) = {(uu + v) : u ∈ B(n1 , k1 , d1 ) ∧ v ∈ B(n2 , k2 , d2 )} . This code construction creates all vectors of the form (uu + v) by concatenating all possible vectors u and u + v with u ∈ B(n1 , k1 , d1 ) and v ∈ B(n2 , k2 , d2 ). The resulting code is characterised by the following code parameters n = 2 max {n1 , n2 } , k = k1 + k2 , d = min {2 d1 , d2 } . 2.2.8 Examples of Linear Block Codes In this section we will present some important linear block codes. In particular, we will consider the already introduced repetition codes, paritycheck codes and Hamming codes. Furthermore, simplex codes and Reed–Muller codes and their relationships are discussed (Berlekamp, 1984; Bossert, 1999; Lin and Costello, 2004; Ling and Xing, 2004). 12 In the common notation of Plotkin’s (uv) code construction the vector u does not correspond to the information vector. ALGEBRAIC CODING THEORY 47 Repetition code ■ The repetition code B(n, 1, n) repeats the information symbol u0 in the code vector b = (b0 , b1 , . . . , bn−1 ), i.e. b0 = b1 = · · · = bn−1 = u0 ■ ■ (2.37) Minimum Hamming distance d=n (2.38) 1 n (2.39) Code rate R= Figure 2.27: Repetition code Repetition Codes We have already introduced the binary triple repetition code in Section 1.3 as a simple introductory example of linear block codes. In this particular code the binary information symbol 0 or 1 is transmitted with the binary code word 000 or 111 respectively. In general, a repetition code over the alphabet Fq assigns to the qnary information symbol u0 the ndimensional code word b = (u0 , u0 , . . . , u0 ). Trivially, this block code is linear. The minimum Hamming distance is d = n. Therefore, the repetition code in Figure 2.27 is a linear block code B(n, 1, n) that is able to detect edet = d − 1 = n − 1 errors or to correct ecor = (d − 1)/2 = (n − 1)/2 errors. The code rate is 1 R= . n For the purpose of error correction, the minimum distance decoding can be implemented by a majority decoding scheme. The decoder emits the information symbol û0 which appears most often in the received word. The weight distribution of a repetition code is simply given by W (x) = 1 + (q − 1) x n . Although this repetition code is characterised by a low code rate R, it is used in some communication standards owing to its simplicity. For example, in the shortrange wireless communication system BluetoothTM a triple repetition code is used as part of the coding scheme of the packet header of a transmitted baseband packet (Bluetooth, 2004). 48 ALGEBRAIC CODING THEORY Paritycheck code ■ The paritycheck code B(n, n − 1, 2) attaches a paritycheck symbol so that the resulting code vector b = (b0 , b1 , . . . , bn−1 ) fulﬁls the condition b0 + b1 + · · · + bn−1 = 0, i.e. bn−1 = −(u0 + u1 + · · · + un−2 ) ■ ■ (2.40) Minimum Hamming distance d=2 Code rate R= (2.41) 1 n−1 =1− n n (2.42) Figure 2.28: Paritycheck code ParityCheck Codes Starting from the information word u = (u0 , u1 , . . . , uk−1 ) with ui ∈ Fq , a paritycheck code attaches a single paritycheck symbol to the information word u as illustrated in Figure 2.28. The n = (k + 1)dimensional code word b = (b0 , b1 , . . . , bn−2 , bn−1 ) = (b0 , b1 , . . . , bk−1 , bk ) is given by bi = ui for 0 ≤ i ≤ k − 1, and the paritycheck symbol bk which is chosen such that k bi = b0 + b1 + · · · + bk = 0 i=0 is fulﬁlled. Over the ﬁnite ﬁeld Fq we have bk = −(u0 + u1 + · · · + uk−1 ) = − k−1 ui . i=0 In the case of a binary paritycheck code over the alphabet F2 , the paritycheck bit bk is chosen such that the resulting code word b is of even parity, i.e. the number of binary symbols 1 is even. The paritycheck code is a linear block code B(k + 1, k, 2) with a minimum Hamming distance d = 2. This code is capable of detecting edet = d − 1 = 1 error. The correction of errors is not possible. The code rate is R= n−1 1 k = =1− . k+1 n n ALGEBRAIC CODING THEORY 49 The error detection is carried out by checking whether the received vector r = (r0 , r1 , . . . , rn−1 ) fulﬁls the paritycheck condition n−1 ri = r0 + r1 + · · · + rn−1 = 0. i=0 If this condition is not met, then at least one error has occurred. The weight distribution of a binary paritycheck code is equal to n 4 n 2 W (x) = 1 + x + x + · · · + xn 4 2 for an even code word length n and n 2 n 4 W (x) = 1 + x + x + · · · + n x n−1 2 4 for an odd code word length n. Binary paritycheck codes are often applied in simple serial interfaces such as, for example, UART (Universal Asynchronous Receiver Transmitter). Hamming Codes Hamming codes can be deﬁned as binary or qnary block codes (Ling and Xing, 2004). In this section we will exclusively focus on binary Hamming codes, i.e. q = 2. Originally, these codes were developed by Hamming for error correction of faulty memory entries (Hamming, 1950). Binary Hamming codes are most easily deﬁned by their corresponding paritycheck matrix. Assume that we want to attach m paritycheck symbols to an information word u of length k. The paritycheck matrix is obtained by writing down all mdimensional nonzero column vectors. Since there are n = 2m − 1 binary column vectors of length m, the paritycheck matrix 1 0 1 0 1 0 1 0 ··· 0 1 0 1 0 1 0 1 0 1 1 0 0 1 1 0 ··· 0 0 1 1 0 0 1 1 0 0 0 1 1 1 1 0 ··· 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 1 ··· 1 1 1 1 1 1 1 1 .. .. .. .. .. .. .. .. . . .. .. .. .. .. .. .. .. . . . . . . . . . . . . . . . . . 0 0 0 0 0 0 0 0 ··· 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 ··· 1 1 1 1 1 1 1 1 is of dimension m × (2m − 1). By suitably rearranging the columns, we obtain the (n − k) × n or m × n paritycheck matrix H = Bn−k,k In−k of the equivalent binary Hamming code. The corresponding k × n generator matrix is then given by G = Ik − BTn−k,k . 50 ALGEBRAIC CODING THEORY Because of the number of columns within the paritycheck matrix H, the code word length of the binary Hamming code is given by n = 2m − 1 = 2n−k − 1 with the number of binary information symbols k = n − m = 2m − m − 1. Since the columns of the paritycheck matrix are pairwise linearly independent and there exist three columns which sum up to the allzero vector, the minimum Hamming distance of the binary Hamming code is d = 3.13 The binary Hamming code can therefore be characterised as a linear block code B(2m − 1, 2m − m − 1, 3) that is able to detect edet = 2 errors or to correct ecor = 1 error. Because of n = 2n−k − 1 and ecor = 1 we have ecor n = 1 + n = 2n−k , i i=0 i.e. the binary Hamming code is perfect because it fulﬁls the sphere packing bound.14 Since the binary Hamming code B(2m − 1, 2m − m − 1, 3) only depends on the number of parity symbols m, we also call this code H(m) with the code parameters n = 2m − 1, k = 2m − m − 1, d = 3. For a binary Hamming code the decoding of an erroneously received vector r = b + e with error vector e of weight wt(e) = 1 can be carried out by ﬁrst calculating the syndrome s T = H rT = H eT which is then compared with all columns of the paritycheck matrix H. If the nonzero syndrome sT agrees with the j th column vector, the error vector e must have its single nonzero component at the j th position. The received vector r = (r0 , . . . , rj −1 , rj , rj +1 , . . . , rn−1 ) can therefore be decoded into the code word b̂ = (r0 , . . . , rj −1 , rj + 1, rj +1 , . . . , rn−1 ) by calculating b̂j = rj + 1. The weight distribution W (x) of the binary Hamming code H(m) is given by 1 (1 + x)n + n (1 − x)(n+1)/2 (1 + x)(n−1)/2 . n+1 The coefﬁcients wi can be recursively calculated according to n i wi = − wi−1 − (n − i + 2) wi−2 i−1 W (x) = with w0 = 1 and w1 = 0. Figure 2.29 summarises the properties of the binary Hamming code H(m). 13 In the given matrix the ﬁrst three columns sum up to the zero column vector of length m. There are only two other nontrivial perfect linear codes, the binary Golay code B(23, 12, 7) with n = 23, k = 12 and d = 7 and the ternary Golay code B(11, 6, 5) with n = 11, k = 6 and d = 5. The extended binary Golay code has been used, for example, for the Voyager 1 and 2 spacecrafts in deepspace communications. 14 ALGEBRAIC CODING THEORY 51 Binary Hamming code ■ The binary Hamming code H(m) is a perfect singleerror correcting code with paritycheckmatrix H consisting of all 2m − 1 nonzero binary column vectors of length m. ■ Code word length ■ ■ n = 2m − 1 (2.43) d=3 (2.44) Minimum Hamming distance Code rate R= m 2m −