Time-division type matrix calculator

[0001] 1. Field of the Invention

[0002] The present invention relates to a time-division type matrix calculator, and more particularly, to a matrix calculator for multiplying two matrices by sequentially selecting elements of the matrices and performing multiplication and addition of the selected elements. The present invention is based on Korean Patent Application No. 2001-5334 filed on Feb. 5, 2001, which is incorporated herein by reference.

[0003] 2. Description of the Related Art

[0004] Generally, in a field such as image signal processing, multiplication of matrices is often required. In order to perform the multiplication of the matrices, a matrix calculator uses a plurality of multipliers and a plurality of adders to obtain a mathematical expression of a result of a multiplication operation.

[0005] FIG. 1 is a block diagram of a conventional matrix calculator, especially showing a matrix calculator that performs multiplication with two 3×3 square matrices. FIG. 2 shows detailed construction of each block of FIG. 1.

[0006] When the first matrix is X matrix, and the second matrix is Y matrix, the X matrix is, $\left[\begin{array}{ccc}\mathrm{X1}& \mathrm{X2}& \mathrm{X3}\\ \mathrm{X4}& \mathrm{X5}& \mathrm{X6}\\ \mathrm{X7}& \mathrm{X8}& \mathrm{X9}\end{array}\right],$
and Y matrix is, $\left[\begin{array}{ccc}\mathrm{Y1}& \mathrm{Y2}& \mathrm{Y3}\\ \mathrm{Y4}& \mathrm{Y5}& \mathrm{Y6}\\ \mathrm{Y7}& \mathrm{Y8}& \mathrm{Y9}\end{array}\right].$
Also, a product of X and Y matrices is, $\left[\begin{array}{ccc}\mathrm{Z1}& \mathrm{Z2}& \mathrm{Z3}\\ \mathrm{Z4}& \mathrm{Z5}& \mathrm{Z6}\\ \mathrm{Z7}& \mathrm{Z8}& \mathrm{Z9}\end{array}\right]=\hspace{1em}\left[\begin{array}{ccc}\mathrm{X1}& \mathrm{X2}& \mathrm{X3}\\ \mathrm{X4}& \mathrm{X5}& \mathrm{X6}\\ \mathrm{X7}& \mathrm{X8}& \mathrm{X9}\end{array}\right][\begin{array}{ccc}\mathrm{Y1}& \mathrm{Y2}& \mathrm{Y3}\\ \mathrm{Y4}& \mathrm{Y5}& \mathrm{Y6}\\ \mathrm{Y7}& \mathrm{Y8}& \mathrm{Y9}\end{array}]=[\begin{array}{ccc}\mathrm{X1Y1}+\mathrm{X2Y4}+\mathrm{X3Y7}& \mathrm{X1Y2}+\mathrm{X2Y5}+\mathrm{X3Y8}& \mathrm{X1Y3}+\mathrm{X2Y6}+\mathrm{X3Y9}\\ \mathrm{X4Y1}+\mathrm{X5Y4}+\mathrm{X6Y7}& \mathrm{X4Y2}+\mathrm{X5Y5}+\mathrm{X6Y9}& \mathrm{X4Y3}+\mathrm{X5Y6}+\mathrm{X6Y9}\\ \mathrm{X7Y1}+\mathrm{X8Y4}+\mathrm{X9Y7}& \mathrm{X7Y2}+\mathrm{X8Y5}+\mathrm{X9Y8}& \mathrm{X7Y3}+\mathrm{X8Y6}+\mathrm{X9Y9}\end{array}]$

[0007] As shown in FIG. 1, the conventional matrix calculator for processing the operation as described above includes three blocks 10, 20, and 30. The first block 10 is input with X1, X2, X3, the second block 20 is input with X4, X5, X6, and the third block 30 is input with X7, X8, X9. Further, each of the blocks 10, 20, 30 is input with Y1 through Y9.

[0008] As shown in FIG. 2, the first block 10 includes nine (9) multipliers 11 input with Y1 through Y9, respectively, nine (9) D flip-flops 13 (three (3) groups of three (3) D flip-flops—an upper three flip-flops, an intermediate three flip-flops, and a lower three flip-flops) for storing output from the multipliers 11, and three (3) adders 15 input with outputs from three of the nine (9) D flip-flops 13, respectively. The upper three multipliers 11 are input with X1, the intermediate three multipliers 11 are input with X2, and the lower three multipliers 11 are input with X3. Outputs from the respective multipliers 11 are stored in the D flip-flops 13 and then input into the adders 15. The adders 15 add input values and output the results Z1, Z2, Z3, respectively.

[0009] Constructions of the second and the third blocks 20 and 30 are identical to the construction of the first block 10 shown in FIG. 2. That is, the second block 20 outputs Z4, Z5, Z6, and the third block 30 outputs Z7, Z8, Z9.

[0010] The conventional matrix calculator, however, has a disadvantage in that the circuit becomes bulky since it requires a plurality of multipliers 11 and adders 15. That is, a total of twenty-seven (27) multipliers 11 are required for the block 10, 20, 30, while eighteen (18) adders 15 are required for the blocks 10, 20, 30 (since the adder 15 adds three inputs, each adder 15 actually consists of two adders, each of which adds two inputs).

[0011] The present invention has been made to overcome the above-mentioned problems of the related art, and accordingly, it is an object of the present invention to provide a matrix calculator capable of reducing the number of adders and the size of a circuit by sequentially calculating elements of a multiplication result matrix.

[0012] The above-stated object is accomplished by a matrix calculator for performing multiplication on a first matrix and a second matrix in accordance with the present invention, including an element selecting portion being input with elements of the first and the second matrices, the element selecting portion for sequentially selecting each of the input elements that will constitute a multiplicand of each sub-element of each element of a multiplication result matrix, and for sequentially outputting the selected element, a calculating portion for sequentially calculating each element of the multiplication result matrix by sequentially adding multiplied values of outputs from the element selecting portion, a storing portion for storing output from the calculating portion, and a control signal generating portion for generating a control signal that controls a timing of operation of the calculating portion and the storing portion.

[0013] The element selecting portion includes a multiplexer being input with the respective elements of the first and the second matrices in parallel, and a control block for generating a selection signal that selects an output from the multiplexer. The calculating portion includes a multiplier for multiplying the output from the multiplexer, a first memory for temporarily storing output from the multiplier, a second memory, and an adder for adding a value stored in the first memory with a value stored in the second memory, and inputting the resultant value of the adding operation into the second memory.

[0014] The control signal generating portion includes a plurality of flip-flops for generating signals that delay signals output from the control block by a predetermined number of clock pulses, respectively, and then inputs the generated signals into the calculating portion and the storing portion. The storing portion includes a plurality of registers for sequentially storing the output from the calculating portion.

[0015] According to the present invention, the elements consisting of the sums of sub-elements of the multiplication result matrix are sequentially calculated, by sequentially selecting, multiplying and adding the elements of the two multiplicand matrices. Accordingly, the matrix calculator can be constructed with one adder, one multiplier, and a control circuit for controlling the adder and the multiplier, so the size of the circuit is reduced.

[0024] Detailed description according to the preferred embodiment of the present invention will follow referring to the attached drawings.

[0025] First, in order to explain the principle of calculation of a matrix calculator in accordance with the present invention, a method for analyzing the result matrix of the matrix multiplication into respective elements will be described below.

[0026] As described above, Z matrix, which is the result matrix of the multiplication of the X matrix and the Y matrix is, $\left[\begin{array}{ccc}\mathrm{Z1}& \mathrm{Z2}& \mathrm{Z3}\\ \mathrm{Z4}& \mathrm{Z5}& \mathrm{Z6}\\ \mathrm{Z7}& \mathrm{Z8}& \mathrm{Z9}\end{array}\right]=\hspace{1em}\left[\begin{array}{ccc}\mathrm{X1}& \mathrm{X2}& \mathrm{X3}\\ \mathrm{X4}& \mathrm{X5}& \mathrm{X6}\\ \mathrm{X7}& \mathrm{X8}& \mathrm{X9}\end{array}\right][\begin{array}{ccc}\mathrm{Y1}& \mathrm{Y2}& \mathrm{Y3}\\ \mathrm{Y4}& \mathrm{Y5}& \mathrm{Y6}\\ \mathrm{Y7}& \mathrm{Y8}& \mathrm{Y9}\end{array}]=[\begin{array}{ccc}\mathrm{X1Y1}+\mathrm{X2Y4}+\mathrm{X3Y7}& \mathrm{X1Y2}+\mathrm{X2Y5}+\mathrm{X3Y8}& \mathrm{X1Y3}+\mathrm{X2Y6}+\mathrm{X3Y9}\\ \mathrm{X4Y1}+\mathrm{X5Y4}+\mathrm{X6Y7}& \mathrm{X4Y2}+\mathrm{X5Y5}+\mathrm{X6Y8}& \mathrm{X4Y3}+\mathrm{X5Y6}+\mathrm{X6Y9}\\ \mathrm{X7Y1}+\mathrm{X8Y4}+\mathrm{X9Y7}& \mathrm{X7Y2}+\mathrm{X8Y5}+\mathrm{X9Y8}& \mathrm{X7Y3}+\mathrm{X8Y6}+\mathrm{X9Y9}\end{array}]$

[0027] As shown in the above expression, the respective elements of the result matrix are obtained as follows:

 Z1=X1Y1+X2Y4+X3Y7
Z2=X1Y2+X2Y5+X3Y8
Z3=X1Y3+X2Y6+X3Y9
Z4=X4Y1+X5Y4+X6Y7
Z5=X4Y2+X5Y5+X6Y8
Z6=X4Y3+X5Y6+X6Y9
Z7=X7Y1+X8Y4+X9Y7
Z8=X7Y2+X8Y5+X9Y8
Z9=X7Y3+X8Y6+Y9Y9

[0028] As shown in the above expressions, each element (Z1 through Z9) of the result matrix is the sum of three sub-elements (e.g., the element Z1 is the sum of sub-elements X1Y1, X2Y4, and X3Y7). Further, each sub-element is the product of one element from the X matrix and one element from the Y matrix. Taking this into account, in the present invention, the sub-elements of the elements Z1 through Z9 are sequentially calculated, and then the elements Z1 through Z9 are calculated by adding up the sub-elements.

[0029] FIG. 3 is a block diagram of a matrix calculator in accordance with the present invention. The matrix calculator in accordance with the present invention includes an element selecting portion 70 being simultaneously input with the elements X1 through X9, and Y1 through Y9 of the multiplicands, i.e., the X and Y matrices, and sequentially selecting and outputting necessary elements, a calculating portion 40 for performing a certain operation with respect to the elements selected by the element selecting portion 70, a storing portion 60 for storing the calculation result of the calculating portion 40 and finally outputting the elements of the result matrix, and a control signal generating portion 50 for generating a control signal that controls the calculating portion 40 and the storing portion 60.

[0030] FIG. 4 is a block diagram showing the construction of the element selecting portion 70 of FIG. 3 in greater detail. The element selecting portion 70 includes a multiplexer 73 for selecting and outputting two elements from the input elements, and a control block 71 for generating selection signals sel_l and sel_h that control the selection operation of the multiplexer 73.

[0031] The multiplexer 73 is simultaneously input with all the elements X1 through X9 and Y1 through Y9 of the first and second matrices (i.e., X and Y matrices). The multiplexer 73 is driven by the selection signals sel_l and sel_h generated by the control block 71, and according to the selection signals sel_l and sel_h, one element is selected from the elements X1 through X9 of the first matrix and one element is selected from the elements Y1 through Y9 of the second matrix. The selection signals sel_l and sel_h are changed at every pulse from a clock (not shown) that is either installed in the control block 71 or separately provided to control a sequential operation of the control block 71. Accordingly, the multiplexer 73 selects a different element at every clock pulse and outputs the selected element. Two outputs from the multiplexer 73 are input in the D flip-flops 76, respectively, and the D flip-flops 76 delay the output of the multiplexer 73 by one clock pulse and then output the same.

[0032] The two selection signals sel_h and sel_l for driving the multiplexer 73 consist of a high selection signal sel_h and a low selection signal sel_l. The high selection signal sel_h is a signal designating one of the elements of the matrix Z, which is the result matrix of the multiplication. The low selection signal sel_l is a signal for designating one of the sub-elements of the elements designated by the high selection signal sel_h. For example, if the high selection signal sel_h is 2 and the low selection signal sel_l is 3, the multiplexer 73 is driven to output the third sub-elements of Z2, i.e., X3Y8, and accordingly, the element selecting portion 70 selects and outputs X3 and Y8.

[0033] As a start signal to start the driving of the control block 71, for example, a starting signal generated by a vertical sync that is generated once every field of image signal can be used. When the starting signal is input to the control block 71, the high selection signal sel_h increases by one (1) at the first clock pulse (initial value of the high selection signal is zero), and simultaneously, the low selection signal sel_l increases by one (1) (initial value of the low selection signal is also zero). The value of the low selection signal sel_l increases by one every clock pulse, and accordingly, each sub-element of the first element Z1 is selected and output sequentially every clock pulse. The high selection signal sel_h increases by one (1) every third clock pulse. Accordingly, when the sequential output with respect to the three sub-elements X1Y1, X2Y4, X3Y7 of the first element Z1 is complete, the high selection signal sel_h increases to two (2) to indicate the second element Z2. As the above process repeats, the elements of the first and the second matrices, used in calculating the sub-elements of the elements of the matrix Z, are output sequentially.

[0034] Meanwhile, in addition to the selection signals sel_h and sel_l , the control block 71 generates control signals (flag, stop) to control the control signal generating portion 50. The ‘flag’ signal generates a ‘high’ pulse for one clock pulse at every end of the calculation of one element of the matrix Z, in order to indicate the completion of the calculation of one element. The ‘stop’ signal generates a ‘high’ pulse for one clock pulse at the end of calculation of nine (9) elements of matrix Z, in order to indicate the completion of the calculation of the matrix Z. Further, the ‘stop’ signal is feedback to the control block 71, to initialize the control block 71 by generating a ‘high’ pulse. The control signals (flag, stop) and the high selection signal sel_h are input to the control signal generating portion 50.

[0035] FIG. 5 is a block diagram showing the construction of the control signal generating portion 50 of FIG. 3 in greater detail. The control signal generating portion 50 includes a first delay portion 51 for delaying the high selection signal sel_h, a second delay portion 53 for delaying the ‘flag’ signal, and third and fourth delay portions 55 and 57 for delaying the ‘stop’ signal (reference character ‘d’ in FIGS. 3 through 6 indicates a delayed signal, and the number before the ‘d’ indicates the number of delayed clock pulses. For example, ‘_—3d’ indicate a signal delayed for three clock pulses).

[0036] The first delay portion 51 includes three D flip-flops and generates a signal sel_h_—3d, which is the high selection signal sel_h delayed for three clock pulses. The second delay portion 53 includes two D flip-flops, and generates a signal flag_—2d, which is the ‘flag’ signal delayed for two clock pulses. The third delay portion 55 includes three D flip-flops and generates a signal stop_—3d, which is a ‘stop’ signal delayed for three clock pulses. The fourth delay portion 57 includes a D flip-flop connected in series with the third delay portion 55, and generates a signal stop_—4d, which is an output signal stop_—3d from the third delay portion 55 delayed for one more clock pulse.

[0037] FIG. 6 is a block diagram showing the construction of the calculating portion 40 of FIG. 3 in greater detail. The calculating portion 40 includes a multiplier 41 input with two outputs from the multiplexer 73 of the element selecting portion 70, a first memory 43 for storing the output from the multiplier 41, a second memory 47 installed next to the first memory 43, and an adder 45 for adding the outputs from the first and the second memories 43 and 47 and inputs the resultant sum to the second memory 47. The first and the second memories 43 and 47 include a D flip-flop DFF, store the input value for one clock pulse and then output the same.

[0038] Among the output signals from the control signal generating portion 50, the signal stop_—3d is input to the first memory 43, and when the signal stop_—3d becomes a ‘high’ pulse, the first memory 43 is initialized (value stored in the D flip-flop is reset to zero). Further, among the signals output from the control signal generating portion 50, the signals flag_—2d and stop_—4d are input to the second memory 47, and when one of these two signals becomes a ‘high’ pulse, the second memory 47 is initialized (the value stored in the D flip-flop is reset to zero).

[0039] FIG. 7 is a view showing the construction of the storing portion 60 of FIG. 3. The storing portion 60 includes a 9×1 register. Among the outputs from the control signal generating portion 50, the signals sel_h_—3d and flag_—2d are input to the storing portion 60, and the storing portion 60 is controlled by the signals sel_h_—3d and flag_—2d as input. Outputs Z from the calculating portion 40 are input to the storing portion 60, sequentially, and under the control of the signals sel_h_—3d and flag_—2d from the control signal generating portion 50, the storing portion 60 shifts nine elements Z1 through Z9 every third clock pulse, stores the result, and outputs the same in parallel after the storage has been completed.

[0040] The operation of the matrix calculator in accordance with the present invention will be described below.

[0041] The respective elements X1 through X9, Y1 through Y9 of the first and the second matrices (i.e., X and Y matrices) are simultaneously input to the multiplexer 73 of the element selecting portion 70. When the start signal is input to the control block 71, the control block 71 increases the value of the high and low selection signals sel_h and sel_l by one, which had been set to the initial value ‘zero’. Accordingly, the elements necessary for calculating the first sub-element of the first element Z1 of the matrix Z are selected, and the multiplexer 73 outputs the selected elements X1 and Y1.

[0042] With every clock pulse, the low selection signal sel_l increases by one, and accordingly, the multiplexer 73 sequentially outputs the elements of the matrices X and Y, which constitute multiplicands of the sub-elements of the first element Z1. When the three sub-elements of the first element Z1 are output, the high selection signal sel_h increases by one, and the low selection signal sel_l increases again from the value ‘one’. As a result, the elements of the matrices X and Y, which constitute multiplicands of the sub-elements of the second element Z2, are sequentially output in every clock pulse. As described above, the value of the low selection signal sel_l increases by one every clock pulse, and repeats the variation from one through three, while the value of the high selection signal sel_h increases by one every third clock pulse, and varies from one through nine. Accordingly, the elements necessary for calculation of matrix Z are sequentially output.

[0043] As described above, the ‘flag’ signal generates the ‘high’ pulse for one clock pulse every time the output of the sub-elements of one element of matrix Z is completed, while the ‘stop’ signal generates the ‘high’ pulse for one clock pulse every time the calculation of all the elements Z1 through Z9 of the matrix Z is completed.

[0044] The outputs from the multiplexer 73 are sequentially input to the multiplier 41 of the calculating portion 40, and the multiplier 41 multiplies the outputs from the multiplexer 73, and sequentially calculates the sub-elements X1Y1, . . . of the elements Z1 through Z9 of the matrix Z. The sub-elements output from the multiplier 41 are stored in the first memory 43. The values stored in the first memory 43 are then stored in the second memory 47 via the adder 45. Here, the initial value of the second memory 47 is set at zero. Since the second memory 47 is input with the sum of the output from the first memory 43 and the output from itself, the total sum of sub-elements sequentially calculated by the multiplier 41 is stored in the second memory 47.

[0045] Since the output from the multiplexer 73 is input to the second memory 47 via the D flip-flop 76 and the first memory 43, the second memory 47 is input with the sub-elements calculated by the multiplier 41, after two clock pulses of delay from the output of the elements of matrices X and Y. Since the ‘flag’ signal generates a ‘high’ signal only after the completion of the output of all the sub-elements (e.g. X1Y1, X2Y4, X3Y7) of one element of the Z matrix (e.g. Z1), the signal flag_—2d, which is the ‘flag’ signal delayed by two clock pulses, is reset after one element that is the sum of three sub-elements is stored. Accordingly, every time the calculation of one element of matrix Z is completed, the value stored in the second memory 47 is reset to zero to be prepared for calculation of the next element, and at this time, the value stored in the second memory 47 is input to the storing portion 60 ahead of the reset of the second memory 47.

[0046] As the above process repeats nine times, values of all the elements Z1 through Z9 are calculated by the calculating portion 40, sequentially, and after completion of the calculation, the ‘stop’ signal becomes a ‘high’ pulse. Accordingly, the control block 71 is reset at the time of generation of the ‘stop’ signal, and after three and four clock pulses of delay, the first and the second memories 43 and 47 are reset to zero, respectively. Accordingly, initialization is carried out in order to perform multiplication on the next input of matrices.

[0047] The values of the elements Z1 through Z9 sequentially output from the calculating portion 40 are input to the storing portion 60 comprised of a 9×1 register. The storing portion 60 is input with a signal sel_h_—3d, which is the high selection signal sel_h delayed by three clock pulses, and a signal flag_—2d, which is the ‘flag’ signal delayed by two clock pulses.

[0048] The signal flag_—2d shifts the values of each register in the storing portion 60. Accordingly, as the values of the second memory 47 of the calculating portion 40 are input to the front-most of the registers of the storing portion 60, the values of the registers in the storing portion 60 are shifted, simultaneously. And as this process repeats, values of respective elements stored in the second memory 47 are stored in the registers, sequentially.

[0049] The signal sel_h_—3d outputs the values stored in the registers in the storing portion 60. At this time, the values of the registers of the storing portion 60 are output when the signal sel_h_—3d becomes 1001₍₂₎, i.e., 9. Accordingly, when the values of all of the sequentially-input elements Z1 through Z9 are stored in the registers, the values of Z1 through Z9 are output in parallel. As a result, the matrix Z, the multiplication result of matrices X and Y, is calculated. Here, the high selection signal sel_h is delayed by three clock pulses and the ‘flag’ signal is delayed by two clock pulses, in order to synchronize the shift time of the sequentially-input elements Z1 through Z9 with the output time of the elements Z1 through Z9.

[0050] Although FIGS. 3 through 7 exemplarily show the matrix calculator for performing multiplication of two 3×3 square matrices, it should be understood that the present invention can be applied to the calculation of other types of matrices. For example, the matrix calculator for multiplying 4×4 matrices can be achieved by setting the number of inputs to the multiplexer 73 of the element selecting portion 70 as eight (8), and adjusting the number of delay clock pulses of control signals suitable for the multiplication of 4×4 matrices. The matrix calculator for calculating non-square matrices can also be easily achieved with proper application and necessary adjustments to the number of delay clock pulses.

[0051] According to the present invention, multiplication of two matrices can be performed sequentially, by sequentially outputting and adding the sub-elements of the respective elements of the multiplicands. Accordingly, with the calculating portion comprised of one multiplier and one adder, and a control circuit that selects and controls the values to be input to the calculating portion, the matrix calculator of simple hardware and compact size can be constructed.

[0052] Although the preferred embodiment of the present invention has been described, it will be understood by those skilled in the art that the present invention should not be limited to the described preferred embodiment, but various changes and modifications can be made within the spirit and scope of the present invention as defined by the appended claims.