Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
1998-06-11
2001-03-06
Baker, Stephen M. (Department: 2784)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S774000
Reexamination Certificate
active
06199191
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Title of the Invention
The present invention generally relates to Viterbi decoding method and device thereof, more particularly, relates to path trace method in Viterbi decoding method.
This application is a counterpart of Japanese application Serial Number 09-153431 filed on Jun. 11, 1997, the subject matter of which is incorporated herein by reference.
2. Description of the Related Art
A convolution coding method is one of the error correcting codes which is used in the digital communication. A Viterbi decoding algorism is known as one of a maximum likelihood decoding method in order to decode information coded by convolution coding method.
The Viterbi decoding algorism compare the received bit line with the bit line provided by the trellis diagram, and decode received bit line according to selecting a path which has the least error. A standard value called as a metric, is compared to select the path. There are a branch metric and a path metric in the metric. The branch metric is calculated according to received bit line each states at each times, and the path metric is the cumulative total of the path metric at each time. There will always be two possible paths entering each state; one of two will be eliminated by comparing the path metrics. The process as above mentioned is known as ACS process (Added Compare-Select process). A path selecting signal is memorized in the path memory. The path selecting signal is information that which path is selected at each states.
After ACS process is done with regard to the received bit line having a predetermined decoding cycle, a state having the maximum likelihood path metric which is a path metric having a best possibility for the received bit line, is selected. This state is called as the maximum likelihood state. The received bit line can be decoded by tracing the path selecting signal memorized in the path memory as the start of the maximum likelihood state. This process in the Viterbi decoding algorism is called as a path trace method.
There are two method in the path trace method. One is called as a trace forward method which traces the memorized paths by FIFO method. The other is called a trace back method which trace the memorized paths by LIFO method. The present invention relates to the trace back method.
FIG. 1
discloses a Viterbi decoding algorism of the related art.
The necessary variable to carry out this algorism are initialized (step
101
). The ACS process (step
102
) and the trace back method (step
103
) are done until the path memory length times (At
1
) initialized in step
101
, respectively. In step
104
, whether the trace back method is done for all of the decoding bit line should be decoded or not, is decided. If not, the ACS process is done until the path stop length times (At
2
) initialized in step
101
, and the trace back method is done until the path memory length times (At
1
). Again, in step
104
, whether the trace back method is done for all of the decoding bit line should be decoded or not, is decided. Steps
105
and
106
are done until the trace back method is done for all of the decoding bit line should be decoded. If the trace back method is done for all of the decoding bit line should be decoded, a frame error of the decoding bit line is decided (step
107
). By the way, there is the folloing relationship between the path memory length (At
1
) and the path stop length (At
2
); At
1
≧At
2
.
FIG. 2
discribes a sample to understand the Viterbi decoding algorism of the related art. In
FIG. 2
, all of the decoding bit line is
192
, the path memory length (At
1
) is
96
and the path stop length (At
2
) is
32
. And an address of the path memory is a cyclic address, and memorizing the path selecting signal starts from the first address of the path memory.
The ACS process is done at At
1
=96 times (step
101
), and the trace back method is done at At
1
=96 times (step
102
). By this process, 32 bits initialized as the path stop length (At
2
) is determined as the decoding bits.
Because the trace back method for all of the decoding bit line should be decoded is not done (step
104
), moreover, the ACS process is done at At
2
=32 times (step
105
), and the trace back method is doneatAtl=96 times (step
106
). And 32 bits is determined as the decoding bits. The path selecting signal is memorized from the address which is the first address of the path memory.
By repeating steps
105
and
106
at three times, the trace back method with regard to all of the decoding bit line should be decoded, is finished. Thereby, the bits which is determined at the last trace back method, is 96 bits. The frame error of the decoding bit line is decided (step
107
).
SUMMARY OF THE INVENTION
An object of the present invention is to provide a trace back method which is able to change the path memory length and the path stop length which greatly affect a Frame Error Rate (thereinafter FER), based on the result of the frame error decision.
According to one aspect of the present invention, for achieving the above object, there is provided a Viterbi decoding method for decoding a received signal, doing an ACS process and a trace back process at a first value times, doing the ACS process at a second value times and the trace back process at the first value times until the trace back process is complete for all decode bits when the trace back has not finished for all decode bits, the Viterbi decoding method further comprising; after the trace back has finished for all decode bits, deciding a frame error based on the result of calculating a Hamming distance between the received signal and re-encoded decoded signal, changing the first value or the second value based on the result of the decision of the frame error and a value of the counter which signifies the condition of the frame error for the past several times.
According to another aspect of the present invention, for achieving the above object, there is provided a Viterbi decoding device for decoding an received signal, doing an ACS process and a trace back process at a first value times, doing the ACS process at a second value times and the trace back process at the first value times until the trace back process is complete for all decode bits when the trace back has not finished for all decode bits, the Viterbi decoding device further comprising; a frame error determination part for deciding a frame error based on the result of calculating a Hamming distance between the received signal and re-encoded decoded signal, a frame error condition counter for counting the frame error for the past frame, a controller for deciding whether the first value or the second value change or not based on the result of the frame error deermination part and the value of the frame error condition counter.
REFERENCES:
patent: 5509020 (1996-04-01), Iwakiri et al.
patent: 5537445 (1996-07-01), Blaker et al.
Kubota et al., “Compact, High-Speed and High-Coding-Gain General Purpose FEC Encoder/Decoder -NUFEC codec-”, IEEE CH2655-9/89/0000-0798, pp. 798-803, Dec. 1989.
Kong et al., “A Fast Serial Viterbi Decoder ASIC for CDMA Cellular Base Station”, 1996 IEEE Tencon, pp. 333-337, Dec. 1996.
Baker Stephen M.
Frank Robert J.
OKI Electric Industry Co., Ltd.
Venable
Wood Allen
LandOfFree
Viterbi decoding method and device 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 device thereof, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Viterbi decoding method and device thereof will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2528417