Здраствуйте! В основном я занимаюсь алгоритмизацией и редко сталкиваюсь с математикой вплотную. Но тут ситуация следующая... Начал работать с мультимедиа и постоянно сталкиваюсь с преобразованиями фурье, которое просто необходимо, допустим, для качественного ресемплинга. Фурье в чистом виде я вроде понимаю ("математический резонанс частотной составляющей или как-то так"), но быстрое преобразование фурье, которе собственно и применяется в вычислительных системах не понимаю совсем. В математических статьях говориться чуть ли не на "марсианском" языке терминологии и "голых" формул. Уважаемые Профи... Объясните на языке чайников что даёт fft, с чем его едят, и как его юзать.

ЗЫ : Я не использую "голые" формулы, тк очень сложно алгоритмизировать и оптимизировать такие формулы даже без понятия их происхождения и назначения.

>что даёт fft
по сравнению с обычным, не быстрым Фурье - значительное ускорение

http://algolist.ru/maths/fft.php
не сказать, что "на языке чайников", но практически все нужные выкладки приведены.

Есть ( мы говорим о преобразовании Фурье ) два математических преобразования между частотным и временным доменами.

Прямое преобразование Фурье (ППФ) переводит сигнал, выраженный через амплитудно-временное описание в эквивалентную форму, выраженную через амплитудно-частотное описание.

Надо понимать, что обратное ПФ (ОПФ ) делает обратное.

Есть математические аналоги таких преобразований, трансформированные в дискретные время/частоту.
Они известны как дискретные ППФ ( ДППФ ) и ДОПФ.

Есть алгоритмические разновидности ДППФ и ДОПФ, такие как "быстрые" преобразования.
Основаны они на тех или иных ускоренных алгоритмах:
- числовое основание (двойка, простые числа, числа Мерсена, etc);
- блочность;
- "матричность" ( Винограда )
- ограниченность частот ( синус-косинусное, Гертцеля,...)
и т.д.

Огромное спасибо! Оссобенно Сергей М. :)

> notHaker   (25.01.10 19:50) [4]


Да не за что - все равно разбираться тебе :)

> , допустим, для качественного ресемплинга.

Качественно как-раз делают не через Фурье.


> бственно и применяется в вычислительных системах не понимаю
> совсем. В математических статьях говориться чуть ли не на
> "марсианском" языке терминологии и "голых" формул. Уважаемые
> Профи... Объясните на языке чайников что даёт fft, с чем
> его едят, и как его юзать.

FFT = БПФ = Быстрое преобразование Фурье.
Класс алгоритмов для ускорения расчетов преобразования Фурье.

Если в двух словах. То для расчета коэффициентов Фурье нам надо для каждой частоты посчитать интеграл в комплексных переменных.  Так как синус и косинус периодические сигналы то ясно что в таком случае мы будем делать повторяющие операции. Идея заключается в группировки таких преобразований. Чтобы стало понятно возьми 16 чисел и распиши как ты их множишь. Верхняя строчка для одной частоты нижняя для другой потом обведи похожие комбинации разными цветами.

Было разработано множество алгоритмов. Наиболее известный  Cooley-Tukey для чисел 2^N. Есть алгоритмы для любого N; Для простых чисел; Для основания 3 и 5.

Основное отличие БПФ от простого интегрирования заключается в том что сложность работы БПФ O(N*Log(N)) против O(N^2) элементарных операций. Если у нас N=1024
То имеем  10240 против 1048576. Твоя программа будет работать не час а всего несколько секунд. БПФ лучше взять готовый он все равно будет работать быстрее чем тот который ты сейчас сможешь написать. Причем раз в 20 точно, а то и в 50.

Что бы применять БПФ надо знать его свойства. Так что бегом за учебником математики(понадобиться много учебников) и учи его свойства. Учти что свойства БПФ так как оно является дискретным(ДПФ) отличаются от свойств непрерывного преобразования Фурье.

БПФ применяю в двух основных случаях это для анализа и для оптимизации по скорости.  Часть задач если свести их к ПФ можно вычислить быстрее так как для Фурье уже построены полиномальные алгоритмы - БПФ.

Спасибо Pavia. А если насчёт ресемплинга, то какой метод применяют с точки зрения математики?

Децимация, интерполяция, дробная децимация
decimation, interpolation, fractional decimation

Достаточно подробно:
1. P.P. VAIDYANATHAN - Multirate filters
2. Гольденберг, Матюшкин, Поляк - Цифровая обработка сигналов, 1990
главы 7 ( интерполяция ) и 8 ( децимация )