TURBO
`
`CODING
`
`Chris Heegard
`
`Stephen B. Wicker
`
`Kluwer Academic Publishers
`
`Apple 1120
`
`Apple 1120
`
`

`
`TURBO CODING
`
`

`
`
`
`TURBO CODING
`
`Ll
`
`W
`
`KLUWER ACADEMIC PUBLISHERS
`Boston I Dordrecht I London
`
`
`
`Chris Heegard
`Alcmrro Communications, Inc.
`
`and Cornell University
`
`Stephen B. Wicker
`Cornell University
`
`

`
` Distributors for North, Central and South America:
`
`
`
`Kluwer Academic Publishers
`
`101 Philip Drive
`Assinippi Park
`Norwell, Massachusetts 02061 USA
`Telephone (781) 871-6600
`Fax (731) 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 ‘F8 6546 474
`
`E-Mail <orderdept@wkap.r1l>
`
`
`
`All rights reserved. No part of this publication may be reproduced, stored in a
`retrieval system or transmitted in any form or by any means, mechanical, photo~
`"I copying, recording, or otherwise, without the prior written permission of the
`publisher, Kluwer Academic Publishers, 101 Philip Drive, Assinippi Park, Norwell,
`Massachusetts 02061
`
`I K‘ Electronic Services <http:i’fvv\vw.wl(ap.nl‘>
`'53‘
`
`Library of Congress Cataloging-in-Publication Data
`
`A 01.1’. Catalogue record for this book is available
`- from the Library of Congress.
`
`,;'{Copyright © 1999 by Kluwer Academic Publishers
`
`.
`,
`
`Printed on acid-free paper.
`
`Printed in the United States of America
`
`

`
`12
`
`2.1.
`
`BASIC DEFINITIONS FOR BCE ‘S
`
`
`
`§eeP1EI=¢_
`
`
`
`
`
`—fi>§—>Xi
`_
`
`‘<3
`
`ml
`
`nit
`
`d
`
`""‘”"””X:
`_1
`I
`
`-»
`
`I
`
`my‘
`-—a->8
`
`—-argm
`
`pm‘
`(3)
`systematic
`
`Non-
`
`(bl IIR, Systematic
`
`HR.‘
`(C)
`5V5Ie”1a“C
`
`NOI1-
`
`
`
`2
`mi
`
`L‘
`
`m‘.‘j_
`
`(<1) F
`
`
`
`-5-;
`
`Fi
`
`The most
`_.
`,
`en‘(‘0i
`transform of
`nomial mo +_
`delay Using
`‘rt
`in ter
`Wm en
`x(D) = [xii
`
`= [rm
`
`mu:
`"
`Where mdpt
`
`a generator I’
`generator 1112
`.
`I
`,
`I
`at mos 1 p.
`
`While
`
`3;
`"I
`
`E
`
`__
`"
`.
`
`.
`
`Figure 2.1: Rate 1/2 (rt = 2, k = 1) Encoders
`
`-
`
`A Binary Convolutional Code (BCC) is the set of codewords pro-
`duced at the output of a BCE.
`Figures 2.1 and 2.2 show various types of BCE’s. A BCE can be
`v
`,
`-
`n *
`1:
`it
`Finite Impwlse Response (FIR) (also called feed-forward ,
`feedl9ack-
`free”, or “non—recursiye”) or Infinite Impulse Response (HR) (“feed
`back or
`recursive ). Also, a BC]: can be systematic or nonsysternattc.
`An encoder is FIR {see Figures 2.1(a) and 2.2(a)) if its output can
`be computed as a linear combination of the current input and a finite
`number of past inputs. The linear combination is expressed in terms
`of the input bits and the generator sequences for the encoders. A
`given generator sequence {ppm} relates a particular input sequence
`{mg} to a particular output sequence {xi-9}. A particular value of
`9,-_‘p_; denotes the presence or absence of a tap connecting the tth
`memory element of the tth input shift register to the pm output.
`The 71 output equations have the form
`
`k V
`X?’ = Z Z 91.
`J
`L-211:0
`
`£mt3__ ,
`J I
`
`-P‘
`
`1 5 p 5 «n
`
`The memory for each of the k inputs is enumerated by the mem-
`ory vector (V1, V2,
`-
`r
`-
`,v;¢) (Le.
`the sill input shift register has V,-_
`memory elements ). It is assumed that for each ti there is at least one
`p with 9,-msvfi = 1. The state complexity of the encoder is determined
`by the total encoder memory 12 2 1/']_ + V2 + -
`-
`~ +- vk. The number of
`states in the encoder is 2“, while the window length is determined by
`the memory orderl ,u ——.. 111etx_15._,-,;;< v,-_.
`__
`_
`‘The terminology in the literature is inconsistent; the constraint length of a
`
`
`
`em“
`.
`;
`C9“"°1““0”a1E
`in tGcccs11 it‘.
`'_
`this [ext
`
`
`

`
`
`
`CHAPTER 2.
`
`BINARY CODES, GRAPHS, AND TRELLISES
`
`X.
`
`‘
`
`2
`-‘*1
`-X‘
`
`f
`
`'
`
`2
`m‘
`
`nf
`I
`
`X‘?
`
`Y3
`'
`i
`
`')
`me
`mL—
`
`(a) I-‘IR, Nonsystemattc
`
`(b) HR‘ Systematic
`
`Figure 2.2: Rate 2/3 (71. = 3,1: = 2) Encoders
`
`=[mt£D).---.mr(DJ]
`
`.9t,n(D)
`92.n(D)
`.
`-
`gt.-AD)
`
`'
`
`-
`
`-
`
`-
`
`
`
`The most convenient means for relating the output of a convo-
`lutional encoder to the input is through the “D transforrn." The D
`transform of a temporal sequence ’?’?’L[},?’I’L1,’P'?/1.2,... ,mk is the poly-
`nonnal mg + 771,113 + mgD3 + -
`-
`- + mkD", where D denotes relative
`delay. Using this simple tool, the outnut of an FIR encoder can be
`written in terms of the input by the matrix equation
`XED) = [x1(D),x2(D). -
`-
`-
`,xnED}}
`._cn,1(D)
`.92,1(D)
`.
`3
`9t..:.£D>
`
`---
`91,2{D)
`92,2ED} “'
`.
`_
`-
`9r,2£D)
`
`=m(D)C(D}
`
`where mi-(D) = Z; m._§.D-F’, etc. The pofynomiaf matrix G£D) is called
`a generator matrix for the encoder. In the FIR case, each term of the
`generator matrix is a polynomial gw{D) = Z;"=0 g,-_,m-D-If of degree
`at most Vp. In Figure 2.1(a),
`
`G(D)=[1+D1’31+t)+D21,
`
`.
`“rhfle
`
`G(D):[1+D2 1+D+D2 0]
`
`1
`
`1
`
`1
`
`corwolutional code is defined in U.I1]C83] as n- (u + 1), in [Wie$}S] it is (,u -'r- 1) and
`in [GCCC81] it is v. For reasons of clarity, we avoid the use of the term entirely in
`this text.
`
`'
`
`.-
`
`_
`i
`-'
`
`?
`
`‘’‘’d
`
`‘‘
`
`pro-
`
`1 be
`aCk_
`omh
`Zmc
`
`'
`
`can
`We
`rm;
`‘
`,
`“Le
`3 of
`{Th
`mt
`
`em-
`5 Vt
`IJI1C
`Jed
`
`tof
`
`

`
`
`
`14
`
`2.1. BASIC DEFINITIONS FOR BCE’S
`
`
`
`CHAPTEI
`
`As a
`
`
`IIR encoders are displayed in Figures 2.l{b), 2.1(c) and 2.2(b).
`
`For these encoders,
`the ‘H. output equations involve both past in-
`puts and past outputs — it follows that the output can depend on
`an infinite number of past inputs. However, as we will subsequently
`discuss, the memory structure of HR encoders, as it pertains to the
`state complexity and total encoder memory {and the memory vector
`{V1,‘V2,- -
`-
`,1/kl) 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 the alge-
`braic theory of BCC‘s [l\/IS68, For70, Pir88J is the discovery that the
`memory structure of a minimal encoder has the memory vector as an
`invariant (i.e., every minimal encoder for a given BCC has the same
`memory vector).
`
`
`
`
`
`in Figure 2.2(a).
`
`
`
`that the
`
`sentedii
`
`generatt
`1) BCC
`true fox
`
`2) enco
`
`page 13
`imal IIR
`
`systems
`chapter
`
`develop
`
`2.2
`
`24 dire:
`states ((
`the dire
`
`o‘(l:2) I
`called t
`states 2
`
`since b-
`two bra
`
`the san
`
`to‘ (E9)
`
`of leng
`branch
`
`U+{bfl
`irreduc
`leads t
`
`A 8
`and the.
`
`All BCE‘s, both FIR and HR, are described by generator matrices
`C(13).
`In the case of an HR encoder, the elements of the generator
`matrix are rational -functions (t'.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),
`
`C(17) = [1
`
`1+D+D2
`l+D2 1.
`
`._
`1+D+D2
`C(17) — ll ‘FD fiml.
`
`U
`
`
`
`G£D)2[1t,E‘5:?2 0 1]@510
`
`in Figure 2.1(c),
`
`and
`
`in Figure 2.2(b).
`
`Note that the definitions of BCC’s and BCE’s are somewhat circu-
`lar. A BCC is defined as the set of output sequences produced by a
`given BCE. However, once a BCC is defined, one can consider the set
`of BCE’s that generate it. For example, a systematic encoder is one
`for which the encoder input (the data) forms a substring of the out-
`put (the codeword). It is important to note that every BCC has both a
`graph
`minimal FIR encoder and a minimal systematic (usually IIR) encoder.
`each h
`
`
`set of E
`
`also la-
`
`the gre
`next p:
`sectior