Цитата(Moks @ Oct 3 2006, 18:59)
Извините, а полее подробно и понятно метод "бабочки" растолковать не может? Теория - это хорошо, но от неё мозги опухают. На Си кто-нибудь его делал сам, без использования чьих-то исходников, следуя только требованиям математики, переложенных на язык Си, например?
Помогите, пожалуйста. ссылки, указанные в теме, почитал, но ясности не так уж много стало ...
Так. Дискретное Преобразование Фурье (ДПФ) чисто арифметически является к умножением вектора на матрицу. Но эта матрица имеет настолько специфический вид, что её можно представить как произведение нескольких
сильно разреженных матриц. С формальной точки зрения это ничего не даёт, но с вычислительной - можно поднапрячься и исключить операции с нулевыми значениями в этих матрицах. Это, собственно, суть БПФ - количество операций оказывается существенно меньше, чем при "честном" матричном умножении. Ещё раз - тут используются особенности данной матрицы, в общем случае такой трюк невозможен.
Далее начинается реализация. Вместо записи выражения в матричной форме, которая подразумевает полное формальное умножение,
рисуют граф - кто с кем складывается и с каким коэффицинтом. Если пойти по шагам, то получится что-то вроде V*M1*M2*...Mn->V|G1|*M2*...Mn->...V|G1|G2|..|Gn|. На каждом шаге умножение на матрицу заменяют графом со стрелочками, показывающими какие конкретно элементы и как складываются. При этом оказывается, что элементы всех векторов-результатов - и промежуточных и окончательного - получаются суммой двух слагаемых, т.е. суммой двух значений из предыдущего вектора с коэффициентами. Более того, можно так переставить матрицы, что значения будут получаться "два из двух", т.е. два значения из предыдущего вектора определяют два значения последуюшего. Если выделить на графе этот момент, то четыре линии будут отдалённо напоминать бабочку (отсюда и название). Таким вот образом, ДПФ сводят к выполнению двух операций - бабочки и перестановки индексов, которая подставляет бабочке значения в нужном порядке.
P.S. Не поленись, проделай это на бумаге для матрицы преобразования 8*8 и всё сразу станет на свои места.
FFT, Практическая реализация
Mar 22 2005, 15:48
