one (single)-sided fft and fft2

The solution of FFT is symmetric. I am wondering whether there is a built-in function to produce a one(single)-sided solution. One-dimensional transform is simple. How can we make a 2D FFT producing a single-sided solution?

[David Goodmanson]

Hello Linan,

You mean that the fft of a REAL function is symmetric.

Also, once symmetry is taken into account, a 2n-point fft has n+1 independent coefficients,and a (2n+1)-point fft also has n+1 independent coefficients. Given the output of a single-sided fft you are going to have to either keep track somehow of the original number of points or restrict the one-sided fft to, say, real functions with an even number of points.

[Linan Xu]

Yes, I specifically focus on the real numbers as input for FFT.

How can we do it in 2D efficiently? I make a single example for 1D (fft_half and ifft_half). Following the similar strategy used in 1D, we can develop a fft2_half and ifft2_half in 2D. However, I am not sure how I can efficiently deal with the 2D FFT.

function [S] = fft_half(s,opt)

% Inputs:
%   s: must be real.
%   opt: 'fftshift' or none
% Output:
%   S: one-sided Fourier coefficients.

n=length(s);

if nargin==1
    S = fft(s);  
    S = S(1:floor(n/2)+1);
else
    S = fftshift(fft(s));  
    S = S(1:floor(n/2)+1);   
end

end

According, we have

function [s] = ifft_half(s,opt)

% Inputs:
%   s: one-sided Fourier coefficients (frequency domain).
%   opt: 'fftshift' or none
% Output:
%   S: full signal in the time domain.

n=length(s);
tmp=iscolumn(s);
if tmp==0
    s=s';
end

if mod(n,2)==0 %even number
    S=[s;conj(flip(s(2:end-1)))];    
else % odd number
    S=[s;conj(flip(s(2:end)))];    
end

if nargin==1
    s=ifft(S);
else
    s=ifft(ifftshift(s));
end

if tmp==0
    s=s';
end

end

[David Goodmanson]

Before you get to 2d, what about the situation in 1d? For an 8 point fft_half, the result has five elements. For a 9 point fft_half, the result also has five elements. Ifft_half cannot distinguish between those two cases. So:

x = 1:9
ifft_half(fft_half(x))
ans =
1.0000
9.0000
8.0000
7.0000
6.0000
5.0000
4.0000
3.0000
2.0000

which is not quite right, but fixable. On the other hand,

x = 1:8
ifft_half(fft_half(x))
ans = 
0.4444
7.0181
6.5430
5.5331
4.9259
3.9630
3.3558
2.3459
1.8708    % nine elements

[Linan Xu]

I have noticed that. I think the new version is working. I specify the length of the output signal for the function, ifft_half. Please see below.

RunMe.m

clear all
close all

n=11;

a=rand(n,1)

A0=fft(a);
A=fft_half(a);
ifft_half(A,n)

% A0-ifft2_half(A,nz,nx)
a-ifft_half(A,n)

The two functions (fft_half and ifft_half) are updated as follows

function [S] = fft_half(s,opt)

% Inputs:
%   s: must be real.
%   opt: 'fftshift' or none
% Output:
%   S: one-sided Fourier coefficients.

n=length(s);

if nargin==1
    S = fft(s);  
    S = S(1:floor(n/2)+1);
else
    S = fftshift(fft(s));  
    S = S(1:floor(n/2)+1);   
end

end

function [s] = ifft_half(s,n,opt)

% Inputs:
%   s: one-sided Fourier coefficients (frequency domain).
%   opt: 'fftshift' or none
% Output:
%   S: full signal in the time domain.

tmp=iscolumn(s);
if tmp==0
    s=s';
end

if mod(n,2)==0 %even number
    S=[s;conj(flip(s(2:end-1)))];    
else % odd number
    S=[s;conj(flip(s(2:end)))];    
end

if nargin==2
    s=ifft(S);
else
    s=ifft(ifftshift(s));
end

if tmp==0
    s=s';
end

end

[David Goodmanson]

it's better, although ifft_half(fft_half ... ) still does not bring x = 1:9 back to 1:9

[Linan Xu]

I forgot that fft(a')' is not fft(a). I have fixed the function ifft_half.

function [s] = ifft_half(s,n,opt)

% Inputs:
%   s: one-sided Fourier coefficients (frequency domain).
%   opt: 'fftshift' or none
% Output:
%   S: full signal in the time domain.

tmp=iscolumn(s);
if tmp==0
    s=s';
end

if mod(n,2)==0 %even number
    S=[s;conj(flip(s(2:end-1)))];    
else % odd number
    S=[s;conj(flip(s(2:end)))];    
end

if tmp==0
    S=S';
end

if nargin==2
    s=ifft(S);
else
    s=ifft(ifftshift(s));
end

end

[David Goodmanson]

Since the intent was simply to transpose input s to a column vector without complex conjugation, it might be clearer later on to take your previous code and use s.' instead of s' in a couple of places.

fft2(rand(4,4)) or fft2(rand(5,5)) or fft2(rand(5,4)) shows that placement of the complex conjugates is not so easy in the 2d case.