AT~2L~2≈ N~2/2 for Fast Fourier Transform in Multilayer VLSI

摘要

In this paper, we show that TV-point fast Fourier transform (FIT) circuits with throughput 1 (i.e., time 1 after pipelining) can be optimally laid out with area N~2/(4[L~2/2]) + o(N~2/L~2) under the multilayer 2-D grid model, where only one active layer (for network nodes) is required and L layers of wires are available, 2 ≤ L ≤ o(N~(1/3)). We further propose AT~2L~2 or 2AT~2 [L~2/2] as a new parameter for characterizing the area-time complexity for multilayer VLSI, and show that AT~2L~2 ≈ N~2/2 for N-point Fourier transform.