FFT, Практическая реализация Опции

[lexl]

Кто-нибудь может указать перстом, где просто и доступно объясняется БПФ с примерами кода?

[Moks]

Извините, а полее подробно и понятно метод "бабочки" растолковать не может? Теория - это хорошо, но от неё мозги опухают. На Си кто-нибудь его делал сам, без использования чьих-то исходников, следуя только требованиям математики, переложенных на язык Си, например?
Помогите, пожалуйста. ссылки, указанные в теме, почитал, но ясности не так уж много стало ...

[SasaTheProgramme...]

Извините, а полее подробно и понятно метод "бабочки" растолковать не может? Теория - это хорошо, но от неё мозги опухают. На Си кто-нибудь его делал сам, без использования чьих-то исходников, следуя только требованиям математики, переложенных на язык Си, например?
Помогите, пожалуйста. ссылки, указанные в теме, почитал, но ясности не так уж много стало ...

Так. Дискретное Преобразование Фурье (ДПФ) чисто арифметически является к умножением вектора на матрицу. Но эта матрица имеет настолько специфический вид, что её можно представить как произведение нескольких сильно разреженных матриц. С формальной точки зрения это ничего не даёт, но с вычислительной - можно поднапрячься и исключить операции с нулевыми значениями в этих матрицах. Это, собственно, суть БПФ - количество операций оказывается существенно меньше, чем при "честном" матричном умножении. Ещё раз - тут используются особенности данной матрицы, в общем случае такой трюк невозможен.
Далее начинается реализация. Вместо записи выражения в матричной форме, которая подразумевает полное формальное умножение, рисуют граф - кто с кем складывается и с каким коэффицинтом. Если пойти по шагам, то получится что-то вроде V*M1*M2*...Mn->V|G1|*M2*...Mn->...V|G1|G2|..|Gn|. На каждом шаге умножение на матрицу заменяют графом со стрелочками, показывающими какие конкретно элементы и как складываются. При этом оказывается, что элементы всех векторов-результатов - и промежуточных и окончательного - получаются суммой двух слагаемых, т.е. суммой двух значений из предыдущего вектора с коэффициентами. Более того, можно так переставить матрицы, что значения будут получаться "два из двух", т.е. два значения из предыдущего вектора определяют два значения последуюшего. Если выделить на графе этот момент, то четыре линии будут отдалённо напоминать бабочку (отсюда и название). Таким вот образом, ДПФ сводят к выполнению двух операций - бабочки и перестановки индексов, которая подставляет бабочке значения в нужном порядке.
P.S. Не поленись, проделай это на бумаге для матрицы преобразования 8*8 и всё сразу станет на свои места.

[DRUID3]

Извините, а полее подробно и понятно метод "бабочки" растолковать не может? Теория - это хорошо, но от неё мозги опухают. На Си кто-нибудь его делал сам, без использования чьих-то исходников, следуя только требованиям математики, переложенных на язык Си, например?
Помогите, пожалуйста. ссылки, указанные в теме, почитал, но ясности не так уж много стало ...

Так. Дискретное Преобразование Фурье (ДПФ) чисто арифметически является к умножением вектора на матрицу. Но эта матрица имеет настолько специфический вид, что её можно представить как произведение нескольких сильно разреженных матриц. С формальной точки зрения это ничего не даёт, но с вычислительной - можно поднапрячься и исключить операции с нулевыми значениями в этих матрицах. Это, собственно, суть БПФ - количество операций оказывается существенно меньше, чем при "честном" матричном умножении. Ещё раз - тут используются особенности данной матрицы, в общем случае такой трюк невозможен.
Далее начинается реализация. Вместо записи выражения в матричной форме, которая подразумевает полное формальное умножение, рисуют граф - кто с кем складывается и с каким коэффицинтом. Если пойти по шагам, то получится что-то вроде V*M1*M2*...Mn->V|G1|*M2*...Mn->...V|G1|G2|..|Gn|. На каждом шаге умножение на матрицу заменяют графом со стрелочками, показывающими какие конкретно элементы и как складываются. При этом оказывается, что элементы всех векторов-результатов - и промежуточных и окончательного - получаются суммой двух слагаемых, т.е. суммой двух значений из предыдущего вектора с коэффициентами. Более того, можно так переставить матрицы, что значения будут получаться "два из двух", т.е. два значения из предыдущего вектора определяют два значения последуюшего. Если выделить на графе этот момент, то четыре линии будут отдалённо напоминать бабочку (отсюда и название). Таким вот образом, ДПФ сводят к выполнению двух операций - бабочки и перестановки индексов, которая подставляет бабочке значения в нужном порядке.
P.S. Не поленись, проделай это на бумаге для матрицы преобразования 8*8 и всё сразу станет на свои места.

Позвольте все же заметить, что

a) в общем случае никаких "0"-ых значений в матице преобразования не предполагается, и суть БПФ совсем не в них. Суть в повторяющихся коэффициентах (симметрия и периодичность) арифметические операции с которыми достаточно выполнить только однажды, вот эта избыточность и устраняется.
Кстати, надо заметить, именно поэтому БПФ нельзя делать для части (или одной) точек последовательности, алгоритм работает только со всей последовательностью. Если же надо выделить одну (или несколько в небольшом частотном интервале не начинающимся в "0" оси частот) то применять следует лишь ДПФ и будет это еще и быстрее чем БПФ с последующим отбросом ненужных спектральных компонент (причем основное время уйдет не на отброс )

Есть множество алгоритмов обходящихся без перестановки индексов. Вобщем и целом алгоритм БПФ сводится к 2-х (или 4-х) точечному ДПФ и алгоритму переразбиения массива входных данных на эти ДПФ.