Odd function used for signal processing?

Question

Ηello! I hope this is an acceptable sort of question.

Going through some code used for signal processing I came upon an odd function:

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;

};

This function is called towards the end of a fourier transform calculation to swap indexes in the real+imaginary pair of arrays:

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

};

My question is: what the heck is kInd doing? I've run it to output some example values; it looks like it outputs sums of powers of 2 in a nearly random order as its k1 parameter increments. Small changes to kInd lead to completely wrong results from fft.

Thanks!

(Note: let me know if more code would help. Trying to keep this as brief as possible for the reader's sake!)

user_44615 · Answer

This implements the butterfly operation of the FFT algorithm.

For example, running...

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

...prints...

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

... which is the mapping in the diagram here:

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

user_1447675 · Answer

It looks like some kind of reordering.

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))}
`;
}

user_1092820 · Answer

For any given pow, feeding in an incrementing i produces a cycle of ks. The cycle's length is 2^pow The code below will show two cycles over an increasing i for each pow. What's interesting is the pattern of is that result in ks that are greater than or equal to i (shown in bold in the output below).

For each pow, what's the pattern of k(i) >= i starting with i=0:

Pow 0: TFFF...

Pow 1: TTFFF...

Pow 2: TTFTFTFFF...

Pow 3: TTTTFTFTFFF...

Pow 4: TTTTFTTTFTFTFFFTFFF...

Pow 5: TTTTTTTTFTTTFTTTFTFTFTFTFFFTFFFTFFF...

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;
};

for (let p = 0; p < 7; p++) {
  for (let i = 0; i < Math.pow(2, p) * 2; i++) {
    let k = kInd(i, p)
    if (k >= i) {
      $('#output').append("" + i + "   " + p + "->" + k + "");
    } else {
      $('#output').append("" + i + "   " + p + "->" + k + "");
    }
  }
  $('#output').append("----------------");
}

I know this isn't an answer but I wanted to help and a comment wasn't suitable for the formatting I wanted to put here.

Odd function used for signal processing?

3 Answers