JTransforms FFT：偶数和奇数情况的区别

Question

我对任意长度的数组执行 FFT。 API可以引用如下：

realForward
public void realForward(double[] a)
Computes 1D forward DFT of real data leaving the result in a. The physical layout of the output data is as follows:

if n is even then
a[2*k] = Re[k], 0<=k<n/2
a[2*k+1] = Im[k], 0<k<n/2 
a[1] = Re[n/2]
if n is odd then
a[2*k] = Re[k], 0<=k<(n+1)/2 
a[2*k+1] = Im[k], 0<k<(n-1)/2
a[1] = Im[(n-1)/2]

在阅读了几个已经回答过的问题后，我仍然无法定义循环来获取幅度值 m_k=sqrt(RE_k²+IM_k²)。

每种情况下 index=1 处的内容是什么？（或者作者实际上是指 index=0）？

Answer 1

a 数组中的大多数返回值都是复数，并以其自然频域顺序返回。然而，有一些特殊情况是：

纯实数的0Hz频率分量（偶数和奇数n）
对于奇数也是纯实数的奈奎斯特频率分量 n。

然后作者选择将所有正常情况放在索引 2 之后，并在 a[0] 和 a[1] 中保留一对值来处理那些特殊情况。 a[0] 中的是 0Hz 频率分量。对于 a[1] 它变得有点棘手。它始终是最高频率分量的一部分，但是如果 n 是偶数或奇数，如何处理它会有所不同。对于偶数 n，那么最后一个频率分量是纯实数，因此可以直接存储在 a[1] 中。对于奇数 n 最后的频率分量不是纯实数，所以我们仍然需要一对数组元素来存储结果。在这种情况下，由于对从索引 2 开始，并且数组的大小很奇怪，最后一对不适合，所以作者使用 a[1] 作为缺失的元素。

或许了解这一点的最简单方法是通过几个示例。所以，这是一个偶数长度的 n=8 示例：

Bin  Complex result Comments
===  ============== =============
0    (a[0],0)       Purely real
1    (a[2],a[3])
2    (a[4],a[5])
3    (a[6],a[7])
4    (a[1],0)       Purely real
5    (a[6],-a[7])   Symmetric with bin 3
6    (a[4],-a[5])   Symmetric with bin 2
7    (a[2],-a[3])   Symmetric with bin 1

这是一个奇数长度的 n=7 示例：

Bin  Complex result Comments
===  ============== =============
0    (a[0],0)       Purely real
1    (a[2],a[3])
2    (a[4],a[5])
3    (a[6],a[1])
4    (a[6],-a[1])   Symmetric with bin 3
5    (a[4],-a[5])   Symmetric with bin 2
6    (a[2],-a[3])   Symmetric with bin 1

最后计算幅度的相应代码：

double[] m = new double[n/2 + 1];

boolean isOdd = ((n % 2) == 1);
if (isOdd) {
  // odd case
  m[0] = abs(a[0]);
  for (int i = 1; i < (n-1)/2; i++) {
    m[i] = sqrt(a[2*i]*a[2*i] + a[2*i+1]*a[2*i+1]);
  }
  m[(n-1)/2] = sqrt(a[n-1]*a[n-1] + a[1]*a[1]);
} else {
  // even case
  m[0] = abs(a[0]);
  for (int i = 1; i < n/2; i++) {
    m[i] = sqrt(a[2*i]*a[2*i] + a[2*i+1]*a[2*i+1]);
  }
  m[n/2] = abs(a[1]);
}

JTransforms FFT：偶数和奇数情况的区别

JTransforms FFT: Difference between even and odd-case

java

algorithm

fft