MATLAB Code for computing DFT using DIT-FFT with Butterfly Diagram

dit-fft.m

clc;
clear;
close all;

% Given sequence
X = [1, 0, -1, 0, 1, 0, -1, 0, 1, 0, -1, 0, 1, 0, -1, 0];
N = length(X); % Length of sequence (must be power of 2)

% Bit-reversal permutation
bit_rev_order = bitrevorder(0:N-1) + 1;
X = X(bit_rev_order);

% FFT computation using butterfly structure
stages = log2(N);
all_stages = zeros(stages + 1, N); % Store intermediate values for visualization
all_stages(1, :) = X;

for s = 1:stages
    m = 2^s;
    half_m = m/2;
    W_m = exp(-1j * 2 * pi / m);
    for k = 0:m:N-1
        for j = 0:half_m-1
            idx1 = k + j + 1;
            idx2 = k + j + half_m + 1;
            t = W_m^j * X(idx2);
            X(idx2) = X(idx1) - t;
            X(idx1) = X(idx1) + t;
        end
    end
    all_stages(s + 1, :) = X; % Store each stage result
end

% Display results
fprintf('DFT using DIT-FFT with Butterfly Computation:\n');
disp(X);

% Plot Only the Butterfly Diagram (No Background Grid, No Extra Plots)
figure;
hold on;
axis off; % Remove background grid and axes

node_positions = zeros(stages + 1, N);
for s = 0:stages
    node_positions(s+1, :) = 1:N; % Align nodes vertically
    for n = 1:N
        scatter(s, node_positions(s+1, n), 80, 'bo', 'filled'); % Plot nodes
        text(s, node_positions(s+1, n), sprintf('%.2f + %.2fi', real(all_stages(s+1, n)), imag(all_stages(s+1, n))), ...
            'VerticalAlignment', 'bottom', 'HorizontalAlignment', 'center');
    end
end

for s = 1:stages
    m = 2^s;
    half_m = m/2;
    for k = 0:m:N-1
        for j = 0:half_m-1
            idx1 = k + j + 1;
            idx2 = k + j + half_m + 1;
            x1 = s - 1;
            x2 = s;
            y1 = node_positions(s, idx1);
            y2 = node_positions(s, idx2);
            plot([x1, x2], [y1, y2], 'k-'); % Draw butterfly connections
            plot([x1, x2], [y2, y1], 'k-');
        end
    end
end
hold off;