JPH0277967A - matrix multiplier - Google Patents

Abstract

(57) [Summary] This bulletin contains application data before electronic filing, so abstract data is not recorded.

Description

DETAILED DESCRIPTION OF THE INVENTION Field of the Invention The present invention relates to a matrix multiplier that multiplies a matrix and a vector, and more particularly to a matrix multiplier that performs coordinate transformation at high speed in a graphics display device.

[Prior art] Graphics display devices used in the fields of computer graphics and CAD rapidly display images of a defined object viewed from various viewpoints, or images of the object itself being moved or rotated. This is required. The surface of an object to be displayed is approximated by a polygon, and is defined as a set of polygons. Furthermore, each polygon is expressed as a set of vectors indicating the coordinates of the vertices that make up the polygon. On the other hand, the process of changing the viewpoint or moving an object is expressed as a matrix for converting coordinates. Therefore, in order to display the viewpoint or object as if it were continuously moving, it is necessary to quickly multiply the coordinate vector that defines the object by a transformation matrix representing the transformation. A device that achieves this function is called a matrix multiplier. For details on what kind of matrix represents what kind of transformation, for example,
It is described in detail in Chapters 3 and 4 (pp. 65-211) of ``Graphic Processing Engineering Using Computer Displays'' (Fujio Yamaguchi, Nikkan Kogyo Shimbun, 1981). In general, matrix multipliers used in graphic display devices often multiply one transformation matrix by multiple coordinate vectors, so a register called a matrix register is provided in the matrix multiplier to store matrix elements. Therefore, a method is used in which the elements of the transformation matrix are stored in advance and the coordinate vectors that are sequentially input are multiplied by the transformation matrix. Another method is to provide a plurality of matrix registers, store some transformation matrices, and selectively multiply each input coordinate vector. As an example of such a matrix multiplier, 1974-83744 r matrix multiplier".

FIG. 5 is a block diagram showing the structure of the matrix multiplier shown in the conventional example. In FIG. 5, 501 is a matrix register group, 502 is a matrix readout circuit, 503 is a matrix serving as a multiplier, 504 is an input first m-dimensional vector, 505 is a matrix multiplication circuit, and 506 is a multiplier. The second m-dimensional vector is shown. The matrix reading circuit 502 selects one of the elements of a plurality of m rows and m columns of matrices stored in the matrix register 501, and reads element 5 of the matrix.
03 is supplied to the matrix multiplication circuit 505. The matrix multiplication circuit 505 multiplies the input first m-dimensional vector 504 by the read matrix element 503, and outputs a second m-dimensional vector 506 as the product. The multiplication performed in the matrix multiplication circuit 505 is performed by the first
The first m-dimensional vector 504 is regarded as a row vector and the elements 503 of the matrix are multiplied from the right, or the first m-dimensional vector 504 is regarded as a column vector and the elements 503 of the matrix are multiplied from the left. Perform only one operation.

Problem to be Solved by the Invention In general, when several transformations are performed in succession, it is not efficient to multiply successively input coordinate vectors one by one by a matrix representing these transformations. A method is used in which a matrix representing a transformation is created by combining (or combining) these transformations, and the input coordinate vector is multiplied by this matrix. Composition of transformations corresponds to multiplying the matrices representing the transformations. Therefore, if we consider a matrix as a set of vectors, if we decompose an m-by-m-column matrix into m m-dimensional vectors and use a matrix multiplier to multiply the matrix and the vector m times, Multiplication between matrices can be realized. However, in the conventional matrix multiplier shown in FIG. 5, the elements of the m-dimensional vector of the product output as a result of matrix multiplication are stored in the matrix register and used as elements of the multiplier matrix in subsequent matrix multiplication. The problem is that the matrix already stored in the matrix register cannot be multiplied by another matrix to synthesize the transformation represented by the matrix, and the product matrix cannot be used as a subsequent multiplier matrix. was there. In addition, in the matrix multiplication circuit 505, the element 503 of the multiplier matrix is always multiplied only from either the right or the left. There is a problem in that it is not possible to combine (that is, multiply) a new matrix from the right with the matrix that becomes element 503. In addition, if the element 503 of the multiplier matrix is always multiplied only from the left, the element 503 of the multiplier matrix
There was a problem in that it was not possible to synthesize a new matrix from the left into the matrix.

In view of this point, the present invention allows a new matrix to be synthesized from either the right or the left to the matrix previously stored in the matrix register group, and the synthesized matrix can be stored in the matrix register group and used thereafter. The present invention aims to provide a matrix multiplier that can be used as a multiplier matrix for matrix multiplication.

Means for Solving the Problems In order to solve the above problems, the present invention provides a plurality of m f?
a matrix register group that stores elements of an m-column matrix; a matrix readout circuit that reads out any matrix element held by the matrix register group; and m
fr A matrix transposition circuit that swaps rows and columns of elements of an m-column matrix, and either an element of the m-row m-column matrix outputted by the matrix readout circuit or an element of the m-row m-column matrix outputted by the matrix transposition circuit. a multiplier matrix selection circuit that selects and outputs;
a matrix multiplication circuit that multiplies the input first m-dimensional vector by an element of an m-by-m-column matrix output from the multiplier matrix selection circuit and outputs a second m-dimensional vector that is the product; and the matrix multiplication circuit. The matrix multiplier includes a matrix write circuit for writing an element of a second m-dimensional vector outputted from the circuit into one of the matrix registers of the matrix register group.

According to the above configuration, the present invention reads out the elements of any matrix stored in the matrix register group by the matrix readout circuit, and reads out the readout matrix elements as they are or by transposing the rows and columns with the matrix transposition circuit. Afterwards, the input vector is supplied to a matrix multiplication circuit, multiplied by the input vector, and the elements of the vector that is the product are written to one of the matrix registers in the matrix register group by the matrix write circuit, thereby writing the combined matrix into the matrix register. It is possible to store it in the matrix and use it as a multiplier matrix in subsequent matrix multiplication.

Additionally, a matrix transposition circuit allows matrices to be synthesized from either the right or the left.

Embodiment FIG. 1 is a block diagram showing the structure of an embodiment of the matrix multiplier of the present invention. In FIG. 1, 101 is a matrix register group, 102 is a matrix readout circuit, 103 is a matrix element read out by the matrix readout circuit 102, 104 is a matrix transposition circuit, and 105 is a matrix transposition circuit 104.
106 is the multiplier matrix selection circuit, 107 is the multiplier matrix element selected by the multiplier matrix selection circuit 106, and 108 is the input first m-dimensional vector. , 109 is a matrix multiplication circuit, 110
represents the product output from the matrix multiplication circuit 109.
111 represents an m-dimensional vector, and 111 represents a matrix writing circuit, respectively.

The operation of one embodiment of the matrix multiplier of the present invention configured as described above will be described below. Note that in the following description, the terms "matrix" and "matrix element" are used interchangeably. The matrix register group 101 includes a plurality of matrix registers each having m rows and m columns to store elements of a plurality of m rows and m columns of matrices. The matrix readout circuit 102 selects and reads out the elements of the m-row m-column matrix stored in any one of the matrix registers constituting the matrix register group 101, and outputs the selected elements to the matrix transposition circuit 104 and the multiplier matrix selection circuit 106. do. on the other hand,
The matrix writing circuit 111 writes a second m-dimensional vector 1 representing the product output from the matrix multiplication circuit 109.
Each of the 10 elements is stored in any row or column of any matrix register in the matrix register group 101.

FIG. 2 shows a block diagram of a more detailed embodiment of the matrix register group 101, the matrix read circuit 102, and the matrix write circuit 111, taking as an example the case where m is 3 and there are three matrix registers. Figure 2 (a
) shows an embodiment of the matrix multiplier according to claim 2, and FIG. 2(b) shows an embodiment of the matrix multiplier according to claim 3. Figure 2(a)
In (b), 201 indicates the first element of the vector 110 representing the product output from the matrix multiplication circuit 109, 202 indicates the second element of the vector 110, 203 indicates the third element of the vector 110, and 204 From 21
2 indicates a register that stores elements for each row and each column of the three matrix registers that make up the matrix register group; 204, 205, and 206 are the elements in the first row, and 207, 208, and 209 are the elements in the second row. 210 to the element of
．． 211.212 correspond to the elements in the third row, 204.207.210 correspond to the elements in the first column, 205
．． 208.211 is the second column element, 206.209.
212 correspond to the elements in the third column. 213
221 is a selector for selecting an element of one of the matrix registers from the three registers 204 to 212 holding elements of each row and each column, and constitutes the matrix readout circuit 102. 222 to 230 are respective selectors 2 constituting the matrix readout circuit 102;
These are the elements of the matrix to be output from 13 to 221. Although the matrix write circuit 111 is not shown, vector elements 201 to 203 are written to any one row of any one matrix or register (in the case of FIG. 2(a)) constituting the matrix register group 101. ) or column (in the case of FIG. 2(b)).

Returning to FIG. 1, the matrix transposition circuit 104 interchanges the rows and columns of the matrix element 103 output by the matrix readout circuit 102 and outputs the transposed matrix element 105. The multiplier matrix selection circuit 106 selects either the matrix element 103 outputted by the matrix readout circuit 102 or the transposed matrix element 105 outputted by the matrix transposition circuit 104, and outputs it as the multiplier matrix element 107.

FIG. 3 shows a more detailed embodiment of the matrix transposition circuit 104 and the multiplier matrix selection circuit 106, taking as an example the case where m is 3, as in the case of FIG. In FIG. 3, 301 to 309 indicate each element of the matrix 103 output from the matrix readout circuit 102, and the second
These are the same as 222 to 230 in Figures (a) and (b). 301 is the element in the first row, first column, 302 is the element in the first row, second column, 303 is the element in the first row, third column,
304 is the element in the second row and first column, and in the same way, 30
9 corresponds to the elements in the third row and third column, respectively. 31
0 to 315 are selectors, and when the matrix 103 output from the matrix readout circuit 102 is output as is as the multiplier matrix 107,
When selecting the left input of each selector and selecting the matrix 105 output from the matrix transposition circuit 104 as the multiplier matrix 107, the right input of each selector is selected. 316 to 324
indicates each element of the multiplier matrix output from the multiplier matrix selection circuit 106, where 316 is the element in the first row and first column, 317 is the element in the first row and second column, and 318 is the element in the first row and third column. In the column element, 319 is the element in the second row and first column,
Similarly, 324 corresponds to the elements in the third row and third column.

Returning to FIG. 1, the matrix multiplication circuit 109 adds a multiplier matrix 1 to the input first m-dimensional vector 108.
07 and outputs the second m-dimensional vector 110 as a product. In the matrix multiplier according to claim 2, the first m-dimensional vector 108 is regarded as an m-dimensional row vector, and the multiplier matrix 107 is
In the matrix multiplier according to claim 3, the first
The m-dimensional vector 108 of is regarded as an m-dimensional column vector, and the vector 108 is multiplied by the multiplier matrix 107 from the left.

FIG. 4 shows a more detailed example of the matrix multiplication circuit.
The case where m is 3 will be shown as an example. Figure 4(a) is claim 2.
FIG.
b) is a matrix multiplier according to claim 3, and shows an embodiment of a matrix multiplication circuit in a matrix multiplier which is a matrix multiplier according to claim 4. In FIGS. 4(a) and (b), 401 represents the first element of the first m-dimensional vector 108, and 402 represents the first element of the first m-dimensional vector 108.
403 indicates the second element of the m-dimensional vector 108, 403 indicates the third element of the first m-dimensional vector 108, and 404 to 412 indicate the multiplier matrix selection circuit 106.
shows each element of the multiplier matrix 107 outputted by , and is the same as 316 to 324 in FIG. Further, 413 to 430 are scalar multipliers, and 431 to 442 are scalar adders. In FIG. 4(a), scalar multipliers 413, 416, 419 and scalar adders 4
31, 434 constitute a first product-sum calculation circuit, scalar multipliers 414, 417, 420 and scalar adders 432, 435 constitute a second product-sum calculation circuit,
Scalar multipliers 415, 418, and 421 and scalar adders 433 and 436 constitute a third product-sum operation circuit. In addition, in FIG. 4(b), scalar multipliers 422, 42
3.424 and scalar adders 437.438 constitute a first product-sum calculation circuit, and scalar multiplier 425.4
2-6, 427 and scalar adders 439, 440 constitute a second product-sum operation circuit, and a scalar multiplier 428
．． 429, 430 and scalar adders 441 and 442 constitute a third product-sum operation circuit. 443 to 445
denotes each element of the vector 110 representing the product output from the matrix multiplication circuit 109, and are the same as 201 to 203 in FIG. 2, respectively.

A description will be given of how matrices are combined in the matrix multiplier of the present invention configured as described above. First, the case of the matrix multiplier according to claim 2 will be explained.

In this case, the matrix multiplication circuit 109 regards the input vector 108 as an m-dimensional row vector, and always multiplies the vector 108 from the right by the multiplier matrix 107. Let A be the matrix already stored in the matrix register group 101, and let B be the matrix to be newly combined with matrix A. Matrix A
To synthesize matrix B from the left (that is, to obtain the matrix product B-A), matrix B is decomposed into m row vectors for each row, sequentially input to matrix multiplication circuit 109, and transposed. The i-th row (t=it . . . , m
) is stored in the i-th row of matrix registers other than matrix A in matrix register group 101, the elements of the combined matrix B-A are stored in matrix register group 101. When combining matrix B with matrix A from the right (that is, when calculating the matrix product A and B), matrix B is decomposed into m column vectors for each column and sequentially input to the matrix multiplication circuit 109. death,
Transpose the combined matrices A and B by multiplying by the transposed matrix A and storing the product obtained from the column vector of the i-th column in the i-th row of the matrix register other than matrix A in the matrix register group 101. The elements of the matrix are stored in matrix register group 101. Therefore, if the matrix is transposed by the matrix transposition circuit 104 when used as a multiplier matrix next time, the same elements as the combined matrix A-B can be used as the multiplier matrix. This uses the relationship of the following equation (1) in matrix-matrix multiplication.

A-B= (T (T (B)・T(A)) (1)
However, T (X) represents the transposition of matrix X.

In this case, the transpose T (B) regarding matrix B is realized by inputting matrix B after decomposing it into column vectors, and performing multiplication by treating the column vectors as row vectors.

Next, the case of the matrix multiplier according to claim 3 will be explained. In this case, the matrix multiplication circuit 109 regards the input vector 108 as an m-dimensional column vector, and the multiplier matrix 107 always uses the vector 108.
is multiplied from the left. Already matrix register group 10
Let A be the matrix stored in 1, and B be the matrix to be newly synthesized with matrix A.

When combining matrix B with matrix A from the right (that is, when calculating the matrix product A-B),
Decompose matrix B into m column vectors for each column,
It is sequentially input to the matrix multiplication circuit 109, multiplied by the original matrix A without transposition, and the i-th column (i=1
．． ..., m) in the first column of matrix registers other than matrix A in matrix register group 101, the elements of the combined matrix A-B are stored in matrix register group 101. is stored in When combining matrix B with matrix A from the left (i.e., matrix product B-
A), matrix B is decomposed into m row vectors for each row, and sequentially matrix multiplication circuit 10
9, multiplied by the transposed matrix A, and stored the product obtained from the row vector of the i-th row in the first column of the matrix register other than matrix A in the matrix register group 101. The elements of the transposed matrix of B-A are stored in matrix register group 101.

Therefore, if the matrix is transposed in the matrix transposition circuit 104 when used as a multiplier matrix next time, the same elements as the combined matrix B-A can be used as the multiplier matrix. This uses the relationship of the following equation (2) in matrix-matrix multiplication.

B・A= (T (T (A)・T (B)) (2
) However, T (X) represents the transposition of matrix X.

In this case, the transposition T (B) regarding matrix B is realized by inputting matrix B after decomposing it into row vectors, and performing multiplication by treating the row vectors as column vectors.

Note that although the dimensions of the matrix are illustrated as three in the embodiments of the present invention, this is not limited to this (and the number of matrices stored in the matrix register group is also three).
I would like to add that although this is shown in the diagram, this is not the only limit.

Effects of the Invention As explained above, according to the present invention, combining a new matrix with a matrix already stored in a matrix register can be realized as one of ordinary matrix-vector multiplications. . It is also possible to compose matrices from the right or left. Therefore, in a graphic display device,
It is now possible to quickly and flexibly synthesize transformation matrices for converting coordinate vectors, and it is possible to speed up the generation of images of objects viewed from various viewpoints and images of objects rotated and moved in various ways. The contribution to improvement is significant.

[Brief explanation of the drawing]

FIG. 1 is a block diagram showing the configuration of an embodiment of the matrix multiplier of the present invention, and FIG. FIG. 2(b) is a block diagram showing a more detailed embodiment of the write circuit, and FIG. 2(b) shows a more detailed embodiment of the matrix register group, the matrix read circuit, and the matrix write circuit that constitute the matrix multiplier in the invention according to claim 3. FIG. 3 is a block diagram showing a more detailed embodiment of the matrix transposition circuit and multiplier matrix selection circuit constituting the matrix multiplier of the present invention.
FIG. 4A is a block diagram showing a more detailed embodiment of a matrix multiplication circuit constituting a matrix multiplier which is a matrix multiplier according to the invention as claimed in claim 2 and is also a matrix multiplier as claimed in claim 4. Fig. (b) is a block diagram showing a more detailed embodiment of a matrix multiplier circuit constituting a matrix multiplier which is a matrix multiplier according to the invention according to claim 3 and which is a matrix multiplier according to the invention according to claim 4, FIG. 5 is a block diagram showing an example of a conventional matrix multiplier. 101...Matrix register group. 102... Matrix readout circuit, 104... Matrix transposition circuit, 106... Multiplier matrix selection circuit, 107...
Multiplier matrix, 108... Input vector, 109... Matrix multiplication circuit, 110... Product vector. Name of agent: Patent attorney Shigetaka Awano and one other person Figure 1 Figure 2 42113
Figure 114
and a no Figure 5

Claims (4)

[Claims] (1) A matrix register group that stores elements of a plurality of m rows and m columns of matrices, a matrix readout circuit that reads out the elements of any matrix held by the matrix register group, and m rows and m that the matrix readout circuit outputs. a matrix transposition circuit that swaps the rows and columns of elements of a column matrix; an element of an m-row, m-column matrix outputted by the matrix readout circuit; and an element of an m-row, m-column matrix outputted by the matrix transposition circuit. a multiplier matrix selection circuit to output, and a second m-dimensional vector that is the product of multiplying the input first m-dimensional vector by the elements of the m-row m-column matrix output from the multiplier matrix selection circuit; A matrix multiplier comprising: a matrix multiplication circuit; and a matrix write circuit for writing an element of a second m-dimensional vector output from the matrix multiplication circuit into one of the matrix registers of the matrix register group. (2) A matrix multiplication circuit regards the first m-dimensional vector as an m-dimensional row vector, and outputs m from the multiplier matrix selection circuit to the first m-dimensional row vector.
The elements of the matrix with rows and m columns are multiplied from the right, and an m-dimensional row vector is output as the second m-dimensional vector that is the product, and the matrix writing circuit converts each element of the second m-dimensional row vector into the It is characterized by writing into any row of any matrix register of the matrix register group so that the i-th element (i=1, 2, ..., m) corresponds to the i-th column element of that row. Claim 1
The matrix multiplier described. (3) A matrix multiplication circuit regards the first m-dimensional vector as an m-dimensional column vector, and outputs m from the multiplier matrix selection circuit to the first m-dimensional column vector.
The elements of the m-row, m-column matrix are multiplied from the left, and an m-dimensional column vector is output as the second m-dimensional vector to be the product, and the matrix writing circuit converts each element of the second m-dimensional column vector into the It is characterized by writing into any column of any matrix register of the matrix register group so that the i-th element (i=1, 2, ..., m) corresponds to the i-th row element of that column. Claim 1
The matrix multiplier described. (4) The matrix multiplier according to claim 1, wherein the matrix multiplier circuit is composed of m sets of product-sum calculation circuits.