TK 5183
`
`Chris Heegard
`Stephen B. Wicker
`
`* TURBO
`ODING
`
`Apple 1020
`
`
`
`
`
`Kluwer Academic Publishers
`
`Apple 1020
`
`

`

`TURBO CODING
`
`

`

` TURBO CODING
`
`
`Chris Heegard
`Alantro Communications, Inc.
`and Cornell University
`
`
`
`Stephen B. Wicker
`Cornell University
`
`KLUWER ACADEMIC PUBLISHERS
`
`Boston / Dordrecht / London
`
`

`

`
`
`
`
`
`
`
`
`
`
`Distributors for North, Central and South America:
`Kluwer Academic Publishers
`101 Philip Drive
`Assinippi Park
`Norwell, Massachusetts 02061 USA
`Telephone (781) 871-6600
`Fax (781) 871-6528
`E-Mail <kluwer@wkap.com>
`
`
`
`Distributors for all other countries:
`Kluwer Academic Publishers Group
`Distribution Centre
`Post Office Box 322
`3300 AH Dordrecht, THE NETHERLANDS
`Telephone 31 78 6392 392
`Fax 31 78 6546 474
`E-Mail <orderdept@wkap.nl>
`“&@ Electronic Services <http://www.wkap.nl>
`Be
`
`Library of Congress Cataloging-in-Publication Data
`
`A C.LP. Catalogue record for this book is available
`~ from the Library of Congress.
`
`: ‘Copyright © 1999 by Kluwer Academic Publishers
`
`~All rights reserved. Nopart of this publication may be reproduced,stored in a
`retrieval system or transmitted in any form or by any means, mechanical, photo-
`- ‘copying, recording, or otherwise, without the prior written permission of the
`publisher, Kluwer Academic Publishers, 101 Philip Drive, Assinippi Park, Norwell,
`Massachusetts 02061
`
`|
`:
`
`1
`
`
`
`
`
`
`
`
`
`
`
`Printed on acid-free paper.
`
`Printed in the United States of America
`
`
`
`

`

`2.1. BASIC DEFINITIONS FOR BCE’S
`12
`
`CHAPTER 2.cnase
`
`
`[Re L—~ fa
`Lisa
`“ER
`xX
`x
`ob.
`IR,
`(c)
`Systematic
`
`m
`
`;
`
`my,
`
`FIR,
`(a)
`systematic
`
` Non-
`
`(b) IIR, Systematic
`
`—
`*Se
` Non-
`
`2
`aan
`
`12
`
`
`
`
` Figure 2.1: Rate 1/2 (n = 2,k = 1) Encoders
`
`
`
`
`
`
`The most
`lutional enco:
`transform of
`
`nomial 77109 +.
`delay. Using
`
`An encoderis FIR (see Figures 2.1(a) and 2.2(a)) if its output can
`written in ter
`be computedas a linear combinationof the current input andafinite
`x(D) = [x1
`numberof past inputs. The linear combinationis expressed in terms
`
`of the input bits and the generator sequences for the encoders. A
`
`given generator sequence {Gi,p,1} relates a particular input sequence
`
`{m}} to a particular output sequence {x?}. A particular value of
`Gi,p,. denotes the presence or absence of a tap connecting the jth
`memoryelement of the jth input shift register to the pth output.
`The 7 output equations have the form
`
`A Binary Convolutional Code (BCC)is the set of codewords pro-
`duced at the output of a BCE,
`Figures 2.1 and 2.2 showvarious types of BCE’s. A BCE can be
`Finite Impulse Response (FIR) (also called “feed-forward”, “feedback-
`free”, or “non-recursive”) or Infinite Impulse Response (IIR) (“feed-
`back”or “recursive”). Also, aBCE can be Systematic or non-systematic.
`
`k
`xy =D
`i=1l
`
`=Lt
`
`0
`
`Jiplmj;,
`
`lspsn
`
`
`
`
`
`
`
`
`The memory for each of the k inputs is enumerated by the mem-
`ory vector (V1,V2,--+,Vpe) (ie.
`the jth input shift register has v;
`memoryelements). It is assumedthatfor eachi there is at least one
`p with giy,y, = 1. The state complexity of the encoderis determined
`by the total encoder memory v = Vi + V2+++++ Vp. The numberof
`states in the encoderis 2”, while the window length is determined by
`the memory order? 1 = maxy<j<x Vj.
`
`'The terminologyin the literature is inconsistent; the constraint length of a
`
`
`this text.
`
`convolutional¢
`in [(GCCC81] it:
`
`= [my
`
`=m(L
`
`where m;(D)
`a generator¥
`generator mé
`at most Vp. I
`
`while
`
`

`

`
`
`CHAPTER 2.
`
`
`BINARY CODES, GRAPHS, AND TRELLISES
`
`IX
`
`2
`mj
`
`m,
`
`x}
`
`x}
`x3
`
`5
`TH
`m;
`
`x
`
`i
`
`>
`xj
`x
`
`(a)
`
`on-systematic
`FIR, Non-systemati
`
`(b) IIR, Systematic
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`pro-
`
`1 be
`ack-
`2ed-
`atic.
`
`can
`
`nite
`rms
`
`nce
`
`> of
`jth
`jut.
`
`» Vi
`one
`
`red
`
`r of
`iby
`
`Figure 2.2: Rate 2/3 (n = 3,k = 2) Encoders
`
`The most convenient meansfor relating the output of a convo-
`lutional encoder to the input is through the “D transform.” The D
`transform of a temporal sequence mo, 771, M2,... , Mx is the poly-
`nomial mp +m1D + m2D2 + ---+mxD*, where D denotes relative
`delay. Using this simple tool, the output of an FIR encoder can be
`written in termsof the input by the matrix equation
`
`x(D) = [x1(D),x2(D),--- ,xn(D)]
`Qal(D) gi2(D) +: Gin(D)
`92,1(D) g22(D)
`+--+ gen (D)
`:
`;
`.
`;
`
`= [m(D),-- + ,mx(D)]
`
`9k1(D) gx2(D)
`
`+++ Grn(D)
`
`= m(D)G(D)
`
`where m;(D) = >; miD4, etc. The polynomial matrix G(D) is called
`a generator matrix for the encoder. In the FIR case, each term of the
`generator matrix is a polynomial gi,,(D) = YjLo Ji,p,jD! of degree
`at most vp. In Figure 2.1(a),
`G(D) =[1+D21+D+D*],
`
`while
`
`1
`
`l
`
`1
`
`G(D) = Ls be 1+D+D°2 |
`
`
`
`convolutional code is defined in [LDJC83] as n- (4 +1), in[Wic95] itis (+1) and
`in [GCCC81] it is v. For reasonsofclarity, we avoid the use ofthe termentirelyin
`this text.
`
`
`
`
`

`

`
`
`
`2.1. BASIC DEFINITIONS FOR BCE’S
`14
`CHAPTE
`
`
`
`in Figure 2.2(a).
`IIR encoders are displayed in Figures 2.1(b), 2.1(c) and 2.2(b),
`
`For these encoders,
`the n output equations involve both past in-
`
`puts and past outputs - it follows that the output can depend on
`
`an infinite numberof past inputs. However, as we will subsequently
`
`discuss, the memory structure of IIR encoders, as it pertains to the
`state complexity and total encoder memory (and the memoryvector
`
`(V1, V2,°* +:
`, Vk)) is well defined for all BCE’s. A minimal encoder,for
`a given BCC, is a BCE for which the total memory v of the encoder
`
`is minimum. One of the most important developments in thealge-
`
`braic theory of BCC’s [MS68, For70, Pir88] is the discovery that the
`
`memory structure of a minimal encoder has the memoryvectoras an
`invariant (ie., every minimal encoderfor a given BCC has the same
`
`memory vector).
`
`All BCE’s, both FIR and IIR, are described by generator matrices
`G(D).
`In the case of an IIR encoder, the elements of the generator
`matrix are rational functions(i.e., ratios of polynomials) in the vari-
`able D with binary coefficients. Note that for a causal encoder, the
`denominators must have a constant term of 1. For example, in Figure
`2.1(b),
`
`
`
`AS 4
`that the
`sented iJ
`generat
`1) BCC
`true fol
`2) enco
`page 13
`imal IIR
`systeme
`chapter
`develop
`
`2.2
`
`Al direc
`states ((
`the dire
`ao (b) 1
`called t
`states ¢
`since bi
`two bra
`
`G(D) = (1
`
`1+D+4+pD2
`1+pD2
`
`”
`
`in Figure 2.1(c),
`
`and
`
`G(D) = peTsDipz
`
`~~. 01
`|
`0
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`the sam
`1+D+D¢
`(D)
`=[1+
`i1+D 1,
`(a7 (b)
`G(D) = [1+D —————
`of leng
`branch
`o* (bi)
`irreduc
`leads t
`
`Ag
`in Figure 2.2(b).
`and thi
`Note that the definitions of BCC’s and BCE’s are somewhatcircu-
`set of é
`lar. A BCC is defined as the set of output sequences produced by a
`also kr
`given BCE. However, once a BCC is defined, one can consider the set
`the gré
`of BCE’s that generate it. For example, a systematic encoder is one
`next pi
`for which the encoder input (the data) forms a substring of the out-
`sectior
`put (the codeword). It is important to note that every BCC has botha
`graph
`minimal FIR encoder and a minimal systematic (usually IIR) encoder.
`each b
`
`
`
`
`
`