УСТРОЙСТВО СЕЛЕКЦИИ БОЛЬШЕГО ИЗ ДВОИЧНЫХ ЧИСЕЛ
DEVICE FOR SELECTING GREATER OF BINARY NUMBERS

Изобретение относится к вычислительной технике и может быть использовано для построения средств автоматики, функциональных узлов систем управления и др.
Известны устройства селекции большего из двоичных чисел (см., например, патент РФ 2363034, кл. G06F 7/02, 2009 г.), выполняющие селекцию большего из двух n-разрядных двоичных чисел, задаваемых двоичными сигналами.
К причине, препятствующей достижению указанного ниже технического результата при использовании известных устройств селекции большего из двоичных чисел, относятся ограниченные функциональные возможности, обусловленные тем, что не допускается обработка трех n-разрядных двоичных чисел, задаваемых двоичными сигналами.
Наиболее близким устройством того же назначения к заявленному изобретению по совокупности признаков является принятое за прототип устройство селекции большего из двоичных чисел (патент РФ 2300135, кл. G06F 7/02, 2007 г.), которое содержит 2×(n-2) элементов 2И и выполняет селекцию большего из двух n-разрядных двоичных чисел, задаваемых двоичными сигналами.
К причине, препятствующей достижению указанного ниже технического результата при использовании прототипа, относятся ограниченные функциональные возможности, обусловленные тем, что не допускается обработка трех n-разрядных двоичных чисел, задаваемых двоичными сигналами.
Техническим результатом изобретения является расширение функциональных возможностей за счет обеспечения селекции большего из трех n-разрядных двоичных чисел, задаваемых двоичными сигналами.
Указанный технический результат при осуществлении изобретения достигается тем, что в устройстве селекции большего из двоичных чисел, содержащем 2×(n-2) элементов 2И, особенность заключается в том, что в него дополнительно введены n+1 элементов 2И, n элементов 3ИЛИ, n-1 элементов НЕ и 3×(n-1) мажоритарных элементов, причем все элементы сгруппированы в n групп так, что k-я () и n-я группы содержат соответственно элемент 3ИЛИ, элемент НЕ, три мажоритарных элемента и элемент 3ИЛИ, а r-я () группа дополнительно содержит три элемента 2И, в k-й группе второй вход i-го () мажоритарного элемента, подключенного третьим входом к выходу элемента НЕ, и вход элемента НЕ соединены соответственно с i-ым входом и выходом элемента 3ИЛИ, в r-й группе выход i-го элемента 2И подключен к i-му входу элемента 3ИЛИ, в m-й () группе первый вход i-го элемента 2И соединен с первым входом i-го мажоритарного элемента, выход i-го мажоритарного элемента k-й группы подключен к первому входу i-го элемента 2И (k+1)-й группы, а второй вход i-го мажоритарного элемента первой группы, подключенного первым входом к шине единичного потенциала, второй вход i-го элемента 2И r-й группы и выход элемента 3ИЛИ j-й () группы соединены соответственно с (n×i-n+1)-ым, (n×i-n+r)-ым входами j-ым выходом устройства селекции большего из двоичных чисел.
На фиг. представлена схема предлагаемого устройства селекции большего из двоичных чисел.
12
3n
1
n
1
n-1
11
3(n-1)
k
k
1k
2k
3k
n
r
2r
3r
ik
k
k
k
ir
im
ik
r
im
i(k+1)
i1
ir
j
Устройство селекции большего из двоичных чисел содержит элементы 2И 1,…,1, элементы 3ИЛИ 2,…,2, элементы НЕ 3,…,3, мажоритарные элементы 4,…,4, причем все элементы сгруппированы в n групп так, что k-я () и n-я группы содержат соответственно элементы 2, 3, 4, 4 4 и элемент 2, а r-я () группа дополнительно содержит элементы 1, 1, 1 второй вход элемента 4 (), подключенного третьим входом к выходу элемента 3, и вход элемента 3 соединены соответственно с i-ым входом и выходом элемента 2, выход элемента 1, первый вход элемента 1 () и выход элемента 4 подключены соответственно к i-му входу элемента 2, первому входу элемента 4 и первому входу элемента 1, а второй вход элемента 4, подключенного первым входом к шине единичного потенциала, второй вход элемента 1 и выход элемента 2 () соединены соответственно с (n×i-n+1)-ым, (n×i-n+r)-ым входами и j-ым выходом устройства селекции большего из двоичных чисел.
n-1
0
n-1
0
n-1
0
n-1
0
n-1
0
n-1
0
n-1,
n-1
n-1
0
0,
0
Работа предлагаемого устройства селекции большего из двоичных чисел осуществляется следующим образом. На его первый,…,n-й, (n+1)-й,…, (2×n)-й, (2×n+1)-й,…, (3×n)-й входы подаются соответственно произвольные двоичные сигналы x,…,х∈{0,1}, y,…,у∈{0,1}, g,…,g∈{0,1}, которые задают подлежащие обработке n-разрядные двоичные числа x…х, y…у, g…g (x y, g и х, y g определяют значения старших и младших разрядов соответственно). Тогда сигнал на j-ом () выходе предлагаемого устройства будет определяться выражением
где
⎯
Здесь ∨, ⋅, , # есть символы операций ИЛИ, И, НЕ, Maj. Отметим, что сигнал на выходе трехвходового мажоритарного элемента равен 1 (0) только тогда, когда на двух или на трех входах этого элемента действуют сигналы, равные 1 (0). В представленной ниже таблице приведены значения реализуемых выражениями (2), (3), (4) функций на всех возможных наборах значений их аргументов. Жирным в таблице выделены значения функций и их аргументов при j=2.
Анализ данных, приведенных в таблице, позволяет заключить, что:
n-1
n-1
n-1
n-1
n-1
n-1
n-1
n-1
n-1
n-1
n-1
n-1
n-1
n-1
n-1
n-1
n-1
n-1
n-1
n-1
n-1
11
21
31
11
21
31
21
11
31
31
11
21
11
21
31
11
31
21
21
31
11
1) если x=y=g либо x>y=g либо y>x=g либо g>x=y либо x=y>g либо x=g>y либо y=g>x, то соответственно z=z=z=1 либо z=1, z=z=0 либо z=1, z=z=0 либо z=1, z=z=0 либо z=z=1, z=0 либо z=z=1, z=0 либо z=z=1, z=0;
1(j-2)
2(j-2)
3(j-2)
n-j+1
n-j+1
n-j+1
1(j-2)
2(j-2)
3(j-2)
n-j+1
n-j+1
n-j+1
1(j-2)
2(j-2)
3(j-2)
n-j+1
n-j+1
n-j+1
1(j-2)
2(j-2)
3(j-2)
n-j+1
n-j+1
n-j+1
1(j-2
2(j-2)
3(j-2)
n-j+1
n-j+1
n-j+1
1(j-2)
2(j-2)
3(j-2)
n-j+1
n-j+1
n-j+1
1(j-2)
2(j-2)
3(j-2)
n-j+1
n-j+1
n-j+1
1(j-1)
2(j-1)
3(j-1)
1(j-1)
2(j-1)
3(j-l)
2(j-1)
1(j-1)
3(j-1)
3(j-1)
1(j-1)
2(j-1)
1(j-1)
2(j-1)
3(j-1)
1(j-1)
3(j-1)
2(j-1)
2(j-1)
3(j-1)
1(j-1)
2) если z=z=z=1 и x=y=g, либо z=z=z=1 и x>y=g либо z=z=z=1 и y>x=g либо z=z=z=1 и g>x=y либо z=z=z=1 и x=y>g либо z=z=z=1 и x=g>y либо z=z=z=1 и y=g>x, то соответственно z=z=z=1 либо z=1, z=z=0 либо z=1, z=z=0 либо z=1, z=z=0 либо z=z=1, z=0 либо z=z=1, z=0 либо z=z=1, z=0;
1(j-2)
2(j-2)
3(j-2)
2(j-2)
1(j-2)
3(j-2)
3(j-2)
1(j-2)
2(j-2)
1(j-1)
2(j-1)
3(j-1)
2(j-1)
1(j-1)
3(j-1)
3(j-1)
1(j-1)
2(j-1)
3) если z=1 и z=z=0 либо z=1 и z=z=0 либо z=1 и z=z=0, то соответственно z=1, z=z=0 либо z, z=z=0 либо z=1, z=z=0;
1(j-2)
2(j-2)
3(j-2)
n-j+1
n-j+1
1(j-2)
2(j-2)
3(j-2)
n-j+1
n-j+1
1(j-2)
2(j-2)
3(j-2)
n-j+1
n-j+1
1(j-1)
2(j-1)
3(j-1)
1(j-1)
2(j-1)
3(j-1)
2(j-1)
1(j-1)
3(j-1)
4) если z=z=1, z=0 и x=y либо z=z=1, z=0 и x>y либо z=z=1, z=0 и x<y, то соответственно z=z=1, z=0 либо z=1, z=z=0 либо z=1, z=z=0;
1(j-2)
3(j-2)
2(j-2)
n-j+1
n-j+1
1(j-2)
3(j-2)
2(j-2)
n-j+1
n-j+1
1(j-2)
3(j-2)
2(j-2)
n-j+1
n-j+1
1(j-1)
3(y-1)
2(j-1)
1(j-l)
2(j-1)
3(j-l)
3(j-l)
1(j-1)
2(j-1)
5) если z=z=1, z=0 и x=g либо z=z=1, z=0 и x>g либо z=z=1, z=0 и x<g, то соответственно z=z=1, z=0 либо z=1, z=z=0 либо z=1, z=z=0;
2(j-2)
3(j-2)
1(j-2)
n-j+1
n-j+1
2(j-2)
3(j-2)
1(j-2)
n-j+1
n-j+1
2(j-2)
3(j-2)
1(j-2)
n-j+1
n-j+1
2(j-1)
3(j-1)
1(j-1)
2(j-l)
1(j-l)
3(j-l)
3(j-l)
1(j-l)
2(j-1)
6) если z=z=1, z=0 и y=g либо z=z=1, z=0 и y>g либо z=z=1, z=0 и y<g, то соответственно z=z=1, z=0 либо z=1, z=z=0 либо z=1, z=z=0.
Таким образом, на первом и r-ом () выходах предлагаемого устройства согласно (1) получим
и
,
n-1
n-r+1
n-1
n-r+1
n-1
n-r+1
n-1
0
n-1
0
n-1
0
n-1
0
n-1
0
n-1
0
n-1
0
n-1
0
0
n-1
n-1
0
где x…x, y…y, g…g - фрагменты n-разрядных двоичных чисел x…x, y…y, g…g. Следовательно, с учетом (5), (6) имеем w…w=max(x…x, y…y, g…g), где w…w есть n-разрядное двоичное число, задаваемое двоичными сигналами w,…,w∈{0,1} (w и w определяют значения старшего и младшего разрядов соответственно).
Вышеизложенные сведения позволяют сделать вывод, что предлагаемое устройство обладает более широкими по сравнению с прототипом функциональными возможностями, так как обеспечивает селекцию большего из трех n-разрядных двоичных чисел, задаваемых двоичными сигналами.