4.5. Обзор других быстрых алгоритмов. Особенности двумерных преобразований

Используя подход, описанный в предыдущих параграфах, можно получить факторизованное представление матриц и других ортогональных преобразований, описанных в § 3.11, а также ряд других полезных результатов. Эти результаты сведены в табл. 4.1. Среди них особый интерес представляют так называемые усеченные преобразования Фурье и Уолша и факторизованное представление матриц, связывающих между собой матрицы различных преобразований.

Усеченные алгоритмы БПФ-БПУ.

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

(см. скан)

(см. скан)

(см. скан)

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

Посмотрим, как меняется структура алгоритмов БПФ и БПУ в этом случае и оценим возможный выигрыш. Ввиду отмеченного выше родства БПУ и БПФ будем рассматривать только последнее.

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

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

и единичных матриц

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

Рассматривая факторизованный вид усеченной с двух сторон матрицы

в два приема, сначала умножая - слева на а затем умножая результирующую матрицу справа на Р и используя приемы совмещения матриц, подобные тем, которые применялись в § 4.3,

можно получить для факторизованного представления матрицы ДПФ (4.66) [74], что при

где определяется (3.135), a

Таким образом, усеченное преобразование состоит из каскадов: одного каскада двоичного инвертирования; одного каскада периодического повторения ненулевых входных отсчетов (матрица размножения каскадов неусеченного преобразования (произведение матриц от до каскадов преобразования «с пропусками» (произведения матриц от до

При преобразование вырождается: выпадают матрицы неусеченного преобразования, построенные на 1:

Граф усеченного преобразования (4.71) для показан на рис. 4.9. Числа в узлах графа означают степень комплексной экспоненты Нетрудно подсчитать количество

операций, затрачиваемых усеченным преобразованием. Количество операций сложения N и умножения равно:

при

при

Рис. 4.9.

Выигрыш в количестве операций за счет усечения преобразования по сравнению с вычислением неусеченного преобразования равен:

при

при

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

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

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

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

где или по теореме 2 из § 4.1

Используя (4.80) как рекуррентную формулу для можно получить

где — знак прямой суммы матриц.

Сравнив выражение в фигурных скобках в правой части (4.81) с факторизованным представлением матрицы Хаара (4.29), а также представление матрицы Хаара с матрицей модифицированного преобразования Адамара в виде сумм кронекеровских матриц (табл. 3.5), нетрудно видеть, что это выражение является с точностью до диагональной матрицы факторизованным представлением модифицированной матрицы Адамара:

Тогда первый сомножитель в (4.81), очевидно, представляет собой матрицу перехода от модифицированного преобразования Адамара к ДПФ с двоичной инверсией:

Для того чтобы факторизовать эту матрицу, заметим, что из (4.83) следует

Используя эту формулу рекуррентно, получаем

Наконец, подставив сюда выражение (4.82) для после очевидных преобразований окончательно придем к выражению

Рис. 4.10.

Обратная матрица перехода будет равна произведению этих же матриц, взятых в обратном порядке и с заменой на :

т. е.

Переход от модифицированного преобразования Адамара к ДПФ с двоичной инверсией иллюстрируется графом на рис. 4.10. Для удобства в левой части рисунка показан граф, соответствующий модифицированному преобразованию Адамара (см. табл. 4.1), Сравнивая этот совмещенный граф с графом БПФ на рис. 4.8, нетрудно видеть, что граф MHAD является усеченным графом БПФ, а граф дополняет его до графа БПФ. Отсюда, в частности, вытекает, что по количеству операций алгоритмы вычисления ДПФ через БПФ или через модифицированное преобразование Адамара с последующим переходом к ДПФ эквивалентны.

Ввиду аналогии между факторизованными представлениями матриц матрицу можно превратить в матрицу перехода от модифицированного преобразования Адамара к преобразованию Уолша—Адамара, изъяв из диагональные матрицы. Наконец, действуя так же, как для матрицы нетрудно получить матрицу перехода от преобразования Хаара к преобразованию Пэли. Эти матрицы приведены в табл. 4.1.

Вычисление двумерных преобразований.

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

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

в ОЗУ, транспонируют в ОЗУ массив внутри каждого фрагмента и транспонируют порядок расположения фрагментов в двумерном массиве. Для удобства транспонирования расположения фрагментов целесообразно иметь дополнительный буфер в ВЗУ с емкостью, равной объему фрагмента.

Транспонирование — не неизбежная операция при выполнении двумерных преобразований сигналов, не помещающихся в ОЗУ. Используя такой же принцип переадресации, что и при двумерном преобразовании в ОЗУ, можно построить алгоритмы двумерных преобразований без транспонирования (см., например, [86]).