Error-Correction
`Coding for Digital
`Communications
`
`
`
`Apple 1021
`
`Apple 1021
`
`

`

`Applications of Communications Theory
`Series Editor: R. W. Lucky, Beli Laboratories
`
`
`SEeeaeens
`
`ESRESctrperSaIa
`
`
`INTRODUCTION TO COMMUNICATION SCIENCE AND SYSTEMS
`John R. Pierce and Edward C. Posner
`
`OPTICAL FIBER TRANSMISSION SYSTEMS
`Stewart D. Personick
`
`TELECOMMUNICATIONS SWITCHING
`J. Gordon Pearce
`
`Errot
`Codi
`Com
`
`George ¢
`and
`J. Bibb ¢
`
`Harris Corporation
`Melbourne, Floridt
`
`ERROR-CORRECTION CODING FOR DIGITAL COMMUNICATIONS
`George C. Clark, Jr., and J. Bibb Cain
`
`
`
`
`
`A Continuation Order Plan is available for this series. A continuation order will bring
`delivery of each new volume immediately upon publication. Volumes are billed only upon
`actual shipment. For further information please contact
`the publisher.
`
`PLENUM PRI
`
`

`

`
`
`Error-Correction
`Codingfor Digital
`
`
`Communications
`
`
`
`
`
`George C. Clark, Jr.
`
`and
`J. Bibb Cain
`
`ionamin
`
`Harris Corporation
`Melbourne, Florida
`
`PLENUM PRESS «+ NEW YORK AND LONDON
`
`

`

`
`
`
`Library of Congress Cataloging in Publication Data
`Clark, George C. (George Cyril), 1938-
`Error-correction coding for digital communications.
`Bibliography: p.
`Includes index.
`1. Data transmission systems. 2. Error-correcting codes (Information theory). I,
`Cain, J. Bibb. IL. Title.
`TK5102.5.C52
`621.38'0413
`81-1630
`ISBN 0-306-40615-2
`AACR2
`
`serra
`
`
`
`
`Preface
`
`
`Seas
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`xe OF CONG,
`Sng mea
`JUL
`1 1981
`
`
`
`
`
`
`
`Error-correction cot
`new communicatior
`increase the energy«
`also providing inn
`problems. Among {
`caused byfiltering
`certain frequency m
`coding provided by
`merous articles have
`deficiencies. First,
`tl
`algorithm into actua
`that is available is sk
`required to evaluate
`counteredin practice
`reports.
`This book is air
`for the design engine
`and for the commu
`equipment
`into a sy
`graduate text for an
`The book uses.
`classical theorem/pri
`ever possible heuristi
`by drawing analogi
`mathematical rigort
`standing, coding is a
`
`remem
`
`©1981 PlenumPress, New York
`A Division of Plenum Publishing Corporation
`233 Spring Street, New York, N.Y. 10013
`All rights reserved
`
`Nopart of this book maybe reproduced, stored in aretriev.
`al system, or transmitted,
`in any formor by any means, electronic, mechanic
`al, photocopying, microfilming,
`recording, or otherwise, without written permission from the Publis
`Printed in the United States of America
`“at all. The assumptio
`
`
`impossible task to a
`
`

`

`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Chap.
`| @ Fundamental Concepts of Coding
`differ in twopositions, etc. As in the simple example given previously, there
`will almost always be some patterns that are left over after assigning all
`those that differ in ¢ or fewer places (thus accounting for the inequality).
`At this point we are in a Position to relate the amount of redundancy
`in a code to the numberof errors that are correctable. First observe that
`there are 2” possible sequences. Each column ofthe decodingtable contains
`N, of these sequences so that the number of code words, N., must obeythe
`inequality
`N, S27] itn Jens
`)
`(1-3)
`i
`i
`/
`2
`t/.
`This is called a Hamming bound or “sphere-packing™ bound. The equality
`in this bound can be achieved only for so-called perfect codes. These are
`codes which can correctall patterns of t or fewer errors and no others.
`There are only a small numberof perfect codes which have been found and
`consequently the equality in (1-3) is almost never achieved.
`At the encoder weenvision a process by which a k-symbolinformation
`Sequence is mapped into an n-symbol code sequence. Although the termi-
`nology is usually restricted to the so-called linear codes (to be discussed),
`we shall refer to any such mapping as an (n,k) code. Since the k-symbol
`Sequence can take on 2* distinct values. inequality(1-3) can be written
`es 2/ fiona (Seo 4(")]
`(1-4)
`A measure of the efficiency implied by a particular code choice is given by
`
`Sec. 1.1. @ Basic P
`
`Many gooc¢
`permit the corre
`remarkable imp
`to generate and
`relatively straigt
`of length 40 that
`ing up to four.
`reveals that
`this
`than 10°>*. If this
`of increasing the
`going to a some
`averaging. In eitl
`Bothoptions. he
`tives.
`
`Before proc
`practical importe
`for manyyears. T
`schemefor correc
`(in this case t/ni
`made arbitrarily
`Unfortunately, th
`procedures encou
`ratio t/n at the e
`(or equivalently. }
`the relative numb
`vanishingly small
`was given by Just
`construct a class
`scribed above) an
`the authors’ knov
`
`/
`
`the ratio
`
`
`
`
`(1-5)
`R=k/n
`
`where R is defined as the code rate. The fraction of transmitted symbols
`that are redundant is | — R.
`The mapping implied by the encoder can be described by a look-up
`
`table. For example, the four-word code discussed previouslyis described in
`Table 1-2. The portion of the code Sequence contained between the dashed
`
`lines is identical to the input sequence. Thus, each code sequenceis easily
`
`and uniquely related to the input. Notall block codes exhibit this property.
`Those which doare referred to as systematic codes. For systematic codes.
`
`the conceptof redundant digits becomesvery clear and in Table 1-2 consists
`
`of the digits in positions 1, 4, and 5. Conversely, codes which do not exhibit
`
`this property arecalled nonsystematic codes,
`
`
`
`real communicatic
`
`

`

` Decoding
`
`Sec. 6.1. @ Binary Rate-1/2 Convolutional Codes
`
`229
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`ire of a
`rovides
`‘mance.
`
`rorithm
`ful per-
`rn will
`irdware
`rmance
`
`k-stage
`\dulo -2
`ynvolu-
`1 at the
`adders
`register
`nerator
`
`x +x?
`t-order
`> input
`series
`0 or1)
`1€ con-
`
`tion of
`
`output
`pressed
`
`as T; (x) = I(x) g, (x), where the polynomial multiplication is carried
`out in GF(2).
`The code used in this example is a nonsystematic code because neither
`T, (x) nor T,(x) is
`identically equal
`to the information sequence I (x).
`Conversely, a systematic code would have either g, (x) = | org,(x) = 1
`so that
`the information sequence would appear directly in the output
`sequence. For reasons which will subsequently become clear, nonsystematic
`codes are usually preferred in systems which utilize Viterbi decoding.
`As one might suspect from the name, the output of the encoder can
`also be thought of'as the convolution ofthe impulse response of the encoder
`with the input sequence. For example, if a single one followed byall zeros
`[1(x) = 1]
`is shifted into the encoder of Fig. 6-1,
`the resultant output
`sequence is 1101110000.... The reader mayverify that the response to
`anyarbitrary input sequence may be produced by adding modulo-2 appro-
`priately shifted versions of this sequence. This suggests that a generator
`matrix, G, can be constructed as
`
`110111000000 ...
`OO L101 110000 00 ...
`G=|] 000011011100 00 00...
`
`(6-1)
`
`In contrast with block codes, convolutional codes do not need to have
`the information sequence in blocked form, i.e,
`the code words may have
`infinite length. Thus, the generator matrix as shownin (6-1) is sometimes
`said to be a semi-infinite matrix. The code word corresponding any input
`sequence X maybe found by multiplying the input vector by G, Le.,
`
`Y=X'G
`
`(6-2)
`
`Thus, the output sequence corresponding to X? = 111000... is obtained
`by adding rows 1,2,and 30f GtogiveY’ = 11 1001 10110000....
`Another convenient method of describing the relationship between
`input and output sequencesis a code tree such as shown in Fig. 6-2. Each
`branch ofthe tree represents a single input symbol. The convention used
`is
`that an input 0 corresponds to the upper branch and an input
`|
`corresponds to the lower branch. Thus, anyinput sequence traces out a
`particular path through the tree. Specifically, a 10110 input sequence
`causes a 11 Q1 00 10 10 output sequence. This path is indicated in Fig.
`6-2. Of course, as the input sequence growsin length, the number ofpossible
`paths grow exponentially, thus limiting the role of such a tree diagram
`to a conceptual] one.
`
`
`Fortunately, the exponential growth of the code tree can be “tamed”
`
`