Глава 7. ФАКТОРИЗАЦИЯ МАТРИЦЫ ПРЕОБРАЗОВАНИЯ

И вставь в него оправленные камни в четыре ряда. Рядом: рубин, топаз, изумруд - один ряд. Второй ряд: карбункул, сапфир и алмаз. Третий ряд: яхонт, агат и аметист. Четвертый ряд: хризолит, оникс и яспис. В золотых гнездах должны быть вставлены они.

Библия, Вторая книга Моисеева; Исход, глава 28

Один из подходов к рассмотрению операции суммирования, определяющей значение дискретного преобразования Хартли, заключается в приведении квадратной матрицы к -мерному вектору. Ниже будет развит именно этот подход, так как он ведет к пониманию основ формирования быстрого алгоритма. Каждый элемент матрицы соответствует одному этапу реализации алгоритма, или его подпрограмме. Матричный подход проясняет операцию перестановки, когда сложная матрица может рассматриваться просто в виде графа (или диаграммы рассеяния), устанавливающего соответствие между выходным и входным индексами. Процедура перехода от преобразования Хартли к преобразованию Фурье к тому же может быть выражена с помощью матричного умножения, так как факторизация матрицы преобразования Хартли непосредственно ведет к новой факторизации матрицы преобразования Фурье; именно этой характерной особенностью обусловлена важность настоящей главы.

Матричное представление дискретного оператора

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

Если раскрыть знак суммы в формуле дискретного преобразования, то получится N отдельных равенств. Так, для случая

ДПФ, соответствующее формуле

будет иметь вид

Такая система уравнений может быть выражена через матричное умножение, связывающее входной -мерный вектор вида

с выходным вектором

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

что оправдано наличием экспоненциального множителя в большинстве слагаемых; там, где этот множитель отсутствует, можно предположить существование множителя равного единице.

В матричном представлении приведенные уравнения сводятся к одному уравнению

Квадратная матрица представляет собой оператор, преобразующий последовательность в последовательность преобразования Фурье . Используя буквы, набранные жирным шрифтом, для обозначения матриц, можем записать (опуская величину в соответствии с разделом «коэффициент гл. 5):

где - вектор-столбец с элементами - вектор-столбец с элементами и

Аналогично существует другая матрица , преобразующая исходную последовательность в последовательность дискретного преобразования Хартли

Интересным свойством матрицы является возможность ее факторизации с помощью метода, который приводит к алгоритму быстрого преобразования Фурье (БПФ). Факторизация матрицы Ч в виде

приводит к новому своеобразному быстрому алгоритму вычисления матрицы Н дискретного преобразования Хартли.

Наименьшее значение N, для которого можно пояснить суть процедуры факторизации, равно 16, когда имеется пять матричных коэффициентов и постоянный коэффициент Если то число этих матричных коэффициентов равно

Первый матричный коэффициент, который в порядке очередности первым осуществляет отображение последовательности является оператором перестановки. Последующие Р операторов могут быть названы каскадными матрицами. Если то , т. е. имеются четыре каскадные матрицы, если то их число равно 5 и т. д.