Large dft modules: 11, 13, 16, 17, 19, and 25  (Page 4/5)

Scaling in a common factor dft

Scaling short length DFT algorithms can sometimes save multiplies. The prime length modules $(p>2)$ generally include one constant equal to $1/(p-1)$ , corresponding to convolution modulo $x-1$ This convenient constant can in some cases be exploited. One particularly nice example is the length 25 DFT.

Use length 5 DFT modules to put together a length 25 DFT with Singleton's algorithm. This results in an algorithm which uses the length 5 module ten times, and has sixteen non-trivial twiddle factors. Counting a twiddle factor as 3/2 multiplies, and using DFT modules with 5 multiplies, the full length 25 algorithm will have 74 multiplies.

In order to exploit the constant 1/4 which appears in each length 5 module the basic length 5 module must be modified to create alternate modules A and B (Figure I). The regular length 5 DFT is represented as R. Algorithm A computes the same DFT, but with outputs 1 through 4 scaled up by a factor of 4. Algorithm B expects inputs 1 through 4 to be scaled down by a factor of 1/4. Algorithms A and B have each traded 1 multiply for 2 additions. The additions are used to implement the -factor of 4 which appears in both algorithms.

To implement a scaled algorithm:

• i Assume the input data has been appropriately mapped into a 5 by 5 array.
• ii Use $R$ on the first column of data and A on all other columns. This will scale the data in the twiddle area The twiddle area is the collection of data locations which will be multiplied by non-trivial twiddles and in this instance is composed of all data which falls both in the last four columns and the last four rows of the data array. up by a factor of 4.
• iii Scale down all twiddle factors by a factor of 1/16. This leaves data in the twiddle area scaled down by a composite factor of 1/4 when compared to a normal length 25 DFT.
• iv Use $R$ on the first row of data and use B on all other rows. $B$ is modified to expect the scaled down data in the twiddle area.

Since 4 A's and 4 B's were used, a total trade has been made of 8 multiplies for 16 adds. Such a trade may in many instances be a reasonable exchange. The great thing about this scaling is that the D.C. terms did not have to be scaled, which would have generated more adds in modification A and multiplies in modification B. No additional counter-scaling multiplies were needed in this special example because the twiddle factor were available to absorb the scaling mismatches. Similar approaches should be possible for lengths 9, 49, and 121.

The PFA case is similar in spirit, but is lacking the twiddle factors to perform counter-scaling. One of the modules will have to be modified to perform the counter-scaling function.

Two basic facts will be needed. First, any Winograd-type prime length DFT module contains one constant equal to $1/(p-1)$ and can be modified like algorithm A to scale up all of its outputs except the DC term. This modification trades one multiply for the number of adds needed to implement a multiply by $(p-1)$ . Secondly, any Winograd-type prime length DFT module can be modified to scale all of its outputs by an arbitrary constant at the expense of only one multiply. This is accomplished by nesting the scaling constant with the multiplies in the middle of the Winograd module. Since only one of the module's original constants is trivial (that is the unity constant on the DC term) only one extra multiply is generated. This procedure assumes the module has first been re-arranged to eliminate the "cross" computation as illustrated in Figure II. Such a rearrangement can always be accomplished in prime length modules.