JPH0226477A - Matrix element transposing device - Google Patents

Abstract

PURPOSE:To eliminate the uselessness of use of a storing area, to attain pipe-line processing and to make action at high speed by writing the operating result of a row converter in the vacant area in which reading by a column converter is finished in order. CONSTITUTION:A storing part 11 is constituted with arranging 16 ten bits shift registers and is specified with the pair of respective registers 11ij (i, j=1, 2, 3, 4). First, when the first row of the storing part 11 is selected, the writing of data is executed to the respective registers 1111-1114. When the writing of the data of the first row is finished, the output of a two bits counter 17 becomes 01, and the writing of the data of a second row is executed. When the writing of the data is finished to a fourth row in this way, a mode signal MODE is switched, a first column is selected, reading is executed at the same time as the writing. Thus, since a row converter 1 and a column converter 2 work at the same time and parallel processing is attained and can made into a pipe- line, high speed processing is attained with the capacity of one block portion.

Description

Detailed Description of the Invention [Industrial Application Field] The present invention provides a matrix computing unit that performs two-dimensional orthogonal transformation on a block of data expressed in a matrix such as image data. The present invention relates to a matrix element transposition device that is inserted between a row transformer and a column transformer and creates a transposed matrix from the calculation results of the row transformer.

[Prior Art] Conventionally, when compressing data by removing redundancy from image data, etc., a method has been known in which the data is expressed as a matrix and orthogonal transformation is performed on the data. Orthogonal transforms used to compress image data include Hadamard transform, Karhunen-Loeve transform, Barr transform, discrete cosine transform, and extrapolation predictive discrete sine transform.

For example, if we define an N-th orthogonal matrix as Φ=(Φ..l (n・1
．． 2゜-...,N), using this matrix Φ, the column vector x = fx, l (n=1.2.--...
・, N) is subjected to one-dimensional orthogonal transformation, resulting in a transform coefficient vector X=(Xゎ)(口・1 , 2 , , , , , ).

N) can be expressed by the following formula.

X=ΦX...■ When compressing image data, the original image data is divided into blocks of appropriate size, and a two-dimensional orthogonal transformation is applied to each block in which the data is expressed as a matrix. The two-dimensional orthogonal transformation is a two-dimensional extension of the equation (■), in which the block is a matrix x =
, n・1,2. ..., N),
By using the orthogonal matrix Φ-(Φ,,l (m□1,2.-,M) and M/=l?,,1(n・1,2...-,N), the following equation transform coefficient matrix X = +
X. ).

X=ΦxV...■■If we consider the formula, the operation of x'11/ can be regarded as repeating one-dimensional orthogonal transformation M times for each row of the matrix X, and the operation of ΦX is It can be considered that one-dimensional orthogonal transformation is repeated N times for each column of the matrix X.

In this way, the first step of the two-dimensional orthogonal transformation is a one-dimensional orthogonal transformation for each row, and the second step is a one-dimensional orthogonal transformation for each column.
While performing dimensional orthogonal transformation (the order may be reversed), the first step is to create a transposed matrix of this matrix for the matrix obtained by the row transformer, and the second step is column transformation of the obtained transposed matrix. If the calculation is performed using a converter, the row converter and column converter can be made to have the same configuration. As a means for creating such a transposed matrix, a matrix element transposing device generally called a transport memory is considered.

The transport memory that has been provided in the past has a storage capacity for one block, and as shown in Figure 3, it temporarily stores the matrix obtained by the row converter and converts the stored matrix from the column direction. By reading, the positions of rows and columns are swapped, and reading is performed as a transposed matrix with respect to the written matrix.

According to this configuration, reading to the column converter cannot be performed until all data for one block has been collected, so the row converter and column converter cannot be operated in parallel at the same time, which increases the processing time. The problem is that it becomes long.

As a solution to this problem, as shown in Figure 4,
A configuration with a storage capacity of two blocks is conceivable; US Pat. No. 4,302,775 and US Pat. No. 4,39
4,774), in this configuration, two memories RAM each having a storage capacity of one block 1. R
A M 2, and multiplexers MPX1 to MPX such that when one is in the write state, the other is in the read state;
It is designed to switch alternately. Each memory RAM, RAM, has an input terminal IN and an output terminal OUT.
, an address terminal ^DD, a write control terminal -R and a read control terminal RD.

The calculation result of the row converter is input to the input terminal IN, and the output to the column converter is taken out from the output terminal OUT.

A write signal WRITE is input to the write control terminal -R via a multiplexer MP×1, and a read signal READ is input to the read control terminal RD via a multiplexer MPX2.
is input. Furthermore, a multiplexer MP is connected to the address terminal of each memory RAM, RAM2.
Row address generation circuit HADD and column address generation circuit VADD are connected via X, , MPX. Each multiplexer MPX, ~MPX, is switched by a select signal SEL, while the memory RAM + (RA
In the state in which the write signal WRITE is input to the other memory RAM M2 (RAM), the read signal READ is input to the other memory RAM M2 (RAM), and the memory RAM L (RAM) to which the write signal -RATE is input is input. 2) is connected to the row address generation circuit HADD, and the leaching signal READ
The memory RAM 2 (RAM l
) is connected to the column address generation circuit VADD.

As described above, each memory RAM, RAM.

On the other hand, writing is performed in the row direction, and reading is performed in the column direction. Also, different memory RAM +
, Since writing and reading are performed on RAM 2 at the same time, the row converter and column converter can be operated in parallel at the same time. If they have the same operating speed, there is no idle time and processing can be performed efficiently.

[Problems to be Solved by the Invention] With the above configuration, processing time is shortened, but two blocks of memory are required, and the number of multiplexers is also required in proportion to the number of bits of data and address. The problem is that the scale of the hardware increases.

The present invention aims to solve the above-mentioned problems, and provides a matrix element transposition device that uses relatively small hardware and can perform relatively high-speed processing. be.

[Means for Solving the Problems] In order to achieve the above object, the present invention includes a storage unit having a capacity to store the calculation results for one block of the output of the row converter, and a memory unit that processes one block. The input control unit alternately switches the writing direction to the storage unit between the row direction and the column direction each time, and the input control unit alternately switches the reading direction from the storage unit between the row direction and the column direction every time one block is processed. an output control section;
The data written in either the row direction or the column direction via the input control section is read out in the other direction via the output control section, and the data is written to the area where the reading has been completed via the input control section. and an overall control section that controls writing from the other direction.

[Function] In the conventional configuration shown in FIG. 3, the present invention is advantageous in that when writing the results of the row converter, the area where data will be written from now on becomes a free area, and when reading by the column converter, the area that has already been This is done by focusing on the fact that the area where data reading is completed becomes an empty area, and with the above configuration, the calculation results of the row converter are sequentially written into the area that becomes empty after reading by the column converter, so the memory There is no waste in the use of space, pipeline processing becomes possible, and high-speed operation can be expected.

[Example] In this example, the case where the block size to be processed is 4 x 4 is exemplified, but there is no restriction on the block size. Also, if the block is not a square matrix, the number of rows and The storage capacity is a square matrix having the order of the larger value of the number of columns. For example, if the size of the block to be processed is MXN,
If M>N, settings are made so that the MXM matrix has a storage capacity.

The row converter and column converter are capable of operating on 10-bit data, and the output data of the row converter is 10-bit serial. Furthermore, four pieces of data for one line are processed in parallel in the row converter, and four pieces of data for one line outputted from the line converter are input to the storage unit 11 at the same time.

The storage unit 11 stores a 10-bit shift register in the 111th
], 16 shift registers are arranged in a row, and each shift register 11 is specified by a pair of z(i, j4, 2, 3.4). An input control unit 1 is provided before and after the storage unit 11, respectively.
．． 2 and an output control section 13 are provided, and each shift register 114 . is adapted to shift data in synchronization with the clock signal CLQCK during a period when the shift signal input from the outside is 1. This shift signal is generated by the overall control section 14. The overall control section 14 receives a clock signal CL from the output of the counter section 15.
The counter section 15 is composed of a frequency divider 16 that divides the clock signal CLOCK by 10, and a 2-bit counter 17 that counts the output of the frequency divider 16.

The mode signal MODE sets whether reading and writing to the storage section 11 is performed in the row direction or in the column direction.

That is, when the mode signal MODE is 1, the data input to the first input terminal IN of the four outputs of the row converter is transferred to the shift register 11. , (i·1, 2, 3° 4), and the other input terminals IN2 to IN are similarly set to be input to one of the shift registers 1112 to 111 . is set to be input. When the mode signal MODE becomes 0, data to each input terminal IN, ~IN, is transferred to one of the shift registers 11 . j~114J (J・
1, 2, 3.4). When the mode signal MODE is 1, data for one row in the row direction of the storage unit 11 can be stored by specifying a row, and when the mode signal MODE is 0, data for one row can be stored in the storage unit 11 by specifying a column. Data for one column in the 11 column direction can be stored.

Row designation when the mode signal MODE is 1 and column designation when the mode signal MODE is 0 are performed by the overall control unit 14. In other words, one of the two output terminals Q, , Q, of the 2-bit counter 17 can take on four states.
If the mode signal MODE is 1 when the output value is OO, the shift signal is input to the shift register 111J in the first row, so data is written in the first row of the storage section 11 after all. become. Here, each shift register 11. Since J has 10 bits each,
The shift signal remains in the same state while the 10 clock signals CLOCK are issued. This state is the clock signal CL.
This is realized by a frequency divider 16 that divides OCK into 1/10. When the outputs of the 2-bit counters 17 are the same and the mode signal MODE is 0, the overall control section 14 controls the shift registers 111 . Since this is specified, when combined with the settings of the input control unit 12, data will be written to the shift register 11□1 in the first column. When the mode signal MODE and the outputs Qo and Q of the 2-bit counter 17 are combined, the storage section 11 is specified as shown in the following table.

On the other hand, the output control section 13 has 8 4-to-1 multiplexers.
It consists of four 2-to-1 multiplexers.

The output control section 13, like the overall control section 14, is controlled by the mode signal MODE and the output of the 2-bit counter 17.The mode signal MODE controls the 2-to-1 multiplexer, A 4-to-1 multiplexer is controlled by the output of . 4
If the input terminals of the pair-one multiplexer are shifted from the top in FIG. 1 to A, B, C, and D, then A→D corresponds to the output value of the 2-bit counter 17 from OO→11. It is set as follows. For a 2-to-1 multiplexer, the input terminal A from the top in FIG.

If B is selected, A is selected when the mode signal MODE is 1, and B is selected when the mode signal MODE is 0. Therefore, if the output value of the 2-bit counter 17 is 00, reading from the first row or first column of the storage section 11 is possible, and furthermore, the mode signal MODE
If the mode signal MODE is 1, the first row is selected, and if the mode signal MODE is 0, the first column is selected, and data is read from the output terminals OUT, .about.0IIT. In other words, the same selections as in the table above are made.

To summarize the above operations, first, if the first row of the storage section 11 is selected as shown in FIG. be exposed. At this time, reading is also performed, but since no valid data is stored in the storage unit 11 at first, it is ignored. 10 clock signals CLOCK
When the writing of the row data is completed, the 2-bit counter 17
The output becomes 01, and the data of the second row is written as shown in FIG. 2(b). In this way, when writing of data up to the fourth row is completed, the mode signal MODE is switched, the first column is selected as shown in FIG. 2(c), and reading is performed simultaneously with writing. In this way, when the writing up to the fourth column is completed as shown in FIG. 2(d), as shown in FIG. 2(e),
The first row is selected again. Here, the portion where data is written in the selected state in the row direction is indicated by diagonal lines. In this way, the data written in the row direction is read out in the column direction, so the matrix element output as (i, j) in the row converter 1 is converted into (i, j) in the column converter 2. It is read out as a matrix element of j, i), and a transposed matrix is obtained. Furthermore, since writing and reading are performed simultaneously, row converter 1 and column converter 2 operate simultaneously.
This allows for parallel processing and pipeline processing. In other words, high-speed processing is possible with the storage capacity of one block.

[Effects of the Invention] As described above, the present invention includes a storage unit having a capacity to store the calculation results for one block of the output of the row converter, and a storage unit that writes data to the storage unit each time one block is processed. an input control unit that alternately switches the direction between the row direction and the column direction; an output control unit that alternately switches the reading direction from the storage unit between the row direction and the column direction each time one block is processed; and an input control unit. The data written in either the row direction or the column direction is read out in the other direction via the output control section.
It is equipped with an overall control unit that controls writing from the other direction to the area where the reading has been completed via the input control unit, and the area that is vacant after the leaching by the column converter is completed. Since the calculation results of the row converter are sequentially written into the memory, storage space is not wasted, and if there is a storage capacity of about one block, pipeline processing becomes possible and high-speed operation can be expected. Furthermore, since the storage section is composed of shift registers, a serial bit slice configuration can be realized, which has the advantage of reducing the scale of hardware.

[Brief explanation of the drawing]

Fig. 1 is a circuit diagram showing an embodiment of the present invention, Fig. 2(a) -
3(e) is an explanatory diagram of the same operation as above, FIGS. 3(a) and 3(b) are explanatory diagrams of the operating principle of the matrix element transposition device according to the present invention, and FIG. 4 is a block diagram showing a conventional example. 1...Storage unit, 2...Address counter, 3, 4.
...Multiplexer, 5...Input decoder, 11...
・Storage unit, 11+t to 1144...shift register,
12... Input control section, 13... Output control section, 14.
...Shift signal generation section, 15...Overall control section, 21.
... Row converter, 22... Column converter. Agent Patent Attorney Ishi 1) Chief 7 Figure 2 (a) Figure 2 (e) Figure 2 (C) Figure 3 (a) (b)

Claims (1)

[Claims] (1) A matrix operator that performs two-dimensional orthogonal transformation on a block of data expressed in a matrix is configured together with a row transformer and a column transformer, and is inserted between the row transformer and column transformer to perform row transformation. In a matrix element transposition device that creates a transposed matrix from the calculation results of a row converter, a memory consisting of a plurality of shift registers each storing each matrix element and having a capacity capable of storing the calculation results of one block of the output of a row converter. an input control unit that alternately switches the write direction to the storage unit between the row direction and the column direction each time one block is processed; and an input control unit that switches the read direction from the storage unit in the row direction every time one block is processed. Data written in either the row direction or the column direction via the input control section is read in the other direction via the output control section. With,
1. A matrix element transposition device comprising: an overall control section that controls writing from the other direction to an area where reading has been completed via an input control section.