Результат интеллектуальной деятельности: УСТРОЙСТВО ПЕРЕСТАНОВОК И СДВИГОВ БИТОВ ДАННЫХ В МИКРОПРОЦЕССОРАХ

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

Известен метод и система для осуществления перестановок на базе сетей 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-разрядным входом данных X₁-X_n, n-разрядным выходом данных Y₁-Y_n, m-разрядным входом C_1,1-C_n/2,k кода управления сетью; устройство также включает n-разрядный мультиплексор 2→1 входных данных с первым n-разрядным входом X_1,1-X_1,n, вторым n-разрядным входом X_2,1-X_2,n, входом управления A, соединенным с бинарным входом AOR управления маскированием на выходе и мультиплексором входных данных устройства, n-разрядным выходом Y₁-Y_n, соединенным с n-разрядным входом данных X₁-X_n многоуровневой коммутационной сети; устройство также включает n-разрядный входной соединитель с n-разрядным входом X₁-X_n и n-разрядным выходом Y₁-Y_n, соединенным с первым n-разрядным входом X_1,1-X_1,n n-разрядного мультиплексора 2→1 входных данных, входной соединитель обеспечивает фиксированные соединения входных и выходных разрядов; устройство также включает n-разрядный блок маскирования данных на входе с первым n-разрядным входом данных X₁-X_n, вторым n-разрядным входом F₁-F_n, n-разрядным выходом Y₁-Y_n, соединенным с n-разрядным входом X₁-X_n входного соединителя и со вторым n-разрядным входом X_2,1-X_2,n, n-разрядного мультиплексора 2→1 входных данных; устройство также включает m-разрядный мультиплексор 2→1 битов управления с входом управления AC, первым m-разрядным входом C_1,1,1-C_1,n/2,k битов управления, вторым m-разрядным входом C_2,1,1-C_2,n/2,k битов управления, m-разрядным выходом Y_1,1-Y_n/2,k, соединенным с m-разрядным входом C_1,1-C_n/2,k кода управления сетью; устройство также включает блок формирования битов маскирования и управления, с бинарным входом AOR, соединенным с бинарным входом управления маскированием на выходе и мультиплексором входных данных устройства, бинарным входом RL управления направлением сдвига данных, бинарным входом AMUX управления мультиплексором битов маскирования, бинарным входом AIOR управления маскированием на входе, n-разрядным входом F₁-F_n битов маскирования, k-разрядным входом A₀-A_k-1 значения числа сдвига данных, n-разрядным выходом FI₁-FI_n битов маскирования входных данных, соединенным со вторым n-разрядным входом F₁-F_n блока маскирования данных на входе, n-разрядным выходом FO₁-FO_n битов маскирования выходных данных, (n-1)-разрядным выходом С₁-C_n-1 кода маскирования данных на входе, (n-1)-разрядным выходом C₁-C_n-1 кода управления сдвигом, соединенным с вторым m-разрядным входом С_2,1,1-C_2,n/2,k битов управления мультиплексора 2→1 битов управления; устройство также включает n-разрядный блок маскирования данных на выходе с первым n-разрядным входом Х₁-X_n, соединенным с n-разрядным выходом данных Y₁-Y_n многоуровневой коммутационной сети, вторым n-разрядным входом F₁-F_n, соединенным с n-разрядным выходом битов маскирования выходных данных FO₁-FO_n, n-разрядным выходом Y₁-Y_n; устройство также включает n-разрядный выходной соединитель с n-разрядным выходом Y₁-Y_n, n-разрядным входом Х₁-X_n, соединенным с n-разрядным выходом Y₁-Y_n n-разрядного блока маскирования данных на выходе, выходной соединитель обеспечивает фиксированные соединения входных и выходных разрядов; устройство также включает n-разрядный мультиплексор 2→1 выходных данных с первым n-разрядным входом X_1,1-X_1,n, соединенным с n-разрядным выходом Y₁-Y_n n-разрядного блока маскирования данных на выходе, вторым n-разрядным входом X_2,1-X_2,n, соединенным с n-разрядным выходом Y₁-Y_n n-разрядного выходного соединителя, входом управления A, соединенным с бинарным входом управления мультиплексором выходных данных AOUT устройства, n-разрядным выходом данных Y₁-Y_n. При использовании сети baseline бит i-го разряда C_i, кода управления сдвигом подают на входы разрядов C_2,q,r второго m-разрядного входа мультиплексора битов управления, где индекс q - целое число и INT(i-2^r-1)·2^k-r<q<(INT((i-2^r-1))+l)·2^k-r+1, r=INT(log₂(i))+1, INT - функция, выделяющая целую часть аргумента. При использовании сети ibaseline на входы разрядов C_2,q,j, где , , второго m-разрядного входа мультиплексора битов управления подают бит i-го разряда C_i (n-1)-разрядного выхода C₁-C_n-1 кода управления сдвигом, причем i=mod(q-1,2^j-1)+2^j-1, где mod(q-1,2^j-1) - функция, вычисляющая число q-1 по модулю 2^j-1. Блок формирования битов маскирования и управления включает первый блок побитовой дизъюнкции с n-разрядным входом данных X₁-X_n, соединенным с n-разрядным входом F₁-F_n битов маскирования, n-разрядным выходом данных Y₁-Y_n, и входом AOR, первый блок побитовой дизъюнкции осуществляет функции побитовое логическое ИЛИ Y_i=X_i∨AOR, где ; блок формирования битов маскирования и управления также включает n-разрядный мультиплексор битов маскирования, с выходом FO₁-FO_n, первым n-разрядным входом X_1,1-X_1,n, вторым n-разрядным входом X_2,1-X_2,n, соединенным выходом Y₁-Y_n первого блока побитовой дизъюнкции, входом AMUX, блок формирования битов маскирования и управления также включает n логических инверторов D₁-D_n и n-1 модуль формирования битов кода управления сдвигом M_i,j, где , , каждый из которых имеет три бинарных входа f, ci, rotr, три бинарных выхода c, f₁, f₂, и выполняет логические функции: , , , входы rotr всех модулей M_i,j соединены с входом RL, модули M_i,j соединены так, что образуют двоичное дерево с k уровнями, при этом на уровне j содержится 2^j-1 модулей M_i,j, причем выход с каждого из модулей M_i,j соединен с выходом C_p блока формирования битов маскирования и управления, где p=2^j-1+i-1, выход f₁ каждого модуля M_i,j, расположенного на уровне j соединен с входом f модуля M_2i-1,j+,1, расположенного на уровне j+1, выход f₂ каждого модуля M_i,j, расположенного на уровне j, соединен с входом f модуля M_2i,j+1, расположенного на уровне j+1, вход f модуля M_1,1 предназначен для сигнала с низким логическим уровнем, вход ci каждого модуля M_i,j, расположенного на уровне j, соединен с входом разряда A_j-1 входа A₀-A_k-1, выход f₁ каждого модуля M_i,k, расположенного на k-ом уровне, соединен с входом логического инвертора D_2i-1, выход f₂ каждого модуля M_i,k, расположенного на k-ом уровне, где , соединен с входом логического инвертора D_2i каждый выход логического инвертора D_i, где соединен с разрядом X_1,i, первого входа мультиплексора битов маскирования; блок формирования битов маскирования и управления включает второй блок побитовой дизъюнкции с n-разрядным входом данных X₁-X_n, соединенным с n-разрядным входом F₁-F_n битов маскирования, выходом FI₁-FI_n, входом AIOR, второй блок побитовой дизъюнкции осуществляет функции побитовое логическое ИЛИ Y_i=X_i∨AIOR, где . Многоуровневая коммутационная сеть baseline состоит из переключателей T_i,j, где , , расположенных в матричном порядке по n/2 линиям и k=log₂n уровням, каждый переключатель имеет два бинарных входа X₁, Х₂, два бинарных выхода Y₁, Y₂ и бинарный вход управляющего сигнала C, каждый переключатель реализует логические функции , , бинарные входы управляющих сигналов переключателей сети образуют m-разрядный вход C_1,1-C_n/2,k кода управления многоуровневой коммутационной сетью baseline, причем бинарный вход C переключателя T_i,j, где , , соединен с входом разряда C_i,j кода управления многоуровневой коммутационной сетью baseline, каждый переключатель сети j-го уровня, где , расположенный на линии с номером i, соединен первым выходом Y₁ с первым входом X₁ при нечетном i или со вторым входом X₂ при четном i переключателя j+1 уровня, расположенного на линии с номером , а вторым выходом Y₂ с первым входом X₁ при нечетном i или со вторым входом X₂ при четном i переключателя j+1 уровня сети, расположенного на линии с номером , где INT - функция вычисления целой части от аргумента; первые входы X₁ переключателей первого уровня T_i,1 где , являются входами нечетных разрядов X_2i-1 n-разрядного входа сети baseline, вторые входы X₂ переключателей первого уровня T_i,1, где , являются входами четных разрядов X_2i, n-разрядного входа сети baseline, первые выходы Y₁ переключателей последнего уровня T_i,k, где , являются выходами нечетных разрядов Y_2i-1 n-разрядного выхода сети baseline, вторые выходы Y₂ переключателей последнего уровня T_i,k где , являются выходами четных разрядов Y_2i, n-разрядного выхода сети baseline. Обратная многоуровневая коммутационная сеть ibaseline состоит из переключателей T_i,j, где , расположенных в матричном порядке по n/2 линиям и k=log₂ n уровням, каждый переключатель имеет два бинарных входа X₁, X₂, два бинарных выхода Y₁, Y₂ и бинарный вход управляющего сигнала C, каждый переключатель реализует логические функции , , бинарные входы управляющих сигналов переключателей сети образуют m-разрядный вход C_1,1-C_n/2,k кода управления обратной многоуровневой коммутационной сетью ibaseline, причем бинарный вход C переключателя T_i,j, где , , соединен с входом разряда C_i,j кода управления обратной многоуровневой коммутационной сетью ibaseline, каждый переключатель сети (k-j+1)-го уровня, где , расположенный на линии с номером i, соединен первым входом X₁ с первым выходом Y₁ при нечетном i или со вторым выходом Y₂ при четном i переключателя (k-j)-го уровня, расположенного на линии с номером , а вторым входом X₂ с первым выходом Y₁ при нечетном i или со вторым выходом Y₂ при четном i переключателя (k-j)-го уровня сети, расположенного на линии с номером , где INT - функция вычисления целой части от аргумента, первые входы X₁ переключателей первого уровня T_i,1, где , являются входами нечетных разрядов X_2i-1 n-разрядного входа сети ibaseline, вторые входы X₂ переключателей первого уровня T_i,1, где , являются входами четных разрядов X_2i n-разрядного входа сети ibaseline, первые выходы Y₁ переключателей последнего уровня T_i,k где , являются выходами нечетных разрядов Y_2i-1 n-разрядного выхода сети ibaseline, вторые выходы Y₂ переключателей последнего уровня T_i,k где , являются выходами четных разрядов Y_2i n-разрядного выхода сети ibaseline. Каждый входной разряд X_i выходного соединителя соединен с выходным разрядом Y_j, причем, если i - нечетное число, то j=m, а если i - четное число, то j=m+n/2, где число m определяют путем последовательного вычисления функции ξ_p(x)=2х-1+a_p, где , аргументом функции ξ_p является значение функции ξ_p-1, а аргументом функции ξ₁ является 1, значение a_p определяют из двоичного представления номера i=a_k-12^k-1+…+a₁2¹+a₀2⁰. Каждый выходной разряд Y_i входного соединителя соединен с входным разрядом X_j, причем, если i - нечетное число, то j=m, а если i - четное число, то j=m+n/2, где число m определяют путем последовательного вычисления функции ξ_p(x)=2х-1+a_p, где , аргументом функции ξ_p является значение функции ξ_p-1, а аргументом функции ξ₁ является 1, значение a_p определяют из двоичного представления номера i=a_k-12^k-1+…+a₁2¹+a₀2⁰.

Изобретение поясняется чертежами, где на фиг.1 приведена блок-схема устройства, на фиг.2 приведена схема устройства для случая n=8, где n - число бит входных данных; на фиг.3 приведена схема многоуровневой коммутационной сети baseline для случая n=8; на фиг.4 приведена возможная схема переключателя многоуровневой коммутационной сети baseline или ibaseline; на фиг.5 приведена схема блока формирования битов маскирования и управления осуществлением циклических и логических сдвигов для случая n=8; на фиг.6 приведена схема модуля M_i,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·log₂(n);

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

T_i,j, где , , k=log₂(n) - переключатели многоуровневой коммутационной сети baseline с первым Х₁ и вторым Х₂ бинарными входами данных, первым Y₁ и вторым Y₂ бинарными выходами данных, бинарным входом кода управления C;

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

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

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

D_i, где - логические инверторы;

M_i,j - модули формирования битов кода управления сдвигом, где , ;

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

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

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

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

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

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

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

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

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

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

Устройство перестановок и сдвигов битов данных в микропроцессорах, предназначенное для осуществления операций логического и циклического сдвига данных, размещения и выборки группы битов данных, и произвольной перестановки битов данных, включает многоуровневую коммутационную сеть baseline или обратную многоуровневую коммутационную сеть ibaseline 1 с n-разрядным входом X₁-X_n данных, n-разрядным выходом Y₁-Y_n данных, m-разрядным входом C_1,1-C_n/2,k кода управления сетью.

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

Вход данных устройства образован n-разрядным входом данных Х₁-X_n n-разрядного блока маскирования данных на входе, на n-разрядный вход битов маскирования F₁-F_n которого поступают биты с n-разрядного выхода битов маскирования входных данных FI₁-FI_n блока формирования битов маскирования и управления.

Блок маскирования данных на входе своим n-разрядным выходом Y₁-Y_n соединен со вторым n-разрядным входом Х_2,1-Х_2,n n-разрядного мультиплексора 2→1 входных данных и с n-разрядным входом Х₁-X_n входного соединителя, который своим n-разрядным выходом Y₁-Y_n соединен с первым n-разрядным входом X_1,1-X_1,n n-разрядного мультиплексора 2→1 входных данных, бинарный вход управления которого A соединен с входом AOR устройства.

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

Многоуровневая коммутационная сеть своим m-разрядным входом C_1,1-C_n/2,k кода управления сетью соединена с m-разрядным выходом Y_1,1-Y_n/2,k m-разрядного мультиплексора 2→1 битов управления, имеющего первый m-разрядный вход C_1,1,1-C_1,n/2,k, бинарный вход управления AC, а второй m-разрядный вход С_2,1,1-С_2,n/2,k, соединенный с (n-1)-разрядным выходом C₁-C_n-1 кода управления сдвигом. При этом, если используется многоуровневая коммутационная сеть baseline, бит первого разряда С₁ кода управления сдвигом подается на входы разрядов C_2,1,1-C_2,n/2,1 m-разрядного входа мультиплексора 2→1 битов управления, бит второго разряда C₂ кода управления сдвигом подается на входы разрядов C_2,1,2-C_2,n/4,2 m-разрядного входа мультиплексора 2→1 битов управления, бит третьего разряда C₃ кода управления сдвигом подается на входы разрядов C_2,n/4+1,2-C_2,n/2,2 m-разрядного входа мультиплексора 2→1 битов управления и т.д. В общем случае бит i-го разряда C_i, , кода управления сдвигом подается на входы С_2,q,r m-разрядного входа мультиплексора 2→1 битов управления, где

INT(i-2^r-1)·2^k-r<q<(INT((i-2^r-1))+1)·2^k-r+1, r=INT(log₂(i))+1,

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

При использовании сети ibaseline вместо сети baseline на входы разрядов C_2,q,j, где , , m-разрядного входа мультиплексора 2→1 битов управления подают бит i-го разряда C_i (n-1)-разрядного выхода C₁-C_n-1 кода управления сдвигом, причем i=mod(q-1,2^j-1)+2^j-1, где mod(q-1,2^j-1) - функция, вычисляющая число q-1 по модулю 2^j-1.

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

n-разрядный выход FO₁-FO_n битов маскирования выходных данных блока формирования битов маскирования и управления соединен с n-разрядным входом F₁-F_n битов маскирования n-разрядного блока маскирования данных на выходе.

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

Упомянутая ранее многоуровневая коммутационная сеть baseline имеет n бинарных входов, n бинарных выходов и состоит из переключателей T_i,j, где , , расположенных в матричном порядке по n/2 линиям и k=log₂n уровням, каждый переключатель имеет два бинарных входа Х₁, Х₂, два бинарных выхода Y₁, Y₂ и бинарный вход управляющего сигнала, переключатели реализуют логическую функцию , , где знак ∨ означает логическую операцию дизъюнкция (логическое ИЛИ), знак ∧ означает логическую операцию конъюнкция (логическое И), а подчеркивание сверху означает операцию логического отрицания.

Бинарные входы управляющих сигналов переключателей сети образуют m-разрядный вход C_1,1-C_n/2,k кода управления многоуровневой коммутационной сетью baseline, причем бинарный вход C переключателя T_i,j, где , , соединен с входом разряда C_i,j кода управления многоуровневой коммутационной сетью baseline.

Каждый переключатель сети baseline j-го уровня, где , расположенный на линии с номером i, соединен одним выходом с входом переключателя j+1 уровня, расположенного на линии с номером , a другим выходом с входом переключателя j+1 уровня сети baseline, расположенного на линии с номером , где INT - функция вычисления целой части от аргумента, каждый вход каждого переключателя уровня j+1 соединен с одним выходом переключателя уровня j. Первые входы X₁ переключателей первого уровня T_i,1, где , являются входами нечетных разрядов X_2i-1 n-разрядного входа сети baseline, вторые входы X₂ переключателей первого уровня T_i,1, где , являются входами четных разрядов X_2i, n-разрядного входа сети baseline, первые выходы Y₁ переключателей последнего уровня T_i,k где , являются выходами нечетных разрядов Y_2i-1 n-разрядного выхода сети baseline, вторые выходы Y₂ переключателей последнего уровня T_i,k, где , являются выходами четных разрядов Y_2i, n-разрядного выхода сети baseline.

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

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

Обратная многоуровневая коммутационная сеть ibaseline состоит из переключателей T_i,j, где , расположенных в матричном порядке по n/2 линиям и k=log₂n уровням, каждый переключатель имеет два бинарных входа Х₁, Х₂, два бинарных выхода Y₁, Y₂ и бинарный вход управляющего сигнала, каждый переключатель реализует логическую функцию , , бинарные входы управляющих сигналов переключателей сети образуют m-разрядный вход C_1,1-C_n/2,k кода управления обратной многоуровневой коммутационной сетью ibaseline, причем бинарный вход С переключателя T_i,j, где , , соединен с входом разряда C_i,j кода управления обратной многоуровневой коммутационной сетью ibaseline, каждый переключатель сети (k-j+1)-го уровня, где , расположенный на линии с номером i, соединен одним входом с выходом переключателя (k-j)-го уровня, расположенного на линии с номером , а другим входом с выходом переключателя (k-j)-го уровня сети, расположенного на линии с номером , где INT - функция вычисления целой части от аргумента, каждый выход каждого переключателя (k-j)-го уровня соединен с одним входом переключателя (k-j+1)-го уровня, первые входы X₁ переключателей первого уровня T_i,1, где , являются входами нечетных разрядов X_2i-1 n-разрядного входа сети ibaseline, вторые входы X₂ переключателей первого уровня T_i,1, где , являются входами четных разрядов X_2i n-разрядного входа сети ibaseline, первые выходы Y₁ переключателей последнего уровня T_i,k, где , являются выходами нечетных разрядов Y_2i-1 n-разрядного выхода сети ibaseline, вторые выходы Y₂ переключателей последнего уровня T_i,k, где , являются выходами четных разрядов Y_2i, n-разрядного выхода сети ibaseline.

Блок формирования битов маскирования и управления (см. фиг.5) характеризуется наличием бинарных входов управления AOR, RL, AMUX, AIOR, k-разрядного входа А₀-A_k-1 значения числа сдвига данных, n-разрядного входа битов маскирования данных F₁-F_n, образующих соответстующие входы предлагаемого устройства. Блок формирования битов маскирования и управления характеризуется также наличием n-разрядного выхода FI₁-FI_n битов маскирования входных данных, n-разрядного выхода FO_I-FO_n битов маскирования выходных данных, (n-1)-разрядного выхода С₁-C_n-1 кода управления сдвигом, образующих соответстующие выходы предлагаемого устройства.

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

Блок формирования битов маскирования и управления также включает мультиплексор битов маскирования 25, имеющий первый n-разрядный вход X_1,1-X_1,n, второй n-разрядный вход Х_2,1-Х_2,n, n-разрядный выход FO₁-FO_n битов маскирования выходных данных и бинарный вход управления AMUX.

Блок формирования битов маскирования и управления также включает n/2 логических инверторов и n-1 модуль M_i,j, где , , формирования битов кода управления сдвигом, каждый из которых имеет три бинарных входа f, ci, rotr и три бинарных выхода с, f₁, f₂, и выполняет три логических функции , , . На языке Verilog эти логические функции описываются следующим образом:

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

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

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

На фиг.6 приведена возможная схема модуля формирования битов кода управления сдвигом M_i,j, где , .

Модули формирования битов кода управления соединены так, что образуют двоичное дерево (пирамидальную структуру) с k уровнями. При этом на первом уровне двоичного дерева содержится один модуль M_1,1, выход с которого соединен с выходом С₁ блока формирования битов маскирования и управления. На втором уровне двоичного дерева содержится два модуля: М_1,2, выход с которого соединен с выходом C₂ блока формирования битов маскирования и управления, и M_2,2, выход с которого соединен с выходом C₃ блока формирования битов маскирования и управления. На третьем уровне двоичного дерева содержится четыре модуля M_1,3, M_2,3, M_3,3, M_4,3, выходы с которых соответственно соединены с выходами С₄, С₅, C₆, C₇, блока формирования битов маскирования и управления. В общем случае на уровне j, где , содержится 2^j-1 модулей M_i,j, где , причем выход с каждого из модулей M_i,j соединен с выходом C_p блока формирования битов маскирования и управления, где р=2^j-1+i-1.

Выход f₁ каждого модуля M_i,j, где , формирования битов кода управления, расположенного на уровне j, где , соединен с входом f модуля M_2i-1,j+1, расположенного на уровне j+1. Выход f₂ каждого модуля M_i,j, где , формирования битов кода управления сдвигом, расположенного на уровне j, где , соединен с входом f модуля M_2i,j+1, расположенного на уровне j+1. На вход f модуля М_1,1 формирования битов кода управления подается сигнал с низким логическим уровнем. Вход ci каждого модуля M_i,j формирования битов кода управления сдвигом, расположенного на уровне j, где , соединен с входом разряда A_j-1 k-разрядного входа A₀-A_k-1 значения числа сдвига данных, расположенного в блоке формирования битов маскирования и управления.

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

Выход f₁ каждого модуля M_i,k, расположенного на последнем k-м уровне, где , соединен с входом логического инвертора D_2i-1. Выход f₂ каждого модуля M_i,k расположенного на последнем k-м уровне, где , соединен с входом логического инвертора D_2i. Каждый выход логического инвертора D_i, где , соединен с разрядом X_1,i, где , первого n-разрядного входа мультиплексора битов маскирования 25, n-разрядный выход которого Y₁-Y_n соединен с n-разрядным выходом FO₁-FO_n блока формирования битов маскирования и управления.

В блоке формирования битов маскирования и управления n-разрядный вход F₁-F_n битов маскирования соединен с n-разрядным входом Х₁-X_n первого блока побитовой дизъюнкции 23 и с n-разрядным входом Х₁-X_n второго блока побитовой дизъюнкции 24. n-разрядный выход Y₁-Y_n первого блока побитовой дизъюнкции 23 соединен со вторым n-разрядным входом Х_2,1-Х_2,n мультиплексора битов маскирования 25. Бинарный вход AOR первого блока побитовой дизъюнкции 23 является входом AOR устройства. Бинарный вход AIOR второго блока побитовой дизъюнкции 24 является входом AIOR устройства. n-разрядный выход FI₁-FI_n 23 является выходом блока формирования битов маскирования и управления.

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

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

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

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

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

Выходной соединитель имеет n-разрядный вход Х₁-X_n данных, n-разрядный выход Y₁-Y_n данных, где каждый входной разряд X_i с номером i, , соединен с выходным разрядом Y_j с номером j, причем, если i - нечетное число, то j=m, если i - четное число, то j=m+n/2, где m=ξ_k-1(…ξ₂(ξ₁(1)))…), ξ_р(х)=2х-1+а_р значение а_р, где , определяется двоичным представлением i: i=a_k-12^k-1+…+a₁2¹+a₀2⁰. Таким образом, число m определяется путем последовательного вычисления функции ξ_р, где , аргументом функции ξ_p является значение функции ξ_p-1, а аргументом функции является 1.

Входной соединитель имеет n-разрядный вход Х₁-X_n данных, n-разрядный выход Y₁-Y_n данных, где каждый выходной разряд Y_i с номером i, соединен с входным разрядом X_j с номером j, причем, если i - нечетное число, то j=m, если i - четное число, то j=m+n/2, где m=ξ_k-1(…ξ₂(ξ₁(1)))…), ξ_p(x)=2x-1+a_p значение а_р, где , определяется двоичным представлением номера i: i=a_k-12^k-1+…+a₁2¹+a₀2⁰. Таким образом, число m определяется путем последовательного вычисления функции ξ_р, где , аргументом функции ξ_р является значение функции ξ_p-1, а аргументом функции ξ₁ является 1.

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

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

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

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

На вход Х₁-X_n n-разрядного блока маскирования данных на входе подаются входные данные, например, из регистра r₂ микропроцессора. При реализации инструкций рех или pdep на n-разрядный вход битов маскирования F₁-F_n блока формирования битов маскирования и управления подаются биты маскирования, например, из регистра r₃ микропроцессора. Для реализации инструкций bsn, рех или pdep на первый m-разрядный вход C_1,1,1-C_1,n/2,k битов управления мультиплексора битов управления подаются коды управления, например, из регистров ar.b₁, ar.b₁, ar.b₂, ar.b₃ микропроцессора. Для осуществления инструкций shr, shl, rotr, rotl, логического и циклического сдвигов на k-разрядный вход A₀-A_k-1 подается значение числа сдвига данных. Значение числа сдвига данных может содержаться, например, в младших битах регистра r₂ микропроцессора, так как при выполнении инструкций shr, shl биты маскирования формируются блоком формирования битов маскирования и управления, а при выполнении инструкций rotr, rotl биты маскирования не используются.

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

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

При выполнении инструкции bsn на n-разрядный вход Х₁-X_n блока маскирования данных на входе поступают данные, которые без изменения проходят через этот блок, поступают на второй вход мультиплексора входных данных и с его выхода Y₁-Y_n на вход многоуровневой коммутационной сети. Одновременно через первый вход и затем выход n-разрядного мультиплексора биты управления переключателями сети поступают на вход C_1,1-C_n/2,k управления переключателями коммутационной сети. С выхода Y₁-Y_n сети перестановленные биты данных без изменения проходят через блок маскирования данных на выходе и поступают на выход модуля манипуляции битами через первый вход, а затем выход мультиплексора выходных данных.

При выполнении инструкции pex биты данных поступают на n-разрядный вход Х₁-X_n блока маскирования данных на входе, на второй вход F₁-F_n которого подаются биты маскирования с выхода FI₁-FI_n блока формирования битов маскирования и управления. Маскированные данные через второй вход, а затем выход мультиплексора входных данных поступают на вход многоуровневой коммутационной сети. Одновременно через первый вход и затем выход m-разрядного мультиплексора биты управления переключателями сети поступают на вход C_1,1-C_n/2,k управления переключателями коммутационной сети. С выхода сети данные, проходя без изменения через блок маскирования данных на выходе, подаются на вход выходного соединителя и, проходя через него, поступают на второй вход мультиплексора выходных данных и далее попадают на его выход.

При выполнении инструкции pdep данные поступают на n-разрядный вход Х₁-X_n блока маскирования данных на входе, проходят его без изменений и через входной соединитель поступают на первый вход мультиплексора входных данных и с выхода этого мультиплексора поступают на вход многоуровневой коммутационной сети. Одновременно через первый вход и затем выход m-разрядного мультиплексора биты управления переключателями сети поступают на вход C_1,1-C_n/2,k управления переключателями коммутационной сети. Далее данные поступают на вход блока маскирования данных на выходе, на второй вход которого поступают биты маскирования с выхода FO₁-FO_n блока формирования битов маскирования и управления. Маскированные на выходе данные через выходной соединитель поступают на второй вход и затем на выход мультиплексора выходных данных, формируя, таким образом, выходные данные предлагаемого устройства.

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

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

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

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