Быстрое преобразование Хартли

Дата добавления: 2014-11-27; просмотров: 1411; Нарушение авторских прав

Как уже отмечалось в разделе 6.2, множители ядра преобразования Харли не обладают свойством мультипликативности. Это не позволяет достаточно просто записать выражения для итерации алгоритма БПХ в матричной форме.

Выполним выкладки для получения выражений, описывающих итерацию БПХ. Для этого возьмем за основу выражения для описания “бабочки” БПФ ( ) произвольной итерации согласно (8.10):

(8.20)

здесь l=2^m-1, , .

Воспользуемся выражениями, связывающими отсчёты ДПФ и ДПХ [3]:

подставим (*), (**) и (***) в формулу (1) выражения (8.20) и получим:

(8.21)

В свою очередь, из выражения (8.21) можно получить выражения для действительной и мнимой частей:

Сложив выражения (3.22) и (3.23), можно получить:

Заметим, что (p+l)_{mod l}ºp, откуда следует:

(8.24)

Проделав аналогичные выкладки, можно получить, что:

здесь p = l+(l-k)_{mod l}, , , k=(n)_{mod l} , n - текущий индекс элемента вектора ( ).

Таким образом, при “бабочка” БПХ подобна “бабочке” БПФ, но обладает следующим отличием: правило вычисления индекса элемента синусной компоненты иное, чем у индекса косинусного элемента. Индекс же элемента косинусной компоненты и “свободной” компоненты, а также индекса у результирующего элемента и аргументы косинуса и синуса вычисляются так же, как и для “бабочки” БПФ [23].

На рис. 8.7. приведен граф базовой операции бабочка для алгоритма БПХ.

Рис.8.7. Граф базовой операции БПХ, где

Граф алгоритма БПХ для приведен на рис.8.8.

Рис.8.8. Граф алгоритма БПХ

Из представленного графа видно, что на третьей итерации при вычислении и в “бабочках” участвуют cos[...] и sin[...] компоненты с разными элементами.

<== предыдущая лекция	\|	следующая лекция ==>
Вычислительная сложность алгоритмов БПФ	\|