Cryptography Reference
In-Depth Information
two states is represented by an arc between the two associated nodes and labelled
with the outputs of the encoder. In the case of a binary code, the transition on an
input at 0 (resp. 1) is represented by a dotted (resp. solid) line. The succession
of
s
i
states up to instant
t
is represented by the different paths between the
initial state and the different possible states at instant
t
.
Let us show this with the example of the systematic encoder of Figure 5.1.
Hypothesizing that the initial state
s
0
is state (000) :
•
If
d
1
=0
then the following state,
s
1
, is also (000). The transition is
represented by a dotted line and labelled in this first case 00, the value of
the encoder outputs;
•
If
d
1
=1
, then the following state,
s
1
, is (100). The transition is repre-
sented by a solid line and here labelled 11.
•
We must next envisage the four possible transitions:
s
1
= (000)
if
d
2
=0
or
d
2
=1
and
s
1
= (100)
if
d
2
=0
or
d
2
=1
.
Iterating this construction, we reach the representation, in Figure 5.7, of all
the possible successions of states from the initial state to instant 5, without the
unlimited increase of the tree diagram.
A complete section of the trellis suces to characterize the code. The trel-
lis section of the previous code is thus shown in Figure 5.8(a). Likewise, the
encoders presented in Figures 5.2 and 5.3 are associated with trellis sections,
illustrated in Figures 5.8(b) and 5.8(c) respectively.
00
00
00
(000)
(000)
(000)
01
11
11
11
11
00
11
(001)
(001)
(001)
10
00
00
10
01
01
10
(010)
(010)
(010)
11
01
01
10
10
(011)
(011)
(011)
10
01
01
01
10
(100)
(100)
(100)
10
10
01
00
11
10
01
01
10
(101)
(101)
(101)
01
11
00
11
00
(110)
(110)
(110)
10
00
00
00
(111)
11
(111)
11
(111)
11
(1)
(2)
d
i
r
d
i
d
i
r
i
r
i
i
r
i
r
i
d
=0
d
i
d
i
=0
d
i
=0
i
(1)
(2)
r
i
d
i
r
i
d
i
=1
=1
d
=1
i
[1
,
1+
D
+
D
3
]
(a),
[1 +
D
2
+
D
3
,
1+
D
+
D
3
]
(b) and
[1
,
(1 +
D
2
+
D
3
)
/
(1 +
D
+
D
3
)]
(c)
Figure 5.8 - Trellis sections of the codes with generator polynomials
