5–59
1
2
3
4
5
6
ït
çi
G3 FACSIMILE COMMUNICATIONS
010001 and each of the eight possible coded data strings of all these
become that as shown in Table 5-10. In this example, there are three coded
data strings (000000, 000011 and 110101) for which the Hamming dis-
tance with receive data string 010001 is the minimum, and the Hamming
distance is 2 in each case. At this point in time, candidates for the most
reliable-looking decoding data has been narrowed down to three. Next, at
the point where the data strings following input data 110 have finished
being received, the decoding data for which the Hamming distance with
the receive data string is the minimum is selected as 1. In the trallis dia-
gram, the path of maximum likelihood is said to follow the transition con-
dition. Input data is generated by reversing the coding procedure from the
decoding data obtained in this way.
By the procedure for judging the maximum likelihood path in maximum
likelihood decoding and performing decoding, the number of coded data
strings to be targeted increases exponentially when the receive data strings
have increased. So, a coder that calculates all Hamming distances one by
one will be a massively large-scale circuit. Whereas, Vitterbi decoding is a
decoding scheme that suppresses and minimizes the number of calcula-
tions required for selecting the most reliable-looking coded data string to
only the number of states that are determined by the structure of the trellis
coder. It achieves this by making use of the repetitive structure of trellis
coding, that is, the nature of the correlation between data. A feature relat-
ing to the repetitive structure of a trellis coder, for example, in the trellis
diagram in Fig. 5-51, is that in each of the states from step 3 onwards,
there are only two paths to be arrived at from the previous state. In each of
the steps in this trellis diagram, of the two paths for arriving at the four
states A, B, C and D, the path having the smaller distance with the receive
data string is chosen, and this is stored and updated as the survivor path.
Table 5-10 Hamming Distance with Receive Data String
Coder Input Data
Coding Series
Hamming Distance with
Data String 010001
000
100
001
101
010
110
011
111
000000
111011
000011
111000
001110
110101
001101
110110
2
3
2
3
5
2
3
4