fftshift/ifftshift C/C++ source code [closed]

Question

Does anyone know if there is any free and open source library that has implemented these two functions the way they are defined in matlab?

Thanks

Answer 1

FFTHIFT / IFFTSHIFT is a fancy way of doing CIRCSHIFT. You can verify that FFTSHIFT can be rewritten as CIRCSHIFT as following. You can define macros in C/C++ to punt FFTSHIFT to CIRCSHIFT.

A = rand(m, n);
mm = floor(m / 2);
nn = floor(n / 2);
% All three of the following should provide zeros.
circshift(A,[mm, nn]) - fftshift(A)
circshift(A,[mm,  0]) - fftshift(A, 1)
circshift(A,[ 0, nn]) - fftshift(A, 2) 

Similar equivalents can be found for IFFTSHIFT.

Circular shift can be implemented very simply with the following code (Can be improved with parallel versions ofcourse).

template<class ty>
void circshift(ty *out, const ty *in, int xdim, int ydim, int xshift, int yshift)
{
  for (int i = 0; i < xdim; i++) {
    int ii = (i + xshift) % xdim;
    for (int j = 0; j < ydim; j++) {
      int jj = (j + yshift) % ydim;
      out[ii * ydim + jj] = in[i * ydim + j];
    }
  }
}

And then

#define fftshift(out, in, x, y) circshift(out, in, x, y, (x/2), (y/2))
#define ifftshift(out, in, x, y) circshift(out, in, x, y, ((x+1)/2), ((y+1)/2))

This was done a bit impromptu. Bear with me if there are any formatting / syntactical problems.

Answer 2

Normally, centering the FFT is done with v(k)=v(k)*(-1)**k in the time domain. Shifting in the frequency domain is a poor substitute, for mathematical reasons and for computational efficiency. See pp 27 of: http://show.docjava.com/pub/document/jot/v8n6.pdf

I am not sure why Matlab documentation does it the way they do, they give no technical reference.