Глава 4. АЛГОРИТМЫ ЛИНЕЙНЫХ ПРЕОБРАЗОВАНИЙ

4.1. Понятие о быстрых алгоритмах дискретных ортогональных преобразований

Рассмотренные в предыдущей главе ортогональные преобразования сигналов описываются общей формулой

где — последовательность отсчетов сигнала; — базисные функции преобразования.

Если выполнять вычисления непосредственно по этой формуле, то для нахождения всех N коэффициентов необходимо проделать операций умножения и сложения (в случае ДПФ — умножения и сложения комплексных чисел). Даже при умеренных значениях N это количество операций может оказаться очень большим. Поэтому при цифровой обработке сигналов и в особенности изображений, задаваемых обычно большим количеством отсчетов, ДПФ и другие ортогональные преобразования получили практическое применение только после изобретения так называемых быстрых алгоритмов преобразований, для которых число операций растет с ростом N не быстрее, чем

Идея быстрых алгоритмов становится наглядной, если рассмотреть двумерные разделимые преобразования, базисные функции которых являются произведением одномерных базисных функций:

Поскольку они сводятся к двум одномерным преобразованиям

количество операций равно вместо операций, которые потребовались, если бы двумерное преобразование не было разделимым. Быстрые алгоритмы ортогональных преобразований как раз основаны на представлении одномерных преобразований в виде разделимых многомерных.

В настоящее время существует обширная литература по быстрым алгоритмам (см., например, [11, 16, 57, 67, 74, 77, 80, 91]) и описаны разные подходы к выводу таких алгоритмов для различных преобразований.

В последующих параграфах представлен единый подход к выводу быстрых алгоритмов, основанный на представлении матриц преобразований в виде сумм кронекеровских матриц (§ 3.11). Показано, что матрицы преобразований, размерностью могут быть факторизованы, т. е. представлены в виде произведения слабо заполненных матриц, содержащих максимум два отличных от нуля элемента в каждой строке. Получены также факторизованные представления для матриц перестановок и некоторых матриц, связывающих матрицы разных преобразований между собой. Для этого используются следующие определения и теоремы матричной алгебры.

Определение 1. Прямой суммой матриц называется клеточная матрица М вида

Прямая сумма обладает следующими необходимыми в дальнейшем свойствами:

где индекс Т означает транспонирование матрицы.

Определение 2 [4]. Правым прямым (кронекерэвским) произведением матриц и называется матрица

составленная из подматриц, каждая из которых является произведением соответствующего элемента матрицы на матрицу

Свойства прямого произведения матриц:

Теорема I. Если матрица М может быть разделена горизонтальной чертой на две подматрицы, каждая из которых является произведением некоторых двух матриц

то

Теорема 2. Если матрица М может быть разделена горизонтальной чертой на две подматрицы, каждая из которых является прямым (кронекеровским) произведением

некоторой матрицы-строки на некоторую матрицу

то

где — единичные матрицы размерности соответственно.

Теорема 3. Кронекеровская матрица

может быть представлена в виде произведения двух слабо заполненных матриц

Теорема 4.

где

Доказать эти теоремы можно прямой проверкой, пользуясь схемами умножения матриц, показанными на рис. 4.1 (а — для теоремы 1, б — для теоремы 2, в — для теоремы 3, г — для теоремы 4).