Фаза переупорядочения FFT

Question

У меня есть код для вас, ребята. Это первый шаг алгоритма расщепления для быстрого преобразования Фурье.

Что должен сделать алгоритм, так это переупорядочить массив таким образом, чтобы каждый элемент на входе был смещен в «двоичном зеркальном» положении вывода.

Например, элемент Х [4] будет находиться в положении X [1], так как зеркальная представление 100 001.

До здесь все понятно. Однако алгоритм, который выполняет такое переупорядочение, не является. По крайней мере, я с трудом понимаю.

Что делает вторая внутренняя петля?

// N is the length of the array 
// p is the number of bits needed to represent the index 

for(int n=0; n<N; n++) { 

    int j=0; 
    int m=n; 
    for(int i=0; i<p; i++) { 
    j = 2∗j + m%2; m = m/2; 
    } 

    if (j>n) { 
    complex<double> h; 
    h = X[j]; 
    X[j] = X[n]; 
    X[n] = h; 
    } 

} 

Answer 1

Подумайте, что целое число является последовательностью бит.

• j = 2j это выталкивает немного слева и толкает ноль в правую
• m % 2 это получает правильный бит
• m = m/2 выскакивает бит справа и толкает копию левого бита слева
• j + x устанавливает крайний правый бит j в x, при условии, что бит в настоящее время равна нулю и что x является 0 или 1

поэтому все это делается, выбирая биты справа от m и нажимая их справа от j.

Answer 2

Каждая итерация, умножаем j на 2 (который является таким же, как сворачивает налево на 1), а затем добавить четность m. Затем мы делаем целочисленное деление m на два (это то же самое, что смещение справа на 1). m начинается со значения n. Таким образом, мы по существу реверсируем бит в n и сохраняем его в j.