Q10Digital Signal Processing

DIF (Decimation-In-Frequency) FFT Algorithm

The Decimation-In-Frequency (DIF) FFT algorithm is structurally complementary to the DIT algorithm discussed in the companion u5-q5(b) answer: rather than splitting the INPUT sequence into even/odd-indexed subsequences (as DIT does), DIF instead splits the OUTPUT (frequency-domain) sequence into even- and odd-indexed frequency components, computed by first combining the first-half and second-half TIME-domain samples (using addition/subtraction and twiddle-factor multiplication) before performing two separate (N/2)-point DFTs on the resulting combined sequences.

First-stage DIF decomposition formulas: for an N-point sequence x(n), define two new (N/2)-length sequences:

The even-indexed DFT outputs are then obtained as the (N/2)-point DFT of g(n): X(2k)=DFT{g(n)}, and the odd-indexed DFT outputs are obtained as the (N/2)-point DFT of h(n): X(2k+1)=DFT{h(n)}.

First-Stage Calculation for the Given Sequence

Given: x(n) = {1, 2, 3, 4, 4, 3, 2, 1} for n=0,...,7, N=8 (so N/2=4).

Computing g(n) = x(n) + x(n+4) for n=0,1,2,3:

• g(0) = x(0)+x(4) = 1+4 = 5
• g(1) = x(1)+x(5) = 2+3 = 5
• g(2) = x(2)+x(6) = 3+2 = 5
• g(3) = x(3)+x(7) = 4+1 = 5

Interestingly, g(n)={5,5,5,5} is a constant sequence, whose 4-point DFT is trivially G(k)={20,0,0,0} (since the DFT of a constant sequence has all its energy concentrated at k=0), directly giving X(0)=20, X(2)=0, X(4)=0, X(6)=0 - matching the verified final result.

*Computing h(n) = [x(n)-x(n+4)]W_8^n for n=0,1,2,3, where W_8^n=e^(-j2pin/8):*

• n=0: [x(0)-x(4)]W_8^0 = (1-4)1 = -3
• n=1: [x(1)-x(5)]W_8^1 = (2-3)e^(-jpi/4) = (-1)(0.7071-j0.7071) = -0.7071+j0.7071
• n=2: [x(2)-x(6)]W_8^2 = (3-2)e^(-jpi/2) = (1)(0-j1) = -j1
• n=3: [x(3)-x(7)]W_8^3 = (4-1)e^(-j3pi/4) = (3)*(-0.7071-j0.7071) = -2.1213-j2.1213

This gives h(n) = {-3, -0.7071+j0.7071, -j1, -2.1213-j2.1213}, which must then itself be transformed via a further 4-point DFT to yield the odd-indexed outputs X(1), X(3), X(5), X(7) - continuing this recursive computation (either by direct further application of the DIF splitting to this 4-point sequence, or, equivalently, by direct 4-point DFT summation applied to h(n)) yields the odd-indexed frequency components.

Final Complete DFT Result

Completing the full recursive DIF-FFT computation (or, equivalently, verifying via direct 8-point DFT summation) yields the complete result:

• X(0) = 20
• X(1) = -5.8284 - j2.4142
• X(2) = 0
• X(3) = -0.1716 - j0.4142
• X(4) = 0
• X(5) = -0.1716 + j0.4142
• X(6) = 0
• X(7) = -5.8284 + j2.4142

Verification via symmetry: since x(n) is both real-valued AND symmetric (x(n)=x(N-n) for this specific palindromic sequence, i.e., x(1)=x(7)=... reading the sequence forwards and backwards gives the same values), the resulting DFT X(k) is guaranteed to be entirely real-valued... however, examining the computed result shows X(k) has non-zero imaginary parts for k=1,3,5,7, which at first appears inconsistent with a symmetric real sequence - closer inspection shows that x(n)={1,2,3,4,4,3,2,1} is symmetric about the point between n=3 and n=4 (an EVEN symmetry point, not centered exactly at n=0), meaning the sequence is real and even-symmetric about n=3.5 rather than about n=0, and a sequence with this kind of offset (rather than origin-centered) symmetry produces a DFT with a well-defined LINEAR phase component (a constant phase slope with frequency) superimposed on an otherwise real-valued underlying magnitude pattern, rather than a purely real DFT outright - this linear-phase characteristic (consistent with the given sequence being a simple, symmetric, even-length triangular-shaped pulse merely offset from the n=0 origin) is fully consistent with the complex-valued but conjugate-symmetric result obtained above (X(7)=X(1), X(5)=X(3), exactly as expected for any real-valued input sequence regardless of its specific internal symmetry properties).

The Decimation-In-Frequency (DIF) FFT algorithm used to compute this 8-point DFT takes a complementary approach to the DIT algorithm discussed elsewhere in this paper: rather than splitting the input sequence into even and odd time-domain samples, the DIF algorithm splits the input sequence into its first half and second half (x(0) through x(3), and x(4) through x(7) respectively for this N=8 example), forms two new N/2-length sequences by adding and subtracting corresponding samples from each half (weighted by the appropriate twiddle factors in the subtraction case), and recursively computes the DFT of each resulting half-length sequence, with this recursive splitting again applied log2(N) times until reaching trivial 2-point DFT computations - the DIF algorithm's characteristic signal-flow structure requires naturally-ordered input but produces bit-reversed-ordered output (exactly the reverse ordering situation compared to the DIT algorithm, which takes bit-reversed input and produces naturally-ordered output), a structural duality that follows directly from the different (time-domain versus frequency-domain) points at which the recursive splitting is applied in each algorithm.

The specific input sequence given here, x(n)={1,2,3,4,4,3,2,1}, possesses an evident even symmetry about its midpoint (x(n)=x(7-n) for all n, i.e., x(0)=x(7)=1, x(1)=x(6)=2, x(2)=x(5)=3, x(3)=x(4)=4), and this time-domain even symmetry has an important, exploitable consequence for the resulting DFT: the DFT of any real, even-symmetric sequence is guaranteed to be purely real-valued at every frequency bin (no imaginary component whatsoever), a considerably stronger symmetry condition than the general conjugate symmetry that holds for any real-valued sequence's DFT (which only guarantees X(N-k)=X*(k), not that each individual X(k) is itself real) - this purely-real-DFT property provides an valuable independent check on the correctness of the computed DFT values X(0) through X(7), since any computed DFT coefficient with a non-negligible imaginary part would immediately indicate an arithmetic error somewhere in the DIF butterfly-computation process, given the guaranteed-real nature of the true result for this particular symmetric input sequence.

Beyond this specific numerical example, it is worth noting the broader computational-savings context that motivates FFT algorithms generally: a direct evaluation of the 8-point DFT definition, computed naively via the double summation formula, requires on the order of N^2=64 complex multiplications, whereas the DIF (or equivalently DIT) FFT algorithm computes the identical result using only (N/2)log2(N) = 43=12 complex multiplications (following the standard FFT multiplication-count formula), representing more than a five-fold reduction in computational effort even for this quite modest N=8 example - this computational saving grows dramatically more significant for the much larger transform lengths (N in the thousands or millions of points) routinely used in real-world spectral-analysis, communications, and audio/image-processing applications, explaining why the FFT algorithm, in either its DIT or DIF form, is considered one of the most important and widely-used algorithms in the entire history of digital signal processing and numerical computing generally.

Finally, it is worth noting the practical significance of this exercise beyond the specific numeric example: computing a DFT via the FFT algorithm (whether DIT or DIF) rather than by direct summation is what makes real-time spectral analysis, digital filtering via fast convolution, and a host of other frequency-domain signal processing techniques computationally feasible for the very large transform lengths routinely required in modern audio, image, radar, and communications signal processing applications, and understanding the underlying butterfly-computation structure illustrated by this small, hand-computable N=8 example provides the essential conceptual foundation for understanding how these much larger, software- or hardware-implemented FFT computations actually operate internally.