Fast Fourier Transform

Scaling

Because the base-4 architecture is inherently regular, it lends itself to a large variety of implementation options, all of which still use the same circuit structure. Larger transform sizes are achieved by extending the array size along the North/South direction.

Also, the same transform size can be performed using different array sizes. This is possible because the architecture uses the basic "row/column" decomposition of the transform size N such that N=N_rN_c, where the array length is N_r/4. Therefore different resource-speed tradeoffs simply involve changing N_r and N_c , keeping N the same. For example a 1024 point (streaming) transform could be computed using three different sets of values as shown in Table 1. Here, the transform time can be varied by a factor of ~4 in this simple way.

N_r (multipliers)	N_c	Transform Size	Throughput (cycles/DFT)	Throughput (µsec)	ALMs
32	32	1024	689	1.78	7795
16	64	1024	1584	4.08	4400
64	16	1024	432	1.12	14186

Table 1. Example of estimated performance for scaling options obtained by varying N_r and N_c, keeping N the same. The number of real multipliers is N_r.

Finally, it is very straight forward to partition the matrix computations in such a way that the FFT can “re-mapped” to arrays of arbitrarily small size. In this way any base-4 architecture can do any allowed transform size as long as there is sufficient memory.

Note that “scaling” used in this context is different from the term “scalable FFT” used in the context of wireless communication protocols, where its meaning applies to circuits that provide a “run time” or “dynamic” choice of transform size.