Optimal Architectures for Multidimensional Transforms

TitleOptimal Architectures for Multidimensional Transforms
Publication TypeReports
Year of Publication1988
AuthorsChakrabarti C, JaJa JF
Date Published1988///
InstitutionInstitute for Systems Research, University of Maryland, College Park
KeywordsTechnical Report

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.