Быстрые обобщенные преобразования Хартли в одноосновных системах счисления

16 / 19

Для полного БОПХ – Адамара γ = n − 1 и начальные условия
определяются с помощью p-точечных обычных ДПФ Хартли над вы-
борками (38). При реализации БОПХ – Адамара индекс γ пробегает
значения от (n − 1) до 1.
Оценка вычислительной сложности БОПХ. Из математических
описаний приведенных алгоритмов БОПХ следует, что все они вне
зависимости от способов прореживания сигнала и спектра и упорядо-
чения ОФХ являются итерационными процедурами с близкой вычи-
слительной структурой и требуют для своей реализации одинакового
числа вещественных умножений и сложений. Это позволяет провести
оценку сложности только для одного алгоритма БОПХ, распространив
затем полученные результаты на все виды БОПХ. Выберем для расче-
тов в качестве базового алгоритма алгоритм БОПХ – Пэли с прорежен-
ным порядком следования отсчетов сигнала и естественным порядком
следования отсчетов спектра.
Начнем с подсчета числа умножений. На γ -м шаге при одной ком-
бинации индексов {λ γ} необходимо для каждого значения qγ 6= 0 и при
всех значениях {kγ} выполнить число умножений на тригонометриче-
ские множители, равное p n−γ (p − 1) + (p − 1)(p − 2). Здесь учтено, что
часть произведений равны между собой. Для qγ = 0 тригонометри-
ческие множители в алгоритме равны единице и нулю и умножения
не выполняются. Поэтому для всех pγ −1 комбинаций индексов {λγ }
число умножений составит (p − 1)[p n−1 + (p − 2)pγ −1]. На последнем
(n −1)-м шаге при образовании начальных значений требуется выпол-
нить (p − 1)2pn−1 умножений на значения обычных функций Хартли.
Суммируя результаты для всех значений γ от 1 до (n − 1) получаем
следующую оценку числа умножений в полном алгоритме БОПХ:
MБ = p n−1[p (p − 2) + n (p − 1)] − p + 2 . (42)
Перейдем к сложениям. На каждом γ-м уровне при одной комбина-
ции индексов {λ γ} для значения qγ = 0 и всех значений kγ число сло-
жений, выполняемых в алгоритме, равно pn−γ(p −1). Поскольку число
комбинаций индексов {λγ } равно pγ− 1, то общее число сложений для
всех них будет (p − 1)pn−1. Для каждого значения qγ 6= 0 и для всех kγ
при одной комбинации { λγ } число сложений будет равно pn−γ (p−1)2 +
+( p−1)(pn−γ −1), а для всех комбинаций — (p−1)(pn−pγ−1) . В послед-
ней формуле учтено, что члены с одинаковыми множителями можно
объединить, сократив тем самым число сложений. Это связано с тем,
что в уравнениях БОПХ участвуют тригонометрические множители,
принимающие только p различных значений. Общее число сложений
для γ-го шага будет равно (p − 1)[pn−1(p + 1) − pγ − 1]. На последнем
(n − 1)-м шаге при вычислении начальных значений необходимо за-
тратить (p − 1)pn сложений. Окончательное общее число сложений на
78 ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2015. № 6