function  c=ftr(m,y)

% c=ftr(m,y)
% fft of y, a vector of dimension 2^m


N=2^m;
z=0:N-1;
z=exp(-2*pi*i*z/N);
c=y;
for n=1:m
  for k=1:2^(m-n)
    for j=1:2^(n-1)
      u=c((k-1)*2^(n-1)+j);
      v=z((j-1)*2^(m-n)+1)*c((k-1)*2^(n-1)+j+2^(m-1));
      d((k-1)*2^n+j)=(u+v)/2;
      d((k-1)*2^n+j+2^(n-1))=(u-v)/2;
    end
  end
  c=d;
end