УСТРОЙСТВО СЕЛЕКЦИИ ДВОИЧНЫХ ЧИСЕЛ
DEVICE FOR SELECTING BINARY NUMBERS

Изобретение относится к вычислительной технике и может быть использовано для построения средств автоматики, функциональных узлов систем управления и др.
Известны устройства селекции двоичных чисел (см., например, патент РФ 2300130, кл. G06F 7/02, 2007 г.), выполняющие селекцию меньшего из двух n-разрядных двоичных чисел, задаваемых двоичными сигналами.
К причине, препятствующей достижению указанного ниже технического результата при использовании известных устройств селекции двоичных чисел, относятся ограниченные функциональные возможности, обусловленные тем, что не выполняется идентификация меньшего, либо селекция и идентификация большего, либо селекция произвольно назначенного из двух n-разрядных двоичных чисел, задаваемых двоичными сигналами.
Наиболее близким устройством того же назначения к заявленному изобретению по совокупности признаков является принятое за прототип устройство селекции двоичных чисел (патент РФ 2300135, кл. G06F 7/02, 2007 г.), которое содержит 2n входов, n выходов и выполняет селекцию большего из двух n-разрядных двоичных чисел, задаваемых двоичными сигналами.
К причине, препятствующей достижению указанного ниже технического результата при использовании прототипа, относятся ограниченные функциональные возможности, обусловленные тем, что не выполняется идентификация большего, либо селекция и идентификация меньшего, либо селекция произвольно назначенного из двух n-разрядных двоичных чисел, задаваемых двоичными сигналами.
Техническим результатом изобретения является расширение функциональных возможностей за счет обеспечения селекции и идентификации меньшего, либо селекции и идентификации большего, либо селекции произвольно назначенного из двух n-разрядных двоичных чисел, задаваемых двоичными сигналами.
Указанный технический результат при осуществлении изобретения достигается тем, что в устройстве селекции двоичных чисел, содержащем 2n входов и n выходов, особенность заключается в том, что в него введены 7n мажоритарных элементов, имеющих по три входа, и 2n элементов НЕ, причем все элементы сгруппированы в n групп так, что j-я () группа содержит семь мажоритарных элементов и два элемента НЕ, в j-й группе выход i-го () мажоритарного элемента, подключенного третьим входом к первому входу (i+2)-го мажоритарного элемента, выход (i+2)-го мажоритарного элемента, подключенного третьим входом к выходу i-го элемента НЕ, и вход i-го элемента НЕ соединены соответственно с первым, третьим входами (i+4)-го и выходом (3-i)-го мажоритарных элементов, а первый, третий и второй входы седьмого мажоритарного элемента соединены соответственно с первым входом пятого, первым входом шестого мажоритарных элементов и объединенными вторым входом (i+4)-го мажоритарного элемента, четвертым настроечным входом устройства селекции двоичных чисел, подключенного третьим настроечным входом к объединенным вторым входам первого-четвертого мажоритарных элементов j-й группы, выход (i+4)-го мажоритарного элемента предыдущей группы соединен с третьим входом i-го мажоритарного элемента последующей группы, а третий вход i-го мажоритарного элемента первой группы подключен к i-му настроечному входу устройства слекции двоичных чисел, j-й, (n+j)-й входы и j-й выход которого соединены соответственно с первым входом первого, первым входом второго и выходом седьмого мажоритарных элементов j-й группы.
На чертеже представлена схема предлагаемого устройства селекции двоичных чисел.
11
7n
11
2n
1j
…
7j
Устройство селекции двоичных чисел содержит мажоритарные элементы 1, …, 1, имеющие по три входа, и элементы НЕ 2, …, 2, причем все элементы сгруппированы в n групп так, что j-я () группа содержит элементы 1,, 1,
1j
2j
ij
(i+2)j
(i+2)j
ij
ij
(i+4)j
(3-i)j
2, 2, выход элемента 1(), подключенного третьим входом к первому входу элемента 1, выход элемента 1, подключенного третьим входом к выходу элемента 2, и вход элемента 2 соединены соответственно с первым, третьим входами элемента 1 и выходом элемента 1, а первый, третий и второй входы элемента
7j
5j
6j
(i+4)j
1j
4j
(i+4)k
i(k+1)
i1
1j
2j
7j
1 соединены соответственно с первыми входами элементов 1, 1 и объединенными вторым входом элемента 1, четвертым настроечным входом устройства селекции двоичных чисел, подключенного третьим настроечным входом к объединенным вторым входам элементов 1, …, 1, выход элемента 1 () соединен с третьим входом элемента 1, а третий вход элемента 1 подключен к i-му настроечному входу устройства селекции двоичных чисел, j-й, (n+j)-й входы и j-й выход которого соединены соответственно с первыми входами элементов 1, 1 и выходом элемента 1.
1
4
n-1
0
n-1
0
n-1
0
n-1
0
n-1
n-1
0,
0
5j
6j
Работа предлагаемого устройства селекции двоичных чисел осуществляется следующим образом. На его первый, …, четвертый настроечные входы подаются соответственно двоичные сигналы f, …, f∈{0,1}. На его первый, …, n-й и (n+1)-й, …, (2n)-й входы подаются соответственно двоичные сигналы x, …, x∈{0,1} и y, …, y∈{0,1}, которые задают подлежащие обработке n-разрядные двоичные числа x…xи y…y (x, yи xy определяют значения старших и младших pазрядов соответственно). Сигнал на выходе мажоритарного элемента равен 1 (0) только тогда, когда на двух или на всех входах этого элемента действуют сигналы, равные 1 (0). Следовательно, если на втором входе мажоритарного элемента присутствует 1 (0), то этот элемент будет выполнять операцию ИЛИ (И) над сигналами, действующими на его первом и третьем входах. На основании изложенного сигналы на выходах элементов 1, 1() и j-м выходе предлагаемого устройства будут определяться выражениями
10
1
20
2
где z=f, z=f. В представленной ниже таблице приведены значения реализуемых выражениями (1), (2) функций на всех возможных наборах значений их аргументов.
z<sub>1(j-1)</sub>
z<sub>2(j-1)</sub>
x<sub>n-j</sub>
у<sub>n-j</sub>
f<sub>3</sub>=0, f<sub>4</sub>=1
f<sub>3</sub>=1, f<sub>4</sub>=0
z<sub>lj</sub>
z<sub>2j</sub>
z<sub>1j</sub>
z<sub>2j</sub>
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
0
1
0
0
0
1
0
0
0
1
1
0
0
0
0
0
1
0
0
0
1
0
1
0
1
0
1
0
1
0
1
0
1
1
0
0
1
0
1
0
1
1
1
0
1
0
1
1
0
0
0
1
0
1
0
1
0
0
1
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
1
1
0
1
0
1
1
0
0
1
1
1
1
1
1
0
1
0
1
1
1
1
1
1
0
1
0
1
1
1
1
1
1
1
1
1
1
3
4
Анализ данных, приведенных в таблице, позволяет заключить, что при f=0, f=1:
1j
2j
1(j-1)
2(j-1)
1(j-1)
2(j-1)
n-j
n-j
1(j-1)
2(j-1)
n-j
n-j
1) z=0 (z=0), когда z=0 (z=0) или z=z=1 и x<y (z=z=1 и y<x);
1j
2j
1(j-1)
2(j-1)
2(j-1)
1(j-1)
1(j-1)
2(j-1)
n-j
n-j
1(j-1)
2(j-1)
n-j
n-j
2) z=1 (z=1), когда z=1 и z=0 (z=1 и z=0) или z=z=1 и x≥y (z=z=1 и y≥x);
3
4
а также, что при f=1, f=0:
1j
2j
1(j-1)
2(j-1)
1(j-1)
2(j-1)
n-j
n-j
1(j-1)
2(j-1)
n-j
n-j
1) z=1 (z=1), когда z=1 (z=1) или z=z=0 и x>y (z=z=0 и y>x);
1j
2j
1(j-1)
2(j-1)
2(j-1)
1(j-1)
1(j-1)
2(j-1)
n-j
n-j
1(j-1)
2(j-1)
n-j
n-j
1
2
4
3
2) z=0 (z=0), когда z=0 и z=1 (z=0 и z=1) или z=z=0 и x≤y (z=z=0 и y≤x). Таким образом, при f=f=f=1, f=0 на первом и r-м
() выходах предлагаемого устройства с учетом (3) соответственно получим
и
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
1n
2n
n-1
0
n-1
0
n-1
0
n-1
0
n-1
0
Здесь и далее x…xи y…y - фрагменты n-разрядных двоичных чисел x…xи y…y. Согласно (4), (5) предлагаемое устройство реализует операцию w…w=mах(x…x, y…y) селекции большего из чисел x…xи y…y. При этом z=1 (z=1) когда x…x=mах(x…x, y…y) (y…y=mах(x…x,
n-1
0
3
4
1
2
y…y), то есть предлагаемое устройство одновременно с селекцией выполняет идентификацию селектируемого числа. Если f=0, f=1 и f≠f, то согласно (3) и данным таблицы предлагаемое устройство воспроизводит операцию
1
2
n-1
0
0
n-1
n-1
0
1
2
4
3
селекции числа, назначенного сигналами f, f (операцию мультиплексирования). Отметим, что w…w - n-разрядное двоичное число, задаваемое двоичными сигналами w, …, w∈{0,1} (wи w определяют значения старшего и младшего разрядов соответственно). При f=f=f=0, f=1 с учетом (3) имеем
n-1
0
n-1
Согласно (6), (7) предлагаемое устройство реализует операцию w…w=min(x…
0
n-1
0
n-1
0
n-1
0
1n
2n
n-1
0
n-1
0
n-1
0
n-1
0
n-1
0,
n-1
0
3
4
x, y…y) селекции меньшего из чисел x…x, y…y. При этом выполняется идентификация селектируемого числа, поскольку z=0 (z=0), когда x…x=mах(x…x, y…y) (y…y=mах(x…x y…y)). Если f=1, f=0 и
1
2
f≠f, то согласно (3) и данным таблицы предлагаемое устройство воспроизводит следующую операцию мультиплексирования:
Вышеизложенные сведения позволяют сделать вывод, что предлагаемое устройство обладает более широкими по сравнению с прототипом функциональными возможностями, так как обеспечивает селекцию и идентификацию меньшего, либо селекцию и идентификацию большего, либо селекцию произвольно назначенного из двух n-разрядных двоичных чисел, задаваемых двоичными сигналами.