Cryptography Reference
In-Depth Information
Such a representation shows the basic pattern of these trellises: the butterfly,
so called because of its shape. Each of the sections of Figures 5.8 is thus made up
of 4 butterflies (the transitions of states 0 and 1 towards states 0 and 4 make up
one). The butterfly structure of the three trellises illustrated is identical but the
sequences coded differ. It should be noted in particular that all the transitions
arriving at the same node of a trellis of a non-recursive code are due to the same
value at the input of the encoder. Thus, among the two non-recursive examples
treated (Figures 5.8(a) and 5.8(b)), a transition associated with a 0 at the input
necessarily arrives at one of the states between 0 and 3 and a transition with a
1 arrives at one of the states between 4 and 7. It is different in the case of a
recursive code (like the one presented in Figure 5.8(c)): each state allows one
incident transition associated with an input with a 0, and another one associated
with 1. We shall see the consequences of this in Section 5.3.
5.2.5 State machine of a code
To represent the different transitions between the states of an encoder, there is
a final representation, that of a state machine. The convention for defining the
transition branches is identical to that used in the previous section. Only
2
ν
nodes are represented, independently of instant
i
, the previous representation
being translated into a trellis section. The encoders of Figures 5.1, 5.2 and
5.3 thus allow a representation in the form of a state machine illustrated in
Figures 5.9, 5.10 and 5.11 respectively.
10
11
(100)
(110)
10
01
11
11
00
(000)
10
(010)
(101)
01
(111)
11
00
00
10
01
00
(001)
(011)
01
d
i
r
d
i
=0
d
i
r
i
d
=1
i
Figure 5.9 - State machine for a code with generator polynomials
[1
,
1+
D
+
D
3
]
.
This representation is particularly useful for determining the transfer func-
tion and the distance spectrum of a convolutional code (see Section 5.3). It is
now possible to see a notable difference between a state machine of a recursive
code and that of a non-recursive code: the existence and the number of cycles
1
on an all-zero sequence at the input.
In the case of two non-recursive state machines, there is a single cycle on a null
sequence at the input: the loop on state 0.
1
A cycle is a succession of states such that the initial state is also the final state.
