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

ISBN 0471-49581-6

**Download**(direct link)

**:**

**42**> 43 44 45 46 47 48 .. 86 >> Next

sf] -> sf’ -f si2) -> si1] -> 5|3) s)2) -> 5q0)-

From this sequence, the corresponding information sequence can be recovered, by reversing the state transitions: ? = ( 1 1 0 1 0 0).

For high-speed continuous VD operation with the traceback method, the traceback memory must be partitioned into several blocks. In this way, while one block is being written with decisions at the current stage i, another block is read (decoded) at a time i — L, L > ?, and another (possibly more than one) block for intermediate stages is used for performing

94

THE ART OF ERROR CORRECTING CODING

advance

Figure 47 Channel error rate estimation for a BSC channel.

Table 3 Tracing back the path that ended in state S,(0 ].

k i = l i = 2 i = 3 i = 4 i = 5 i — 6

0 0 1 1 0 0 1

1 0 1 1 0 0 1

2 0 1 1 1 0 0

3 1 0 0 1 1 1

traceback tracing. This memory partitioning improves speed but increases the latency (or decoding delay) of the decoder [Col, BABSZ].

ACS

For memory-m rate-1 jn binary convolutional codes codes, the basic trellis element is a butterfly, as shown in Figure 48. The add-compare-select (ACS) operation is implemented using this structure over 2m_1 pairs, i.e., j = 0,1,2, • • •, 2m_1 — 1. Therefore, the ACS operation can be done either serially (a loop on j in software) or in parallel, with 2m~1 ACS units, one per butterfly. If the code is antipodal then the generators of the code have a one in the first and last positions. In this case, the labels of the branches incident to a state S(2j> are the same as those incident to state S(2j+l! in a butterfly. Moreover, the label of a branch incident to a state S-2j l is equal to the complement of the label of the other branch8. Using these facts, a clever technique [FL2] based on branch metric differences was proposed. For rate-1 /n codes, the result is a Viterbi decoder with a compare-add-select (CAS) architecture, and lower complexity of implementation than the conventional ACS approach.

5.5 Punctured convolutional codes

Punctured convolutional codes were introduced in [Cla], Puncturing is the process of systematically deleting, or not sending, some output bits of a low-rate encoder9. Since the trellis structure of the low-rate encoder remains the same, the number of information bits per sequence does not change. As a result, the output sequences belong to a higher-rate punctured convolutional (PC) code. The following discussion focuses on codes obtained from a binary

8 The complement of a bit a is 1 + a mod 2.

9 Sometimes referred to as the mother code.

BINARY CONVOLUTIONAL CODES

95

Figure 48 Trellis butterfly of a memory-m rate-1 jn binary convolutional code, memory-m rate-1 /n convolutional code.

Figure 49 Encoder of a punctured code based on a rate-1 /n code.

A puncturing matrix P specifies the rules of deletion of output bits. P is a k x np binary matrix, with binary symbols pij that indicate whether the corresponding output bit is transmitted (pij = 1) or not (pij = 0). Generally, the puncturing rule is periodic. A ratek/np PC encoder based on a rate-1 /n encoder, has a puncturing matrix P that contains I zero entries, where np = kn — I, 0 < i < kn.

Example 65 A rate-2/3 memory-2 convolutional code can be constructed by puncturing the output bits of the encoder of Figure 29, according to the puncturing matrix

P=(X 1 ^10

The corresponding encoder is depicted in Figure 50. A coded sequence

v — \ -vi vi -vi+lVi+l-Vi+2vi+2-Vi+3Vi+3- )

of the rate-1/2 encoder is transformed into code sequence

r. (0) (1) (0) (0) (1) (0) _ V

VP — \ -.vi vi ?vi+l-vi+2vi+2-vi+3- >?

i.e., every other bit of the second output is not transmitted.

One of the goals of puncturing is that the same decoder can be used for a variety of high-rate codes. One way to achieve decoding of a PC code using the Viterbi decoder of the low-rate code, is by the insertion of “deleted” symbols in the positions that were not sent. This process is known as depuncturing. The “deleted” symbols are marked by a special flag. This can be done, for example, using an additional bit and setting it to 1 in the position of an erased bit. If

96 THE ART OF ERROR CORRECTING CODING

111001 1X1X0X

v = (11,01,01,00,10,11) 12outputbits—rate-1/2

v= (11,0,01,0,10,1) 9 output bits —rate-2/3

Figure 50 Encoder of a rate-2/3 memory-2 PCC.

Table 4 Puncturing matrices for the de-facto standard rate-1/2 code.

Rate

Pattern

Coded sequence

df

1/2

2/3

3/4

5/6

7/8

1 1

1 0 1 1 1 0 1 1 1 1 0 1 110 10 1 0 0 0 1 0 1 11110 10

0

0 1

(0) (1) v) .v)

V- ,v

,V.

i+1

^(0)^(1) „(1) „(0)

J°) w(l) „(1) JO) J!) J°)

Ui -Vi ' °i+1: Ui+2 i vi+3 : j+4

«(0) t;(1) «(1) w(1) i)(1) w(0) v{1) v{0)

Vi -Vi ' Vi+1 • Vi+2 ? Vi+3 ? vi+4 • Vi+5 ? Vi+6

10

6

5

4

3

a position is flagged, then the corresponding received symbol is not taken into account in the branch metric computation10.

In a software implementation, an alternative method is for the decoder to check the entries pmj of matrix P in the transmission order, m = 0,1. ? ? ?. n — 1, j = i, i + 1, • • •. i + k — 1. If Pm,j = 0, then the current received symbol is not used to update the branch metric. The decoder advances a pointer to the next branch symbol in the trellis and repeats the test on pm,j- Otherwise, pm,j = 1 and the received symbol are used to update the branch metric. Every time the branch pointer is advanced, a check is made to determine if all the symbols in that branch have been processed. If they have, then the ACS operation is performed. This method is used in some of the programs that implement Viterbi decoding of PC codes on the ECC web site.

**42**> 43 44 45 46 47 48 .. 86 >> Next