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

`
`.r;-2;.-z:~.'«?.z:<,'=.-.;:'.)I;~=:-z.,‘?.-.-.--'_.'.'_.'=-.*.’.'..'~'=;"';-'-“':'.'-’j-i'-:'=1-2"".':..~.":
`
`
`
`
`
`"_;,,(._aav_¢°;ae¢«-9a..\.-.;"3'-3
`
`Errol
`Codi]
`Com“;
`
`George
`
`and
`
`J. Bibb (
`
`Harris Corporafioe
`Melbotmze. Horidi
`
`
`
`Applications of Communications Theory
`Series Edit0l'! R. W. Lucky, Bell Laboratories
`
`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
`
`ERROR-CORRECTION CODING FOR DIGITAL COMMUNICATIONS
`
`George C. Clark, Jr., and J. Bibb Cain
`
`A Cunununtion Order Plan is
`
`;1va':lablc for this .‘§[_‘|'It,‘_\'. A ¢:onl1'nuation order will hrillg
`
`(Ecli\'ur;.-' of czluh new volume inmtetiiately u-pun ruabliasmion. Vululnrcs are billed only upon
`actual shinrnent. For further inf0rn1ntiun plc:m; contact
`the puhIiu'm:r.
`
`
`
`

`
`
`
`Error- Correction
`Coding for Digital
`
`
`
`Communications
`
`
`George C. Clark, Jr.
`and
`‘
`
`J. Bibb Cain
`
`Harrfs Corpora {ion
`Melbounze. Fiorfda
`
`
`
`..'..-—«--«.«»..
`
`PLENUM PRESS 0 NEW YORK AND LONDON
`
`
`
`

`
`
`
`
`
`orrectirrg codes (lrrfonnzrtiori
`
`theory). I.
`
`éid63o
`AACR2
`
`
`
`Preface
`
`Library of Congress Cataloging in Publication Data
`Clark, George C. (George Cyril), l938~
`Error—corrt-:ction coding for digital communications.
`Bibliogrzipiry: p.
`Irrc1udesindex_
`
`
`
`__..fi._....t..,.....
`
`I. Data transrnission systeiirs. 2. Error—c
`Cain, J. Bibb. II. Title.
`TKS102.5.C52
`ISBN 0-306-40615-2
`
`62I.38’O413
`
`
`
`
`
`-se"””“"'
`
`_
`\
`"J
`
`(<3 1981 Plenunr Press, New York
`A Division of Plenum Pubfishing Corporation
`233 Spring Street, New York, NY. 10013
`All rights reserved
`
`No part of this book may be reproduced, stored in ;1 retriev
`at system. or trtansmitted,
`in any form or by any means, eiectronic, nreciuznical, photocopying, microfilming,
`recording, or otiierwise, without written permission from the Publisher
`Printed in the United States of America
`
`
`
`
`Error-eomcction cos
`new t.?OI‘I1I'l1LmiC21Ii(‘1I_j
`increatso the cncr'g_»_-'
`1
`aiso prox-iding inn
`problems. Among i
`ceitised by filtering
`certain freqiicmsy in
`coding provided by.
`inerous articles have
`deficiciieies. First.
`tl
`algorithm into actua
`that is E,i\";iii'di')iC is sk
`required to cwiltmte
`countered in practict
`reports.
`This book is air
`for the design engine
`and for the commu
`
`I
`'
`
`
`
`.-wu—w'
`
`1
`,i
`
`'
`
`into 21 sy
`equipment
`gradtizite test for atri
`The book uscs=
`
`classical thi:or'enr.-"pr":
`ever possible heuristi
`by di"dW'i[1§_Z amulogii
`inathernatic:-:J rigor I.
`stamding. coding iszt
`impo.~;sibIc task to a
`"at all. The zissumptio
`
`

`
`
`
`Chap.
`
`1' n Fundamental Concepts of Coding
`
`differ in two positions, etc. As in
`the simple example given previously, there
`will almost always be some patterns that are left over aft
`er assigning all
`those that differ in r 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 number of errors tha
`t are correctable. First observe lhat
`there are 2“ possible sequences. Each c
`olumn ofthe decoding table contains
`_.N'r of these sequences so that the num
`ber ofcode words. .-N}. must obey the
`inequality
`
`
`
`See. 1.]. 3 Basic P
`
`Many goo:
`permit the eorrt
`
`remarkable imp
`to generate and
`
`relatively straigl“.
`of length 40 that
`ing up to four.
`reveals that
`this
`than l0 "'4. Ifthis
`
`of increasing the
`going to a some
`averaging. In eitl
`Both options. he
`tivcs.
`
`Before proe:
`practical import:
`for many years. I
`scheme for corret
`{in this case r..-“ii
`i
`
`made arbitrarily
`Unfortunately. tli
`procedures encou
`ratio r ‘ii at the e:
`
`[or equivalently. I
`the relative numb
`
`vanishingly small
`was given by Just
`construct ‘cl Uléi-N‘-‘i
`scribed above} an
`the authors" knot’
`real comrnunicatit
`
`_
`
`(1~3l
`N <2"r‘l[I+n+(”)+---+(”)
`‘" /
`2
`r
`This is called a Hamnriizg bound or “sphere-pacl<ing" bound. The equality
`in this bound can be achieved only for so—called ptwfirt-r r'orfe.s'. These are
`codes which can correct all patterns of: or fewer errors and no others.
`There are only a small number of perfect codes which have been found and
`consequently the equality in (1-3) is almost never achieved.
`At the encoder we envision a process by which a it-symbol information
`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 (wk) code. Since the k—symbol
`sequence can take on 2* distinct values. inequality [I-3] can be written
`
`(1-4)
`2‘<s2"f/[1+u-+(:)+---+(:'H
`A measure of the efficiency implied by a particular code choice is given by
`the ratio
`
`
`
`where R is defined as the code
`that are redundant is l — R.
`
`rate. The fraction of transmitted symbols
`
`R = I-c.-"u
`
`(1.5;
`
`Table 1-2. The portion of the code sequence contained between the dashed
`lines is identical to the input sequence. Thus. each code sequence is easily
`and uniquely related to the input. Not all block codes exhibit this property.
`Those which do are referred to as .3‘y5temttItc' codes. For systematic codes.
`the concept of redundant digits becom
`of the digits in positions 1. 4, and 5. Conversely. codes which do not exhibit
`this property are called norrs_i>srematic' codes.
`
`
`
`

`
` Decoding
`
`Sec. 6.1. 0 Binary Rate-1,-'2 tfonvolutional Codes
`
`229
`
`
`
`T1 (.\'} = 1' [,\'] g, (x). where the polynomial multiplication is carried
`as
`out in GF 2].
`The code used in this example is a nmi.s'_t'str>nratt‘c code because neither
`[.\'} nor T2['.\'} is
`identically equal
`to the information sequence I[.\'}.
`T,
`Conversely. a .x'ysteinarit' code would have either 5.11 [x] = 1or'_q2{'x) = I
`so that
`the information sequence would appear‘ directly in the output
`sequence. For reasons which will subsequently become clear. nonsysteinatic
`codes are usually prclisried in systems which utilize Vitcrbi decoding.
`As one might suspect from the name. the output of the encoder can
`also be thought ofas the convolution otithe impulse response ofthe encoder
`with the input sequence. For example. it‘ a single one followed by all zeros
`[fix] = 1]
`is shifted into the encoder of Fig. 6-1.
`the resultant output
`sequence is 1
`1 01 1
`1 0000
`The reader may verify that the response to
`any arbitrary input sequence may be produced by adding rnodulo—2 appro-
`priately shifted versions 01‘ this sequence. This suggests that a generator
`rnatrix. G. can be constructed as
`
`ire oi‘ a
`trot-‘ides
`.‘IT1E1I1(.‘C.
`
`gorithm
`ful per-
`irn will
`trdware
`rmance
`
`3 input
`series
`:0 or 1)
`1e con-
`
`tion of
`
`output
`pressed
`
`110111000000...
`00 11 01 110000 00
`
`G: 0000110l11000000...
`
`161)
`
`In contrast with block codes, conyolutional codes do not need to have
`
`i.e.._ the code words may have
`the information sequence in blocked form.
`infinite length. Thus. the generator matrix as shown in {'6-1) is sometimes
`said to be a semi—r'ii_ft'itt'rr= matrix. The code word corresponding any input
`sequence X may be found by rnultiplying the input vector by G. i.e..
`
`Y = xto
`
`(6-2)
`
`is obtained
`I 1000
`Thus. the output sequence corresponding to X7" = 1
`byaddingrows1.2.and3ofGtogiveY"'=11 10 01 101100 00
`Another convenient method ol‘ describing the relationship between
`input and output sequences is a code tree such as shown in Fig. 6-2. Each
`branch of the tree represents a single input symbol. The convention used
`is
`that an input 0 corresponds to the upper branch and an input
`1
`corresponds to the lower branch. Thus, any input sequence traces out a
`particular path through the tree. Specifically, a 10110 input sequence
`causes a 11 01 00 10 10 output sequence. This path is indicated in Fig.
`6-2. Ofeourse. as the input sequence grows in length. the number 01" possible
`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“