Optimal layout for fast Fourier transform in multilayer VLSI

Summary form only given. Fast Fourier transform (FFT) is among the most important problems in computer science and engineering, with a variety of important applications including multimedia processing, communications, and numerical computation. Previous butterfly-based FFT implementations are not optimal even if the layouts employed are optimal for butterfly networks. We propose the expanded indirect swap networks (EISN) that is particularly suitable for FFT operations and have efficient layouts. Based on EISN, we propose the first and only optimal VLSI layouts (within a factor of 1+o(1)) reported in the literature thus far for performing FFT under the Thompson model, the extended grid model, and the multilayer 2D grid model. We show that N-point FFT circuits with throughput 1 (i.e., time I after pipelining) can be laid out with area N²/4└L²/2┘+o(N²/L²) and volume LN²/4└L²/2┘+o(N²/L), under the multilayer 2D grid model where only one active layer (for network nodes) is required and L layers of wires are available, 2 ≤ L ≤ o(&nthroot;N). We use AT²L² or 2AT²└L²/2┘ as a new parameter for characterizing the area-time complexity for multilayer VLSI, and show that AT²L² ≈ N²/2for N-point Fourier transform.