УСТРОЙСТВО ПЕРЕСТАНОВОК И СДВИГОВ БИТОВ ДАННЫХ В МИКРОПРОЦЕССОРАХ
DEVICE FOR SWAPPING AND SHIFTING OF DATA BITS IN MICROPROCESSORS

Устройство относится к области преобразования информации и может быть использовано в микропроцессорах вычислительной техники.
Известен метод и система для осуществления перестановок на базе сетей 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.
Техническим результатом является упрощение конструкции устройства при сохранении высокой скорости выполнения операций.
1
n
1
n
1,1
n/2,k
1,1
1,n
2,1
2,n
1
n
1
n
1
n
1
n
1,1
1,n
1
n
1
n
1
n
1
n
2,1
2,n
1,1,1
1,n/2,k
2,1,1
2,n/2,k
1,1
n/2,k
1,1
n/2,k
1
n
0
k-1
1
n
1
n
1
n
1
n-1
1
n-1
2,1,1
2,n/2,k
1
n
1
n
1
n
1
n
1
n
1
n
1
n
1
n
1,1
1,n
1
n
2,1
2,n
1
n
1
n
i
2,q,r
2
2,q,j
i
1
n-1
1
n
1
n
1
n
i
i
1
n
1,1
1,n
2,1
2,n
1
n
1
n
i,j
1
2
i,j
i,j
i,j
i,j
p
1
i,j
2i-1,j+,1
2
i,j
2i,j+1
1,1
i,j
j-1
0
k-1
1
i,k
2i-1
2
i,k
2i
i
1,i
1
n
1
n
1
n
i
i
i,j
2
1
2
1
2
1,1
n/2,k
i,j
i,j
1
1
2
2
1
2
1
i,1
2i-1
2
i,1
2i
1
i,k
2i-1
2
i,k
2i
i,j
2
1
2
1
2
1,1
n/2,k
i,j
i,j
1
1
2
2
1
2
1
i,1
2i-1
2
i,1
2i
1
i,k
2i-1
2
i,k
2i
i
j
p
p
p
p-1
1
p
k-1
1
0
i
j
p
p
p
p-1
1
p
k-1
1
0
<mrow><mi>i</mi><mo>=</mo><mover accent="true"><mrow><mn>1,</mn><mi>n</mi><mo>−</mo><mn>1</mn></mrow><mo stretchy="true">¯</mo></mover></mrow>
<mrow><mi>j</mi><mo>=</mo><mover accent="true"><mrow><mn>1,</mn><mi>k</mi></mrow><mo stretchy="true">¯</mo></mover></mrow>
<mrow><mi>q</mi><mo>=</mo><mover accent="true"><mrow><mn>1,</mn><mi>n</mi><mo>/</mo><mn>2</mn></mrow><mo stretchy="true">¯</mo></mover></mrow>
<mrow><mi>i</mi><mo>=</mo><mover accent="true"><mrow><mn>1,</mn><mi>n</mi></mrow><mo stretchy="true">¯</mo></mover></mrow>
<mrow><mi>i</mi><mo>=</mo><mover accent="true"><mrow><msup><mrow><mn>1,2</mn></mrow><mrow><mi>j</mi><mo>−</mo><mn>1</mn></mrow></msup></mrow><mo stretchy="true">¯</mo></mover></mrow>
<mrow><mi>j</mi><mo>=</mo><mover accent="true"><mrow><mn>1,</mn><mi>k</mi></mrow><mo stretchy="true">¯</mo></mover></mrow>
<mrow><mi>c</mi><mo>=</mo><mi>f</mi><mo>∧</mo><mi>c</mi><mi>i</mi><mo>∨</mo><mover accent="true"><mrow><mi>f</mi><mo>∨</mo><mi>c</mi><mi>i</mi></mrow><mo stretchy="true">¯</mo></mover></mrow>
<mrow><msub><mi>f</mi><mn>1</mn></msub><mo>=</mo><mover accent="true"><mrow><mrow><mo>(</mo><mrow><mover accent="true"><mrow><mi>r</mi><mi>o</mi><mi>t</mi><mi>r</mi></mrow><mo stretchy="true">¯</mo></mover><mo>∨</mo><mover accent="true"><mrow><mi>f</mi><mo>∨</mo><mi>c</mi><mi>i</mi></mrow><mo stretchy="true">¯</mo></mover></mrow><mo>)</mo></mrow><mo>∧</mo><mrow><mo>(</mo><mrow><mover accent="true"><mrow><mi>f</mi><mo>∧</mo><mi>c</mi><mi>i</mi></mrow><mo stretchy="true">¯</mo></mover></mrow><mo>)</mo></mrow></mrow><mo stretchy="true">¯</mo></mover></mrow>
<mrow><msub><mi>f</mi><mn>2</mn></msub><mo>=</mo><mover accent="true"><mrow><mrow><mo>(</mo><mrow><mi>r</mi><mi>o</mi><mi>t</mi><mi>r</mi><mo>∨</mo><mover accent="true"><mrow><mi>f</mi><mo>∨</mo><mi>c</mi><mi>i</mi></mrow><mo stretchy="true">¯</mo></mover></mrow><mo>)</mo></mrow><mo>∧</mo><mrow><mo>(</mo><mrow><mover accent="true"><mrow><mi>f</mi><mo>∧</mo><mi>c</mi><mi>i</mi></mrow><mo stretchy="true">¯</mo></mover></mrow><mo>)</mo></mrow></mrow><mo stretchy="true">¯</mo></mover></mrow>
<mrow><mi>i</mi><mo>=</mo><mover accent="true"><mrow><mn>1,</mn><mi>n</mi><mo>/</mo><mn>2</mn></mrow><mo stretchy="true">¯</mo></mover></mrow>
<mrow><mi>i</mi><mo>=</mo><mover accent="true"><mrow><mn>1,</mn><mi>n</mi></mrow><mo stretchy="true">¯</mo></mover></mrow>
<mrow><mi>i</mi><mo>=</mo><mover accent="true"><mrow><mn>1,</mn><mi>n</mi></mrow><mo stretchy="true">¯</mo></mover></mrow>
<mrow><mi>i</mi><mo>=</mo><mover accent="true"><mrow><mn>1,</mn><mi>n</mi><mo>/</mo><mn>2</mn></mrow><mo stretchy="true">¯</mo></mover></mrow>
<mrow><mi>j</mi><mo>=</mo><mover accent="true"><mrow><mn>1,</mn><mi>k</mi></mrow><mo stretchy="true">¯</mo></mover></mrow>
<mrow><msub><mi>Y</mi><mn>1</mn></msub><mo>=</mo><mi>C</mi><mo>∧</mo><msub><mi>X</mi><mn>1</mn></msub><mo>∨</mo><mover accent="true"><mi>C</mi><mo stretchy="true">¯</mo></mover><mo>∧</mo><msub><mi>X</mi><mn>2</mn></msub></mrow>
<mrow><msub><mi>Y</mi><mn>2</mn></msub><mo>=</mo><mover accent="true"><mi>C</mi><mo stretchy="true">¯</mo></mover><mo>∧</mo><msub><mi>X</mi><mn>1</mn></msub><mo>∨</mo><mi>C</mi><mo>∧</mo><msub><mi>X</mi><mn>2</mn></msub></mrow>
<mrow><mi>i</mi><mo>=</mo><mover accent="true"><mrow><mn>1,</mn><mi>n</mi><mo>/</mo><mn>2</mn></mrow><mo stretchy="true">¯</mo></mover></mrow>
<mrow><mi>j</mi><mo>=</mo><mover accent="true"><mrow><mn>1,</mn><mi>k</mi></mrow><mo stretchy="true">¯</mo></mover></mrow>
<mrow><mi>j</mi><mo>=</mo><mover accent="true"><mrow><mn>1,</mn><mi>k</mi><mo>−</mo><mn>1</mn></mrow><mo stretchy="true">¯</mo></mover></mrow>
<mrow><msubsup><mi>u</mi><mi>i</mi><mn>1</mn></msubsup><mo>=</mo><mi>I</mi><mi>N</mi><mi>T</mi><mrow><mo>(</mo><mrow><mfrac><mrow><mi>i</mi><mo>+</mo><mn>1</mn></mrow><mn>2</mn></mfrac></mrow><mo>)</mo></mrow><mo>+</mo><msup><mn>2</mn><mrow><mi>k</mi><mo>−</mo><mi>j</mi><mo>−</mo><mn>1</mn></mrow></msup><mo>⋅</mo><mi>I</mi><mi>N</mi><mi>T</mi><mrow><mo>(</mo><mrow><mfrac><mrow><mi>i</mi><mo>⋅</mo><msup><mn>2</mn><mrow><mi>j</mi><mo>−</mo><mn>1</mn></mrow></msup></mrow><mrow><mrow><mo>(</mo><mrow><msup><mn>2</mn><mrow><mi>k</mi><mo>−</mo><mn>1</mn></mrow></msup><mo>+</mo><mn>1</mn></mrow><mo>)</mo></mrow></mrow></mfrac></mrow><mo>)</mo></mrow></mrow>
<mrow><msubsup><mi>u</mi><mi>i</mi><mn>2</mn></msubsup><mo>=</mo><mi>I</mi><mi>N</mi><mi>T</mi><mrow><mo>(</mo><mrow><mfrac><mrow><mi>i</mi><mo>+</mo><mn>1</mn></mrow><mn>2</mn></mfrac></mrow><mo>)</mo></mrow><mo>+</mo><msup><mn>2</mn><mrow><mi>k</mi><mo>−</mo><mi>j</mi><mo>−</mo><mn>1</mn></mrow></msup><mo>⋅</mo><mi>I</mi><mi>N</mi><mi>T</mi><mrow><mo>(</mo><mrow><mfrac><mrow><mi>i</mi><mo>⋅</mo><msup><mn>2</mn><mrow><mi>j</mi><mo>−</mo><mn>1</mn></mrow></msup></mrow><mrow><mrow><mo>(</mo><mrow><msup><mn>2</mn><mrow><mi>k</mi><mo>−</mo><mn>1</mn></mrow></msup><mo>+</mo><mn>1</mn></mrow><mo>)</mo></mrow></mrow></mfrac></mrow><mo>)</mo></mrow><mo>+</mo><msup><mn>2</mn><mrow><mi>k</mi><mo>−</mo><mi>j</mi><mo>−</mo><mn>1</mn></mrow></msup></mrow>
<mrow><mi>i</mi><mo>=</mo><mover accent="true"><mrow><mn>1,</mn><mi>n</mi><mo>/</mo><mn>2</mn></mrow><mo stretchy="true">¯</mo></mover></mrow>
<mrow><mi>i</mi><mo>=</mo><mover accent="true"><mrow><mn>1,</mn><mi>n</mi><mo>/</mo><mn>2</mn></mrow><mo stretchy="true">¯</mo></mover></mrow>
<mrow><mi>i</mi><mo>=</mo><mover accent="true"><mrow><mn>1,</mn><mi>n</mi><mo>/</mo><mn>2</mn></mrow><mo stretchy="true">¯</mo></mover></mrow>
<mrow><mi>i</mi><mo>=</mo><mover accent="true"><mrow><mn>1,</mn><mi>n</mi><mo>/</mo><mn>2</mn></mrow><mo stretchy="true">¯</mo></mover></mrow>
<mrow><mi>i</mi><mo>=</mo><mover accent="true"><mrow><mn>1,</mn><mi>n</mi><mo>/</mo><mn>2</mn></mrow><mo stretchy="true">¯</mo></mover></mrow>
<mrow><mi>j</mi><mo>=</mo><mover accent="true"><mrow><mn>1,</mn><mi>k</mi></mrow><mo stretchy="true">¯</mo></mover><mo>,</mo></mrow>
<mrow><msub><mi>Y</mi><mn>1</mn></msub><mo>=</mo><mi>C</mi><mo>∧</mo><msub><mi>X</mi><mn>1</mn></msub><mo>∨</mo><mover accent="true"><mi>C</mi><mo stretchy="true">¯</mo></mover><mo>∧</mo><msub><mi>X</mi><mn>2</mn></msub></mrow>
<mrow><msub><mi>Y</mi><mn>2</mn></msub><mo>=</mo><mover accent="true"><mi>C</mi><mo stretchy="true">¯</mo></mover><mo>∧</mo><msub><mi>X</mi><mn>1</mn></msub><mo>∨</mo><mi>C</mi><mo>∧</mo><msub><mi>X</mi><mn>2</mn></msub></mrow>
<mrow><mi>i</mi><mo>=</mo><mover accent="true"><mrow><mn>1,</mn><mi>n</mi><mo>/</mo><mn>2</mn></mrow><mo stretchy="true">¯</mo></mover></mrow>
<mrow><mi>j</mi><mo>=</mo><mover accent="true"><mrow><mn>1,</mn><mi>k</mi></mrow><mo stretchy="true">¯</mo></mover></mrow>
<mrow><mi>j</mi><mo>=</mo><mover accent="true"><mrow><mn>1,</mn><mi>k</mi><mo>−</mo><mn>1</mn></mrow><mo stretchy="true">¯</mo></mover></mrow>
<mrow><msubsup><mi>u</mi><mi>i</mi><mn>1</mn></msubsup><mo>=</mo><mi>I</mi><mi>N</mi><mi>T</mi><mrow><mo>(</mo><mrow><mfrac><mrow><mi>i</mi><mo>+</mo><mn>1</mn></mrow><mn>2</mn></mfrac></mrow><mo>)</mo></mrow><mo>+</mo><msup><mn>2</mn><mrow><mi>j</mi><mo>−</mo><mn>2</mn></mrow></msup><mo>⋅</mo><mi>I</mi><mi>N</mi><mi>T</mi><mrow><mo>(</mo><mrow><mfrac><mrow><mi>i</mi><mo>⋅</mo><msup><mn>2</mn><mrow><mi>k</mi><mo>−</mo><mi>j</mi></mrow></msup></mrow><mrow><mrow><mo>(</mo><mrow><msup><mn>2</mn><mrow><mi>k</mi><mo>−</mo><mn>1</mn></mrow></msup><mo>+</mo><mn>1</mn></mrow><mo>)</mo></mrow></mrow></mfrac></mrow><mo>)</mo></mrow></mrow>
<mrow><msubsup><mi>u</mi><mi>i</mi><mn>2</mn></msubsup><mo>=</mo><mi>I</mi><mi>N</mi><mi>T</mi><mrow><mo>(</mo><mrow><mfrac><mrow><mi>i</mi><mo>+</mo><mn>1</mn></mrow><mn>2</mn></mfrac></mrow><mo>)</mo></mrow><mo>+</mo><msup><mn>2</mn><mrow><mi>j</mi><mo>−</mo><mn>2</mn></mrow></msup><mo>⋅</mo><mi>I</mi><mi>N</mi><mi>T</mi><mrow><mo>(</mo><mrow><mfrac><mrow><mi>i</mi><mo>⋅</mo><msup><mn>2</mn><mrow><mi>k</mi><mo>−</mo><mi>j</mi></mrow></msup></mrow><mrow><mrow><mo>(</mo><mrow><msup><mn>2</mn><mrow><mi>k</mi><mo>−</mo><mn>1</mn></mrow></msup><mo>+</mo><mn>1</mn></mrow><mo>)</mo></mrow></mrow></mfrac></mrow><mo>)</mo></mrow><mo>+</mo><msup><mn>2</mn><mrow><mi>j</mi><mo>−</mo><mn>2</mn></mrow></msup></mrow>
<mrow><mi>i</mi><mo>=</mo><mover accent="true"><mrow><mn>1,</mn><mi>n</mi><mo>/</mo><mn>2</mn></mrow><mo stretchy="true">¯</mo></mover></mrow>
<mrow><mi>i</mi><mo>=</mo><mover accent="true"><mrow><mn>1,</mn><mi>n</mi><mo>/</mo><mn>2</mn></mrow><mo stretchy="true">¯</mo></mover></mrow>
<mrow><mi>i</mi><mo>=</mo><mover accent="true"><mrow><mn>1,</mn><mi>n</mi><mo>/</mo><mn>2</mn></mrow><mo stretchy="true">¯</mo></mover></mrow>
<mrow><mi>i</mi><mo>=</mo><mover accent="true"><mrow><mn>1,</mn><mi>n</mi><mo>/</mo><mn>2</mn></mrow><mo stretchy="true">¯</mo></mover></mrow>
<mrow><mi>p</mi><mo>=</mo><mover accent="true"><mrow><mn>1,</mn><mi>k</mi><mo>−</mo><mn>1</mn></mrow><mo stretchy="true">¯</mo></mover></mrow>
<mrow><mi>p</mi><mo>=</mo><mover accent="true"><mrow><mn>1,</mn><mi>k</mi><mo>−</mo><mn>1</mn></mrow><mo stretchy="true">¯</mo></mover></mrow>
r-1
k-r
r-1
k-r
j-1
j-1
j-1
j-1
j-1
j-1
k-1
1
0
k-1
1
0
Поставленная задача достигается тем, что устройство перестановок и сдвигов битов данных в микропроцессорах согласно решению включает многоуровневую коммутационную сеть baseline или обратную многоуровневую коммутационную сеть ibaseline, с n-разрядным входом данных X-X, n-разрядным выходом данных Y-Y, m-разрядным входом C-C кода управления сетью; устройство также включает n-разрядный мультиплексор 2→1 входных данных с первым n-разрядным входом X-X, вторым n-разрядным входом X-X, входом управления A, соединенным с бинарным входом AOR управления маскированием на выходе и мультиплексором входных данных устройства, n-разрядным выходом Y-Y, соединенным с n-разрядным входом данных X-X многоуровневой коммутационной сети; устройство также включает n-разрядный входной соединитель с n-разрядным входом X-X и n-разрядным выходом Y-Y, соединенным с первым n-разрядным входом X-X n-разрядного мультиплексора 2→1 входных данных, входной соединитель обеспечивает фиксированные соединения входных и выходных разрядов; устройство также включает n-разрядный блок маскирования данных на входе с первым n-разрядным входом данных X-X, вторым n-разрядным входом F-F, n-разрядным выходом Y-Y, соединенным с n-разрядным входом X-X входного соединителя и со вторым n-разрядным входом X-X, n-разрядного мультиплексора 2→1 входных данных; устройство также включает m-разрядный мультиплексор 2→1 битов управления с входом управления AC, первым m-разрядным входом C-C битов управления, вторым m-разрядным входом C-C битов управления, m-разрядным выходом Y-Y, соединенным с m-разрядным входом C-C кода управления сетью; устройство также включает блок формирования битов маскирования и управления, с бинарным входом AOR, соединенным с бинарным входом управления маскированием на выходе и мультиплексором входных данных устройства, бинарным входом RL управления направлением сдвига данных, бинарным входом AMUX управления мультиплексором битов маскирования, бинарным входом AIOR управления маскированием на входе, n-разрядным входом F-F битов маскирования, k-разрядным входом A-A значения числа сдвига данных, n-разрядным выходом FI-FI битов маскирования входных данных, соединенным со вторым n-разрядным входом F-F блока маскирования данных на входе, n-разрядным выходом FO-FO битов маскирования выходных данных, (n-1)-разрядным выходом С-C кода маскирования данных на входе, (n-1)-разрядным выходом C-C кода управления сдвигом, соединенным с вторым m-разрядным входом С-C битов управления мультиплексора 2→1 битов управления; устройство также включает n-разрядный блок маскирования данных на выходе с первым n-разрядным входом Х-X, соединенным с n-разрядным выходом данных Y-Y многоуровневой коммутационной сети, вторым n-разрядным входом F-F, соединенным с n-разрядным выходом битов маскирования выходных данных FO-FO, n-разрядным выходом Y-Y; устройство также включает n-разрядный выходной соединитель с n-разрядным выходом Y-Y, n-разрядным входом Х-X, соединенным с n-разрядным выходом Y-Y n-разрядного блока маскирования данных на выходе, выходной соединитель обеспечивает фиксированные соединения входных и выходных разрядов; устройство также включает n-разрядный мультиплексор 2→1 выходных данных с первым n-разрядным входом X-X, соединенным с n-разрядным выходом Y-Y n-разрядного блока маскирования данных на выходе, вторым n-разрядным входом X-X, соединенным с n-разрядным выходом Y-Y n-разрядного выходного соединителя, входом управления A, соединенным с бинарным входом управления мультиплексором выходных данных AOUT устройства, n-разрядным выходом данных Y-Y. При использовании сети baseline бит i-го разряда C,
кода управления сдвигом подают на входы разрядов C второго m-разрядного входа мультиплексора битов управления, где индекс q - целое число и INT(i-2)·2<q<(INT((i-2))+l)·2+1, r=INT(log(i))+1, INT - функция, выделяющая целую часть аргумента. При использовании сети ibaseline на входы разрядов C, где
,
, второго m-разрядного входа мультиплексора битов управления подают бит i-го разряда C (n-1)-разрядного выхода C-C кода управления сдвигом, причем i=mod(q-1,2)+2, где mod(q-1,2) - функция, вычисляющая число q-1 по модулю 2. Блок формирования битов маскирования и управления включает первый блок побитовой дизъюнкции с n-разрядным входом данных X-X, соединенным с n-разрядным входом F-F битов маскирования, n-разрядным выходом данных Y-Y, и входом AOR, первый блок побитовой дизъюнкции осуществляет функции побитовое логическое ИЛИ Y=X∨AOR, где
; блок формирования битов маскирования и управления также включает n-разрядный мультиплексор битов маскирования, с выходом FO-FO, первым n-разрядным входом X-X, вторым n-разрядным входом X-X, соединенным выходом Y-Y первого блока побитовой дизъюнкции, входом AMUX, блок формирования битов маскирования и управления также включает n логических инверторов D-D и n-1 модуль формирования битов кода управления сдвигом M, где
,
, каждый из которых имеет три бинарных входа f, ci, rotr, три бинарных выхода c, f, f, и выполняет логические функции:
,
,
, входы rotr всех модулей M соединены с входом RL, модули M соединены так, что образуют двоичное дерево с k уровнями, при этом на уровне j содержится 2 модулей M, причем выход с каждого из модулей M соединен с выходом C блока формирования битов маскирования и управления, где p=2+i-1, выход f каждого модуля M, расположенного на уровне j соединен с входом f модуля M, расположенного на уровне j+1, выход f каждого модуля M, расположенного на уровне j, соединен с входом f модуля M, расположенного на уровне j+1, вход f модуля M предназначен для сигнала с низким логическим уровнем, вход ci каждого модуля M, расположенного на уровне j, соединен с входом разряда A входа A-A, выход f каждого модуля M, расположенного на k-ом уровне, соединен с входом логического инвертора D, выход f каждого модуля M, расположенного на k-ом уровне, где
, соединен с входом логического инвертора D каждый выход логического инвертора D, где
соединен с разрядом X, первого входа мультиплексора битов маскирования; блок формирования битов маскирования и управления включает второй блок побитовой дизъюнкции с n-разрядным входом данных X-X, соединенным с n-разрядным входом F-F битов маскирования, выходом FI-FI, входом AIOR, второй блок побитовой дизъюнкции осуществляет функции побитовое логическое ИЛИ Y=X∨AIOR, где
. Многоуровневая коммутационная сеть baseline состоит из переключателей T, где
,
, расположенных в матричном порядке по n/2 линиям и k=logn уровням, каждый переключатель имеет два бинарных входа X, Х, два бинарных выхода Y, Y и бинарный вход управляющего сигнала C, каждый переключатель реализует логические функции
,
, бинарные входы управляющих сигналов переключателей сети образуют m-разрядный вход C-C кода управления многоуровневой коммутационной сетью baseline, причем бинарный вход C переключателя T, где
,
, соединен с входом разряда C кода управления многоуровневой коммутационной сетью baseline, каждый переключатель сети j-го уровня, где
, расположенный на линии с номером i, соединен первым выходом Y с первым входом X при нечетном i или со вторым входом X при четном i переключателя j+1 уровня, расположенного на линии с номером
, а вторым выходом Y с первым входом X при нечетном i или со вторым входом X при четном i переключателя j+1 уровня сети, расположенного на линии с номером
, где INT - функция вычисления целой части от аргумента; первые входы X переключателей первого уровня T где
, являются входами нечетных разрядов X n-разрядного входа сети baseline, вторые входы X переключателей первого уровня T, где
, являются входами четных разрядов X, n-разрядного входа сети baseline, первые выходы Y переключателей последнего уровня T, где
, являются выходами нечетных разрядов Y n-разрядного выхода сети baseline, вторые выходы Y переключателей последнего уровня T где
, являются выходами четных разрядов Y, n-разрядного выхода сети baseline. Обратная многоуровневая коммутационная сеть ibaseline состоит из переключателей T, где
,
расположенных в матричном порядке по n/2 линиям и k=log n уровням, каждый переключатель имеет два бинарных входа X, X, два бинарных выхода Y, Y и бинарный вход управляющего сигнала C, каждый переключатель реализует логические функции
,
, бинарные входы управляющих сигналов переключателей сети образуют m-разрядный вход C-C кода управления обратной многоуровневой коммутационной сетью ibaseline, причем бинарный вход C переключателя T, где
,
, соединен с входом разряда C кода управления обратной многоуровневой коммутационной сетью ibaseline, каждый переключатель сети (k-j+1)-го уровня, где
, расположенный на линии с номером i, соединен первым входом X с первым выходом Y при нечетном i или со вторым выходом Y при четном i переключателя (k-j)-го уровня, расположенного на линии с номером
, а вторым входом X с первым выходом Y при нечетном i или со вторым выходом Y при четном i переключателя (k-j)-го уровня сети, расположенного на линии с номером
, где INT - функция вычисления целой части от аргумента, первые входы X переключателей первого уровня T, где
, являются входами нечетных разрядов X n-разрядного входа сети ibaseline, вторые входы X переключателей первого уровня T, где
, являются входами четных разрядов X n-разрядного входа сети ibaseline, первые выходы Y переключателей последнего уровня T где
, являются выходами нечетных разрядов Y n-разрядного выхода сети ibaseline, вторые выходы Y переключателей последнего уровня T где
, являются выходами четных разрядов Y n-разрядного выхода сети ibaseline. Каждый входной разряд X выходного соединителя соединен с выходным разрядом Y, причем, если i - нечетное число, то j=m, а если i - четное число, то j=m+n/2, где число m определяют путем последовательного вычисления функции ξ(x)=2х-1+a, где
, аргументом функции ξ является значение функции ξ, а аргументом функции ξ является 1, значение a определяют из двоичного представления номера i=a2+…+a2+a2. Каждый выходной разряд Y входного соединителя соединен с входным разрядом X, причем, если i - нечетное число, то j=m, а если i - четное число, то j=m+n/2, где число m определяют путем последовательного вычисления функции ξ(x)=2х-1+a, где
, аргументом функции ξ является значение функции ξ, а аргументом функции ξ является 1, значение a определяют из двоичного представления номера i=a2+…+a2+a2.
i,j
Изобретение поясняется чертежами, где на фиг.1 приведена блок-схема устройства, на фиг.2 приведена схема устройства для случая n=8, где n - число бит входных данных; на фиг.3 приведена схема многоуровневой коммутационной сети baseline для случая n=8; на фиг.4 приведена возможная схема переключателя многоуровневой коммутационной сети baseline или ibaseline; на фиг.5 приведена схема блока формирования битов маскирования и управления осуществлением циклических и логических сдвигов для случая n=8; на фиг.6 приведена схема модуля M формирования битов кода управления сдвигом; на фиг.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-разрядный блок маскирования данных на выходе;
2
7 - m-разрядный мультиплексор 2→1 битов управления, где m=n/2·log(n);
8 - n-разрядный входной соединитель;
9 - n-разрядный выходной соединитель;
1
n
X-X - n-разрядный вход данных многоуровневой коммутационной сети, n-разрядный вход данных n-разрядного блока маскирования данных на входе, n-разрядный вход данных n-разрядного блока маскирования данных на выходе, n-разрядные входы входного и выходного соединителей;
1,1
n/2,k
2
C-C - m-разрядный вход кода управления сетью, где k=log(n);
1,1
1,n
X-X - первый n-разрядный вход мультиплексоров 2→1 входных и выходных данных, первый n-разрядный вход n-разрядного мультиплексора 2→1 битов маскирования;
2,1
2,n
X-X - второй n-разрядный вход мультиплексоров 2→1 входных и выходных данных, второй n-разрядный вход n-разрядного мультиплексора 2→1 битов маскирования;
1
n
Y-Y - n-разрядные выходы мультиплексоров 2→1 входных и выходных данных, n-разрядные выходы блоков маскирования данных на входе и выходе, n-разрядный выход данных многоуровневой коммутационной сети, n-разрядные выходы входного и выходного соединителей, n-разрядный выход n-разрядного мультиплексора 2→1 битов маскирования;
1,1,1
1,n/2,k
2
C-C - первый m-разрядный вход битов управления, где m=n/2·k, k=log(n);
2,1,1
2,n/2,k
2
С-С - второй m-разрядный вход битов управления, где m=n/2·k, k=log(n);
1,1
n/2,k
2
Y-Y - m-разрядный выход мультиплексора, где m=n/2·k, k=log(n);
1
n-1
C-C- (n-1)-разрядный выход кода управления сдвигом;
0
k-1
А-A - k-разрядный вход значения числа сдвига данных;
AOR - бинарный вход управления маскированием на выходе и мультиплексором входных данных;
RL - бинарный вход управления направлением сдвига данных;
AMUX - бинарный вход управления мультиплексором битов маскирования;
AIOR - бинарный вход управления маскированием на входе;
AOUT - бинарный вход управления мультиплексором выходных данных;
AC - бинарный вход управления мультиплексором битов управления;
1
n
F-F - n-разрядный вход битов маскирования;
1
n
FO-FO - n-разрядный выход битов маскирования выходных данных;
1
n
FI-FI - n-разрядный выход битов маскирования входных данных;
i,j
2
1
2
1
2
<mrow><mi>i</mi><mo>=</mo><mover accent="true"><mrow><mn>1,</mn><mi>n</mi><mo>/</mo><mn>2</mn></mrow><mo stretchy="true">¯</mo></mover></mrow>
<mrow><mi>i</mi><mo>=</mo><mover accent="true"><mrow><mn>1,</mn><mi>k</mi></mrow><mo stretchy="true">¯</mo></mover></mrow>
T, где
,
, k=log(n) - переключатели многоуровневой коммутационной сети baseline с первым Х и вторым Х бинарными входами данных, первым Y и вторым Y бинарными выходами данных, бинарным входом кода управления C;
23 - первый блок побитовой дизъюнкции;
24 - второй блок побитовой дизъюнкции;
25 - n-разрядны мультиплексор 2→1 битов маскирования;
i
<mrow><mi>i</mi><mo>=</mo><mover accent="true"><mrow><mn>1,</mn><mi>n</mi></mrow><mo stretchy="true">¯</mo></mover></mrow>
D, где
- логические инверторы;
i,j
<mrow><mi>i</mi><mo>=</mo><mover accent="true"><mrow><msup><mrow><mn>1,2</mn></mrow><mrow><mi>j</mi><mo>−</mo><mn>1</mn></mrow></msup></mrow><mo stretchy="true">¯</mo></mover></mrow>
<mrow><mi>j</mi><mo>=</mo><mover accent="true"><mrow><mn>1,</mn><mi>k</mi></mrow><mo stretchy="true">¯</mo></mover></mrow>
M - модули формирования битов кода управления сдвигом, где
,
;
rotr, ci, f - бинарные входы модуля формирования битов кода управления сдвигом;
1
2
c, f, f - бинарные выходы модуля формирования битов кода управления сдвигом;
A - бинарный вход управления мультиплексором 2→1;
211, 212, 213 - логические элементы 2И-НЕ;
214 - логический инвертор;
215, 216 - логические элементы 2ИЛИ;
217 - логический элемент 2ИЛИ-НЕ с инверсией сигнала на первом входе;
218 - логический элемент 2ИЛИ-НЕ;
MX - мультиплексоры 2→1 n-разрядного мультиплексора 2→1.
2
В дальнейшем изложении n означает число двоичных разрядов данных, k=log(n) - число уровней преобразования, m=n/2·k - число двоичных разрядов кода управления сетью.
1
n
1
n
1,1
n/2,k
Устройство перестановок и сдвигов битов данных в микропроцессорах, предназначенное для осуществления операций логического и циклического сдвига данных, размещения и выборки группы битов данных, и произвольной перестановки битов данных, включает многоуровневую коммутационную сеть baseline или обратную многоуровневую коммутационную сеть ibaseline 1 с n-разрядным входом X-X данных, n-разрядным выходом Y-Y данных, m-разрядным входом C-C кода управления сетью.
Устройство также включает блок формирования битов маскирования и управления 2; n-разрядный мультиплексор 2→1 входных данных 3, n-разрядный мультиплексор 2→1 выходных данных 4, n-разрядный блок маскирования данных на входе 5, n-разрядный блок маскирования данных на выходе 6, m-разрядный мультиплексор 2→1 битов управления 7, n-разрядный входной соединитель 8 и n-разрядный выходной соединитель 9.
1
n
1
n
1
n
Вход данных устройства образован n-разрядным входом данных Х-X n-разрядного блока маскирования данных на входе, на n-разрядный вход битов маскирования F-F которого поступают биты с n-разрядного выхода битов маскирования входных данных FI-FI блока формирования битов маскирования и управления.
1
n
2,1
2,n
1
n
1
n
1,1
1,n
Блок маскирования данных на входе своим n-разрядным выходом Y-Y соединен со вторым n-разрядным входом Х-Х n-разрядного мультиплексора 2→1 входных данных и с n-разрядным входом Х-X входного соединителя, который своим n-разрядным выходом Y-Y соединен с первым n-разрядным входом X-X n-разрядного мультиплексора 2→1 входных данных, бинарный вход управления которого A соединен с входом AOR устройства.
1
n
1
n
1
n
Мультиплексор 2→1 входных данных своим n-разрядным выходом Y-Y соединен с n-разрядным входом данных Х-X многоуровневой коммутационной сети, которая своим n-разрядным выходом Y-Y соединена с n-разрядным входом данных n-разрядного блока маскирования данных на выходе.
1,1
n/2,k
1,1
n/2,k
1,1,1
1,n/2,k
2,1,1
2,n/2,k
1
n-1
1
2,1,1
2,n/2,1
2
2,1,2
2,n/4,2
3
2,n/4+1,2
2,n/2,2
i
2,q,r
<mrow><mi>i</mi><mo>=</mo><mover accent="true"><mrow><mn>1,</mn><mi>n</mi><mo>−</mo><mn>1</mn></mrow><mo stretchy="true">¯</mo></mover></mrow>
Многоуровневая коммутационная сеть своим m-разрядным входом C-C кода управления сетью соединена с m-разрядным выходом Y-Y m-разрядного мультиплексора 2→1 битов управления, имеющего первый m-разрядный вход C-C, бинарный вход управления AC, а второй m-разрядный вход С-С, соединенный с (n-1)-разрядным выходом C-C кода управления сдвигом. При этом, если используется многоуровневая коммутационная сеть baseline, бит первого разряда Скода управления сдвигом подается на входы разрядов C-C m-разрядного входа мультиплексора 2→1 битов управления, бит второго разряда C кода управления сдвигом подается на входы разрядов C-C m-разрядного входа мультиплексора 2→1 битов управления, бит третьего разряда C кода управления сдвигом подается на входы разрядов C-C m-разрядного входа мультиплексора 2→1 битов управления и т.д. В общем случае бит i-го разряда C,
, кода управления сдвигом подается на входы С m-разрядного входа мультиплексора 2→1 битов управления, где
r-1
k-r
r-1
k-r
2
INT(i-2)·2<q<(INT((i-2))+1)·2+1, r=INT(log(i))+1,
INT(x) - функция, выделяющая целую часть аргмента x.
2,q,j
i
1
n-1
<mrow><mi>j</mi><mo>=</mo><mover accent="true"><mrow><mn>1,</mn><mi>k</mi></mrow><mo stretchy="true">¯</mo></mover></mrow>
<mrow><mi>q</mi><mo>=</mo><mover accent="true"><mrow><mn>1,</mn><mi>n</mi><mo>/</mo><mn>2</mn></mrow><mo stretchy="true">¯</mo></mover></mrow>
j-1
j-1
j-1
j-1
При использовании сети ibaseline вместо сети baseline на входы разрядов C, где
,
, m-разрядного входа мультиплексора 2→1 битов управления подают бит i-го разряда C (n-1)-разрядного выхода C-C кода управления сдвигом, причем i=mod(q-1,2)+2, где mod(q-1,2) - функция, вычисляющая число q-1 по модулю 2.
1
n
1
n
1
n
1
n
n-разрядный выход Y-Y блока маскирования данных на выходе соединен с входом Х-X n-разрядного выходного соединителя и с первым n-разрядным входом мультиплексора 2→1 выходных данных, выход Y-Y n-разрядного выходного соединителя соединен со вторым n-разрядным входом мультиплексора 2→1 выходных данных. Вход управления A n-разрядного мультиплексора 2→1 выходных данных соединен с входом AOUT устройства, а n-разрядный выход Y-Y мультиплексора 2→1 выходных данных является выходом данных устройства.
1
n
1
n
n-разрядный выход FO-FO битов маскирования выходных данных блока формирования битов маскирования и управления соединен с n-разрядным входом F-F битов маскирования n-разрядного блока маскирования данных на выходе.
0
k-1
1
n
0
k-1
1
n
Входы AIOR, RL, AMUX, A-A, F-F устройства образованы входами AIOR, RL, AMUX, A-A, F-F блока формирования битов маскирования и управления. Вход AOR устройства соединен с входом AOR блока формирования битов маскирования и управления и с входом управления A n-разрядного мультиплексора 2→1 входных данных.
i,j
2
1
2
1
2
<mrow><mi>i</mi><mo>=</mo><mover accent="true"><mrow><mn>1,</mn><mi>n</mi><mo>/</mo><mn>2</mn></mrow><mo stretchy="true">¯</mo></mover></mrow>
<mrow><mi>j</mi><mo>=</mo><mover accent="true"><mrow><mn>1,</mn><mi>k</mi></mrow><mo stretchy="true">¯</mo></mover></mrow>
<mrow><msub><mi>Y</mi><mn>1</mn></msub><mo>=</mo><mi>C</mi><mo>∧</mo><msub><mi>X</mi><mn>1</mn></msub><mo>∨</mo><mover accent="true"><mi>C</mi><mo stretchy="true">¯</mo></mover><mo>∧</mo><msub><mi>X</mi><mn>2</mn></msub></mrow>
<mrow><msub><mi>Y</mi><mn>2</mn></msub><mo>=</mo><mover accent="true"><mi>C</mi><mo stretchy="true">¯</mo></mover><mo>∧</mo><msub><mi>X</mi><mn>1</mn></msub><mo>∨</mo><mi>C</mi><mo>∧</mo><msub><mi>X</mi><mn>2</mn></msub></mrow>
Упомянутая ранее многоуровневая коммутационная сеть baseline имеет n бинарных входов, n бинарных выходов и состоит из переключателей T, где
,
, расположенных в матричном порядке по n/2 линиям и k=logn уровням, каждый переключатель имеет два бинарных входа Х, Х, два бинарных выхода Y, Y и бинарный вход управляющего сигнала, переключатели реализуют логическую функцию
,
, где знак ∨ означает логическую операцию дизъюнкция (логическое ИЛИ), знак ∧ означает логическую операцию конъюнкция (логическое И), а подчеркивание сверху означает операцию логического отрицания.
1,1
n/2,k
i,j
i,j
<mrow><mi>i</mi><mo>=</mo><mover accent="true"><mrow><mn>1,</mn><mi>n</mi><mo>/</mo><mn>2</mn></mrow><mo stretchy="true">¯</mo></mover></mrow>
<mrow><mi>j</mi><mo>=</mo><mover accent="true"><mrow><mn>1,</mn><mi>k</mi></mrow><mo stretchy="true">¯</mo></mover></mrow>
Бинарные входы управляющих сигналов переключателей сети образуют m-разрядный вход C-C кода управления многоуровневой коммутационной сетью baseline, причем бинарный вход C переключателя T, где
,
, соединен с входом разряда C кода управления многоуровневой коммутационной сетью baseline.
<mrow><mi>j</mi><mo>=</mo><mover accent="true"><mrow><mn>1,</mn><mi>k</mi><mo>−</mo><mn>1</mn></mrow><mo stretchy="true">¯</mo></mover></mrow>
<mrow><msubsup><mi>u</mi><mi>i</mi><mn>1</mn></msubsup><mo>=</mo><mi>I</mi><mi>N</mi><mi>T</mi><mrow><mo>(</mo><mrow><mfrac><mrow><mi>i</mi><mo>+</mo><mn>1</mn></mrow><mn>2</mn></mfrac></mrow><mo>)</mo></mrow><mo>+</mo><msup><mn>2</mn><mrow><mi>k</mi><mo>−</mo><mi>j</mi><mo>−</mo><mn>1</mn></mrow></msup><mo>⋅</mo><mi>I</mi><mi>N</mi><mi>T</mi><mrow><mo>(</mo><mrow><mfrac><mrow><mi>i</mi><mo>⋅</mo><msup><mn>2</mn><mrow><mi>j</mi><mo>−</mo><mn>1</mn></mrow></msup></mrow><mrow><mrow><mo>(</mo><mrow><msup><mn>2</mn><mrow><mi>k</mi><mo>−</mo><mn>1</mn></mrow></msup><mo>+</mo><mn>1</mn></mrow><mo>)</mo></mrow></mrow></mfrac></mrow><mo>)</mo></mrow></mrow>
<mrow><msubsup><mi>u</mi><mi>i</mi><mn>2</mn></msubsup><mo>=</mo><mi>I</mi><mi>N</mi><mi>T</mi><mrow><mo>(</mo><mrow><mfrac><mrow><mi>i</mi><mo>+</mo><mn>1</mn></mrow><mn>2</mn></mfrac></mrow><mo>)</mo></mrow><mo>+</mo><msup><mn>2</mn><mrow><mi>k</mi><mo>−</mo><mi>j</mi><mo>−</mo><mn>1</mn></mrow></msup><mo>⋅</mo><mi>I</mi><mi>N</mi><mi>T</mi><mrow><mo>(</mo><mrow><mfrac><mrow><mi>i</mi><mo>⋅</mo><msup><mn>2</mn><mrow><mi>j</mi><mo>−</mo><mn>1</mn></mrow></msup></mrow><mrow><mrow><mo>(</mo><mrow><msup><mn>2</mn><mrow><mi>k</mi><mo>−</mo><mn>1</mn></mrow></msup><mo>+</mo><mn>1</mn></mrow><mo>)</mo></mrow></mrow></mfrac></mrow><mo>)</mo></mrow></mrow>
<mrow><mi>i</mi><mo>=</mo><mover accent="true"><mrow><mn>1,</mn><mi>n</mi><mo>/</mo><mn>2</mn></mrow><mo stretchy="true">¯</mo></mover></mrow>
<mrow><mi>i</mi><mo>=</mo><mover accent="true"><mrow><mn>1,</mn><mi>n</mi><mo>/</mo><mn>2</mn></mrow><mo stretchy="true">¯</mo></mover></mrow>
<mrow><mi>i</mi><mo>=</mo><mover accent="true"><mrow><mn>1,</mn><mi>n</mi><mo>/</mo><mn>2</mn></mrow><mo stretchy="true">¯</mo></mover></mrow>
<mrow><mi>i</mi><mo>=</mo><mover accent="true"><mrow><mn>1,</mn><mi>n</mi><mo>/</mo><mn>2</mn></mrow><mo stretchy="true">¯</mo></mover></mrow>
1
i,1
2i-1
2
i,1
2i
1
i,k
2i-1
2
i,k
2i
Каждый переключатель сети baseline j-го уровня, где
, расположенный на линии с номером i, соединен одним выходом с входом переключателя j+1 уровня, расположенного на линии с номером
, a другим выходом с входом переключателя j+1 уровня сети baseline, расположенного на линии с номером
, где INT - функция вычисления целой части от аргумента, каждый вход каждого переключателя уровня j+1 соединен с одним выходом переключателя уровня j. Первые входы X переключателей первого уровня T, где
, являются входами нечетных разрядов X n-разрядного входа сети baseline, вторые входы X переключателей первого уровня T, где
, являются входами четных разрядов X, n-разрядного входа сети baseline, первые выходы Y переключателей последнего уровня T где
, являются выходами нечетных разрядов Y n-разрядного выхода сети baseline, вторые выходы Y переключателей последнего уровня T, где
, являются выходами четных разрядов Y, n-разрядного выхода сети baseline.
i,j
На фиг.3 изображена схема многоуровневой коммутационной сети baseline для случая n=8. Переключатели сети расположены в матричном порядке на четырех линиях и трех уровнях. На фиг.4 изображена возможная схема переключателя T, где 111, 112 - мультиплексоры 2→1.
В предлагаемом устройстве вместо многоуровневой коммутационной сети baseline может быть использована обратная многоуровневая коммутационная сеть ibaseline. Если в многоуровневой коммутационной сети baseline входы и выходы поменять местами, нумерацию уровней заменить на обратную, а также поменять местами входы и выходы переключателей сети, то получится обратная многоуровневая коммутационная сеть ibaseline.
i,j
2
1
2
1
2
1,1
n/2,k
i,j
i,j
1
i,1
2i-1
2
i,1
2i
1
i,k
2i-1
2
i,k
2i
<mrow><mi>i</mi><mo>=</mo><mover accent="true"><mrow><mn>1,</mn><mi>n</mi><mo>/</mo><mn>2</mn></mrow><mo stretchy="true">¯</mo></mover></mrow>
<mrow><mi>j</mi><mo>=</mo><mover accent="true"><mrow><mn>1,</mn><mi>k</mi></mrow><mo stretchy="true">¯</mo></mover></mrow>
<mrow><msub><mi>Y</mi><mn>1</mn></msub><mo>=</mo><mi>C</mi><mo>∧</mo><msub><mi>X</mi><mn>1</mn></msub><mo>∨</mo><mover accent="true"><mi>C</mi><mo stretchy="true">¯</mo></mover><mo>∧</mo><msub><mi>X</mi><mn>2</mn></msub></mrow>
<mrow><msub><mi>Y</mi><mn>2</mn></msub><mo>=</mo><mover accent="true"><mi>C</mi><mo stretchy="true">¯</mo></mover><mo>∧</mo><msub><mi>X</mi><mn>1</mn></msub><mo>∨</mo><mi>C</mi><mo>∧</mo><msub><mi>X</mi><mn>2</mn></msub></mrow>
<mrow><mi>i</mi><mo>=</mo><mover accent="true"><mrow><mn>1,</mn><mi>n</mi><mo>/</mo><mn>2</mn></mrow><mo stretchy="true">¯</mo></mover></mrow>
<mrow><mi>j</mi><mo>=</mo><mover accent="true"><mrow><mn>1,</mn><mi>k</mi></mrow><mo stretchy="true">¯</mo></mover></mrow>
<mrow><mi>j</mi><mo>=</mo><mover accent="true"><mrow><mn>1,</mn><mi>k</mi><mo>−</mo><mn>1</mn></mrow><mo stretchy="true">¯</mo></mover></mrow>
<mrow><msubsup><mi>u</mi><mi>i</mi><mn>1</mn></msubsup><mo>=</mo><mi>I</mi><mi>N</mi><mi>T</mi><mrow><mo>(</mo><mrow><mfrac><mrow><mi>i</mi><mo>+</mo><mn>1</mn></mrow><mn>2</mn></mfrac></mrow><mo>)</mo></mrow><mo>+</mo><msup><mn>2</mn><mrow><mi>j</mi><mo>−</mo><mn>2</mn></mrow></msup><mo>⋅</mo><mi>I</mi><mi>N</mi><mi>T</mi><mrow><mo>(</mo><mrow><mfrac><mrow><mi>i</mi><mo>⋅</mo><msup><mn>2</mn><mrow><mi>k</mi><mo>−</mo><mi>j</mi></mrow></msup></mrow><mrow><mrow><mo>(</mo><mrow><msup><mn>2</mn><mrow><mi>k</mi><mo>−</mo><mn>1</mn></mrow></msup><mo>+</mo><mn>1</mn></mrow><mo>)</mo></mrow></mrow></mfrac></mrow><mo>)</mo></mrow></mrow>
<mrow><msubsup><mi>u</mi><mi>i</mi><mn>2</mn></msubsup><mo>=</mo><mi>I</mi><mi>N</mi><mi>T</mi><mrow><mo>(</mo><mrow><mfrac><mrow><mi>i</mi><mo>+</mo><mn>1</mn></mrow><mn>2</mn></mfrac></mrow><mo>)</mo></mrow><mo>+</mo><msup><mn>2</mn><mrow><mi>j</mi><mo>−</mo><mn>2</mn></mrow></msup><mo>⋅</mo><mi>I</mi><mi>N</mi><mi>T</mi><mrow><mo>(</mo><mrow><mfrac><mrow><mi>i</mi><mo>⋅</mo><msup><mn>2</mn><mrow><mi>k</mi><mo>−</mo><mi>j</mi></mrow></msup></mrow><mrow><mrow><mo>(</mo><mrow><msup><mn>2</mn><mrow><mi>k</mi><mo>−</mo><mn>1</mn></mrow></msup><mo>+</mo><mn>1</mn></mrow><mo>)</mo></mrow></mrow></mfrac></mrow><mo>)</mo></mrow><mo>+</mo><msup><mn>2</mn><mrow><mi>j</mi><mo>−</mo><mn>2</mn></mrow></msup></mrow>
<mrow><mi>i</mi><mo>=</mo><mover accent="true"><mrow><mn>1,</mn><mi>n</mi><mo>/</mo><mn>2</mn></mrow><mo stretchy="true">¯</mo></mover></mrow>
<mrow><mi>i</mi><mo>=</mo><mover accent="true"><mrow><mn>1,</mn><mi>n</mi><mo>/</mo><mn>2</mn></mrow><mo stretchy="true">¯</mo></mover></mrow>
<mrow><mi>i</mi><mo>=</mo><mover accent="true"><mrow><mn>1,</mn><mi>n</mi><mo>/</mo><mn>2</mn></mrow><mo stretchy="true">¯</mo></mover></mrow>
<mrow><mi>i</mi><mo>=</mo><mover accent="true"><mrow><mn>1,</mn><mi>n</mi><mo>/</mo><mn>2</mn></mrow><mo stretchy="true">¯</mo></mover></mrow>
Обратная многоуровневая коммутационная сеть ibaseline состоит из переключателей T, где
,
расположенных в матричном порядке по n/2 линиям и k=logn уровням, каждый переключатель имеет два бинарных входа Х, Х, два бинарных выхода Y, Y и бинарный вход управляющего сигнала, каждый переключатель реализует логическую функцию
,
, бинарные входы управляющих сигналов переключателей сети образуют m-разрядный вход C-C кода управления обратной многоуровневой коммутационной сетью ibaseline, причем бинарный вход С переключателя T, где
,
, соединен с входом разряда C кода управления обратной многоуровневой коммутационной сетью ibaseline, каждый переключатель сети (k-j+1)-го уровня, где
, расположенный на линии с номером i, соединен одним входом с выходом переключателя (k-j)-го уровня, расположенного на линии с номером
, а другим входом с выходом переключателя (k-j)-го уровня сети, расположенного на линии с номером
, где INT - функция вычисления целой части от аргумента, каждый выход каждого переключателя (k-j)-го уровня соединен с одним входом переключателя (k-j+1)-го уровня, первые входы X переключателей первого уровня T, где
, являются входами нечетных разрядов X n-разрядного входа сети ibaseline, вторые входы X переключателей первого уровня T, где
, являются входами четных разрядов X n-разрядного входа сети ibaseline, первые выходы Y переключателей последнего уровня T, где
, являются выходами нечетных разрядов Y n-разрядного выхода сети ibaseline, вторые выходы Y переключателей последнего уровня T, где
, являются выходами четных разрядов Y, n-разрядного выхода сети ibaseline.
0
k-1
1
n
1
n
I
n
1
n-1
Блок формирования битов маскирования и управления (см. фиг.5) характеризуется наличием бинарных входов управления AOR, RL, AMUX, AIOR, k-разрядного входа А-A значения числа сдвига данных, n-разрядного входа битов маскирования данных F-F, образующих соответстующие входы предлагаемого устройства. Блок формирования битов маскирования и управления характеризуется также наличием n-разрядного выхода FI-FI битов маскирования входных данных, n-разрядного выхода FO-FO битов маскирования выходных данных, (n-1)-разрядного выхода С-C кода управления сдвигом, образующих соответстующие выходы предлагаемого устройства.
i
i
i
i
<mrow><mi>i</mi><mo>=</mo><mover accent="true"><mrow><mn>1,</mn><mi>n</mi></mrow><mo stretchy="true">¯</mo></mover></mrow>
<mrow><mi>i</mi><mo>=</mo><mover accent="true"><mrow><mn>1,</mn><mi>n</mi></mrow><mo stretchy="true">¯</mo></mover></mrow>
Блок формирования битов маскирования и управления включает идентичные первый 23 и второй 24 блоки побитовой дизъюнкции (см. фиг.9), каждый из которых характеризуется наличием n-разрядного входа данных, n-разрядного выхода данных, входа управления AOR для блока 23 или AIOR для блока 24. Блок побитовой дизъюнкции 23 осуществляет логические функции побитовое логическое ИЛИ, т.е. Y=X∨AOR, где
. Блок побитовой дизъюнкции 24 осуществляет логические функции побитовое логическое ИЛИ, т.е. FI=X∨AIOR, где
.
1,1
1,n
2,1
2,n
1
n
Блок формирования битов маскирования и управления также включает мультиплексор битов маскирования 25, имеющий первый n-разрядный вход X-X, второй n-разрядный вход Х-Х, n-разрядный выход FO-FO битов маскирования выходных данных и бинарный вход управления AMUX.
i,j
1
2
<mrow><mi>i</mi><mo>=</mo><mover accent="true"><mrow><msup><mrow><mn>1,2</mn></mrow><mrow><mi>j</mi><mo>−</mo><mn>1</mn></mrow></msup></mrow><mo stretchy="true">¯</mo></mover></mrow>
<mrow><mi>j</mi><mo>=</mo><mover accent="true"><mrow><mn>1,</mn><mi>k</mi></mrow><mo stretchy="true">¯</mo></mover></mrow>
<mrow><mi>c</mi><mo>=</mo><mi>f</mi><mo>∧</mo><mi>c</mi><mi>i</mi><mo>∨</mo><mover accent="true"><mrow><mi>f</mi><mo>∨</mo><mi>c</mi><mi>i</mi></mrow><mo stretchy="true">¯</mo></mover></mrow>
<mrow><msub><mi>f</mi><mn>1</mn></msub><mo>=</mo><mover accent="true"><mrow><mrow><mo>(</mo><mrow><mover accent="true"><mrow><mi>r</mi><mi>o</mi><mi>t</mi><mi>r</mi></mrow><mo stretchy="true">¯</mo></mover><mo>∨</mo><mover accent="true"><mrow><mi>f</mi><mo>∨</mo><mi>c</mi><mi>i</mi></mrow><mo stretchy="true">¯</mo></mover></mrow><mo>)</mo></mrow><mo>∧</mo><mrow><mo>(</mo><mrow><mover accent="true"><mrow><mi>f</mi><mo>∧</mo><mi>c</mi><mi>i</mi></mrow><mo stretchy="true">¯</mo></mover></mrow><mo>)</mo></mrow></mrow><mo stretchy="true">¯</mo></mover></mrow>
<mrow><msub><mi>f</mi><mn>2</mn></msub><mo>=</mo><mover accent="true"><mrow><mrow><mo>(</mo><mrow><mi>r</mi><mi>o</mi><mi>t</mi><mi>r</mi><mo>∨</mo><mover accent="true"><mrow><mi>f</mi><mo>∨</mo><mi>c</mi><mi>i</mi></mrow><mo stretchy="true">¯</mo></mover></mrow><mo>)</mo></mrow><mo>∧</mo><mrow><mo>(</mo><mrow><mover accent="true"><mrow><mi>f</mi><mo>∧</mo><mi>c</mi><mi>i</mi></mrow><mo stretchy="true">¯</mo></mover></mrow><mo>)</mo></mrow></mrow><mo stretchy="true">¯</mo></mover></mrow>
Блок формирования битов маскирования и управления также включает n/2 логических инверторов и n-1 модуль M, где
,
, формирования битов кода управления сдвигом, каждый из которых имеет три бинарных входа f, ci, rotr и три бинарных выхода с, f, f, и выполняет три логических функции
,
,
. На языке Verilog эти логические функции описываются следующим образом:
c=f&ci|~(f|ci);
1
f=~((~rotr|~(f|ci))&~(f&ci));
2
f=~((rotr|~(f|ci))&~(f&ci));
i,j
<mrow><mi>i</mi><mo>=</mo><mover accent="true"><mrow><msup><mrow><mn>1,2</mn></mrow><mrow><mi>j</mi><mo>−</mo><mn>1</mn></mrow></msup></mrow><mo stretchy="true">¯</mo></mover></mrow>
<mrow><mi>j</mi><mo>=</mo><mover accent="true"><mrow><mn>1,</mn><mi>k</mi></mrow><mo stretchy="true">¯</mo></mover></mrow>
На фиг.6 приведена возможная схема модуля формирования битов кода управления сдвигом M, где
,
.
1,1
1
1,2
2
2,2
3
1,3
2,3
3,3
4,3
4
5
6
7
i,j
i,j
p
<mrow><mi>j</mi><mo>=</mo><mover accent="true"><mrow><mn>1,</mn><mi>k</mi></mrow><mo stretchy="true">¯</mo></mover></mrow>
<mrow><mi>i</mi><mo>=</mo><mover accent="true"><mrow><msup><mrow><mn>1,2</mn></mrow><mrow><mi>j</mi><mo>−</mo><mn>1</mn></mrow></msup></mrow><mo stretchy="true">¯</mo></mover></mrow>
j-1
j-1
Модули формирования битов кода управления соединены так, что образуют двоичное дерево (пирамидальную структуру) с k уровнями. При этом на первом уровне двоичного дерева содержится один модуль M, выход с которого соединен с выходом С блока формирования битов маскирования и управления. На втором уровне двоичного дерева содержится два модуля: М, выход с которого соединен с выходом C блока формирования битов маскирования и управления, и M, выход с которого соединен с выходом C блока формирования битов маскирования и управления. На третьем уровне двоичного дерева содержится четыре модуля M, M, M, M, выходы с которых соответственно соединены с выходами С, С, C, C, блока формирования битов маскирования и управления. В общем случае на уровне j, где
, содержится 2 модулей M, где
, причем выход с каждого из модулей M соединен с выходом C блока формирования битов маскирования и управления, где р=2+i-1.
1
i,j
2i-1,j+1
2
i,j
2i,j+1
1,1
i,j
j-1
0
k-1
<mrow><mi>i</mi><mo>=</mo><mover accent="true"><mrow><msup><mrow><mn>1,2</mn></mrow><mrow><mi>j</mi><mo>−</mo><mn>1</mn></mrow></msup></mrow><mo stretchy="true">¯</mo></mover></mrow>
<mrow><mi>j</mi><mo>=</mo><mover accent="true"><mrow><mn>1,</mn><mi>k</mi></mrow><mo stretchy="true">¯</mo></mover></mrow>
<mrow><mi>i</mi><mo>=</mo><mover accent="true"><mrow><msup><mrow><mn>1,2</mn></mrow><mrow><mi>j</mi><mo>−</mo><mn>1</mn></mrow></msup></mrow><mo stretchy="true">¯</mo></mover></mrow>
<mrow><mi>j</mi><mo>=</mo><mover accent="true"><mrow><mn>1,</mn><mi>k</mi></mrow><mo stretchy="true">¯</mo></mover></mrow>
<mrow><mi>i</mi><mo>=</mo><mover accent="true"><mrow><msup><mrow><mn>1,2</mn></mrow><mrow><mi>j</mi><mo>−</mo><mn>1</mn></mrow></msup></mrow><mo stretchy="true">¯</mo></mover></mrow>
Выход f каждого модуля M, где
, формирования битов кода управления, расположенного на уровне j, где
, соединен с входом f модуля M, расположенного на уровне j+1. Выход f каждого модуля M, где
, формирования битов кода управления сдвигом, расположенного на уровне j, где
, соединен с входом f модуля M, расположенного на уровне j+1. На вход f модуля М формирования битов кода управления подается сигнал с низким логическим уровнем. Вход ci каждого модуля M формирования битов кода управления сдвигом, расположенного на уровне j, где
, соединен с входом разряда A k-разрядного входа A-A значения числа сдвига данных, расположенного в блоке формирования битов маскирования и управления.
i,j
Вход rotr каждого модуля M соединен с бинарным входом управления направлением сдвига данных RL.
1
i,k
2i-1
2
i,k
2i
i
1,i
1
n
1
n
<mrow><mi>i</mi><mo>=</mo><mover accent="true"><mrow><mn>1,</mn><mi>n</mi><mo>/</mo><mn>2</mn></mrow><mo stretchy="true">¯</mo></mover></mrow>
<mrow><mi>i</mi><mo>=</mo><mover accent="true"><mrow><mn>1,</mn><mi>n</mi><mo>/</mo><mn>2</mn></mrow><mo stretchy="true">¯</mo></mover></mrow>
<mrow><mi>i</mi><mo>=</mo><mover accent="true"><mrow><mn>1,</mn><mi>n</mi></mrow><mo stretchy="true">¯</mo></mover></mrow>
<mrow><mi>i</mi><mo>=</mo><mover accent="true"><mrow><mn>1,</mn><mi>n</mi></mrow><mo stretchy="true">¯</mo></mover></mrow>
Выход f каждого модуля M, расположенного на последнем k-м уровне, где
, соединен с входом логического инвертора D. Выход f каждого модуля M расположенного на последнем k-м уровне, где
, соединен с входом логического инвертора D. Каждый выход логического инвертора D, где
, соединен с разрядом X, где
, первого n-разрядного входа мультиплексора битов маскирования 25, n-разрядный выход которого Y-Y соединен с n-разрядным выходом FO-FO блока формирования битов маскирования и управления.
1
n
1
n
1
n
1
n
2,1
2,n
1
n
В блоке формирования битов маскирования и управления n-разрядный вход F-F битов маскирования соединен с n-разрядным входом Х-X первого блока побитовой дизъюнкции 23 и с n-разрядным входом Х-X второго блока побитовой дизъюнкции 24. n-разрядный выход Y-Y первого блока побитовой дизъюнкции 23 соединен со вторым n-разрядным входом Х-Х мультиплексора битов маскирования 25. Бинарный вход AOR первого блока побитовой дизъюнкции 23 является входом AOR устройства. Бинарный вход AIOR второго блока побитовой дизъюнкции 24 является входом AIOR устройства. n-разрядный выход FI-FI 23 является выходом блока формирования битов маскирования и управления.
Вход AMUX мультиплексора битов маскирования 25 является входом предлагаемого устройства.
Под соединением входа и выхода или выхода и входа понимается условие, при котором если подать сигнал на вход, соединенный с выходом, или выход, соединенный с входом, на выходе через некоторую временную задержку, обусловленную временем распространения сигнала, появится входной сигнал и, наоборот, если подать сигнал на выход, на входе через некоторую временную задержку, обусловленную временем распространения сигнала, появится выходной сигнал. В частности, соединение может быть электрическим соединением.
Упомянутые ранее n-разрядные мультиплексоры 2→1 входных данных и n-разрядный мультиплексор 2→1 выходных данных представляют собой одинаковые модули, каждый из которых имеет первый n-разрядный вход данных, второй n-разрядный вход данных, n-разрядный выход данных и бинарный вход управления. Если на вход поступает сигнал с низким логическим уровнем, на n-разрядный выход мультиплексора поступают сигналы с первого n-разрядного входа данных. Если на вход поступает сигнал с высоким логическим уровнем, на n-разрядный выход мультиплексора поступают сигналы со второго n-разрядного входа данных.
1,1,1
1,n/2,k
2,1,1
2,n/2k
1,1
n/2,k
Упомянутый ранее m-разрядный мультиплексор 2→1 аналогичен описанному выше n-разрядному мультиплексору 2→1, но имеет m-разрядные входы данных C-C, С-С и m-разрядный выход данных Y-Y.
Описание и способ построения n-разрядных мультиплексоров 2→1 известен в технике, их можно найти, например, в справочнике: Пухальский Г.И., Новосельцева Т.Я. Проектирование дискретных устройств на интегральных микросхемах: Справочник. М.: Радио и связь, 1990. 304 с.
1
n
1
n
i
j
k-1
2
1
р
р
р
k-1
1
0
р
p
p-1
<mrow><mi>i</mi><mo>=</mo><mover accent="true"><mrow><mn>1,</mn><mi>n</mi></mrow><mo stretchy="true">¯</mo></mover></mrow>
<mrow><mi>p</mi><mo>=</mo><mover accent="true"><mrow><mn>1,</mn><mi>k</mi><mo>−</mo><mn>1</mn></mrow><mo stretchy="true">¯</mo></mover></mrow>
<mrow><mi>p</mi><mo>=</mo><mover accent="true"><mrow><mn>1,</mn><mi>k</mi><mo>−</mo><mn>1</mn></mrow><mo stretchy="true">¯</mo></mover></mrow>
k-1
1
0
Выходной соединитель имеет n-разрядный вход Х-X данных, n-разрядный выход Y-Y данных, где каждый входной разряд X с номером i,
, соединен с выходным разрядом Y с номером j, причем, если i - нечетное число, то j=m, если i - четное число, то j=m+n/2, где m=ξ(…ξ(ξ(1)))…), ξ(х)=2х-1+а значение а, где
, определяется двоичным представлением i: i=a2+…+a2+a2. Таким образом, число m определяется путем последовательного вычисления функции ξ, где
, аргументом функции ξ является значение функции ξ, а аргументом функции является 1.
1
n
1
n
i
j
k-1
2
1
p
p
р
k-1
1
0
р
р
p-1
1
<mrow><mi>i</mi><mo>=</mo><mover accent="true"><mrow><mn>1,</mn><mi>n</mi></mrow><mo stretchy="true">¯</mo></mover></mrow>
<mrow><mi>p</mi><mo>=</mo><mover accent="true"><mrow><mn>1,</mn><mi>k</mi><mo>−</mo><mn>1</mn></mrow><mo stretchy="true">¯</mo></mover></mrow>
<mrow><mi>p</mi><mo>=</mo><mover accent="true"><mrow><mn>1,</mn><mi>k</mi><mo>−</mo><mn>1</mn></mrow><mo stretchy="true">¯</mo></mover></mrow>
k-1
1
0
Входной соединитель имеет n-разрядный вход Х-X данных, n-разрядный выход Y-Y данных, где каждый выходной разряд Y с номером i,
соединен с входным разрядом X с номером j, причем, если i - нечетное число, то j=m, если i - четное число, то j=m+n/2, где m=ξ(…ξ(ξ(1)))…), ξ(x)=2x-1+a значение а, где
, определяется двоичным представлением номера i: i=a2+…+a2+a2. Таким образом, число m определяется путем последовательного вычисления функции ξ, где
, аргументом функции ξ является значение функции ξ, а аргументом функции ξ является 1.
1
n
2,1
2,n
Обозначения блоков, приведенные на фиг.2, совпадают с обозначениями на фиг.1. Входной и выходной соединители не показаны на фиг.2 в виде блоков, а реализованы описанным выше способом соединения выхода блока маскирования данных на входе с первым входом мультиплексора входных данных, а также описанным выше способом соединения выхода Y-Y блока маскирования данных на выходе со вторым входом Х-Х мультиплексора выходных данных.
Устройство работает следующим образом.
Режим работы устройства задается подачей на бинарные входы управления AOR, RL, AMUX, AIOR, AOUT, AC управляющих сигналов в соответствии с табл.1
Табл.1
Сигналы управления устройством перестановок и сдвигов битов данных
Инструкции
RL
AOUT
AC
AMUX
AOR
AIOR
shr r<sub>1</sub>=r<sub>2</sub>,r<sub>3</sub>
0
1
1
0
1
-
shl r<sub>1</sub>=r<sub>2</sub>,r<sub>3</sub>
1
1
1
0
1
-
rotr r<sub>1</sub>=r<sub>2</sub>,r<sub>3</sub>
0
1
1
1
1
1
rotl r<sub>1</sub>=r<sub>2</sub>,r<sub>3</sub>
1
1
1
1
1
1
рех r<sub>1</sub>=r<sub>2</sub>, ar.b<sub>1</sub>, ar.b<sub>2</sub>, ar.b<sub>3</sub>
-
1
0
1
1
0
pdep r<sub>1</sub>=r<sub>2</sub>, ar.b<sub>1</sub>, ar.b<sub>2</sub>, ar.b<sub>3</sub>
-
0
0
1
0
1
bsn r<sub>1</sub>=r<sub>2</sub>, ar.b<sub>1</sub>, ar.b<sub>2</sub>, ar.b<sub>3</sub> или ibsn r<sub>1</sub>=r<sub>2</sub>, ar.b<sub>1</sub>, ar.b<sub>2</sub>, ar.b<sub>3</sub>
-
0
0
1
1
1
Краткое описание инструкций из табл.1 приведено в табл.2. Подробное описание инструкций из табл.1 можно найти, например, в статье «Методы синтеза устройств, выполняющих инструкции перестановки битов данных». / Сотов Л.С. // Гетеромагнитная микроэлектроника. 2011. Вып.10. С.25-50.
Табл.2
Инструкции манипуляции битами данных
Инструкция
Описание
bsn r<sub>1</sub>=r<sub>2</sub>, ar.b<sub>1</sub>, ar.b<sub>2</sub>, ar.b<sub>3</sub> или ibsn r<sub>1</sub>=r<sub>2</sub>, ar.b<sub>1</sub>, ar.b<sub>2</sub>, ar.b<sub>3</sub>
Осуществление инструкции перестановки битов данных с использованием многоуровневой коммутационной сети baseline или ibaseline в соответствии с управляющими кодами в регистрах ar.b<sub>1</sub>, ar.b<sub>2</sub>, ar.b<sub>3</sub> микропроцессора и запись результата в регистр r<sub>1</sub> микропроцессора.
рех r<sub>1</sub>=r<sub>2, </sub>r<sub>3</sub>, ar.b<sub>1</sub>, ar.b<sub>2</sub>, ar.b<sub>3</sub>
Статическая инструкция извлечения группы битов из регистра r<sub>2</sub> и размещение их в начале регистра r<sub>1</sub> в соответствии с управляющими кодами в регистрах ar.b<sub>1</sub>, ar.b<sub>2</sub>, ar.b<sub>3</sub> микропроцессора и запись результата в регистр r<sub>1</sub> микропроцессора и запись результата в регистр r<sub>1</sub> микропроцессора.
pder r<sub>1</sub>=r<sub>2, </sub>r<sub>3</sub>, ar.b<sub>1</sub>, ar.b<sub>2</sub>, ar.b<sub>3</sub>
Статическая инструкция размещения группы битов регистра r<sub>2</sub> в регистре r<sub>1</sub> в соответствии с управляющими кодами в регистрах ar.b<sub>1</sub>, ar.b<sub>2</sub>, ar.b<sub>3</sub> микропроцессора и запись результата в регистр r<sub>1</sub> микропроцессора.
shr r1=r<sub>2</sub>, r<sub>3</sub>
Логический сдвиг данных в регистре r<sub>2</sub> микропроцессора вправо на число бит, содержащееся в регистре r<sub>3</sub> микропроцессора и запись результата в регистр r<sub>1</sub> микропроцессора.
shl r<sub>1</sub>=r<sub>2</sub>, r<sub>3</sub>
Логический сдвиг данных в регистре r<sub>2</sub> микропроцессора вправо на число бит, содержащееся в регистре r<sub>3</sub> микропроцессора и запись результата в регистр r<sub>1</sub> микропроцессора.
rotr r<sub>1</sub>=r<sub>2</sub>, r<sub>3</sub>
Циклический сдвиг данных в регистре r<sub>2</sub> микропроцессора вправо на число бит, содержащееся в регистре r<sub>3</sub> микропроцессора и запись результата в регистр r<sub>1</sub> микропроцессора.
rotl r<sub>1</sub>=r<sub>2</sub>, r<sub>3</sub>
Циклический сдвиг данных в регистре r<sub>2</sub> микропроцессора вправо на число бит, содержащееся в регистре r<sub>3</sub> микропроцессора и запись результата в регистр r<sub>1</sub> микропроцессора.
1
n
2
1
n
3
1,1,1
1,n/2,k
1
1
2
3
0
k-1
2
На вход Х-X n-разрядного блока маскирования данных на входе подаются входные данные, например, из регистра r микропроцессора. При реализации инструкций рех или pdep на n-разрядный вход битов маскирования F-F блока формирования битов маскирования и управления подаются биты маскирования, например, из регистра r микропроцессора. Для реализации инструкций bsn, рех или pdep на первый m-разрядный вход C-C битов управления мультиплексора битов управления подаются коды управления, например, из регистров ar.b, ar.b, ar.b, ar.b микропроцессора. Для осуществления инструкций shr, shl, rotr, rotl, логического и циклического сдвигов на k-разрядный вход A-A подается значение числа сдвига данных. Значение числа сдвига данных может содержаться, например, в младших битах регистра r микропроцессора, так как при выполнении инструкций shr, shl биты маскирования формируются блоком формирования битов маскирования и управления, а при выполнении инструкций rotr, rotl биты маскирования не используются.
1
n
1
После выполнения одной из инструкций bsn, рех, pdep, shr, shl, rotr или rotl результат формируется на n-разрядном выходе Y-Y мультиплексора выходных данных и записывается, например, в регистр r микропроцессора.
Рассмотрим отдельно пути прохождения данных в схемах модуля манипуляции битами, представленных на фиг.1, фиг.2, при реализации инструкций bsn, рех, pdep, shr, shl, rotr или rotl.
1
n
1
n
1,1
n/2,k
1
n
При выполнении инструкции bsn на n-разрядный вход Х-X блока маскирования данных на входе поступают данные, которые без изменения проходят через этот блок, поступают на второй вход мультиплексора входных данных и с его выхода Y-Y на вход многоуровневой коммутационной сети. Одновременно через первый вход и затем выход n-разрядного мультиплексора биты управления переключателями сети поступают на вход C-C управления переключателями коммутационной сети. С выхода Y-Y сети перестановленные биты данных без изменения проходят через блок маскирования данных на выходе и поступают на выход модуля манипуляции битами через первый вход, а затем выход мультиплексора выходных данных.
1
n
1
n
1
n
1,1
n/2,k
При выполнении инструкции pex биты данных поступают на n-разрядный вход Х-X блока маскирования данных на входе, на второй вход F-F которого подаются биты маскирования с выхода FI-FI блока формирования битов маскирования и управления. Маскированные данные через второй вход, а затем выход мультиплексора входных данных поступают на вход многоуровневой коммутационной сети. Одновременно через первый вход и затем выход m-разрядного мультиплексора биты управления переключателями сети поступают на вход C-C управления переключателями коммутационной сети. С выхода сети данные, проходя без изменения через блок маскирования данных на выходе, подаются на вход выходного соединителя и, проходя через него, поступают на второй вход мультиплексора выходных данных и далее попадают на его выход.
1
n
1,1
n/2,k
1
n
При выполнении инструкции pdep данные поступают на n-разрядный вход Х-X блока маскирования данных на входе, проходят его без изменений и через входной соединитель поступают на первый вход мультиплексора входных данных и с выхода этого мультиплексора поступают на вход многоуровневой коммутационной сети. Одновременно через первый вход и затем выход m-разрядного мультиплексора биты управления переключателями сети поступают на вход C-C управления переключателями коммутационной сети. Далее данные поступают на вход блока маскирования данных на выходе, на второй вход которого поступают биты маскирования с выхода FO-FO блока формирования битов маскирования и управления. Маскированные на выходе данные через выходной соединитель поступают на второй вход и затем на выход мультиплексора выходных данных, формируя, таким образом, выходные данные предлагаемого устройства.
1
n
1,1
n/2,k
1
n-1
При выполнении инструкций shr, shl, rotr, rotl биты данных поступают на n-разрядный вход Х-X блока маскирования данных на входе и проходят его без изменений. С выхода блока маскирования данных на входе данные через второй вход, а затем выход мультиплексора входных данных поступают на вход многоуровневой коммутационной сети. Управление осуществляется путем подачи на вход C-C сети кодов управления с выхода C-C блока формирования битов маскирования и управления через второй вход и затем выход мультиплексора битов управления. С выхода сети данные поступают на вход блока маскирования данных на выходе.
1
n
При выполнении инструкций rotr, rotl на второй вход F-F блока маскирования данных на выходе подаются сигналы с высоким логическим уровнем и данные без изменений подаются на вход выходного соединителя, проходя через который, поступают на второй вход мультиплексора выходных данных и далее попадают на его выход.
1
n
При выполнении инструкций shr, shl на второй вход F-F блока маскирования данных на выходе подаются сигналы маскирования и маскированные данные подаются на вход выходного соединителя, проходя через который, поступают на второй вход мультиплексора выходных данных и далее попадают на его выход.
Таким образом, при одинаковой функциональности с существующими решениями предлагаемое устройство имеет более простую конструкцию за счет использования только одной многоуровневой коммутационной сети с топологией baseline или ibaseline для выполнения произвольных перестановок, циклических и логических сдвигов данных, операций извлечения и размещения в заданных позициях групп битов данных. Предложенное решение имеет расширенную функциональность по сравнению с используемыми устройствами логического и циклического сдвига и позволяет вычислять циклические и логические сдвиги данных, операции извлечения и размещения в заданных позициях групп битов данных за один цикл микропроцессора. Произвольные перестановки осуществляются за два цикла процессора с последовательным использованием двух команд bsn. При этом сохраняется высокое быстродействие устройства, что существенно повышает производительность микропроцессоров при решении задач обработки изображений, распознавания образов, кодирования, стеганографии, криптографии, обработки сигналов и т.п.