Устройство перестановок и сдвигов битов данных в микропроцессорах



Устройство перестановок и сдвигов битов данных в микропроцессорах
Устройство перестановок и сдвигов битов данных в микропроцессорах
Устройство перестановок и сдвигов битов данных в микропроцессорах
Устройство перестановок и сдвигов битов данных в микропроцессорах
Устройство перестановок и сдвигов битов данных в микропроцессорах
Устройство перестановок и сдвигов битов данных в микропроцессорах
Устройство перестановок и сдвигов битов данных в микропроцессорах
Устройство перестановок и сдвигов битов данных в микропроцессорах
Устройство перестановок и сдвигов битов данных в микропроцессорах

 


Владельцы патента RU 2488161:

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования "Саратовский государственный университет имени Н.Г. Чернышевского" (RU)

Изобретение относится к средствам перестановок и сдвигов битов данных в микропроцессорах. Технический результат заключается в увеличении скорости выполнения операций. Устройство содержит n-разрядный вход данных X1-Xn, n-разрядный выход данных Y1-Yn, n-разрядный вход битов маскирования F1-Fn, m-разрядный вход кода управления устройства C1,1-Cn/2,k, где m=n/2k, k=log2(n), k-разрядный вход значения числа сдвига данных A0-Ak-1, бинарные входы кодов управления режимом функционирования устройства: AOR, RL, AMUX, AIOR, AOUT, АС. Устройство включает многоуровневую коммутационную сеть baseline или ibaseline 1, блок формирования битов маскирования и управления, n-разрядный мультиплексор входных данных, n-разрядный мультиплексор выходных данных, n-разрядный блок маскирования данных на входе, n-разрядный блок маскирования данных на выходе, m-разрядный мультиплексор битов управления, n-разрядный входной соединитель и n-разрядный выходной соединитель. 7 з.п. ф-лы, 9 ил., 2 табл.

 

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

Известен метод и система для осуществления перестановок на базе сетей butterfly (патент US 6922472, МПК H04L 9/34 (20060101); 380/37; Method and system for performing permutations using permutation instructions based on butterfly networks / Lee; Ruby В., Yang; Xiao, Vachharajani; Manish. July 26, 2005). Устройство включает в себя две многоуровневых коммутационных сети с топологией butterfly и инверсной топологией butterfly (ibutterfly). Переключатели сетей управляются битами, поступающими с внешних регистров. Произвольная перестановка битов входных данных осуществляется с использованием двух инструкций bfly и ibfly.

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

Известен метод и система для осуществления перестановок на базе модифицированных сетей omega и flip (патент US 6952478, МПК G06F 7/76 (20060101); 380/37; Method and system for performing permutations using permutation instructions based on modified omega and flip stages/Lee; Ruby В., Yang; Xiao. October 4, 2005). Устройство включает в себя две многоуровневые коммутационные сети с топологией omega и flip (ibutterfly). Переключатели сетей управляются битами, поступающими с внешних регистров. Произвольная перестановка битов входных данных осуществляется с использованием двух инструкций, связанных с прохождением данных через сети omega и flip.

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

Известен универсальный блок выполнения сдвигов и перестановок, описанный в работе Hilewitz Y., Lee R.A New Basis for Shifters in General-Purpose Processors for Existing and Advanced Bit Manipulations. / IEEE Transactions on Computing. 2009. Vol.58. №.8. P.1035-1048.

Блок включает в себя две многоуровневые коммутационные сети с топологией butterfly и инверсной топологией butterfly (ibutterfly), формирователь битов управления переключателями сетей, схемы мультиплексирования и маскирования входных и выходных битов данных. Блок позволяет выполнять инструкции циклических и логических сдвигов вправо и влево, команды рех (parallel extract) и pdep (parallel deposit) извлечения и размещения в определенных позициях групп битов входных данных, произвольные перестановки битов входных данных за две команды bfly и ibfly с использованием многоуровневых коммутационных сетей butterfly и ibutterfly.

Недостатком данного решения является необходимость использования двух многоуровневых коммутационных сетей и двух команд для выполнения произвольной перестановки битов данных. Кроме этого для выполнения инструкций рех и pdep также требуется использование двух коммутационных сетей butterfly и ibutterfly.

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

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

Поставленная задача достигается тем, что устройство перестановок и сдвигов битов данных в микропроцессорах согласно решению включает многоуровневую коммутационную сеть baseline или обратную многоуровневую коммутационную сеть ibaseline, с n-разрядным входом данных X1-Xn, n-разрядным выходом данных Y1-Yn, m-разрядным входом C1,1-Cn/2,k кода управления сетью; устройство также включает n-разрядный мультиплексор 2→1 входных данных с первым n-разрядным входом X1,1-X1,n, вторым n-разрядным входом X2,1-X2,n, входом управления A, соединенным с бинарным входом AOR управления маскированием на выходе и мультиплексором входных данных устройства, n-разрядным выходом Y1-Yn, соединенным с n-разрядным входом данных X1-Xn многоуровневой коммутационной сети; устройство также включает n-разрядный входной соединитель с n-разрядным входом X1-Xn и n-разрядным выходом Y1-Yn, соединенным с первым n-разрядным входом X1,1-X1,n n-разрядного мультиплексора 2→1 входных данных, входной соединитель обеспечивает фиксированные соединения входных и выходных разрядов; устройство также включает n-разрядный блок маскирования данных на входе с первым n-разрядным входом данных X1-Xn, вторым n-разрядным входом F1-Fn, n-разрядным выходом Y1-Yn, соединенным с n-разрядным входом X1-Xn входного соединителя и со вторым n-разрядным входом X2,1-X2,n, n-разрядного мультиплексора 2→1 входных данных; устройство также включает m-разрядный мультиплексор 2→1 битов управления с входом управления AC, первым m-разрядным входом C1,1,1-C1,n/2,k битов управления, вторым m-разрядным входом C2,1,1-C2,n/2,k битов управления, m-разрядным выходом Y1,1-Yn/2,k, соединенным с m-разрядным входом C1,1-Cn/2,k кода управления сетью; устройство также включает блок формирования битов маскирования и управления, с бинарным входом AOR, соединенным с бинарным входом управления маскированием на выходе и мультиплексором входных данных устройства, бинарным входом RL управления направлением сдвига данных, бинарным входом AMUX управления мультиплексором битов маскирования, бинарным входом AIOR управления маскированием на входе, n-разрядным входом F1-Fn битов маскирования, k-разрядным входом A0-Ak-1 значения числа сдвига данных, n-разрядным выходом FI1-FIn битов маскирования входных данных, соединенным со вторым n-разрядным входом F1-Fn блока маскирования данных на входе, n-разрядным выходом FO1-FOn битов маскирования выходных данных, (n-1)-разрядным выходом С1-Cn-1 кода маскирования данных на входе, (n-1)-разрядным выходом C1-Cn-1 кода управления сдвигом, соединенным с вторым m-разрядным входом С2,1,1-C2,n/2,k битов управления мультиплексора 2→1 битов управления; устройство также включает n-разрядный блок маскирования данных на выходе с первым n-разрядным входом Х1-Xn, соединенным с n-разрядным выходом данных Y1-Yn многоуровневой коммутационной сети, вторым n-разрядным входом F1-Fn, соединенным с n-разрядным выходом битов маскирования выходных данных FO1-FOn, n-разрядным выходом Y1-Yn; устройство также включает n-разрядный выходной соединитель с n-разрядным выходом Y1-Yn, n-разрядным входом Х1-Xn, соединенным с n-разрядным выходом Y1-Yn n-разрядного блока маскирования данных на выходе, выходной соединитель обеспечивает фиксированные соединения входных и выходных разрядов; устройство также включает n-разрядный мультиплексор 2→1 выходных данных с первым n-разрядным входом X1,1-X1,n, соединенным с n-разрядным выходом Y1-Yn n-разрядного блока маскирования данных на выходе, вторым n-разрядным входом X2,1-X2,n, соединенным с n-разрядным выходом Y1-Yn n-разрядного выходного соединителя, входом управления A, соединенным с бинарным входом управления мультиплексором выходных данных AOUT устройства, n-разрядным выходом данных Y1-Yn. При использовании сети baseline бит i-го разряда Ci, i = 1, n 1 ¯ кода управления сдвигом подают на входы разрядов C2,q,r второго m-разрядного входа мультиплексора битов управления, где индекс q - целое число и INT(i-2r-1)·2k-r<q<(INT((i-2r-1))+l)·2k-r+1, r=INT(log2(i))+1, INT - функция, выделяющая целую часть аргумента. При использовании сети ibaseline на входы разрядов C2,q,j, где j = 1, k ¯ , q = 1, n / 2 ¯ , второго m-разрядного входа мультиплексора битов управления подают бит i-го разряда Ci (n-1)-разрядного выхода C1-Cn-1 кода управления сдвигом, причем i=mod(q-1,2j-1)+2j-1, где mod(q-1,2j-1) - функция, вычисляющая число q-1 по модулю 2j-1. Блок формирования битов маскирования и управления включает первый блок побитовой дизъюнкции с n-разрядным входом данных X1-Xn, соединенным с n-разрядным входом F1-Fn битов маскирования, n-разрядным выходом данных Y1-Yn, и входом AOR, первый блок побитовой дизъюнкции осуществляет функции побитовое логическое ИЛИ Yi=Xi∨AOR, где i = 1, n ¯ ; блок формирования битов маскирования и управления также включает n-разрядный мультиплексор битов маскирования, с выходом FO1-FOn, первым n-разрядным входом X1,1-X1,n, вторым n-разрядным входом X2,1-X2,n, соединенным выходом Y1-Yn первого блока побитовой дизъюнкции, входом AMUX, блок формирования битов маскирования и управления также включает n логических инверторов D1-Dn и n-1 модуль формирования битов кода управления сдвигом Mi,j, где i = 1,2 j 1 ¯ , j = 1, k ¯ , каждый из которых имеет три бинарных входа f, ci, rotr, три бинарных выхода c, f1, f2, и выполняет логические функции: c = f c i f c i ¯ , f 1 = ( r o t r ¯ f c i ¯ ) ( f c i ¯ ) ¯ , f 2 = ( r o t r f c i ¯ ) ( f c i ¯ ) ¯ , входы rotr всех модулей Mi,j соединены с входом RL, модули Mi,j соединены так, что образуют двоичное дерево с k уровнями, при этом на уровне j содержится 2j-1 модулей Mi,j, причем выход с каждого из модулей Mi,j соединен с выходом Cp блока формирования битов маскирования и управления, где p=2j-1+i-1, выход f1 каждого модуля Mi,j, расположенного на уровне j соединен с входом f модуля M2i-1,j+,1, расположенного на уровне j+1, выход f2 каждого модуля Mi,j, расположенного на уровне j, соединен с входом f модуля M2i,j+1, расположенного на уровне j+1, вход f модуля M1,1 предназначен для сигнала с низким логическим уровнем, вход ci каждого модуля Mi,j, расположенного на уровне j, соединен с входом разряда Aj-1 входа A0-Ak-1, выход f1 каждого модуля Mi,k, расположенного на k-ом уровне, соединен с входом логического инвертора D2i-1, выход f2 каждого модуля Mi,k, расположенного на k-ом уровне, где i = 1, n / 2 ¯ , соединен с входом логического инвертора D2i каждый выход логического инвертора Di, где i = 1, n ¯ соединен с разрядом X1,i, первого входа мультиплексора битов маскирования; блок формирования битов маскирования и управления включает второй блок побитовой дизъюнкции с n-разрядным входом данных X1-Xn, соединенным с n-разрядным входом F1-Fn битов маскирования, выходом FI1-FIn, входом AIOR, второй блок побитовой дизъюнкции осуществляет функции побитовое логическое ИЛИ Yi=Xi∨AIOR, где i = 1, n ¯ . Многоуровневая коммутационная сеть baseline состоит из переключателей Ti,j, где i = 1, n / 2 ¯ , j = 1, k ¯ , расположенных в матричном порядке по n/2 линиям и k=log2n уровням, каждый переключатель имеет два бинарных входа X1, Х2, два бинарных выхода Y1, Y2 и бинарный вход управляющего сигнала C, каждый переключатель реализует логические функции Y 1 = C X 1 C ¯ X 2 , Y 2 = C ¯ X 1 C X 2 , бинарные входы управляющих сигналов переключателей сети образуют m-разрядный вход C1,1-Cn/2,k кода управления многоуровневой коммутационной сетью baseline, причем бинарный вход C переключателя Ti,j, где i = 1, n / 2 ¯ , j = 1, k ¯ , соединен с входом разряда Ci,j кода управления многоуровневой коммутационной сетью baseline, каждый переключатель сети j-го уровня, где j = 1, k 1 ¯ , расположенный на линии с номером i, соединен первым выходом Y1 с первым входом X1 при нечетном i или со вторым входом X2 при четном i переключателя j+1 уровня, расположенного на линии с номером u i 1 = I N T ( i + 1 2 ) + 2 k j 1 I N T ( i 2 j 1 ( 2 k 1 + 1 ) ) , а вторым выходом Y2 с первым входом X1 при нечетном i или со вторым входом X2 при четном i переключателя j+1 уровня сети, расположенного на линии с номером u i 2 = I N T ( i + 1 2 ) + 2 k j 1 I N T ( i 2 j 1 ( 2 k 1 + 1 ) ) + 2 k j 1 , где INT - функция вычисления целой части от аргумента; первые входы X1 переключателей первого уровня Ti,1 где i = 1, n / 2 ¯ , являются входами нечетных разрядов X2i-1 n-разрядного входа сети baseline, вторые входы X2 переключателей первого уровня Ti,1, где i = 1, n / 2 ¯ , являются входами четных разрядов X2i, n-разрядного входа сети baseline, первые выходы Y1 переключателей последнего уровня Ti,k, где i = 1, n / 2 ¯ , являются выходами нечетных разрядов Y2i-1 n-разрядного выхода сети baseline, вторые выходы Y2 переключателей последнего уровня Ti,k где i = 1, n / 2 ¯ , являются выходами четных разрядов Y2i, n-разрядного выхода сети baseline. Обратная многоуровневая коммутационная сеть ibaseline состоит из переключателей Ti,j, где i = 1, n / 2 ¯ , j = 1, k ¯ , расположенных в матричном порядке по n/2 линиям и k=log2 n уровням, каждый переключатель имеет два бинарных входа X1, X2, два бинарных выхода Y1, Y2 и бинарный вход управляющего сигнала C, каждый переключатель реализует логические функции Y 1 = C X 1 C ¯ X 2 , Y 2 = C ¯ X 1 C X 2 , бинарные входы управляющих сигналов переключателей сети образуют m-разрядный вход C1,1-Cn/2,k кода управления обратной многоуровневой коммутационной сетью ibaseline, причем бинарный вход C переключателя Ti,j, где i = 1, n / 2 ¯ , j = 1, k ¯ , соединен с входом разряда Ci,j кода управления обратной многоуровневой коммутационной сетью ibaseline, каждый переключатель сети (k-j+1)-го уровня, где j = 1, k 1 ¯ , расположенный на линии с номером i, соединен первым входом X1 с первым выходом Y1 при нечетном i или со вторым выходом Y2 при четном i переключателя (k-j)-го уровня, расположенного на линии с номером u i 1 = I N T ( i + 1 2 ) + 2 j 2 I N T ( i 2 k j ( 2 k 1 + 1 ) ) , а вторым входом X2 с первым выходом Y1 при нечетном i или со вторым выходом Y2 при четном i переключателя (k-j)-го уровня сети, расположенного на линии с номером u i 2 = I N T ( i + 1 2 ) + 2 j 2 I N T ( i 2 k j ( 2 k 1 + 1 ) ) + 2 j 2 , где INT - функция вычисления целой части от аргумента, первые входы X1 переключателей первого уровня Ti,1, где i = 1, n / 2 ¯ , являются входами нечетных разрядов X2i-1 n-разрядного входа сети ibaseline, вторые входы X2 переключателей первого уровня Ti,1, где i = 1, n / 2 ¯ , являются входами четных разрядов X2i n-разрядного входа сети ibaseline, первые выходы Y1 переключателей последнего уровня Ti,k где i = 1, n / 2 ¯ , являются выходами нечетных разрядов Y2i-1 n-разрядного выхода сети ibaseline, вторые выходы Y2 переключателей последнего уровня Ti,k где i = 1, n / 2 ¯ , являются выходами четных разрядов Y2i n-разрядного выхода сети ibaseline. Каждый входной разряд Xi выходного соединителя соединен с выходным разрядом Yj, причем, если i - нечетное число, то j=m, а если i - четное число, то j=m+n/2, где число m определяют путем последовательного вычисления функции ξp(x)=2х-1+ap, где p = 1, k 1 ¯ , аргументом функции ξp является значение функции ξp-1, а аргументом функции ξ1 является 1, значение ap определяют из двоичного представления номера i=ak-12k-1+…+a121+a020. Каждый выходной разряд Yi входного соединителя соединен с входным разрядом Xj, причем, если i - нечетное число, то j=m, а если i - четное число, то j=m+n/2, где число m определяют путем последовательного вычисления функции ξp(x)=2х-1+ap, где p = 1, k 1 ¯ , аргументом функции ξp является значение функции ξp-1, а аргументом функции ξ1 является 1, значение ap определяют из двоичного представления номера i=ak-12k-1+…+a121+a020.

Изобретение поясняется чертежами, где на фиг.1 приведена блок-схема устройства, на фиг.2 приведена схема устройства для случая n=8, где n - число бит входных данных; на фиг.3 приведена схема многоуровневой коммутационной сети baseline для случая n=8; на фиг.4 приведена возможная схема переключателя многоуровневой коммутационной сети baseline или ibaseline; на фиг.5 приведена схема блока формирования битов маскирования и управления осуществлением циклических и логических сдвигов для случая n=8; на фиг.6 приведена схема модуля Mi,j формирования битов кода управления сдвигом; на фиг.7 приведена схема блока мультиплексоров для случая n=8; на фиг.8 приведена схема блока маскирования с использованием логических элементов «2И» для случая n=8; на фиг.9 приведена схема блока побитовой дизъюнкции с использованием логических элементов «2ИЛИ» для случая n=8. Позициями на чертежах обозначены:

1 - многоуровневая коммутационная сеть baseline или обратная многоуровневая коммутационная сеть ibaseline;

2 - блок формирования битов маскирования и управления;

3 - n-разрядный мультиплексор 2→1 входных данных;

4 - n-разрядный мультиплексор 2→1 выходных данных;

5 - n-разрядный блок маскирования данных на входе;

6 - n-разрядный блок маскирования данных на выходе;

7 - m-разрядный мультиплексор 2→1 битов управления, где m=n/2·log2(n);

8 - n-разрядный входной соединитель;

9 - n-разрядный выходной соединитель;

X1-Xn - n-разрядный вход данных многоуровневой коммутационной сети, n-разрядный вход данных n-разрядного блока маскирования данных на входе, n-разрядный вход данных n-разрядного блока маскирования данных на выходе, n-разрядные входы входного и выходного соединителей;

C1,1-Cn/2,k - m-разрядный вход кода управления сетью, где k=log2(n);

X1,1-X1,n - первый n-разрядный вход мультиплексоров 2→1 входных и выходных данных, первый n-разрядный вход n-разрядного мультиплексора 2→1 битов маскирования;

X2,1-X2,n - второй n-разрядный вход мультиплексоров 2→1 входных и выходных данных, второй n-разрядный вход n-разрядного мультиплексора 2→1 битов маскирования;

Y1-Yn - n-разрядные выходы мультиплексоров 2→1 входных и выходных данных, n-разрядные выходы блоков маскирования данных на входе и выходе, n-разрядный выход данных многоуровневой коммутационной сети, n-разрядные выходы входного и выходного соединителей, n-разрядный выход n-разрядного мультиплексора 2→1 битов маскирования;

C1,1,1-C1,n/2,k - первый m-разрядный вход битов управления, где m=n/2·k, k=log2(n);

С2,1,12,n/2,k - второй m-разрядный вход битов управления, где m=n/2·k, k=log2(n);

Y1,1-Yn/2,k - m-разрядный выход мультиплексора, где m=n/2·k, k=log2(n);

C1-Cn-1 - (n-1)-разрядный выход кода управления сдвигом;

А0-Ak-1 - k-разрядный вход значения числа сдвига данных;

AOR - бинарный вход управления маскированием на выходе и мультиплексором входных данных;

RL - бинарный вход управления направлением сдвига данных;

AMUX - бинарный вход управления мультиплексором битов маскирования;

AIOR - бинарный вход управления маскированием на входе;

AOUT - бинарный вход управления мультиплексором выходных данных;

AC - бинарный вход управления мультиплексором битов управления;

F1-Fn - n-разрядный вход битов маскирования;

FO1-FOn - n-разрядный выход битов маскирования выходных данных;

FI1-FIn - n-разрядный выход битов маскирования входных данных;

Ti,j, где i = 1, n / 2 ¯ , i = 1, k ¯ , k=log2(n) - переключатели многоуровневой коммутационной сети baseline с первым Х1 и вторым Х2 бинарными входами данных, первым Y1 и вторым Y2 бинарными выходами данных, бинарным входом кода управления C;

23 - первый блок побитовой дизъюнкции;

24 - второй блок побитовой дизъюнкции;

25 - n-разрядны мультиплексор 2→1 битов маскирования;

Di, где i = 1, n ¯ - логические инверторы;

Mi,j - модули формирования битов кода управления сдвигом, где i = 1,2 j 1 ¯ , j = 1, k ¯ ;

rotr, ci, f - бинарные входы модуля формирования битов кода управления сдвигом;

c, f1, f2 - бинарные выходы модуля формирования битов кода управления сдвигом;

A - бинарный вход управления мультиплексором 2→1;

211, 212, 213 - логические элементы 2И-НЕ;

214 - логический инвертор;

215, 216 - логические элементы 2ИЛИ;

217 - логический элемент 2ИЛИ-НЕ с инверсией сигнала на первом входе;

218 - логический элемент 2ИЛИ-НЕ;

MX - мультиплексоры 2→1 n-разрядного мультиплексора 2→1.

В дальнейшем изложении n означает число двоичных разрядов данных, k=log2(n) - число уровней преобразования, m=n/2·k - число двоичных разрядов кода управления сетью.

Устройство перестановок и сдвигов битов данных в микропроцессорах, предназначенное для осуществления операций логического и циклического сдвига данных, размещения и выборки группы битов данных, и произвольной перестановки битов данных, включает многоуровневую коммутационную сеть baseline или обратную многоуровневую коммутационную сеть ibaseline 1 с n-разрядным входом X1-Xn данных, n-разрядным выходом Y1-Yn данных, m-разрядным входом C1,1-Cn/2,k кода управления сетью.

Устройство также включает блок формирования битов маскирования и управления 2; n-разрядный мультиплексор 2→1 входных данных 3, n-разрядный мультиплексор 2→1 выходных данных 4, n-разрядный блок маскирования данных на входе 5, n-разрядный блок маскирования данных на выходе 6, m-разрядный мультиплексор 2→1 битов управления 7, n-разрядный входной соединитель 8 и n-разрядный выходной соединитель 9.

Вход данных устройства образован n-разрядным входом данных Х1-Xn n-разрядного блока маскирования данных на входе, на n-разрядный вход битов маскирования F1-Fn которого поступают биты с n-разрядного выхода битов маскирования входных данных FI1-FIn блока формирования битов маскирования и управления.

Блок маскирования данных на входе своим n-разрядным выходом Y1-Yn соединен со вторым n-разрядным входом Х2,12,n n-разрядного мультиплексора 2→1 входных данных и с n-разрядным входом Х1-Xn входного соединителя, который своим n-разрядным выходом Y1-Yn соединен с первым n-разрядным входом X1,1-X1,n n-разрядного мультиплексора 2→1 входных данных, бинарный вход управления которого A соединен с входом AOR устройства.

Мультиплексор 2→1 входных данных своим n-разрядным выходом Y1-Yn соединен с n-разрядным входом данных Х1-Xn многоуровневой коммутационной сети, которая своим n-разрядным выходом Y1-Yn соединена с n-разрядным входом данных n-разрядного блока маскирования данных на выходе.

Многоуровневая коммутационная сеть своим m-разрядным входом C1,1-Cn/2,k кода управления сетью соединена с m-разрядным выходом Y1,1-Yn/2,k m-разрядного мультиплексора 2→1 битов управления, имеющего первый m-разрядный вход C1,1,1-C1,n/2,k, бинарный вход управления AC, а второй m-разрядный вход С2,1,12,n/2,k, соединенный с (n-1)-разрядным выходом C1-Cn-1 кода управления сдвигом. При этом, если используется многоуровневая коммутационная сеть baseline, бит первого разряда С1 кода управления сдвигом подается на входы разрядов C2,1,1-C2,n/2,1 m-разрядного входа мультиплексора 2→1 битов управления, бит второго разряда C2 кода управления сдвигом подается на входы разрядов C2,1,2-C2,n/4,2 m-разрядного входа мультиплексора 2→1 битов управления, бит третьего разряда C3 кода управления сдвигом подается на входы разрядов C2,n/4+1,2-C2,n/2,2 m-разрядного входа мультиплексора 2→1 битов управления и т.д. В общем случае бит i-го разряда Ci, i = 1, n 1 ¯ , кода управления сдвигом подается на входы С2,q,r m-разрядного входа мультиплексора 2→1 битов управления, где

INT(i-2r-1)·2k-r<q<(INT((i-2r-1))+1)·2k-r+1, r=INT(log2(i))+1,

INT(x) - функция, выделяющая целую часть аргмента x.

При использовании сети ibaseline вместо сети baseline на входы разрядов C2,q,j, где j = 1, k ¯ , q = 1, n / 2 ¯ , m-разрядного входа мультиплексора 2→1 битов управления подают бит i-го разряда Ci (n-1)-разрядного выхода C1-Cn-1 кода управления сдвигом, причем i=mod(q-1,2j-1)+2j-1, где mod(q-1,2j-1) - функция, вычисляющая число q-1 по модулю 2j-1.

n-разрядный выход Y1-Yn блока маскирования данных на выходе соединен с входом Х1-Xn n-разрядного выходного соединителя и с первым n-разрядным входом мультиплексора 2→1 выходных данных, выход Y1-Yn n-разрядного выходного соединителя соединен со вторым n-разрядным входом мультиплексора 2→1 выходных данных. Вход управления A n-разрядного мультиплексора 2→1 выходных данных соединен с входом AOUT устройства, а n-разрядный выход Y1-Yn мультиплексора 2→1 выходных данных является выходом данных устройства.

n-разрядный выход FO1-FOn битов маскирования выходных данных блока формирования битов маскирования и управления соединен с n-разрядным входом F1-Fn битов маскирования n-разрядного блока маскирования данных на выходе.

Входы AIOR, RL, AMUX, A0-Ak-1, F1-Fn устройства образованы входами AIOR, RL, AMUX, A0-Ak-1, F1-Fn блока формирования битов маскирования и управления. Вход AOR устройства соединен с входом AOR блока формирования битов маскирования и управления и с входом управления A n-разрядного мультиплексора 2→1 входных данных.

Упомянутая ранее многоуровневая коммутационная сеть baseline имеет n бинарных входов, n бинарных выходов и состоит из переключателей Ti,j, где i = 1, n / 2 ¯ , j = 1, k ¯ , расположенных в матричном порядке по n/2 линиям и k=log2n уровням, каждый переключатель имеет два бинарных входа Х1, Х2, два бинарных выхода Y1, Y2 и бинарный вход управляющего сигнала, переключатели реализуют логическую функцию Y 1 = C X 1 C ¯ X 2 , Y 2 = C ¯ X 1 C X 2 , где знак ∨ означает логическую операцию дизъюнкция (логическое ИЛИ), знак ∧ означает логическую операцию конъюнкция (логическое И), а подчеркивание сверху означает операцию логического отрицания.

Бинарные входы управляющих сигналов переключателей сети образуют m-разрядный вход C1,1-Cn/2,k кода управления многоуровневой коммутационной сетью baseline, причем бинарный вход C переключателя Ti,j, где i = 1, n / 2 ¯ , j = 1, k ¯ , соединен с входом разряда Ci,j кода управления многоуровневой коммутационной сетью baseline.

Каждый переключатель сети baseline j-го уровня, где j = 1, k 1 ¯ , расположенный на линии с номером i, соединен одним выходом с входом переключателя j+1 уровня, расположенного на линии с номером u i 1 = I N T ( i + 1 2 ) + 2 k j 1 I N T ( i 2 j 1 ( 2 k 1 + 1 ) ) , a другим выходом с входом переключателя j+1 уровня сети baseline, расположенного на линии с номером u i 2 = I N T ( i + 1 2 ) + 2 k j 1 I N T ( i 2 j 1 ( 2 k 1 + 1 ) ) , где INT - функция вычисления целой части от аргумента, каждый вход каждого переключателя уровня j+1 соединен с одним выходом переключателя уровня j. Первые входы X1 переключателей первого уровня Ti,1, где i = 1, n / 2 ¯ , являются входами нечетных разрядов X2i-1 n-разрядного входа сети baseline, вторые входы X2 переключателей первого уровня Ti,1, где i = 1, n / 2 ¯ , являются входами четных разрядов X2i, n-разрядного входа сети baseline, первые выходы Y1 переключателей последнего уровня Ti,k где i = 1, n / 2 ¯ , являются выходами нечетных разрядов Y2i-1 n-разрядного выхода сети baseline, вторые выходы Y2 переключателей последнего уровня Ti,k, где i = 1, n / 2 ¯ , являются выходами четных разрядов Y2i, n-разрядного выхода сети baseline.

На фиг.3 изображена схема многоуровневой коммутационной сети baseline для случая n=8. Переключатели сети расположены в матричном порядке на четырех линиях и трех уровнях. На фиг.4 изображена возможная схема переключателя Ti,j, где 111, 112 - мультиплексоры 2→1.

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

Обратная многоуровневая коммутационная сеть ibaseline состоит из переключателей Ti,j, где i = 1, n / 2 ¯ , j = 1, k ¯ расположенных в матричном порядке по n/2 линиям и k=log2n уровням, каждый переключатель имеет два бинарных входа Х1, Х2, два бинарных выхода Y1, Y2 и бинарный вход управляющего сигнала, каждый переключатель реализует логическую функцию Y 1 = C X 1 C ¯ X 2 , Y 2 = C ¯ X 1 C X 2 , бинарные входы управляющих сигналов переключателей сети образуют m-разрядный вход C1,1-Cn/2,k кода управления обратной многоуровневой коммутационной сетью ibaseline, причем бинарный вход С переключателя Ti,j, где i = 1, n / 2 ¯ , j = 1, k ¯ , соединен с входом разряда Ci,j кода управления обратной многоуровневой коммутационной сетью ibaseline, каждый переключатель сети (k-j+1)-го уровня, где j = 1, k 1 ¯ , расположенный на линии с номером i, соединен одним входом с выходом переключателя (k-j)-го уровня, расположенного на линии с номером u i 1 = I N T ( i + 1 2 ) + 2 j 2 I N T ( i 2 k j ( 2 k 1 + 1 ) ) , а другим входом с выходом переключателя (k-j)-го уровня сети, расположенного на линии с номером u i 2 = I N T ( i + 1 2 ) + 2 j 2 I N T ( i 2 k j ( 2 k 1 + 1 ) ) + 2 j 2 , где INT - функция вычисления целой части от аргумента, каждый выход каждого переключателя (k-j)-го уровня соединен с одним входом переключателя (k-j+1)-го уровня, первые входы X1 переключателей первого уровня Ti,1, где i = 1, n / 2 ¯ , являются входами нечетных разрядов X2i-1 n-разрядного входа сети ibaseline, вторые входы X2 переключателей первого уровня Ti,1, где i = 1, n / 2 ¯ , являются входами четных разрядов X2i n-разрядного входа сети ibaseline, первые выходы Y1 переключателей последнего уровня Ti,k, где i = 1, n / 2 ¯ , являются выходами нечетных разрядов Y2i-1 n-разрядного выхода сети ibaseline, вторые выходы Y2 переключателей последнего уровня Ti,k, где i = 1, n / 2 ¯ , являются выходами четных разрядов Y2i, n-разрядного выхода сети ibaseline.

Блок формирования битов маскирования и управления (см. фиг.5) характеризуется наличием бинарных входов управления AOR, RL, AMUX, AIOR, k-разрядного входа А0-Ak-1 значения числа сдвига данных, n-разрядного входа битов маскирования данных F1-Fn, образующих соответстующие входы предлагаемого устройства. Блок формирования битов маскирования и управления характеризуется также наличием n-разрядного выхода FI1-FIn битов маскирования входных данных, n-разрядного выхода FOI-FOn битов маскирования выходных данных, (n-1)-разрядного выхода С1-Cn-1 кода управления сдвигом, образующих соответстующие выходы предлагаемого устройства.

Блок формирования битов маскирования и управления включает идентичные первый 23 и второй 24 блоки побитовой дизъюнкции (см. фиг.9), каждый из которых характеризуется наличием n-разрядного входа данных, n-разрядного выхода данных, входа управления AOR для блока 23 или AIOR для блока 24. Блок побитовой дизъюнкции 23 осуществляет логические функции побитовое логическое ИЛИ, т.е. Yi=Xi∨AOR, где i = 1, n ¯ . Блок побитовой дизъюнкции 24 осуществляет логические функции побитовое логическое ИЛИ, т.е. FIi=Xi∨AIOR, где i = 1, n ¯ .

Блок формирования битов маскирования и управления также включает мультиплексор битов маскирования 25, имеющий первый n-разрядный вход X1,1-X1,n, второй n-разрядный вход Х2,12,n, n-разрядный выход FO1-FOn битов маскирования выходных данных и бинарный вход управления AMUX.

Блок формирования битов маскирования и управления также включает n/2 логических инверторов и n-1 модуль Mi,j, где i = 1,2 j 1 ¯ , j = 1, k ¯ , формирования битов кода управления сдвигом, каждый из которых имеет три бинарных входа f, ci, rotr и три бинарных выхода с, f1, f2, и выполняет три логических функции c = f c i f c i ¯ , f 1 = ( r o t r ¯ f c i ¯ ) ( f c i ¯ ) ¯ , f 2 = ( r o t r f c i ¯ ) ( f c i ¯ ) ¯ . На языке Verilog эти логические функции описываются следующим образом:

c=f&ci|~(f|ci);

f1=~((~rotr|~(f|ci))&~(f&ci));

f2=~((rotr|~(f|ci))&~(f&ci));

На фиг.6 приведена возможная схема модуля формирования битов кода управления сдвигом Mi,j, где i = 1,2 j 1 ¯ , j = 1, k ¯ .

Модули формирования битов кода управления соединены так, что образуют двоичное дерево (пирамидальную структуру) с k уровнями. При этом на первом уровне двоичного дерева содержится один модуль M1,1, выход с которого соединен с выходом С1 блока формирования битов маскирования и управления. На втором уровне двоичного дерева содержится два модуля: М1,2, выход с которого соединен с выходом C2 блока формирования битов маскирования и управления, и M2,2, выход с которого соединен с выходом C3 блока формирования битов маскирования и управления. На третьем уровне двоичного дерева содержится четыре модуля M1,3, M2,3, M3,3, M4,3, выходы с которых соответственно соединены с выходами С4, С5, C6, C7, блока формирования битов маскирования и управления. В общем случае на уровне j, где j = 1, k ¯ , содержится 2j-1 модулей Mi,j, где i = 1,2 j 1 ¯ , причем выход с каждого из модулей Mi,j соединен с выходом Cp блока формирования битов маскирования и управления, где р=2j-1+i-1.

Выход f1 каждого модуля Mi,j, где i = 1,2 j 1 ¯ , формирования битов кода управления, расположенного на уровне j, где j = 1, k ¯ , соединен с входом f модуля M2i-1,j+1, расположенного на уровне j+1. Выход f2 каждого модуля Mi,j, где i = 1,2 j 1 ¯ , формирования битов кода управления сдвигом, расположенного на уровне j, где j = 1, k ¯ , соединен с входом f модуля M2i,j+1, расположенного на уровне j+1. На вход f модуля М1,1 формирования битов кода управления подается сигнал с низким логическим уровнем. Вход ci каждого модуля Mi,j формирования битов кода управления сдвигом, расположенного на уровне j, где i = 1,2 j 1 ¯ , соединен с входом разряда Aj-1 k-разрядного входа A0-Ak-1 значения числа сдвига данных, расположенного в блоке формирования битов маскирования и управления.

Вход rotr каждого модуля Mi,j соединен с бинарным входом управления направлением сдвига данных RL.

Выход f1 каждого модуля Mi,k, расположенного на последнем k-м уровне, где i = 1, n / 2 ¯ , соединен с входом логического инвертора D2i-1. Выход f2 каждого модуля Mi,k расположенного на последнем k-м уровне, где i = 1, n / 2 ¯ , соединен с входом логического инвертора D2i. Каждый выход логического инвертора Di, где i = 1, n ¯ , соединен с разрядом X1,i, где i = 1, n ¯ , первого n-разрядного входа мультиплексора битов маскирования 25, n-разрядный выход которого Y1-Yn соединен с n-разрядным выходом FO1-FOn блока формирования битов маскирования и управления.

В блоке формирования битов маскирования и управления n-разрядный вход F1-Fn битов маскирования соединен с n-разрядным входом Х1-Xn первого блока побитовой дизъюнкции 23 и с n-разрядным входом Х1-Xn второго блока побитовой дизъюнкции 24. n-разрядный выход Y1-Yn первого блока побитовой дизъюнкции 23 соединен со вторым n-разрядным входом Х2,12,n мультиплексора битов маскирования 25. Бинарный вход AOR первого блока побитовой дизъюнкции 23 является входом AOR устройства. Бинарный вход AIOR второго блока побитовой дизъюнкции 24 является входом AIOR устройства. n-разрядный выход FI1-FIn 23 является выходом блока формирования битов маскирования и управления.

Вход AMUX мультиплексора битов маскирования 25 является входом предлагаемого устройства.

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

Упомянутые ранее n-разрядные мультиплексоры 2→1 входных данных и n-разрядный мультиплексор 2→1 выходных данных представляют собой одинаковые модули, каждый из которых имеет первый n-разрядный вход данных, второй n-разрядный вход данных, n-разрядный выход данных и бинарный вход управления. Если на вход поступает сигнал с низким логическим уровнем, на n-разрядный выход мультиплексора поступают сигналы с первого n-разрядного входа данных. Если на вход поступает сигнал с высоким логическим уровнем, на n-разрядный выход мультиплексора поступают сигналы со второго n-разрядного входа данных.

Упомянутый ранее m-разрядный мультиплексор 2→1 аналогичен описанному выше n-разрядному мультиплексору 2→1, но имеет m-разрядные входы данных C1,1,1-C1,n/2,k, С2,1,12,n/2k и m-разрядный выход данных Y1,1-Yn/2,k.

Описание и способ построения n-разрядных мультиплексоров 2→1 известен в технике, их можно найти, например, в справочнике: Пухальский Г.И., Новосельцева Т.Я. Проектирование дискретных устройств на интегральных микросхемах: Справочник. М.: Радио и связь, 1990. 304 с.

Выходной соединитель имеет n-разрядный вход Х1-Xn данных, n-разрядный выход Y1-Yn данных, где каждый входной разряд Xi с номером i, i = 1, n ¯ , соединен с выходным разрядом Yj с номером j, причем, если i - нечетное число, то j=m, если i - четное число, то j=m+n/2, где m=ξk-1(…ξ21(1)))…), ξр(х)=2х-1+ар значение ар, где p = 1, k 1 ¯ , определяется двоичным представлением i: i=ak-12k-1+…+a121+a020. Таким образом, число m определяется путем последовательного вычисления функции ξр, где p = 1, k 1 ¯ , аргументом функции ξp является значение функции ξp-1, а аргументом функции является 1.

Входной соединитель имеет n-разрядный вход Х1-Xn данных, n-разрядный выход Y1-Yn данных, где каждый выходной разряд Yi с номером i, i = 1, n ¯ соединен с входным разрядом Xj с номером j, причем, если i - нечетное число, то j=m, если i - четное число, то j=m+n/2, где m=ξk-1(…ξ21(1)))…), ξp(x)=2x-1+ap значение ар, где p = 1, k 1 ¯ , определяется двоичным представлением номера i: i=ak-12k-1+…+a121+a020. Таким образом, число m определяется путем последовательного вычисления функции ξр, где p = 1, k 1 ¯ , аргументом функции ξр является значение функции ξp-1, а аргументом функции ξ1 является 1.

Обозначения блоков, приведенные на фиг.2, совпадают с обозначениями на фиг.1. Входной и выходной соединители не показаны на фиг.2 в виде блоков, а реализованы описанным выше способом соединения выхода блока маскирования данных на входе с первым входом мультиплексора входных данных, а также описанным выше способом соединения выхода Y1-Yn блока маскирования данных на выходе со вторым входом Х2,12,n мультиплексора выходных данных.

Устройство работает следующим образом.

Режим работы устройства задается подачей на бинарные входы управления AOR, RL, AMUX, AIOR, AOUT, AC управляющих сигналов в соответствии с табл.1

Табл.1
Сигналы управления устройством перестановок и сдвигов битов данных
Инструкции RL AOUT AC AMUX AOR AIOR
shr r1=r2,r3 0 1 1 0 1 -
shl r1=r2,r3 1 1 1 0 1 -
rotr r1=r2,r3 0 1 1 1 1 1
rotl r1=r2,r3 1 1 1 1 1 1
рех r1=r2, ar.b1, ar.b2, ar.b3 - 1 0 1 1 0
pdep r1=r2, ar.b1, ar.b2, ar.b3 - 0 0 1 0 1
bsn r1=r2, ar.b1, ar.b2, ar.b3 или ibsn r1=r2, ar.b1, ar.b2, ar.b3 - 0 0 1 1 1

Краткое описание инструкций из табл.1 приведено в табл.2. Подробное описание инструкций из табл.1 можно найти, например, в статье «Методы синтеза устройств, выполняющих инструкции перестановки битов данных». / Сотов Л.С. // Гетеромагнитная микроэлектроника. 2011. Вып.10. С.25-50.

Табл.2
Инструкции манипуляции битами данных
Инструкция Описание
bsn r1=r2, ar.b1, ar.b2, ar.b3 или ibsn r1=r2, ar.b1, ar.b2, ar.b3 Осуществление инструкции перестановки битов данных с использованием многоуровневой коммутационной сети baseline или ibaseline в соответствии с управляющими кодами в регистрах ar.b1, ar.b2, ar.b3 микропроцессора и запись результата в регистр r1 микропроцессора.
рех r1=r2, r3, ar.b1, ar.b2, ar.b3 Статическая инструкция извлечения группы битов из регистра r2 и размещение их в начале регистра r1 в соответствии с управляющими кодами в регистрах ar.b1, ar.b2, ar.b3 микропроцессора и запись результата в регистр r1 микропроцессора и запись результата в регистр r1 микропроцессора.
pder r1=r2, r3, ar.b1, ar.b2, ar.b3 Статическая инструкция размещения группы битов регистра r2 в регистре r1 в соответствии с управляющими кодами в регистрах ar.b1, ar.b2, ar.b3 микропроцессора и запись результата в регистр r1 микропроцессора.
shr r1=r2, r3 Логический сдвиг данных в регистре r2 микропроцессора вправо на число бит, содержащееся в регистре r3 микропроцессора и запись результата в регистр r1 микропроцессора.
shl r1=r2, r3 Логический сдвиг данных в регистре r2 микропроцессора вправо на число бит, содержащееся в регистре r3 микропроцессора и запись результата в регистр r1 микропроцессора.
rotr r1=r2, r3 Циклический сдвиг данных в регистре r2 микропроцессора вправо на число бит, содержащееся в регистре r3 микропроцессора и запись результата в регистр r1 микропроцессора.
rotl r1=r2, r3 Циклический сдвиг данных в регистре r2 микропроцессора вправо на число бит, содержащееся в регистре r3 микропроцессора и запись результата в регистр r1 микропроцессора.

На вход Х1-Xn n-разрядного блока маскирования данных на входе подаются входные данные, например, из регистра r2 микропроцессора. При реализации инструкций рех или pdep на n-разрядный вход битов маскирования F1-Fn блока формирования битов маскирования и управления подаются биты маскирования, например, из регистра r3 микропроцессора. Для реализации инструкций bsn, рех или pdep на первый m-разрядный вход C1,1,1-C1,n/2,k битов управления мультиплексора битов управления подаются коды управления, например, из регистров ar.b1, ar.b1, ar.b2, ar.b3 микропроцессора. Для осуществления инструкций shr, shl, rotr, rotl, логического и циклического сдвигов на k-разрядный вход A0-Ak-1 подается значение числа сдвига данных. Значение числа сдвига данных может содержаться, например, в младших битах регистра r2 микропроцессора, так как при выполнении инструкций shr, shl биты маскирования формируются блоком формирования битов маскирования и управления, а при выполнении инструкций rotr, rotl биты маскирования не используются.

После выполнения одной из инструкций bsn, рех, pdep, shr, shl, rotr или rotl результат формируется на n-разрядном выходе Y1-Yn мультиплексора выходных данных и записывается, например, в регистр r1 микропроцессора.

Рассмотрим отдельно пути прохождения данных в схемах модуля манипуляции битами, представленных на фиг.1, фиг.2, при реализации инструкций bsn, рех, pdep, shr, shl, rotr или rotl.

При выполнении инструкции bsn на n-разрядный вход Х1-Xn блока маскирования данных на входе поступают данные, которые без изменения проходят через этот блок, поступают на второй вход мультиплексора входных данных и с его выхода Y1-Yn на вход многоуровневой коммутационной сети. Одновременно через первый вход и затем выход n-разрядного мультиплексора биты управления переключателями сети поступают на вход C1,1-Cn/2,k управления переключателями коммутационной сети. С выхода Y1-Yn сети перестановленные биты данных без изменения проходят через блок маскирования данных на выходе и поступают на выход модуля манипуляции битами через первый вход, а затем выход мультиплексора выходных данных.

При выполнении инструкции pex биты данных поступают на n-разрядный вход Х1-Xn блока маскирования данных на входе, на второй вход F1-Fn которого подаются биты маскирования с выхода FI1-FIn блока формирования битов маскирования и управления. Маскированные данные через второй вход, а затем выход мультиплексора входных данных поступают на вход многоуровневой коммутационной сети. Одновременно через первый вход и затем выход m-разрядного мультиплексора биты управления переключателями сети поступают на вход C1,1-Cn/2,k управления переключателями коммутационной сети. С выхода сети данные, проходя без изменения через блок маскирования данных на выходе, подаются на вход выходного соединителя и, проходя через него, поступают на второй вход мультиплексора выходных данных и далее попадают на его выход.

При выполнении инструкции pdep данные поступают на n-разрядный вход Х1-Xn блока маскирования данных на входе, проходят его без изменений и через входной соединитель поступают на первый вход мультиплексора входных данных и с выхода этого мультиплексора поступают на вход многоуровневой коммутационной сети. Одновременно через первый вход и затем выход m-разрядного мультиплексора биты управления переключателями сети поступают на вход C1,1-Cn/2,k управления переключателями коммутационной сети. Далее данные поступают на вход блока маскирования данных на выходе, на второй вход которого поступают биты маскирования с выхода FO1-FOn блока формирования битов маскирования и управления. Маскированные на выходе данные через выходной соединитель поступают на второй вход и затем на выход мультиплексора выходных данных, формируя, таким образом, выходные данные предлагаемого устройства.

При выполнении инструкций shr, shl, rotr, rotl биты данных поступают на n-разрядный вход Х1-Xn блока маскирования данных на входе и проходят его без изменений. С выхода блока маскирования данных на входе данные через второй вход, а затем выход мультиплексора входных данных поступают на вход многоуровневой коммутационной сети. Управление осуществляется путем подачи на вход C1,1-Cn/2,k сети кодов управления с выхода C1-Cn-1 блока формирования битов маскирования и управления через второй вход и затем выход мультиплексора битов управления. С выхода сети данные поступают на вход блока маскирования данных на выходе.

При выполнении инструкций rotr, rotl на второй вход F1-Fn блока маскирования данных на выходе подаются сигналы с высоким логическим уровнем и данные без изменений подаются на вход выходного соединителя, проходя через который, поступают на второй вход мультиплексора выходных данных и далее попадают на его выход.

При выполнении инструкций shr, shl на второй вход F1-Fn блока маскирования данных на выходе подаются сигналы маскирования и маскированные данные подаются на вход выходного соединителя, проходя через который, поступают на второй вход мультиплексора выходных данных и далее попадают на его выход.

Таким образом, при одинаковой функциональности с существующими решениями предлагаемое устройство имеет более простую конструкцию за счет использования только одной многоуровневой коммутационной сети с топологией baseline или ibaseline для выполнения произвольных перестановок, циклических и логических сдвигов данных, операций извлечения и размещения в заданных позициях групп битов данных. Предложенное решение имеет расширенную функциональность по сравнению с используемыми устройствами логического и циклического сдвига и позволяет вычислять циклические и логические сдвиги данных, операции извлечения и размещения в заданных позициях групп битов данных за один цикл микропроцессора. Произвольные перестановки осуществляются за два цикла процессора с последовательным использованием двух команд bsn. При этом сохраняется высокое быстродействие устройства, что существенно повышает производительность микропроцессоров при решении задач обработки изображений, распознавания образов, кодирования, стеганографии, криптографии, обработки сигналов и т.п.

1. Устройство перестановок и сдвигов битов данных в микропроцессорах, характеризующееся тем, что включает многоуровневую коммутационную сеть baseline или обратную многоуровневую коммутационную сеть ibaseline, с n-разрядным входом данных X1-Xn, n-разрядным выходом данных Y1-Yn, m-разрядным входом C1,1-Cn/2,k кода управления сетью; устройство также включает n-разрядный мультиплексор 2→1 входных данных с первым n-разрядным входом X1,1-X1,n, вторым n-разрядным входом X2,1-X2,n, входом управления A, соединенным с бинарным входом AOR управления маскированием на выходе и мультиплексором входных данных устройства, n-разрядным выходом Y1-Yn, соединенным с n-разрядным входом данных X1-Xn многоуровневой коммутационной сети; устройство также включает n-разрядный входной соединитель с n-разрядным входом X1-Xn и n-разрядным выходом Y1-Yn, соединенным с первым n-разрядным входом X1,1-X1,n n-разрядного мультиплексора 2→1 входных данных, входной соединитель обеспечивает фиксированные соединения входных и выходных разрядов; устройство также включает n-разрядный блок маскирования данных на входе с первым n-разрядным входом данных X1-Xn, вторым n-разрядным входом F1-Fn, n-разрядным выходом Y1-Yn, соединенным с n-разрядным входом X1-Xn входного соединителя и со вторым n-разрядным входом Х2,12,n, n-разрядного мультиплексора 2→1 входных данных; устройство также включает m-разрядный мультиплексор 2→1 битов управления с входом управления AC, первым m-разрядным входом C1,1,1-C1,n/2,k битов управления, вторым m-разрядным входом C2,1,1-C2,n/2,k битов управления, m-разрядным выходом Y1,1-Yn/2,k, соединенным с m-разрядным входом C1,1-Cn/2,k кода управления сетью; устройство также включает блок формирования битов маскирования и управления, с бинарным входом AOR, соединенным с бинарным входом управления маскированием на выходе и мультиплексором входных данных устройства, бинарным входом RL управления направлением сдвига данных, бинарным входом AMUX управления мультиплексором битов маскирования, бинарным входом AIOR управления маскированием на входе, n-разрядным входом F1-Fn битов маскирования, k-разрядным входом A0-Ak-1 значения числа сдвига данных, n-разрядным выходом FI1-FIn битов маскирования входных данных, соединенным со вторым n-разрядным входом F1-Fn блока маскирования данных на входе, n-разрядным выходом FO1-FOn битов маскирования выходных данных, (n-1)-разрядным выходом C1-Cn-1 кода маскирования данных на входе, (n-1)-разрядным выходом C1-Cn-1 кода управления сдвигом, соединенным с вторым m разрядным входом C2,1,1-C2,n/2,k битов управления мультиплексора 2→1 битов управления; устройство также включает n-разрядный блок маскирования данных на выходе с первым n-разрядным входом X1-Xn, соединенным с n-разрядным выходом данных Y1-Yn многоуровневой коммутационной сети, вторым n-разрядным входом F1-Fn, соединенным с n-разрядным выходом битов маскирования выходных данных FO1-FOn, n-разрядным выходом Y1-Yn; устройство также включает n-разрядный выходной соединитель с n-разрядным выходом Y1-Yn, n-разрядным входом X1-Xn, соединенным с n-разрядным выходом Y1-Yn n-разрядного блока маскирования данных на выходе, выходной соединитель обеспечивает фиксированные соединения входных и выходных разрядов; устройство также включает n-разрядный мультиплексор 2→1 выходных данных с первым n-разрядным входом X1,1-X1,n, соединенным с n-разрядным выходом Y1-Yn n-разрядного блока маскирования данных на выходе, вторым n-разрядным входом Х2,12,n, соединенным с n-разрядным выходом Y1-Yn n-разрядного выходного соединителя, входом управления А, соединенным с бинарным входом управления мультиплексором выходных данных AOUT устройства, n-разрядным выходом данных Y1-Yn.

2. Устройство по п.1, характеризующееся тем, что при использовании сети baseline бит i-го разряда Ci, i = 1, n 1 ¯ кода управления сдвигом подают на входы разрядов C2,q,r второго m-разрядного входа мультиплексора битов управления, где индекс q - целое число и INT(i-2r-1)·2k-r<q<(INT((i-2r-l))+1)·2k-r+1, r=INT(log2(i))+1, INT - функция, выделяющая целую часть аргумента.

3. Устройство по п.1, характеризующееся тем, что при использовании сети ibaseline на входы разрядов C2,q,j, где j = 1, k ¯ , q = 1, n / 2 ¯ , второго m-разрядного входа мультиплексора битов управления подают бит i-го разряда Ci (n-1)-разрядного выхода C1-Cn-1 кода управления сдвигом, причем i=mod(q-1,2j-1)+2j-1, где mod(q-1,2j-1) - функция, вычисляющая число q-1 по модулю 2j-1.

4. Устройство по п.1, характеризующееся тем, что блок формирования битов маскирования и управления включает первый блок побитовой дизъюнкции с n-разрядным входом данных Х1-Xn, соединенным с n-разрядным входом F1-Fn битов маскирования, n-разрядным выходом данных Y1-Yn, и входом AOR, первый блок побитовой дизъюнкции осуществляет функции побитовое логическое ИЛИ Yi=Xi∨AOR, где i = 1, n ¯ ; блок формирования битов маскирования и управления также включает n-разрядный мультиплексор битов маскирования, с выходом FO1-FOn, первым n-разрядным входом X1,1-X1,n, вторым n-разрядным входом Х2,12,n, соединенным выходом Y1-Yn первого блока побитовой дизъюнкции, входом AMUX, блок формирования битов маскирования и управления также включает n логических инверторов D1-Dn и n-1 модуль формирования битов кода управления сдвигом Mi,j, где i = 1,2 j 1 ¯ , j = 1, k ¯ , каждый из которых имеет три бинарных входа f, ci, rotr, три бинарных выхода с, f1, f2, и выполняет логические функции: c = f c i f c i ¯ , f 1 = ( r o t r ¯ f c i ¯ ) ( f c i ¯ ) ¯ , f 2 = ( r o t r f c i ¯ ) ( f c i ¯ ) ¯ , входы rotr всех модулей Mi,j соединены с входом RL, модули Mi,j соединены так, что образуют двоичное дерево с k уровнями, при этом на уровне j содержится 2j-1 модулей Mi,j, причем выход с каждого из модулей Mi,j соединен с выходом Ср блока формирования битов маскирования и управления, где p=2j-1+i-1, выход f1 каждого модуля Mi,j, расположенного на уровне j, соединен с входом f модуля M2i-1,j+1, расположенного на уровне j+1, выход f2 каждого модуля Mi,j, расположенного на уровне j, соединен с входом f модуля M2i,j+1, расположенного на уровне j+1, вход f модуля М1,1 предназначен для сигнала с низким логическим уровнем, вход ci каждого модуля Mi,j, расположенного па уровне j, соединен с входом разряда Aj-1 входа A0-Ak-1, выход f1 каждого модуля Mi,k, расположенного на k-м уровне, соединен с входом логического инвертора D2i-1, выход f2 каждого модуля Mi,k, расположенного на k-м уровне, где i = 1, n / 2 ¯ , соединен с входом логического инвертора D2i, каждый выход логического инвертора Di, где i = 1, n ¯ , соединен с разрядом Х1,i первого входа мультиплексора битов маскирования; блок формирования битов маскирования и управления включает второй блок побитовой дизъюнкции с n-разрядным входом данных Х1-Xn, соединенным с n-разрядным входом F1-Fn битов маскирования, выходом FI1-FIn, входом AIOR, второй блок побитовой дизъюнкции осуществляет функции побитовое логическое ИЛИ Yi=Xi∨AIOR, где i = 1, n ¯ .

5. Устройство по п.1, характеризующееся тем, что многоуровневая коммутационная сеть baseline состоит из переключателей Ti,j, где i = 1, n / 2 ¯ , j = 1, k ¯ , расположенных в матричном порядке по n/2 линиям и k=log2n уровням, каждый переключатель имеет два бинарных входа Х1, Х2, два бинарных выхода Y1, Y2 и бинарный вход управляющего сигнала С, каждый переключатель реализует логические функции Y 1 = C X 1 C ¯ X 2 , Y 2 = C ¯ X 1 C X 2 , бинарные входы управляющих сигналов переключателей сети образуют m-разрядный вход C1,1-Cn/2,k кода управления многоуровневой коммутационной сетью baseline, причем бинарный вход С переключателя Ti,j, где i = 1, n / 2 ¯ , j = 1, k ¯ , соединен с входом разряда Ci,j, кода управления многоуровневой коммутационной сетью baseline, каждый переключатель сети j-го уровня, где j = 1, k 1 ¯ , расположенный на линии с номером i, соединен первым выходом Y1 с первым входом X1 при нечетном i или со вторым входом Х2 при четном i переключателя j+1 уровня, расположенного на линии с номером u i 1 = I N T ( i + 1 2 ) + 2 k j 1 I N T ( i 2 j 1 ( 2 k 1 + 1 ) ) ,
а вторым выходом Y2 с первым входом X1 при нечетном i или со вторым входом Х2 при четном i переключателя j+1 уровня сети, расположенного на линии с номером u i 2 = I N T ( i + 1 2 ) + 2 k j 1 I N T ( i 2 j 1 ( 2 k 1 + 1 ) ) + 2 k j 1 ,
где INT - функция вычисления целой части от аргумента; первые входы X1 переключателей первого уровня Ti,1, где i = 1, n / 2 ¯ , являются входами нечетных разрядов X2i-1 n-разрядного входа сети baseline, вторые входы Х2 переключателей первого уровня Ti,1, где i = 1, n / 2 ¯ , являются входами четных разрядов X2i, n-разрядного входа сети baseline, первые выходы Y1 переключателей последнего уровня Ti,k, где i = 1, n / 2 ¯ , являются выходами нечетных разрядов Y2i-1 n-разрядного выхода сети baseline, вторые выходы Y2 переключателей последнего уровня Ti,k, где i = 1, n / 2 ¯ , являются выходами четных разрядов Y2i n-разрядного выхода сети baseline.

6. Устройство по п.1, характеризующееся тем, что обратная многоуровневая коммутационная сеть ibaseline состоит из переключателей Ti,j, где i = 1, n / 2 ¯ , j = 1, k ¯ , расположенных в матричном порядке по n/2 линиям и k=log2n уровням, каждый переключатель имеет два бинарных входа X1, Х2, два бинарных выхода Y1, Y2 и бинарный вход управляющего сигнала С, каждый переключатель реализует логические функции Y 1 = C X 1 C ¯ X 2 , Y 2 = C ¯ X 1 C X 2 , бинарные входы управляющих сигналов переключателей сети образуют m-разрядный вход C1,1-Cn/2,k кода управления обратной многоуровневой коммутационной сетью ibaseline, причем бинарный вход С переключателя Ti,j, где i = 1, n / 2 ¯ , j = 1, k ¯ , соединен с входом разряда Ci,j кода управления обратной многоуровневой коммутационной сетью ibaseline, каждый переключатель сети (k-j+1)-го уровня, где j = 1, k 1 ¯ , расположенный на линии с номером i, соединен первым входом X1 с первым выходом Y1 при нечетном i или со вторым выходом Y2 при четном i переключателя (k-j)-го уровня, расположенного на линии с номером u i 1 = I N T ( i + 1 2 ) + 2 j 2 I N T ( i 2 k j ( 2 k 1 + 1 ) ) ,
а вторым входом X2 с первым выходом Y1 при нечетном i или со вторым выходом Y2 при четном i переключателя (k-j)-го уровня сети, расположенного на линии с номером u i 2 = I N T ( i + 1 2 ) + 2 j 2 I N T ( i 2 k j ( 2 k 1 + 1 ) ) + 2 j 2 ,
где INT - функция вычисления целой части от аргумента, первые входы X1 переключателей первого уровня Ti,1, где i = 1, n / 2 ¯ , являются входами нечетных разрядов X2i-1 n-разрядного входа сети ibaseline, вторые входы Х2 переключателей первого уровня Ti,1, где i = 1, n / 2 ¯ , являются входами четных разрядов X2i n-разрядного входа сети ibaseline, первые выходы Y1 переключателей последнего уровня Ti,k, где i = 1, n / 2 ¯ , являются выходами нечетных разрядов Y2i-1 n-разрядпого выхода сети ibaseline, вторые выходы Y2 переключателей последнего уровня Ti,k, где i = 1, n / 2 ¯ , являются выходами четных разрядов Y2i n-разрядного выхода сети ibaseline.

7. Устройство по п.1, характеризующееся тем, что каждый входной разряд Xi выходного соединителя соединен с выходным разрядом Yj, причем, если i - нечетное число, то j=m, а если i - четное число, то j=m+n/2, где число m определяют путем последовательного вычисления функции ξр(х)=2х-1+ар, где p = 1, k 1 ¯ , аргументом функции ξp является значение функции ξp-1, a аргументом функции ξ1 является 1, значение ap определяют из двоичного представления номера i=ak-12k-1+…+а121020.

8. Устройство по п.1, характеризующееся тем, что каждый выходной разряд Yi входного соединителя соединен с входным разрядом Xj, причем, если i - нечетное число, то j=m, а если i - четное число, то j=m+n/2, где число m определяют путем последовательного вычисления функции ξp(x)=2x-1+ap, где p = 1, k 1 ¯ , аргументом функции ξр является значение функции ξр-1, а аргументом функции ξ1 является 1, значение ap определяют из двоичного представления номера i=ak-12k-1+…+а121020.



 

Похожие патенты:

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

Изобретение относится к области вычислительной техники и может использоваться в высокопроизводительных системах обработки больших массивов данных, передаваемых по высокоскоростным каналам передачи (приема), в том числе и в режиме реального времени.

Изобретение относится к средствам ретрансляции потерь в линии связи. .

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

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

Изобретение относится к вычислительной технике. .

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

Изобретение относится к вычислительной технике

Изобретение относится к области вычислительной техники, а именно к микропроцессорным системам с кэш-памятью, блоками обнаружения и коррекции ошибок и встроенным блоком самотестирования

Изобретение относится к области систем функционального резервирования электронных плат, а именно к резервированию плат измерительного канала космического аппарата

Изобретение относится к современным пилотажно-навигационным комплексам летательных аппаратов и их бортовой аппаратуре и может быть использовано для восстановления работоспособности систем радиоавтоматики и автоматического управления, резервированных с помощью мажоритарных элементов путем формирования сигналов управления элементами резервированных систем. Техническим результатом является повышение надежности устройства. Устройство содержит рабочий элемент, два элемента сравнения (резервных элемента), коммутируемый дополнительный элемент сравнения, шесть электронных ключей, три вычитающих устройства, три компаратора, блок управления, два логических элемента ИЛИ, три логических элемента НЕ, переключатель электронных ключей, четыре логических элемента И, три триггера. 3 ил.

Изобретение относится к телекоммуникации и вычислительной технике и может быть использовано для организации работы компьютерных сетей. Технический результат заключается в повышении устойчивости к сетевым атакам за счет уменьшения влияния на работоспособность сервера пакетов, поступающих от атакующих ботов. Способ включает формирование запроса от терминального устройства клиента на получение IP адреса сервера, проверку сертификата сервера и сертификата клиента, формирование одной или нескольких таблиц IP адресов в виде двоичных кодов, установление безопасного соединения, передачу сформированной таблицы терминальному устройству клиента, а передачу пакетов данных между терминальным устройством клиента и сервером осуществляют с изменением IP адреса сервера, который выбирают из таблицы IP адресов. Система включает терминальное устройство клиента, сервер данных, сервер доменных имен, сервер обеспечения безопасного соединения, два маршрутизатора и блок, формирующий таблицу IP адресов в виде двоичных кодов и меняющий IP адреса по таблице, назначаемой для каждого соединения. 2 н. и 12 з.п. ф-лы, 7 ил.

Изобретение относится к области автоматики и цифровой вычислительной техники. Технический результат заключается в повышении надежности функционирования тестопригодных логических преобразователей. Способ включает первоначальное получение исходного математического описания рабочего закона функционирования n-входовых логических преобразователей в тестопригодном логическом базисе Жегалкина, разработку и реализацию структурной схемы логического преобразователя из элемента - генератор логической 1, r последовательных цепочек из (k-1) двухвходовых логических элементов с электронно перестраиваемой логической функцией, реализующих k-аргументные функции И, и последовательной цепочки из (r-1) двухвходовых элементов неравнозначности, реализующих рабочую функцию Fp, причем на этапе разработки и реализации структурной схемы логического преобразователя дополнительно вводят (s+1) последовательных цепочек из (k-1) двухвходовых логических элементов с электронно перестраиваемой логической функцией и последовательную цепочку из (s+1) двухвходовых элементов неравнозначности, которая на выходе формирует признак ошибки путем реализации свертки по модулю два значения функции Fp, всех s дополнительных k-аргументных конъюнкций и дополнительной n-аргументной конъюнкции инверсий входных аргументов. 2 ил.

Изобретение относится к вычислительной технике. Технический результат заключается в сокращении сбоев резервного копирования данных. Устройство обработки данных, выполненное с возможностью резервного копирования данных во внешний модуль памяти, содержащее: модуль управления доступом, выполненный с возможностью установки доступного состояния внешнего модуля памяти; модуль установки, выполненный с возможностью установки внешнего модуля памяти в качестве места назначения для резервного копирования; и модуль резервного копирования, выполненный с возможностью резервного копирования данных во внешний модуль памяти, установленный в доступное состояние и в качестве места назначения для резервного копирования, при этом модуль управления доступом выполнен с возможностью не отменять доступное состояние внешнего модуля памяти, установленного в качестве места назначения для резервного копирования, даже когда данные не сохраняются во внешний модуль памяти. 4 н. и 13 з.п. ф-лы, 18 ил.

Изобретение относится к безопасному способу представления или отображения информации путем определения критических для безопасности ошибок в процессе обработки информации. Техническим результатом является безопасное представление информации на дисплее. Способ безопасного представления информации, имеющей отношение к безопасности, включающий: ввод, по меньшей мере, одного вводимого параметра в процессор, компьютерную обработку вводимого параметра преобразованием его в последовательность видеоданных, которые представляют собой вводимый параметр, передачу последовательности видеоданных на дисплей и представление последовательности видеоданных на дисплее, при этом последовательность видеоданных передают в испытательное устройство, выполняют испытание безопасности компьютерной генерацией тестового кода для этой последовательности видеоданных, тестовый код проверяют в сравнении с несколькими контрольными кодами, далее идентифицированному контрольному коду назначают соответствующее возможное значение вводимого параметра и проверяют в сравнении со значением вводимого параметра с помощью испытательного устройства, генерирующего либо положительный, либо отрицательный результат испытания для вызова отклика, направленного на безопасность. Устройство предназначено для реализации данного способа. 2 н. и 20 з.п. ф-лы, 4 ил.

Изобретение относится к вычислительной технике. Технический результат заключается в осуществлении с высокой скоростью контроля по четности вводимых и хранящихся данных. Параллельная ассоциативная память для одновременного поиска по всем адресам и определения того, хранятся ли в памяти те же данные, что и введенные данные, содержащая средство генерации четности для генерации бита четности n-разрядных данных, вводимых во время записи и во время поиска, и множество мест памяти, которое соответствует множеству адресов, причем каждое из указанных мест памяти содержит: n запоминающих ячеек ассоциативной памяти для хранения n-разрядных данных; ячейку хранения четности для хранения бита четности; средство контроля по четности для определения того, совпадают ли бит четности, сгенерированный указанным средством генерации четности во время поиска, и бит четности, хранящийся в ячейке хранения четности, и для активации сигнала совпадения по четности в случае их совпадения; схему обнаружения совпадения слов, предназначенную для активации сигнала совпадения слов данных в случае совпадения n-разрядных данных; и средство подтверждения совпадения по четности; причем параллельная ассоциативная память дополнительно содержит средство обнаружения ошибки четности. 1 з.п. ф-лы, 13 ил.
Наверх