javascript - 用于信号处理的奇函数？

你好！我希望这是一个可以接受的问题。

在查看一些用于信号处理的代码时，我遇到了一个奇怪的函数：

let kInd = (k1, pow) => {

  let k2 = 0;
  let k3 = 0;

  for (let i = 0; i < pow; i++) {
    k3 = k1 >> 1;
    k2 = 2 * (k2 - k3) + k1;
    k1 = k3;
  }

  return k2;

};

此函数在傅里叶变换计算结束时调用，用于交换实部+虚部数组对中的索引：

let fft = samples => {

  let pow = Math.log2(samples.length); // `samples.length` is expected to be 2^int

  // ... a bunch of code to generate `rBuff` and `iBuff` arrays representing 
  // real and imaginary components of fourier values

  // Now make use of `kInd`; conditionally swap some indexes in `rBuff` and `iBuff`:
  for (let i = 0; i < rBuff.length; i++) {
    let k = kInd(i, pow);
    if (k >= i) continue;
    [ rBuff[i], rBuff[k] ] = [ rBuff[k], rBuff[i] ];
    [ iBuff[i], iBuff[k] ] = [ iBuff[k], iBuff[i] ];
  }

  // ... A bit of code to convert to power spectrum and return result

};

我的问题是：kInd到底在干什么？我已经运行它输出了一些示例值；看起来随着它的 k1 参数递增，它会以几乎随机的顺序输出2的幂的和。kInd 的小变化会导致 fft 得到完全错误的结果。

谢谢！

（注意：如果更多代码会有帮助，请告诉我。为了读者的缘故，尽量保持简短！）

答案＃1

这实现了FFT算法的蝶形操作。

例如，跑步...

console.log([0,1,2,3,4,5,6,7].map(i => kInd(i, 3)))

...打印...

[ 0, 4, 2, 6, 1, 5, 3, 7 ]

... 这是图中所示的映射：

http://www.alwayslearn.com/DFT%20and%20FFT%20Tutorial/DFTandFFT_FFT_Butterfly_8_Input.html

答案＃2

看起来像某种重新排序。

let kInd = (k1, pow) =>{
  let k2 = 0;
  let k3 = 0;

  for (let i = 0; i < pow; i++) {
    k3 = k1 >> 1;
    k2 = 2 * (k2 - k3) + k1;
    k1 = k3;
  }
  return k2;
};

const format = (s, p = 5) => s.toString().padStart(p);

var i,
    l = 16,
    pow = Math.log2(l);
    
for (i = 0; i < l; i++) {
    document.getElementById('out').innerHTML += `${format(i)} ${format(kInd(i, pow))}<br>`;
}

<pre id="out"></pre>