JPH0335701B2 - - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION [Technical Field of the Invention] The present invention particularly relates to a matrix multiplier that calculates the product of a row vector and a column vector necessary for coordinate transformation in graphic processing.

[Technical Background of the Invention and Problems Therewith] In recent years, graphic processing systems using computers have become widely used. This system generally consists of a graphics definition system and a graphics display system. The figure defined in virtual space (xy-space) by the figure definition system is
undergoes several transformations by the graphical display system,
It is mapped to real space (UV-space). This real space corresponds to the surface of a CRT tube in a graphic display device or the surface of paper on an electrostatic plotter.

Now, the transformation in the two-dimensional coordinate space is as follows.
Equation (1) is the basis.

e _i+1 f _i+1 1=a, b, e _i c, d, f _i 0, 0, 1 Δx Δy 1 (1) Δx, Δy: Absolute value coordinates in virtual space e, f: Real space In the above equation (1), the constant terms a, b, c,
d is a real number expressed as a floating point number, Δx,
Δy is an integer expressed in two's complement. Therefore, in order to convert the above equation (1), sum-of-product calculations involving complicated floating-point processing are required. For this reason, the conversion of equation (1) above has conventionally been performed by a microprocessor in a host computer or peripheral device. However, performing the above conversion using a host computer or microprocessor requires a large amount of processing time, which poses a problem as a bottleneck for high-speed display.

[Purpose of the invention] This invention was made in view of the above circumstances, and its purpose is to solve the problems of a, Δx+b, Δy+e _i (a and b are constant terms, and The object of the present invention is to provide a matrix _multiplier that can perform product-sum operations at high speed with a simple hardware configuration.

[Summary of the Invention] According to the present invention, constant terms a and b are expressed as am×2 ^ae-m and bm×2 ^be-m (am and bm are l-bit integers expressed as two's complement numbers, ae, be, m is 0≦
ae, an integer satisfying be≦m) and the previous operation result e _i (e _i is the integer part p bits expressed as a two's complement number,
A row vector consisting of three elements: a fixed point number with q bits in the fractional part), a variable term Δx, Δy (Δx, Δy are k-bit integers expressed in two's complement), and a fixed value 1. Using the column vector, a・Δx+ which is the product of the row vector and the column vector
A matrix multiplier is provided which performs a product-sum operation indicated by b·Δy+e.

The matrix multiplier above latches am
A register, a bm register that latches bm, and a first register that performs counting according to the basic clock signal at the start of operation, and repeatedly generates a first control trigger pulse synchronized with the same clock signal when the difference between m and q is counted. The control means performs counting according to the basic clock signal at the start of operation, and the above-mentioned
A second control means that repeatedly generates a second control trigger pulse synchronized with the same clock signal when only ae is counted; and third control means for repeatedly generating control trigger pulses.

The matrix multiplier also latches the initial value e ₀ in the initial state, and a first shift register that shifts the contents downward in response to a first control trigger pulse from the first control means, and a first shift register that latches Δx. a second shift register that shifts the contents downward in response to a second control trigger pulse from the second control means; and a second shift register that latches Δy and shifts the contents in response to a third control trigger pulse from the third control means. It has a third shift register that shifts in the lower direction, and first and second 1.times.1 bit multipliers. Serial output bit from second shift register and
The contents of the am register are supplied to the first multiplier,
Serial output bit from third shift register and
The contents of the bm register are fed to a second multiplier.
The first multiplier multiplies the serial output bits from the second shift register by the contents of the am register in response to a second control trigger pulse from the second control means; The serial output bit from the register is multiplied by the contents of the bm register in response to a third control trigger pulse from the third control means, and the least significant bit of the multiplication result is output for each multiplication operation. That is, the first and second multipliers output the multiplication results of a*Δx and b*Δy in units of 1 bit.

The matrix multiplier further includes addition means. The adding means is supplied with the output bits from the first and second multipliers and the serial output bits from the first shift register. The adding means repeatedly adds these three types of input bits. The 1-bit addition result of the addition means is serially input from the upper part of the first shift register in response to a first control trigger pulse from the first control means. The 1-bit addition result of the addition means becomes the j-th bit of e _i (j=0, 1, . . . p+q-1) in the calculation for the desired e _i+1 and the next set of Δx and Δy.

Now, the operation of the first shift register is controlled by the first control trigger pulse from the first control means, and the operation of the second shift register and the first multiplier is controlled by the second control trigger pulse from the second control means. 3 shift registers and the second multiplier
The operation is controlled by a third control trigger pulse from the control means. Therefore, the respective bit data from the first and second multipliers and the first shift register supplied to the addition means are correctly aligned, and therefore the addition means outputs a・Δx+b・
The results of the product-sum operation indicated by Δy+e _i are output in order starting from the lower bit.

[Embodiment of the Invention] An embodiment of the present invention will be described below with reference to the drawings.

FIG. 1 shows the configuration of a matrix multiplier according to an embodiment of the present invention. The matrix multiplier shown in FIG. 1 is used to calculate e _i+1 (=a·Δx+b·Δy+e _i ) in equation (1) above. In Figure 1, 11
12 is a Δx register that latches a variable term Δx given from the outside (upper processor), and a Δy register 12 that latches a variable term Δy given from the outside in correspondence with Δx. Δx and Δy are k-bit integers expressed in two's complement numbers. In this example, k
=24.

Now, the constant terms a to d in the above equation (1) are real numbers (R). A real number (R) is expressed by the following equation (2) using a mantissa part (P) and an exponent part (E').

R=P×2 ^E ′ (2) The exponent part E′ can take a value expressed by −s≦E′≦t (3). However, s and t are positive integers. The above equation (3) can be rewritten as 0≦E≦m (4) by setting m=s+t and E=E′+s. Also, equation (2) can be rewritten as R=Pm×2 ^Em (5) by setting Pm=P×2 ^t . As is clear from equation (4), the exponent part E-m of equation (5) above is 0 or negative. In this embodiment, a real number (R) in the form of equation (5) above is applied. That is, in this embodiment, unlike a normal floating point number, the exponent part of all the handled data (real numbers) is set to be less than or equal to 0, and accordingly, the mantissa part is multiplied ^{by 2t} in advance.

From the above, constant terms a, b, c, and d can be expressed as a=am×2 ^ae-m b=bm×2 ^be-m c=cm×2 ^ce-m d=dm×2 ^de-m However, am to dm are l-bit integers expressed in two's complement, and ae to ad, m are integers satisfying the conditions 0≦ae, be, ce, de≦m.

In addition, e _i and f _i in equation (1) are expressed as two's complement numbers,
It is a fixed-point number with p bits for the integer part and q bits for the fractional part.

Using these, e _i+1 and f _i+1 in equation (1) above become (6)
The equation becomes as shown in equation (7).

e _i+1 = am・Δx・2 ^ae-m +bm・Δy・2 ^be-m +e _i (6) f _i+1 = cm・Δx・2 ^ce-m +dm・Δy・2 ^de-m +f _i ( 7) The above equation (6) is schematically shown in Figure 2. As is clear from the above explanation and FIG. 2, m indicates the reference point (position) relative to the decimal point position of each handling data, and ae and be are
Indicates the number of bits of (am・Δx) and bm (bm・Δy) up to the least significant bit. The number of bits from the reference point to the least significant bit of e _i is (m-q) bits.
Therefore, when handling am (am・Δx) and bm (bm・Δy), count ae and be, and when handling e _i , count m−q to determine the timing to start processing. , it becomes possible to align the digits correctly.

Referring again to FIG. 1, 13 is the am register that latches the constant term am, 14 is the bm register that also latches bm, 15 is the ae register that also latches ae, and 16 is the be register that also latches be.
It is a register. As mentioned above, am and bm are 1-bit integers expressed as two's complement numbers. In this example, l=24. am, bm, ae, and be are given in advance from the outside (upper processor). 17 is a Δx shift register that loads the variable term Δx (x relative coordinate value) latched into the Δx register 11 and shifts its contents downward in accordance with the control trigger pulse CLK2; 18 is a Δx shift register latched into the y register 12; Load the variable term Δy (y relative coordinate value) and control its contents with the trigger pulse
This is a Δy shift register that shifts downward in accordance with CLK3. Also, 19 and 20 are register 1
The sign bits S of Δx and Δy from 1 and 12 are latched, and the most significant bits of shift registers 18 and 19 are
This is a flip-flop that supplies the MSB position.

21 loads the held content am from the am register 13 and sends the control trigger pulse CLK between it and the serial output bit X'j from the Δx shift register 17.
1×l bits (l=24) multiplied according to 2
The multiplier 22 loads the held content bm from the bm register 14 and multiplies it with the serial output bit Y'k from the Δy shift register 18 according to the control trigger pulse CLK3. = 24) multiplier. The multipliers 21 and 22 are
The least significant bit of the result for each multiplication operation
It is designed to output LSB. multiplier 21,
22 is constructed using, for example, three 25LS14 (1×8 bit multipliers) manufactured by AMD, USA.

Reference numerals 23 and 24 denote control blocks (DELAY) that incorporate counters (not shown) and generate control trigger pulses CLK2 and CLK3. control block 23,
24 loads ae and be from registers 15 and 16, counts down the values to "0" using the basic clock signal CLK, and then outputs control trigger pulses CLK2 and B in synchronization with the same clock signal CLK.
CLK3 is generated k+l times (k=24, l=24). Control trigger pulse CLK2 from control block 23 is supplied to Δx shift register 17 and multiplier 21, and control trigger pulse CLK3 from control block 24 is supplied to Δy shift register 18 and multiplier 22. 25 again
is a control block (DELAY) that generates the control trigger pulse CLK1. The control block 25 is
A predetermined value m-q is held internally, and when the operation starts, m-q is loaded into an internal counter (not shown), and after that value is counted down to "0" by the basic clock signal CLK. , a control trigger pulse CLK1 synchronized with the same clock signal CLK is generated p+q times. As mentioned above, m indicates the number of bits from the reference point to the decimal point, and is, for example, 51. Furthermore, p and q are the number of bits in the integer part and decimal part, respectively, of the operation result e _i+1 . In this example, p=40 and q=8.

26 is a p+q bit (p+q=48) e shift register which latches the operation result e _i+1 (e _oew ) and serially outputs its contents as e _i (e _pld ) for the next operation. The e shift register 26 is
Control trigger pulse CLK from control block 25
1, a shift operation is performed in the lower direction. e
The serial output bit Ei of the shift register 26 is supplied to a flip-flop (L) 27 for timing correction.

31 is the serial output bit AX'j of the multiplier 21
and a 1-bit adder (ADD) for adding the output bits E'i of the flip-flop 27; 32 is a flip-flop (L) for timing correction that holds the addition result ^R1 of the adder 31; Further, 33 is a timing correction flip-flop (L) that holds the serial output bit BY'k of the multiplier 22, and 34 is a 1-bit adder (ADD) that adds each output bit of the flip-flops 32 and 33. The addition result R ² _n of the adder 34 is _{the mth}
(m=0, 1, . . . p+q) bits are supplied to the MSB of the e-shift register 26.

Next, the operation of one embodiment of the present invention will be explained with reference to the timing chart of FIG. In addition, the third
In the figure, Ti (i=1, 2,...98) represents the clock cycle, RDY represents the status signal indicating the state of the matrix multiplier shown in FIG. 1, and D1,
D2 and D3 indicate changes in the values (ae, be, m-q) loaded into control blocks 23, 24, 25.

In the matrix multiplier shown in Figure 1, before calculating e _i+1 for each set of Δx and Δy, am, ae, bm, be, and e ₀ (initial values of e _i ) are input from the outside (upper processor). Given sequentially. Then, am is set in the am register 13 and ae is set in the ae register 15, respectively. Also, bm is stored in the bm register 14, be is stored in the be register 16, and e ₀ is stored in the e shift register 26.
are set respectively. After this, Δx, Δy
Only the sets of are given sequentially from the outside, and coordinate transformation is performed continuously.

Now, the operation of the matrix multiplier shown in FIG.
It begins when becomes high level (T1).
First, am in the am register 13 is set to the multiplier 21
Then, bm in the bm register 14 is sent to the multiplier 22, and ae
ae in the register 15 is sent to the control block 23 (a counter not shown), be in the be register 16 is sent to the control block 24 (a counter not shown),
Δx in Δx register 11 is Δx shift register 1
7, and Δy in the Δy register 12 is loaded into the Δy shift register 18, respectively (T2).
Also, at T2, the sign bit S of Δx in the Δx register 11 is transferred to the flip-flop 19.
The sign bit S of Δy in Δy register 12 is loaded into flip-flop 20, respectively. Furthermore, at T2, m-q held in the control block 25 is loaded into a counter (not shown) in the block 25. However, control block 2
3, 24, and 25 count down using the basic clock signal CLK until the loaded value becomes "0". In this example, ae=0, be=
41, m-q=51-8=43. Therefore, the control block 24 counts down from T3 to T44, and the control block 25 counts down from T3 to T46. In addition, in the control block 23, ae
= 0, so no countdown is performed. This operation corresponds to the process of aligning the decimal points in FIG.

The control blocks 23, 24, and 25 start the control trigger pulses CLK1 and CLK from that time when the loaded value becomes "0" due to the countdown operation.
2. Generate CLK3. Specifically, the control blocks 23, 24, 25 control the basic clock signal.
Trigger pulse that directly controls the CLK pulse train
Output as CLK1, CLK2, CLK3. Note that since ae=0 in the control block 23,
Control trigger pulse CLK2 is generated from T3.

Control trigger pulse from control block 23
CLK2 is Δx shift register 17 and multiplier 2
1. As a result, the Δx shift register 17 performs a downward shift operation (right shift operation).
Start. The serial output bit X'j from the LSB of the Δx shift register 17 is supplied to the multiplier 21. The multiplier 21 outputs the am register 13 in response to the control trigger pulse CLK2 from the control block 23.
Loads the content am and controls the multiplication of am and X′j from the Δx shift register 17.
Performed according to CLK2. And the multiplier 21 is
The LSB (AX′j) of the product is output. This AX′j is
As is well known, this is the LSB of the addition result of the upper bit string of AX'j-1 output last time and the bit string indicating the current 1.times.l bit multiplication result.
That is, in the multiplier 21, when the above addition result is obtained, it is shifted to the right by 1 bit, its serial output bit is used as AX'j, and the remaining bits are used as internal input for addition with the next 1×1 bit multiplication result. Retained. In the Δx shift register 17, when the contents held therein are shifted to the right by one bit by the control trigger pulse CLK2, the held bit of the flip-flop 19, ie, the sign bit S, is input to the MSB thereof.

On the other hand, the control trigger pulse CLK3 from the control block 24 is supplied to the Δy shift register 18 and the multiplier 22. As a result, the Δy shift register 18 starts a downward shift operation (right shift operation). LSB of Δy shift register 18
The serial output bit Y'k from is supplied to multiplier 22. The multiplier 22 loads the content bm of the bm register 14 in response to the control trigger pulse CLK3 from the control block 24, and multiplies the content bm by Y'k from the Δy shift register 18 in response to the control trigger pulse CLK3. Let's do it. And the multiplier 22 is
The LSB (BY′k) of the product is output.

Further, the control trigger pulse CLK1 from the control block 25 is supplied to the e-shift register 26.
As a result, the e-shift register 26 starts a downward shift operation (right shift operation), and holds the previous calculation result e _i+1 (however, the first Δx,
In the case of an operation on a set of Δy, the initial value e ₀ ) is output serially as e _i starting from the least significant bit E ₀ . The serial output bit Ei from the LSB of the e-shift register 26 is temporarily held in the flip-flop 27, subjected to timing adjustment, and is supplied to the A input of the adder 31 as E'i. Adder 31
The serial output bit AX'j from the multiplier 21 is supplied to the B input of the multiplier 21. The adder 31 then adds E'i and AX'j. Adder 3
The addition result R ¹ _l (E'i+AX'j) of 1 is temporarily held in the flip-flop 32, subjected to timing adjustment, and supplied to the A input of the adder 34. Adder 34
The serial output bit BY'k from the multiplier 22 is once held in the flip-flop 33, subjected to timing adjustment, and then supplied to the B input of the multiplier 22.
Thus, in the adder 34, R ¹ _l and BY'k are added. Addition result of adder 34 R ² _n (E′i+AX′j
+BY'k) is serially input to the MSB of the e shift register 26 as the m-th bit of the desired e _i+1 (e _oew ). At this time, the operation result already held in the e shift register 26 is shifted downward, and its LSB is transferred to the flip-flop 27 as Ei.
supplied to

When the above operation is repeated and the serial input of the addition result R ² _n of the adder 34 to the e-shift register 26 is repeated p+q (=48) times, the contents of the e-shift register 26 at that time become the required e _{i +1} (=
a・Δx+b・Δy+e _i ). As described above, e _i+1 obtained in the e shift register 26 is used as e _i in the calculation for the next set of Δx and Δy. Note that in this embodiment, instead of e _i+1 determined by the e shift register 35, its upper p
(=40) bits, that is, the result of calculating the integer part data e′ _i+1 . That is, in this embodiment, q (=8) bits of the decimal part are used to improve the accuracy of calculation.

As mentioned above, according to this embodiment, e _i+1 (=
a・Δx+b・Δy+e _i ) can be calculated.
In addition, the matrix multiplier in Fig. 1 is f _i+1 (=c・Δx
+d・Δy+f _i ) can also be used for calculation.
In this case, am register 13 is used for cm latch, bm
Register 14 is for DM latch, ae register 15 is for DM latch.
For ce latch, be for register 16 to de latch, e
Shift registers 26 may be used for the f _i+1 latches. Similarly, the multiplier 21 may be used for multiplying cm and Δx, and the multiplier 22 may be used for multiplying dm and Δy. In this case, regarding the operation of calculating f _i+1 ,
In the operation explanation of e _i+1 calculation mentioned above, a, b, e
I would like to read them as c, d, f. Furthermore, by providing two matrix multipliers shown in FIG. 1, one for calculating e _i+1 and the other for calculating f _i+1 , it is also possible to obtain e _i+1 and f _i+1 in parallel. In this case, there may be only one set of the Δx register 11 and the Δy register 12. Also,
It is also possible to use the matrix multiplier of FIG. 1 alternately for calculating e _i+1 and f _i+1 . However, in this case, am register 13, bm register 14, ae
It is necessary to set data in the register 15, the be register 16, and the e shift register 26 each time e _i+1 or f _i+1 is determined. Further, when a result is obtained in the e-shift register 26, it is necessary to save the result in a save register and load the saved data into the e-shift register 26 at the time of the next operation.

Note that the matrix multiplier according to the present invention is applicable not only to coordinate transformation in graphic processing but also to multiplication of row vectors and column vectors in general arithmetic expressions such as the one expressed by equation (1).

[Effects of the Invention] As detailed above, according to the present invention, a.
A row vector consisting of three elements: b, e _i (a, b are constant terms and real numbers, e _i is the previous calculation result and a fixed point number), and Δx, Δy, 1 (Δx, Δy are variable terms) The product-sum operation represented by a, Δx+b, Δy+e _i , which is the product of a column vector consisting of three elements (integer), can be performed at high speed with a simple hardware configuration.

[Brief explanation of drawings]

FIG. 1 is a block diagram of a matrix multiplier according to an embodiment of the present invention, FIG. 2 is a diagram for explaining the principle of the invention, and FIG. 3 is a timing chart for explaining the operation. 11...Δx register, 12...Δy register,
13...am register, 14...bm register, 1
7...Δx shift register, 18...Δy shift register, 21, 22... Multiplier, 23-25...
Control block, 26...e shift register, 3
1, 34... Adder.

Claims (1)

[Claims] Constant terms a, b expressed as 1 am x 2 ^ae-m , bm x 2 ^be-m (am, bm are l-bit integers expressed in two's complement, ae, be, m are A row vector consisting of three elements: an integer that satisfies 0≦ae, be≦m) and the previous operation result e _i (e _i is a fixed-point number with p bits in the integer part and q bits in the fraction part, expressed as a two's complement number) and a column vector consisting of variable terms Δx, Δy (Δx, Δy are k-bit integers expressed in two's complement) and a fixed value of 1. It is a matrix multiplier that performs a product-sum operation indicated by _i , and has an am register that latches the above am, and an above bm
The bm register that latches the clock, and the count is performed according to the basic clock signal by specifying the start of operation.
A first control means that repeatedly generates a first control trigger pulse synchronized with the basic clock signal when the difference between m and q is counted; a second control means that repeatedly generates a second control trigger pulse synchronized with the basic clock signal when counting;
a third control means that repeatedly generates a third control trigger pulse synchronized with the basic clock signal when the above be is counted, and an initial value e ₀ in the initial state;
a first shift register for latching the first shift register, the contents of which are sequentially shifted in a lower direction in response to the first control trigger pulse from the first control means;
a shift register; a second shift register that latches the Δx and sequentially shifts its contents downward in response to the second control trigger pulse from the second control means; A third shift register that sequentially shifts downward in response to the third control trigger pulse from the third control means, and a third shift register that performs multiplication of the serial output bit from the second shift register and the contents of the am register. The first multiplier of 1×1 bits is executed in response to the second control trigger pulse from the second control means, and the third multiplier multiplies the serial output bit from the third shift register by the contents of the bm register. A 1×l bit second multiplier executed in response to the third control trigger pulse from the control means, and a maximum of the multiplication results output from the first and second multipliers for each multiplication operation. addition means for adding the lower bits and the serial output bits from the first shift register; the first shift register adds the output bits from the addition means to the first bits from the first control means; A matrix multiplier characterized in that serial input is performed from an upper level according to a control trigger pulse. 2. The first control means generates the first control trigger pulse p+q times, the second control means generates the second control trigger pulse k+l times, and the third control means generates the second control trigger pulse k+l times.
2. A matrix multiplier according to claim 1, wherein said control means generates said third control trigger pulse k+l times.