这个逆FFT实现有什么问题?

huangapple go评论64阅读模式
英文:

What is wrong with this inverse FFT implementation

问题

以下是您要翻译的内容:

"I am using the following implementation of an inverse Fast Fourier transform (FFT) for images in which the image of size N by N is stored in a vector of length N x N (with N a square number). When I feed this implementation a matrix of zeros except two 1s, one a few rows above the center and symmetrically below the center, the inverse is correctly an image with vertical bands whose frequency matches the position of the 1s.

However, when the 1s are on the left and on the right of the center, I get horizontal bands, but they are not perfectly horizontal. They have a very small slope. When I do exactly the same in Mathematica with the build-in InverseFourier function, the bands are very precisely horizontal.

Is there something wrong in the JavaScript implementation below? The relevant code is given below; a complete MWE is available at this JSFiddle

function invFFT_radix2(out, start, input, N, offset, s ) {
    if (N === 1) {
        out[start] = input[offset];
    } else {
        invFFT_radix2(out, start,     input, N/2, offset,   2*s);
        invFFT_radix2(out, start+N/2, input, N/2, offset+s, 2*s);
        for (var k = 0; k < N/2; k++) {
            var twiddle = cisExp(2*Math.PI*k/N);
            var t = out[start+k];
            out[start+k]     = t.plus ( twiddle.times(out[start+k+N/2]) );
            out[start+k+N/2] = t.minus( twiddle.times(out[start+k+N/2]) );
        }
    }
}

called with 

```javascript
invFFT_radix2(out, 0, input, input.length, 0, 1 )

in which input is the input vector, and out contains the result. All the entries are Complex numbers (as per this response) and the function cisExp is defined as

function cisExp(x) { // e^ix = cos x + i*sin x
    return new Complex(Math.cos(x), Math.sin(x));
}

As a comparision, this is the magnified top of the image with the JSFiddle
这个逆FFT实现有什么问题?

and with Mathematica
这个逆FFT实现有什么问题?

The JS image begins on the left with a white line which becomes black on the right.

请告诉我,您需要进一步的帮助或信息吗?

英文:

I am using the following implementation of an inverse Fast Fourier transform (FFT) for images in which the image of size N by N is stored in a vector of length N x N (with N a square number). When I feed this implementation a matrix of zeros except two 1s, one a few rows above the center and symmetrically below the center, the inverse is correctly an image with vertical bands whose frequency matches the position of the 1s.

However, when the 1s are on the left and on the right of the center, I get horizontal bands, but they are not perfectly horizontal. They have a very small slope. When I do exactly the same in Mathematica with the build-in InverseFourier function, the bands are very precisely horizontal.

Is there something wrong in the JavaScript implementation below? The relevant code is given below; a complete MWE is available at this JSFiddle

function invFFT_radix2(out, start, input, N, offset, s ) {
    if (N === 1) {
        out[start] = input[offset];
    } else {
        invFFT_radix2(out, start,     input, N/2, offset,   2*s);
        invFFT_radix2(out, start+N/2, input, N/2, offset+s, 2*s);
        for (var k = 0; k < N/2; k++) {
            var twiddle = cisExp(2*Math.PI*k/N);
            var t = out[start+k];
            out[start+k]     = t.plus ( twiddle.times(out[start+k+N/2]) );
            out[start+k+N/2] = t.minus( twiddle.times(out[start+k+N/2]) );
        }
    }
}

called with

invFFT_radix2(out, 0, input, input.length, 0, 1 )

in which input is the input vector, and out contains the result. All the entries are Complex numbers (as per this response) and the function cisExp is defined as

function cisExp(x) { // e^ix = cos x + i*sin x
    return new Complex(Math.cos(x), Math.sin(x));
}

As a comparision, this is the magnified top of the image with the JSFiddle
这个逆FFT实现有什么问题?

and with Mathematica
这个逆FFT实现有什么问题?

The JS image begins on the left with a white line which becomes black on the right.

答案1

得分: 1

A 2D [inverse] DFT is the 1D version on one axis then the other, so you could do, for example,

for (let i = 0; i < 2; i++) {
  for (let y = 0; y < HEIGHT; y++) {
    invFFT_radix2(out, y * WIDTH, ss, WIDTH, y * WIDTH, 1);
  }
  ss = out.slice();
  transpose(ss);
}

where

const WIDTH = 256;
const HEIGHT = 256;
const swap = (arr, i, j) => {
  const t = arr[i];
  arr[i] = arr[j];
  arr[j] = t;
};
const transpose = (ss) => {
  for (let i = 1; i < HEIGHT; i++) {
    for (let j = 0; j < i; j++) {
      swap(ss, i * WIDTH + j, j * WIDTH + i);
    }
  }
};
英文:

A 2D [inverse] DFT is the 1D version on one axis then the other, so you could do, for example,

for (let i = 0; i &lt; 2; i++) {
  for (let y = 0; y &lt; HEIGHT; y++) {
    invFFT_radix2(out, y * WIDTH, ss, WIDTH, y * WIDTH, 1);
  }
  ss = out.slice();
  transpose(ss);
}

where

const WIDTH = 256;
const HEIGHT = 256;
const swap = (arr, i, j) =&gt; {
  const t = arr[i];
  arr[i] = arr[j];
  arr[j] = t;
};
const transpose = (ss) =&gt; {
  for (let i = 1; i &lt; HEIGHT; i++) {
    for (let j = 0; j &lt; i; j++) {
      swap(ss, i * WIDTH + j, j * WIDTH + i);
    }
  }
};

huangapple
  • 本文由 发表于 2023年5月17日 09:41:24
  • 转载请务必保留本文链接:https://go.coder-hub.com/76268062.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定