Accession Number:

AD1007036

Title:

Optimal Architectures for Multidimensional Transforms

Descriptive Note:

Technical Report

Corporate Author:

University of Maryland College Park United States

Personal Author(s):

Report Date:

1988-01-01

Pagination or Media Count:

19.0

Abstract:

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.

Subject Categories:

  • Numerical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE