Decimation in Frequency (DIF - FFT) Algorithm in MATLAB, without using in-built functions.

I am trying to implement the following code in MATLAB -

% Define input sequence
x = input('Enter the sequence : ')
% Get sequence length
N = input('Enter length of DFT : ')
% Compute number of stages
nStages = log2(N);

% Compute twiddle factors
W = exp(-1j*2*pi/N).^(0:N/2-1);

% Apply DIF-FFT algorithm
X = x;
for stage = 1:nStages
    % Compute butterfly indices and twiddle factors
    k1 = 1:2^(stage-1):N;
    k2 = k1 + 2^(stage-1);
    W_stage = W(1:2^(stage-1));
    
    % Apply butterfly to each group of two
    for i = 1:2^(stage-1)
        tmp = X(k1(i)) + X(k2(i))*W_stage(i);
        X(k2(i)) = X(k1(i)) - X(k2(i))*W_stage(i);
        X(k1(i)) = tmp;
    end
    
    % Print output at this stage
    disp(['Output at stage ', num2str(stage), ':']);
    disp(X);
end

% Display final output
disp('DFT:');
disp(X);

But, I am getting the following output with errors -

Index exceeds the number of array elements. Index must not exceed 8.

My Inputs are -

Enter the sequence : [1 2 3 4 5 6 7 2]

Enter length of DFT : 8

Please help me solve this problem!!

Answer 1

[Naren]

Hey,

I understand you are getting an indexing error while writing a code for the DIF-FFT algorithm.The problem here is, in the third iteration, the value of the variable “stage” is 3 and k1 and k2 will have two values each. But in the nested loop, x(k1(3)) and x(k1(4)) are accessed. Another thing is the value inside k2 will be greater than eight, which is higher than the length of the sequence.

Refer to the MATLAB code attached below.

x = input("enter the sequence");  
N = length(x);                          % Length of sequence
p=log2(N);                                 % computing the number of conversion stages
Half=N/2;                                  % half the length of the array
for stage=1:p                             % stages of transformation
    for index=0:(N/(2^(stage-1))):(N-1)    % series of "butterflies" for each stage
        for n=0:(Half-1)                   % creating "butterfly" and saving the results
            pos=n+index+1;                 % index of the data sample
            pow=(2^(stage-1))*n;           % part of power of the complex multiplier
            w=exp((-1i)*(2*pi)*pow/N);     % complex multiplier
            a=x(pos)+x(pos+Half);          % 1-st part of the "butterfly" creating operation
            b=(x(pos)-x(pos+Half)).*w;     % 2-nd part of the "butterfly" creating operation
            x(pos)=a;                      % saving computation of the 1-st part
            x(pos+Half)=b;                 % saving computation of the 2-nd part
        end
    end
Half=Half/2;                               % computing the next "Half" value
end
y=bitrevorder(x);

Hope this will solve your problem.

[Achyuth S.S]

thank you so much. Will verify with this code

[Achyuth S.S]

Thank you, it worked

Answer 2

[Karthick]

x = input("enter the sequence");

N = length(x); % Length of sequence

p=log2(N); % computing the number of conversion stages

Half=N/2; % half the length of the array

for stage=1:p % stages of transformation

for index=0:(N/(2^(stage-1))):(N-1) % series of "butterflies" for each stage

for n=0:(Half-1) % creating "butterfly" and saving the results

pos=n+index+1; % index of the data sample

pow=(2^(stage-1))*n; % part of power of the complex multiplier

w=exp((-1i)*(2*pi)*pow/N); % complex multiplier

a=x(pos)+x(pos+Half); % 1-st part of the "butterfly" creating operation

b=(x(pos)-x(pos+Half)).*w; % 2-nd part of the "butterfly" creating operation

x(pos)=a; % saving computation of the 1-st part

x(pos+Half)=b; % saving computation of the 2-nd part

end

end

Half=Half/2; % computing the next "Half" value

end

y=bitrevorder(x);

Answer 3

[samarth]

% Define input sequence

x = input('Enter the sequence : ')

% Get sequence length

N = input('Enter length of DFT : ')

% Compute number of stages

nStages = log2(N);

% Compute twiddle factors

W = exp(-1j*2*pi/N).^(0:N/2-1);

% Apply DIF-FFT algorithm

X = x;

for stage = 1:nStages

% Compute butterfly indices and twiddle factors

k1 = 1:2^(stage-1):N;

k2 = k1 + 2^(stage-1);

W_stage = W(1:2^(stage-1));

% Apply butterfly to each group of two

for i = 1:2^(stage-1)

tmp = X(k1(i)) + X(k2(i))*W_stage(i);

X(k2(i)) = X(k1(i)) - X(k2(i))*W_stage(i);

X(k1(i)) = tmp;

end

% Print output at this stage

disp(['Output at stage ', num2str(stage), ':']);

disp(X);

end

% Display final output

disp('DFT:');

disp(X);