The Discrete Fourier Transform (DFT)

• The Discrete Fourier Transform (DFT) is defined for an N-point sequence Xn, where n ranges from 0 to N-1.
• An N-point sequence yields an N-point transform.
• Xk can be shown as an inner product.
• WN Notation: WN = e^(-j2π/N).
• Xk = [1 Wk W2k ...W(N-1)k]
  • Wk = e^(-j2π/N)
• By varying k from 0 to N–1 and combining the N inner products, the following is obtained: X = Wx.
• W is an N×N matrix, known as the "DFT Matrix”.
• WN is used to make the DFT matrix size explicit.
• Each inner product needs N complex multiplications and N inner products are required.
• N² multiplications are required, but the first row and first column are all 1s and should not be counted as multiplications.
• There are 2N - 1 such instances, and the number of complex multiplications is hence N² – 2N + 1, which is (N – 1)².
• Each inner product requires N-1 complex additions, and thus N(N-1) complex additions are required.
• Complex multiplications is (N – 1)² and complex additions is N(N-1).
• This operation count for multiplications and additions assumes that Wk has been pre-computed offline and available in memory.
• If values of Wk are not available, the operation count increases, but it is assumed that all the required Wk have been pre-computed and are available.
• For large N, (N – 1)² ≈ N² ≈ N(N − 1).
• Multiplications and additions are O(N²).
• If N = 10^3, then O(N²) = 10^6 (one million), making the straightforward method slow and impractical even for a moderately long sequence.
• If N is even, the sequence can be split into two halves to reduce the operation count using a divide and conquer approach.
• Each sequence has N/2 points, and the N/2 point DFT of each sequence is computed.
• Multiplications = 2 x (N/2)² = N²/2.
• Individual DFT results can be combined to get the DFT and overhead will be consumed to combine the two results.
• If (N²/2 + overhead) < N², this will reduce the operation count.
• With N set to 8, strightforward implementation requries approximately 64 multiplications.
• The "divide and conquer" approach requires approximately 2*(8/2)² + overhead, or 32 + overhead multiplications.
• It must be possible to combine the two DFTs to get the original DFT, and the overhead must be less than 64 additions.

Decimation in Time (DIT) Algorithm

• The decimation-in-time (DIT) algorithm has {gn} = {X2n} and {hn} = {X2n+1}.
• {gn} contains the even-indexed samples, and {hn} contains the odd-indexed samples.
• {Gk} and {Hk} are N/2 point DFTs.
• The overhead for combining the two N/2 point DFTs is the multiplicative factor Wkn for k = 0,1,..., N-1.
• Wkn is known as the twiddle factor.
• {Gk} and {Hk} are periodic with period N/2: Gk+(N/2) = Gk , Hk+(N/2) = Hk
• W+ = -Wk
• WknHk needs to be computed only once for k = 0 to N/2-1.
• The multiplication overhead due to the twiddle factors is only N/2.

Butterfly Diagram

• Shows the computation of Xk and Xk+N/2 from Gk and Hk using twiddle factors.

Savings

• With N=8 straightforward requires approximately 64 multiplications.
• The "Divide and Conquer" approach after the first stage requires 32 + 4 = 36 multiplications.
• This approach reduces the number of additions and multiplications.

Strategy

• The same idea can be applied for calculating the N/2 point DFT of the sequences {gr} and {hr}.
• Computational savings can be obtained by dividing {gr} and {hr} into their odd- and even-indexed halves.
• Can be applied recursively log2N times if N is a power of 2.
• Such algorithms are called radix 2 algorithms.
• If N= 2γ , then the final stage sequences are all length 2.
• For a 2-point sequence {P0, P1 }, the DFT coefficients are P0 = P0 + P1 and P1 = P0 – P1.

Overall operation count

• Direct method requires N² multiplications.
• N²/2 is due to the twiddle factors.
• The number of multiplications needed with there are log2 N stages, approximately (N/2)log2N.
• If W+ = -Wk is not considered, the overhead count will be N.
• The overall multiplication count will be Nlog2N.
• Savings of two orders of magnitude can be shown where N² = 1,048,576 and Nlog2N = 10,240.
• For N = 8, the first split requires the data to be arranged as follows: X0, X2,X4,X6, X1,X3,X5,X7.
• In the second and final split, the data appear in the following order: X0, X4, X2, X6, X1, X5, X3, X7.
• The final order is said to be in "bit reversed" form.
• For a card sequence 7, 8, 9, 10, J, Q, K, A, reverse as follows:
  • First, reverse pairwise: 8, 7, 10, 9, Q, J, A, K.
  • Then swap the adjacent pairs: 10, 9, 8, 7, A, K, Q, J.
  • Finally, swap the two groups of 4: A, K, Q, J, 10, 9, 8, 7.
• The first step of swapping of bits pairwise can be done with bitwise AND/OR and bit shift operators.
• Pick out the even and odd bits using masks, left shift the first result and right shift the second result.
• Bitwise OR the two above results.
• Bit reversal for the entire array can be costly if not performed efficiently. Several efficient algorithms are available for sorting an array in bit-reversed order.

In-Place computation

• Considers Notation: X(0)= Xk being the first stage.
• X(log2N)= Xk is the last stage.
• For the m-th stage butterfly:
  • Input: X(m-1), X(m-1)
  • Output: X(m), X(m)
• The corresponding equations are X(m)= X(m-1)+ WX(m-1) and X(m)= X(m-1)WX(m-1).
  • X(m-1)and X(m-1)are needed for computing X(m)and X(m)
  • Hence, X(m) ←X(m-1)This is called "in-place computation".
• X0 and X4 are not needed once that butterfly is computed, therefore can be overwritten with the results of the butterly computation.
• X0 + X4 = X[0]
• X0 - X4 = X[4]
• Another method of splitting the input sequence into half is as follows: X0,X1,X2,X3,X4,X5,X6,X7.
• Similar savings are obtained in this case also.
• The output 𝑋k will now appear in bit reversed order.
• This method is called as the Decimation in Frequency algorithm.
• When N is not a power of 2 but is a composite number, it can be expressed in terms of its prime factors: N=6=3x2.
• We can split the sequence into 3 segments of 2 samples each: X0,X3, X1,X4, X2,X5.
• Three 2point DFTs are computed to get the final DFT, significant savings is obtained.
• Efficient algorithms exist when N is prime!