Гетеромагнитная микроэлектроника (стр. 11 )

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) показаны в табл. 1.

Таблица 1

Алгоритм формирования перестановки σ = (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)

Квадратные скобки в выражении (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).

Диаграмма орграфа одного из вариантов коммутационной матрицы формирователя упорядоченных разбиений для случая 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. Причем на соединения накладываются ограничения:

, ,