Neubauer A., Freudenberger J., Kuhn V. Coding theory: algorithms, architectures and applications
Подождите немного. Документ загружается.
106 CONVOLUTIONAL CODES
Recursive encoder
u
b
(1)
b
(2)
Figure 3.8: Recursive encoder for the code B(2, 1, 2)
in Chapter 4, usually recursive encoders, i.e. encoders with feedback, are employed. In the
case of recursive encoders, we cannot simply add m zeros to the information sequence.
The termination sequence for a recursive encoder depends on the encoder state. However,
the termination sequence can be easily determined. Consider, for instance, the encoder
in Figure 3.8. To encode the information bits, the switch is in the upper position. The
tail bits are then generated by shifting the switch into the down position. This forces the
encoder state back to the all-zero state in m transitions at most.
The method of tail-biting for recursive encoders is more complicated, because in this
case the start state depends on the complete information sequence. An algorithm to calculate
the encoder start state for tail-biting with recursive encoders is presented elsewhere (Weiss
et al., 1998).
3.1.5 Puncturing
In Figure 3.2 we have introduced the general convolutional encoder with k inputs and n
outputs. In practical applications we will usually only find encoders for rate 1/n convolu-
tional codes, i.e. with one input. One reason for this is that there exists a simple method
to construct high-rate codes from rate R = 1/n codes. This method is called puncturing,
because a punctured code sequence is obtained by periodically deleting a part of the code
bits of rate R = 1/n code (cf. Section 2.2.7). However, the main reason is that the decoding
of high-rate convolutional codes can be significantly simplified by using punctured codes.
This will be discussed in more detail in Section 3.4.2. Tables of punctured convolutional
codes with a large free distance can be found elsewhere (Lee, 1997).
Consider again the convolutional encoder shown in Figure 3.1. For each encoding step
the encoder produces two code bits b
(1)
i
and b
(2)
i
. Now let us delete all bits of the sequence
b
(2)
for odd times i, i.e. we delete b
(2)
2i+1
from each 4-bit output block. We obtain the
encoder output
b = (b
(1)
0
,b
(2)
0
,b
(1)
1
,b
(2)
1
,b
(1)
2
,b
(2)
2
,...) ⇒ b
punctured
= (b
(1)
0
,b
(2)
0
,b
(1)
1
,b
(1)
2
,b
(2)
2
,...).
CONVOLUTIONAL CODES 107
Code puncturing
■ A punctured code sequence is obtained by periodically deleting a part of
thecodebitsofrateR = 1/n code.
■ The puncturing pattern is determined by an n × T puncturing matrix P,
where the j th row corresponds to the jth encoder output and T is the period
of the puncturing pattern. A zero element means that the corresponding
code bit will be deleted, a code bit corresponding to a 1 will be submitted.
■ Example: Puncturing of the code B(2, 1, 2) according to P =
11
10
results in a code B
punctured
(3, 2, 1).
Figure 3.9: Code puncturing
We can express the periodic deletion pattern by an n × T puncturing matrix, where the jth
row corresponds to the j th encoder output and T is the period of the puncturing pattern.
For our example we have
P =
11
10
,
where ‘0’ means that the corresponding code bit will be deleted; a code bit corresponding to
a ‘1’ will be submitted. The puncturing procedure is summarised in Figure 3.9. Obviously,
the original rate R = 1/2 mother code has become a rate R = 2/3 code after punctur-
ing according to P. But what is the generator matrix of this code and what does the
corresponding encoder look like?
To answer these questions, we consider the semi-infinite generator matrix of the mother
code
G =
11 10 11 00 00 ...
00 11 10 11 00 ...
00 00 11 10 11 ...
00 00 00
.
.
.
.
.
.
.
This matrix was constructed from the submatrices
G
0
= (11), G
1
= (10) and G
2
= (11).
However, we can also find another interpretation of the generator matrix G. Considering
the submatrices
G
0
=
1110
0011
and G
1
=
1100
1011
we can interpret the matrix G as the generator matrix of a code with the parameters
k = 2, n = 4 and m = 1. Note that other interpretations with k = 3, 4,... would also
108 CONVOLUTIONAL CODES
be possible. The generator matrix of the punctured code is obtained by deleting every
column that corresponds to a deleted code bit. In our example, this is every fourth column,
resulting in
G
punctured
=
11 1 11 0 00 ...
00 1 10 1 00 ...
00 0 11 1 11 ...
00 0 00
.
.
.
.
.
.
and the submatrices
G
0,punctured
=
111
001
and G
1,punctured
=
110
101
.
From these two matrices we could deduce the six generator impulse responses of the corres-
ponding encoder. However, the construction of the encoder is simplified when we consider
the generator matrix in the D-domain, which we will discuss in the next section.
3.1.6 Generator Matrix in the D-Domain
As mentioned above, an LTI system is completely characterised by its impulse response.
However, it is sometimes more convenient to specify an LTI system by its transfer function,
in particular if the impulse response is infinite. Moreover, the fact that the input/output
relation of an LTI system may be written as a convolution in the time domain or as a
multiplication in a transformed domain suggests the use of a transformation in the context
of convolutional codes. We use the D-transform
x = x
i
,x
i+1
,x
i+2
,...◦−• X(D) =
+∞
i=j
x
i
D
i
,j ∈ Z.
Using the D-transform, the sequences of information and code blocks can be expressed in
terms of the delay operator D as follows
u(D) = u
0
+ u
1
D + u
2
D
2
+···,
b(D) = b
0
+ b
1
D + b
2
D
2
+···.
Moreover, infinite impulse responses can be represented by rational transfer functions
G
l,j
(D) =
P
l,j
(D)
Q
l,j
(D)
=
p
0
+ p
1
D +···+p
m
D
m
1 + q
1
D +···+q
m
D
m
.
The encoding process that is described as a convolution in the time domain can be expressed
by a simple multiplication in the D-domain
b(D) = U(D)G(D),
where G(D) is the encoding (or generator) matrix of the convolutional code. In general, a
generator matrix G(D) is a k × n matrix. The elements G
l,j
(D) of this matrix are realisable
rational functions. The term realisable reflects the fact that a linear sequential circuit always
CONVOLUTIONAL CODES 109
has a causal impulse response. Hence, we can only realise transfer functions that result in
a causal impulse response. For the encoder in Figure 3.1 we obtain
G(D) = (1 +D + D
2
, 1 + D
2
).
The generator matrix of the punctured convolutional code from Section 3.1.5 is
G
punctured
(D) = G
0,punctured
+ DG
1,punctured
=
111
001
+ D
110
101
=
1 + D 1 + D 1
D 01+ D
.
Considering the general controller canonical form of a shift register in Figure 3.4, it is now
easy to construct the encoder of the punctured code as given in Figure 3.10.
Usually an octal notation is used to specify the generator polynomials of a generator
matrix. For example, the polynomial g(D) = 1 + D + D
2
+ D
4
can be represented by a
binary vector g = (11101), where the elements are the binary coefficients of the polynomial
Encoder of a punctured code
■ Puncturing of the code B(2, 1, 2) according to P =
11
10
results in a
code B
punctured
(3, 2, 1) with the following encoder
u
(1)
u
(2)
b
(1)
b
(2)
b
(3)
Figure 3.10: Encoder of the punctured code B
punctured
(3, 2, 1)
110 CONVOLUTIONAL CODES
g(D) with the coefficient of the lowest order in the leftmost position. To convert this vector
to octal numbers, we use right justification, i.e. g = (11101) becomes g = (011101). Now,
the binary vector g = (011101) is equivalent to (35)
8
in octal notation. For example, the
generator matrix of our canonical example code B(2, 1, 2) can be stated as (75)
8
, whereas
the generator matrix (35 23)
8
defines the code B(2, 1, 4).
3.1.7 Encoder Properties
We have already mentioned that a particular encoder is just one possible realisation of
a generator matrix. Moreover, there exist a number of different generator matrices that
produce the same set of output sequences. Therefore, it is important to distinguish between
properties of encoders, generator matrices and codes.
A convolutional code is the set of all possible output sequences of a convolutional
encoder. Two encoders are called equivalent encoders if they encode the same code. Two
encoding matrices G(D) and G
(D) are called equivalent generator matrices if they encode
the same code. For equivalent generator matrices G(D) and G
(D) we have
G
(D) = T(D)G(D),
with T(D) a non-singular k × k matrix.
We call G(D) a polynomial generator matrix if Q
l,j
(D) = 1 for all submatrices G
l,j
(D).
Some polynomial generator matrices lead to an undesired mapping from information se-
quence to code sequence. That is, an information sequence containing many (possibly
infinite) 1s is mapped to a code sequence with only a few (finite) number of 1s. As a
consequence, a small number of transmission errors can lead to a large (possibly infinite)
number of errors in the estimated information sequence. Such a generator matrix is called a
catastrophic generator matrix. Note that the catastrophic behaviour is not a property of the
code but results from the mapping of information sequence to code sequence. Hence, it is a
property of the generator matrix. Methods to test whether a generator matrix is catastrophic
can be found elsewhere (Bossert, 1999; Johannesson and Zigangirov, 1999). The state dia-
gram of the encoder provides a rather obvious condition for a catastrophic mapping. If there
exists a loop (a sequence of state transitions) in the state diagram that produces zero output
for a non-zero input, this is a clear indication of catastrophic mapping.
For example, the generator matrix G(D) = (1 +D, 1 +D
2
) is catastrophic. The corres-
ponding encoder and the state diagram are depicted in Figure 3.11, where the critical loop
in the state diagram is indicated by a dashed line. The generator matrix results from
G(D) = T(D)G
(D)
= (1 +D)(1, 1 + D)
= (1 +D, 1 +D
2
).
Note that in our example all elements of G(D) have a common factor (1 + D). In general,
a generator matrix G(D) of a rate 1/n code is catastrophic if and only if all elements of
G(D) have a common factor other than D.
CONVOLUTIONAL CODES 111
Catastrophic encoder with state diagram
■ Catastrophic encoder:
u
b
(1)
b
(2)
■ State diagram with zero loop for non-zero input:
10 01
11
00
1 / 00
0 / 11
0 / 101 / 11
1 / 10
0 / 00
1 / 01
0 / 01
Figure 3.11: Encoder and state diagram corresponding to the catastrophic generator
matrix G(D) = (1 + D, 1 +D
2
)
A systematic encoding results in a mapping where the code sequence contains the
unchanged information sequence. We call G(D) a systematic generator matrix if it satisfies
G(D) =
1 G
1,k+1
(D) ... G
1,n
(D)
1
.
.
.
.
.
.
.
.
.
1 G
k,k+1
(D) ... G
k,n
(D)
= (I
k
A(D)).
112 CONVOLUTIONAL CODES
That is, the systematic generator matrix contains an k × k identity matrix I
k
. In general, the
k unit vectors may be arbitrarily distributed over the n columns of the generator matrix.
Systematic generator matrices will be of special interest in Chapter 4, because they are
used to construct powerful concatenated codes. A systematic generator matrix is never
catastrophic, because a non-zero input leads automatically to a non-zero encoder output.
Every convolutional code has a systematic generator matrix. The elements of a systematic
generator matrix will in general be rational functions. Codes with polynomial system-
atic generator matrices usually have poor distance- and error-correcting capabilities. For
instance, for the polynomial generator matrix G(D) = (1 + D + D
2
, 1 + D
2
) we can write
the two equivalent systematic generator matrices as follows
G
(D) =
1,
1 + D
2
1 + D + D
2
and G
(D) =
1 + D + D
2
1 + D
2
, 1
.
The encoder for the generator matrix G
(D) is depicted in Figure 3.8, i.e. the encoders in
Figure 3.1 and Figure 3.8 encode the same code B(2, 1, 2).
3.2 Trellis Diagram and the Viterbi Algorithm
Up to now we have considered different methods to encode convolutional codes. In this
section we discuss how convolutional codes can be used to correct transmission errors.
We consider possibly the most popular decoding procedure, the Viterbi algorithm, which
is based on a graphical representation of the convolutional code, the trellis diagram. The
Viterbi algorithm is applied for decoding convolutional codes in Code Division Multiple
Access (CDMA) (e.g. IS-95 and UMTS) and GSM digital cellular systems, dial-up modems,
satellite communications (e.g. Digital Video Broadcast (DVB) and 802.11 wireless LANs.
It is also commonly used in other applications such as speech recognition, keyword spotting
and bioinformatics.
In coding theory, the method of MAP decoding is usually considered to be the opti-
mal decoding strategy for forward error correction. The MAP decision rule can also be
used either to obtain an estimate of the transmitted code sequence on the whole or to
perform bitwise decisions for the corresponding information bits. The decoding is based
on the received sequence and an a-priori distribution over the information bits. Figure 3.12
provides an overview over different decoding strategies for convolutional codes. All four
formulae define decision rules. The first rule considers MAP sequence estimation, i.e. we
are looking for the code sequence
ˆ
b that maximizes the a-posteriori probability Pr{b|r}.
MAP decoding is closely related to the method of ML decoding. The difference is that
MAP decoding exploits an a-priori distribution over the information bits, and with ML
decoding we assume equally likely information symbols.
Considering Bayes law Pr{r}Pr{b|r}=Pr{r|b}Pr{b}, we can formulate the MAP rule as
ˆ
b = argmax
b
{
Pr{b|r}
}
= argmax
b
%
Pr{r|b}Pr{b}
Pr{r}
&
.
The constant factor Pr{r} is the same for all code sequences. Hence, it can be neglected
and we obtain
ˆ
b = argmax
b
{
Pr{r|b}Pr{b}
}
.
CONVOLUTIONAL CODES 113
Decoding strategies
■ Maximum A-Posteriori (MAP) sequence estimation:
ˆ
b = argmax
b
{
Pr{b|r}
}
(3.1)
■ Maximum Likelihood (ML) sequence estimation:
ˆ
b = argmax
b
{
Pr{r|b}
}
(3.2)
■ Symbol-by-symbol MAP decoding:
ˆu
t
= argmax
u
t
{
Pr{u
t
|r}
}
∀ t (3.3)
■ Symbol-by-symbol ML decoding:
ˆu
t
= argmax
u
t
{
Pr{r|u
t
}
}
∀ t (3.4)
Figure 3.12: Decoding rules for convolutional codes
The term Pr{b} is the a-priori probability of the code sequence b. If all information
sequences and therefore all code sequences are equally likely, then Pr{b} is also a constant.
In this case we can neglect Pr{b} in the maximisation and have
ˆ
b = argmax
b
{
Pr{r|b}
}
,
the so-called ML sequence estimation rule. Hence, ML decoding is equivalent to MAP
decoding if no a-priori information is available.
The Viterbi algorithm finds the best sequence
ˆ
b according to the ML sequence estimation
rule, i.e. it selects the code sequence
ˆ
b that maximizes the conditional probability Pr{r|b}
ˆ
b = argmax
b
{
Pr{r|b}
}
.
Therefore, implementations of the Viterbi algorithm are also called maximum likelihood
decoders. In Section 3.5 we consider the BCJR algorithm that performs symbol-by-symbol
decoding.
3.2.1 Minimum Distance Decoding
In Section 2.1.2 we have already considered the concept of maximum likelihood decoding
and observed that for the Binary Symmetric Channel (BSC) we can actually apply minimum
114 CONVOLUTIONAL CODES
distance decoding in order to minimise the word error probability. To simplify the following
discussion, we also consider transmission over the BSC. In later sections we will extend
these considerations to channels with continuous output alphabets.
It is convenient to revise some results concerning minimum distance decoding. Remem-
ber that the binary symmetric channel has the input and output alphabet F
2
={0, 1}. The
BSC complements the input symbol with probability ε<
1
2
. When an error occurs, a 0 is
received as a 1, and vice versa. The received symbols do not reveal where the errors have
occurred.
Let us first consider a binary block code B of length n and rate R =
k
n
. Let r denote
the received sequence. In general, if B is used for transmission over a noisy channel and
all code words b ∈ B are a priori equally likely, then the optimum decoder must compute
the 2
k
probabilities Pr{r|b}. In order to minimise the probability of a decoding error, the
decoder selects the code word corresponding to the greatest value of Pr{r|b}.
For the BSC, the error process is independent of the channel input, thus we have
Pr{r|b}=Pr{r − b}. Furthermore, the error process is memoryless which yields
Pr{r|b}=Pr{r − b}=
n
i=1
Pr{r
i
|b
i
}.
Note that we have Pr{r
i
|b
i
}=ε if r
i
and b
i
differ. Similarly, we have Pr{r
i
|b
i
}=1 −ε for
r
i
= b
i
. Now, consider the Hamming distance dist(r, b) between the received sequence r
and a code word b ∈ B, i.e. the number of symbols where the two sequences differ. Using
the Hamming distance, we can express the likelihood Pr{r|b} as
Pr{r|b}=
n
i=1
Pr{r
i
|b
i
}=ε
dist
(r,b)
(1 − ε)
n−dist(r,b)
,
because we have dist(r, b) bit positions where r and b differ and n − dist(r, b) positions
where the two sequences match. Hence, for the likelihood function we obtain
Pr{r|b}=ε
dist
(r,b)
(1 − ε)
n−dist(r,b)
= (1 − ε)
n
ε
1−ε
dist
(r,b)
.
The term (1 −ε)
n
is a constant and is therefore independent of r and b. For ε<0.5, the
term
ε
1−ε
satisfies
ε
1−ε
< 1. Thus, the maximum of Pr{r|b} is attained for the code
word b that minimizes the distance dist(r, b). Consequently, the problem of finding the
most likely code word can be solved for the BSC by minimum distance decoding. A
minimum distance decoder selects the code word
ˆ
b that minimizes the Hamming distance
to the received sequence
ˆ
b = argmin
b∈B
dist(r, b).
The derivation of the minimum distance decoding rule is summarized in Figure 3.13.
Viterbi‘s celebrated algorithm is an efficient implementation of minimum distance decoding.
This algorithm is based on the trellis representation of the code, which we will discuss next.
CONVOLUTIONAL CODES 115
Minimum distance decoding
■ In order to minimise the probability of a decoding error, the maximum
likelihood decoder selects the code word corresponding to the greatest
value of Pr{r|b }.
■ The error process of the BSC is memoryless and independent of the
channel input
Pr{r|b}=Pr{r − b}=
n
i=1
Pr{r
i
|b
i
}=ε
dist
(r,b)
(1 − ε)
n−dist(r,b)
.
■ We obtain the likelihood function
Pr{r|b}=(1 −ε)
n
ε
1 − ε
dist
(r,b)
.
■ For ε<0.5, the maximum of Pr{r|b} is attained for the code word b that
minimizes the distance dist(r,b).
■ A minimum distance decoder selects the code word that minimizes the
Hamming distance to the received sequence
ˆ
b = argmin
b∈B
dist(r, b) = argmax
b
Pr{r|b}
Figure 3.13: Minimum distance decoding
It is particularly efficient for convolutional codes, because the trellises of these codes have
a very regular structure.
3.2.2 Trellises
In Section 3.1.3 we have seen that the encoder of a convolutional code can be considered as
a finite-state machine that is characterized by a state diagram. Alternatively, a convolutional
encoder may be represented by a trellis diagram. The concept of the trellis diagram was
invented by Forney (Forney, Jr, 1973b, 1974). The trellis for the encoder in Figure 3.1 is
depicted in Figure 3.14. A trellis is a directed graph, where the nodes represent encoder
states. In contrast to the state diagram, the trellis has a time axis, i.e. the ith level of the
trellis corresponds to all possible encoder states at time i. The trellis of a convolutional
code has a very regular structure. It can be constructed from the trellis module, which
is simply a state diagram, where the states σ
i
at each time i and σ
i+1
at time i + 1 are