Уровень алгоритма

Быстрое дискретное преобразование Фурье (БПФ): различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
[непроверенная версия][непроверенная версия]
Строка 34: Строка 34:
 
где матрица <math>A = \{e^{-\frac{2\pi i}{N}(i - 1)(j - 1)}\}_{i,j=1}^{N}</math>
 
где матрица <math>A = \{e^{-\frac{2\pi i}{N}(i - 1)(j - 1)}\}_{i,j=1}^{N}</math>
 
== Вычислительное ядро алгоритма ==
 
== Вычислительное ядро алгоритма ==
Пусть, для простоты <math> N = km</math>, тогда рекурсивная реализация преобразования Фурье, за счет <math>O(N{k})</math> уровней рекурсии, имеет суммарную сложность <math>O(Nk + Nm + km) = O(N(k + m))</math>. В случае, например <math>N = 2^n</math> сложность БПФ составляет <math>O(N\log{N})</math>.
+
Пусть, для простоты <math> N = km</math>, тогда рекурсивная реализация преобразования Фурье, за счет <math>O(N{k})</math> уровней рекурсии, имеет суммарную сложность <math>O(Nk + Nm + km) = O(N(k + m))</math>.  
 +
 
 +
В случае, например <math>N = 2^n</math> сложность БПФ составляет <math>O(N\log{N})</math>.
 +
 
 +
В общем же случае, когда <math>N = \prod_{i=1}^np_i</math> сложность БПФ составляет <math> O(N(\sum_{i=1}^np_i))</math>.
  
 
== Макроструктура алгоритма ==
 
== Макроструктура алгоритма ==

Версия 14:57, 14 октября 2016

Авторы: Чачба А.Н., Костоев Р.С.



Быстрое преобразование Фурье (БПФ)
Последовательный алгоритм
Последовательная сложность [math]O(N \log N)[/math]
Объём входных данных [math]N[/math]
Объём выходных данных [math]N[/math]
Параллельный алгоритм
Высота ярусно-параллельной формы [math]O(\log N)[/math]
Ширина ярусно-параллельной формы [math]O(N)[/math]


1 ЧАСТЬ. Свойства и структура алгоритмов

1.1 Общее описание алгоритма

Преобразование Фурье - взаимно однозначное отображение одной функции вещественной, называемой таргетным сигналом, с другой функцией вещественной переменной, называемой образом Фурье или спектром исходной функции по формуле:

[math] \hat{f}(\omega)=\frac{1}{\sqrt{2\pi}}\int\limits_{-\infty}^{\infty}f(x)e^{-ix\omega}\,dx [/math]

Дискретное преобразование Фурье, в свою очередь, если аналог непрерывного преобразования Фурье, но для дискретного сигнала содержащего [math]N[/math] отсчетов. Широко применяет в цифровой обработке сигналов, теории вероятностей, криптографии и акустике. Преобразование Фурье обратимо, причем обратное преобразование имеет практически ту же форму, что и прямое. Преобразование Фурье имеет сложность [math]O(N^2)[/math], но существует быстрый вариант преобразование Фурье со сложностью [math]O(N\log{N})[/math].

1.2 Математическое описание алгоритма

Пусть исходный сигнал имеет значения [math]x_n,\quad n = 0,\dots,N-1[/math], тогда дискретное прямое преобразование Фурье (ДПФ) имеет вид:

[math] X_k = \sum_{n=0}^{N-1}x_ne^{-\frac{2\pi i}{N}kn},\quad k = 0, \dots, N-1 [/math]

Обозначим [math] \varepsilon_{N} = e^{-\frac{2\pi i}{N}}[/math], тогда ДПФ можно перезаписать в матричной форме:

[math] \bar X = A\bar x [/math]

где матрица [math]A = \{e^{-\frac{2\pi i}{N}(i - 1)(j - 1)}\}_{i,j=1}^{N}[/math]

1.3 Вычислительное ядро алгоритма

Пусть, для простоты [math] N = km[/math], тогда рекурсивная реализация преобразования Фурье, за счет [math]O(N{k})[/math] уровней рекурсии, имеет суммарную сложность [math]O(Nk + Nm + km) = O(N(k + m))[/math].

В случае, например [math]N = 2^n[/math] сложность БПФ составляет [math]O(N\log{N})[/math].

В общем же случае, когда [math]N = \prod_{i=1}^np_i[/math] сложность БПФ составляет [math] O(N(\sum_{i=1}^np_i))[/math].

1.4 Макроструктура алгоритма

1.5 Схема реализации последовательного алгоритма

Рекурсивный метод для случая [math]N = 2^k[/math], без оптимизации на C++:

#include <vector>
#include <complex>

using namespace std;

typedef complex<double> cd;
typedef vector<cd> vcd;

vcd fft(const vcd &as) { 
  int n = as.size();
  if (n == 1) return vcd(1, as[0]);

  vcd w(n); // Calculate roots
  for (int i = 0; i < n; i++) {
    double alpha = 2 * M_PI * i / n;
    w[i] = cd(cos(alpha), sin(alpha));
  }

  vcd A(n / 2), B(n / 2);
  for (int i = 0; i < n / 2; i++) {
    A[i] = as[i * 2];
    B[i] = as[i * 2 + 1];
  }
  vcd Av = fft(A);
  vcd Bv = fft(B);
  vcd res(n);
  for (int i = 0; i < n; i++)
    res[i] =   Av[i % (n / 2)] +
        w[i] * Bv[i % (n / 2)];
  return res;
}

1.6 Последовательная сложность алгоритма

1.7 Информационный граф

Рисунок 1. Информационный граф преобразования Кули-Тьюки для [math]N = km = 25, k = 5, m = 5[/math]. Желтые вершины - умножение на поворотные множители.

1.8 Ресурс параллелизма алгоритма

1.9 Входные и выходные данные алгоритма

1.10 Свойства алгоритма

2 ЧАСТЬ. Программная реализация алгоритма

2.1 Особенности реализации последовательного алгоритма

2.2 Локальность данных и вычислений

2.3 Возможные способы и особенности параллельной реализации алгоритма

2.4 Масштабируемость алгоритма и его реализации

2.5 Динамические характеристики и эффективность реализации алгоритма

2.6 Выводы для классов архитектур

2.7 Существующие реализации алгоритма

3 Литература