Optimal Architectures for Multidimensional Transforms

Multidimensional transforms have widespread applications in computer vision, pattern analysis and image processing. The only existing optimal architecture for computing multidimensional DFT on data of size n = Nd requires very large rotator units of area O(n^2) and pipeline-time O(log n). In this paper we propose a family of optimal architectures with areatime trade-offs for computing multidimensional transforms. The large rotator unit is replaced by a combination of a small rotator unit, a transpose unit and a block rotator unit. The combination has an area of O(N^(d+2a)) and a pipeline time of O(N^(d/2-a)log n), for 0 < a < d/2. We apply this scheme to design optimal architectures for two-dimensional DFT, DHT and DCT. The computation is made efficient by mapping each of the one-dimensional transforms involved into two dimensions.