Transposition circuit

• US 7,231,413 B2
• Filed: 01/29/2004
• Issued: 06/12/2007
• Est. Priority Date: 10/21/1999
• Status: Expired due to Fees

• Current Assignee: LAPIS Semiconductor Co., Ltd. (ROHM Co., Ltd.)
• Original Assignee: OKI Electric Industry Company Limited
• Inventors: Natsume, Kenichi
• Primary Examiner(s): Ngo; Chuong D.
• Application Number:
  US10/766,484
• Publication Number:
  US 20040186869A1
• Time in Patent Office: 1,230 Days
• Field of Search: 708/401, 708/400
• US Class Current: 708/401
• CPC Class Codes: G06F 7/785 having a sequence of storage locations each being individually accessible for both enqueue and dequeue operations, e.g. using a RAM

Abstract

The transposition circuit includes N input terminals (where N is an integer of 2 or greater) and N output terminals. This transposition circuit is configured such that when N packets of data for each matrix row are inputted in parallel to the corresponding input terminals, N packets of data are output in parallel for each matrix column from the corresponding output terminals. This transposition circuit generates data packets arranged as a transposed matrix and obtained from data packets in the form of an N×N matrix by interchanging the rows and columns of the original matrix.

Claims

1. A transposition circuit for generating data packets arranged as a transposed matrix and obtained from data packets in the form of an N×

N matrix (where N is an integer of 2 or greater) by interchanging rows and columns of an original matrix, wherein N input terminals and N output terminals are provided;

wherein N packets of data are output in parallel for each matrix column from said output terminals when N packets of data are input in parallel for each matrix row to said input terminals;

wherein the transposition circuit is provided with N memory units having storage areas to accommodate N data packets, N input selectors having output ports individually connected to input ports of the memory units, N output selectors having output ports individually connected to said output terminals, and a control unit;

wherein said input and output selectors having N ports, and any of the ports of said input and output selectors are used as an input port in accordance with a common selection signal from said control unit to said input and output selectors;

wherein the ports of said input selectors are connected to corresponding ones of the input terminals;

wherein the ports of said output selectors are connected to output ports of corresponding ones of the memory units; and

wherein said control unit generates the common selection signal, and produces address signals to specify a common storage area for each of the memory units, to both read data from and write data to the common storage areas during a same period.

2. The transposition circuit of claim 1, wherein the memory units are units of random access memory.

3. The transposition circuit of claim 1, wherein N is 4.

4. The transposition circuit of claim 3, wherein the first input terminal is connected to the first port of the first input selector, the second port of the second input selector, the third port of the third input selector, and the fourth port of the fourth input selector;

wherein the second input terminal is connected to the fourth port of the first input selector, the first port of the second input selector, the second port of the third input selector, and the third port of the fourth input selector;

wherein the third input terminal is connected to the third port of the first input selector, the fourth port of the second input selector, the first port of the third input selector, and the second port of the fourth input selector;

wherein the fourth input terminal is connected to the second port of the first input selector, the third port of the second input selector, the fourth port of the third input selector, and the first port of the fourth input selector;

wherein the first through fourth input selectors have output ports individually connected to the input ports of the first through fourth memory units;

wherein the output port of the first memory unit is connected to the first port of the first output selector, the fourth port of the second output selector, the third port of the third output selector, and the second port of the fourth output selector;

wherein the output port of the second memory unit is connected to the second port of the first output selector, the first port of the second output selector, the fourth port of the third output selector, and the third port of the fourth output selector;

wherein the output port of the third memory unit is connected to the third port of the first output selector, the second port of the second output selector, the first port of the third output selector, and the fourth port of the fourth output selector;

wherein the output port of the fourth memory unit is connected to the fourth port of the first output selector, the third port of the second output selector, the second port of the third output selector, and the first port of the fourth output selector; and

wherein the output ports of the first through fourth output selectors are individually connected to the first through fourth output terminals.

5. The transposition circuit of claim 4, wherein the memory units are units of random access memory.

6. The transposition circuit of claim 4, wherein a data packet corresponding to a single 4×

4 matrix is processed in eight periods;

wherein during a first four periods, values of said selection signal and i address signals increase from 0 to 3 in increments of one for each period;

wherein during a last four periods, the values of said selection signal increases from 0 to 3 in increments of one for each period and the i address signals decrease in increments of one for each period with (i−

1) as an initial value;

wherein the first through fourth input selectors and the first through fourth output selectors select the first, second, third, and fourth ports of the memory units as input ports when the selection signals respectively assume values of 0, 1, 2 and 3; and

wherein when the address signals assume values of 0, 1, 2 and 3, the i address signals specify addresses 0, 1, 2, and 3 as common storage areas of the memory units, respectively.

7. The transposition circuit of claim 1, wherein the memory units are units of 2-port random access memory.

8. A transposition circuit comprising:

N input terminals, wherein N is an integer greater than 2;

N output terminals;

N input selectors each having N input ports coupled to the N input terminals and each having an output port, the N input selectors providing data from one of the input ports as an output responsive to a common selection signal;

N memory units having storage areas for N packets of data and each having an input port coupled to respectively different ones of the output ports of the N input selectors;

N output selectors each having N input ports coupled to the output ports of the N memory units and each having an output port coupled to respectively different ones of the N output terminals, the N output selectors respectively providing data from one of the input ports thereof as an output responsive to the common selection signal; and

a controller that provides the common selection signal, and that provides address signals to the N memory units to designate common storage areas, wherein data is both written into and read out from the common storage areas during a same period.

9. The transposition circuit of claim 8, wherein N=4.

10. The transposition circuit of claim 8, wherein the N memory units are random access memories.