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

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

166 TURBO CODES

Tanner graph of the Hamming code

■ The parity-check matrix of the Hamming code B(7, 4, 3)

H =





1001101

0101011

0010111





can be considered as adjacency matrix of the following Tanner graph

⊕ b

= 0

⊕ b

= 0

⊕ b

= 0

Figure 4.2: Tanner graph of the Hamming code

and b

. Note that edges only connect two nodes not residing in the same class. A vector

b = (b

,...,b

) is a code word if and only if all parity-check equations are satisﬁed, i.e.

for all check nodes the sum of the neighbouring positions among the message nodes is

zero. Hence, the graph deﬁnes a linear code of block length n. The dimension is at least

k = n − r. It might be larger than n − r, because some of the check equations could be

linearly dependent.

Actually, the r × n parity-check matrix can be considered as the adjacency matrix of

the Tanner graph.

The entry h

of the parity-check matrix H is 1 if and only if the jth

check node is connected to the ith message node. Consequently, the j th row of the parity-

check matrix determines the connections of the check node c

, i.e. c

is connected to all

message nodes corresponding to 1s in the jth row. We call those nodes the neighbourhood

of c

. The neighbourhood of c

is represented by the set P

={i : h

= 1}. Similarly, the

1s in the ith column of the parity-check determine the connections of the message node

In general, the adjacency matrix A for a ﬁnite graph with N nodes is an N × N matrix where the entry

is the number of edges connecting node i and node j . In the special case of a bipartite Tanner graph, there

exist no edges between check nodes and message nodes. Therefore, we do not require a square (n + r) × (n + r)

adjacency matrix. The parity-check matrix is sufﬁcient. For sparse graphs an adjacency list is often the preferred

representation because it uses less space.

TURBO CODES 167

Tanner graph of a regular code

■ All message nodes have the degree 2.

■ All check nodes have the degree 3.

⊕ b

= 0

⊕ b

= 0

⊕ b

= 0

⊕ b

= 0

⊕ b

= 0

⊕ b

= 0

Figure 4.3: Tanner graph of a regular code

. We call all check nodes that are connected to b

the neighbourhood of b

and denote it

by the set M

={j : h

= 1}. For instance, we have P

={1, 4, 5, 7} and M

={1, 2, 3}

for the Tanner graph in Figure 4.2.

The Tanner graph in Figure 4.2 deﬁnes an irregular code, because the different message

nodes have different degrees (different numbers of connected edges).

A graph where all

message nodes have the same degree and all check nodes have the same degree results in

a regular code. An example of a regular code is given in Figure 4.3. The LDPC codes as

invented by Gallager were regular codes. Gallager deﬁned the code with the parity-check

matrix so that every column contains a small ﬁxed number d

of 1s and each row contains

a small ﬁxed number d

of 1s. This is equivalent to deﬁning a Tanner graph with message

node degree d

and check node degree d

In graph theory, the degree of a node is the number of edges incident to the node.

168 TURBO CODES

4.1.2 Decoding for the Binary Erasure Channel

Let us now consider the decoding of an LDPC code. Actually there is more than one

such decoding algorithm. There exists a class of algorithms that are all iterative procedures

where, at each round of the algorithm, messages are passed from message nodes to check

nodes, and from check nodes back to message nodes. Therefore, these algorithms are

called message-passing algorithms. One important message-passing algorithm is the belief

propagation algorithm which was also presented by Robert Gallager in his PhD thesis

(Gallager, 1963). It is also used in Artiﬁcial Intelligence (Pearl, 1988).

In order to introduce this message passing, we consider the Binary Erasure Channel

(BEC). The input alphabet of this channel is binary, i.e. F

={0, 1}. The output alphabet

consists of F

and an additional element, called the erasure. We will denote an erasure by

a question mark. Each bit is either transmitted correctly or it is erased where an erasure

occurs with probability ε. Note that the capacity of this channel is 1 − ε. Consider, for

instance, the code word b = (1, 0, 1, 0, 1, 1, 0, 0, 0) of the code deﬁned by the Tanner

graph in Figure 4.3. After transmission over the BEC we may receive the vector r =

(1, ?, 1, ?, ?, 1, 0, 0, ?).

How can we determine the erased symbols? A simple method is the message passing

illustrated in Figure 4.4. In the ﬁrst step we assume that all message nodes send the received

values to the check nodes. In the second step we can evaluate all parity-check equations.

Message passing for the Binary Erasure Channel (BEC)

1st iteration

2nd iteration

= b

⊕ b

= b

⊕ b

= 1

= b

⊕ b

= b

⊕ b

= 0

= b

⊕ b

= b

⊕ b

= 0

= b

⊕ b

= 0

= b

⊕ b

= 1

Figure 4.4: Message passing for the BEC

TURBO CODES 169

If a single symbol in one of the equations is unknown, e.g. b

in b

⊕ b

, then

the parity-check equation determines the value of the erased symbol. In our example,

= b

⊕ b

= 0. However, if more than one erasure occurs within a parity-check equation,

we cannot directly infer the corresponding values. In this case we assume that evaluation

of the parity-check equation results in an erasure, e.g. b

= b

⊕ b

=?. All results from

the parity-check equations are then forwarded to the message nodes. Basically, every check

node will send three messages. In Figure 4.4 we have only stated one equation per check

node. The connection for this message is highlighted. With this ﬁrst iteration of the message-

passing algorithm we could determine the bits b

= 0 and b

= 0. Now, we run the same

procedure for a second iteration, where the message nodes b

and b

send the corrected

values. In Figure 4.4 we have highlighted the two important parity-check equations and

connections that are necessary to determine the remaining erased bits b

= 0 and b

= 1.

4.1.3 Log-Likelihood Algebra

To discuss the general belief propagation algorithm, we require the notion of a log-likelihood

ratio. The log-likelihood algebra, as introduced in this section, was developed by Hagenauer

(Hagenauer et al., 1996). Let x be a binary random variable and let Pr{x = x



} denote the

probability that the random variable x takes on the value x



. The log-likelihood ratio of x

is deﬁned as

L(x) = ln

Pr{x = 0}

Pr{x = 1}

where the logarithm is the natural logarithm. The log-likelihood ratio L(x) is also called

the L-value of the binary random variable x. From the L-value we can calculate the

probabilities

Pr{x = 0}=

1 + e

−L(x)

and Pr{x = 1}=

1 + e

L(x)

If the binary random variable x is conditioned on another random variable y, we obtain

the conditional L-value

L(x|y) = ln

Pr{x = 0|y}

Pr{x = 1|y}

= ln

Pr{y|x = 0}

Pr{y|x = 1}

+ ln

Pr{x = 0}

Pr{x = 1}

= L(y|x) + L(x).

Consider, for example, a binary symbol transmitted over a Gaussian channel. With binary

phase shift keying we will map the code bit b

= 0 to the symbol −1 and b

= 1to+1. Let

be the received symbol. For the Gaussian channel with variance σ and signal-to-noise

ratio

2σ

, we have the probability density function

p(r

) =

√

2πσ

exp



−(r

− (1 −2b

))

2σ



Thus, for the conditional L-values we obtain

L(r

) = ln

Pr{r

= 0}

Pr{r

= 1}

= ln

p(r

= 0)

p(r

= 1)

170 TURBO CODES

= ln

exp



−

− 1)



exp



−

+ 1)



=−



− 1)

− (r

+ 1)



= 4

As L(r

) only depends on the received value r

and the signal-to-noise ratio, we will

usually use the shorter notation L(r

) for L(r

). The a-posteriori L-value L(b

) is

therefore

L(b

) = L(r

) + L(b

) = 4

+ L(b

The basic properties of log-likelihood ratios are summarised in Figure 4.5. Note that the

hard decision of the received symbol can be based on this L-value, i.e.

0ifL(b

)>0 ,i.e. Pr{b

= 0|r

} > Pr{b

= 1|r

}

1ifL(b

)<0 ,i.e. Pr{b

= 0|r

} < Pr{b

= 1|r

}

Furthermore, note that the magnitude |L(b

)| is the reliability of this decision. To see this,

assume that L(b

)>0. Then, the above decision rule yields an error if the transmitted

bit was actually b

= 1. This happens with probability

Pr{b

= 1}=

1 + e

L(b

)

,L(b

)>0.

Now, assume that L(b

)<0. A decision error occurs if actually b

= 0 was transmitted.

This event has the probability

Pr{b

= 0}=

1 + e

−L(b

)

1 + e

|L(b

,L(b

)<0.

Hence, the probability of a decision error is

Pr{b

=

1 + e

|L(b

and for the probability of a correct decision we obtain

Pr{b

|L(b

1 + e

|L(b

Up to now, we have only considered decisions based on a single observation. In the

following we deal with several observations. The resulting rules are useful for decoding.

If the binary random variable x is conditioned on two statistically independent random

variables y

and y

, then we have

L(x|y

) = ln

Pr{x = 0|y

}

Pr{x = 1|y

}

= ln

Pr{y

|x = 0}

Pr{y

|x = 1}

+ ln

Pr{y

|x = 0}

Pr{y

|x = 1}

+ ln

Pr{x = 0}

Pr{x = 1}

= L(y

|x) + L(y

|x) + L(x).

TURBO CODES 171

Log-likelihood ratios

■ The log-likelihood ratio of the binary random variable x is deﬁned as

L(x) = ln

Pr{x = 0}

Pr{x = 1}

(4.1)

■ From the L-value we can calculate the probabilities

Pr{x = 0}=

1 + e

−L(x)

and Pr{x = 1}=

1 + e

L(x)

(4.2)

■ If the binary random variable x is conditioned on another random variable

y, or on two statistically independent random variables y

and y

,weobtain

the conditional L-values

L(x|y) = L(y|x) + L(x) or L(x|y

) = L(y

|x) + L(y

|x) + L(x) (4.3)

■ For the Gaussian channel with binary phase shift keying and signal-to-noise

ratio

we have the a-posteriori L-value

L(b

) = L(r

) + L(b

) = 4

+ L(b

) (4.4)

where b

is the transmitted bit and r

is the received symbol.

Figure 4.5: Log-likelihood ratios

This rule is useful whenever we have independent observations of a random variable, for

example for decoding a repetition code. Consider, for instance, the code B ={(0, 0), (1, 1)}.

We assume that the information bit u is equally likely to be 0 or 1. Hence, for a memoryless

symmetrical channel we can simply sum over the received L-values to obtain L(u|r) =

L(r

) + L(r

) with the received vector r = (r

Consider now two statistically independent random variables x

and x

. Let ⊕ denote

the addition modulo 2. Then, x

⊕ x

is also a binary random variable with the L-value

L(x

⊕ x

). This L-value can be calculated from the values L(x

) and L(x

)

L(x

⊕ x

) = ln

Pr{x

= 0}Pr{x

= 0}+Pr{x

= 1}Pr{x

= 1}

Pr{x

= 1}Pr{x

= 0}+Pr{x

= 0}Pr{x

= 1}

Using Pr{x

⊕ x

= 0}=Pr{x

= 0}Pr{x

= 0}+(1 −Pr{x

= 0})(1 −Pr{x

= 0}) and

Equation (4.2), we obtain

Pr{x

⊕ x

= 0}=

1 + e

L(x

)

L(x

)

(1 + e

L(x

)

)(1 + e

L(x

)

172 TURBO CODES

Similarly, we have

Pr{x

⊕ x

= 1}=

L(x

)

+ e

L(x

)

(1 + e

L(x

)

)(1 + e

L(x

)

which yields

L(x

⊕ x

) = ln

1 + e

L(x

)

L(x

)

L(x

)

+ e

L(x

)

This operation is called the boxplus operation, because the symbol  is usually used for

notation, i.e.

L(x

⊕ x

) = L(x

)  L(x

) = ln

1 + e

L(x

)

L(x

)

L(x

)

+ e

L(x

)

Later on we will see that the boxplus operation is a signiﬁcant, sometimes dominant portion

of the overall decoder complexity with iterative decoding. However, a ﬁxed-point Digital

Signal Processor (DSP) implementation of this operation is rather difﬁcult. Therefore, in

practice the boxplus operation is often approximated. The computationally simplest estimate

is the so-called max-log approximation

L(x

)  L(x

) ≈ sign(L(x

) · L(x

)) · min

{

|L(x

)|, |L(x

}

The name expresses the similarity to the max-log approximation introduced in Section 3.5.2.

Both approximations are derived from the Jacobian logarithm.

Besides a low computational complexity, this approximation has another advantage,

i.e. the estimated L-values can be arbitrarily scaled, because constant factors can be

cancelled. Therefore, an exact knowledge of the signal-to-noise ratio is not required.

The max-log approximation is illustrated in Figure 4.6 for a ﬁxed value of L(x

) =

2.5. We observe that maximum deviation from the exact solution occurs for

|L(x

)|−

|L(x

= 0.

We now use the boxplus operation to decode a single parity-check code B(3, 2, 2) after

transmission over the Additive White Gaussian Noise (AWGN) channel with a signal-to-

noise ratio of 3 dB (σ = 0.5). Usually, we assume that the information symbols are 0 or

1 with a probability of 0.5. Hence, all a-priori L-values L(b

) are zero. Assume that the

code word b = (0, 1, 1) was transmitted and the received word is r = (0.71, 0.09, −1.07).

To obtain the corresponding channel L-values, we have to multiply r by 4

= 8.

Hence, we have L(r

) = 5.6, L(r

) = 0.7 and L(r

) =−8.5. In order to decode the code,

we would like to calculate the a-posteriori L-values L(b

|r). Consider the decoding of the

ﬁrst code bit b

which is equal to the ﬁrst information bit u

. The hard decision for the

information bit ˆu

should be equal to the result of the modulo addition

⊕

. The log-

likelihood ratio of the corresponding received symbols is L(r

)  L(r

). Using the max-log

approximation, this can approximately be done by

) = L(r

)  L(r

)

≈ sign

(

L(r

) · L(r

)

· min

{

|L(r

)|, |L(r

}

≈ sign(0.7 ·(−8.5)) · min

{

|0.7|, |−8.5|

}

≈−0.7.

TURBO CODES 173

Boxplus operation

■ For x

and x

, two statistically independent binary random variables, x

⊕ x

is also a binary random variable. The L-value L(x

⊕ x

) of this random

variable is calculated with the boxplus operation

L(x

⊕ x

) = L(x

)  L(x

) = ln

1 + e

L(x

)

L(x

)

L(x

)

+ e

L(x

)

(4.5)

■ This operation can be approximated by

L(x

)  L(x

) ≈ sign(L(x

) · L(x

)) · min

{

|L(x

)|, |L(x

}

(4.6)

as illustrated in the following ﬁgure for L(x

) = 2.5

Ŧ10 Ŧ8 Ŧ6 Ŧ4 Ŧ2 0 2 4 6 8 10

Ŧ3

Ŧ2

Ŧ1

exact value

approximation

L(x

)

L(x

)  L(x

)

Figure 4.6: Illustration of the boxplus operation and its approximation. Reprinted with

permission from  2001 IEEE.

The value L

) is called an extrinsic log-likelihood ratio. It can be considered as the

information that results from the code constraints. Note that this extrinsic information is

statistically independent of the received value r

. Therefore, we can simply add L

) and

L(u

) = L(r

) to obtain the a-posteriori L-value

L(u

|r) = L(r

) + L

) ≈ 4.9.

For the two other bits we calculate the extrinsic L-values L

) =−5.6 and L

) = 0.7,

as well as the a-posteriori L-values L(u

|r) =−4.9 and L(b

|r) =−7.7. The hard decision

results in

b = (0, 1, 1).

174 TURBO CODES

4.1.4 Belief Propagation

The general belief propagation algorithm is also a message-passing algorithm similar to

the one discussed in Section 4.1.2. The difference lies in the messages that are passed

between nodes. The messages passed along the edges in the belief propagation algorithm

are log-likelihood values. Each round of the algorithm consists of two steps. In the ﬁrst

half-iteration, a message is sent from each message node to all neighbouring check nodes.

In the second half-iteration, each check node sends a message to the neighbouring message

nodes. Let L

→ c

] denote the message from a message node b

to a check node c

the lth iteration. This message is computed on the basis of the observed channel value r

and

some of the messages received from the neighbouring check nodes except c

according

to Equation (4.7) in Figure 4.7. It is an important aspect of belief propagation that the

message sent from a message node b

to a check node c

must not take into account the

message sent in the previous round from c

to b

. Therefore, this message is explicitly

excluded in the update Equation (4.7). Remember that M

denotes the neighbourhood of

the node b

The message L

→ b

] from the check node c

to the message node b

is an extrinsic

log-likelihood value based on the parity-check equation and the incoming messages from

all neighbouring message nodes except b

. The update rule is given in Equation (4.8). The

symbol

 denotes the sum with respect to the boxplus operation.

Consider now the code deﬁned by the Tanner graph in Figure 4.3. We consider transmis-

sion over a Gaussian channel with binary phase shift keying. Suppose the transmitted code

word is b = (+1, −1, −1, −1, −1, +1, −1, +1, −1). For this particular code word we may

obtain the following channel L-values L(r) = 4

· r = (5.6, −10.2, 0.7, 0.5, −7.5, 12.2,

−8.5, 6.9, −7.7). In the ﬁrst step of the belief propagation algorithm the message nodes

pass these received values to the neighbouring check nodes. At each check node we calcu-

late a message for the message nodes. This message takes the code constraints into account.

For the ﬁrst check node this is the parity-check equation b

⊕ b

= 0. Based on this

Update equations for belief propagation

■ Messages from message nodes to check nodes

→ c

] =

L(r

) if l = 1

L(r

) +



∈M

\{j }

l−1



→ b

] if l>1

(4.7)

■ Messages from check nodes to message nodes

→ b

] =



∈P

\{i}

 L

l−1



→ c

] (4.8)

Figure 4.7: Update equations for the message passing with belief propagation

TURBO CODES 175

Example of belief propagation

1st iteration

2nd iteration

5.6

−10.2

0.7

0.5

−7.5

12.2

−8.5

6.9

−7.7

→ b

] ≈−5.6

→ b

] ≈−0.7

→ b

] ≈ 0.5

→ b

] ≈ 0.7

→ b

] ≈−7.7

→ b

] ≈−6.9

12.4

−15.3

−4.4

−5.7

−20.8

20.2

−14.7

14.1

−22.1

→ c

] ≈ 4, 6

→ c

] ≈ 13, 1

Figure 4.8: Example of belief propagation

equation, we calculate three different extrinsic messages for the three neighbouring message

nodes

) = L(b

⊕ b

) = L(b

)  L(b

) ≈ 7.5,

) = L(b

⊕ b

) = L(b

)  L(b

) ≈−5.6,

) = L(b

⊕ b

) = L(b

)  L(b

) ≈−5.6.

Similarly, we can calculate the messages for the remaining check nodes. Some of these

messages are provided in Figure 4.8, where the corresponding connections from check node

to message node are highlighted.

The extrinsic L-values from the check nodes are based on observations that are sta-

tistically independent from the received value. Therefore, we can simply add the received

channel L-value and the extrinsic messages for each message node. For instance, for the

node b

we have L(b

) = L(r

) + L(b

⊕ b

) + L(b

⊕ b

) ≈ 12.4. If we do this for all

message nodes we obtain the values given in Figure 4.8. These are the L-values for the

message nodes after the ﬁrst iteration.

As mentioned above, it is an important aspect of belief propagation that we only pass

extrinsic information between nodes. In particular, the message that is sent from a message