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

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

186 TURBO CODES

Partially concatenated convolutional encoder

o,(1)

o,(2)

outer encoder

inner encoder

■ The partial rate R

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

the inner encoder

s,j

(4.10)

■ The rate of the overall code is

R =

+ R

(1 − R

)

(4.11)

where R

and R

are the rate of the inner code and outer code respectively.

■ R

= 1 results in a serially concatenated convolutional code.

■ R

= R

and systematic outer and inner encoding result in a parallel

concatenated convolutional code.

Figure 4.15: Partially concatenated convolutional encoder

constructed in Figure 4.16. Those codes are all of overall rate R = 1/3, but with different

partial rates. There are classical parallel R

= 1/2 and serially concatenated convolutional

codes R

= 1, as well as partially concatenated convolutional codes.

4.3.5 Turbo Decoding

All turbo-like codes can be decoded iteratively with a message-passing algorithm similar

to belief propagation. The iterative decoding is based on symbol-by-symbol soft-in/soft-out

(SISO) decoding of the component codes, i.e. algorithms that use reliability information

at the input and provide reliability information at the output, like the BCJR algorithm

which evaluates symbol-by-symbol a-posteriori probabilities. For the following discussion,

all symbol reliabilities are represented by log-likelihood ratios (L-values).

We consider only the decoder structure for partially concatenated codes as given in

Figure 4.17. Decoders of parallel and serial constructions can be derived as special cases

from this structure. The inner component decoder requires channel L-values as well as

TURBO CODES 187

Example of concatenated convolutional codes

■ We construct different concatenated codes of overall rate R = 1/3. For

the inner encoding we always employ rate R

= 1/2 codes with generator

matrix G

(D) = (1,

1+D

1+D+D

■ For outer encoding we employ the mother code with generator matrix

G(D)= (1 +D + D

, 1 + D

), but we apply puncturing and partitioning to

obtain the desired overall rate.

■ We consider:

– Two parallel concatenated codes: both with partial rate R

= R

= 1/2,

but with different partitioning schemes (P = (1, 0), P = (0, 1) ).

– A serially concatenated code with R

= 1, R

= 2/3.

– Two partially concatenated constructions with R

= 3/5, R

4/5 and P = (0, 1, 1, 1, 1) and with R

= 4/7, R

= 5/7 and P =

(1, 1, 0, 1, 1, 0, 1). Note that here the partitioning matrices are obtained

by optimising the partial distances (see Section 4.6.2).

Figure 4.16: Example of concatenated convolutional codes

a-priori information for the inner information symbols as an input. The output of the inner

decoder consists of channel and extrinsic information for the inner information symbols.

The outer decoder expects channel L-values and provides extrinsic L-values L

) for

the outer code symbols and estimates

u for the information symbols. Initially, the received

sequence r is split up into a sequence r

(1)

which is fed into the inner decoder and a sequence

(2)

which is not decoded by the inner decoder. Moreover, the a-priori values for the inner

decoder L

) are set to zero.

For each iteration we use the following procedure. We ﬁrst perform inner decoding. The

output symbols L(u

) of the inner decoder are de-interleaved (π

−1

). This de-interleaved

sequence and the received symbols r

(2)

are multiplexed according to the partitioning scheme

P. The obtained sequence L(r

) is regarded as the channel values of the outer code,

i.e. it is decoded by the outer decoder. The outer decoder provides extrinsic L-values

for the outer code bits L

) and an estimated information sequence ˆu. For the next

round of iterative decoding, the extrinsic output L

) is partitioned according to P into

o,(1)

) and L

o,(2)

), whereas the sequence L

o,(2)

) is not regarded any more, because

o,(2)

was not encoded by the inner encoder. L

o,(1)

) is interleaved again such that the

resulting sequence L

) can be used as a-priori information for the next iteration of inner

decoding.

Finally, we give some simulation results for the AWGN channel with binary phase shift

keying. All results are obtained for ten iterations of iterative decoding, where we utilise the

188 TURBO CODES

Decoding structure

For each iteration we use the following procedure:

■ Perform inner decoding. The output symbols L(u

) of the inner decoder

are de-interleaved (π

−1

), and the received symbols r

(2)

are multiplexed

according to the partitioning scheme P.

■ The obtained sequence L(b

) is decoded by the outer decoder. The

extrinsic output L

) is partitioned according to P into L

o,(1)

) and

o,(2)

),whereL

o,(2)

) is discarded.

■ L

o,(1)

) is interleaved again such that the resulting sequence L

) can

be used as a priori information for the next iteration of inner decoding.

inner decoder

outer decoder

L(u

)

o,(1)

)

o,(2)

)

L(r

)

(1)

(2)

−1

Figure 4.17: Decoding structure

max-log version of the BCJR algorithm as discussed in Section 3.5.2. Simulation results

are depicted in Figure 4.18, where the ﬁgures presents the Word Error Rate (WER) for

codes of length n = 600 or n = 3000 respectively. The component codes are as given in

Figure 4.16. The two partially concatenated codes outperform the serial concatenated code

for the whole considered region of WER. At high SNR we notice the typical error ﬂoor

of the turbo code (P = (1, 0)). Here, the partially concatenated codes achieve signiﬁcantly

better performance. Simulation results regarding the bit error rate are similar.

4.4 EXIT Charts

For the analysis of the iterative decoding algorithm we utilise the EXtrinsic Information

Transfer (EXIT) characteristics as proposed by ten Brink (ten Brink, 2000; see also ten

Brink, 2001). The basic idea of the EXIT chart method is to predict the behaviour of

TURBO CODES 189

Simulation results

■ The ﬁgure depicts word error rates (WER) for n = 600 and n = 3000 respect-

ively.

0 1 2 3

Ŧ4

Ŧ3

Ŧ2

Ŧ1

WER

=1/2

=5/7

=4/5

0 0.5 1 1.5 2

Ŧ4

Ŧ3

Ŧ2

Ŧ1

WER

=1/2

=5/7

=4/5

Figure 4.18: Simulation results

the iterative decoder by looking at the input/output relations of the individual constituent

decoders.

4.4.1 Calculating an EXIT Chart

We assume that a-priori information can be modelled by jointly independent Gaussian

random variables. The decoder can then be characterised by its transfer function where

the mutual information at the output is measured depending on the a-priori information

and the channel input. All considerations are based on the assumptions in Figure 4.19.

These assumptions are motivated by simulation results, which show that with large inter-

leavers the a priori values remain fairly uncorrelated from the channel values. More-

over, the histograms of the extrinsic output values are Gaussian-like. This is indicated

in Figure 4.20 which depicts the distribution of the L-values at the input and output of

the Soft-Input Soft-Output (SISO) decoder. For this ﬁgure we have simulated a transmitted

190 TURBO CODES

Basic assumptions of the EXIT charts method

(1) The a-priori values are independent of the respective channel values.

(2) The probability density function p

(·) of the extrinsic output values is the

Gaussian density function.

(3) The probability density function p

(·) fulﬁls the symmetry condition (Divsalar

and McEliece, 1998)

(ξ|X = x) = p

(−ξ |X = x) · e

xξ

(4.12)

where the binary random variable X denotes a transmitted symbol (either

outer code symbol or inner information symbol) with x ∈{±1}.

Figure 4.19: Basic assumptions of the EXIT charts method

Distribution of L-values before and after decoding

Ŧ5 0 5 10 15 20 25

0.05

0.1

decoder input

decoder output

relative frequency

L-value

Figure 4.20: Distribution of the L-values at the decoder input and output

TURBO CODES 191

all-zero code sequence of the (75) convolutional code over a Gaussian channel with binary

phase shift keying. The Gaussian distribution of the input values is a consequence of

the channel model. The distribution of the output L-values of the SISO decoder is also

Gaussian-like. Note that the area under the curve on the right of the axis L = 0 determines

the bit error rate. Obviously, this area is smaller after decoding, which indicates a smaller

bit error rate.

4.4.2 Interpretation

Let L

denote the a-priori L-value corresponding to the transmitted symbol X . Based on

the assumptions in Figure 4.19, the a-priori input of the SISO decoders is modelled as

independent random variables

= µ

· X +N

where µ

is a real constant and N

is a zero-mean Gaussian distributed random variable

with variance σ

. Thus, the conditional probability density function of the a-priori L-values

(ξ|X = x) =

√

2πσ

−

(ξ−µ

2σ

Moreover, the symmetry condition (4.12) implies

The mutual information I

= I(X ;L

) between the transmitted symbol X and the corres-

ponding L-value L

is employed as a measure of the information content of the a-priori

knowledge



x∈{−1,1}

∞

−∞

(ξ|X = x)

×log

2 · p

(ξ|X = x)

(ξ|X =−1) + p

(ξ|X = 1)

dξ.

With Equation (4.13) and µ

we obtain

= 1 −

√

2πσ

∞

−∞

−

(ξ−

2σ

log

(1 + e

−ξ

)dξ.

Note that I

is only a function of σ

. Similarly, for the extrinsic L-values we obtain

= I(X;L

) =



x∈{−1,1}

∞

−∞

(ξ|X = x)

×log

2 · p

(ξ|X = x)

(ξ|X =−1) + p

(ξ|X = 1)

dξ.

192 TURBO CODES

Calculating an EXIT chart

■ The a-priori input of the SISO decoders is modelled as independent

Gaussian random variables L

with variance σ

. The conditional probability

density function of the a-priori L-values is

(ξ|X = x) =

√

2πσ

−

(ξ−

2σ

(4.13)

■ The mutual information I

= I(X ;L

) between the transmitted symbol

X and the corresponding L-value L

is employed as a measure of the

information content of the a-priori knowledge. I

is only a function of σ

= 1 −

√

2πσ

∞

−∞

−

(ξ−

2σ

log

(1 + e

−ξ

)dξ (4.14)

■ The mutual information I

= I(X ;L

) between the transmitted symbol X

and the corresponding extrinsic L-value L

is employed as a measure of

the information content of the code correlation

= I(X;L

) =



x∈{−1,1}

∞

−∞

(ξ|X = x)

×log

2 · p

(ξ|X = x)

(ξ|X =−1) + p

(ξ|X = 1)

dξ (4.15)

where p

(·) is estimated by means of Monte Carlo simulations.

Figure 4.21: Calculating an EXIT chart

Note that it is not possible to express I

= I(X ;L

) and I

= I(X ;L

) in closed form.

However, both quantities can be evaluated numerically. In order to evaluate Equation (4.15),

we estimate p

(·) by means of Monte Carlo simulations. For this purpose, we generate

independent random variables L

according to Equation (4.13) and apply them as a-priori

input to the SISO decoder. We obtain a similar distribution p

(·) to Figure 4.20. With this

distribution we can calculate I

= I(X ;L

) numerically according to Figure 4.21. I

I(X ;L

) is also evaluated numerically according to Equation (4.14).

In order to analyse the iterative decoding algorithm, the resulting extrinsic information

transfer (EXIT) characteristics I

= T(I

) of the inner and outer decoder are plotted

into a single diagram, where for the outer decoder the axes of the transfer characteristic are

swapped. An example of an EXIT chart is given in Figure 4.22. This EXIT chart can be

TURBO CODES 193

Interpretation of an EXIT chart

0 0.2 0.4 0.6 0.8 1

0.2

0.4

0.6

0.8

inner code

outer code

= I

■ The resulting extrinsic information transfer (EXIT) characteristics I

T(I

) of the inner and outer decoder are plotted into a single

diagram, where for one decoder the axes of the transfer characteristic is

swapped.

■ During the iterative decoding procedure the extrinsic output values of one

decoder become the a-priori values of the other decoder. This is indicated

by the line between the transfer functions.

■ Each line indicates a single decoding step of the iterative decoding proce-

dure.

Figure 4.22: Interpretation of an EXIT chart

interpreted as follows. During the iterative decoding procedure, the extrinsic output values

of one decoder become the a-priori values of the other decoder. This is indicated by the

line between the transfer functions, where each line indicates a single decoding step of one

of the constituent decoders (a half-iteration of the iterative decoding procedure).

EXIT charts provide a visualisation of the exchange of extrinsic information between

the two component decoders. Moreover, for very large interleaver sizes, EXIT charts

make it possible to predict the convergence of the iterative decoding procedure accord-

ing to Figure 4.23. Convergence is only possible if the transfer characteristics do not

intersect. In the case of convergence, the average number of required decoding steps

can be estimated. Furthermore, the EXIT chart method make it possible to predict the

so-called waterfall region of the bit error rate performance. This means that we observe

194 TURBO CODES

Convergence of iterative decoding

0 0.5 1

0.2

0.4

0.6

0.8

=0.1dB

0 0.5 1

0.2

0.4

0.6

0.8

=0.3dB

0 0.5 1

0.2

0.4

0.6

0.8

=0.8dB

0 0.2 0.4

BER →

These EXIT charts can be interpreted as follows:

■ Pinch-off region: the region of low signal-to-noise ratios where the bit

error rate is hardly improved with iterative decoding.

■ Bottleneck region: here the transfer characteristics leave a narrow tunnel.

During the iterative decoding the convergence towards low bit error rates

is slow, but possible.

■ Wide-open region: region of fast convergence.

Figure 4.23: EXIT charts and the simulated bit error rate (BER) for a serially

concatenated code with overall rate R = 1/3

an E

-decoding threshold that corresponds to the region of the EXIT charts where

the transfer characteristics leave a narrow tunnel. For this signal-to-noise ratio, the iter-

ative decoding algorithm converges towards low bit error rates with a large number of

iterations. Therefore, this region of signal-to-noise ratios is also called the bottleneck

region. The region of low signal-to-noise ratios, the pinch-off region, is characterised by

an intersection of the transfer characteristics of the two decoders. Here, the bit error rate

is hardly improved with iterative decoding. Finally, we have the region of fast conver-

gence, where the signal-to-noise ratio is signiﬁcantly larger than the decoding threshold. In

TURBO CODES 195

the so-called wide-open region the decoding procedure converges with a small number of

iterations.

For instance, we construct a serially concatenated code. For the inner encoding we

employ a rate R

= 1/2 code with generator matrix G

(D) = (1,

1+D

1+D+D

). For the outer

encoding we employ the same code, but we apply puncturing and partitioning to obtain

the outer rate R

= 2/3 and the desired overall rate R = 1/3. For this example, the EXIT

charts for different values of E

are depicted in Figure 4.23. The bottleneck region

corresponds to a signal-to-noise ratio E

≈ 0.3 dB. For the code of rate R = 1/3 and

length n = 100 000, the required signal-to-noise ratio in order to obtain a bit error rate

of 10

−4

is less than 0.1 dB away from the predicted threshold value, where the iterative

decoding procedure was run for 30 iterations.

Now, consider our running example with the codes from Figure 4.16. The corres-

ponding EXIT charts for a signal-to-noise ratio E

= 0.1 dB can be found in

Figure 4.24. The solid line is the transfer characteristic of the inner code. The two other

charts correspond to the parallel concatenation (R

= 1/2) with the partitioning matrix

P = (1, 0) and the partially concatenated code with R

= 5/7. For the parallel concatenation

the EXIT chart leaves a narrow tunnel. Thus, the iterative decoding should converge towards

low bit error rates. Similarly, with R

= 5/7 the convergence of the iterative decoding is

EXIT charts for different partial rates

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

=0.1dB

=4/7, R

=5/7

=1/2, P=(1 0)

Figure 4.24: EXIT charts for the codes from Figure 4.16 for E

= 0.1dB