Главная > Моделирование, обработка сигналов > Преобразование Хартли
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

Перестановка

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

Рис. 7.1. Идеальное тасование.

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

Перестановка последовательности из N элементов включает в себя следующие этапы: 1) инверсное перемешивание всей исходной последовательности, 2) инверсное перемешивание каждой половины полученной на первом этапе последовательности, 3) инверсное перемешивание каждой четверти, полученной на втором этапе и так далее до тех пор, пока не сформируются группы из 4 элементов. Данная операция завершается выполнением инверсного перемешивания этих «четверок». С целью детального анализа операции перестановки для -элементной последовательности проиллюстрируем выполнение трех последовательных перегруппировок строк:

Исходная последовательность

Первое перемешивание

Второе перемешивание

Третье перемешивание

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

<< Предыдущий параграф Следующий параграф >>
Оглавление