Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
1999-07-14
2002-06-18
Decady, Albert (Department: 2784)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S794000, C714S796000
Reexamination Certificate
active
06408420
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to a Viterbi decoding method and a Viterbi decoding apparatus in which the Viterbi algorithm being an example of a most likelihood decoding method of convolutional codes is used as an error correction method at the digital transmission. The Viterbi algorithm is described, for example, in Proceeding of IEEE, vol. 61, pp. 268-278, Mar. 1973, by G. D. Forney Jr.
DESCRIPTION OF THE RELATED ART
As a system of a digital transmission, there is a packet communication system in which data to be transmitted is divided into packets of a certain bit length (word length) and which transmits the data in a packet unit. At the packet communication system, at the time when two packets transmitted in sequence are received at a receiving side, the time interval between packets is generally not fixed. In the space communication and the mobile communication for such as a mobile phone, a Viterbi decoding apparatus has been used for the error correction.
FIG. 1
is a block diagram showing a conventional Viterbi decoding apparatus. Referring to
FIG. 1
, the operation of the conventional Viterbi decoding apparatus used in a packet communication system is explained. In this, it is defined that the receiving soft decision P data and Q data are three bits respectively.
The conventional Viterbi decoding apparatus
59
shown in
FIG. 1
provides input terminals
41
and
42
to which the receiving soft decision P data and Q data are inputted respectively, a selector
3
which switches the group of the receiving soft decision P data and Q data, and the group of “000” data, a branch metric generator
4
which obtains the metric of the output of the selector
3
by comparing the output of the selector
3
with each transmitting data of a group of transmitting data, a path metric register
6
which stores the accumulated metric of survivor path, an ACS (add, compare and select) circuit
5
which outputs a path metric value of “n” state (n is an integer of two or more) and selecting information (branch value) of “n” state every symbol interval based on the outputs of the branch metric generator
4
and the path metric register
6
, a path memory
7
which stores the selecting information of “n” state outputted from the ACS circuit
5
every symbol interval, a most likelihood path state detector
9
which obtains a state number having a maximum path metric from the path metric values of “n” state outputted from the ACS circuit
5
every symbol interval, a trace back circuit
48
which performs a trace back process for the data in the path memory
7
and outputs the obtained result as a decoded data from an output terminal
16
, and a control circuit
50
which controls this whole Viterbi decoding apparatus
59
. The “000” data inputting to the selector
3
are, after the last part of the packet data are inputted, during the packet data are decoded, the data (terminal data) which makes each circuit in the Viterbi decoding apparatus
59
return to the state before the packet data are inputted. In this, three bit soft decision data are inputted to the Viterbi decoding apparatus
59
, therefore the “000” data are composed of three bit binary figure “0”.
The ACS circuit
5
outputs the compared and selected path metric value of “n” state and selecting information of “n” state, by adding, comparing and selecting the outputs of the branch metric generator
4
and the path metric register
6
, every symbol interval, corresponding to a trellis line diagram. The trace back circuit
48
outputs a path memory control signal to the path memory
7
and reads data from the path memory
7
, with this, every “g−f” symbols, traces back the path memory
7
to the past only for “g” symbol from the state number of the output of the most likelihood path state detector
9
and outputs “g−f” bits from the finally reached bits as decoded data.
The Viterbi decoding apparatus
59
further provides a receiving clock input terminal
52
to which a receiving clock is inputted and supplied to the branch metric generator
4
, the ACS circuit
5
, the path metric register
6
, the path memory
7
and the trace back circuit
48
, an input terminal
54
which a packet data starting pulse is inputted to and supplies the pulse to the control circuit
50
and an input terminal
55
which a packet data finishing pulse is inputted to and supplies the pulse to the control circuit
50
. The control circuit
50
outputs a select signal to the selector
3
, and outputs a path metric set signal to the path metric register
6
and outputs a trace back starting signal to the trace back circuit
48
. Moreover, the control circuit
50
gives a high path metric to the state number “0” of the path metric register
6
and gives the same low path metric, for example “0”, to the other state numbers by the packet data starting pulse and makes the Viterbi decoding operate. After the packet data finishing pulse is inputted, the control circuit
50
switches the output of the selector
3
to the data group “000”, during the Viterbi decoding is operated and at the time when the output of the most likelihood path state detector
9
becomes the state number “0”, the control circuit
50
makes the operation of the branch metric generator
4
, the ACS circuit
5
, the path metric register
6
and the most likelihood path state detector
9
stop and makes the trace back circuit
48
perform the trace back from the series connecting to the most likelihood path of the state number “0”.
Next, the operation of the conventional Viterbi decoding apparatus
59
for the packet data processing is explained. In this, in order to make the explanation understandable, the case that a coding ratio R=1/2 and a constraint length K=3 is explained.
First, a coding apparatus of transmission side using with this Viterbi decoding apparatus is explained.
FIG. 2
is a block diagram showing a convolutional coding apparatus. At the transmission side, as shown in
FIG. 2
, the convolutional coding apparatus
23
is constituted of a three stage shift register
20
and Exclusive-OR gates
21
and
22
. And inputted data are coded by this convolutional coding apparatus
23
. The series of data is inputted to the shift register
20
from an input terminal
24
every symbol interval. And the output of each stage designated by the shift register
20
is logically operated by the Exclusive-OR gates
21
and
22
, and P data and Q data are outputted from output terminals
25
and
26
respectively. The shift register
20
is made to reset by giving a reset signal.
FIG. 3
is a series of data diagram showing a series of transmitted data and a series of convolutionally coded data. As shown in
FIG. 3
, at the case that the “d” pieces of the packet data i
1
, i
2
, . . . , i
d
are convolutionally coded, generally the convolutional coding apparatus
23
is made to reset before the data i
1
is inputted. That is, the contents of each stage of the shift register
20
are made to be “0”. And after the last packet data i
d
is inputted to the shift register
20
, the “the constraint length K−1” pieces of “0” is inputted. In this, the constraint length K=3, therefore two pieces of “0” data are inputted. In
FIG. 3
, the P data and Q data outputted from the convolutional coding apparatus
23
are denoted as P
1
, P
2
, . . . , P
d
, P
d+1
, P
d+2
and Q
1
, Q
2
, . . . , Q
d
, Q
d+1
) Q
d+2
respectively.
The P data and Q data being the output of the convolutional coding apparatus
23
are transmitted and inputted to the Viterbi decoding apparatus
59
in FIG.
1
. At this time, in order for the Viterbi decoding apparatus
59
to make use of the additional information of the P data and Q data corrupted by noise over the channel, the received P data and Q data are expressed in the soft decision.
FIG. 4
is soft decision data diagram showing three bit soft decision data for “0” and “1” data. In
FIG. 4
, the above mentioned soft decision data are shown.
Next, the operation of the conventional Viterb
De'cady Albert
Lamarre Guy
NEC Corporation
Whitham Curtis & Christofferson, P.C.
LandOfFree
Viterbi decoding method and apparatus thereof does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Viterbi decoding method and apparatus thereof, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Viterbi decoding method and apparatus thereof will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2969079