Участник:Victoria Stepanischeva/Быстрое преобразование Фурье (FFT)

2016-10-15T19:14:44Z

Victoria Stepanischeva: /* Свойства и структура алгоритма [DRAFT] */

Авторы: [[Участник:Victoria_Stepanischeva|Степанищева В.С.]],
[[Участник:Igor_Munkin|Мунькин И.А.]]

{{algorithm
| name = Быстрое преобразования Фурье
| serial_complexity = <math>O(n \; log \, n)</math>
| input_data = <math>n</math>
| output_data = <math>n</math>
| pf_height = <math>O(log \,n)</math>
| pf_width = <math>O(n)</math>
}}

==Свойства и структура алгоритма [DRAFT]==

===Общее описание алгоритма [DRAFT]===

Алгоритм '''быстрого преобразования Фурье''', включая его рекурсивную
реализацию, был использован
[https://en.wikipedia.org/wiki/Carl_Friedrich_Gauss Карлом Фридрихом Гауссом]
еще в 1805 году для интерполяции траекторий астероидов, однако эта работа не
получила широкого признания. Алгоритм быстрого преобразования Фурье обрел свою
популярность благодаря работе
[https://en.wikipedia.org/wiki/James_Cooley James Cooley], работающего в то
время в [https://en.wikipedia.org/wiki/IBM IBM], и
[https://en.wikipedia.org/wiki/John_Tukey John Tukey], параллельно принимающего
участие в разработках [https://en.wikipedia.org/wiki/Bell_Labs Bell Labs] и
работающего в
[https://en.wikipedia.org/wiki/Princeton_University Принстонском университетe].
В их статье, изданной в 1965 году, они представили подробное описание алгоритма
и его программной реализации.

====Разновидности алгоритма быстрого преобразования Фурье [DRAFT]====
Помимо традиционного алгоритма
[https://en.wikipedia.org/wiki/Cooley%E2%80%93Tukey_FFT_algorithm Cooley-Tukey]
существует также несколько других часто используемых реализаций алгоритма
быстрого преобразования Фурье.

=====PFA-алгоритм [REVIEW]=====
Алгоритм [https://en.wikipedia.org/wiki/Prime-factor_FFT_algorithm prime-factor]
(PFA), также называемый алгоритмом Good-Thomas, представляет собой алгоритм
быстрого преобразования Фурье, который представляет дискретное преобразование
Фурье размера <math>N = N_1\,N_2</math> в виде двумерного
<math>N_1 \times N_2</math> дискретного преобразования Фурье, при условии, что
<math>N_1</math> и <math>N_2</math> - взаимно простые числа. Представленные
преобразования меньшего размера могут быть вычислены либо рекурсивным
применением PFA либо используя какой-либо иной метод быстрого преобразования
Фурье.

=====Алгоритм Bluestein [DRAFT]=====
Алгоритм
[https://en.wikipedia.org/wiki/Chirp_Z-transform#Bluestein.27s_algorithm Bluestein],
обычно называемый <math>\mathcal{Z}</math>-чирп алгоритмом, представляет собой
алгоритм быстрого преобразования Фурье, который вычисляет дискретное
преобразование Фурье различных размеров с помощью представления оного в виде
линейной свертки. Другой алгоритм быстрого преобразования Фурье, использующий
свойства простых чисел, алгоритм
[https://en.wikipedia.org/wiki/Rader%27s_FFT_algorithm Rader], также вычисляет
дискретное преобразование Фурье в виде свертки.

====Приложения быстрого преобразования Фурье [DRAFT]====

Алгоритм быстрого преобразования Фурье имеет множество областей приложения, а
именно:
* Обработка изображений
* Цифровое сжатие
* Численное интегрирование
* Быстрые методы решения уравнения Пуассона
* Спектральные методы решения обыкновенных дифференциальных уравнений

Остановимся на некоторых из них подробнее

=====Обработка изображений [DONE]=====
Все фильтры делят на две группы: пространственные и частотные. Типов
пространственных фильтров достаточно много: линейные, медианные, изотропные и
др. Процесс фильтрации в этих фильтрах основан на простом применении маски
фильтра ко всем точкам изображения. В каждой точке отклик фильтра вычисляется с
использованием предварительно заданных связей. Все пространственные фильтры
имеют линейную трудоемкость.

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

Простота фильтрации в частотной области заключается в простой интерпретации
частот:
* низкие частоты - плавное изменение яркости изображения
* высокие частоты - быстрое изменение яркости изображения (границы объектов)
За счет изменения значений определенных частот можно добиться размытия
изображения, повышение резкости и др.

=====Цифровое сжатие [REVIEW]=====
Одним из первых форматов файла-контейнера для хранения записи оцифрованного
аудипотока является формат WAV. Этот формат чаще всего используется в качестве
оболочки для несжатого звука. При таком кодировании в WAV-файле хранится полная
информация об исходном звуке, оцифрованном и проквантованном с некоторой
частотой, например 44 кГц. Этой информации абсолютно достаточно для
воспроизведения всех частот исходного сигнала, меньших половины частоты
квантования (по [https://ru.wikipedia.org/wiki/%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%9A%D0%BE%D1%82%D0%B5%D0%BB%D1%8C%D0%BD%D0%B8%D0%BA%D0%BE%D0%B2%D0%B0 теореме Котельникова] ). При этом одна
минута записи занимает около 15 Мб, поэтому в настоящее время очень популярным
стал формат кодирования MPEG Layer-3 со сжатием.

При сжатии кодеком MPEG Layer-3 исходный звуковой сигнал разбивается на
фрагменты, длительностью по 50 миллисекунд, каждый из которых анализируется
отдельно. При анализе фрагмент раскладывается на гармоники по методу Фурье, из
которых в соответствии с теорией восприятия звука человеческим ухом
выбрасываются те гармоники, которые человек хуже воспринимает на фоне остальных:
* более тихие гармоники на фоне более громких
* звуки, замаскированные вследствие инертности слуха (так, например, если за очень громким хлопком, с задержкой в долю секунды, пойдет какой-то иной кратковременный сигнал, то его слышно не будет)

При воспроизведении файла закодированного MPEG Layer-3 производится обратное
преобразование, при котором оставшиеся гармоники вновь преобразуются в звуковую
волну. Поскольку часть информации об исходном сигнале была удалена, звук
получается не совпадающий с исходным. Одной из основных характеристик качества
аудио потока является битрейт.

''Битрейт'' - это объем информации на каждую секунду записи:
* чем он меньше, тем меньший размер имеют файлы с одинаковой по времени длине
* чем он меньше, тем большее количество "лишних" гармоник приходится удалять

===Математическое описание алгоритма [DRAFT]===
Пусть задан вектор действительных чисел
<math>\left(f_1, f_2, f_3, \dots, f_{N-1} \right)</math>

Дискретное преобразование Фурье определено следующим образом

<math>
F_k = \sum_{n = 0}^{N - 1}\, f_n\, e^{\left(\frac{i2\pi kn}{N}\right)}
</math>

Обозначим <math>W_N = e^{\left(\frac{i2\pi}{N}\right)}</math> - <math>N</math>-ый
корень единицы. Таким образом <math>(W_N)^N = 1</math>. Несложные математические
преобразования приводят формулу дискретного преобразования Фурье к следующему
виду

<math>
F_k = \sum_{n = 0}^{N - 1}\, f_n\, W_n^{-nk}
</math>

Таким образом, алгоритм вычисления дискретного преобразования Фурье состоит из
2 шагов:
# Вычисление поворотных коэффициентов <math>W_n^{-nk},\; n,k = 0, 1, \dots, N-1</math>
# Вычисление коэффициентов Фурье <math>F_k,\; k = 0, 1, \dots, N-1</math>

Идея быстрого преобразования Фурье:

<math>
F_k = \sum_{n = 0}^{N - 1}\, f_n\, W_{N}^{-nk}
= \sum_{n = 0}^{N/2 - 1}\, g_n\, W_{N/2}^{-nk}
+ \sum_{n = 0}^{N/2 - 1}\, h_n\, W_{N/2}^{-nk}
</math>

Таким образом четные и нечетные коэффициенты Фурье могут быть записаны в
следующем виде:

<math>
F_{2k} = \sum_{n = 0}^{N/2 - 1}\, \underbrace{
\left(f_n + f_{n + N/2}\right)
}_{g_n} \, W_{N/2}^{-nk}
</math>

<math>
F_{2k+1} = \sum_{n = 0}^{N/2 - 1}\, \underbrace{
\left((f_n + f_{n + N/2}) W^{-n}\right)
}_{h_n} \, W_{N/2}^{-nk}
</math>

Таким образом, вычисление дискретного преобразования Фурье от <math>N</math>
коэффициентов сводится к вычислению 2 дискретных преобразований Фурье от
<math>N/2</math> коэффициентов. Применяя данную идею рекурсивно, получаем
алгоритм быстрого преобразования Фурье.

===Вычислительное ядро алгоритма [DRAFT]===
[[File:Stepmoon_buttefly.png|200px]]

===Макроструктура алгоритма [DRAFT]===
Описываемый алгоритм работает по принципу
[https://en.wikipedia.org/wiki/Divide_and_conquer_algorithms "разделяй и властвуй"]
# Исходное множество точек разбивается на два равных подмножества
# Над каждым из полученных множеств выполняется быстрое преобразование Фурье. Для его вычисления над каждым из подмножеств снова выполняется деление на 2 равные части. Такое разбиение продолжается до тех пор, пока количество элементов, над которыми необходимо выполнить ДПФ, не будет равно одному.
# После этого выполняется объединение всех промежуточных результатов. Полученные на предыдущем шаге множества объединяются за линейное время.

Ниже представлена схема алгоритма Cooley-Tukey для <math>N = 2^M</math>

[[File:Stepmoon_macro.png|center|800px]]

Обработку подмножеств, получаемых после разбиения можно выполнять независимо,
этот факт будет использован в дальнейшем при реализации параллельной версии.

===Схема реализации последовательного алгоритма [DONE]===
Ниже представлен прототип реализации для <math>N = 2^M</math>.
<source lang=perl>
use Math::Complex;

sub fft {
my $input = shift;
return $input if @{ $input } == 1;
my @w = map {
my $theta = 2 * pi * $_ / @{ $input };
Math::Complex->make(cos($theta), sin($theta));
} (0 .. $#input);
my $odd = fft([ map { $input->[2 * $_ + 1] }, (0 .. $#input / 2) ]);
my $even = fft([ map { $input->[2 * $_] }, (0 .. $#input / 2) ]);
return [ map {
$even->[$_ % @{ $even }] + $w[$_] * $odd->[$_ % @{ $odd }];
} (0 .. $#input) ];
};
</source>

===Последовательная сложность алгоритма [TODO]===

===Информационный граф [TODO]===

===Ресурс параллелизма алгоритма [DONE]===
Простой алгоритм Cooley-Tukey имеет критический путь, состоящий из
<math>log\, n</math> операций сложения и вычитания и <math>log\, n</math>
операций комплексного умножения (основание логарифма зависит от выбранного на
каждом шаге алгоритма разбиения). Следовательно, простой алгоритм быстрого
преобразования Фурье в общем случае может быть отнесен к логарифмическому классу
по параллельной сложности.

===Входные и выходные данные алгоритма [TODO]===

===Свойства алгоритма [TODO]===

==Программная реализация алгоритма [REVIEW]==

===Существующие реализации алгоритма [REVIEW]===
Наиболее популярной библиотекой, содержащей реализацию быстрого преобразования
Фурье, является [http://fftw.org/ FFTW], изначально разработанная сотрудниками
[https://en.wikipedia.org/wiki/Massachusetts_Institute_of_Technology MIT]
Matteo Frigo и Steven G. Johnson. На сегодняшний день исходный код библиотеки
распространяется под свободной лицензией
[https://en.wikipedia.org/wiki/GNU_General_Public_License#Version_2 GNU General Public Licence v2]
с помощью сервиса [https://github.com/FFTW/fftw3 Github], тем самым давая
возможность сообществу принимать участие в разработке. Несмотря на то, что сама
библиотека [http://fftw.org/faq/section2.html#whynotfortran написана на языке C]
существуют интерфейсы для работы с ней используя такие языки программирования
как Fortran, C++ и другиe.

Для разбиения преобразований, размеры которых являются составным числом, на
меньшие используется одна из многочисленных реализаций алгоритма
[https://en.wikipedia.org/wiki/Cooley%E2%80%93Tukey_FFT_algorithm Cooley-Tukey]
(в зависимости от разложения на простые множители и паттернов доступа к памяти).
В свою очередь для преобразований, размеры которых являются простыми числом
используется либо алгоритм
[https://en.wikipedia.org/wiki/Rader%27s_FFT_algorithm Raider], либо алгоритм
[https://en.wikipedia.org/wiki/Chirp_Z-transform#Bluestein.27s_algorithm Bluestein].
Библиотека признана самой быстрой реализацией быстрого преобразования Фурье,
гарантируя на любых объемах входных данных сложность
<math>O \left(n\; log\, n \right)</math>. Существует реализация FFTW и с
поддержкой [https://en.wikipedia.org/wiki/Message_Passing_Interface MPI],
позволяющая работать с данными не помещающимися в память. Однако перегруппировка
данных приводит к оверхеду, которого трудно избежать при in-place вычислении
преобразований различных размеров.

==Литература==
[2] L. Rabiner, B. Gold, ''"Theory and application of digital signal processing"'' // Prentice Hall, New Jersey, 1975.

Обсуждение участника:Lineprinter

2016-10-12T06:16:43Z

Victoria Stepanischeva: /* Перенос */

== Перенос ==

Статья: algowiki-project.org/ru/Решение_задачи_Коши_для_системы_ОДУ_методом_Рунге-Кутты_4_порядка;
Выполняют: Алимов Дамир и Антон Лесничий

Статья: Алгоритм кластеризации, основанный на минимальном остовном дереве;
Выполняет: Стандрик Антон Сергеевич (Astandrik)

Статья: [[Нахождение_собственных_чисел_квадратной_матрицы_методом_QR_разложения_(3)|Нахождение собственных чисел квадратной матрицы методом QR разложения (3)]];
Выполняют: [[Участник:Смирнова_Александра|Смирнова А.С.]], [[Участник:Александра_Киямова|Киямова А.]]

Статья: [[Метод_Якоби_вычисления_сингулярных_чисел_и_векторов]];
Выполняют: [[Участница:Почернина_Елена| Почернина Елена]] и [[Участница:Светлана|Костюкова Светлана]]

Статья: [[Метод_Ньютона_для_решения_систем_нелинейных_уравнений(2)]];
Выполняют: [[Участник:Oleggium|Гирняк О.Р.]], [[Участник:Dimx19|Васильков Д.А.]]

Статья: [[Алгоритм_кластеризации_с_использованием_представлений]];
Выполняют: [[Участник:Cookie|Шатков С.А.]], [[Антохина Ю.А.]]

Статья: [[Быстрое_преобразование_Фурье_(FFT)|Быстрое преобразование Фурье (FFT)]];
Выполняют: [[Участник:Victoria_Stepanischeva|Степанищева Виктория]] и [[Участник:Igor_Munkin|Мунькин Игорь]]

Участник:Victoria Stepanischeva

2016-10-12T06:16:21Z

Victoria Stepanischeva: Новая страница: «Студентка ВМК МГУ, группа 601.»

Студентка ВМК МГУ, группа 601.

Алговики - Вклад [ru]

Участник:Victoria Stepanischeva/Быстрое преобразование Фурье (FFT)

Обсуждение участника:Lineprinter

Участник:Victoria Stepanischeva