Дата последнего обновления файла 28.04.2013

Быстрое преобразование Фурье

Известно, что количество операций умножения в дискретном преобразовании Фурье определяется как nоп = N2, то если мы сможем получить преобразование Фурье из двух преобразований Фурье меньшего объема, то в результате можно получить выигрыш по быстродействию. Впервые это удалось американскому ученому C. M. Rader. Разобъем исходный сигнал x(n) на несколько последовательностей меньшей длины. В простейшем случае это будет две последовательности: четные отсчеты сигнала и нечетные отсчеты входного сигнала. Такой алгоритм вычисления спектра получил название быстрое преобразование Фурье с прореживанием по времени на 2.

Пусть количество отсчетов цифрового сигнала x(n) будет равно N. Тогда дискретное преобразование Фурье временной последовательности x(n) будет записываться следующим образом:

Формула вычисления дискретного преобразования Фурье

Для сокращения записи при преобразовании формул произведем замену переменной. Комплексную частоту e−jω заменим переменной W:

Формула записи четных отсчетов входного сигнала

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

Формула вычисления дискретного преобразования Фурье

Запишем последовательность четных отсчетов сигнала x(n) в следующем виде:

Формула записи четных отсчетов входного сигнала

Точно таким же образом запишем нечетные отсчеты входного сигнала:

Формула записи нечетных отсчетов входного сигнала

Теперь выразим дискретное преобразование Фурье через дискретные преобразования Фурье четных и нечетных последовательностей входных отсчетов сигнала:

Формула дискретного преобразования Фурье через два ДПФ меньшей длины

Раскроем скобки в степени коэффициента W:

Формула ДПФ через два ДПФ меньшей длины

В результате математических преобразований мы выяснили, что два ДПФ четных и нечетных временных отсчетов входного сигнала можно объединить в дискретное преобразование Фурье полной длины, если просуммировать частотные отсчеты четной последовательности с произведением частотных отсчетов нечетной последовательности входных сигналов на комплексную экспоненту WN. Количество операций умножения при этом значительно уменьшается по сравнению с прямым вычислением дискретного преобразования Фурье. Теперь обратим внимание, что отсчеты комплексной экспоненты WN симметричны относительно N/2. График комплексной экспоненты WN приведен на рисунке 1.

Графики реальной и мнимой составляющих комплексной экспоненты
Рисунок 1. Графики реальной и мнимой составляющих комплексной экспоненты WN

По формуле Эйлера реальная составляющая комплексной экспоненты представляет собой cos(x), а мнимая составляющая — sin(x). На графике sin(x) показан красным цветом, а cos(x) — синим, количество точек равно 10000. Из графика четко видно, что sin(n+N/2) = −sin(n) и cos(n+N/2) = −cos(n). В результате этого свойства комплексной экспоненты все частотные отсчеты от 0 до N/2−1 можно вычислить, просуммировав частотные отсчеты четного и нечетного ДПФ, а частотные отсчеты от N/2 до N−1 — вычислив разность. Граф вычисления быстрого преобразования Фурье с прореживанием по времени на 2 приведен на рисунке 2.

Граф вычисления быстрого преобразования Фурье
Рисунок 2. Граф вычисления быстрого преобразования Фурье

Если количество отсчетов (точек) в исходных ДПФ будет снова четным числом, то их, в свою очередь, можно будет разбить на четные и нечетные последовательности временных отсчетов. Это снова позволит сократить количество операций комплексного умножения. Граф быстрого преобразования Фурье при этом примет вид, изображенный на рисунке 3.

Улучшенный граф вычисления быстрого преобразования Фурье
Рисунок 3. Улучшенный граф вычисления быстрого преобразования Фурье

Для окончательного алгоритма 8-ми точечного быстрого преобразования Фурье с прореживанием по времени граф будет выглядеть, как это показано на рисунке 4.

Окончательный граф вычисления быстрого преобразования Фурье
Рисунок 4. Окончательный граф вычисления быстрого преобразования Фурье

Теперь оценим выигрыш полученного алгоритма быстрого преобразования Фурье с прореживанием по времени. Наибольший выигрыш получается для длины временной последовательности N = 2K, так как в этом случае процесс разбиения на две последовательности удается довести до 2-х точечного преобразования Фурье. При этом на каждом этапе объединения двух БПФ меньшего порядка требуется N/2 операций умножения. Общее количество операций комплексного умножения для вычисления БПФ потребуется:

Nоп = N/2×log2N

В качестве примера рассмотрим быстрое преобразование Фурье (БПФ) последовательности из 1024 отсчетов. Для прямого вычисления ДПФ нам бы потребовалось N2 операций умножения. Это приблизитеьно 1 млн. операций. При быстром преобразовании Фурье нам потребуется 512×10 = 5120 операций комплексного умножения. Выигрыш составляет приблизительно 200 раз! При оценке количества операций следует учитывать, что операция комплексного умножения приблизительно соответствует четырем обычным умножениям. Это может привести к тому, что операция прямого преобразования Фурье может дать выигрыш в два раза меньший по сравнению с ожидаемым, так как при прямом дискретном преобразовании Фурье осуществляется умножение реального числа на комплексное, а это две операции обычного умножения.

Теперь обратим внимание, что последовательность отсчетов сигнала на входе алгоритма быстрого преобразования Фурье не соответствует естественному течению времени. Ее следует переупорядочить. Для того, чтобы определить как следует переставить отсчеты воспользуемся двоичным представлением номера входного отсчета При перестановке младшие и старшие биты номера отсчета меняются местами. В качестве примера рассмотрим перестановку входных отсчетов 8-ми точечного БПФ. Соответствие входных номеров отсчетов сигнала и номеров на входе алгоритма БПФ приведено в таблице 1.

Номер Двоичное представление Двоично-инверсная перестановка Десятичное представление
0 000 000 0
1 001 100 4
2 010 010 2
3 011 110 6
4 100 001 1
5 101 101 5
6 110 011 3
7 111 111 7

Следует отметить, что в настоящее время быстрое преобразование Фурье обычно выполняется в сигнальных процессорах, а в них предусмотрен особый вид адресации — двоично-инверсный адрес. При этом старшие и младшие биты адреса меняются местами аппаратно, а реальная перестановка не производится. Это позволяет значительно сокращать время вычисления спектра входного сигнала. Не меньший выигрыш в быстродействии получается за счет применения умножителей-накопителей (MAC), а в современных сигнальных процессорах таких как SM320VC5510A фирмы Texas Instruments их применяется две штуки. Есть модели сигнальных процессоров, в которых применяется и большее количество MAC.

Литература:

  1. Б. Голд, Ч. Рейдер Цифровая обработка сигналов. пер. с англ., под ред. А. М. Трахтмана. М., "Сов. радио", 1973, 368 с.
  2. Ричард Лайонс Цифровая обработка сигналов. — 2-е. — М: Бином-Пресс, 2006. — 656 с.
  3. Куприянов М. C. Матюшкин Б. Д. Цифровая обработка сигналов. — 2-е. — СПб: Политехника, 2000. — 592 с.
  4. Сергиенко А. Б. Цифровая обработка сигналов. — 2-е. — СПб: Питер, 2006. — 751 с.
  5. БПФ по основанию 2 с прореживанием по времени (dsplib.ru)
  6. Быстрое преобразование Фурье

Вместе со статьей "Быстрое преобразование Фурье" читают:

Дискретное преобразование Фурье (ДПФ)
http://digteh.ru/dsp/DFT/

Преобразование Лапласа
http://digteh.ru/dsp/Laplas/

Z–преобразование
http://digteh.ru/dsp/Z/

Дискретные цепи
http://digteh.ru/dsp/DiscrNet/


Автор Микушин А. В. All rights reserved. 2001 ... 2017

Предыдущие версии сайта:
http://neic.nsk.su/~mavr
http://digital.sibsutis.ru/

Поиск по сайту сервисом Яндекс

Поиск по сайту сервисом ГУГЛ

пЕИРХМЦ@Mail.ru


Rambler's Top100