Optimal Architectures for Multidimensional Transforms
University of Maryland College Park United States
Pagination or Media Count:
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 On2 and pipeline-time Olog 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 ONd2a and a pipeline time of ONd2-alog n, for 0 a d2. 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.
- Numerical Mathematics