# The art of error correcting coding - Moreloz R.H.

ISBN 0471-49581-6

**Download**(direct link)

**:**

**36**> 37 38 39 40 41 42 .. 86 >> Next

(5.4)

where the blank entries represent zeros. Generalization to any rate 1 /n encoder is straightforward.

Example 51 For the memory-2 rate-1/2 encoder in Figure 29,

/11 10 11 11 10 11 11 10 11 11 10 11

G =

\

Let u = (110100). Then it follows from (5.3) that v = uG = (11,01.01,00.10,11), which is the same output as in Example 50.

Let v(D) = v^(D) + Dv^(D) + ? ? + Dn~1v^n~1\D). Then the relationship between input and output sequences can be written as

v{D) = u{D)G(D),

(5.5)

where generators of a rate-l/n convolutional code are arranged in a matrix, referred to as a polynomial generator matrix,

G(D) = (g0{D) g,{D)

Qni {D)).

(5.6)

78

THE ART OF ERROR CORRECTING CODING

5.1.1 Recursive systematic convolutional codes

With the use of (5.6), a memory-m rate-1 /n recursive systematic convolutional code, or RSC code, has a generator matrix of the form

As a short notation of this generator matrix, the generators {l,gi/go, ?, gn-i /fin) can be specified. Division and multiplication of the right-hand side of (5.5) by go(D) give, together with (5.6),

where u'(D) = go(D)u(D). This shows that both the nonsystematic encoder and the systematic encoder produce the same coded sequences, but that the corresponding information sequences are scrambled by go (D) in the RSC code.

A systematic encoder is also an example of a discrete-time linear time-invariant system. Because the generator matrix contains rational functions, the encoder is an infinite-impulse-response (HR) linear system, as opposed to a non-systematic encoder which is a finite impulse response (FIR) linear system. The preferred form of expressing the encoder circuit is the controller canonical form [For4]. An encoder for an RSC code, consists of a shift registers, a circuit3 for dividing by go{D) and n 1 circuits for multiplying by gi(D), , gn-i(D).

Example 52 A rate-1/2 memory-2 binary RSC encoder with generators (1,5/7) is shown in Figure 34. The trellis structure of this code is the same as the nonsystematic code with generators (7,5). However the input/output bits per transition are different. The state diagram of this code is shown in Figure 35. Compare with Figure 30 on page 75. Among other things, this difference in input/ouput mapping means that the all-zero sequence may not necessarily bring the state back to .sq.s i = 00. This is evident from Figure 35. In particular, the impulse response of this encoder is (11,01.01,00,01,01,00,01,01,00, ? ).

(5.7)

v(D) =u'(D)G'(D).,

(5.8)

u

<+>

U(4>

s

<?)-

Figure 34 Encoder of a memory-2 rate-1/2 recursive systematic convolutional encoder.

3 The general structure of circuits that multiply and divide by two polynomials can be found, among others, in [PW], Figure 7.8, or [LC], Sec. 4.7.

BINARY CONVOLUTIONAL CODES

79

Figure 35 State diagram of a memory-2 rate-1/2 recursive systematic convolutional encoder.

5.1.2 Free distance

The free distance d/ of a convolutional code is the smallest distance between any two distinct code sequences. The length of the sequences has to be sufficiently large, much larger than the constraint length of the code. The free distance of a convolutional code can be obtained from its weight enumerator polynomial, as described in Section 5.3. There are other distances associated with a convolutional code, when the length of the sequence is of the order of the constraint length, but these are not relevant for the discussion in this book. More details on the structure of a general rate-k/n convolutional encoder can be found in references [LC] and [Joh],

5.2 Connections with block codes

There is a connection between convolutional codes and block codes, as it is evident from the above description of convolutional encoders. As indicated previously, it is customary for the information sequences input to a convolutional encoder to be broken into blocks of finite length (e.g. a few thousands of bits). Generally, a fixed sequence of length m is appended at the end of each information sequence. This sequence is typically a unique word that serves to synchronize the receiver and forces the convolutional encoder to return to a known state.

In the following, for simplicity of exposition, let C be a nonsystematic (FIR) convolutional code C with free distance df, obtained from a memory-m rate-l/n convolutional encoder. Similar arguments apply to RSC codes.

5.2.1 Zero-tail construction

By appending a tail of m zeros to an information vector u of length (K m), all paths in the trellis corresponding to 2K~m codewords merge at the all-zero state. The result is a linear block (nK, (K m), dzr ) code, denoted by C'zt If K is large enough, then the rate of C'zt approaches the rate of C. As long as K > m holds, with K sufficiently large, even though the code sequences are restricted to end at the all-zero state, the minimum distance of C'zt satisfies dzT = df.

Example 53 Let C be the convolutional code obtained from the rate-1/2 memory-2 encoder in Figure 29, of free distance4 df = 5. Assume that message vectors of length K = 3 bits are encoded, each followed by m = 2 zeros. Then the zero-tail construction results in a binary

**36**> 37 38 39 40 41 42 .. 86 >> Next