БИЕКТИВНОЕ ОТОБРАЖЕНИЕ КОДА ЛЕМЕРА
НА ЭЛЕМЕНТЫ МОДИФИЦИРОВАННОЙ МНОГОУРОВНЕВОЙ
КОММУТАЦИОННОЙ СХЕМЫ БЕНЕША
Л. С. Сотов, В. С. Чесаков
Саратовский национальный исследовательский
государственный университет имени Н. Г. Чернышевского
Россия, 410012, Саратов, Астраханская, 83
E-mail: kof@info.sgu.ru
Коды Лемера часто используются для кодирования любой возможной перестановки элементов множества. Мы доказали, что код Лемера биективно отображается на биты управления модифицированной многоуровневой коммутационной схемой Бенеша. Это может быть использовано в алгоритмах реализации и перечисления перестановок. Коды Лемера хорошо подходят для управления модифицированными схемами Бенеша и манипуляции битами данных в ЭВМ.
Ключевые слова: многоуровневая коммутационная схема, схема Бенеша, перестановка элементов множества, коды Лемера, манипуляция битами.
Bijective Map of Lehmer Codes to Benes-type
Multistage Interconnection Network
L. S. Sotov, V. S. Chesakov
The Lehmer code is a common used way to encode each possible permutation of a set. We found the bijective mapping between the Lehmer code and the Benes-type multistage interconnection network control bits. It can be used in the permutation algorithms and in numbering permutations. The Lehmer code is good for Benes-type network control and the hardware manipulation with bits of data.
Key words: multistage interconnection network, Benes networks, permutation of a set, Lehmer codes, bit manipulation.
Создание новых алгоритмов и аппаратурных устройств, осуществляющих перестановки входных данных, связано с решением ряда прикладных задач обработки информации в различных областях. Подобные задачи возникают в системах управления хранилищами и базами данных [1, 2], защиты информации [3], генерации шумов [4, 5], кодирования [6], автоматизированного проектирования [7], комбинаторных автоматах [8, 9], системах связи [3] и микропроцессорах [10]. Перестановки используются в качестве примитивов в криптографических шифрах [11].
Перестановки данных сложны для программной реализации [12]. Высокой производительности при осуществлении перестановок можно добиться, используя аппаратурные устройства [13, 14]. Для ускорения операции перестановки обычно используют аппаратурные средства [15]. Известны RISC-процессоры, осуществляющие перестановку n битов за несколько операций [16].
В микропроцессорах перестановки, извлечение и размещение битов машинного слова выполняются специальными модулями на базе многоуровневых коммутационных схем [17]. Скорость роста определяется комбинаторной моделью, положенной в основу формирователя перестановки, при этом с уменьшением времени преобразования увеличивается аппаратурная сложность преобразователя [18, 19]. В то же время упрощение конструкции преобразователя формата приводит к необходимости многоуровневой обработки и сокращает скорость выполнения операции конверсии форматов данных [20].
Проблемами построения устройств перестановки являются большая длина битов управления и сложность их настройки, приводящая к неоправданно громоздким решениям.
Известно, что перестановки данных можно осуществлять с использованием векторов инверсий, компонентами которых являются коды Лемера [21].
В данной статье доказано, что коды Лемера биективно отображаются на элементы управления многоуровневыми переключательными схемами, осуществляющими перестановки битов данных. Это может быть использовано для совершенствования архитектуры микропроцессорных модулей, их упрощения и увеличения быстродействия.
Векторы инверсий и перечисление перестановок
На векторах инверсий основан один из способов перечисления перестановок. Пусть X = (x1, x2, …, xn) – некоторая перестановка элементов 1, 2, …, n. Пара (xi, xj) называется инверсией, если i < j, а xi > xj. Например, в перестановке (5, 2, 1, 3, 4) имеются инверсии (5, 2), (5, 1), (5, 3), (5, 4), (2, 1). Вектором инверсий называют упорядоченное множество
D = (d1, d2, …, dn),
где dj – количество элементов xi таких, что пара (xi, xj) является инверсией. Иными словами, dj – это число элементов, больших xj и стоящих в перестановке X слева от xj. Очевидно, что d1 = 0 и 0 ≤ dj < j.
Вектор инверсий однозначно определяется по перестановке. Например, для перестановки X = (5, 2, 1, 3, 4) вектор инверсий D = (0, 1, 2, 1, 1).
В то же время по корректному вектору инверсий однозначно восстанавливается перестановка. Пусть, например, D = (0, 1, 2, 1, 1). Будем рассматривать компоненты вектора инверсий справа налево. Поскольку d5 = 1, то из чисел 1, 2, 3, 4, 5 лишь одно больше величины x5. Значит, x5 = 4. Так как d1 = 0, то из оставшихся чисел 1, 2, 3, 5 на последнем месте стоит наибольшее из них, т. е. 5. Значение d3 = 2 указывает, что среди чисел 1, 2, 3 в середине должно стоять число 1. В результате приходим к исходной перестановке X = (5, 2, 1, 3, 4). Таким образом, существует взаимно-однозначное соответствие (изоморфизм) между перестановками и векторами инверсий.
Рассмотрим алгоритм преобразования вектора инверсий
d = (d0, d1, …, dn-1)
в перестановку = (0, 1, …, n-1).
Пусть S – первоначально пустой упорядоченный список. Для i от n–1 до 0 необходимо вставить элемент i на di место в списке S. Элементы списка S в конечном итоге составят исходную перестановку .
Шаги алгоритма формирования перестановки = (2, 3, 1, 0) по вектору инверсий d = (0, 0, 2, 3) показаны в табл. .
Таблица
Алгоритм формирования перестановки = (2, 3, 1, 0)
по вектору инверсий d = (0, 0, 2, 3)
Шаг
|
1
|
2
|
3
|
4
|
Мно-
жество
|
Элементы
|
Мно-
жество
|
Элементы
|
Мно-
жество
|
Элементы
|
Мно-
жество
|
Элементы
|
i
|
3 2 1 0
|
i
|
3 2 1 0
|
i
|
3 2 1 0
|
I
|
3 2 1 0
|
d
|
0 0 2 3
|
d
|
0 0 2 3
|
d
|
0 0 2 3
|
d
|
0 0 2 3
|
S
|
3 (элемент 3 на нулевое место)
|
S
|
2 3 (элемент 2 на нулевое место)
|
S
|
2 3 1 (элемент 1 на 2-е место)
|
S
|
2 3 1 0 (элемент 0 на 3-е место)
|
Соответственно для конвертации бинарной строки из формата хранения согласно данным работы [ 6] с использованием в качестве дескриптора формата вектора инверсий d может использоваться следующий алгоритм.
Пусть S – первоначально пустой упорядоченный список. Для i от 0 до n–1 необходимо вставить элемент ai на di место в списке S. Элементы списка S в конечном итоге составят вектор b в обратном порядке.
Шаги алгоритма формирования вектора инверсий d = (0, 0, 2, 3) по перестановке = (2, 3, 1, 0) представлены в табл. 2.
Таблица 2
Алгоритм формирования вектора инверсий d = (0, 0, 2, 3)
по перестановке = (2, 3, 1, 0)
Шаг
|
1
|
2
|
3
|
4
|
Мно-
жество
|
Элементы
|
Мно-
жество
|
Элементы
|
Мно-
жество
|
Элементы
|
Мно-
жество
|
Элементы
|
i
|
a0 a1 a2 a3
|
i
|
a0 a1 a2 a3
|
i
|
a0 a1 a2 a3
|
i
|
a0 a1 a2 a3
|
d
|
0 0 2 3
|
d
|
0 0 2 3
|
d
|
0 0 2 3
|
d
|
0 0 2 3
|
S
|
a0
(элемент a0 на нулевое место)
|
S
|
a1 a0 (элемент a1 на нулевое место)
|
S
|
a1 a0, a2 (элемент a2 на 2-е место)
|
S
|
a1 a0 a2 a3 (элемент a3 на 3-е место)
|
Таким образом, перестановку по такому алгоритму можно записать в виде
 .
Очевидно, что этот алгоритм довольно трудоемкий для шифрования/дешифрования в режиме реального времени, так как количество операций составляет O(n2) и не подлежит распараллеливанию, поскольку на i-м шаге мы не можем определить окончательный индекс текущего элемента.
В работах [22, 23] показано, что для описания произвольной перестановки в методе динамического форматирования для каждого форматируемого блока длиной 16 битов используется дескриптор формата длиной 60 битов (с учетом, что последняя строка дескриптора однозначно вычисляется). В общем случае для блока размером n битов длина дескриптора в битах вычисляется по формуле
N = (n–1)·[log2(n)].
Такое представление обладает избыточностью n·log2(e). Этот уровень избыточности можно существенно уменьшить, используя представление перестановок в виде кода Лемера или в виде координат вектора инверсий.
Эти представления перестановок являются однозначными и наиболее компактными. Например, для данной перестановки σ длиной n вектором инверсий является вектор d длиной n, i-й элемент которого вычисляется как количество элементов в перестановке σ, больших, чем i, расположенных слева от i.
Примеры перестановок чисел от 1 до 4, т. е. n = 4, и векторы инверсий для них приведены в табл. 3.
Таблица 3
Перестановки чисел от 1 до 4 и векторы инверсий для них
Перестановка σ
|
Вектор инверсий d
|
Примечание
|
1
|
2
|
3
|
4
|
0
|
0
|
0
|
0
|
Перестановка 1
|
1
|
2
|
4
|
3
|
0
|
0
|
0
|
1
|
Перестановка 2
|
1
|
3
|
2
|
4
|
0
|
0
|
1
|
0
|
Перестановка 3
|
…
|
4
|
3
|
2
|
1
|
0
|
1
|
2
|
3
|
Последняя перестановка
|
1..4
|
1..4
|
1..4
|
1..4
|
0..0
|
0..1
|
0..2
|
0..3
|
Возможные значения для i-го элемента
|
2 бита
|
2 бита
|
2 бита
|
2 бита
|
0 битов
|
1 бит
|
2 бита
|
2 бита
|
Количество информации
для i-го элемента
|
8 битов
|
5 битов
|
Количество информации
|
В общем случае для перестановки длиной n соответствующий вектор инверсий потребует битов информации:
 .
|
()
|
Квадратные скобки в выражении (1) означают, что берется ближайшее целое число, большее log2(i).
Многоуровневая коммутационная схема
для осуществления перестановок
Диаграмма орграфа одного из вариантов коммутационной матрицы формирователя разбиений для случая n = 16, u = 1 приведена на рисунке. Согласно результатам работы [24] матрица осуществляет упорядоченное разбиение исходного n элементного множества S, где n = 2k, на подмножества одинаковой мощности равной 2u, где  , при этом число управляемых переключателей матрицы составляет n·(log2(n)–u/2–1)+1.
Входная часть матрицы состоит из управляемых и неуправляемых переключателей Tij, где  ,  . Выходная часть состоит из аналогичных управляемых переключателей Vsg, где  ,  ,  . Неуправляемые переключатели не имеют входа управляющего кода и осуществляют фиксированное соединение первого входа с первым выходом, второго входа со вторым выходом. На первом уровне один переключатель Т31 неуправляемый. На втором уровне неуправляемых переключателей два (Т42, Т52), на третьем – четыре (Т13, Т33, Т53 и Т73).
G1
S1
S2
S3
S4
S5
S6
S7
S8
S9
S10
S11
S12
S13
S14
S15
S16
d1
d2
d3
d4
d5
d6
d7
d8
d9
d10
d11
d12
d13
d14
d15
d16
T11
T12
T13
V11
V12
V13
T21
T22
T23
V21
V22
V23
T31
T32
T33
V31
V32
V33
T41
T42
T43
V41
V42
V43
T81
T82
T83
V81
V82
V83
T71
T72
T62
T61
T63
T73
V71
V72
V73
V63
V62
V61
T53
T52
T51
V51
V52
V53
F1
F2
F3
G2
G3
Диаграмма орграфа одного из вариантов коммутационной матрицы формирователя упорядоченных разбиений для случая n = 16, u = 1
Переключатели составляют входную часть матрицы c n/2-линиями и ( )-уровнями F1,…,Fk–1 и выходную часть матрицы c n/2-линиями и (k–u)-уровнями G1,…,Gk–u. Каждый переключатель Tim уровня  входной части матрицы своими выходами соединен с входами данных переключателей Th,m+1, Tp,m+1 уровня m+1. Каждый переключатель Vim уровня  выходной части матрицы своими выходами соединен с входами данных переключателей Vh,m+1, Vp,m+1 уровня m+1. Причем на соединения накладываются ограничения:
 ,  ,
где int – функция выделения целой части;  – операция вычисления остатка от частного  .
Переключатели входной части матрицы соединены так, что на уровне F1 входное множество S исходных данных разбивается на два множества S11 и S21, причем |S11|=|S21|. На следующем уровне F2 каждое из множеств S11 и S21 разбивается на два множества S12, S22 и S32, S42, причем
|S12| = |S22| = |S32| = |S42|.
Для обеспечения работы алгоритма настройки матрицы, приведенного выше, каждый переключатель уровня q<k выходной части матрицы может быть соединен через промежуточные переключатели с переключателями только одного из множеств Si,k–q уровня k–q входной части матрицы.
На уровне G1 входные данные выходной части матрицы разбиваются на два множества D11 и D21, причем |D11|=|D21|, и любой элемент множества D11 больше каждого из элементов множества D21. На следующем уровне G2 каждое из множеств D11 и D21 разбивается на два множества D12, D22 и D32, D42, причем
|D12| = |D22| = |D32| = |D42|,
и элементы множества D12 больше элементов множества D22, элементы множества D22 больше элементов множества D32, элементы множества D32 больше элементов множества D42.
Коммутационная матрица формирователя упорядоченных разбиений осуществляет полную перестановку элементов при u = 0. Тогда количество управляемых переключателей матрицы составляет n·(log2(n) – 1) + 1, т. е для управления матрицей необходимо n·(log2(n) – 1) + 1 битов информации. В случае выполнения перестановок будем называть матрицу модифицированной многоуровневой коммутационной схемой Бенеша. В выражении () положим n = 2m, где m = 1, 2, 3, … ,k. Можно доказать, что
 .
|
()
|
Доказательство () проведем по индукции. Для m = 1 выражение () верно. Пусть оно верно для m, докажем его для m + 1:
Nm+1 = 2m+1·(log2(2m+1) – 1) + 1 = 2·2m·log2(2m) + 1= Nm + 2m·log2(2m+1).
|
()
|
В то же время согласно ()
 .
|
()
|
Рассмотрим сумму  из (). Она содержит 2m слагаемых длиной log2(2m+1) битов, поэтому
 ,
 .
|
()
|
Равенство () является доказательством выражения ().
Некоторые значения m, n, Nm, вычисленные с использованием выражения (), представлены в табл. 4.
Таблица 4
Длина кода Лемера и число битов управления
модифицированной схемой Бенеша Nm для различных значений m
-
-
Длина перестановки
|
Число битов управления
и кода Лемера
|
n
|
Nm
|
2
|
1
|
4
|
5
|
8
|
17
|
16
|
49
|
32
|
129
|
64
|
321
|
128
|
769
|
256
|
1793
|
512
|
4097
|
Анализируя (), заметим, что каждому биту вектора инверсий соответствует ровно один бит управления модифицированной схемой Бенеша, при этом обратное отображение обладает тем же свойством. Следовательно, компоненты векторов инверсий биективно отображаются на биты управления модифицированной схемой Бенеша. Число переключателей схемы составляет
 ,
где n = 2m – число входов схемы.
Таким образом, в работе доказано, что компоненты векторов инверсий, представляющие собой код Лемера, биективно отображаются на биты управления модифицированной схемой Бенеша. Это отображение может использоваться в комбинаторных автоматах, алгоритмах реализации и перечисления перестановок. Коды Лемера хорошо подходят для управления модифицированными схемами Бенеша и их можно использовать для манипуляции битами данных в ЭВМ [25].
БИБЛИОГРАФИЧЕСКИЙ СПИСОК
|
