Экономика в промышленности Под редакцией профессора А. В. Ляшенко Саратов Издательство Саратовского университета 2016
|
Скачать 2.32 Mb.
|
БИЕКТИВНОЕ ОТОБРАЖЕНИЕ КОДА ЛЕМЕРАНА ЭЛЕМЕНТЫ МОДИФИЦИРОВАННОЙ МНОГОУРОВНЕВОЙКОММУТАЦИОННОЙ СХЕМЫ БЕНЕШАЛ. С. Сотов, В. С. Чесаков Саратовский национальный исследовательский государственный университет имени Н. Г. Чернышевского Россия, 410012, Саратов, Астраханская, 83 E-mail: [email protected] Коды Лемера часто используются для кодирования любой возможной перестановки элементов множества. Мы доказали, что код Лемера биективно отображается на биты управления модифицированной многоуровневой коммутационной схемой Бенеша. Это может быть использовано в алгоритмах реализации и перечисления перестановок. Коды Лемера хорошо подходят для управления модифицированными схемами Бенеша и манипуляции битами данных в ЭВМ. Ключевые слова: многоуровневая коммутационная схема, схема Бенеша, перестановка элементов множества, коды Лемера, манипуляция битами. 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)
Соответственно для конвертации бинарной строки из формата хранения согласно данным работы [ 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)
Таким образом, перестановку по такому алгоритму можно записать в виде  .Очевидно, что этот алгоритм довольно трудоемкий для шифрования/дешифрования в режиме реального времени, так как количество операций составляет 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 и векторы инверсий для них
В общем случае для перестановки длиной 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:
В то же время согласно ()
Рассмотрим сумму  из (). Она содержит 2m слагаемых длиной log2(2m+1) битов, поэтому ,
Равенство () является доказательством выражения (). Некоторые значения m, n, Nm, вычисленные с использованием выражения (), представлены в табл. 4. Таблица 4 Длина кода Лемера и число битов управления модифицированной схемой Бенеша Nm для различных значений m
Анализируя (), заметим, что каждому биту вектора инверсий соответствует ровно один бит управления модифицированной схемой Бенеша, при этом обратное отображение обладает тем же свойством. Следовательно, компоненты векторов инверсий биективно отображаются на биты управления модифицированной схемой Бенеша. Число переключателей схемы составляет  ,где n = 2m – число входов схемы. Таким образом, в работе доказано, что компоненты векторов инверсий, представляющие собой код Лемера, биективно отображаются на биты управления модифицированной схемой Бенеша. Это отображение может использоваться в комбинаторных автоматах, алгоритмах реализации и перечисления перестановок. Коды Лемера хорошо подходят для управления модифицированными схемами Бенеша и их можно использовать для манипуляции битами данных в ЭВМ [25]. БИБЛИОГРАФИЧЕСКИЙ СПИСОК |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
.
.
.
.Похожие:
 |
Экономика в промышленности Под редакцией профессора А. В. Ляшенко... Решением Президиума вак министерства образования и науки РФ издание включено в Перечень ведущих рецензируемых изданий, в которых |
 |
Издательство саратовского университета Для преподавателей, научных работников и студентов, обучающихся по специальности «Социально-культурный сервис и туризм» |
|
Учебное пособие для преподавателей и студентов медицинских институтов... Ценность брошюры заключается также и в том, что в ней напоминается о многих ученых, внесших большой вклад в развитие неврологии и... |
|
Издательство саратовского университета Франции и Англии xvii–xix вв до нынешних проблем культурного сотрудничества в Западной Польше. Особое внимание уделяется практике... |
|
Учебник для вузов Под редакцией Заслуженного деятеля науки Российской Федерации, профессора Р. С. Белкина |
|
К. Гроер Д. Кавалларо Перевод с английского канд мед наук Е. Б. Клейменовой... Книга рекомендована Управлением учебных заведений Министерства здравоохранения и медицинской промышленности Российской Федерации... |
|
Учебное пособие под редакцией профессора С. И. Данилова Грибковые заболевания кожи. Учебное пособие под ред проф. Си. Данилова спбгма им. И. И. Мечникова спб: 2005. С. 124 |
|
Весы 2009 -№39 Альманах гуманитарных кафедр Балашовского института... Альманах гуманитарных кафедр Балашовского института Саратовского государственного университета им |
|
Радиожурналистика под редакцией профессора A. A. Шереля Рекомендовано Министерством образования Российской Федерации в качестве учебника для студентов высших учебных заведений, обучающихся... |
|
Радиожурналистика под редакцией профессора A. A. Шереля Рекомендовано Министерством образования Российской Федерации в качестве учебника для студентов высших учебных заведений, обучающихся... |
|
Методическое пособие для студентов 2-го курса, обучающихся по специальности... Под редакцией зав кафедрой пропедевтики внутренних болезней профессора В. В. Аникина |
|
Методические рекомендации по оформлению отчета производственной практики... Под редакцией заведующей кафедрой госпитальной педиатрии д м н., профессора М. А. Скачковой |
|
Н. И. Бычков, Ю. Л. Колчинский, С. М. Семин Под общей редакцией доктора... Экзаменационные билеты для приема теоретического экзамена по безопасной эксплуатации самоходных машин категории «С» |
|
Регламент информационно-вычислительной сети сгту Ивс саратовского государственного технического университета объединяет подразделения университета в информационно-коммуникационную... |
|
Собриология наука об отрезвлении общества под редакцией профессора А. Н. Маюрова Собриология. Наука об отрезвлении общества. /Под ред проф. А. Н. Маюрова. Авторы: А. Н. Маюров, В. П. Кривоногов, Н. А. Гринченко,... |
|
Собриология наука об отрезвлении общества под редакцией профессора А. Н. Маюрова Собриология. Наука об отрезвлении общества. /Под ред проф. А. Н. Маюрова. Авторы: А. Н. Маюров, В. П. Кривоногов, Н. А. Гринченко,... |