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

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