Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
1998-09-30
2001-10-02
Ngo, Chuong Dinh (Department: 2121)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
C708S625000
Reexamination Certificate
active
06298369
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Technical Field
The present invention relates to a high speed multiplier and specifically to a high speed multiplier that utilizes cache memory searches for previous results. The multiplier would be well suited for various digital signal processing (DSP) applications,
2. Description of the Related Art
Besides addition, multiplication is a very heavily used core operation for signal processing. To achieve high throughput, fast multiplications are required. The multiplication of two unsigned numbers A and B creates the product P
P=A*B
where A is called the multiplicand and B the multiplier. Given that A is an m-bit positive whole number and B is an n-bit positive whole number, then the numeric representation of the product P requires (m+n) bits.
In digital signal processing (DSP) system, there is always a demand for fast multiplication. For example, an N-tap with M-bit per tap FIR filter
100
, shown in
FIG. 1
, requires N×M multiplications. A multiplicand X
n
102
is multiplied by a first coefficient C1
106
, while X
n−1
112
, the output of the Z
−1
operator, is multiplied by a second coefficient C2
108
, and X
n−2
114
, the output from a second Z
−1
operator, is multiplied by a third coefficient C3
110
. The results of each multiplication are summed
116
to produce the output value Y
n
104
.
For a real-time DSP application, the Nyquist theory dictates that the sampling rate of a system (Fs) is twice the bandwidth of the system (Fs=2F). Thus, higher system bandwidth requires faster multiplication operations. There are many hardware implementations of parallel multipliers. However, the basic design for each multiplier is an add and shift algorithm. This algorithm generates a partial product, using Booth's algorithm for example, and then adding a partial product using a ROM look up table. For a very basic implementation of the multiplier is consisting of a fast adder, multiplexer (mux) and shift register. An example of a 4×4 multiplier is following:
0110
×
1010
0000
0110
0000
0110
0111100
=
Multiplicand
Multiplier
>
3
c
hex
or
60
decimal
Two registers
202
,
204
are used to hold the value of the multiplier and the multiplicand as shown in FIG.
2
. The multiplier register
202
is shifted into the control logic. If multiplier bit n is a zero, the multiplexer (mux)
216
will select a zero output. Otherwise the mux will select the multiplicand output. The shift register will shift the mux output to n−1 bit to the left. The adder
212
will add this with the partial register
210
that has the initial value of zero. After N iterations the adder
212
will output the final product
214
From the above example, there are N iterations for an N×N multiple. Thus, for a 30-bit by 30-bit multiplication, there would be 30 iterations. Likewise, for a 60×60 multiplication, there would be 60 iterations. A need exists to perform these multiplications with fewer iterations.
SUMMARY OF THE INVENTION
The present invention recognizes that in many circumstances, several multiplication operations are conducted as part of a sequence. The multiplier may be the same for each operation while the multiplicand differs only slightly. The method used to improve the speed of multiplication operations involves dividing the multiplicand into two portions. The first portion is referred to as a cache lookup bit (CLB), while the second portion is referred to as a table lookup bit (TLB). For example, a 30 bit multiplicand could be divided into a 24 bit CLB and a 6 bit TLB. Of course, the lengths of the CLB and TLB can be varied. When a first multiplication operation is performed, its result is stored in cache memory. When the second multiplication is performed, then the method first compares the CLB of the multiplicand with the previous multiplicand. If the CLB's match, also known as a cache hit, the output data from the cache will add/sub with a value pulled from the TLB RAM lookup for a final product. The RAM lookup table is simply a multiplication table. For example, if the TLB is 4 bits in length then the table will contain the results of values 0 to 16 multiplied with C1.
The decision to add or subtract is made from the comparison between the multiplicand TLB and cache TLB address bit. If the multiplicand TLB bit is smaller than the cache TLB address bit, then a subtract operation will be performed. If the TLB bit is equal to the cache TLB bit, then cache output is the final product. If it is bigger, then an add operation will be performed. If no cache hit occurs, also known as a cache miss, then a conventional multiplier will be used to perform the multiplication. The output data from the multiplier can still be used to update the cache and the final product.
REFERENCES:
patent: 4573136 (1986-02-01), Rossiter
patent: 4611305 (1986-09-01), Iwase
patent: 4864529 (1989-09-01), Shah et al.
patent: 5117385 (1992-05-01), Gee
patent: 5150320 (1992-09-01), Nakayama
patent: 5255216 (1993-10-01), Blanz et al.
patent: 5260898 (1993-11-01), Richardson
patent: 5343416 (1994-08-01), Eisig et al.
patent: 5715187 (1998-02-01), Chen et al.
patent: 5828591 (1998-10-01), Rotstain
patent: 2 184 269 (1987-06-01), None
Galanthay Theodore E.
Jorgenson Lisa K.
Munck William A.
Ngo Chuong Dinh
STMicroelectronics Inc.
LandOfFree
High speed multiplier does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with High speed multiplier, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and High speed multiplier will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2600262