Patent US4816805A successfully refreshed from Google Patents.
US4816805A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Residue number system shift accumulator decoder
Assignee: Grumman Corp
•
Filing: 1987-02-02
•
Granted: 1989-03-28
•
Expires: 2007-02-02
Abstract
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.
Inventors
- 👤 William M. Vojir
- 👤 Joel R. Davidson
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-07 21:14
CPC Classifications
H; H03; H03H; H03H17/00; H03H17/02; H03H17/0223; H03H17/0238; H03H17/0242; H03M; H03M7/00; H03M7/14; H03M7/18
Claims Analysis
Total Claims: 17
Claim 1
Independent Claim
195 words
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.
Claim 2
Dependent Claim
195 words
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.
Claim 3
Dependent Claim
32 words
The decoder system of claim 1 including a logic array for controlling said means for selecting, said means for summing, said means for multiplying and said means for testing the resultant product.
Claim 4
Dependent Claim
46 words
A system according to claim 1 in which said means for multiplying comprises a storage shift register and said means for testing comprises a comparator having one input supplied by the output of said storage shift register and another input related to the operative modulus value.
Claim 5
Dependent Claim
41 words
A system according to claim 1 in which said means for storing includes a ROM for storing coefficients related to the chinese remainder theorem and said means for selecting comprises a multiplexer circuit responsive to said outputs for addressing said ROM.
Claim 6
Dependent Claim
27 words
A system according to claim 3 including a logic array connected to respond to the output of said comparator and having means for controlling said reducing means.
Claim 7
Dependent Claim
17 words
A system according to claim 4 including logic circuits for controlling the addressing of said CRT ROM.
Claim 8
Dependent Claim
145 words
A digital signal processing method for decoding numbers in residue form comprising the steps of: (a) writing into memory having a plurality of addressable memory locations a chinese remainder theorem (CRT) function value of a form : f(j)=G(b.sub.Lj, . . . , b.sub.1 j)=m.sub.i b.sub.i j wherein m i is the product of all moduli in a moduli set divided by an i TH modulus and b ij is the i TH bit in a binary bit pattern at a j TH address of each addressable memory location; (b) sequentially accessing said addresses to select said values; (c) summing the selected value with the result of any previously processed value; (d) multiplying the resultant by 2 and storing the product; (e) testing the product value for inclusion within the operative modulus range; (f) reducing said product value as required to bring the product within range.
Claim 9
Dependent Claim
145 words
A digital signal processing method for decoding numbers in residue form comprising the steps of: (a) writing into memory having a plurality of addressable memory locations a chinese remainder theorem (CRT) function value of a form : f(j)=G(b.sub.Lj, . . . , b.sub.1 j)=m.sub.i b.sub.i j wherein m i is the product of all moduli in a moduli set divided by an i TH modulus and b ij is the i TH bit in a binary bit pattern at a j TH address of each addressable memory location; (b) sequentially accessing said addresses to select said values; (c) summing the selected value with the result of any previously processed value; (d) multiplying the resultant by 2 and storing the product; (e) testing the product value for inclusion within the operative modulus range; (f) reducing said product value as required to bring the product within range.
Claim 10
Dependent Claim
38 words
The method of claim 7 in which the number of bits in the bit pattern is at least s+1 wherein s is the lowest order binary digit capable of representing the largest value modulus in the moduli set.
Claim 11
Dependent Claim
21 words
The method of claim 7 in which the step of reducing said product is multiplexed with the steps accessing said addresses.
Claim 12
Dependent Claim
26 words
The method of claim 7 in which the step of testing is accomplished by comparing said product value with a value related to the modulus value.
Claim 13
Independent Claim
162 words
An apparatus for translating to true external form residue value outputs of a signal processor, said apparatus comprising a residue number system shift accumulator (RNSSA) connected to receive said outputs for implementing a chinese remainder theorem (CRT) decoding method using adaptive modulo reduction, said RNSSA including: (a) control logic means for implementing control logic throughout the RNSSA; (b) means for storing CRT decoding function values; (c) means for deriving addresses for said stored values as a function of said outputs; (d) selecting means for sequentially addressing and reading out said stored function values; (e) means for subjecting said selected value to arithmetic operations and for storing the resultant value; (f) testing means for determining if said resultant value is greater than a predetermined range related to the decoded moduli; (g) means for reducing said resultant value if it does exceed said range to bring it within the said range; (h) means for repeating steps (c) through (g) for other of said outputs.
Claim 14
Independent Claim
162 words
An apparatus for translating to true external form residue value outputs of a signal processor, said apparatus comprising a residue number system shift accumulator (RNSSA) connected to receive said outputs for implementing a chinese remainder theorem (CRT) decoding method using adaptive modulo reduction, said RNSSA including: (a) control logic means for implementing control logic throughout the RNSSA; (b) means for storing CRT decoding function values; (c) means for deriving addresses for said stored values as a function of said outputs; (d) selecting means for sequentially addressing and reading out said stored function values; (e) means for subjecting said selected value to arithmetic operations and for storing the resultant value; (f) testing means for determining if said resultant value is greater than a predetermined range related to the decoded moduli; (g) means for reducing said resultant value if it does exceed said range to bring it within the said range; (h) means for repeating steps (c) through (g) for other of said outputs.
Claim 15
Dependent Claim
34 words
A system as defined in claim 11 in which said reducing means decrements said value by one or more steps each equal to the modulus as required to achieve a value within said range.
Claim 16
Dependent Claim
24 words
A system as defined in claim 11 further comprising multiplexing means responsive to said logic means for controlling access to said addressable memory locations.
Claim 17
Dependent Claim
31 words
A system as defined in claim 11, wherein said translating apparatus is implemented to decode the residue value output of a residue number system (RNS) finite impulse response (FIR) filter output.
References Cited (Backward Citations)
US4064400A
Cited
US4121298A
Cited
US4041284A
Cited
US4107783A
Cited
US4187549A
Cited
US4281391A
Cited
US4458327A
Cited
US4506340A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1992-03-27 | 1992-09-26 | 1993-03-28 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1996-03-27 | 1996-09-26 | 1997-03-28 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2000-03-27 | 2000-09-26 | 2001-03-28 | $7700.00 | Window Closed / Lapsed |