KissFFT и Power of Two

Question

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

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

Answer 1

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

• Во-первых, Кули и Тьюки алгоритм link

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

Спасибо всем

Answer 2

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

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

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