Cryptography Reference
In-Depth Information
10
(100)
(110)
11
00
01
01
01
10
00
(000)
00
(010)
(101)
11
(111)
11
10
10
11
00
(001)
(011)
01
i
r
i
r
i
(1)
(2)
d
i
d
i
=0
(1)
(2)
r
i
=1
Figure 5.10 - State machine for a code with generator polynomials
[1 +
D
2
+
D
3
,
1+
D
+
D
3
]
.
[1
,
(1+
D
2
+
D
3
)
/
(1+
Figure 5.11 - State machine for a code with generator polynomials
D
+
D
3
)]
.
However, the recursive state machine allows another cycle on a null sequence at
the input: state 4
→
state 6
→
state 7
→
state 3
→
state 5
→
state 2
→
state
1
state 4.
Moreover, this cycle is linked to the loop on state 0 by two transitions associated
with inputs at 1 (transitions 0
→
0). There therefore exists an infinite
number of input sequences with Hamming weight
2
equal to 2 producing a cycle
on state 0. This weight 2 is the minimum weight of any sequence that makes
the recursive encoder leave state 0 and return to zero. Because of the linearity
of the code (see Chapter 1), this value of 2 is also the smallest distance that can
separate two sequences with different inputs that make the encoder leave the
same state and return to the same state.
In the case of non-recursive codes, the Hamming weight of the input se-
quences allowing a cycle on state 0 can only be 1 (state 0
→
4and1
→
→
state 4
→
state 2
→
state 0). This distinction is essential for understanding the interest
of recursive codes used alone (see Section 5.3) or in a turbocode structure (see
Chapter 7).
state 1
→
2
The Hamming weight of a binary sequence is equal to the number of bits equal to 1.
