Universal architecture for matrix transposition

Abstract

A new real-time architecture for matrix transposition is presented. This architecture exploits the inherent parallelism and pipelining of the transposition operation resulting in an efficient mapping of the operation (algorithm) onto the structure. More importantly, this architecture is an universal implementation of executing matrix transposition because it allows data to flow in and out of the structure in either serial or parallel fashion. This architecture has potentially wide applications in real-time data processing, particularly in the areas of signal processing, FFT computations, multidimensional image processing, robotic-vision, database manipulation etc. A basic cell is defined which represents a matrix element and is capable of handling data K bits in width. For a N × N matrix, N2 basic cells are connected in a pipelined fashion along the N rows (N columns) of the matrix with the interconnection between adjacent rows (columns) organised in a serpentine fashion. The architecture has a very small execution time and low communication complexity. The simplicity and regular nature of the structure combined with the local interconnection of the elements makes VLSI implementation of the architecture possible.