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

где 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 битов информации. В случае выполнения перестановок будем называть матрицу модифицированной многоуровневой коммутационной схемой Бенеша. В выражении (1) положим n = 2m, где m = 1, 2, 3, … ,k. Можно доказать, что

.

(2)

Доказательство (2) проведем по индукции. Для m = 1 выражение (2) верно. Пусть оно верно для m, докажем его для m + 1:

Nm+1 = 2m+1·(log2(2m+1) – 1) + 1 = 2·2m·log2(2m) + 1= Nm + 2m·log2(2m+1).

(3)

В то же время согласно (1)

.

(4)

Рассмотрим сумму из (4). Она содержит 2m слагаемых длиной log2(2m+1) битов, поэтому

,

.

(5)

Равенство (5) является доказательством выражения (2).

Некоторые значения m, n, Nm, вычисленные с использованием выражения (2), представлены в табл. 4.

Таблица 4

Длина кода Лемера и число битов управления

модифицированной схемой Бенеша Nm для различных значений m

Длина перестановки	Число битов управления и кода Лемера
n	Nm
2	1
4	5
8	17
16	49
32	129
64	321
128	769
256	1793
512	4097

Анализируя (2), заметим, что каждому биту вектора инверсий соответствует ровно один бит управления модифицированной схемой Бенеша, при этом обратное отображение обладает тем же свойством. Следовательно, компоненты векторов инверсий биективно отображаются на биты управления модифицированной схемой Бенеша. Число переключателей схемы составляет

,

где n = 2m – число входов схемы.

Таким образом, в работе доказано, что компоненты векторов инверсий, представляющие собой код Лемера, биективно отображаются на биты управления модифицированной схемой Бенеша. Это отображение может использоваться в комбинаторных автоматах, алгоритмах реализации и перечисления перестановок. Коды Лемера хорошо подходят для управления модифицированными схемами Бенеша и их можно использовать для манипуляции битами данных в ЭВМ [25].

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

, Концепция ТСВ-платформы для распределенных информационно-вычислительных систем специального назначения // Гетеромагнитная микроэлектроника : сб. науч. тр. Саратов : Изд-во Сарат. ун-та, 2008. Вып. 3 : Гетеромагнитная микро - и наноэлектроника. Прикладные аспекты. С. 66–72. , , О формировании доверенной среды серверных систем у правления базами данных // Проблемы информационной безопасности. Компьютерные системы. 2008. № 3. С. 23–27. , , Минимизация рисков утечки информации из-за побочных электромагнитных излучений персонального комьютера // Гетеромагнитная микроэлектроника : сб. науч. тр. Саратов : Изд-во Сарат. ун-та, 2014. Вып. 17 : Гетеромагнитная микро - и наноэлектроника. Методические аспекты физического образования. Экономика в промышленности. С. 66–77. , Стохастические генераторы упорядоченных разбиений конечных множеств с быстрым ростом энтропии // Гетеромагнитная микроэлектроника : сб. науч. тр. Саратов : Изд-во Сарат. ун-та, 2010. Вып. 8 : Гетеромагнитная микро - и наноэлектроника. Системы информационной безопасности. Прикладные аспекты. С. 57–72. , , Математические модели стохастического формирования изоморфных представлений структурных элементов данных в ЭВМ // Гетеромагнитная микроэлектроника : сб. науч. тр. Саратов : Изд-во Сарат. ун-та, 2008. Вып. 4 : Гетеромагнитная микро - и наноэлектроника. Прикладные аспекты. Устройства различного назначения. С. 29–41. , , Аппаратный акселератор сервера форматирования данных // Надежность и качество : тр. междунар. симпозиума : в 2 т. Пенза, 2007. Т. 1. С. 134–136. Аппаратные устройства формирования прямых и обратных перестановок данных // Гетеромагнитная микроэлектроника : сб. науч. тр. Саратов : Изд-во Сарат. ун-та, 2011. Вып. 9 : Магнитоэлектроника. Микро - и наноструктуры. Прикладные аспекты. Проблемы физического образования. С. 61–77. , , Алгоритм работы и модель функционального генератора перестановок // Информационные технологии. 2010. № 4. С. 41–46. , Простой матричный формирователь r-выборок // Гетеромагнитная микроэлектроника : сб. науч. тр. Саратов : Изд-во Сарат. ун-та, 2010. Вып. 8 : Гетеромагнитная микро - и наноэлектроника. Системы информационной безопасности. Прикладные аспекты. С. 47–56. , , Микропроцессор с ускоренной манипуляцией битами данных для обработки сигналов в системах связи // Гетеромагнитная микроэлектроника : сб. науч. тр. Саратов : Изд-во Сарат. ун-та, 2015. Вып. 18 : Гетеромагнитная микро - и наноэлектроника. Методические аспекты физического образования. Экономика в промышленности. С. 72–81. , , Перспективы разработки скоростных шифров на основе управляемых перестановок // Вопр. защиты информации. 1999. № 1. C. 41–47. Об эффективности использования специальных команд преобразования форматов данных в вычислительной технике // Гетеромагнитная микроэлектроника : сб. науч. тр. Саратов : Изд-во Сарат. ун-та, 2011. Вып. 10 : Гетеромагнитная микро - и наноэлектроника. Системы информационной безопасности. Прикладные аспекты. С. 61–80. , , Модели аппаратных акселераторов перестановок бинарных множеств // Гетеромагнитная микроэлектроника : сб. науч. тр. Саратов : Изд-во Сарат. ун-та, 2008. Вып. 4 : Гетеромагнитная микро - и наноэлектроника. Прикладные аспекты. Устройства различного назначения. С. 11–23. Аппаратные устройства формирования прямых и обратных перестановок данных // Гетеромагнитная микроэлектроника : сб. науч. тр. Саратов : Изд-во Сарат. ун-та, 2011. Вып. 9 : Магнитоэлектроника. Микро - и наноструктуры. Прикладные аспекты. Проблемы физического образования. С. 61–77. , Универсальный модуль манипуляции битами данных в микропроцессорах // Гетеромагнитная микроэлектроника : сб. науч. тр. Саратов : Изд-во Сарат. ун-та, 2011. Вып. 11 : Гетеромагнитная микро - и наноэлектроника. Прикладные аспекты. Экономика. Методические аспекты физического образования. С. 57–73. , , Проектирование микропроцессора c расширенным набором команд манипуляции битами данных на базе архитектуры OPENRISC1200 // Гетеромагнитная микроэлектроника : сб. науч. тр. Саратов : Изд-во Сарат. ун-та, 2014. Вып. 17 : Гетеромагнитная микро - и наноэлектроника. Методические аспекты физического образования. Экономика в промышленности. С. 50–65. Методы синтеза устройств, выполняющих инструкции перестановки битов данных // Гетеромагнитная микроэлектроника : сб. науч. тр. Саратов : Изд-во Сарат. ун-та, 2011. Вып. 10 : Гетеромагнитная микро - и наноэлектроника. Прикладные аспекты. Экономика. Методические аспекты физического образования. С. 25–50. , , Модели аппаратных функциональных формирователей перестановок // Информационно-измерительные и управляющие системы. 2009. Т. 7, № 10. С. 78–84. , , Моделирование архитектуры акселератора битовых перестановок с использованием САПР SYSTEM STUDIO фирмы SYNOPSYS // Гетеромагнитная микроэлектроника : сб. науч. тр. Саратов : Изд-во Сарат. ун-та, 2008. Вып. 3 : Гетеромагнитная микро - и наноэлектроника. Прикладные аспекты. С. 60–66. , , Алгоритм создания диверсификационного метода битовых преобразований // Естественные и технические науки. 2007. № 6. С. 222–225. Lehmer D. H. Teaching combinatorial tricks to a computer // Proceedings of Symposia in Applied Mathematics. binatorial Analysis. 1960. № 10. Р. 179–193. , , Динамическое форматирование структурных объектов хранилищ данных // Проблемы информационной безопасности. Компьютерные системы. 2008. № 4. С. 28–33. , , Cтруктура подсистемы стохастической генерации дескрипторов форматов //Аспирант и соискатель. 2009. № 4. С. 86–88. Комбинаторная модель функционального формирователя разбиений бинарного множества // Информационные технологии. 2010. № 10. С. 46–52. , , Процессор с улучшенной манипуляцией битами данных для средств навигации, обработки сигналов и изображений, криптографии, мобильных диагностических устройств // Гетеромагнитная микроэлектроника : сб. науч. тр. Саратов : Изд-во Сарат. ун-та, 2014. Вып. 16 : Гетеромагнитная микро - и наноэлектроника. Методические аспекты физического образования. Экономика в промышленности. С. 51–63.

УДК 631.391