скачать doc
5 спектральный анализ. дискретное преобразование фурье. алгоритмы быстрого преобразования фурье.
5.1 Применение дискретного преобразования Фурье в современных системах управления
Анализ Фурье закладывает основы многих методов, применяющихся в области ЦОС. Дискретное преобразование Фурье (ДПФ) находит самое широкое применение в анализаторах спектра, устройствах обработки речи, изображений, сжатия информации и системах распознавания (рис. 5.1). ДПФ является частью программ проектирования фильтров для расчета импульсной характеристики фильтра по его частотной характеристике и обратно. Отдельной и достаточно обширной областью применения являются задачи распознавания характеристик объектов по их спектральным портретам. Это используется, в частности, при обработке радиолокационных сигналов. [2]
5.2 Типы преобразований Фурье
Преобразование Фурье позволяет сопоставить сигналу, заданному во временной области, его эквивалентное представление в частотной области. Наоборот, если известна частотная характеристика сигнала, то обратное преобразование Фурье позволяет определить соответствующий сигнал во временной области (рис. 5.2).
Фактически существует несколько вариантов таких преобразований. Семейство преобразований Фурье представлено на рис. 6.3. Классификация преобразований Фурье проводится в зависимости от природы сигнала во временной области: непрерывна или дискретна последовательность данных и конечен или бесконечен интервал, на котором рассматривается сигнал (табл. 5.1). Преобразование Фурье, независимо от того, производится ли оно над аналоговым или дискретным сигналом, и независимо от того, является оно прямым или обратным, характеризуется следующим свойством: преобразование Фурье, выполняемое над периодической функцией, приводит к
Цифровой спектральный анализ
Анализаторы спектра
Обработка речи
Обработка изображений
Распознавание образов
Проектирование фильтров
Вычисление импульсной характеристики по частотной
Вычисление частотной характеристики по импульсной
Быстрое преобразование Фурье
Рис. 5.1. Применение ДПФ
Рис. 5.2. Обратимость преобразования Фурье
Р
ис. 5.3. Семейство преобразований Фурье как функция сигнала во временной области
Таблица 5.1.
Типы преобразований Фурье
| Тип преобразования | Природа и интервал изменения сигнала во временной области | Природа и интервал изменения сигнала в частотной области |
| Ряды Фурье | Непрерывный, периодический | Дискретный, апериодический |
| Преобразование Фурье | Непрерывный, апериодический | Непрерывный, апериодический |
| Преобразование Фурье для сигналов дискретного времени | Дискретный, апериодический | Непрерывный, периодический |
| Дискретное преобразование Фурье | Дискретный, периодический | Дискретный, периодический |
дискретной функции, и, наоборот, преобразование Фурье дискретной функции является периодической функцией. [4]
Любой периодический сигнал x(t) можно представить в виде суммы бесконечного числа синусоидальных и косинусоидальных членов и одного постоянного члена. Этот представление называется рядом Фурье и задается следующим образом:
,где
; 
; 
.Операция получения спектральной функции X(j) аналогового сигнала x(t) и обратная операция получения сигнала x(t) по известной его спектральной функции X(j) производится с помощью пары преобразований Фурье:
, (5.1)
. (5.2)Пусть
– аналоговый сигнал, а соответствующий ему цифровой сигнал, полученный в результате аналого-цифрового преобразования, есть 
, где T – период дискретизации, n – номер отсчета аналогового сигнала при его преобразовании в цифровую форму, nT – моменты отсчета аналогового сигнала. Далее, для удобства, везде вместо будет употребляться 
. При этом будем полагать, что аналоговый сигнал имеет ограниченный спектр и период дискретизации удовлетворяет условию 
. В дальнейшем будем считать, что при t<0 
и, следовательно, отличные от нуля значения могут иметь место лишь при 
. Тогда для цифрового сигнала спектральная функция последовательности обозначается 
, а преобразования Фурье определяются следующими выражениями:
, (5.3)
. (5.4)Вычисление выражения (5.3) может быть выполнено только для аналитической функции, т. к. В нем предусматривается суммирование бесконечного числа членов. Результат вычисления этого выражения в общем случае является непрерывной функцией частоты
.При решении практических задач используется конечное число N отсчетов аналогового сигнала и, следовательно, в выражении (5.3) может производиться суммирование конечного числа членов. N отсчетов преобразований Фурье для сигналов дискретного времени
на интервале 
полностью описывают последовательность . В этом случае пара преобразований Фурье принимает вид дискретного преобразования Фурье:
, k = 0, 1, …N – 1; (5.5)
, n = 0, 1, …N – 1, (5.6)где
– комплексный фазовый коэффициент (тильда-коэффициент), корень степени N из единицы; N – число отсчетов дискретного сигнала x[n].Из определений (5.5) и (5.6) видно, что обе последовательности
и 
периодичны с периодом в N отсчетов.Некоторые свойства ДПФ играют в практических вопросах обработки сигналов очень важную роль. Ниже перечислены основные свойства ДПФ.
Линейность. Если
и 
– периодические последовательности (с периодом в N отсчетов каждая), а и 
– их ДПФ, то дискретное преобразование Фурье последовательности 
равно 
. Это положение справедливо и для последовательностей конечной длины.Сдвиг. Если последовательность
периодическая с периодом в N отсчетов, а ее ДПФ равно , то ДПФ периодической последовательности вида 
будет равно 
.Свойства симметрии. Если периодическая последовательность
с периодом в N отсчетов является действительной, то ее ДПФ удовлетворяет следующим условиям симметрии:
, 
. (5.7)5.3 Введение в быстрые алгоритмы
Любой алгоритм, подобно большинству инженерных устройств, можно описать либо через соотношение между входом и выходом, либо детально объясняя его внутреннюю структуру. Если алгоритм вычисляется в прямом соответствии с математической формулой, то такая реализация называется прямой. Но для решения задачи можно найти и более эффективные пути, которые называются быстрыми алгоритмами. Под быстрыми алгоритмами понимается детальное описание вычислительной процедуры, которая не является очевидным способом вычисления выхода по данному входу.
Простейшим примером быстрых алгоритмов являются действия по определению общего множителя:
. (5.8)5.4. Способы реализации быстрого преобразования Фурье
Набор алгоритмов, называемых алгоритмами БПФ, включают разнообразные методы уменьшения времени вычисления ДПФ. Поскольку вычисление ДПФ является основной операцией в большинстве задач спектрального анализа, то использование БПФ в некоторых встречающихся на практике случаях, позволяющее ускорить вычисление ДПФ в 100 и более раз по сравнению с методами прямого вычисления ДПФ, имеет чрезвычайно важное значение и должно рассматриваться как неотъемлемая часть применения методов цифровой обработки сигналов для спектрального анализа [5].
В практике самыми распространенными являются следующие два алгоритма БПФ: прореживание по времени (decimation-in-time, DIT) по основанию два (Radix 2) и прореживание по частоте (decimation-in-frequency, DIF) по основанию два.
5.4.1 БПФ с прореживанием по времени
При использовании прореживания во времени равенство ДПФ представляется как сумма двух вычислений, одно состоит из четных отсчетов, а другое- из нечетных отсчетов входной последовательности. Проиллюстрируем описанную методику для N-точечной последовательности {x [n]}, считая, что N равно степени 2.
(5.1)Введем две (N/2)–точечные последовательности {x1[n]} и {x2[n]} из четных и нечетных членов x[n] соответственно, т.е.:
(5.2)С учетом того, что
, (5.3)перепишем выражение (1.2.1) в виде
(5.4)
(5.5)где X1[k] и X2[k] равны (N/2)-точечным ДПФ последовательностей x1[n] и x2[n]. Из формулы (1.2.5) следует, что N-точечное ДПФ X[k] может быть разложено на два (N/2)-точечных ДПФ, результаты которых объединяются согласно (1.2.5). Если бы (N/2)-точечные ДПФ вычислялись обычным способом, то для вычисления N-точечного ДПФ потребовалось бы (N + N2/2) комплексных умножений. При больших N (когда N2 /2 >> N) это позволяет сократить время вычисления на 50%.
Поскольку X[k] определено при 0 ≤ k ≤ N –1 , а X1[k] и X2[k] определены при 0 ≤ k ≤N/2 – 1 , необходимо доопределить формулу (1.2.5) для k ≥ N/2. Заметим также, что WNk+N/2 = – WNk. И так как спектр дискретного сигнала периодичен, т.е.
и 
, то определение (5.5) может быть записано следующим образом:
(5.6)Входная последовательность x[n] сначала разбивается на две последовательности x1[n] и x2[n] из четных и нечетных членов x[n], после чего рассчитываются их преобразования X1[k] и X2[k]. Затем в соответствии с формулой (1.2.6) получают X[k].
Рассмотренная схема вычислений может быть использована для расчета N/2-точечных ДПФ в соответствии с формулой (5.6). Каждая из последовательностей x1[n] и x2[n] разбивается на две последовательности, состоящие из четных и нечетных членов. Аналогично N/2-точечные ДПФ могут быть записаны как комбинации двух N/4-точечных ДПФ.
Процесс уменьшения размера ДПФ от L до L/2 , где L равно степени 2, может быть продолжен до тех пор, пока не останутся только двухточечные ДПФ. Двухточечное ДПФ F[k], k=0,1 , может быть рассчитано без использования умножений по следующим формулам:
(5.7)Здесь f[n], n = 0, 1, – преобразуемая двухточечная последовательность. Поскольку W80 = 1 и W84 = – 1, для вычислений по формулам (5.7) действительно не нужны операции умножения. [5]
Алгоритм БПФ по основанию 2 разделяет полное вычисление ДПФ на комбинацию 2-точечных ДПФ. Каждое 2-точечное ДПФ содержит базовую операцию умножения с накоплением, называемую «бабочкой» и иллюстрируемую на рис. 5.1. На диаграмме показаны два представления «бабочки»: верхняя диаграмма фактически является функциональным представлением «бабочки», построенным на цифровых умножителях и сумматорах. В упрощенной нижней диаграмме операции умножения помечаются множителем возле стрелки, а под суммированием подразумеваются две стрелки, сходящиеся в точке.
Таким образом, восьмиточечное ДПФ в итоге сводится к алгоритму, описываемому направленным графом, представленным на рис. 5.2. Восьмиточечное БПФ с прореживанием во времени вычисляет окончательный результат с использованием трех каскадов, как это следует из рис. 5.3. Восемь входных отсчетов из временной области сначала разделяются (или прореживаются) на четыре группы 2-точечных ДПФ. Затем четыре 2-точечных ДПФ объединяются в два 4-точечных ДПФ. Затем два 4-точечных ДПФ объединяются для того, чтобы получить окончательный результат X[k]. Подробно процесс рассмотрен на рис. 5.1, где показаны все операции умножения и суммирования. Нетрудно заметить, что базовая операция «бабочки» 2-точечного ДПФ формирует основу для всего вычисления. Вычисление осуществляется в трех каскадах. После того, как заканчивается вычисление первого каскада, нет необходимости сохранять какие-либо предыдущие результаты. Результаты вычисления первого каскада могут быть сохранены в тех же самых регистрах или ячейках памяти, которые первоначально хранили исходные отсчеты из временной области
Рис. 5.1. Базовая операция "бабочка" в алгоритме БПФ с
прореживанием по времени
Рис. 5.2. Алгоритм 8-точечного БПФ с прореживанием
по времени
Рис. 5.3. Вычисление 8-точечного ДПФ в трех каскадах
с использованием прореживания по времени
Рис. 5.4. Пример бит-реверсивного прореживания
для N = 8
x[n]. Точно так же, когда заканчивается вычисление второго каскада, результаты вычисления первого каскада могут быть удалены. Таким же образом осуществляется вычисление последнего каскада, заменяя в памяти промежуточный результат вычисления предыдущего каскада. Следует обратить внимание, что для того, чтобы алгоритм работал должным образом, входные отсчеты по времени x[n] должны быть упорядочены определенным образом с использованием алгоритма реверсирования битов.
Двоично-инверсный порядок определяется следующим образом. Если записать порядковые номера элементов входной последовательности в двоичном коде, используя L двоичных разрядов, причем N = 2L, а затем инвертировать порядок следования разрядов, то получаемые при этом числа и будут номерами элементов входной последовательности после их перестановки. Так, для случая N = 8 = 23 порядок номеров приведен на рис. 5.4. Таким образом, для двоичной входной последовательности необходим соответствующий алгоритм.
Реверсирование битов часто выполняют аппаратурой ЦОС в генераторе адреса данных (DAG), упрощая таким образом программное обеспечение, сокращая количество дополнительных операций и ускоряя вычисления. [3]
5.4.2. БПФ с прореживанием по частоте
Другая распространенная форма алгоритма БПФ – так называемый алгоритм БПФ с прореживанием по частоте. В этом варианте алгоритма БПФ входная последовательность {x[n]} разбивается на две последовательности, содержащие по N/2 отсчетов каждая следующим образом: первая последовательность {x1[n]} состоит из первых (N/2) отсчетов {x[n]}, а вторая {x2[n]} – из остальных (N/2) отсчетов {x[n]}, т.е.:
(5.8)Разделим равенство для вычисления ДПФ на два, как сказано выше:
(5.9)Так как
,то равенство (5.9) можно также представить как
(5.10)Прореживание выходной (частотной) последовательности выполняется путем деления X[k] на два равенства: одно- для вычисления четных выходных отсчетов, а другое- для вычисления нечетных выходных отсчетов:
(5.11)Из выражения (5.11) видно, что четные и нечетные отсчеты ДПФ можно получить из (N/2)-точечных ДПФ последовательностей f[n] и g[n], равных
(5.12)Таким образом, снова вычисление N-точечного ДПФ удалось свести к вычислению двух (N/2)-точечных ДПФ.
Прореживание выходной (частотной) последовательности выполняется путем деления X[k] на два равенства: одно- для вычисления четных выходных отсчетов, а другое- для вычисления нечетных выходных отсчетов. Для четных отсчетов X[k], k=2r:
(5.13)Для нечетных отсчетов X[k], k=2r+1:
(5.14) Отметим, что X[2r] и X[2r+1] - это результаты N/2-точечных БПФ, выполненных над суммой и разностью первой и второй половин входной последовательности. В равенстве (1.2.14) разность двух половин входной последовательности умножена на тильда-коэффициент
. Первое деление сокращает число вычислений в два раза.Каждое из двух N/2-точечных ДПФ (X[2r] и X[2r+1]) делятся на два N/4-точечных ДПФ тем же способом, что N-точечное ДПФ делится на два N/2-точечных ДПФ. После замены
последовательность четных отсчетов в равенстве (5.9) имеет вид
(5.15)Эта N/2-точечная последовательность имеет ту же форму, что и первоначальная N-точечная последовательность в равенстве (5.10) и может быть поделена на половинки тем же способом, чтобы получить
(5.16)Для четных отсчетов введем обозначение r=2s.
(5.17)Для нечетных отсчетов введем обозначение r=2s+1.
(5.18)X[2r+1] также делится на два равенства (одно- для вычисления четных выходных отсчетов и другое- для вычисления нечетных выходных отсчетов) тем же способом, что X[2r] разделена на
и 
. Таким образом мы имеем четыре N/4-точечных последовательности.Если произвести замены
равенство (1.2.17) примет вид
(5.19)Эти четыре N/4-точечных последовательности, полученные в результате деления X(2r) и X(2r+1), представляются в виде восьми N/8-точечных последовательностей при третьем прореживании. Этот процесс повторяется до тех пор, пока результатом деления последовательности не будет пара равенств, которые вместе вычисляют двухточечное ДПФ. В этой паре переменная n, по которой проводится суммирование, равна нулю, так что никакого суммирования не выполняется. Это двумерное ДПФ, вычисляемое этой парой равенств, является ядром вычисления (бабочкой) для вычисления ДПФ по основанию 2 методом разреживания по частоте. [6]
На рис. 5.6 и 5.7 представлено вычисление БПФ с использованием алгоритма с прореживанием по частоте. Этот метод требует, чтобы алгоритм реверсирования был применен к адресам выходных отсчетов X(k). Следует обратить внимание, что «бабочка» для алгоритма с прореживанием по частоте слегка отличается от «бабочки» для алгоритма с прореживанием по времени, как это показано на рис. 5.5.
Как и в БПФ с прореживанием по времени в БПФ с прореживанием по частоте, после того, как заканчивается вычисление очередного каскада, нет необходимости сохранять какие-либо предыдущие результаты. Таким же образом осуществляется вычисление следующего каскада, заменяя в памяти промежуточный результат вычисления предыдущего каскада.
Использование алгоритмов с прореживанием по времени, по сравнению с алгоритмами с прореживанием по частоте, в значительной степени является вопросом предпочтения, так как оба алгоритма дают одинаковый результат. Определенные ограничения той или иной системы могут сделать одно из двух решений оптимальным. Необходимо отметить, что алгоритмы, требуемые для вычисления обратного БПФ, почти идентичны тем, которые необходимы для вычисления прямого БПФ, если принять во внимание, что речь идет об использовании комплексного БПФ. В действительности, полезный метод проверки алгоритма комплексного БПФ состоит в осуществлении БПФ с отсчетами из временной области x[n], а затем – в вычислении обратного БПФ с отсчетами из частотной области X[k]. В конце этого процесса должны быть получены первоначальные отсчеты из временной области Re x[n], а мнимая часть Im x[n] должна быть нулевой (в пределах ошибки математического округления). [3]
Рис. 5.5. Базовая операция "бабочка" в алгоритме БПФ с
прореживанием по частоте
Рис. 5.6. Вычисление 8-точечного ДПФ в три этапа,
алгоритм с прореживания по частоте
Рис. 5.7. Алгоритм 8-точечного БПФ с прореживанием
по частоте
5.4.3. БПФ по основанию 4
Обсуждавшиеся до сих пор БПФ представляют алгоритм БПФ по основанию 2, то есть их вычисление основано на 2-точечных базовых операциях типа «бабочка». Подразумевается, что число точек в БПФ должно быть степенью числа 2. Если число точек в БПФ является степенью числа 4, то БПФ может быть разделено на множество 4-точечных ДПФ, показанное на рисунке 1.2.8. Такое преобразование называется алгоритмом БПФ по основанию 4 (Radix 4). Базовая операция «бабочка» БПФ по основанию 4 с прореживанием по частоте представлена на рисунке.1.2.9.
Алгоритм БПФ по основанию 4 требует меньшего количества умножений с комплексными числами, но большего количества операций суммирования, чем БПФ по основанию 2 для такого же количества точек. По сравнению с алгоритмом БПФ по основанию 2, алгоритм по основанию 4 использует более сложную адресацию и дополнительные фазовые коэффициенты, но меньшее количество вычислений. Окончательная экономия времени вычисления различается для разных DSP, но алгоритм БПФ по основанию 4 может быть более чем вдвое быстрым, чем алгоритм по основанию 2 для DSP с оптимальной архитектурой. Это возможно, поскольку сигнальные процессоры компании Analog Devices содержат дополнительные внутренние функции, такие, как например, наличие двух генераторов адреса с возможностью бит-реверсивной адресации, и других аппаратных возможностей, широко используемых для оптимизации вычислений. [2]
Рассмотрим N -точечные ДПФ, N=2t, где t — четное число. В этом случае первый шаг БПФ выполняется для N1=4 и N2 = 2t-2, что эквивалентно разбиению N – точечной последовательности хт на 4 подпоследовательности: X4m, X4т+1, X4m+2 и X4m+3 для m = 0, 1, ..., N/4—1. Для такого разбиения Хk получается из выражения:
и, поскольку
, то
,
,
, K = 0, …, N/4 – 1.Следовательно, метод прореживания по времени при основании 4 сводит N-точечное ДПФ к четырем N/4-точечным ДПФ с помощью N комплексных умножений на фазовые множители Wlk и 3N комплексных сложений. Такая процедура может применяться рекурсивно t/2 раз, причем каждый раз длина преобразуемой последовательности уменьшается в четыре раза. Так, N-точечное ДПФ с помощью алгоритма по основанию 4 вычисляется за (N/2)log2N комплексных умножений и (3N/2) log2N комплексных сложений. Следовательно, число операций в этом случае больше, чем для БПФ-алгоритма по основанию 2. Однако покажем, что можно получить более точную оценку, если провести более детальный анализ.
Можно добиться уменьшения числа сложений на каждом шаге до 2N вместо 3N, используя следующую процедуру:
, l = 0, …, 3,
,
где Xl,k обозначает N/4-точечное ДПФ. Фазовые множители для последовательных шагов принимают значения: Wlk, W4lk, W16lk,... . Таким образом, они имеют вид Wlk4i, где i = 0, 1, ... . На шаге с номером i вычисление 4i N/4i -точечных ДПФ сводится к вычислению 4i+1 N/4i+1-точечных ДПФ. Так как общее число умножений на фазовые множители на каждом шаге равно N, то на каждом шаге множители разбиваются на 4i групп множителей Wlk4i где K = 0, ... , N/4i+1 - 1 и l = 0, 1, 2, 3. На последнем шаге фазовые множители равны ±1, ±j и умножения на них тривиальны. Для остальных шагом l = 1, 3 единственные простые умножения соответствуют k = 0 и k = (N/2)4i+1. Эти случаи соответствуют умножениям на 1 и Wl8= [(1 - j)/
]l. При l = 0 имеем Wlk=1. Для l = 2 умножения на Wlk4i выполняется с двумя тривиальными умножениями, двумя умножениями на нечетную степень W8 и (N/4i+1)-4 комплексными умножениями. На каждом шаге имеется 4i групп множителей, что соответствует (ЗN/4) – 8*4i комплексным умножениям и 4i+1 умножениям на нечетную степень W8 на каждый шаг. Далее, N = 2t = 4t/2 и, следовательно, нужно сложить числа умножений для (t/2) — 1 шагов. Таким образом, число M1 нетривиальных комплексных умножений дается выражением:M1=(3N/8)log2N - (17/12)N+ 8/3.
Аналогично число М2 умножений на нечетную степень W8 будет
M2=(N - 4)/3.
Следовательно, если комплексное умножение реализуется с четырьмя вещественными умножениями и двумя вещественными сложениями, то общее число М вещественных умножений и число А вещественных сложений будут равны
М = (ЗN/2) log2 N - 5N + 8,
A=(11N/4)log2N - (13N/6 + (8/3).
Если же комплексное умножение реализуется с тремя вещественными умножениями и тремя сложениями, то
М= (9N/8)log2N - (43N/12) + (16/3),
А = (25N/8)log2N - (43N/12) + (16/3).
Таким образом, БПФ-алгоритм по основанию 4 значительно уменьшает число требуемых операций по сравнению с алгоритмом по основанию 2. В табл. 2.2 приведены числа вещественных операций для БПФ-алгоритмов по основаниям 2 и 4, соответствующие выражениям __. Комплексное умножение выполняется с тремя вещественными умножениями и тремя вещественными сложениями. Из табл. 2.2, видно, что алгоритм по основанию 4 уменьшает число умножений примерно на 25% по сравнению с алгоритмом по основанию 2, тогда как число сложений в обоих случаях примерно одинаково. Небольшими видоизменениями можно получить алгоритмы по основаниям 8 и 16 . Если N не является степенью одного числа, то можно использовать смешанные основания. Например, ДПФ, включающее 32 точки, можно вычислить за два шага алгоритма по основанию 4 с последующим одношаговым применением алгоритма по основанию 2. С точки зрения числа операций БПФ-алгоритмы по смешанным основаниям позволяют добиться дополнительной экономии, однако при этом усложняется реализация этих алгоритмов.
Рис. 5.8. Трехкаскадное вычисление 16-точечного ДПФ
на основе алгоритма с прореживанием по
времени по основанию 4
Рис. 5.9. "Бабочка" алгоритма БПФ по основанию 4
с прореживанием по времени
5.4.4. Сравнение БПФ с ДПФ
Рассмотрим ДПФ на 8 точек, представленное на рисунке 5.10 в развернутом виде. ДПФ, представленное на диаграмме, требует 64 операций умножения с комплексными числами. N-точечное ДПФ требует N2 операций умножения с комплексными числами. Знание количества умножений важно потому, что на реализацию операций умножения затрачиваются существенные вычислительные ресурсы DSP. В действительности, общее время, требуемое для вычисления ДПФ, прямо пропорционально числу умножений с учетом необходимого числа дополнительных операций.
ДПФ, может быть сильно упрощено, если использовать свойства симметрии и периодичности фазовых коэффициентов, как показано на рис. 5.11. Результатом переработки выражений для ДПФ является БПФ, которое требует только Nlog2(N) пар операций “сложение-умножение” комплексных чисел. Вычислительная эффективность БПФ по сравнению с ДПФ становится весьма существенной, когда количество точек БПФ увеличивается до нескольких тысяч, как это следует из таблицы 5.1. Очевидно, что БПФ вычисляет все компоненты выходного спектра (или все, или ни одного!). Если необходимо рассчитать только несколько точек спектра, ДПФ может оказаться более эффективным. Вычисление одного выходного отсчета спектра с использованием ДПФ требует только N умножений с комплексными числами [3].
| X(0) = | x(0)W80+x(1)W80+x(2)W80 + x(3)W80 + x(4)W80 + x(5)W80 + x(6)W80 + x(7)W80 |
| X(1) = | x(0)W80+x(1)W81+x(2)W82 + x(3)W83 + x(4)W84 + x(5)W85 + x(6)W86 + x(7)W87 |
| X(2) = | x(0)W80+x(1)W82+x(2)W84 + x(3)W86 + x(4)W88 + x(5)W810 + x(6)W812 + x(7)W814 |
| X(3) = | x(0)W80+x(1)W83+x(2)W86 + x(3)W89 + x(4)W812 + x(5)W815 + x(6)W818 + x(7)W821 |
| X(4) = | x(0)W80+x(1)W84+x(2)W88 + x(3)W812 + x(4)W816 + x(5)W820 + x(6)W824 + x(7)W828 |
| X(5) = | x(0)W80+x(1)W85+x(2)W810 + x(3)W815+ x(4)W820 + x(5)W825 + x(6)W830 + x(7)W835 |
| X(6) = | x(0)W80+x(1)W86+x(2)W812 + x(3)W818+ x(4)W824 + x(5)W830 + x(6)W836 + x(7)W842 |
| X(7) = | x(0)W80+x(1)W87+ x(2)W814 + x(3)W821+ x(4)W828 + x(5)W835 + x(6)W842 + x(7)W849 |
N2 умножений с комплексными числами
Рис. 5.10. 8-точечное ДПФ (N=8)
симметричность: WN r+N/2 = – WN r, периодичность: WN r+N = WN r
| W84 = W80+4 = –W80 = –1 |
| W85 = W81+4 = –W81 |
| W86 = W82+4 = –W82 |
| W87 = W83+4 = –W83 |
| W88 = W80+8 = +W80 = +1 |
| W89 = W81+8 = +W81 |
| W810 = W82+8 = +W82 |
| W811 = W83+8 = +W83 |
| * * * * * * * * * |
Рис. 5.11. Свойства симметрии и периодичности
фазовых коэффициентов WN r
Таблица 5.1
| N точек | Количество операций | Эффект БПФ | |
| ДПФ | БПФ | ||
| 4096 | 16777216 | 49152 | 341:1 |
| 2048 | 4194304 | 22528 | 186:1 |
| 1024 | 1048576 | 10240 | 102:1 |
| 512 | 262144 | 4608 | 56:1 |
| 256 | 65536 | 2048 | 32:1 |
Таблица 5._
Оценка количества операций при различных способах вычисления БПФ
| Способ вычисления ДПФ | На одну точку | На все точки | ||||||
| Число умноже-ний M | Число сложений A | Число умножений M | Число сложений A | |||||
| MC | MR | AC | AR | MC | MR | AC | AR | |
| ДПФ | N | 4N | N-1 | 2N-2+ +2N | N2 | 4N2 | N2-N | 2N2-2N+2N2 |
| БПФ по основанию 2 | | | | | N/2log2N | 2Nlog2N | Nlog2N | 3N2log2N |
| БПФ по основанию 4 | | | | | | (ЗN/2) log2 N - 5N + 8, | | (11N/4)log2N - (13N/6 + (8/3). |