Некоторые свойства алгоритма БПФ

Рассмотренный алгоритм с основанием 2 является алгоритмом с прореживанием по времени. Число операций комплексного умножения : P = N/2(log₂N)

Эта формула приближенная, она тем точнее, чем больше N. Дело в том, что ряд операций комплексного умножения сводится к умножению текущего отсчета на комплексную экспоненту в нулевой степени, равную 1-це.

Прореживание по времени – разделение временной последов-ти на две последовательности с вдвое меньшим количеством отсчетов.

Базовая операция алгоритма , так называемая «бабочка», состоит в том, что 2 входных числа A и B объединяются для получения 2-х выходных чисел X и Y следующим образом :

A,B → X,Y Аналитическая запись поясняет смысл

X=A+W˛N˛^k·B направлений графа

Y=A-W˛N˛^k·B

Для хранения данных при выполнении БПФ необходимо N+1 – ячейка памяти. В том случае, когда для размещения входной последов-ти, промежуточных результатов и выходной последов-ти используются одни и те же ячейки памяти, то алгоритм БПФ принято называть алгоритмом с замещением.

Основной особенностью алгоритма с прореживанием по времени является необходимость такой перестановки элементов входной последов-ти, чтобы выходная последов-ть коэффициентов X(k) имела бы прямой или естественный порядок расположения, т.е. прямой порядок изменения номера индекса k=0,1,2,3…N-1.

Для этого в рассмотренном примере элементы входной последов-ти размещались следующим образом:

x(0);x(4);x(2);x(6);x(1);x(5);x(3);x(7)

Алгоритм перестановки определяется 2-чно инверсным порядком расстановки.

Смысл этого алгоритма в том, что иллюстрацией служит таблица, 1-ый столбец которой – это обычный номер № элемента, 2-ой столбец – 2-чн. № элемента :

№ 2-чн. 2-чн.инверсн. новый

эл-та № эл-та № эл-та № эл-та

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

Реализация БПФ начинается с 4-го номера элемента входной последов-ти.

1-ый цикл БПФ – это сложение (+) и вычытание (-), умножения нет.

Микрооперация – это сложение; для операции умножения используется программа.

Для реализации 8-ми точечного БПФ необходимо 12 операций комплексного умножения ( т.е. N=8 Þ P = N/2(log₂N)=12). Для выполнения операций комплексного умножения необходимо 48 операций простого умножения.

Разрядность представления зависит от разрядности АЦП (пусть 8 разрядов).

Задача :

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

Время, необходимое для выполнения одной операции t=100нс.

Иллюстрация для БПФ : 100нс·7·48=33.6мкс

На этот интервал времени приходится 4 отсчета выходной последов-ти (4,5,6,7-всего 4).

33.6/4 Þ Ткв=8.4мкс

Fкв»100КГц – частота квантования, т.е. дискретизации.

Частота дискретизации – удвоенная ωгр спектра.

Fкв=2ωгрÞωгр»100/2»50

ωгр<50КГц

Для упрощения расчетов, т.е. чтобы не делить на 4, применяется алгоритм, описанный ниже.