Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
1999-08-20
2002-09-17
Malzahn, David H. (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
C708S620000
Reexamination Certificate
active
06453332
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The invention relates to a method and apparatus for performing matrix multiplication operations, more particularly to a method and apparatus for performing plural matrix multiplication operations.
2. Description of the Related Art
Matrix multiplication is frequently needed in a digital signal-processing device. For example, the functions of color space conversion and discrete cosine transform (DCT) in digital video processing involve matrix multiplication of one domain with a corresponding common scaler to obtain converted or transformed results of another domain. Conventionally, matrix multiplication is commonly implemented using multipliers or look-up tables. The look-up table approach is often preferred because it involves less complexity.
While the prior art has taught that matrix multiplication can be implemented using look-up table techniques, there is still room for improvement. Particularly, it is preferable to devise a way of implementing the look-up table technique to conduct plural matrix multiplication operations efficiently.
SUMMARY OF THE INVENTION
Therefore, the object of the present invention is to provide an efficient method and apparatus for performing plural matrix multiplication operations using reduced look-up tables.
According to the present invention, a method and apparatus are provided for performing plural matrix multiplication operations. A first one of the matrix multiplication operations is performed to obtain a product of a first coefficient (a) and a first variable (X). A second one of the matrix multiplication operations is performed to obtain a product of a second coefficient (b) and the first variable (X). In the method and apparatus of this invention, a look-up table having a plurality of entries is constructed such that each of the entries corresponds to a value of the first variable (X) and has first and second data fields that store coded products associated with the coefficients (a), (b). When the first variable (X) is provided to the look-up table to address a corresponding one of the entries, the coded product in the first data field of the corresponding one of the entries is generated at a first output of the look-up table, while the coded product in the second data field of the corresponding one of the entries is generated at a second output of the look-up table. A decoder processes the coded products from the first and second outputs of the look-up table, such as by performing arithmetic combining operations, to obtain the results of the matrix multiplication operations.
In a preferred embodiment, a DPCM coding scheme is applied to reduce the size of the look-up table such that the first data field stores the product of the corresponding value of the first variable (X) and the first coefficient (a), while the second data field stores the product of the corresponding value of the first variable (X) and a differential coefficient (b−2
m
a), where m is an integer. The result of the first one of the matrix multiplication operations is obtained from the first output of the look-up table when the first variable (X) is used to address the look-up table. The decoder combines the products at the first and second outputs of the look-up table to obtain the result of the second one of the matrix multiplication operations when the first variable (X) is used to address the look-up table.
In another preferred embodiment, a binary polynomial approximation coding scheme is applied to reduce the size of the look-up table such that the first data field stores the product of the corresponding value of the first variable (X) and a third coefficient (r), while the second data field stores the product of the corresponding value of the first variable (X) and a fourth coefficient (c), where a=r*2
m
+c and b=r*2
n
, and m and n are integers.
REFERENCES:
patent: 5255216 (1993-10-01), Blanz et al.
patent: 5617346 (1997-04-01), Inoue
patent: 5715187 (1998-02-01), Chen et al.
patent: 5737257 (1998-04-01), Chen et al.
patent: 6101522 (2000-08-01), Sato
patent: 6219375 (2001-04-01), Dent
Christensen O'Connor Johnson & Kindness PLLC
Malzahn David H.
Winbond Electronics Corp.
LandOfFree
Method and apparatus for performing plural matrix... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for performing plural matrix..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for performing plural matrix... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2853502