|
Новосибирский государственный университет
|
|
Функция тасующей подстановки
Синонимы: функция тасующей подстановки; тасование;Функция тасующей подстановки может быть реализована в одном из четырех вариантов (совершенное тасование, инверсное совершенное тасование, субтасование по i-му биту и супертасование по i-му биту), из которых наиболее распространены два: совершенная тасующая подстановка (perfect shuffle permutation) и инверсная совершенная тасующая подстановка (inverse perfect shuffle permutation).
Предполагается, что размер сети (количество узлов) равен N, разрядность адреса - n, где n=log2N и биты адреса обозначены как xi.Тогда:
- Совершенная тасующая подстановка:
S(xn-1xn-2,...,x1x0) = xn-2,...,x1x0xn-1.
Из приведенной формулы видно, что адрес узла-получателя может быть получен из двоичного кода узла-источника циклическим сдвигом этого кода влево на одну позицию. Если использовать аналогию с картами, то тасующая подстановка эквивалентна разбиению колоды карт на две половины с последующим равномерным чередованием карт из каждой половины.
- Инверсная совершенная тасующая подстановка:
U(xn-1xn-2,...,x1x0) = x0xn-1,...,x2x1.
Здесь также используется циклический сдвиг, но вправо.
Ключевые термины, связанные с термином "функция тасующей подстановки":
- Сеть Бэтчера-Баньяна
- Топология «Омега»
Ключевые термины: функции маршрутизации данных;
|Список
основных тем курса|
© 2012-2024, Новосибирский государственный университет, Новосибирск
© 2004-2024, Институт вычислительных технологий СО РАН, Новосибирск
© 2004-2024, Федотов А.М.
Дата последней модификации:
14.08.2013