МАТРИЦА ФОРМИРОВАТЕЛЯ ИНВОЛЮТИВНЫХ ПЕРЕСТАНОВОК Российский патент 2012 года по МПК G06F7/76 

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

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

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

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

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

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

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

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

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

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

Поставленная задача достигается тем, что матрица формирователя инволютивных перестановок согласно решению имеет n=2^k входов данных, 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, где , соединен либо с входом X11, либо с входом Х21 переключателя, расположенного на следующем уровне m+1 и на линии h, а вход Х12 каждого переключателя, расположенного на линии i и уровне m, где , соединен либо с выходом Y12, либо с выходом Y22 переключателя, расположенного на следующем уровне m+1 и на линии h, выход Y21 каждого переключателя, расположенного на линии i и уровне m, где , соединен либо с входом Х21, либо с входом X11 переключателя, расположенного на следующем уровне m+1 и на линии p, а вход Х22 каждого переключателя, расположенного на линии i и уровне m, где , соединен либо с выходом Y22, либо с входом Y12 переключателя, расположенного на следующем уровне m+1 и на линии p, причем для значений p и h, определяющих соединения переключателя, расположенного на линии m с переключателем, расположенным на линии m+1, должно выполняться условие: либо , a , либо , а , где int - функция выделения целой части, - операция вычисления остатка от частного . Выход 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, где

- F₁, F₂, F₃ - уровни преобразования матрицы формирователя;

- - переключатели матрицы формирователя;

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

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

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

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

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

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

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

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

Матрица формирователя инволютивных перестановок имеет n=2^k входов данных, n выходов данных, входы управляющих кодов и состоит из управляемых и неуправляемых переключателей Т_ij, где , , k=log₂n - целое положительное число. Каждый переключатель имеет первую пару входов 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 уровнями F₁, …, F_k. Входы управляющих кодов матрицы формирователя образованы входами кодов переключателей С. Входы данных матрицы формирователя образованы входами X11, Х21 переключателей Т_i1 первого уровня матрицы. Выходы данных матрицы формирователя образованы выходами Y12, Y22 Т_i1 первого уровня F₁ матрицы.

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

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

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

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

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

Один из переключателей на каждом из уровней F₁, …, F_k-1 может быть неуправляемым. На фиг.1, 2 неуправляемыми являются переключатели T₄₁, T₁₂.

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

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

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

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

1. Матрица формирователя инволютивных перестановок, характеризующаяся тем, что имеет n=2^k входов данных, 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, где , соединен либо с входом X11, либо с входом Х21 переключателя, расположенного на следующем уровне m+1 и на линии h, а вход X12 каждого переключателя, расположенного на линии i и уровне m, где , соединен либо с выходом Y12, либо с выходом Y22 переключателя, расположенного на следующем уровне m+1 и на линии h, выход Y21 каждого переключателя, расположенного на линии i и уровне m, где , соединен либо с входом Х21, либо с входом X11 переключателя, расположенного на следующем уровне m+1 и на линии p, а вход Х22 каждого переключателя, расположенного на линии i и уровне m, где , соединен либо с выходом Y22, либо с входом Y12 переключателя, расположенного на следующем уровне m+1 и на линии p, причем для значений p и h, определяющих соединения переключателя, расположенного на линии m с переключателем, расположенным на линии m+1, должно выполняться условие: либо
, а либо , а где int - функция выделения целой части, - операция вычисления остатка от частного .

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.