Systolic VLSI architecture for multi-dimensional transforms

A VLSI architecture for separable kernel multi-dimensional transforms is described. What is novel about the architecture is its data rotator, which is a hexagonal mesh of processors. The rotator is completely scalable and modular and is programmable with respect to d and the length of each dimension. The proposed architecture has an AT² figure of O(d²n² log² n), where d is the dimensionality, n is the total number of elements in the data cube, and the precision of an element is assumed to be Θ(log n). The value of AT² for the rotator itself is O(n² log² n) for a single rotation, which is optimal. Multi-dimensional separable kernel transforms may be computed by performing d sets of 1-D transforms, each along a unique axis of the d-D data cube. A natural architecture for such problems consists of a number of 1-D transform processors and a rotator or transposer.