матрица формирователя инволютивных перестановок

Классы МПК:G06F7/76 устройства для упорядочивания, перестановки или выбора данных согласно заранее установленными правилами, независимо от содержания данных
Автор(ы):
Патентообладатель(и):Государственное образовательное учреждение высшего профессионального образования "Саратовский государственный университет им. Н.Г. Чернышевского" (RU)
Приоритеты:
подача заявки:
2010-11-26
публикация патента:

Устройство относится к области кодирования информации и может быть использовано в вычислительной технике, системах коммуникации и защиты информации от несанкционированного доступа. Техническим результатом является обеспечение высокоскоростной инволютивной перестановки элементов входных данных. Устройство имеет n=2k входов данных, n выходов данных, бинарные входы управляющих кодов, состоящее из переключателей, которые расположены по n/2-линиям - строкам и k уровням - столбцам и являются управляемыми и неуправляемыми, причем один из переключателей на каждом из уровней от 1 до k-1 может быть неуправляемым, неуправляемые переключатели имеют первую пару входов данных X11, Х21, вторую пару входов данных X12, Х22, первую пару выходов данных Y11, Y21, вторую пару выходов данных Y12, Y22, а управляемые переключатели имеют дополнительно бинарный вход управляющего кода и выполнены с возможностью управляемого соединения входов с выходами. 2 з.п. ф-лы, 2 ил.

матрица формирователя инволютивных перестановок, патент № 2448358 матрица формирователя инволютивных перестановок, патент № 2448358

Формула изобретения

1. Матрица формирователя инволютивных перестановок, характеризующаяся тем, что имеет n=2k входов данных, n выходов данных, бинарные входы управляющих кодов, состоящая из переключателей, которые расположены по n/2-линиям - строкам и k уровням - столбцам и являются управляемыми и неуправляемыми, причем один EG переключателей на каждом из уровней от 1 до k-1 может быть неуправляемым, неуправляемые переключатели имеют первую пару входов данных X11, Х21, вторую пару входов данных X12, Х22, первую пару выходов данных Y11, Y21, вторую пару выходов данных Y12, Y22, а управляемые переключатели имеют дополнительно бинарный вход управляющего кода С и выполнены с возможностью соединения либо входа X11 с выходом Y11, входа Х21 с выходом Y21, входа X12 с выходом Y12, входа Х22 с выходом Y22, либо входа X11 с выходом Y21, входа Х21 с выходом Y11, входа X12 с выходом Y22, входа Х22 с выходом Y12, неуправляемые переключатели имеют фиксированные соединения входа X11 с выходом Y11, входа Х21 с выходом Y21, входа Х12 с выходом Y12, входа Х22 с выходом Y22, причем входы управляющих кодов матрицы формирователя инволютивных перестановок образованы входами кодов управляемых переключателей, входы данных матрицы формирователя образованы входами X11, Х21 переключателей первого уровня, выходы данных формирователя образованы выходами Y12, Y22 переключателей первого уровня, выходы и входы переключателей, расположенных на соседних уровнях, соединены между собой, при этом вход переключателя может быть соединен только с одним выходом, а выход переключателя может быть соединен только с одним входом, под соединением понимается условие, при котором если подать сигнал на вход, соединенный с выходом, или выход, соединенный с входом, на выходе через некоторую временную задержку, обусловленную временем распространения сигнала, появится входной сигнал и, наоборот, если подать сигнал на выход, на входе, через некоторую временную задержку, обусловленную временем распространения сигнала, появится выходной сигнал.

2. Матрица по п.1, характеризующаяся тем, что выход Y11 каждого переключателя, расположенного на линии i и уровне m, где матрица формирователя инволютивных перестановок, патент № 2448358 , соединен либо с входом X11, либо с входом Х21 переключателя, расположенного на следующем уровне m+1 и на линии h, а вход X12 каждого переключателя, расположенного на линии i и уровне m, где матрица формирователя инволютивных перестановок, патент № 2448358 , соединен либо с выходом Y12, либо с выходом Y22 переключателя, расположенного на следующем уровне m+1 и на линии h, выход Y21 каждого переключателя, расположенного на линии i и уровне m, где матрица формирователя инволютивных перестановок, патент № 2448358 , соединен либо с входом Х21, либо с входом X11 переключателя, расположенного на следующем уровне m+1 и на линии p, а вход Х22 каждого переключателя, расположенного на линии i и уровне m, где матрица формирователя инволютивных перестановок, патент № 2448358 , соединен либо с выходом Y22, либо с входом Y12 переключателя, расположенного на следующем уровне m+1 и на линии p, причем для значений p и h, определяющих соединения переключателя, расположенного на линии m с переключателем, расположенным на линии m+1, должно выполняться условие: либо

матрица формирователя инволютивных перестановок, патент № 2448358 , а матрица формирователя инволютивных перестановок, патент № 2448358 либо матрица формирователя инволютивных перестановок, патент № 2448358 , а матрица формирователя инволютивных перестановок, патент № 2448358 где int - функция выделения целой части, матрица формирователя инволютивных перестановок, патент № 2448358 - операция вычисления остатка от частного матрица формирователя инволютивных перестановок, патент № 2448358 .

3. Матрица по п.1 или 2, характеризующаяся тем, что выход Y11 каждого переключателя, расположенного на последнем уровне и линии с номером больше n/4, соединен либо с входом Х22, либо с входом X12 одного переключателя, расположенного на последнем уровне и линии с номером меньшим или равным n/4, выход Y21 каждого переключателя, расположенного на последнем уровне и линии с номером больше n/4, соединен либо с входом X12, либо с входом Х22 одного переключателя, расположенного на последнем уровне и линии с номером, меньшим или равным n/4, выход Y11 каждого переключателя, расположенного на последнем уровне и линии с номером, меньшим или равным n/4, соединен либо с входом Х22, либо с входом X12 одного переключателя, расположенного на последнем уровне и линии с номером больше n/4, выход Y21 каждого переключателя, расположенного на последнем уровне и линии с номером, меньшим или равным n/4, соединен либо с входом X12, либо с входом Х22 одного переключателя, расположенного на последнем уровне и линии с номером больше n/4.

Описание изобретения к патенту

Устройство относится к области преобразования информации и может быть использовано в вычислительной технике, системах коммуникации и защиты информации от несанкционированного доступа.

Под инволютивными перестановками понимается преобразование перестановки элементов входных данных, при котором осуществляется транспозиция произвольных пар входных данных.

Известно устройство для осуществления перестановок с использованием команд, основанное на сети (коммутационной матрице) «butterfly» (см. патент US № 6922472, МПК H04L 9/34).

Используя данное устройство, можно осуществлять инволютивные перестановки входных данных, однако число используемых в данной сети переключателей составляет n/2(log2(n)-1) и для выполнения только инволютивных перестановок может быть сокращено.

Известно устройство для осуществления перестановок с использованием команд, основанных на базе сетей омега (omega) и флип (flip) (см. патент US № 6952478, МПК G06F 7/76; G06F 9/30). Предложены инструкции для осуществления перестановок, которые могут использоваться в программном обеспечении, выполненном в программируемом процессоре. Инструкции для осуществления перестановок основаны на сети омега-флип, включающей, по крайней мере, два уровня, каждый из которых может выполнить функцию или сети омега, или флип. Начальная последовательность битов от исходного регистра преобразуется в промежуточные последовательности битов. Каждая промежуточная последовательность битов является входной для последующей инструкции перестановки. Инструкции перестановки определены для того, чтобы переставить начальную исходную последовательность битов в одну или более промежуточных последовательностей битов, пока не будет получена требуемая перестановка. Промежуточные последовательности битов определены битами конфигурации. Инструкции перестановки образуют последовательность инструкций перестановки, состоящую, по крайней мере, из одной инструкции. Последовательность инструкций перестановки максимального размера составляет 21r/m инструкций перестановки, где r - число переставляемых k-битных элементов и m - число уровней сети, задействованных в одной инструкции. Инструкции перестановки могут использоваться, чтобы переставить k-битные элементы, упакованные в n-битное слово, где k может быть 1, 2 матрица формирователя инволютивных перестановок, патент № 2448358 , n, и k*r=n.

Используя данное устройство, можно осуществлять инволютивные перестановки входных данных, однако управление данным устройством осуществляется программно, что существенно увеличивает время обработки при чистом изменении управляющих кодов. Кроме этого, для выполнения только инволютивных перестановок число переключателей может быть сокращено.

Известна коммутационная сеть (матрица) (см. патент US № 5175539, МПК H04J 3/00). Коммутационная сеть предназначена для избирательного одновременного соединения каждого из n входов с одним из n выходов. Она имеет входную часть, содержащую входы и имеющую, по крайней мере, k-1 (k=log2n) последовательно соединенных уровней k-уровневой сети baseline, n выходов и выходную часть, в которой n входов соединены с n выходами входной части, включающую k-уровневую сеть baseline и n выходов, которые образуют выходы коммутационной сети.

Используя данную коммутационную, сеть можно осуществлять инволютивные перестановки входных данных. Однако для осуществления таких перестановок число уровней выходной части данной коммутационной сети составляет k, что является завышенным и замедляет скорость осуществления перестановок. Кроме этого, для проведения оптимизации топологии коммутационной сети представляет интерес расширение возможных соединений между ее уровнями.

Задачей настоящего решения является обеспечение одновременной перестановки произвольных пар элементов входных данных с использованием управляющих кодов при минимизации ограничений на возможные соединения между уровнями коммутационной матрицы и сокращении количества ее коммутационных элементов.

Техническим результатом является ускорение выполнения инволютивных перестановок за счет сокращения числа уровней преобразования.

Поставленная задача достигается тем, что матрица формирователя инволютивных перестановок согласно решению имеет n=2k входов данных, n выходов данных, бинарные входы управляющих кодов, состоящая из переключателей, которые расположены по n/2-линиям - строкам и k уровням - столбцам и являются управляемыми и неуправляемыми, причем один из переключателей на каждом из уровней от 1 до k-1 может быть неуправляемым, неуправляемые переключатели имеют первую пару входов данных X11, Х21, вторую пару входов данных Х12, Х22, первую пару выходов данных Y11, Y21, вторую пару выходов данных Y12, Y22, а управляемые переключатели имеют дополнительно бинарный вход управляющего кода С и выполнены с возможностью соединения либо входа XII с выходом Y11, входа Х21 с выходом Y21, входа Х12 с выходом Y12, входа Х22 с выходом Y22, либо входа X11 с выходом Y21, входа Х21 с выходом Y11, входа Х12 с выходом Y22, входа Х22 с выходом Y12, неуправляемые переключатели имеют фиксированные соединения входа X11 с выходом Y11, входа Х21 с выходом Y21, входа Х12 с выходом Y12, входа Х22 с выходом Y22, причем входы управляющих кодов матрицы формирователя инволютивных перестановок образованы входами кодов управляемых переключателей, входы данных матрицы формирователя образованы входами X11, Х21 переключателей первого уровня, выходы данных формирователя образованы выходами Y12, Y22 переключателей первого уровня, выходы и входы переключателей, расположенных на соседних уровнях, соединены между собой, при этом вход переключателя может быть соединен только с одним выходом, а выход переключателя может быть соединен только с одним входом, под соединением понимается условие, при котором если подать сигнал на вход, соединенный с выходом, или выход, соединенный с входом, на выходе через некоторую временную задержку, обусловленную временем распространения сигнала, появится входной сигнал и, наоборот, если подать сигнал на выход, на входе, через некоторую временную задержку, обусловленную временем распространения сигнала, появится выходной сигнал. Выход Y11 каждого переключателя, расположенного на линии i и уровне m, где матрица формирователя инволютивных перестановок, патент № 2448358 , соединен либо с входом X11, либо с входом Х21 переключателя, расположенного на следующем уровне m+1 и на линии h, а вход Х12 каждого переключателя, расположенного на линии i и уровне m, где матрица формирователя инволютивных перестановок, патент № 2448358 , соединен либо с выходом Y12, либо с выходом Y22 переключателя, расположенного на следующем уровне m+1 и на линии h, выход Y21 каждого переключателя, расположенного на линии i и уровне m, где матрица формирователя инволютивных перестановок, патент № 2448358 , соединен либо с входом Х21, либо с входом X11 переключателя, расположенного на следующем уровне m+1 и на линии p, а вход Х22 каждого переключателя, расположенного на линии i и уровне m, где матрица формирователя инволютивных перестановок, патент № 2448358 , соединен либо с выходом Y22, либо с входом Y12 переключателя, расположенного на следующем уровне m+1 и на линии p, причем для значений p и h, определяющих соединения переключателя, расположенного на линии m с переключателем, расположенным на линии m+1, должно выполняться условие: либо матрица формирователя инволютивных перестановок, патент № 2448358 , a матрица формирователя инволютивных перестановок, патент № 2448358 , либо матрица формирователя инволютивных перестановок, патент № 2448358 , а матрица формирователя инволютивных перестановок, патент № 2448358 , где int - функция выделения целой части, матрица формирователя инволютивных перестановок, патент № 2448358 - операция вычисления остатка от частного матрица формирователя инволютивных перестановок, патент № 2448358 . Выход Y11 каждого переключателя, расположенного на последнем уровне и линии с номером больше n/4, соединен либо с входом Х22, либо с входом Х12 одного переключателя, расположенного на последнем уровне и линии с номером, меньшим или равным n/4, выход Y21 каждого переключателя, расположенного на последнем уровне и линии с номером больше n/4, соединен либо с входом Х12, либо с входом Х22 одного переключателя, расположенного на последнем уровне и линии с номером, меньшим или равным n/4, выход Y11 каждого переключателя, расположенного на последнем уровне и линии с номером, меньшим или равным n/4, соединен либо с входом Х22, либо с входом Х12 одного переключателя, расположенного на последнем уровне и линии с номером больше n/4, выход Y21 каждого переключателя, расположенного на последнем уровне и линии с номером, меньшим или равным n/4, соединен либо с входом Х12, либо с входом Х22 одного переключателя, расположенного на последнем уровне и линии с номером больше n/4.

Изобретение поясняется примерами возможных схем матриц формирователя инволютивных перестановок для случая n=8, изображенных на фиг.1, фиг.2, где

- F1, F2, F 3 - уровни преобразования матрицы формирователя;

- матрица формирователя инволютивных перестановок, патент № 2448358 - переключатели матрицы формирователя;

- X1-X8 - входы матрицы формирователя;

- Y1-Y8-выходы матрицы формирователя;

- С1-С10 - бинарные входы управляющих кодов матрицы формирователя;

- X11, Х21 - первая пара входов переключателя матрицы формирователя;

- Y11, Y21 - первая пара выходов переключателя матрицы формирователя;

- Х12, Х22 - вторая пара входов переключателя матрицы формирователя;

- Y12, Y22 - вторая пара выходов переключателя матрицы формирователя;

- С - бинарный вход управляющего кода переключателя матрицы формирователя.

Матрица формирователя инволютивных перестановок имеет n=2k входов данных, n выходов данных, входы управляющих кодов и состоит из управляемых и неуправляемых переключателей Тij, где матрица формирователя инволютивных перестановок, патент № 2448358 , матрица формирователя инволютивных перестановок, патент № 2448358 , k=log2n - целое положительное число. Каждый переключатель имеет первую пару входов X11, Х21, вторую пару входов Х12, Х22, первую пару выходов Y11, Y21, вторую пару выходов Y12, Y22, причем управляемые переключатели имеют также вход управляющего кода С, который принимает значения логического нуля или единицы. Каждый переключатель выполнен с возможностью соединения входа X11 с выходом Y11, входа Х21 с выходом Y21, а входа Х12 с выходом Y12, входа Х22 с выходом Y22; либо входа XII с выходом Y21, входа Х21 с выходом Y11, а входа Х12 с выходом Y22, входа Х22 с выходом Y12. Например, если сигнал на входе С управляемого переключателя имеет высокий логический уровень, то сигнал на выходе Y21 равен сигналу на X11, сигнал на выходе Y11 равен сигналу на входе Х21, сигнал на выходе Y22 равен сигналу на входе Х12, сигнал на выходе Y12 равен сигналу на входе Х22, таким образом переключатель осуществляет транспозицию сигналов, подаваемых на каждую из пар входов. Если сигнал на входе С имеет низкий логический уровень, то сигнал на выходе Y11 равен сигналу на входе X11, сигнал на выходе Y21 равен сигналу на входе Х21, сигнал на выходе Y12 равен сигналу на входе Х12, сигнал на выходе Y22 равен сигналу на входе Х22.

Неуправляемые переключатели не имеют входа управляющего кода и осуществляют фиксированное соединение входа X11 с выходом Y11, входа Х21 с выходом Y21, входа Х12 с выходом Y12, входа Х22 с выходом Y22.

Переключатели образуют матрицу формирователя с n/2-линиями и k уровнями F1, матрица формирователя инволютивных перестановок, патент № 2448358 , Fk. Входы управляющих кодов матрицы формирователя образованы входами кодов переключателей С. Входы данных матрицы формирователя образованы входами X11, Х21 переключателей Т i1 первого уровня матрицы. Выходы данных матрицы формирователя образованы выходами Y12, Y22 Тi1 первого уровня F 1 матрицы.

Переключатели каждого уровня можно разбить на группы. Переключатели первого уровня образуют одну группу первого уровня. Переключатели второго уровня образуют две группы второго уровня. Переключатели третьего уровня образуют четыре группы третьего уровня и т.д. Пары входов и выходов Х12, Y11 и Х22, Y21 каждого переключателя, расположенного на уровне m, где матрица формирователя инволютивных перестановок, патент № 2448358 , и входящего в одну группу, соединены с парами входов и выходов X11, Y12 и Х21, Y22, расположенных на уровне m+1 и входящих в две различные группы. Причем каждый вход переключателя соединяется только с одним выходом переключателя соседнего уровня и каждый выход переключателя соединяется только с одним входом переключателя соседнего уровня.

Таким образом, выход Y11 каждого переключателя, расположенного на линии i и уровне m, где матрица формирователя инволютивных перестановок, патент № 2448358 , соединен либо с входом X11, либо с входом Х21 переключателя, расположенного на следующем уровне m+1 и на линии h, a вход X12 каждого переключателя, расположенного на линии i и уровне m, где

матрица формирователя инволютивных перестановок, патент № 2448358 , соединен либо с выходом Y12, либо с входом Y22 переключателя, расположенного на следующем уровне m+1 и на линии h, выход Y21 каждого переключателя, расположенного на линии i и уровне m, где матрица формирователя инволютивных перестановок, патент № 2448358 , соединен либо с входом Х21, либо с входом X11 переключателя, расположенного на следующем уровне m+1 и на линии p, а вход Х22 каждого переключателя, расположенного на линии i и уровне m, где матрица формирователя инволютивных перестановок, патент № 2448358 , соединен либо с выходом Y22, либо с входом Y12 переключателя, расположенного на следующем уровне m+1 и на линии p, причем для значений p и h, определяющих соединения переключателя, расположенного на линии m с переключателем, расположенным на линии m+1, должно выполняться условие: либо матрица формирователя инволютивных перестановок, патент № 2448358 , a матрица формирователя инволютивных перестановок, патент № 2448358 , либо матрица формирователя инволютивных перестановок, патент № 2448358 , а матрица формирователя инволютивных перестановок, патент № 2448358 , где int - функция выделения целой части, матрица формирователя инволютивных перестановок, патент № 2448358 - операция вычисления остатка от частного матрица формирователя инволютивных перестановок, патент № 2448358 .

Пары входов X12, Х22 и выходов Y11,Y21 каждого переключателя последнего уровня Fk соединены между собой. Причем выход Y11 каждого переключателя, расположенного в нижней половине последнего уровня, соединен либо с входом Х22, либо с входом X12 одного переключателя, расположенного в верхней половине последнего уровня, выход Y21 каждого переключателя, расположенного в нижней половине последнего уровня, соединен либо с входом X12, либо с входом Х22 одного переключателя, расположенного в верхней половине последнего уровня. Вход X12 каждого переключателя, расположенного в нижней половине последнего уровня, соединен либо с выходом Y21, либо с выходом Y11 одного переключателя, расположенного в верхней половине последнего уровня, а вход Х22 каждого переключателя, расположенного в нижней половине последнего уровня, соединен либо с выходом Y11, либо с выходом Y21 одного переключателя, расположенного в верхней половине последнего уровня.

В матрице формирователя инволютивных перестановок вход одного переключателя может быть соединен только с одним выходом другого переключателя, а выход одного переключателя может быть соединен только с одним входом другого переключателя.

Один из переключателей на каждом из уровней F 1, матрица формирователя инволютивных перестановок, патент № 2448358 , Fk-1 может быть неуправляемым. На фиг.1, 2 неуправляемыми являются переключатели T41, T12 .

Устройство работает следующим образом. На входы матрицы формирователя подаются входные данные или сигналы. На бинарные входы управляющих кодов матрицы формирователя подаются управляющие коды. Через время задержки преобразования 2матрица формирователя инволютивных перестановок, патент № 2448358 ·log2n, где матрица формирователя инволютивных перестановок, патент № 2448358 - задержка на одном переключателе, на выходах матрицы формирователя появляется инволютивная перестановка входных данных или сигналов.

Таким образом, формирование произвольных управляемых инволютивных перестановок входных данных осуществляется параллельно за один такт внешнего генератора тактовых импульсов. Устройство может формировать только инволютивные перестановки входных данных.

Число переключателей матрицы составляет (n/2-1)·log2(n)+1 и растет практически линейно с ростом n, что делает технически возможным реализацию инволютивных перестановок при больших значениях n. Если использовать для построения данного преобразования коммутационную матрицу с топологией «butterfly» или «omega-flip», потребуется на матрица формирователя инволютивных перестановок, патент № 2448358 переключателей больше. Соответственно, для управления матрицей потребуется код на матрица формирователя инволютивных перестановок, патент № 2448358 бит длиннее. Число различных инволютивных перестановок, осуществляемых данным устройством, составляет матрица формирователя инволютивных перестановок, патент № 2448358 .

Класс G06F7/76 устройства для упорядочивания, перестановки или выбора данных согласно заранее установленными правилами, независимо от содержания данных

устройство поиска нижней оценки размещения в матричных системах при двунаправленной передаче информации -  патент 2447485 (10.04.2012)
устройство формирования обратных перестановок информации, хранимой в эвм -  патент 2446445 (27.03.2012)
устройство управляемой перестановки битов бинарной строки -  патент 2439662 (10.01.2012)
устройства и способы, предназначенные для обеспечения модификаций выходных данных в электронном устройстве в ответ на движение -  патент 2434263 (20.11.2011)
быстродействующий генератор случайных перестановок и сочетаний -  патент 2427885 (27.08.2011)
дешифратор управляемой перестановки информации, хранимой в персональной эвм -  патент 2390052 (20.05.2010)
способ обработки информации с использованием подхода, основанного на управлении потоком данных, и устройство для его осуществления -  патент 2360279 (27.06.2009)
реляционный процессор -  патент 2346322 (10.02.2009)
дешифратор управляемой побитовой транспозиции информации, хранимой в персональной эвм -  патент 2320000 (20.03.2008)
устройство обработки адресов коммутатора локальной вычислительной сети, работающего по принципу прозрачного моста -  патент 2304802 (20.08.2007)
Наверх