Error correction circuit and method

Details Error correction circuit and method Error correction circuit and method

2000-01-20

2003-10-21

Chung, Phung M. (Department: 2133)

Error detection/correction and fault detection/recovery

Pulse or data error handling

Digital data error correction

C714S794000, C714S795000

Reexamination Certificate

active

06637004

ABSTRACT:

BACKGROUND OF THE INVENTION
The present invention relates to error correction circuits and method, and more particularly, to an error correction circuit and method for path metric computing system adopting a Viterbi decoding system.
Path metric computing systems are well known as disclosed in, for instance, “Metric Computation System” in Japanese Patent Laid-Open No. 62-77717 and “Viterbi decoder” in Japanese Patent Laid Open No. 6-164423.
In such prior art path metric computing systems, usually either an ACS (Add Compare Select) circuit or a branch metric value computing circuit computes each path metric value by subtracting the minimum path metric value from the preceding path metric value for preventing the overflow off the path metric memory.
FIG. 8
is block diagram showing a prior art error correction circuit. In this circuit, an ACS circuit
103
receives the outputs of a branch metric value computing circuit
101
and a minimum path metric value subtracting circuit
102
, and feeds its output to a path memory. The output of the ACS circuit
103
is also fed back via a path metric memory
105
to the minimum path metric value subtracting circuit
102
and also fed back via a minimum 25 path metric value detecting circuit
104
to the circuit
102
.
The above prior art error correction circuit has some points to be improved. A first point is that the path metric memory bits are not effectively utilized due to the following ground. Usually, the bit length, of the path metric memory that is used is the sum of the input data bit length and a number of bits corresponding to the maximum inter-code distance. Actually, however, where C/N is bad, the bit length is not effectively used. Where C/N is good, the path metric memory bit length is effectively used so long as it has an adequate value although some difference arises depending on the restriction length. Where C/N is good, the path metric assumes a maximum value in its range with an effective path, while is assumes a minimum value with an ineffective path. This means that effective use of the bit length in obtainable in this case even by carrying our, as a measure against over-flow, a path metric value computation “Preceding path metric value−Minimum path metric value=New path metric value”. Where C/N is bad, however, the effective and ineffective path metric values are closely spaced apart, and therefore the computed new path metric value is small. For this ground, the path metric memory bit length can no longer be, effectively used.
A second point in the prior art circuit is that increasing the number of input data judgment bits in an error correction circuit based on the Viterbi algorithm, extremely increases the size of the memory, which is necessary for tentatively storing path metric values. This is so because it is necessary to store (ZN−1) path metric values where Z is the number of possible states and N is the restriction length. By way of a specific example, where the restriction length is 9, the state number Z is 2
9−1
=256. This means that increasing the effective accuracy by one bit requires an additive memory capacity of 256 bits.
SUMMARY OF THE INVENTION
An object of the present, invention, therefore, is to provide an error correction circuit and method capable of reducing its scale and simplifying its construction by reducing the capacity of the memory necessary for tentatively storing path metric values.
According to an aspect of the present invention, there is provided an error correction circuit based on a Viterbi decoding system comprising a branch metric computing circuit, an ACS circuit and a path metric memory, wherein: the error correction circuit comprises subtracting circuit with range shift disposed between the branch metric computing circuit and the ACS circuit; the output of the ACS circuit being fed our via a detector to the subtracting circuit with range shift.
The subtracting, circuit with range shift includes a subtracting circuit of a minimum path metric value from a path metric value and a first and a second range shifters.
The detector includes a maximum/minimum path metric value detecting circuit having a maximum and a minimum path metric value register, a range comparing circuit and a reversible counter.
The branch metric computing circuit includes a plurality of adders, and the ACS circuit includes ACS sub-circuits corresponding to the adders, respectively, whereby a parallel processing of a plurality of paths is executed.
According to another aspect of the present invention, there is provided an error correction circuit adopting a Viterbi decoding system, wherein preceding to a computing means for adding branch metric values and path metric values are provided a means for updating the dynamic ranges of the branch and path metric values, a means for executing a check, from all the new path metric values, as to whether it is necessary to update the dynamic ranges, n the next ACS process and holding the result of the check, during the next ACS process.
According to other aspect of the present invention, there is provided an error correction circuit comprising: a branch metric value computing circuit for computing branch metric value from received data; a subtracting circuit with range shift receiving range shift signal, and executes range shift of the path and branch metric value ranges in which the minimum path metric value has been subtracted, for subtracting the previously detected minimum path metric value from the immediately preceding path metric value; an ACS circuit for executing addition and comparison of the preceding p:ass metric values and branch metric values, and selecting the maximum path metric value to provide the selected new path metric value and a path selection signal; a detector for detecting the maximum and minimum path metric values in an ACS process for one-bit data, and also for detecting the range shift value to provide a range shift signal to the subtracting circuit with range shift; and a path metric memory (memory means) for holding the computed path metric values.
The subtracting circuit with range shift includes a subtracting circuit for subtracting a preceding minimum path metric value from the preceding path metric value; a range shifter for contracting the input data to one half in response to the reception of the down signal while expanding the input data to double thereof in response to the reception of the up signal to feed out the resultant data to the ACS circuit; and a range shifter for multiplying the branch metric value by 2S or (½)S, where S is a shift constant, and feeding out the resultant product value to the ACS circuit.
The subtracting circuit with range shift includes: a detector for detecting the maximum and minimum path values among the new path metric values which have been obtained in an ACS process for one bit of decoded data; a range comparing circuit for generating a range shift-up signal when ((previous maximum path metric value−previous minimum path metric value)+maximum branch metric value) becomes greater than the maximum value that can be stored in the memory, and a range shift-down signal when ((previous maximum path metric value−previous minimum path metric value)×2+maximum branch metric value) becomes less than the maximum value that can be stored in the memory; shift signal register for latching the shift-up or shift-down signal, and holding the latched signal during the next process for one decoded data bit. When the ACS process for one decoded data is ended; and a reversible counter for detecting the shift-up or shift-down signal, and executing one count-up (+1) or -down (−1), and during the nest ACS process for one decoded data bit when the ACS process for one decoded data bit is ended.
According to further aspect of the present invention, thee is provided an error correction method comprising steps of: computing branch metric value from received data; receiving a range shift-up (or -down) signal, and executing range shift-up (or -down) of t

Affiliated with

Also associated with

Rating

Error correction circuit and method does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Error correction circuit and method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Error correction circuit and method will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3156296