Conferences in Research and Practice in Information Technology
  

Online Version - Last Updated - 20 Jan 2012

 

 
Home
 

 
Procedures and Resources for Authors

 
Information and Resources for Volume Editors
 

 
Orders and Subscriptions
 

 
Published Articles

 
Upcoming Volumes
 

 
Contact Us
 

 
Useful External Links
 

 
CRPIT Site Search
 
    

New Area-Time Lower Bounds for the Multidimensional DFT

Bilardi, G. and Fantozzi, C.

    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.
Cite as: Bilardi, G. and Fantozzi, C. (2011). New Area-Time Lower Bounds for the Multidimensional DFT. In Proc. Computing: The Australasian Theory Symposium (CATS 2011) Perth, Australia. CRPIT, 119. Alex Potanin and Taso Viglas Eds., ACS. 111-120
pdf (from crpit.com) pdf (local if available) BibTeX EndNote GS