clear all
close all

g(1,:)=[1 1 1 1];                                                           
g(2,:)=[1 -1 1 -1];
g(3,:)=[1 -j -1 j];
g(4,:)=[1 j -1 -j];
N=5;                                                                        
Z=4^N;                                                                      
w=exp(-j*2*pi/(4^N));                                                       
x(1,:)=1:(4^N);                                                             
o=fft(x);                                                                   

for i=0:(4^(N-1)-1)                                                         
    for k=1:N
        a(i+1,:,k)=dec2bin(i,2*(N-1));
        r(i+1,:,k)=dec2bin(0,2*(N-1));
    end
end

for i=1:(N-1)                                                               
    for k=1:(2*i)
        r(:,k,(i+1))=a(:,(2*i-k+1),(i+1));
    end
end   

for i=1:N                                                                   
    b(:,i)=bin2dec(r(:,:,i));
end

clear a  i k

for m=1:N                                                                   
    km(m)=4^(m-1);
    im(m)=(4^(N-1))/km(m);
end


for m=1:N
    for k=1:km(m)                                                           
        for i=1:im(m)
            p(m,i+(k-1)*Z/km(m)+0*im(m))=x(m,i+(k-1)*Z/km(m)+0*im(m))*w^(b(((k-1)*im(m)+i),m)*0);
            p(m,i+(k-1)*Z/km(m)+1*im(m))=x(m,i+(k-1)*Z/km(m)+1*im(m))*w^(b(((k-1)*im(m)+i),m)*1);
            p(m,i+(k-1)*Z/km(m)+2*im(m))=x(m,i+(k-1)*Z/km(m)+2*im(m))*w^(b(((k-1)*im(m)+i),m)*2);
            p(m,i+(k-1)*Z/km(m)+3*im(m))=x(m,i+(k-1)*Z/km(m)+3*im(m))*w^(b(((k-1)*im(m)+i),m)*3);
            t(i+(k-1)*Z/km(m)+0*im(m),m)=0;                                  
            t(i+(k-1)*Z/km(m)+1*im(m),m)=2;                                
            t(i+(k-1)*Z/km(m)+2*im(m),m)=1;
            t(i+(k-1)*Z/km(m)+3*im(m),m)=3;
        end
    end
    for k=1:km(m)                                                           
        for i=1:im(m)         
            x(m+1,i+(k-1)*Z/km(m)+0*im(m))=g(1,:)*[p(m,i+(k-1)*Z/km(m)+0*im(m));p(m,i+(k-1)*Z/km(m)+1*im(m));p(m,i+(k-1)*Z/km(m)+2*im(m));p(m,i+(k-1)*Z/km(m)+3*im(m))];
            x(m+1,i+(k-1)*Z/km(m)+1*im(m))=g(2,:)*[p(m,i+(k-1)*Z/km(m)+0*im(m));p(m,i+(k-1)*Z/km(m)+1*im(m));p(m,i+(k-1)*Z/km(m)+2*im(m));p(m,i+(k-1)*Z/km(m)+3*im(m))];
            x(m+1,i+(k-1)*Z/km(m)+2*im(m))=g(3,:)*[p(m,i+(k-1)*Z/km(m)+0*im(m));p(m,i+(k-1)*Z/km(m)+1*im(m));p(m,i+(k-1)*Z/km(m)+2*im(m));p(m,i+(k-1)*Z/km(m)+3*im(m))];
            x(m+1,i+(k-1)*Z/km(m)+3*im(m))=g(4,:)*[p(m,i+(k-1)*Z/km(m)+0*im(m));p(m,i+(k-1)*Z/km(m)+1*im(m));p(m,i+(k-1)*Z/km(m)+2*im(m));p(m,i+(k-1)*Z/km(m)+3*im(m))];
        end
    end
end

s=t*km'+1;                                                                  
for i=1:Z
    result(i)=x(N+1,s(i));                                                  
end