Преобразование Фурье в цифровой информации

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

который может быть представлен в виде графика:


Рис.11. Разложение ДПФ на четные и нечетные отсчеты.

Обратите внимание, что элементы:

можно вычислить таким же образом: элементы x (0), x (4), x (1) и x (5) являются в своих диаграммах четными индексами, тогда как x (2), x (6), x (3) и x (7) являются нечетными. Объединив их в упорядоченные пары, приведенные выше графики можно перерисовать:

Рис.12. Быстрое преобразование Фурье (RADIX-2) для сигнала N = 8.

Обозначая определение DFT для сигнала N = 8, мы должны были выполнить 64 операции умножения, но из-за вышеприведенного наблюдения мы сделали их только 12. Чем больше количество отсчетов в сигнале, тем больше преимущество в количестве вычислений с использованием алгоритма БПФ, так как объем вычислений для N-кратного сигнала может быть определен как:

N/2*log2(N)
N/2*log2(N)
Базовый элемент такого расчета называется "бабочка":




Быстрое преобразование Фурье на практике
Правильное количество выборок
Самый простой способ обработки сигнала имеет количество выборок, которое является степенью 2, просто заполните недостающие выборки нулями. В зависимости от структуры сигнала дополнения могут быть сделаны как правосторонними, так и левосторонними или обеими сторонами.

Рис.13. Дополненный сигнал из рис.2

Сортировка выборок
Для соединения последовательных отсчетов сигналов в соответствующих парах используются алгоритмы предварительной сортировки. Однако алгоритм БПФ может быть выполнен на несортированных выборках, а операция сортировки (таким же образом) может быть выполнена на выборках спектра.

В аппаратных анализаторах спектра и низкоуровневых языках программирования сортировка выборок намного проще, поскольку операция основана на простой инверсии битов в двоичном представлении индексной выборки.

В нашем сигнале N = 8 мы можем заметить, что:

public >returns<
Sorted signal samples///>
name="x" param< Original input signal samples
///>
summary summary<
// Double[] FFTDataSort(Double[] x)
{
int N = x.Length; // длина сигнала

if (Math.Log(N, 2) % 1 != 0)

{
бросить новое исключение ("Количество выборок в сигнале должно быть мощностью 2");
}

Double[] y = new Double[N]; // output (sorted) vector

int BitsCount = (int)Math.Log(N, 2); // maximum number of bits in index binary representation
for (int n = 0; n < N; n++)
{
string bin = Преобразовать.toString(n, 2).PadLeft(BitsCount, '0'); // двоичное представление индекса
Отражение StringBuilder = new StringBuilder(new string('0', bin.Длина));

for (int i = 0; i < bin.Длина; i++)

{
reflection[bin.Length - i - 1] = bin[i]; // двоичное отражение
}

int number = Преобразовать.ToInt32 (отражение.toString(),2); // новый индекс

y[число] = x[n];

}

возврат y;

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

public >returns<

Sorted signal samples///>
name="x" param< Original input signal samples
///>
summary summary<
// Double[] FFTDataSort2(Double[] x)
{
int N = x.Length; // длина сигнала

if (Math.Log(N, 2) % 1 != 0)

{
бросить новое исключение ("Количество выборок в сигнале должно быть мощностью 2");
}

int m = 1; // исходный индекс

для (int n = 0; n < N - 1; n++) // n - новый индекс
{
если (n < m)
{
Double T = x[m-1];
x[m-1] = x[n];
x[n] = T;
}

int s = N / 2; // оператор сдвига

while (s < m)
{
m = m - s;
s = s / 2;
}

m = m + s;

}

возврат x;

}