US 4,816,805 A · Residue number system shift accumulator decoder

Abstract

Signal processing techniques are disclosed for applications such as finite impulse response filtering. After initial processing in residue number system (RNS) channels, the signals are converted from residue form to a true external representation of the filter output. The conversion employs a chinese remainder theorem decoder and shift accumulator controlled to utilize adaptive modulo reduction. As a consequence, each modulus function value is reduced during computation when it exceeds the modulus and not at the end of the function evaluation. This reduces hardware requirements by minimizing the arithmetic word length. In implementing the technique, each function value is tested to see if it is within a modulus range and the corresponding modulus value is subtracted if it is not. This is done as many times as is necessary to bring each function value within the range. By utilizing this technique, speed and computational accuracy are improved in filter processes thereby producing improved performance in radar, seismic, acoustic and other applications which depend on such filter characteristics.

Claims14

Dependent claims

A residue number system (RNS) decoder system for decoding the outputs of a plurality of parallel RNS channels at least some of which include means based on different relatively prime moduli for performing modular arithmetic, which comprises:

(a) means for storing a set of chinese remainder theorem (CRT) function values in a set of addressable locations;
(b) means responsive to said outputs for deriving corresponding addresses of said CRT values in said storage means;
(c) means for selecting one of said addresses;
(d) means for deriving the function value at said address;
(e) means for summing said function value with any previously summed value;
(f) means for multiplying the new summed value by 2;
(g) means for testing the resultant product to see if it is outside a predetermined range dependent on the decoded moduli;
(h) means for reducing said product by the value of the modulus if it is otherwise outside said range;
(i) means for repeating steps (g) and (h) as needed to bring said modulus within said range;
(j) means causing the summed value to be outputted;
(k) means for repeating steps (c) through (k) as required until the decoding is complete.

8 more elements

Dependencies are inferred from the claim text.

Residue number system shift accumulator decoder

Life of this patent

Residue number system shift accumulator decoder

Life of this patent

Abstract

Claims14