Знак и множитель в FFT в различных программах

Сведем путаницу в знаках в одну таблицу

Формулировка преобразования Фурье всегда содержит в себе две вольности: это знак (+/−) в экспоненте и выбор множителей перед прямым и обратным преобразованием. В прямом и обратном преобразованиях знаки должны быть противоположными, а произведение множителей в прямом и обратном преобразованиях должно дать 1/N, где N — число точек в массиве.

Вот один из примеров задания прямого и обратного преобразований Фурье:

 
Прямое преобразование

Обратное преобразование

В различных книгах по обработке сигналов и в различных программах используются разные множители и знаки. Попробуем свести все воедино.

На что влияет знак?

Знак в экспоненте сказывается на результате лишь в том случае, когда преобразуемый сигнал — комплексный (то есть не чисто вещественный или мнимый). В этом случае смена знака ведет к смене знака частоты в спектре на противоположный. Спектр отражается слева-направо. Это равносильно "смене местами" вещественной и мнимой частей сигнала. Если сигнал чисто вещественный, его спектр и без того симметричен, и смена знака не сказывается.

На что влияет множитель?

Очевидно, множитель при прямом преобразовании влияет на получаемую амплитуду спектра. Для того, чтобы задав синус с единичной амплитудой получить единичную амплитуду на спектре, нужно задать правильный множитель. Правильные множители такие: если сигнал комплексный, то нужен множитель 1/N, а если чисто вещественный или чисто мнимый, то есть спектр получается симметричный, и нужен множитель 2/N (и рассматривать надо только половину спектра).

Таблица

 

Прямое
знак, множ.

Обратное
знак, множ.
Ссылка
Numerical
Receipts in C1
+
−, 1/N

nrbook.com
p. 503

Matlab
+
−, 1/N
Справка
Matlab

Origin ≤52
−, опция 2/N
(1/N для k=0)
+

Origin ≥7
−/+, опция 2/N
(1/N для k=0)
+/-
Справка
Origin 8

SciDAVis,
QTiPlot

−, Normalize3+

Опытно.
Тут приведена
странная формула

MagicPlot ≥1.3
−/+, опция 1/N
+/−, опция N
Справка
MagicPlot

А. Б. Сергиенко
Цифр. обр. сигн.
+, 1/Nc. 251 в 1 изд.

Примечания

1. Алгоритмы, описанные в книге, считаются практически стандартном в отрасли. Многие программы имеют ссылки на книгу в справке.

2. Не смотря на старость, Origin 5 по-прежнему широко распространен и используется.

3. В SciDAVis/QTiPlot и Origin есть опция с одинаковым названием Normalize. В Ориджине она задает деление на N, а в SciDAVis — нормализацию амплитуды на 1. Можно спутать.

Принимаются дополнения и замечания.

БПФ — не обязательно степень двойки!

Если считать преобразование Фурье "в лоб", то нужно произвести N2 действий, что очень долго. В шестидесятых годах были изобретены алгоритмы быстрого преобразования Фурье (БПФ, FFT), число необходимых действий для которых имеет порядок N*log(N). Наиболее известный алгоритм — алгоритм Cooley-Tukey требует, чтобы длина массива была равна степени двойки. Поскольку в многих книгах разговор дальше этого алгоритма не заходи, существует заблуждение, что для того, чтобы считать преобразование Фурье быстро, нужно, чтобы длина массива обязательно равнялась степени двойки. Это не так. Кроме алгоритма Cooley-Tukey существуют и другие алгоритмы (Bluestein), правильное применение которых позволяет вычислять преобразование Фурье для массива произвольной длины затрачивая количество операций N*log(N) (хотя для произвольной длины вычисления будут идти дольше, чем для степени двойки, но не на порядки). Например, на Си, Фортране и Java существует бесплатная (public domain) библиотека FFTPACK, в которой реализованы эти алгоритмы: БПФ для массива произвольной длины.


Electriq Thursday 14 October 2010 at 12:07 pm | | Russian
Used tags: ,

No comments

(optional field)
(optional field)
Remember personal info?
Small print: All html tags except <b> and <i> will be removed from your comment. You can make links by just typing the url or mail-address.