JPH0226476A - 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 an action at high speed by writing the operating result of a row converter in the vacant area in which reading by a colum converter is finished in order. CONSTITUTION:A storing part to have a capacity which can store the operating result of the one block portion of the output of a row converter 21, an input control part to switch a writing direction to the storing part 1 to a row direction and a column direction alternately every time when the one block portion is processed, an output control part to switch a reading direction from the storing part 1 to the row direction and the column direction alternately every time when the one block portion is processed and a whole control part to read data written either in the row direction or in the column direction through the input control part through the output control part in the other direction and to control to execute writing in an area in which reading is finished through the input control part from the other direction are provided. Then, the operating result of the row converter 21 is written in the vacant area in which the reading by a column converter 22 is finished in order. Thus, the uselessness of use of the storing area is eliminated, pipe-line processing is attained, and a high speed action can be executed.

Description

DETAILED DESCRIPTION OF THE INVENTION [Industrial Application Fields] The present invention is 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., it has been known to express the data in a matrix and perform orthogonal transformation on it. Examples of orthogonal transforms used include Agemar 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), the transform coefficient vector X = the result of performing one-dimensional orthogonal transformation on the column vector x = (×.l (n: 1, 2...-7N)) using this matrix Φ (X
, ) (n·1,2.−·−N) can be expressed by the following formula.

X = Φ Dimensional orthogonal transformation is a two-dimensional extension of formula (■), in which the block is a matrix X = (Xm n ) ('1, 2. = -, M,
n□1.2.・−・=, N), the orthogonal matrix Φ−(Φ,, + (,・1,2...−1 units) and city=(Ma1゜)(n;1,2 By using the following equation, the transformation coefficient matrix X-fX,
. ).

X=ΦX city...■ ■If we consider the formula, the calculation of Xψ can be regarded as repeating one-dimensional orthogonal transformation M times for each row of the matrix X, and the calculation of ΦX is as follows.

It can be considered that one-dimensional orthogonal transformation is repeated N times for each column of the matrix X.

In this way, in the two-dimensional orthogonal transformation, the first stage is a one-dimensional orthogonal transformation for each row, and the second stage is a one-dimensional orthogonal transformation for each column.
Since dimensional orthogonal transformation is performed (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 for 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. A matrix element transposition device generally called a transport memory is considered as a means for creating such a transposed matrix.

Conventionally available transport memories have a storage capacity of one block, and as shown in Figure 5, they temporarily store the matrix obtained by the row converter and convert the stored matrix from the column direction. By reading, the positions of the rows and columns are swapped, and successive output is performed as the inversion 1 matrix of the written matrix.

According to this configuration, the data cannot be continuously output to the column converter until all the data for one block has been collected, so the row converter and column converter cannot operate 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 6,
A configuration that can have a storage capacity of two blocks is conceivable (
U.S. Pat. No. 4,302,775, U.S. Pat. No. 4,39
4,774), in this configuration, two memories RAM, each having a storage capacity of one block, are used.
2, and are alternately switched by multiplexers MPX, . Each memory RAM
l, RAM 2 has an input terminal IN and an output terminal 0 (
IT, address terminal AI) [In addition to 1, write control terminal -
R and a continuous control terminal R0.

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 QIIT. A write signal WRITE is input to the write control terminal ridge via the multiplexer MPX+, and a leaching signal R is input to the read control terminal RD via the multiplexer MPX2.
EAD is input. Furthermore, each memory RAM1. R.A.
The address terminal ^[10 of M2 is connected to a row address generation circuit HADD and a column address generation circuit VADD via multiplexers MPX3 and MPX4, respectively.
are connected. Each multiplexer M P
PX4 is switched by the select signal SEL, and when the write signal ITE is input to one memory RAM + (RAM z ), the other memory RAM
A read signal READ is input to 2 (RAM l ),
Memory RA to which write signal 1IIRITE is input
Row address generation circuit HA in M + (RAM2)
The column address generation circuit VADD is connected to the memory RAM 2 (RAM,) to which DD is connected and the read signal READ is input.

As described above, data is written to each memory RAMI and RAM2 in the row direction, and read from the column direction. Also, since writing and reading are performed simultaneously to different memories RAMI and RAM2, the row converter and column converter can be operated in parallel at the same time, and if the block is a square matrix, the row converter and column converter If the converters and converters have the same operating speed, there is no idle time and processing can be performed efficiently.

[Problem to be solved by the invention] With the above configuration, the processing time is shortened, but the memory is
The number of blocks is required, and the number of multiplexers required is proportional to the number of data and address bits.
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. 5, the present invention has the advantage that when the row converter writes the result, the area where data will be written from now on becomes an empty area, and when the column converter reads the result, the area becomes a free area. This is done by focusing on the fact that the area where data reading has already been completed becomes a free 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 has finished. , storage space is not wasted, pipeline processing becomes possible, and high-speed operation can be expected.

[Example 1] In this example, the case where the block size to be processed is 8x8 is illustrated, but there is no restriction on the block size. Also, if the block is not a square matrix, the row A square matrix having the order of the larger value of the number and the number of columns has a storage capacity. 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 have the ability to operate on 10-bit data, and as shown in Figure 1, the output data of the row converter is sent through six 10-bit parallel D flip-flops.
A storage section configured using four Each D flip-flop has an address set individually, and since there are 64, the address is specified by 6 bits. For address specification, the output of address counter 2, which is a binary up counter, is first divided into upper 3 bits and lower 3 bits, and each is sent to multiplexer 3.
．． 4, and then the upper 3 bits and lower 3 bits of the address are given to the storage unit 1 via the input decoder 5. Here, a clock signal CLOCK is input to the storage section 1 and the address counter 2, and the clock signal CLOCK is a system clock common to each D flip-flop in the storage section 1. Furthermore, the input data is also synchronized with the clock signal CLOCK.

Each multiplexer 3.4 is configured to select one of the inputs according to the mode signal MODE, and when the upper 3 bits are input to one multiplexer 3 (4), the other multiplexer 4 (3 ) is set so that the lower 3 bits are input. therefore,
When the mode signal MODE is switched, the upper 3 addresses
The bit and the lower three bits are exchanged. That is, if we divide the address of storage unit 1 into the upper 3 bits and lower 3 bits, the address of storage unit 1 becomes (i
, j). That is, the address (
If we swap the upper 3 bits and lower 3 bits of j), we get
The address can be changed to (j, i). In other words,
When considered as a matrix representation, the state in which the upper 3 bits and lower 3 bits of the address are swapped becomes a transposed matrix for the original matrix.

The operation will be explained below. Initially, if the mode signal MODE is set so as not to interchange the upper 3 bits and lower 3 bits of the output of address counter 2, the output of the row converter will be as shown in Figures 2(a) and 2(b). As shown in FIG. is expressed as (i, j) using the upper and lower 3 bits, first increase j by 1, and when j reaches the maximum value (7 in this example), j
This is the order in which i is returned to its minimum value (0 in this embodiment) and i is increased by one. Further, reading is performed from the same address slightly prior to writing. In the initial state, since the data to be read is not stored in the storage unit 1, the read output data is ignored.

When data has been written to all the address spaces of the storage unit 1 in this way, the mode signal MODE is activated so that the upper 3 bits and the lower 3 bits of the output of the address counter 2 are exchanged.
to occur. As a result, the order of addressing is switched in the row direction as shown in FIGS. 2(e) and 2(d).

Here, in the row direction, when the address of the storage unit 1 is expressed as (i, j) using the upper and lower 3 bits, first, i is increased by 1, and when i reaches the maximum value, i This is the order in which j is returned to its minimum value and j is increased by one. In this way, (1,1>(1,2)(1,3)...
・For the data written in the order (1, 1
)<2.1)(3,1>...), which is equivalent to obtaining the transposed matrix for the original matrix.Of course, reading is performed at the same time as writing. The address space of storage unit 1 is filled with data when reading in the row direction is completed.The upper 3 bits and lower 3 bits of the address are then swapped again. , reads and writes in the column direction.

By repeating the above operations, it is possible to perform two-dimensional orthogonal transformation while simultaneously operating the row transformer and column transformer, and while the storage unit 1 has the storage capacity of one block, row transform and column transform can be performed. These can be processed in parallel and pipelined, making high-speed processing possible.

[Example 2] This example is configured to be adapted to a block of size 4 x 4. In Example 1, the data was 10 bit parallel, but in this example, the data was 10 bit parallel. It's a 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 is composed of 16 10-bit shift registers lined up as shown in FIG. 3, and each shift register 11.1 (i, j: 1.2, 3.4) is be done. An input control unit 12 is provided before and after the storage unit 11, respectively.
and an output control section 13, and each shift register 111J receives one shift signal input from the outside.
Data is shifted in synchronization with the clock signal CLOCK during the period when the clock signal CLOCK is set. This shift signal is generated by the overall control section 14. Overall control section 14
is the clock signal CLOC based on the output of the counter section 15.
The counter section 15 includes a frequency divider 16 that divides the tarlock signal CLOCK by 10, and a frequency divider 16.
A 2-bit counter 17 counts the output of the 2-bit counter 17.

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 input to the shift register 11□, (i・1, 2, 3°4) Similarly, the other input terminals IN2 to IN are set to be input to one of the shift registers 11.2 to 11□ in each corresponding column. When the mode signal MODE becomes O, data to each input terminal IN, .about.IN, is transferred to one of the shift registers 11.about.111.about.in of each corresponding row. (j・1,
2, 3.4). In other words, when the mode signal MODE is 1, if you specify a row, the storage unit 1
When the mode signal MODE is 0, data for one column in the column direction of the storage section 11 can be stored by specifying a column. .

The row assignment when the mode signal MODE is 1 and the column assignment when the mode signal MODE is O are performed by the overall control section 14. That is, one of both output ends Q of the 2-bit counter 17. , Ql can take four states,
If the mode signal MODE is 1 when the output value is 00, the shift signal is input to the shift register IIIJ in the first row, so data is eventually written to the first row of the storage section 11. become. Here, each shift register 11. ．． have 10 bits each, so
The shift signal remains in the same state while the clock signal CLOC is issued ten times. This state is the clock signal CL.
This is realized by a frequency divider 16 that divides OCK into 1/10. The output of 2-bit counter 17 is the same.

When the mode signal MODE is 0, the overall control unit 14 controls the first column shift register 118 . Since this is specified, when combined with the settings of the input control unit 12, data will be written to the shift registers 11, 1 in the first column. Mode signal MODE and 2-bit counter 17
The output Q. , Ql, the storage unit 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 A, B, C, and D from the top in FIG. 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 the output terminals 0tlT, ~01lT
, data is read from. 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. It will be done. At this time, the data is read out, but since no valid data is stored in the storage unit 11 at first, it is ignored. When the writing of the first row data is completed by the 10 clock signals CLOCK, the output of the 2-bit counter 17 becomes 01, and the writing of the second row data is performed as shown in FIG. 4(b). . In this way, when writing of data up to the fourth row is completed, the mode signal MODE is switched,
As shown in FIG. 4(c), the first column is selected and reading is performed simultaneously with writing. In this way, the fourth
When writing up to the column is completed, the first row is selected again as shown in FIG. 4(e). 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. j, i), and a transposed matrix is obtained.6 Also, since writing and reading are performed at the same time, row converter 1 and column converter 2 They operate at the same time, allowing parallel processing and pipelining.

In other words, high-speed processing is possible with a storage capacity of 11,077 minutes.

[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.
The system is equipped with an overall control section that controls writing from the other direction to the area where reading has been completed via the input control section, and writes to the empty area after reading by the column converter has been completed. Since the calculation results of the row converter are written sequentially, the storage area is not wasted, and if the storage capacity is about one block, pipeline processing becomes possible and high-speed operation can be expected.

[Brief explanation of the drawing]

FIG. 1 is a block diagram showing Embodiment 1 of the present invention, and FIG. 2 (
a) to (e) are explanatory diagrams of the same operation as above, FIG. a) and (b) are diagrams explaining the operating principle of the matrix element transposition device according to the present invention, and FIG. 6 is a block diagram showing a conventional example. 1...Storage unit, 2...Address counter, 3.4.
...Multiplexer, 5...Input decoder, 11...
-Storage unit, 12...Input control unit, 13...Output control unit, 14...Shift signal generation unit, 15...Overall control unit, 21...Row converter, 22...Column converter. Agent Patent Attorney Ishi 1) Chief 7 Fig. 1 1...Storage unit 2...Address counter 3.11...Multiplexer 5...Input decoder Fig. 2 (a) (b) Fig. 2 Figure 2 (d) Figure 4 (a) Figure 4 (C) Figure 5 CG) (b) ■ To /y'J control figure 4 (e) Figure 6 CLOC

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, there is a storage unit that has a capacity to store the calculation results of one block of the output of the row converter, and a storage unit that stores the calculation results of one block of the output of the row converter. an input control unit that alternately switches the write direction of the storage unit between the row direction and the column direction; and an output control unit that alternately switches the read direction from the storage unit between the row direction and the column direction each time one block is processed. 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. A matrix element transposition device comprising: an overall control section that controls writing from the other direction.