Cryptography Reference
In-Depth Information
polynomial is trivial since the code is systematic. To identify the second, we
must note that
s (0)
i
= d i + s (1)
+ s (3)
i
= d i + s (0)
1 + s (0)
(5.4)
i
i
i
3
and that:
r i = s (0)
+ s (2)
i
+ s (3)
i
= s (0)
i
+ s (0)
i
2 + s (0)
(5.5)
i
i
3
which is equivalent to:
d i = s (0)
+ s (0)
i− 1 + s (0)
i
i− 3
(5.6)
r i = s (0)
i
+ s (0)
i− 2 + s (0)
i− 3
This result can be reformulated by introducing the transform in D :
d ( D )= G (2) ( D ) s ( D )
r ( D )= G (1) ( D ) s ( D )
(5.7)
where G (1) ( D ) and G (2) ( D ) are the generator polynomials of the code shown in
Figure 5.2, which leads to
d ( D )
G (2) ( D )
s ( D )=
(5.8)
r ( D )= G (1) ( D )
G (2) ( D ) d ( D )
Thus, a recursive systematic code can easily be derived from a non-systematic
non-recursive code. The codes generated by such encoders can be represented
graphically according to three models: the tree, the trellis and the state machine.
5.2.3 Tree of a code
The first graphic representation of a code and certainly the least pertinent for
the rest of the chapter is the tree representation. It enables all the sequences
of possible states to be presented. The root is associated with the initial state
of the encoder. From the root, we derive all the possible successive states as
a function of input d i of the encoder. The branch linking a father state to a
son state is labelled with the value of the outputs of the encoder during the
associated transition. This principle is iterated for each of the strata and so
forth. The tree diagram associated with the systematic encoder of Figure 5.1 is
illustrated in Figure 5.6. This type of diagram will not be used in what follows
and the only use that is made of it concerns a sequential decoding algorithm
(Fano's algorithm) not treated in this topic.
5.2.4 Trellis of a code
The most common representation of a convolutional code is the trellis diagram.
It is of major importance both for defining the properties of a code and for
decoding it, as we shall see in the next part of Chapter 5.
Search WWH ::




Custom Search