Neubauer A., Freudenberger J., Kuhn V. Coding theory: algorithms, architectures and applications

Подождите немного. Документ загружается.

196 TURBO CODES

slow, but possible. In comparison with P = (1, 0), we observe a wider tunnel for the

= 5/7 construction. Therefore, the iterative decoding should converge with a smaller

number of iterations. Note that the choice of the partitioning pattern is also important. The

parallel construction with P = (0, 1) gets stuck at values > 0.5. Likewise, the EXIT charts

for the serially concatenated code as well as for R

= 4/5 get instantly stuck, so no bit

error rate reduction is expected at this signal-to-noise ratio. These curves are omitted in

Figure 4.24.

For large interleaver sizes the EXIT chart method allows accurate prediction of the

waterfall region. For interleavers of short or moderate length bounding techniques that

include the interleaving depth are more appropriate, particularly if we also consider the

region of fast convergence, i.e. if we wish to determine possible error ﬂoors.

4.5 Weight Distribution

We have seen in Section 3.3.6 that the performance of a code with maximum likelihood

decoding is determined by the weight distribution, of the code. If we know the weight

distribution, we can bound the word error rate using, for example, the union bound.

However, for concatenated codes, even of moderate length, it is not feasible to evaluate

the complete weight distribution. It is usually not even possible to determine the mini-

mum Hamming distance of a particular code. A common approach in coding theory to

overcome this issue, and to obtain at least some estimate of the code performance with

maximum likelihood decoding, is to consider not particular codes but an ensemble of

codes.

In the context of turbo codes, this approach was introduced by Benedetto and Mon-

torsi (Benedetto and Montorsi, 1998). They presented a relatively simple method for

calculating the expected weight distribution of a concatenated convolutional code from

the weight distributions of the component codes. The expected weight distribution is the

average over the weight distributions of all codes in the considered ensemble, where the

ensemble is deﬁned by the set of all possible interleavers. In this section we will utilise

the concept introduced by Benedetto and Montorsi. (Benedetto and Montorsi, 1998) to

derive the expected weight distribution

for partially concatenated convolutional codes.

Then, we will use

to bound the expected code performance with maximum likelihood

decoding.

4.5.1 Partial Weights

For further consideration of partially concatenated convolutional codes it is necessary not

only to regard the overall weight of the outer encoder output but also the partial weights.

These partial weights distinguish between the weight w

of the code sequence being fed

into the inner encoder and the weight w

of the code sequence not being encoded by the

inner encoder.

By analogy with the extended weight enumerator function discussed in Section 3.3.3,

we introduce the labels W

and W

instead of W so that we can determine the partial

weight enumerator function A

PEF

) as described in Section 3.3.4.

TURBO CODES 197

For further calculations, assuming b

is fed into the inner encoder and b

is not encoded,

the matrix A from the above examples is modiﬁed as

A =







10W

010

0 W







The modiﬁcation of A can be done by introducing labels V

,...,V

which represent the

output weight of each output of the encoder so that A contains polynomials A

,...,V

Then the polynomials

) can be easily obtained by replacing V

(k = 1,...,c)

with W

or W

according to the partitioning scheme. In this context, A

marks the element

in row i and column j of matrix A.

4.5.2 Expected Weight Distribution

Now we derive the expected weight distribution A

for partially concatenated convolu-

tional codes, where

denotes the expected number of code words with weight w.We

restrict ourselves to randomly chosen permutations of length N and terminated convolu-

tional component codes. First, we evaluate the expected number of code words E{A

, ˜w

}

with weight ˜w at the output of the inner encoder conditioned on the weight w

of the partial

outer code sequence v

o,(2)

. Let A

, ˜w

denote the number of code words generated by the

inner encoder with input weight w

and output weight ˜w (Benedetto and Montorsi, 1998).

Let A

denote the number of code words with partial weights w

and w

corresponding

to the outer encoder and its partitioning. We have

E{A

, ˜w



· A

, ˜w





This formula becomes plausible if we note that the term A

, ˜w





is the probability that

a random input word u

to the inner encoder of weight w

will produce an output word b

of weight ˜w. With w =˜w + w

we obtain

= E{A



≤w

E{A

,(w−w

)

This is summarized in Figure 4.25. formula (4.16) can be used for bounding the average

maximum likelihood performance of the code ensemble given by all possible permutations.

Let

denote the expected word error rate and n the overall code length. Using the

standard union bound for the additive white Gaussian noise (AWGN) channel with binary

phase shift keying, we have

≤



w=1

−w·R·E

We consider the codes as given in Figure 4.16. However, for inner encoding we use the inner

rate R

= 1/2 code with generator matrix G

(D) = (1,

1+D

). With code length n = 300

198 TURBO CODES

Expected weight distribution

■ The expected weight distribution A

for a partially concatenated convolu-

tional code is

= E{A



≤w



,(w−w

)



(4.16)

where E{A

, ˜w

} is the expected number of code words with weight ˜w at

the output of the inner encoder conditioned on the weight w

of the partial

outer code sequence.

■ Using the standard union bound for the AWGN channel with Binary Phase

Shift Keying (BPSK), we can bound the expected word error rate

≤



w=1

−w·R·E

(4.17)

Figure 4.25: Expected weight distribution

we obtain similar overall rates R ≈ 1/3. The results for bounding the word error rate by

the union bound in inequality (4.17) are depicted in Figure 4.26. R

= 1 corresponds to

a serially concatenated convolutional code, and R

= 1/2 to a turbo code. For a partially

concatenated code with R

= 4/5 we use a rate R

= 3/5 punctured outer code. With

the partitioning period t

= 1 there exist ﬁve different partitioning schemes. The results

for the schemes with best and worst performance are also given in Figure 4.26. The per-

formance difference between P = (1, 1, 1, 1, 0) and P = (0, 1, 1, 1, 1) indicates that the

particular choice of the partitioning scheme is important. In this example the partially con-

catenated code with P = (0, 1, 1, 1, 1) outperforms the serially and parallel concatenated

constructions.

4.6 Woven Convolutional Codes

In this section we concentrate on the minimum Hamming distance of the constructed con-

catenated code. With respect to the minimum Hamming distance of the concatenated code,

especially for codes of short lengths, the choice of the particular interleaver is very impor-

tant. With turbo-like codes, the use of designed interleavers is motivated by the asymptotic

coding gain, which is the gain in terms of transmit power that can be achieved with coding

compared with the uncoded case for very low residual error rates. For unquantised channels

the asymptotic coding gain is (Clark and Cain, 1988)

= 10 log

(R · d)dB,

TURBO CODES 199

Union bound on the word error rate

2 3 4 5 6 7 8

Ŧ6

Ŧ5

Ŧ4

Ŧ3

Ŧ2

Ŧ1

WER

=4/5, P=(1,1,1,1,0)

=4/5, P=(0,1,1,1,1)

=1/2, P=(1,0)

=1, P=(1,1,1)

Figure 4.26: Union bound on the word error rate for rate R = 1/3 codes (code length

n = 300) with different partial rates (cf. Figure 4.16)

where R is the rate and d is the minimum Hamming distance of the code. This formula

implies that for ﬁxed rates the codes should be constructed with minimum Hamming dis-

tances as large as possible, in order to ensure efﬁcient performance for high signal-to-noise

ratios.

We start our discussion by introducing the class of woven convolutional codes. Woven

code constructions yield a larger designed minimum Hamming distance than ordinary

serial or parallel constructions. In the original proposal (H

ost et al., 1997), two types

of woven convolutional code are distinguished: those with outer warp and those with

inner warp. In this section we consider encoding schemes that are variations of woven

codes with outer warp. We propose methods for evaluating the distance characteristics of

the considered codes on the basis of the active distances of the component codes. With

this analytical bounding technique, we derive lower bounds on the minimum (or free)

distance of the concatenated code. These considerations also lead to design criteria for

interleavers.

Note that some of the ﬁgures and results of this section are reprinted, with permission,

from Freudenberger et al. (2001),  2001 IEEE.

200 TURBO CODES

4.6.1 Encoding Schemes

With binary woven convolutional codes, several convolutional encoders are combined in

such a way that the overall code is a convolutional code. The basic woven convolutional

encoder with outer warp is depicted in Figure 4.27. It consists of l

outer convolutional

encoders which have the same rate R

= k

and a single inner encoder.

The informa-

tion sequence u is divided into l

subsequences u

with l = 1,...,l

. These subsequences

are encoded with the outer encoders. The resulting outer code sequences b

,...,b

are

written row-wise into a buffer of l

rows. The binary code bits are read column-wise from

this buffer. The resulting sequence constitutes the input sequence u

of the single inner rate

= k

convolutional encoder. After inner encoding, we obtain the ﬁnal code sequence

b of the Woven Convolutional Code (WCC). The resulting woven convolutional code has

overall rate R = R

Woven encoder with outer warp

outer encoder

inner encoder

■ A woven convolutional encoder with outer warp consists of l

outer convo-

lutional encoders that have the same rate R

= k

■ The information sequence u is divided into l

subsequences u

with l =

1,...,l

■ The outer code sequences b

,...,b

are written row-wise into a buffer

of l

rows. The binary code bits are read column-wise and the resulting

sequence constitutes the input sequence u

of the single inner rate R

convolutional encoder.

■ The resulting woven convolutional code has the overall rate

R = R

Figure 4.27: Woven encoder with outer warp

In contrast, a woven encoder with inner warp has a single outer and several inner encoders.

TURBO CODES 201

Woven turbo encoder

o,(1)

o,(2)

o,(1)

o,(2)

o,(1)

o,(2)

outer encoder

inner encoder

■ The overall woven turbo code has the rate

R =

+ R

(1 − R

)

where R

is the fraction of outer code bits that will be encoded by the inner

encoder.

■ The partitioning of the outer code sequences into two partial code

sequences b

o,(1)

and b

o,(2)

is described by means of a partitioning matrix P.

Figure 4.28: Woven turbo encoder

The concept of partial concatenation as discussed in Section 4.3.4 was ﬁrst introduced

by Freudenberger et al. (Freudenberger et al., 2000a, 2001) in connection with woven turbo

codes. Woven turbo codes belong to the general class of woven convolutional codes.

Figure 4.28 presents the encoder of a Woven Turbo Code (WTC). Like an ordinary woven

encoder, a woven turbo encoder consists also of l

outer convolutional encoders and one

inner convolutional encoder. The information sequence u is subdivided into l

sequences

which are the input sequences to the l

rate R

= k

outer encoders.

Parts of the symbols of the outer code sequences (b

o,(1)

), which are located in the same

bit positions, are multiplexed to the sequence u

. The sequence u

is the input sequence

of the inner encoder. The other symbols of the outer code sequences (b

o,(2)

, dashed lines

in Figure 4.28) are not encoded by the inner encoder. These sequences b

o,(2)

form the

sequence b

o,(2)

which, together with the inner code sequence b

, constitutes the overall

code sequence b.

As with partially concatenated codes, the partitioning of the outer code sequences into

two partial code sequences b

o,(1)

and b

o,(2)

is described by means of a partitioning matrix

P. Furthermore, the overall code rate is

R =

+ R

(1 − R

)

202 TURBO CODES

Woven encoder with row-wise interleaving

outer encoder

inner encoder

Figure 4.29: Woven encoder with row-wise interleaving

where R

is the fraction of outer code bits that will be encoded by the inner encoder as

deﬁned in Section 4.3.4.

Up to now, we have only considered woven constructions without interleavers. These

constructions lead to overall convolutional codes. Usually, when we employ interleaving,

we use block-wise interleavers and terminated convolutional codes so that the resulting

concatenated code is actually a block code. This is possibly also the case with woven

codes for most applications.

However, there are a number of interesting aspects of the construction without inter-

leaving, e.g. a sliding window decoding algorithm for WCC can be introduced (Jordan

et al., 2004a). This algorithm requires no code termination and might be interesting for

applications where low-latency decoding is required. In the following we will mainly con-

sider constructions with interleaving, in particular row-wise interleaving as indicated in

Figure 4.29. Here, each outer code sequence b

is interleaved by arbitrary and independent

interleavers. The interleaved sequences are fed into the inner encoder. Of course, the same

interleaver concept can also be applied to woven turbo codes.

4.6.2 Distance Properties of Woven Codes

Now, we investigate the distance properties of the considered codes on the basis of the

active distances of the component codes. With this analytical bounding technique, we derive

lower bounds on the minimum (or free) distance of the concatenated code.

Below, we deﬁne the generating tuples of an input sequence u(D) of a convolutional

encoder. Then, we show that each generating tuple generates at least d

non-zero bits in

the encoded sequence b(D), where d

is some weight in the region β

≤ d

free

Consider a convolutional encoder and its active burst distance (cf. Section 3.3.2 on

page 122). We call a segment of a convolutional code sequence burst if it corresponds to

an encoder state sequence starting in the all-zero state and ending in the all-zero states

and having no consecutive all-zero states in between which correspond to an all-zero input

TURBO CODES 203

Generating tuples

■ Let d

be an integer with β

≤ d

free

. We deﬁne the generating length

for d



− β



(4.18)

i.e. j

is the minimum j for which the lower bound on the active burst

distance satisﬁes αj + β

≥ 2d

■ Let t

be the time index of the ﬁrst non-zero tuple u

= (u

(1)

(2)

,...,u

(k)

)

of the sequence u.Lett

be the time index of the ﬁrst non-zero tuple with

≥ t

+ j

, and so on. We call the information tuples u

, u

,...generating

tuples.

■ Let u be the input sequence of a convolutional encoder with N

generating

tuples with generating length j

. Then the weight of the corresponding

code sequence b satisﬁes

wt(b) ≥ N

(4.19)

Figure 4.30: Deﬁnition of generating tuples

tuple of the encoder. Note that a burst of length j + 1 has at least weight a

(j), where

length is deﬁned in n-tuples and the corresponding number of bits is equal to n(j + 1).

For an encoder characterised by its active burst distance, we will now bound the weight

of the generated code sequence given the weight of the corresponding information sequence.

Of course, this weight of the code sequence will depend on the distribution of the 1s in the

input sequence. In order to consider this distribution, we introduce the notion of generating

tuples as deﬁned in Figure 4.30. Let d

be an integer satisfying β

≤ d

free

. Remember

that d

free

is the free distance of the code and β

is a constant in the lower bound of the

active burst distance deﬁned in Equation (3.11). We deﬁne the generating length for d



− β



where α is the slope of the lower bound on the active distances. The generating length j

is the minimum length j for which the lower bound on the active burst distance satisﬁes

αj +β

≥ 2d

, i.e. j

is the length of a burst that guarantees that the burst has at least

weight 2d

Now consider an arbitrary information sequence u. We call the ﬁrst non-zero k-tuple

= (u

(1)

(2)

,...,u

(k)

) a generating tuple, because it will generate a weight of at least

free

in the code sequence b. But what happens if there are more non-zero input bits? Now

the deﬁnition of the generating tuples comes in handy. Let t

be the time index of the ﬁrst

204 TURBO CODES

generating tuple, i.e. of the ﬁrst non-zero tuple u

= (u

(1)

(2)

,...,u

(k)

) in the sequence u.

Moreover, let t

be the time index of the ﬁrst non-zero tuple with t

≥ t

+ j

, and so on.

We call the information tuples u

, u

,... generating tuples. If the number of generating

tuples is N

, then the weight of the code sequence is at least N

· d

Why is this true? Consider an encoder with generating length j

according to Equation

(4.18). The weight of a burst that is started by a generating tuple of the encoder will be

at least d

free

if the next generating tuple enters the encoder in a new burst, and at least

if the next generating tuple enters the encoder inside the burst. This approach can be

generalised. Let N

denote the number of generating tuples corresponding to the ith burst.

For N

= 1 the weight of the ith burst is greater or equal to d

free

, which is greater or equal

to d

. The length of the ith burst is at least (N

− 1)j

+ 1 for N

> 1 and we obtain

wt(burst

) ≥˜a



− 1)j



≥ α(N

− 1)j

+ β

With Equation (4.18) we have αj

≥ 2d

− β

and it follows that

wt(burst

) ≥ (N

− 1)(2d

− β

) + β

≥ N

+ (N

− 2)(d

− β

Taking into account that d

≥ β

, i.e. d

− β

≥ 0, we obtain

wt(burst

) ≥ N

∀ N

≥ 1.

Finally, with N

we obtain

wt(b) ≥



wt(burst

) ≥



= N

We will now use this result to bound the free distance of a WCC. Consider the encoder

of a woven convolutional code with outer warp as depicted in Figure 4.29. Owing to the

linearity of the considered codes, the free distance of the woven convolutional code is given

by the minimal weight of all possible inner code sequences, except the all-zero sequence.

If one of the outer code sequences b

is non-zero, then there exist at least d

free

non-

zero bits in the inner information sequence. Can we guarantee that there are at least d

free

generating tuples? In fact we can if we choose a large enough l

. Let d

be equal to the free

distance d

free

of the inner code. We deﬁne the effective length of a convolutional encoder

eff

= k



free

− β



Let l

eff

be the effective length of the inner encoder. If l

≥ l

eff

holds and one of the

outer code sequences b

is non-zero, then there exist at least d

free

generating tuples in

the inner information sequence that generate a weight greater or equal to d

free

. Conse-

quently, it follows from inequality (4.19) that d

WCC

free

≥ d

free

. This result is summarised

in Figure 4.31.

TURBO CODES 205

Free distance of woven convolutional codes

■ We deﬁne the effective length of a convolutional encoder as

eff

= k



free

− β



(4.20)

■ Let l

eff

be the effective length of the inner encoder. The free distance of the

WCC with l

≥ l

eff

outer convolutional encoders satisﬁes the inequality

WCC

free

≥ d

free

(4.21)

Figure 4.31: Free distance of woven convolutional codes

For instance, let us construct a woven encoder employing l

outer codes. For outer

codes we use the punctured convolutional code deﬁned in Section 3.1.5 with the generator

matrix

(D) =



1 + D 1 + D 1

D 01+ D



This code has free distance d

free

= 3. The generator matrix of the inner convolutional

code is G

(D) = (1,

1+D

1+D+D

), i.e. d

free

= 5. The lower bound on the active burst distance

of the inner encoder is given by ˜a

b,i

(j) = 0.5j + 4 and we have l

eff

= 12. Then, with

= l

eff

= 12, we obtain the free distance d

WCC

free

= 15. The rate of the overall code is

R = R

4.6.3 Woven Turbo Codes

We will now analyse the free distance of a woven turbo code. In Section 4.6.2 we have

used the concept of generating tuples and the fact that any non-zero outer code sequence

in a woven convolutional encoder has at least weight d

free

With woven turbo codes, however, the number of non-zero bits encoded by the inner

encoder will be smaller than d

free

. We will now deﬁne a distance measure that enables us

to estimate the free distance in the case of partitioned outer code sequences. We call this

distance measure the partial distance.

The partitioning matrix P determines how a code sequence b is partitioned into the two

sequences b

(1)

and b

(2)

. Note that, using the notion of a burst, we could deﬁne the free

distance as the minimum weight of a burst. Analogously, we deﬁne the partial distance as

the minimum weight of partial code sequence b

(2)

[0,j]

. However, we condition this value on

the weight of the partial code sequence b

(1)

[0,j]

. The formal deﬁnition is given in Figure 4.32.