Matrix multiplication circuit for graphic display

• US 4,719,588 A
• Filed: 05/07/1984
• Issued: 01/12/1988
• Est. Priority Date: 05/06/1983
• Status: Expired due to Term

• Current Assignee: Cadtrak Corporation
• Original Assignee: Seiko Instruments & Electronics Ltd. (Seiko Group Corp.)
• Inventors: Tatemichi, Takaomi, Takahashi, Masato
• Primary Examiner(s): Harkcom, Gary V.
• Assistant Examiner(s): Shaw, Dale M.
• Application Number:
  US06/607,420
• Time in Patent Office: 1,345 Days
• Field of Search: 364/715, 364/736, 364/749, 364/754, 364/757-760
• US Class Current: 708/607
• CPC Class Codes: G06F 17/16 Matrix or vector computation , e.g. matrix-matrix or matrix-vector multiplication, matrix factorization matrix transposition G06F7/78

Abstract

A matrices elements memory is constituted by random access memories, and its addresses are divided into a high address and a low address. The high address specifies areas holding matrix elements, and the low addresses of the matrix elements are designated sequentially bit-by-bit, starting from the least significant bit, so as to enable serial reading. A calculation unit consists of pairs of serial multiplicators which are either used in a cascade connection or independently as independent multiplicators, in order to correspond to the data length of a multiplicand.

Claims

1. A matrix multiplication apparatus for a graphic display which transforms line segments into a dot pattern and displays a graphic picture corresponding to the dot pattern, the matrix multiplication apparatus comprising:

multiplication means for multiplying transformation matrices with each other and for multiplying a coordinate matrix with a transformation matrix;

matrix-storing means for storing bit data representative of the elements of the transformation matrices so as to provide multiplicands and multipliers; and

a processor for controlling the multiplication means and the matrix-storing means, said processor including means for supplying bit data representative of the elements of the coordinate matrices to the multiplication means as multiplicands;

the multiplication means comprising a plurality of groups of serial multiplicators, each multiplicator processing in sequence a predetermined bit length not less than a bit length of the coordinate matrix element and less than a bit length of the transformation matrix element, each multiplicator having a direct-connection terminal for receiving the multipliers from the matrix-storing means and a cascade terminal, first change-over means for connecting the plurality of multiplicators of the different groups in a cascade connection at the cascade terminals so as to receive the multiplicands representative of the transformation matrix elements from the matrix-storing means in sequence and for enabling the multiplicators to operate independently of each other to receive the multiplicands representative of the coordinate matrix elements from the processor in sequence, second change-over means connected between the matrix-storing means and respective ones of the direct-connection terminals for multiplexing the different multipliers fed from the matrix-storing means so as to enable the cascade-connected multiplicators to process the different multipliers, and addition means for adding the results of the multiplications obtained by the multiplicators belonging to the same groups;

the matrix-storing means being directly connected to the multiplication means and comprising random access memories having a predetermined number of blocks corresponding to the number of transformation matrix elements, each block being divided into at least one area which stores whole bits of one element of one transformation matrix, high address setting means for designating the area, and low address setting means for serially reading out the bit data representative of the transformation matrix element stored in the designated area from the least significant bit.

2. A matrix multiplication apparatus as defined in claim 1;

wherein the first change-over means comprises a plurality of switches each having one output terminal and a pair of input terminals, the one output terminal being connected to respective ones of the cascade terminals, one input terminal being grounded, and the other input terminal being connected to an output terminal of another multiplicator to form the cascade connection.

3. A matrix multiplication apparatus as defined in claim 1;

wherein the second change-over means comprises a plurality of switches each having one output terminal and a pair of input terminals, the one output terminal being connected to respective ones of the direct-connection terminals, one input terminal being connected to one block of the matrix-storing means storing an odd-numbered row element of the transformation matrix, and the other input terminal being connected to another block of the matrix-storing means storing an even-numbered row element of the transformation matrix.

4. A matrix multiplication apparatus of a graphic display for multiplying transformation matrices with each other and for multiplying a coordinate matrix with a transformation matrix, the matrix multiplication apparatus comprising:

matrix-storing means for storing the transformation matrices, the matrix-storing means comprising random access memories for storing bit data representative of the elements of the transformation matrices, high address setting means for designating the memories storing the elements of one transformation matrix, and low address setting means for reading out multipliers in the form of serial bit data stored in the designated memories in the order from the least significant bit to the most significant bit;

data bus means for providing multiplicands in the form of long bit data representative of the elements of another transformation matrix and in the form of short bit data representative of the elements of one coordinate matrix; and

multiplication means directly connected to the matrix-storing means for receiving the multipliers and connected to the data bus means for sequentially receiving the multiplicands, the multiplication means comprising a plurality of serial multiplicators for multiplying the same multiplicand of one matrix with the different multipliers of another matrix in one sequence, each multiplicator processing a predetermined bit length of the multiplicand not less than a bit length of the short bit data and less than a bit length of the long bit data, first change-over means operative when the multiplication means receives the long bit data to cascade-connect a predetermined number of the serial multiplicators so that the cascade-connected multiplicators can process the long bit data, and operative when the multiplication means receives the short bit data to enable the plurality of multiplicators to operate independently of each other so that the independent multiplicators can process the short bit data, second change-over means connected between the matrix-storing means and respective ones of the multiplicators for multiplexing the different multipliers fed from the matrix-storing means so as to enable the cascade-connected multiplicators to process the different multipliers with the same multiplicand, and addition means connected to the multiplicators for adding the multiplication products.

5. A matrix multiplication apparatus as defined in claim 4;

wherein the random access memories comprise a plurality of blocks corresponding to respective elements of one transformation matrix.

6. A matrix multiplication apparatus as defined in claim 5;

wherein the blocks have the same number of areas for storing a plurality of transformation matrices.

7. A matrix multiplication apparatus as defined in claim 6, wherein each area stores a bit data representative of one element of one transformation matrix.

8. A matrix multiplication apparatus as defined in claim 6;

wherein the high address setting means includes means for simultaneously designating the areas belonging to the different blocks to store respective elements of the same transformation matrix in the simultaneously designated areas.

9. A matrix multiplication apparatus as defined in claim 4;

wherein the data bus means includes means for providing multiplicands in the form of 64-bit data representative of the elements of the one transformation matrix and in the form of 32-bit data representative of the elements of one coordinate matrix.

10. A matrix multiplication apparatus as defined in claim 9;

wherein each of the serial multiplicators has a capacity to process 32-bit data.

11. A matrix multiplication apparatus as defined in claim 10;

wherein the first change-over means has means for cascade-connecting a pair of the serial multiplicators so that the cascade-connected serial multiplicators have a capacity to process 64-bit data.

12. A matrix multiplication apparatus as defined in claim 4;

wherein the plurality of serial multiplicators correspond to respective elements of the transformation matrix.

13. A matrix multiplication apparatus as defined in claim 12;

wherein the first change-over means includes means for cascade-connecting a pair of serial multiplicators corresponding to different row elements of the transformation matrix.

14. A matrix multiplication apparatus as defined in claim 13;

wherein each of the serial multiplicators comprises a cascade terminal for the cascade connection, a direct-connection terminal for receiving the multipliers from the matrix-storing means, an input terminal for receiving the multiplicand, and an output terminal.

15. A matrix multiplication apparatus as defined in claim 14;

wherein the means for cascade-connecting comprises a plurality of first switches for connecting the cascade terminal of one of the pair multiplicators to the output terminal of the other of the pair multiplicators.

16. A matrix multiplication apparatus as defined in claim 15;

wherein the second change-over means comprises a plurality of second switches connected between the random access memories and respective direct-connection terminals of the serial multiplicators for selectively applying one of the different multipliers corresponding to different row elements of the transformation matrix.