KissFFT и Power of Two

Я читал во многих разных местах, что алгоритм БПФ должен иметь размер входного массива, равный степени двойки, например, 512 или 1024. Я также нашел множество различных алгоритмов, вычисляющих БПФ, таких как Кули-Таки и Блустейн. (это также работает с числами, которые следуют за простыми множителями, такими как 2,3,5,7).

Ну, я использую KissFFT и ввожу массив длиной 200. Почему это работает? Кто-нибудь знает, что происходит в этом случае? Это усекает размер до 128 (2 ^ 7) или, может быть, использует другой алгоритм? Если он использует другой алгоритм, дает ли он по-прежнему правильный ответ, но для вычисления требуется больше времени? (Время в данном случае для меня не проблема.)


algorithm fft kissfft
person Will    schedule 28.10.2014    source источник
comment
когда я некоторое время назад реализовывал БПФ, я изменял размер данных до 2 ^ n (и заполнял новые ячейки нулями), и это работало, поэтому его можно было реализовать таким образом.   -  person fex    schedule 28.10.2014

Ответы (2)


arrow_upward
0
arrow_downward

Наконец-то нашел полезную информацию, вот она:

  • Во-первых, алгоритм Кули и Тьюки 1.pdf" rel="nofollow">ссылка

  • Во-вторых, MATLAB: «Вы можете использовать nextpow2 для дополнения сигнала, который вы передаете в БПФ. Это может ускорить вычисление БПФ, когда длина сигнала не является точной степенью числа 2». ссылка

Спасибо вам всем

person Will    schedule 28.10.2014

arrow_upward
0
arrow_downward

Если вам абсолютно необходимо иметь БПФ с длиной, не равной степени двойки, есть по крайней мере два способа сделать это достаточно эффективно:

(1) Если длина, которую вы хотите, является произведением небольших чисел, вы можете обобщить метод, используемый, когда длина является точной степенью двойки.

(2) На самом деле вы можете построить БПФ произвольной длины из сверток, выполненных с векторами, которые длиннее этой произвольной длины, и эти более длинные векторы могут иметь длину, равную степени двойки, что означает, что вы можете выполнять БПФ с помощью сверток по мощности. из двух БПФ. См., например, http://www.engineeringproductivitytools.com/stuff/T0001/PT11.HTM< /а>. Это использует тождество, что AB = (AB) ^ 2 - A ^ 2 - B ^ 2. Вы хотите получить сумму членов, которая немного похожа на f(Xi) exp(ij). Используя свертку, вы можете комбинировать что-то, что немного похоже на f(Xi)exp(-i^2) с exp((ij)^2), так что показатели степени складываются, давая вам exp(-2ij+j^2), и вы можете снимите j ^ 2 в постобработке - в справочнике показано, как это сделать правильно, поэтому показатели степени, конечно, на самом деле правильные.

person mcdowella    schedule 28.10.2014