1.4. Матрицы перестановок

Определение 1.4. Матрицы перестановок — это класс матриц, элементы которых удовлетворяют следующим условиям.

т. е. матрицы содержат или 1, причем в одной строке или столбце - не более одной 1.

Рассмотрим некоторые классы перестановок, приме иемые при синтезе алгоритмов БПФ.

Пусть число является составным Представим произвольное число в позиционной системе по смешанному основанию

Тогда инверсией числа является число

Очевидно, что матричным аналогом (1.1) является единичная матрица, тогда как матричным аналогом (1.2) является матрица единица которой расположены на пересечении строки и столбца.

Пусть произвольная матрица тогда в определяется как матрица А, строки которой переставлены сопасно правилу (1.2), и является перестановкой столбцов согласно

Часгным с перестановки (1.2) является -ичная инверсии, когда

Обозначим матрицу цифроинверсной перестановки по смешанному основанию через и по основанию через

В литературе отдельно выделяется еще один частный случай цифро-инверсных перестановок, называемых "совершенными перестановками [3]:

В этом случае получаем следующие правила:

Приведем некоторые свойства матриц цифроинверсных перестановок.

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

В этом случае инверсная запись определяется выражением

где из условия однозначности представления

Для определении из (1.5) и (1.6) матриц перестановок в явнгм виде в [4] вводится лексикографический индекс который определяется при помощи сравнения:

Решение сравнения дает

Выражение устанавливает след; тощие перестановочные правила дня 11.5) и (1,6):

что соответствует матрице перестановки имеющеи единичные элементы на пересечснии 1-й строки и столбца, и

что соответствует матрице перестановки имеющеи единичные элементы на пересечении строки и столбца.

Ниже будет показано, что пара матриц и позволяет разделить ядро ДПФ (или на ДПФ (или с ядрамл меньшей размерности.

В теории факторизации матриц типа ДПФ перестановка класса (1.5) гсполмуется также для взаимно-простых т. е. когда

При этом константы выбираются равными где тогда

Приведем два частных случая перестановки (1.9), известных в литературе [5] под названиями "руританекого" и "китайского" соответствий. Пуританское" соответствие:

"Китайское" соответствие (основано на китайской теореме остатков —

Данный класс перестановок (1.9), как будет показан ниже, позволяет факторизовать ядро ДПФ (или ЦПУ) на ядра меньшей размерности случае взаимно-простых множителей длины преобразования.

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