Gauss's FFT: DIT or DIF?
I may have an answer, and it has to do with the structure of the butterflies.
[Notation: N-point sequence {X[n]} is the DFT of N-point sequence {x[k]}, typically frequency and time domains, respectively.]
DIT: X[n] = Y[n] + W^n Z[k],
X[n+N/2] = Y[n] - W^n Z[n]
where n = 0 ... N/2 - 1, and W = exp(-j2*Pi/N)
The DIF structure is the dual of the DIT structure. Namely, if we want to replace a DFT calculation of length N, with two length N/2 calculations, the data {x[k]}k=0,N-1, is split into {y[k]} and {z[k]} using the DIF butterfly:
DIF: y[k] = x[k] + x[k+N/2],
z[k] = (x[k] - x[k+N/2])W^k
where k = 0 ... N/2 -1, and as in the DIT case, W = exp(-j2*Pi/N).
In Gauss's mixed-radix algorithm, N = 4 x 3, with reference to the previously posted diagrams, we have radix-3 output butterflies such as
X[3] = X[0,3] + X[1,3]W^3 + X[2,3]W^6
X[11] = X[0,3] + X[1,3]W^11 + X[2,3]W^22
Note that the second line of the butterfly above, X[11], was not used by Gauss, who did not bother to compute X[6] through X[11], as is appropriate for real data.
Note that the second line of the butterfly above, X[11], was not used by Gauss, who did not bother to compute X[6] through X[11], as is appropriate for real data.
Gauss's version of this butterfly reads:
X' = γ + (γ' cos x + j δ' sin x) + (γ'' cos 2x + j δ'' sin 2x)
where γ and δ are a confusing notation that Gauss uses three-times-over for the outputs of the three length-4 1st stage DFTs. Note that the cos nx and sin nx are the twiddle factors equivalent to W^n.
The above butterfly structure makes Gauss's N = 4 x 3 FFT algorithm a DIT, which also makes it of the Cooley-Tukey type.
Since Gauss seems to have used the same methodology for all of his examples, the same conclusion, that his algorithms were DIT, applies to his other mixed-radix example, N = 3 x 4, too, and to the common radix N = 6 x 6 example.
