Area-time lower bounds are derived for the VLSI computation of the (n1 x n2 x ... 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 = n1 x n2 x ... x nd, for any word-local protocol. The bound was previously known for the special case when R = Z_M, the ring of integers modulo M. Second, an AT^2 = Ω((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(p^m) is a finite ﬁeld of polynomials of degree m with coefficients in Z_p, 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.

### New Area-Time Lower Bounds for the Multidimensional DFT

#### Abstract

Area-time lower bounds are derived for the VLSI computation of the (n1 x n2 x ... 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 = n1 x n2 x ... x nd, for any word-local protocol. The bound was previously known for the special case when R = Z_M, the ring of integers modulo M. Second, an AT^2 = Ω((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(p^m) is a finite ﬁeld of polynomials of degree m with coefficients in Z_p, 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.
##### Scheda breve Scheda completa Scheda completa (DC) 2011
Computing: The Australasian Theory Symposium (CATS 2011)
9781920682989
File in questo prodotto:
Non ci sono file associati a questo prodotto.
##### Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: `https://hdl.handle.net/11577/2439273`
##### Citazioni
• ND
• 1
• ND