Area-time lower bounds are derived for the VLSI computation of the (n1 ×n2 ×...×nd)-point multidimensional DFT (MDDFT) over different types of rings and different types of input/output protocols.
First, an AT 2 = Ω (N log |R|)2 bound is obtained for any finite ring R, where N = d k=1
nk, for any word-local protocol. The bound was previously known for the special case when R = ZM , the ring of integers modulo M.
Second, an AT2 = Ω(Nb)2 word-local bound is
derived when R is the complex field, the components of the input are fixed-point numbers of b bits, and the precision of the output components guarantees that the resulting approximate transform is injective. No area-time lower bound was previously known for the DFT over the complex field.
Third, an AT 2 = Ω (N log |R|)2 bound is derived when R = GF(pm) is a finite field of polynomials of degree m with coefficients in Zp, for certain classes of non word-local protocols. This is the first area-time lower bound derived for the DFT with I/O protocols that are not word-local. |
(from crpit.com)
