Теория электрической связи. Васильев К.К - 400 стр.

UptoLike

ВУЗ: 

УлГТУ | Ульяновск

Составители: 

Рубрика: 

400
ной последовательности для отсчетов с номерами от 2N до 1−N :
нч
2
чт2 n
Nnj
nnN
CeCC
π
−
+
−=
,
12,...,2,1,0
−
=
Nn
.
(9.43)
Соотношения (9.42) и (9.43) полностью определяют алгоритмы вычисле-
ния коэффициентов с помощью БПФ. Отметим, что экспоненциальные фазовые
множители
Nnj
e
π
2−
в этих алгоритмах учитывают влияние сдвига нечетной под-
последовательности относительно четной.
Чтобы еще уменьшить число вычислений, четную и нечетную подпосле-
довательности также разбивают каждую на две промежуточные части. Разбие-
ние продолжают вплоть до получения простейших двухэлементных последова-
тельностей. Определив ДПФ данных простейших пар отсчетов, можно вычис-
лить ДПФ четырехэлементных, восьмиэлементных
и так далее подпоследова-
тельностей. При объединении ДПФ четной и нечетной подпоследовательностей
используют алгоритмы (9.42) и (9.43), подставляя в них соответствующие зна-
чения номеров
N
и
n
.
Нетрудно заметить, что вычисления по формулам (9.41) не потребуют
операций умножения, в (9.41) имеются только сложение и вычитание ком-
плексных чисел. Учитываться же должны лишь операции умножения в алго-
ритмах (9.42) и (9.43) для различных
n при разбиениях массива отчетов на мел-
кие подпоследовательности. Число этих операций при первом разбиении со-
ставляло
2N . Такое же число 2N операций требуется выполнить при каждом
следующем разбиении. Таким образом, вдвое увеличивается число подпоследо-
вательностей и вдвое сокращается наибольшее число
n в формулах (7.30),
(7.31).
Вычисление коэффициентов ДПФ последовательности из N отсчетов по
алгоритмам БПФ требует примерно
NN
2
log операций умножения. Алгоритмы
БПФ сокращают число операций по сравнению с алгоритмами ДПФ в
NNNNN
22
2
log)log/( = раз. Например, при количестве отсчетов
10
2=N , имеем
10log
2
=N и сокращение числа операций составляет 100log
2
≈NN . При очень
больших массивах отсчетов входного сигнала выигрыш в скорости обработки
может достигать нескольких тысяч.
Таким образом, в алгоритмах БПФ выполняются операции сложения и
вычитания с умножением одного из компонентов на экспоненциальный множи-
тель
Nnj
e
π
2−
. Эту базовую для БПФ операцию очень удобно представлять сиг-

Страницы