`
`i
`
`Apple 1020
`
`
`
`GNIDOCOBRUT
`
`ii
`
`
`
`Chris Heegard
`Alantro Communications, Inc.
`
`and Cornell University
`
`Stephen B. Wicker
`Cornell University
`
`KLUWER ACADEMIC PUBLISHERS
`Boston / Dordrecht / London
`
`iii
`
`
`
`Distributors for North, Central and South America:
`Kluwer Academic Publishers
`
`101 Philip Drive
`Assinippi Park
`Norwell, Massachusetts 02061 USA
`Telephone (7 8 1) 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>
`
`I 5-‘ Electronic Services <http://www.wl<ap.nl>
`'53‘
`
`Library of Congress Cataloging—in-Publication Data
`
`A C.I.P. Catalogue record for this book is available
`fi"om the Library of Congress.
`
`5: §Copyright © 1999 by Kluwer Academic Publishers
`
`rights reserved. No part of this publication may be reproduced, stored in a
`.p retrieval system or transmitted in any form or by any means, mechanical, photo-
`, Wfcopying, recording, or otherwise, without the prior written permission of the
`publisher, Kluwer Academic Publishers, 101 Philip Drive, Assinippi Park, Norwell,
`Massachusetts 02061
`
`Printed on acid—free paper.
`
`Printed in the United States of America
`
`iv
`
`
`
`2.]. BASIC DEFINITIONS FOR BCE’S
`
`CHAPTER 2.
`
`HR
`(3)
`Systematic
`
`Non-
`
`(b) HR, Systematic
`
`HR.’
`(C)
`Systematic
`
`Figure 2.1: Rate 1/2 (rt = 2, k = 1) Encoders
`
`A Binary Convolational 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
`Finite Impulse Response (FIR) (also called “feed-forward”, “feedback-
`free”, or “non—recarsive”) or Infinite Impulse Response (HR) (“feed-
`back” or “recursive ”). Also, a BCE can be systematic or non—systemat1‘c.
`
`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 {glmg} relates a particular input sequence
`{ml‘} to a particular output sequence {xi }. A particular Value of
`gm‘; denotes the presence or absence of a tap connecting the lth
`memory element of the ith input shift register to the nth output.
`The rt output equations have the form
`
`k
`Vi
`p
`.
`xi = 2 2 gt-,p,;m;._l,
`i=1l=0
`
`1 5 p s n
`
`The memory for each of the k inputs is enumerated by the mem-
`ory vector (1/1,1/2, -
`-
`- ,vk) (i.e.
`the ith input shift register has vi
`memory elements ). It is assumed that for each i there is at least one
`p with gt-lpyvl. = 1. The state complexity of the encoder is determined
`by the total encoder memory v 2 V1 + V2 + -
`-
`- + vk. The number of
`states in the encoder is 2*’, while the window length is determined by
`the memory order1 it = maxlsisk vi.
`
`1The terminology in the literature is inconsistent; the constraint length of a
`
`The mos
`
`lutional enc
`transform 0
`
`:m(
`
`where m1:(D
`
`a generator
`
`generator In
`
`at most Vp-
`
`convolutional
`in [GCCC81l i
`this text.
`
`
`
`CHAPTER 2.
`
`BINARY CODES, GRAPHS, AND TRELLISES
`
`(3)
`
`'
`FIR, N —
`on Systemauc
`
`(b) IIR, Systematic
`
`Figure 2.2: Rate 2/3 (TL = 3,k = 2) Encoders
`
`The most convenient means for relating the output of a convo-
`lutional encoder to the input is through the “D transform.” The D
`transform of a temporal sequence 7’I’LQ,7’}’l1,’}’I’L2, . .. ,mk is the poly-
`nomial mo + m1D + m2D2 + -
`-
`- + mkD", where D denotes relative
`delay. Using this simple tool, the output of an FIR encoder can be
`written in terms of the input by the matrix equation
`
`X(D)
`
`[x1(D),x2(D),- -
`
`- ,xn(D)l
`
`91,1(D)
`92,1(D)
`;
`
`91,2(D)
`92,2(D)
`:
`
`-" 91,n(D)
`-
`-
`'
`92,n(D)
`.,
`I
`
`9k,1(D)
`
`9k,2(D)
`
`-
`
`'
`
`'
`
`9k,'n(D)
`
`tm1<D>,—--,mk<D>1
`
`m(D)G(D)
`
`where mi(D) = 21 m§Dj, 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,,7(D) = £0 gt-‘WADJ of degree
`at most Vp. In Figure 2.1(a),
`
`G(D) =[1+D2 1+D+D2],
`
`1
`
`C(13): [1+D2 1+o+o2 0}
`
`1
`
`1
`
`convolutional code is defined in [LDJC83] as n- (u + 1), in [Wic9S] it is (11 + 1) and
`in [GCCC81] it is v. For reasons of clarity, we avoid the use of the term entirely in
`this text.
`
`
`
`14
`
`2.]. BASIC DEFINITIONS FOR BCE’S
`
`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 number of 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 memory vector
`(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 the alge-
`braic theory of BCC’s [MS68, For70, Pir88] 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).
`
`All BCE’s, both FIR and IIR, are described by generator matrices
`G(D).
`In the case of an HR 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),
`
`in Figure 2.l(c),
`
`C(13) = [1
`
`1+D+D2
`
`1+D2
`
`l,
`
`G(D)=l1+D
`
`1+D+D2
`1+D
`
`l,
`
`1“
`
`11- "
`
`cm) ["2 1 J
`
`O
`
`1
`
`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
`minimal FIR encoder and a minimal systematic (usually IIR) encoder.