Новосибирский государственный университет Факультет информационных технологий

А.М.Федотов

Словарь терминов в коллекции "Вычислительные системы"

Функция тасующей подстановки

Функция тасующей подстановки может быть реализована в одном из четырех вариантов (совершенное тасование, инверсное совершенное тасование, субтасование по i-му биту и супертасование по i-му биту), из которых наиболее распространены два: совершенная тасующая подстановка (perfect shuffle permutation) и инверсная совершенная тасующая подстановка (inverse perfect shuffle permutation).

Предполагается, что размер сети (количество узлов) равен N, разрядность адреса - n, где n=log₂N и биты адреса обозначены как x_i.Тогда:

• Совершенная тасующая подстановка:
  S(x_n-1x_n-2,...,x₁x₀) = x_n-2,...,x₁x₀x_n-1.
  Из приведенной формулы видно, что адрес узла-получателя может быть получен из двоичного кода узла-источника циклическим сдвигом этого кода влево на одну позицию. Если использовать аналогию с картами, то тасующая подстановка эквивалентна разбиению колоды карт на две половины с последующим равномерным чередованием карт из каждой половины.


• Инверсная совершенная тасующая подстановка:
  U(x_n-1x_n-2,...,x₁x₀) = x₀x_n-1,...,x₂x₁.
  Здесь также используется циклический сдвиг, но вправо.

Ключевые термины, связанные с термином "Функция тасующей подстановки":

1. Сеть Бэтчера-Баньяна
2. Топология «Омега»

Ключевые термины (головные):  Функции маршрутизации данных;

Контекстный поиск: Задайте образец для поиска:

Федотов Анатолий Михайлович

НГУ ФИТ НГУ ИВТ СО РАН