JPH0443461A - Matrix multiplication circuit - Google Patents

Abstract

PURPOSE:To reduce the scale of hardware and to speed up a multiplication processing by providing a row number switching means which switches the designation of the row number of an element used as a multiplication coefficient in a coefficient matrix and an addition means which adds respective coefficient multiplication values outputted from respective storage means in a parallel multiplication means and which outputs it as the element of an output matrix. CONSTITUTION:Multiplied column elements k=1 - k=8 for one row in a multiplied matrix are collectively multiplied by multiplied row elements j=1 - j=8 for one row in the coefficient matrix by the parallel multiplication means. Respective multiplication results are added by the addition means 12 and they are outputted as the elements of the output matrix. The row number of the multiplied row element in the coefficient matrix is switched by the row number switching means 11 and the column number of the multiplied column element in the multiplied matrix is switched by a column number switching means 14. Thus, respective elements of the output matrix is operated. Thus, the scale of the circuit is reduced and the circuit can be applied to a high speed picture processing and the like.

Description

DETAILED DESCRIPTION OF THE INVENTION "Field of Industrial Application" The present invention relates to a matrix multiplication circuit particularly suitable for use in image compression processing.

"Prior Art" In image processing, information is compressed by performing so-called orthogonal transformation on a matrix of original image data. As one of these orthogonal transformations, D C
'r (D 1screLe Cosine Tra
nafore (discrete cosine transformation) is known.

Here, DCT will be explained. A matrix of NXN (N is an integer) image data (this image data represents the brightness and color of the corresponding pixel) is expressed as f(ijXi=
1 to N, j=1-N), the DCT positive transform value F b (u, v) for this is given as shown in equation (1) below.

Pt>(u, v) N" i=1 3=1 ......(1) However, here, u-1-N, v=I~NC C(u)-1/ FTat Li= 1C(u)=
1, at u=2~NC(u)=
1/FTat u= 1C(u)=l
at u= 2~N again. Aiu and A
iv are each Walsh functions and are given as follows.

Then, the DCT positive transform value F b (u, v) (u= l
-N, v=IN) is given, the following formula (2)
The original image data matrix r(i
, D (i=1-N, j=l~N).

f(i, j) N =Σ・Σ C(u)・C(v)・Fb(u,■
)・Aiu−Ajvun v=1 (2) In the above formula (1), F b(u, v)(u=1~
N, v=1-N) is equal to the coefficient of each spatial frequency component that makes up the original image. Using these coefficients, the above formula (
By performing the inverse transformation of 2) and obtaining image data f(i, j), the original image is faithfully reproduced. However, in reality, these coefficients r(i, j
) (i = 1-N, j = 1-N), power concentration occurs in visually important DC components and low-order components, and on the other hand,
Higher-order components that are not visually important have low power. Therefore, by allocating many bits to the low-order components and relatively few bits to the high-order components, or not transmitting them at all, the receiver receives the inverse of equation (2). By performing the conversion and reproducing the image, the amount of data when transmitting image data is reduced.

Incidentally, such image compression processing using CT is described in, for example, Japanese Patent Laid-Open No. 31473/1983.

``Problem to be solved by the invention'' By the way, the above-mentioned orthogonal transformation is generally performed by converting the original image data into a matrix and multiplying this matrix by a coefficient matrix for orthogonal transformation. Executing the multiplication process requires large-scale hardware and requires a long calculation time. Generally, a method is used in which the original image data matrix is divided into several small blocks and image compression processing is performed for each small block, but in this method, the required hardware is reduced. However, there is a problem in that the time required for multiplication cannot be shortened. In addition, in the field of image compression processing,
In addition to requests for smaller hardware and faster arithmetic processing, there is also a desire to perform image compression processing by dividing the original image into blocks of a desired size, depending on the desired image precision or degree of compression. There was a request.

This invention was made in view of the above-mentioned circumstances, and requires only a small amount of hardware, and can perform multiplication processing at high speed. Moreover, the multiplicand matrix is divided into blocks, and each block is divided into blocks. It is an object of the present invention to provide a matrix multiplication circuit that can freely switch the method of dividing blocks when multiplying coefficient matrices.

"Means for Solving the Problems" The present invention provides a multiplicand matrix storage means for storing a multiplicand matrix and outputting each element belonging to a designated column number as a multiplicand column element; It is constituted by a column number switching means for switching the designation of column numbers, and a plurality of storage means corresponding to each column of the multiplicand matrix, and each storage area constituting each storage means stores information for each coefficient in a predetermined coefficient matrix. Each coefficient multiplication value obtained by multiplying each of the coefficient elements' for one column whose column number corresponds to the storage means by six values within the range that each element of the multiplicand matrix can take is stored. and for each storage means,
The corresponding multiplicand column element and the row number of the one to be used as a multiplication coefficient among the coefficient elements for one column are input as addresses, and the coefficient multiplication corresponding to each multiplicand column element is input from each storage means. a parallel multiplication means configured to obtain a value; a row number switching means for switching the designation of a row number of a zero element used as a multiplication coefficient in the coefficient matrix; and each coefficient outputted from each storage means in the parallel multiplication means. It is characterized by comprising an adding means for adding the multiplied values and outputting it as an element of an output matrix.

"Operation" According to the above configuration, the multiplicand column elements for one column in the multiplicand matrix and the multiplicand elements for one row in the coefficient matrix are multiplied all at once by the parallel multiplication means, and each multiplication result is are added by the adding means and output as elements of the output matrix. and the row number of the multiplicand element in the coefficient matrix is switched by the row number switching means, and
Each element of the output matrix is calculated by switching the column number of the multiplicand column element in the multiplicand matrix by the column number switching means.

"Embodiment" Hereinafter, an embodiment of the present invention will be described with reference to the drawings.

FIG. 1 is a block diagram showing the configuration of a matrix multiplication circuit for DCT according to an embodiment of the present invention. In addition, in the same figure,
” Among the operations of the bipedal formula (1), matrix multiplication i=l j=
Only the parts related to the execution of 1 are shown.

In FIG. 1, 10 is a matrix of input image data to be subjected to DCT processing [X] = X jk (j = 1 to B, =
1 to 8) This is a RAM (random access memory) that stores f (corresponding to i, D) in equation (3), and data for 8 x 8 pixels of input image data is input separately at a predetermined period. Sampling is input from a source etc.

One pixel data is composed of Nin bits, for example, 8 bits. Further, information specifying the column number j is given to RAM10 as address data at every predetermined period, and one column of image data [X k]=X
jk (j=1 to B) are read out in bulk. The image data of this - column is then latched and taken into ~L. Here, address switching in RAMl0 and data fetching in latches Ll-L8 occur every 32 times the period T32=32·T, where T is the system clock period of the system in which this matrix multiplication circuit is installed. This is done in synchronization with the clock.

1 to 8 are ROMs (read only memories), and 11 is a row number switching circuit. As shown in FIG. 2, each storage area of ROM1 to ROM8 has an image data matrix [X]=Xjk(j
= 1 to B, and = 1 to B), and is divided into eight sectors (0th sector to 7th sector). Each sector has the above-mentioned DCT coefficient C1j (i=1
~8, j=1~8) (aiu in the above formula (3)
-aiv) is assigned.

More specifically, the eight sectors that make up ROMI have coefficients Ci, (i=1-8)... The eight sectors that make up ROM j have coefficients C1j (i=1-8).
... Coefficients C1a (i-1 to 8) are respectively assigned to the eight sectors constituting the ROMB.

And each of ROM1-8 has a row number switching circuit! I
The 3-bit row number switching data CT3 output from the latches Ll to
8, image data X, to X, k are input as intra-sector addresses, respectively.

FIG. 3 shows the storage contents of each storage area of the (i-1)th sector in ROMj to which the coefficient C1j is assigned. Here, image data Xjk for one pixel is Ni
Assuming that it is composed of n bits (N in is an integer), the data range of image data Xjk is 0 to (2 to the Nin power - 1), and each sector has (2 to the power Nin) storage areas (addresses 0 to (2 to the power of Nin - 1)) are provided. Then, as shown in FIG.
, C1j-11 for the intra-sector address rlJ, and so on, the value obtained by multiplying the intra-sector address by the coefficient C1j is stored. By writing data in this way, image data Xjk is transferred to RO via latch Lj.
When input as an intra-sector address to Mj, the ROM
Data C1j-xjk is read from j. and,
In this embodiment, the line number switching data CT3 has a cycle '
Since the row number switching circuit 11 switches every r4=4·T, the output data of ROM j is C1j−X jk%Ci+1·Xj
k,... can be switched. RO in this example
The access time for M1 to M8 is within 4·T, and after the line number switching data CT3 is switched, it takes within 4·T to obtain the corresponding output data.

In FIG. 1, 12 indicates each output data (
an adder circuit for adding (consisting of Nout bits), 1
3 is a latch that holds output data of the adder circuit 12; These adder circuits 12 and latches! 4th about 3
This will be explained with reference to the figures.

As shown in FIG. 4, the outputs of ROMI and 2 are added by adder AI, the outputs of ROM3 and 4 are added by adder A2, the outputs of ROM5 and 6 are added by adder A3, and the outputs of ROM7 and ROM1 are added by adder A3. The outputs of 8 and 8 are added by adder A4. These adders Al-A
The number of output bits of 4 is (NOLIL+4) bits. Further, the outputs of adders AI and A2 are added by adder A5, and the outputs of adders A3 and A4 are added by addition 480. These adders A5, A
The number of output bits of 6 is (N out + 2) bits. Furthermore, the outputs of adders BA5 and A6 are added by adder A7. The number of output bits of this adder A7 is (Nout+3) bits. Here, each addition speed of adder AI-A7 is sufficiently faster than the access time of ROMs 1-8. Therefore, ROM
Immediately after each output data of ROMs 1 to 8 is obtained, each output data of ROMs 1 to 8 and each output data of adder AI-A7 are processed so that the data phase of all these outputs is the same and any data is independently Selective access becomes possible. Furthermore, assuming that the above-mentioned state cannot be realized due to constraints on the operating speed of the node/ware, at least ROM1
If the time required from the input of output data from .about.8 to the output of the sum from adder .DELTA.7 is within 4.1", at least the 8.times.8 DCT operation shown in FIG. 5, which will be described later, is possible.

Each output data of ROMs 1 to 8 is input to the input port PI of the selector SEL, and the adder A is input to the input port P2.
Each output data of l-A4 is inputted, the output data of adders A5 and A6 is inputted to the human-powered boat P3, and the output data of the adder A7 is inputted to the human-powered boat P4.

Then, the selector SEL selects the input port according to the control information C0NT, and also selects the input port according to the control information C0NT.
Selection, switching, and output of input data within the boat are performed in synchronization with selector clocks having different speeds according to T.

Data output from the output port of the selector SEL is sequentially written into the latch 13. The latch 13 has a storage area for data for one column (in the case of this embodiment, eight pieces),
Input data to the latch 13 is written to each storage area in synchronization with the selector clock. Further, the writing position of input data is controlled according to control information C0NT. I'll explain it in a little more detail now. When the control information C0NT is "0" and the input port Pl is selected, the subclocker having twice the frequency of the system clock (period T) mentioned above is supplied as a selector clock, and thereby the period T/
The input source is switched as ROM1-ROM2→...-ROMB every 2 and connected to the output port (
If high-speed subclock is not available, selector S
The output port of EL is configured as 2 ports, and RO is output every period T.
MI and ROM2-ROM3 and ROM4→...-ROM
7 and ROM8, and connect each interpersonal power to the two output ports, respectively). In addition, if the control information C0NT is “1)”, the input port P
2 is selected, adder Al-A2→A every period T
3-A4 and the input light are switched and connected to the output port, and when the control information C0NT is "2" and the input port-1-P3 is selected, the adder is switched to the adder A5-A6 every cycle 2·T. When the control information C0NT is [3] and the input capo P4 is selected, the adder Δ7 is connected to the output port.
The output of is selected and connected to the output port for the entire period T4. One column of data output from the latch 13 is sequentially transferred to a buffer memory or the like (not shown) and used for subsequent image processing or the like.

From the above, the matrix multiplication circuit shown in FIG.
Various matrix multiplications are possible by setting the input data string to be taken into ~L8, (1) setting the row number switching data CT3, and (2) setting the control information C0NT of the selector SEL.

The operation of this matrix multiplication circuit will be explained below.

FIG. 5(a) and (b'') show the control information C0NT.
The case where =r3J is shown.

As a result, for example, 8X8DCT, 8th order 1
A dimensional DCT DCT (Y= @Cij −Xjk) is realized.

As shown in Figure 5(a), this is the 8
It is expressed as a matrix product [Y] of a ×8 coefficient matrix [C] and an 8X8 data matrix [X] to be converted.

Figure 5 (
b) is shown as a time chart. First, the image data string [X k]'' for one column of the data matrix [X] is read out from the RAM l0, and these data The row number switching data CT3 is sequentially switched from "0" to "7" at intervals of period T4. First, when the line number switching data CT3 is "0", as is clear from the explanation of each ROM content address in FIG. 2 and FIG. X tk, -
1C. written to a memory location. Next, after cycle T4, when the row number switching data CT3 is switched to rlJ, Ctt is transferred from ROM1 to C0 to C0 and X, respectively.
"X tk,...Cfl・X,k is read out,
The sum, also from adder A7, is written to the second memory location of latch 13. Thereafter, a similar operation is performed every time the row number switching data C'r3 changes from [2] to "7", and all the first to eighth memories of the latch 13 are written during the period T32. , this becomes the data string [Yk] for one column of the output product matrix [Y]. Then, when the cycle T32 changes, the output data string [Yk] is output from the latch 13 and transferred to a buffer memory (not shown) or the like. At the same time, the next column of image data [Xk+
11 = X + (k”+) ~
The output data string [Y k+,] corresponding to the data string [X k+,] is obtained by the same operation as the data string [Xk] described above, and is similarly stored in the buffer memory, etc. be transferred. Thereafter, similar operations are performed, and in the end, by repeating the period T32 eight times, the 8x8
Each element column [Y +] of the product matrix [Y]...[Y,]
are sequentially calculated on the buffer memory, etc., and finally the desired output product matrix [Y] is obtained. According to this matrix multiplication circuit, 8×8D C'r l! Image data processing is performed in a time of 8-'I': 2.4-256.T.

Let's take a moment to consider this calculation speed.

For example, when processing image data of 352 x 28 B pixels for one frame, the total time required is 256-T-(35
2x288)/(8x8)=405504·T. To perform image processing in accordance with NTSC standards, 30
It is necessary to compress the image at a rate of one frame per second, and finding the system clock cycle T that satisfies this condition is 'l
'=82.20ns, or 12.165M in frequency
Hz. Considering current integrated circuit technology, this means that
This is a sufficient number to clear.

Furthermore, the above-described 8x8 matrix product calculation configuration can be applied to other applications by changing the setting of the input data string [Xkl. FIG. 6 shows an application to mask filtering. When encoding in block units like DCT, mask filtering is often performed in block units to smooth quantization noise, but as shown in Figure 6, the target data (here X, ) around 4
The data contents are formatted as a data string [Xkl, and the above-mentioned 8x8 matrix product arithmetic configuration circuit! If a bit shift means 15 and an adder 16 are provided for supplying the data to the [Xk] input terminal of the circuit 4, resetting the contents of the coefficient matrix in this circuit 14 for mask filtering, and performing coefficient multiplication of the target data, , the required 3×3 mask filtering can be easily achieved.

Next, by this matrix multiplication circuit, 4×4.2×2.1×
For the case of performing each matrix multiplication of 1, including an application example,
This will be explained based on FIGS. 7 to 9.

FIGS. 7(a) and (b) show control information C0NT=
The case of r2J is shown. This makes it possible to realize 4×4 DCT. The four 4×4 coefficient matrices for orthogonal transformation [C, the four 4×4 data matrices to be transformed [Xal~[Xdl], and the corresponding four output matrix products [Ya~[Yd] are ,
As shown in FIG. 7(a), they are each arranged in an 8×8 range. The operation will be explained by showing the state changes of each part in the time chart of Fig. 7(b'').
The required 4×4 by decomposing the DCT operation into upper and lower parts
The DCT calculations are performed in parallel.

In the first half of period T32, one each of matrices [Xa and [Xc] or matrices [Xb and [Xdl] is stored from RAM10.
One column of image data string [Xkl] is read out in a form in which the elements of the column are connected in series, and the next one column of data string [X k+1] is newly read out in the second half period. During the period when the row number switching data CT3 is "0" to "3", the image data string [Xk,] is processed, and the selector SEL
selects alternately the sum of the outputs of ROMs 1 to 4 outputted from adder A5 and the sum of the outputs of ROMs 5 to 8 outputted from adder A6, and captures these onto latch 13 as shown in the figure. Then, an output data string [Yk] is formed. During the period when the row number switching data CT3 is "4" to "7", the image data string [X k+, ] is processed, and the selector SEL selects the ROM1 to ROM output from the adder A5.
The sum of the outputs of 4 and RO output from adder 486
The sum of the outputs of M5 to M8 is selected as AC JJ], and this is loaded onto the latch 13, resulting in an output data string [Y k+,]
will continue to form.

In this way, two output data strings are created during the period T32, so if the input data strings are sequentially input and processed in the same way up to the data string [X k+, ], the total will be 128·T. After the elapse of time, the four output product matrices [
Output results in an 8×8 range corresponding to [Ya] to [Yd] are obtained in a buffer memory or the like.

Note that, as in the case of the 8x8DCT described above, the period T32
is the basic period of repetitive operation, and 1 every period T4
The output of the adder is taken into the selector SEL and the latch 13
When performing 4×4 DCT with various operations, such as outputting data to
J-rOJ-rlJ -rlJ→r2J-r2J→r3
It is sufficient to switch as follows: J-r3J-rOJ-rOJ-... In this case, the calculation speed will naturally be halved.

FIG. 8(a) and (b') show the control information C0NT.
= rlJ is shown. With this, we can realize 2X2DC'I゛. 16 2x2 coefficient matrices for orthogonal transformation
[C], 16 2×2 data matrices to be converted [Xa3
~[Xp], and the corresponding 16 output matrix products [Y
a] to [Yp] are each 8 as shown in Figure 8(a).
They are arranged in a ×8 range. The time chart in FIG. 8(b) shows changes in the state of each part.

According to this, in a total time of 64·T, 8×8 outputs corresponding to the set of 16 output product matrices [Ya] to [Ypl are obtained in the buffer memory or the like.

In this case, the contents of ROM1 to ROM8 used during the period when line number switching data CT3 is "2" to "7" are exactly the same as in the case of row number switching data CT3.6 (rOJ and rlJ), so ROM1 Figure 8 (
a ) coefficient matrix above! /4 only (2 × 2 coefficient matrix [C
] are lined up horizontally), and the line number switching data CT
3 every cycle T4, "0" → "1" → "0" → rlJ →
. . . may be switched.

Furthermore, as an application thereof, it is also possible to simultaneously calculate four different types of 2X2DCT during a period of 256·T. The coefficient matrix shown in FIG. 8(a) is divided into four in the vertical direction, and four different 2×2 coefficient matrices [Ca] ~
Let [Cd] be in the form of four identical pieces arranged horizontally in each divided part. Then, by the same process as when reducing the capacity of the coefficient ROM described above, first, in the first 64·T period, a set of target output product matrices is obtained for the coefficient matrix [Cd], and then the coefficients are sequentially Matrix [Cb],...
[Cd] will be processed in the same way. Since a different set of 2X2DCT output product matrices is obtained for each process, when transferring these from the latch 13 to a buffer memory etc., it is only necessary to arrange them separately so that they can be used independently of each other (note that the coefficient It goes without saying that similar results can be obtained even if the matrices [Ca] to [Cd] are processed in parallel).

Note that the output matrix of 2X2DCT has 4 matrix elements for one matrix, and the data length of each element is 16+1 bits in this example, so unless high speed is particularly required, serial port output (However, it is assumed that the T/2 sub-clock described above is used or, in the case of the system clock T, that the selector SEL has a two-vote output configuration).

FIGS. 9(a), (b) and (c) show the case where the control information C0NT=rOJ. This makes it 1x!
Matrix multiplication operations can also be performed. An example of its application is, for example, a transformation as shown in FIG. 9(a) in which a certain vector basis is scaled to generate a new vector basis. This is expressed as 16xl in Figure 9(b).
6 matrix [C], prepare a 1X16 data matrix [X,] for scale change, and multiply these by matrix, which corresponds to a set of new vector bases Y1 to Y, whose scale has been changed. A 16×16 matrix [C′] is generated.

The time chart in FIG. 9(c) shows changes in the state of each part. According to this, a matrix [C'] corresponding to a new set of vector bases is obtained in a buffer memory or the like in a total of 32·T time. In this case, 8×8, that is, 64 pieces of data are all output from the selector SEL to the latch 13 within the period T32.
The selector SEL must use the aforementioned T/2 high-speed subclock, or if only the system clock T can be used, the selector SEL must have a two-port output configuration. Also, of course, the buffer memory
If no particular omissions are taken into account, eight times as much is required as in the case of the 8x8 DCT described above.

"Effects of the Invention" As described above, according to the present invention, it is possible to easily realize a small-scale, high-speed matrix multiplication circuit that can be applied to high-speed image processing and the like. Also, according to this matrix multiplication circuit,
Various matrix multiplications are possible by setting the input data string, ROM switching timing, output connection switching, etc., and it can also flexibly support various orthogonal transformations such as 8 x 8.4 x 4.2 x 2, IXI, etc. You can get the effect that you can.

[Brief explanation of drawings]

FIG. 1 is a block diagram showing the configuration of a matrix multiplication circuit according to an embodiment of this description. FIG. 2 is a diagram showing the assignment of coefficients to ROMs 1 to 8 in the embodiment. FIG. FIG. 4 is a block diagram showing the adder circuit 12 and latch 13 in the same embodiment, and FIGS. 5(a) and (b) are the same. An explanatory diagram and a time chart showing the operation when the embodiment is multiplied by 8 x 8, Fig. 6 is a block diagram showing another example when the embodiment is multiplied by 8 x 8, and Fig. 7 ( a) and (b) are explanatory diagrams and time charts showing the operation when the same embodiment is multiplied by 4 x 4. Fig. 8 (a) and (b) are 1 and the same embodiment is multiplied by 2 An explanatory diagram and a time chart showing the operation when multiplication is performed; FIGS. 9(a), (b), and (c) are first and second explanatory diagrams showing the operation when the same embodiment is multiplied by txt. and the time chart Knee 1 to B.
ROM, I0-RAM. 11... Row number switching circuit, 12... Addition circuit, 13
...-Latch circuit.

Claims (1)

[Scope of Claims] Multiplicand matrix storage means for storing a multiplicand matrix and outputting each element belonging to a designated column number as a multiplicand column element; and a column for switching the designation of the column number of the multiplicand column element. It is constituted by a number switching means and a plurality of storage means corresponding to each column of the multiplicand matrix, and each storage area constituting each storage means has a column number corresponding to the column number of each coefficient in a predetermined coefficient matrix. Each coefficient multiplication value obtained by multiplying each of the coefficient elements for one column corresponding to the means by each value within the possible range of each element of the multiplicand matrix is stored, and each storage means stores On the other hand, the corresponding multiplicand column element and the row number of the one to be used as a multiplication coefficient among the coefficient elements for one column are input together as addresses, and the data corresponding to each multiplicand column element is input from each storage means. Parallel multiplication means for obtaining coefficient multiplication values; Row number switching means for switching designation of row numbers of elements to be used as multiplication coefficients in the coefficient matrix; and each coefficient output from each storage means in the parallel multiplication means. 1. A matrix multiplication circuit, comprising: addition means for adding multiplication values and outputting the multiplication values as elements of an output matrix.