JPH03214269A - Rotation mechanism for two-dimensional array data - Google Patents

Abstract

PURPOSE:To suppress the increase of hardware quantity when the number of data which receive accesses at one time from the RAM unit arrays become larger by providing the storage units arranged in a matrix form and a means which replaces the two-dimensional array data for each row and rotates these array data by an odd multiple of 90 deg.. CONSTITUTION:The address qualifiers 5b and 5c are set in the qualification mode and D is added to the input of each address qualifier. Then the data are read out of the RAM unit arrays 20-28 and sent to a 90 deg.-rotator 1. As the inputs D are added as they are to the RAM units 20-22 as addresses, an access is given to an address D. However the inputs D are qualified for the RAM units 23-28 since the addresses are supplied to the units 23-28 via the qualifiers 5b and 5c. Then D+1 and D+2 are added to the units 23-28 as addresses and the accesses are given to the addresses D+1 and D+2. Thus the increase of hardware is suppressed when the number of access data on the RAM unit arrays is increased.

Description

[Detailed Description of the Invention] [Industrial Application Field] The present invention is applicable to memory access data count (data word length is 1).
Image processing equipment whose performance can be improved by increasing the number of bits (equivalent to data width). 90% of compact and high-speed two-dimensional array data is used in turn recognition devices, etc.
It is related to the technology that realizes the degree rotation mechanism. [Conventional technology] Two-dimensional array data stored in memory can be processed at high speed.
A known method for rotating by an integer multiple of 0 degrees is to use a 90 degree rotator that converts between rows and columns of sub-two-dimensional array data whose length and width are equal to the number of data K accessed once from memory. (For example, see FIA Application No. 59-170863 [Image rotation processing method] for the case of handling two-dimensional array data (bit plane) in which the word length of each data is 1 bit). FIG. 2 shows a schematic block diagram of an example of a bit plane rotation mechanism using this method. Here, IFiWx
90 degree rotator for W sub-bitplane. 200 is a random access memory (RA) with an access width of 1 bit.
M) RAM unit array consisting of W units of unit 2 (
(so-called W-bit width memory), 3 is a control unit. 4 is a data bus with a width of W bits. Cut out the rotated pit plane in memory with WxW sub pit delane,
By first reading the 90 degree rotator in rows, and then pasting the rotation results in column units to an appropriate address, you can see the pits after rotation! A lane is formed in memory.

FIG. 3 illustrates this procedure when W is 3. (i) in the figure is a rotated bit de lane,
In the form shown on the left side of figure (b). RAM unit array 2
Medium K is stored. The arrow pointing from the storage image frame of this pit plane to the 90 degree rotator is . This figure shows how data read out in K word units of 3-pit length from the RAM unit array is sequentially input to the 90-degree rotator as rows of 3×3 sub-pit planes. At this time, by sequentially applying appropriate addresses, 3×3 sub pit lanes are formed in the 90 degree rotator as shown in the figure. On the other hand, the arrow pointing from the 90 degree rotator to the memory storage image on the right side is . The figure shows how the 3×3 sub-bitplane columns in the 90 degree rotator are sequentially extracted and re-stored in the RAM unit array as 3-pit long words. This re-stored array data represents the pit plane of (cl) in the figure. This is exactly the rotated bit plane rotated 90 degrees counterclockwise. By the way, in this conventional example, The time required for 90 degree rotation per sub-bit deletion is as follows: 1 word access from the RAM unit array is performed in 1 unit time, and input/output between the RAM unit array and the 90 degree rotator is performed in parallel with access to the RAM unit array. If it can be done, it will take 2W unit time.

[Problem to be solved by the invention] In this method, the number of data accessed at one time from the RAM unit array and the number of input/output data of the rotator are the same, and both of them must be thickened. No speed improvement can be expected. In this case, the number of access data from the RAM unit array can be expanded relatively easily by arranging the memories IJIC in parallel. but. The number of input/output data for a rotator increases in proportion to the square of the number of input/output data, and the amount of hardware becomes a bottleneck, making it difficult to expand easily.

An object of the present invention is to provide a high-speed two-dimensional array data rotation mechanism that does not increase the amount of hardware even if the number of data accessed at one time from a RAM unit array is expanded.

]Means and methods to solve I! ! ] The present invention aims to achieve the above object. A memory unit arranged in a matrix that serves as a means for accessing the same address as a whole and a means for accessing different addresses for each row.
This method is characterized by having means for replacing two-dimensional array data row by row, and means for rotating the two-dimensional array data by an odd number of times of 90 degrees.

The main feature of the present invention is that it accesses data from a storage unit array of N (N is an integer of 2 or more) rows (or N columns) of a sub-two-dimensional data array to be rotated. . Compared to the conventional method, which accesses only one row (or one column) of data at a time, this method allows access to the same number of data from the storage unit array. Since the row size of the sub-two-dimensional data array to be rotated, that is, the size of one side of the 90 degree rotator, can be reduced to 1×, the amount of hardware for the 90f rotator can be greatly reduced. Here, the sub-2D array data before rotation and the sub-2D array data after rotation are. Both are stored in one row (or column) of storage units, which may be considered as a two-dimensional storage unit array. Therefore, these N rows (or N columns) need to be efficiently accessible from the state stored in the storage unit belonging to one row (or column) of the storage unit array. For this purpose, is it possible to distribute N rows of sub-two-dimensional array data stored in one row of the storage unit array to the entire storage unit array, or vice versa? An advantage of the structure of the present invention is that it includes a means for mutually replacing array data accessed for each row of a storage unit array for the purpose of performing a specific purpose, and a means for accessing each row of the storage unit array from a different address. It is a characteristic. In addition, the rabbit N
Row (N column) Fi. A match may belong to sub-two-dimensional array data of one rotation target, and a match may belong to sub-two-dimensional array data of a plurality of rotation targets. Hereinafter, an embodiment will be described in order, starting with the case where all rows of one rotation target are accessed at once (when N=W).

[Example Fig. 1 shows the tJ. 1 is a diagram showing a block configuration of an embodiment of 1, in which 1 is a 90 degree rotator, 20 to z s 12
RAM unit, data replacement between soFi rows? A switching network for this purpose. 5b5cti address modifier, 6 is an address signal input terminal, 7 is a control input terminal for switching the address modifier between modification mode and non-modification mode, 8-digit 90 degree rotator J, switching network SO. This is a path connecting RAM units 20 to 28.

The address modifiers 5b and 5e are means for generating the same address as a whole and a different address for each line in the scope of the claims. It is output as is, and the modification mode modifies the input signal as follows and outputs it.

5b address modifier: our =A+1-{3[A+
1/3]-3[A/3]}...<1) Address modifier of 5c: OUT =A+2-(3"A
+2/3 Co3 [&3])...{2) Here. OUT is an output address signal value, an input address signal value, and a Gaussian symbol. Figure 4 shows
The configuration of a 90-degree rotator is shown, with 10 basic rotating elements. 1) t'i master rape type D-FF.
13 is a selector. FIG. 5 is a configuration diagram of the switching network 30, where No. 3 is a rotatable shifter, input/output terminals connected to 32 paths 8, and the primary terminal is a RAM unit array A of 20 to 28 as shown in FIG. What are the steps for rotating the two-dimensional array data from OO to 88 stored at address A+1 according to this embodiment? I'll find out later.

◎Stenode 1 Address modifiers 5b and 5c are set to non-modified mode, and 2
(I-211 RAM unit array A+1.A+4.
A+7iI data switching network 30
Start reading. Rotate and shift the distance from the back of the page to the front by [distance] in line units, and change the result to D+l. D+
4 t Store in address D+7 in order. 20
The data at addresses A+2, A+5, and A+8 of the ~28 RAM unit arrays are also read out to the switching network 30, rotated and shifted by K distance 2 in the same direction row by row, and the results are stored at addresses D+2, D+5, and D+8. Do things in order. A, A+3, A
Address +6 is directly transferred to addresses D, D+3, and D+6. the result. At address D-D+8 in the RAM unit array from 20 to 28. Two-dimensional array data shown in FIG. 7 is obtained.

◎Stede 2 Attress modifier 5b. Set 5c to modification mode, 2
Add D to the input of the address modifier from 0 to 28 to obtain 20
The data was read from the ~28 RAM unit array into the 90 degree rotator l, . For RAM units 20, 21.22K, input D is added as an address as is, so D
address is accessed, but 23t24 of the RAM unit
．． 25, 26, 27, and 213 because addresses are supplied via address modifiers 5b and 5c.
Input D is modified. D+1 and D+2 are respectively used as addresses, and addresses D+1 and D+2 are accessed. As a result, the sub-two-dimensional arrays originally stored in 20 to 28 RAM unit arrays are expanded into one-dimensional arrays and read out in a single access. Figure 8 f
A) is stored in the 90 degree rotator 1 as a sub-two-dimensional array. In addition. Storing in the 90 degree rotator J can be done by setting the selector 13 in FIG. 4 to select the input from the RAM units 20 to 28. Step 3 This sub-two-dimensional array Selector 13 of
By selecting the input from the other rotating element on the left side, the rotation element is rotated 90 degrees clockwise as shown in FIG. 8(b).

◎Step 4 This 90-degree rotated sub-two-dimensional array data is transferred to the switching network 30 via the bus 8, rotated and shifted by a distance of 1 from the back of the page to the front in line units, and the address modifier 5b. Set 5c as modification mode and input address tB+2, and store as shown in FIG. 9 (al).

◎Step 5 Step 2ff: Repeat with input address D+3.

As a result, the sub-two-dimensional array shown in FIG. 10 (Todoroki) is read out from the 90-degree rotator 7K.

◎Step 6 Perform the same process as Step 3, and rotate as shown in Figure 1O (bl).

◎Step 7 This sub-two-dimensional array data rotated by 90 degrees is passed through pass 8, and the address modifiers 5b+5c are set to modification mode and the input address is B.
is stored in the RAM unit array.

◎Step 8 Repeat step 2 with the person's address as D+6. As a result, the sub-two-dimensional array shown in FIG. 11(1) is read out from the 90-degree rotator 7K.

◎Step 9 Perform the same steps as step 3 and rotate as shown in Figure 11 (bl).

◎Step 10 This 90-degree rotated sub-two-dimensional array data is transferred to the switching network 30 via path 8, rotated and shifted by a distance of 1 row by row in the opposite direction to step 4, and address modifier sb. 5c as the modified moat 9 and the input address as B+1, it is stored as shown in FIG. 9, 1cl.

◎Switching network 30 as a result of Figure 9 (c) of Stede I
Rotate shift in the column direction row by row using , and store the result from address C to C+2. The results are shown in Figure 9 (
dt. This is the form in which the left three columns of the original two-dimensional array data are rotated 90 degrees clockwise. By repeating steps +'2 to 11 up to this point, 2 from 00 to 88
The entire dimensional array data can be rotated 90 degrees clockwise. On this occasion. As the column to be rotated and the storage location of the result change. In this example, W
The rotation time per sub-bit plane of xW is 2
The time required to access the rotator 1 or the switching network 30 from the sub-unit arrangement of 0 to 28 is 1.
9 in the 90 degree rotator 1 for 1 unit time, an arbitrary amount of rotation shift in the switching network 30
0 degree rotation for 1 unit time, switching network 30
・Rotator J open transfer location! If time is 1 unit time,
3 credit hours in step 1, step f2, 5. 8
Step 3.6.9 is 1 unit time, Steps 4 and 7.10 are 3 unit hours, and Sten 7'1 is 3 unit hours, making a total of 11 unit hours. Although this required time cannot be said to be short, it can be solved by introducing a pipeline-like processing mechanism.

FIG. 30 shows a second embodiment of the present invention, which is one of its implementation examples. Here, 1' is a bidirectional 90-degree rotator that can set the direction of input and output either upward or downward. 3
Company 0 bidirectional switching network, 90-98 is another RAM unit. 99 is another address signal input terminal J8#-1, a path connecting the RAM units 20 to 28 and the opening of the switching network 30', 88
' is a path connecting the switching network sol and the 90-degree rotator 1'. 88 bamboo 90 degree rotator 1' and RAM
This is a path connecting units 90-98. The operation of this embodiment is basically the same as the first embodiment. The difference is A.
~Assign addresses A+8 and C-C+S to RAM unit arrays 90 to 98. The point is that each rotation process is performed during the round trip between 20-28 and 90-98 of the RAM Uninote MP row. Rotation processing in the 90-degree rotator 1', switching network 30Qlc, rotation process}. RAM units 20-28 and 90-9
If any combination of reading and writing in 8 can be executed in 1 unit time. Alternatively, even if this is not possible, each process can be assigned to one stage of the pie line.
If the processing is carried out in equivalent time of one noodle, the required time will be greatly reduced. ′f, that is, step 1
and 4. From RAM unit arrays 90 to 98,
Steps 2, 3 and 1zl'iR are processed in 1 unit time as processing toward the RAM unit arrays 20 to 28.
From AM unit arrays 20-28. Each of the processes directed to the RAM unit arrays 90 to 98 can be executed in one unit time. Therefore, the total time required is 4 unit hours.

W. FIG. 12 is a block configuration diagram of the third embodiment of the present invention, in which 20 to Z8 are RAM units, 40 to 48 are shift registers, 6 address signal input terminals, 7' are shift register control signal input terminals, 9 is a two-dimensional shift unit control signal input terminal, 10' is a two-dimensional shift element,
8' is a shift register 40 to i8. This bus connects the RA111 units 20 to 28 and the two-dimensional shift element io'. 2D shift element 1 0' 3 x 3
The entire arrangement and connections between adjacent elements constitute a two-dimensional shift unit that doubles as a switching network and a 90-degree rotator. Figure 13 (ml, (b)
, (cl is 40-42.43-45.4, respectively.
This is a block diagram showing the internal configuration of shift registers 6 to 48, 5J, 52 are selectors, 53, 54, 55
is a master rape type D-FF. 56 is a data input terminal, and 57 is a data output terminal. D- The output of FF55 is fed back to selector 51, and 53~
It is possible to rotate 7 tones of data (rotatable shift register). In addition. The difference between the shift registers (Todoroki 1, (bl, and (cl) in FIG. 13 is that the input paths to the selector 52 are different. This allows output from addresses that are shifted by one stage in row units. Therefore, in this embodiment, the shift register arrangement is a storage unit arrangement having means for both accessing the same address as a whole and accessing different addresses for each row as defined in the claims. Figure 14 shows the two-dimensional shift element JO'
1), Jx, 11' is a master rape type D-FF. 12 is the tri-state switch, 13', 13'' is the input selector, and 5.16.
Reference numerals 17 and 18 designate input/output terminals for connecting adjacent elements on the depth side, front side, right side, and left side, respectively, with respect to the drawing surface, and 19 represents an input/output terminal for the bus 8/.

Next, as in the case of the first embodiment, as shown in FIG. The procedure for rotating 90 degrees will be explained step by step.

◎Step 1 Address A+1, A+4 of RAM unit array 20-28
Read the data at address A+7 to the two-dimensional shift unit (set to select the input from selector 13' and pass8' of two-dimensional shift element 7 (7/), and use the column direction shift function. , rotate by 1 line by line from the back of the page to the front, and return the result to the original address in order.For addresses A+2, A+5, and A+8 of the RAM unit array of 20 to 28,
Read out to the dimension shift unit and read 2 (
1 in the opposite direction) and perform the rotation shift in the order without returning the result to the original address. The result is as shown in FIG. 7 of the first embodiment. However, in this case, the address remains A instead of D. Here, for the shift in the row direction in the two-dimensional shift unit, the two-dimensional shift element J()/ is set so that terminal 15 is input, terminal 17 is output K, and selector 13' is set to select the input from terminal 15. This is achieved by doing.

◎Step 2 Set the selectors 5 of shift registers 40 to 48 to select the input from path 8', and sequentially read the input from address A to A+2 of the RAM unit array of 20 to 28 to the shift register array. As a result, each shift register 4
The arrangement of the contents of D-FFs 53 to 55 of 0 to 48 is as shown in FIG.

◎Step f3 [Substep J] The input selector 5 of the shift register unit is set to select the input from the left side, and the output selector 52 is set to select the input from the right side, and while rotating and shifting within the shift registers 40 to 48, two-dimensional Read it to the shift unit.

This reading can be performed by setting the selector 13' so that each two-dimensional shift element lO' of the two-dimensional shift unit takes in the input signal from the path 8'. As a result, the data array of FIG. 8 (al) is first entered in the array of D-FFM1 of the two-dimensional shift unit.

[Substead 2] Is this data array a column-wise shift unit? The shift data is shifted row by row from the front to the back, and the shift data is transferred one by one to the shift transfer system in the row direction, and the data is shifted from right to left column by column. Rotation result (Figure 8(b))
is obtained in the array of D-FFII' of the shift transfer unit. This rotation result is stored in address C of RAM units 20-28. Here, the shift in the row direction from right to left in the two-dimensional shift unit is performed by inputting the input/output terminal 16 of the two-dimensional shift element 10', inputting the input/output terminal l8, and connecting the selector IJ'' from the terminal J6. The rice can be actually harvested by selecting the input of .In this case, a path is connected to the rightmost two-dimensional shift element JO' so that the two column-direction shift data that are being performed at the same time are sequentially input. By repeating simultaneous shift transfer in the column and row directions three times, a 90 degree clockwise rotation can be achieved.

[Substep y'3] The same processing as in substep 1 is performed. In this case, D-
The data read out to the FFII is shifted in the column direction as shown in FIG. 16(a). In this case, by shifting once in the opposite direction, a regular sub-two-dimensional array as shown in FIG. 16fb) is obtained.

[Substep 4] The same processing as Substep 2 is performed. However, the storage location is C+1.

[Substep 5] Perform the same processing as substep '7''3.

[Substep f6] The same process as substep 2 is performed. However, the storage location is C+2.

As described above, the data array from addresses A to A+2 in FIG. 6 is converted to addresses from C to C+2 in FIG. 17.

◎Step 4 Perform the same process as step 2. However, the read addresses are A+3 to A+5.

◎Step 5 Performs the same processing as Step 3. However, the write addresses are C+3 to C+5. The results will be as shown at addresses C+3 to C+5 in FIG.

◎Step 6 Perform the same process as step +'2. However, the read addresses are A+6 to A+8.

◎Step 7 Perform the same processing as Step 3. However, the omitted addresses are assumed to be addresses C+6 to C+8. The results will be as shown at addresses C+6 to C+8 in FIG.

ft5) Step 8 Transfer the data at addresses C-C+2 of the RAM unit array 20 to 28 to the two-dimensional shift unit. Using the shift function in the column direction, rotate the page by 2 (or 1 in the opposite direction) row by row from the back of the page to the front, and then return the resulting address to the original address. RA of 20-28
Addresses C+3 to C+5 of the M unit array are also read out to the two-dimensional shift unit, rotated and shifted by 1 in the same direction row by row, and returned to the original address which is the result of two operations. The results are as shown in FIG.

◎Step 9 Set selector 5 of the shift register to select the input from path 8', and sequentially read the data from addresses C+5, C+3, and C of the RAM unit array 20 to 28 to the shift register array 40 to 48. . The results are as shown in No. 19.

(Q) Step 10 Is the input selector 51 of the shift register unit the left input? ．． The output selector 52 is set to select the input from the right side, and the data is read out to the two-dimensional shift unit while being rotated in the shift registers 40 to 48. As a result, the data array of FIG. 20(a)*(ble(c)) is sequentially read out to the D-FFII array of the two-dimensional 7h unit.

Regarding Figure 20 (1), leave it as is i RAM unit 2
The B addresses from 0 to 28 in Figure 20 (b) and (c) are shifted. Using the column direction shift function of the 2D shift unit. After restoring it to its normal form, store it at address 13+l, B+2. This results in Figure 9 (dl), where the left three columns of Figure 6 are rotated 90 degrees clockwise.
By repeating this process for data at addresses +5 and C+6 to C+8, 90 degree rotation data for the entire two-dimensional array data in FIG. 6 can be obtained.

In the second and third embodiments of the present invention, the two-dimensional array data stored in the RAM units 20 to 28 are
When expanding into dimensional array data, it is effective to modify addresses like expressions 1 and 2. Rotate shifters are used for line-by-line replacement. However, the expansion of sub-two-dimensional array data into one-dimensional array data is... Ascension that constitutes a two-dimensional address access memo 1) [Reference Nimotooka et al.
A rapid thinking processing system with two-dimensional memory” IEICE Technical Report E C
76-80], permutation of nine lines, which is different from kone,
This is possible by modifying the address.

FIG. 21 is a block diagram of the fourth embodiment of the present invention, in which l 0 0 , J 0 0', 1 0 0N
is a two-dimensional shift unit that doubles as a storage unit and a 90-degree rotator, 6 is an address signal input terminal, and 20 to 28 are RAs.
M unit, 30#'llt switching network. sid RAM units 20-28. Switching network 30. Two-dimensional shift unit 100, 10
A bus connecting between 0' and 1 0 0'. 60-68 is 2
This is the data input/output terminal of the dimension shift unit.

(al T (bly (e)) in FIG. 22 are two-dimensional shift units J 00 , J 00', 1
00", 60 to 68 are data input/output terminals, 70 is an input selector, 71 is an output selector, 110 to 18, 120 to 128, and 130 to 138 are two-dimensional shift elements. This is a column unit that constitutes a two-dimensional shift element. Fig. 23 is a block diagram of the two-dimensional shift element.
IJ' is a master slave type D-FF. Reference numeral 72 denotes an input selector, 75 an output terminal for upward direction on the paper, 76Fi an input terminal for input from the right side of the paper, 77 an input terminal for input from the lower side of the paper, and 78 an output terminal for the left direction of the paper.

Next, according to this embodiment, 2 in the RAM unit array in FIG.
A case in which dimensional array data is rotated 90 degrees clockwise will be explained with reference to the steps.

◎Stead I Read from address A to address A+2 in order, and shift to two-dimensional shift unit 200, 100', 200''
are stored in each D-FFII as shown in FIG.

Here, the contents of the squares represent the contents of D-FF7J in the corresponding two-dimensional shift element.

◎ Steady 2 Set the selector 72 to D on each two-dimensional shift element of the two-dimensional shift unit 100, 100', 100''.
- By selecting the output of FFM 1, move the contents of D-FFIJ to D-FFMJ'.

◎Stede 3 2-dimensional shift unit 7 00, 1 00', J
The two-dimensional array data stored in the D-FF7J' array at 00'K. Rotate 90 degrees. D-FFI 1
Store it in an array. The storage result is shown in FIG. Here, the 90 degree rotation is performed by setting the input selector of each two-dimensional shift element to select the input from the right neighbor, and shifting the contents of D-FFII from right to left.
The selector 70 of each column unit 80 is set to select the input from the horizontal shift system, and the two-dimensional shift unit 100, J 0 0'. This is executed by repeating three times inputting the output data from the left end of 1 0 0' from the bottom to the top.

◎Stede 4 2-dimensional shift unit 1 0 0, J 0 0',
The contents of D-FFII of 1 0 0' are transferred to column unit 8.
Is the 0 selector 7 the top input? Select it, move it to the switching network 30, and move it to line D-
Move the contents of FF7J to D-FFJ'.

◎Step 3 Two-dimensional shift unit 7 0 0, 1 0 0',
At J 0 0', the two-dimensional array data stored in the array of D-FFJ7' is rotated by 90 degrees and
Store in the J7 array. The storage result is shown in FIG. Here, rotate 90 degrees Vi, change the input selector of each two-dimensional shift element to the input from the right neighbor? While the contents of D-FFJ 7 are shifted from right to left, the input from the selector vof horizontal shift system of each column unit 80 is selected. 2-dimensional shift unit} 100, 1 0 0', 1 0 0"
This is executed by repeating the input data from the bottom to the top three times, starting from the left end.

◎Step 4 Two-dimensional shift unit J 0 0, J 0 0',
The contents of D-FFI of 7 0 0# are transferred to column unit 8.
0 selector 7l to select the topmost input, and then temporarily move it to the switching network 30. Line by line, from the front to the back of the page. 1. After rotating by O, -1, the selector 70 of the column unit 80 is set to select the input from the external bus 8, and the two-dimensional shift unit loo, J 0 0'. J 0 0'
The result shown in FIG. 26 is obtained for the D-FFJ 1 sequence. Here, the sign of the angle represents the transfer in the opposite direction.

◎ Steady 5 In order to select the input from the two-dimensional shift element at the top stage, the selector 70 in the row unit 80 is set to select the input from the two-dimensional shift element at a different stage for each 90-degree rotator (in the block diagram). left input)? D-FF for each row unit 80.
While rotating and shifting the contents of I J from bottom to top. Two-dimensional array data in the D-FFJ array. C+2 of the 20-28 RAM unit array via path 8
, C, and C+1 addresses. The contents of the resulting 20-28 RAM unit array? It is shown in FIG.

Steps 1 to 5 above are arranged in 20 to 28 RAM units! The same process is performed for addresses A13 to A+5 and A+6 to A+8 of 1{. The difference is that the shift amount in units of rows by the switching network 30 in Stead 4 is -1.1.0 and 0. -1.1 and the storage destination in Stead5 is C+3~C+5 and C+6~ respectively.
It should be set to C+S address. As a result of these, 2
The result shown in FIG. 28 is obtained at address C-C+8 of the RAM unit array from 0 to 28.

◎Step 6 Two-dimensional shift unit J 00, lθ”+ 1 0 0
' Set the selector 70 of each column unit 80 to select the input from path 8. While performing a shift operation from bottom to top, C+ of RAM units 20 to 28
Read the contents of addresses 5, C+3, and C sequentially into the D-FFJ JO of each two-dimensional shift element. Second
Obtain the results shown in Figure 9. Here, the contents of each square are D-FF
1 represents the retained data of 1.

◎Step 7 Use the selector 7 in the column unit 80 to select from the two-dimensional shift element in the upper row of the selector 70ttil.
is set to select the input from the two-dimensional shift element of a different stage for each 90 degree rotator, and the contents of D-FFII are rotated from bottom to top for each column unit 8o. The two-dimensional array data in the array of D-FFJ J is output to path 8, passed through the switching network 30, and then transferred to the RAMs 20 to 28.
The domain is stored at address B t B + 2 * B + 1 of the unit array, and the same result as in Fig. 9 fd) is obtained. Here, the shift amount in the switching network 3θ is in the order of 0 and 2.1 from the front to the back of the page.

Processing similar to steps 6 and 7 is performed on C+1, C+4 . C+7 and C+
Perform this for addresses 2, c+5, and C+8. the result? Store at addresses B+3 to B+5 and B+6 to B+8, respectively (at this time, it is necessary to change the access m% of the address of the RAM unit array of 20 to 28 and the shift amount on the switch/gune notebook 3o appropriately. be.

), the two-dimensional array data in Figure 6 is rotated clockwise by 90
It can be obtained at address B − B + 8, which is the result of rotation by degrees.

Next, I will explain the effect K.

First, we evaluate the effect of reducing the hardware scale.

In the first, second and third embodiments of the present invention, when the number of access data in the RAM unit array is L, W is L. Comparing the size of the 90 degree rotator with the conventional method in which W becomes L itself, the side size is 1/VL, and the hardware scale is I
It becomes A. In the fourth embodiment of the present invention, approximately L 90-degree rotators with side size L are provided in parallel, so the hardware cost increases, but it is still compared to the conventional method. The hardware scale of the entire 90 degree rotator is 1/XTJM f+.

When L is small, the hardware reduction effect is small because it is offset by extra hardware such as address modification mechanism and shift register array, but when L is large, for example 64 or more, the present invention It can be seen that the effect of b is very large. In addition, in evaluating the hardware scale. The reason why the RAM unit array is excluded is that we believe that it can be used for other purposes. This applicability is the essential reason why the present invention can reduce the hardware scale. In addition, the relationship between W = and /τ can be made W = V if the access from the RAM unit array is performed in a time-division manner (number of divisions is 2N) and the size of the RAM unit array is equivalently increased. It is. Thereby, L and W can be appropriately selected according to the design conditions.

On the other hand, regarding the effect of speeding up, the time required for the conventional method is 2
W unit time, since the second embodiment of the present invention which adopts the configuration capable of processing in line-like manner has 4 unit time, in the Tohoku case where the size of the 90 degree rotator is the same, the most dog W /
A speed increase rate of about twice can be obtained. For example, W is 8 (L=
In the case of 64), the time required by the conventional method: 16 unit hours The time required by the second embodiment of the present invention: 4 car hours, 4 times faster speed, and 16 times the W (L= 256). Required time for conventional square wave = 32 hours Required time for 20th embodiment of the present invention = 8 times faster speed is achieved in 4 units of time 6 Note that the third and fourth embodiments As it is, the speed performance is inferior to that of the second embodiment, but by adopting a piedline processing configuration, the required time opening can be shortened to a value equivalent to that of the second embodiment.

By the way, Example 1 and implementation fl. 'The difference between the 3t and 4 is mainly in the configuration of the 90 degree rotator. The rotator of Example 1 is
Although it is excellent in performing 90-degree rotations at high speed, the connections between rotating elements are irregular and it is relatively difficult to make large-scale ones. on the other hand. The two-dimensional shift units for 90 degree rotation in Examples 2 and 3 have regular structures and are relatively easy to manufacture. Embodiment 4 can be said to have increased the number of 90 degree rotators in order to improve this rotatability.

As described above, each embodiment has its own characteristics, so when actually utilizing the present invention, performance requirements must be met. Design condition? It is necessary to take this into account and select the optimal configuration.

[Efficacy of invention! ] As explained above, the present invention provides a compact and relatively fast 90 degree rotation even if the number of access data in the RAM unit array (access data@8 if the data word length is 1 bit) is increased. Able to configure mechanisms. Therefore, the present invention provides a method for increasing the number of access data (access width) from a RAM unit array in order to improve the overall performance of a two-dimensional data processing device (for example, an image processing device W).
・It is extremely effective as a technology for shaping and speeding up.

[Brief explanation of drawings]

Fig. 1 is a block diagram of the first embodiment of the present invention; Fig. 2 is a block diagram of a conventional 90-degree U-turn mechanism for pit delane; FIG. 4 is a block diagram showing an example of a 90 degree rotator according to the present invention; FIG. 5 is a block diagram showing an example of a switching network according to the present invention; FIG. 6 is a block diagram showing an example of a switching network according to the present invention; Indicates -fl1 of the two-dimensional array data to be rotated stored in the RAM unit 11 related to
``F explanatory diagram, Figure 7 is a diagram of the two-dimensional array data generated by twisting the two-dimensional array data in Figure 6, Figure 8. Figure 10
Figure 11 (a) shows an example of the sub-two-dimensional array data of the rotation target read out to the 90-degree rotator according to the present invention + construction diagram, Figure 8, Figure 10, Figure 11. [bl
FIG. 9 is an explanatory diagram showing the sub-two-dimensional array data after rotation by 90 degrees in FIG. 9(a), and FIG. Figure 13: (at, (b), (cl) are shift diagrams of the second embodiment of the present invention, respectively. Figure 14 is a block configuration diagram showing an example of a two-dimensional shift element according to the present invention, and Figure 15 is a block diagram of the RAM unit arrangement A to A+2 according to the present invention K.
D is the result of reading addresses sequentially into the Shiftre/Zosta array.
- An explanatory diagram showing the contents of the FF array, Figure 16 bl Vi
FIG. 16 is an explanatory diagram showing the stored data of the D-FF array shifted in the column direction according to the present invention (bl is obtained by shifting from the front to the back of the page by the two-dimensional shift unit according to the present invention An explanatory diagram showing stored data in the format of regular sub-two-dimensional array data, Fig. 17 shows the result of reading out the sub-two-dimensional array data according to the present invention to the RAM unit distribution nosta obtained by storing it for each address. Figure 20 is an explanatory diagram showing the contents of the D-FF array in Figure 19. 21 ambiguity is a block mechanical diagram of the actual travel example of r3 of the present invention, Fig. 22 fal, fbl, !cl is a block elliptical diagram of the two-dimensional shift unit of Fig. 21, and Fig. 23 is a block mechanical diagram of the actual travel example of r3 of the present invention. A block configuration diagram of the dimensional shift element. Fig. 24 is an explanation showing the result of sequentially reading the two-dimensional array data in the RAM unit array of Fig. 6 into the D-FF array of the two-dimensional shift unit at addresses A-A+2. Figure 25 is a diagram showing the contents of the D-FF array obtained by rotating the array data in Figure 24 by 90 degrees using the function of the two-dimensional shift unit. Figure 26 is a diagram showing the array data in Figure 25. Figure 27 shows the contents of the D-FF array in Figure 26 stored in address C-C+2 of the RAM UniSoto array. Figure 28 is an explanatory diagram showing the two-dimensional array data in the RAM unit array including addresses c+3 to C+8 obtained in the manner shown in Figure 28. Fig. 29 is a schematic diagram showing the results of sequentially reading out addresses C+6, C+3, and C in Fig. 28 to the D-FF of the two-dimensional shift unit, and Fig. 30 is a block diagram of the second embodiment of the present invention. It is a configuration diagram. 1. 1'... 90 degree rotator, 2... RAM unit, 3... Control a section, 4... Path. 5b, 5c... Address modifier, 6. 6', 99... Address signal input terminal. 7... Address modification control input terminal, 7'...
Shift register input terminal, 8. 8', 8
lj, 8 B', 8 8'...Pass, Jllll
l... Rotating element %10'... Two-dimensional shift element, 11.11'. 53, 54.55...Master slave D-FF. 12... Tristate Panopha, l 3 , 1 3', 1 3", 51 , 52,
70. 7172...Selector, No5...Upward input/output terminal, l6...Rightward input/output terminal, 17...
・Downward input/output terminal, J8...Leftward input/output terminal, 20~28.90~98...RAM Uninote, 30
...Switching network, 3...Shifter.
32...Data input/output terminal, 40-48...Shift register, 56,76.77...Data input terminal. 5
7, 75.78...Data output terminal, 60-68...
- Input/output terminal of the two-dimensional shift unit for path 8,
80... Column unit in the two-dimensional shift unit. 7
00, 100', 100''...Two-dimensional shift unit, 110~No18, I2θ~1:'11,13σ
~138...Two-dimensional shift element, 2θO...
Makoto unit arrangement.

Claims (4)

[Claims] (1) A memory unit arranged in a matrix that has both a means for accessing the same address as a whole and a means for accessing a different address for each row, and a means for replacing two-dimensional array data on a row-by-row basis; 90 dimensional array data
A two-dimensional array data rotation mechanism characterized by having a means for rotating an odd number of degrees. (2) In the two-dimensional array data rotation mechanism according to claim 1, the memory units arranged in a matrix having both means for accessing the same address as a whole and means for accessing different addresses for each row are randomly arranged. A two-dimensional array data rotation mechanism comprising a two-dimensional array of access type memory units and means for modifying addresses supplied thereto on a row-by-row basis as necessary. (3) In the two-dimensional array data rotation mechanism according to claim 1, the memory units arranged in a matrix having both means for accessing the same address as a whole and means for accessing different addresses for each row are input. 1. A two-dimensional array data rotation mechanism comprising a two-dimensional array of rotatable shift registers whose input ports or output ports can be changed on a row-by-row basis. (4) The two-dimensional array data rotation mechanism according to claim 1, further comprising means for rotating the two-dimensional array data by an odd number of 90 degrees for each row of the matrix array of the storage unit. Data rotation mechanism.