Общая формула разложения.

Ясно, каким образом можно обббщить структуру вышеприведенного равенства. Для заданной последовательности будем полагать, что -элементные подпоследовательности

имеют соответственно . Тогда

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

Так как могут быть получены путем непрерывно повторяющегося разбиения вплоть до четырехэлементных последовательностей, полное разложение выражается через исходные последовательности. Например, для простого 8-эдементного преобразования элемент как оказывается, связан с восемью элементами последовательности следующим образом:

Эта зависимость согласуется с выражением

(см. скан)

(см. скан)

которое непосредственно следует из определения преобразования Хартли. Представляет интерес вопрос: почему оба этих подхода требуют разных временных затрат на вычисление соответствующих алгоритмов? Суть этого различия заключается в многоэтапном характере организации вычислительного процесса, обусловленном процедурой последовательного разбиения. Структура данного алгоритма, хотя мы к ней пришли независимо, соответствует операции факторизации матриц.

С целью иллюстрации последовательности выполнения арифметических операций обратимся к табл. 8.2, в которой приведены соотношения, реализующие операции преобразований.

Соотношения для случая

Как и в случае факторизации матриц, все свойства процедуры преобразования могут быть выявлены при рассмотрении примера, когда . В табл. 8.2 первый столбец содержит исходную последовательность данных . Во втором столбце приводятся результаты выполнения определенной в предыдущей главе операции перестановки элементов исходной последовательности. В последующих столбцах символ используется для обозначения элемента -элементной последовательности на этапе с номером ее преобразования. Таким образом, столбец с элементами содержит результаты этапа преобразования. Стрелки, используемые в операторах присвоения, подчеркивают направление перехода на данном этапе. Видим, что во всех случаях величина получается просто как сумма или разность двух элементов последовательности На этапе эти комбинации используются в качестве операндов, а именно осуществляется суммирование трех слагаемых, заимствованных из формулы разложения; аналогичным образом реализуются 3-й и 4-й этапы. Значения имеющие синусные коэффициенты, в явном виде иллюстрируют явление возвратной индексации.

Очевидно, имеет место экономия числа операций умножения по сравнению с требуемым для формирования суммы, предусмотренной по определению ДПХ. Однако табл. 8.2 непригодна для точного подсчета количества операций из-за вырождения отдельных членов, наглядно иллюстрируемого в табл. 8.3, что становится очевидным при замене коэффициентов в виде тригонометрических функций их числовыми значениями. Как на так и на этапах не требуется ни одной операции умножения, а на этапе необходимо выполнить только 16 операций умножения, в каждой из которых используется умножение на один и тот же коэффициент равный Полный эффект от оценки, характеризующейся сложным механизмом упрощения, анализируется ниже при исследовании временных затрат на вычисления.

Таблица 8.3. Соотношения для -элементной последовательности при подстановке числовых значений коэффициентов (см. скан)