Устройство селекции двоичных чисел
Владельцы патента RU 2703352:
федеральное государственное бюджетное образовательное учреждение высшего образования "Ульяновский государственный технический университет" (RU)
Изобретение предназначено для выполнения селекции и идентификации меньшего, либо селекции и идентификации большего, либо селекции произвольно назначенного из двух n-разрядных двоичных чисел, задаваемых двоичными сигналами, и может быть использовано в системах цифровой вычислительной техники как средство предварительной обработки информации. Техническим результатом является уменьшение аппаратурных затрат. Устройство содержит n групп элементов, каждая из которых содержит пять мажоритарных элементов и элемент НЕ. 1 ил., 1 табл.
Изобретение относится к вычислительной технике и может быть использовано для построения средств автоматики, функциональных узлов систем управления и др.
Известны устройства селекции двоичных чисел (см., например, патент РФ 2300135, кл. G06F 7/02, 2007 г.), выполняющие селекцию большего из двух n-разрядных двоичных чисел, задаваемых двоичными сигналами.
К причине, препятствующей достижению указанного ниже технического результата при использовании известных устройств селекции двоичных чисел, относятся ограниченные функциональные возможности, обусловленные тем, что не выполняется идентификация большего, либо селекция и идентификация меньшего, либо селекция произвольно назначенного из двух n-разрядных двоичных чисел, задаваемых двоичными сигналами.
Наиболее близким устройством того же назначения к заявленному изобретению по совокупности признаков является принятое за прототип устройство селекции двоичных чисел (патент РФ 2363038, кл. G06F 7/02, 2009 г.), которое содержит мажоритарные элементы, элементы НЕ и выполняет селекцию и идентификацию меньшего, либо селекцию и идентификацию большего, либо селекцию произвольно назначенного из двух n-разрядных двоичных чисел, задаваемых двоичными сигналами.
К причине, препятствующей достижению указанного ниже технического результата при использовании прототипа, относятся большие аппаратурные затраты, обусловленные тем, что прототип содержит 7×n мажоритарных элементов и 2×n элементов НЕ.
Техническим результатом изобретения является уменьшение аппаратурных затрат при сохранении функциональных возможностей прототипа.
Указанный технический результат при осуществлении изобретения достигается тем, что в устройстве селекции двоичных чисел, содержащем n групп элементов, каждая из которых содержит пять мажоритарных элементов и элемент НЕ, причем в j-й группе первый вход пятого и третий вход i-го
мажоритарных элементов соединены соответственно с выходом первого и первым входом (i+2)-го мажоритарных элементов, а третий вход i-го мажоритарного элемента первой группы и второй вход i-го мажоритарного элемента j-й группы подключены соответственно к i-му и третьему настроечным входам устройства селекции двоичных чисел, j-й и (n+j)-й входы которого соединены соответственно с первыми входами первого и второго мажоритарных элементов j-й группы, особенность заключается в том, что в j-й группе выход второго и третий вход (i+2)-го, выход пятого и второй вход (i+2)-го мажоритарных элементов соединены соответственно с вторым входом пятого и выходом i-го мажоритарных элементов, входом и выходом элемента НЕ, выход (i+2)-го мажоритарного элемента предыдущей группы подключен к третьему входу i-го мажоритарного элемента последующей группы, а третий вход и выход пятого мажоритарного элемента j-й группы соединены соответственно с четвертым настроечным входом и j-ым выходом устройства селекции двоичных чисел.
На фиг. представлена схема предлагаемого устройства селекции двоичных чисел.
Устройство селекции двоичных чисел содержит мажоритарные элементы 111, …, 15n и элементы НЕ 21, …, 2n, которые сгруппированы в n групп так, что j-я группа содержит элементы 11j, …, 15j, 2j, причем третий вход элемента 1ij
подключенного выходом к i-му входу элемента 15j, третьему входу элемента 1(i+2)j, выход и вход элемента 2j соединены соответственно с первым, вторым входами элемента 1(i+2)j и выходом элемента 15j, выход элемента 1(i+2)k
подключен к третьему входу элемента 1i(k+1), а третий вход элемента 1i1, второй вход элемента 1ij, третий вход и выход элемента 15j соединены соответственно с i-ым, третьим, четвертым настроечными входами и j-ым выходом устройства селекции двоичных чисел, j-й и (n+j)-й входы которого подключены соответственно к первым входам элементов 11j и 12j.
Работа предлагаемого устройства селекции двоичных чисел осуществляется следующим образом. На его первом, …, четвертом настроечных входах фиксируются соответственно необходимые двоичные сигналы ƒ1, …, ƒ4 ∈ {0,1}. На его первый, …, n-й и (n+1)-й, …, (n+n)-й входы подаются соответственно двоичные сигналы xn-1, …, x0 ∈ {0,1} и yn-1, …, y0 ∈ {0,1}, которые задают подлежащие обработке n-разрядные двоичные числа xn-1…х0 и yn-1…y0 (xn-1, yn-1 и х0, y0 определяют значения старших и младших разрядов соответственно). Сигнал на выходе мажоритарного элемента равен 1 (0) только тогда, когда на двух или на трех входах этого элемента действуют сигналы, равные 1 (0). Следовательно, если на одном из трех входов мажоритарного элемента фиксируется 1 (0), то этот элемент будет выполнять операцию ИЛИ(И) над сигналами, действующими на двух других его входах. На основании изложенного сигналы на выходах элементов 13j, 14j и j-ом выходе предлагаемого устройства будут определяться выражениями
и
где ∨, ⋅, # есть символы операций ИЛИ, И, НЕ, Maj; z10=ƒ1; z20=ƒ2. В представленной ниже таблице приведены значения реализуемых выражениями (1), (2) функций на всех возможных наборах значений их аргументов.
Анализ данных, приведенных в таблице, позволяет заключить, что при ƒ3=0, ƒ4=1:1) z1j=0 (z2j=0) когда z1(j-1)=0 (z2(j-1)=0) или z1(j-1)=z2(j-1)=1 и xn-j<yn-j (z1(j-1)=z2(j-1)=1 и yn-j<xn-j); 2) z1j=1 (z2j=1) когда z1(j-1)=1 и z2(j-1)=0 (z2(j-1)=1 и z1(j-1)=0) или z1(j-1)=z2(j-1)=1 и xn-j≥yn-j (z1(j-1)=z2(j-1)=1 и yn-j≥xn-j); a также, что при ƒ3=1, ƒ4=0: 1) z1j=1 (z2j=1) когда z1(j-1)=1 (z2(j-1)=1) или z1(j-1)=z2(j-1)=0 и xn-j>yn-j (z1(j-1)=z2(j-1)=0 и yn-j>xn-j); 2) z1j=0 (z2j=0) когда z1(j-1)=0 и z2(j-1)=1 (z2(j-1)=0 и z1(j-1)=1) или z1(j-1)=z2(j-1)=0 и xn-j≤yn-j (z1(j-1)=z2(j-1)=0 и yn-j≤xn-j). Таким образом, при ƒ1=ƒ2=ƒ4=1, ƒ3=0 на первом и r-ом выходах предлагаемого устройства с учетом (3) соответственно получим
и
Здесь и далее xn-1…xn-r+1 и yn-1…yn-r+1 - фрагменты n-разрядных двоичных чисел xn-1…х0 и yn-1…y0. Согласно (4), (5) предлагаемое устройство реализует операцию wn-1…w0=max(xn-1…х0, yn-1…у0) селекции большего из чисел xn-1…х0, yn-1…у0. При этом z1n=1 (z2n=1) когда xn-1…х0=max(xn-1…х0, yn-1…у0) (yn-1…у0=max(xn-1…х0, yn-1…у0)), то есть предлагаемое устройство одновременно с селекцией выполняет идентификацию селектируемого числа. Если ƒ3=0, ƒ4=1 и ƒ1≠ƒ2, то согласно (3) и данных таблицы предлагаемое устройство воспроизводит операцию
селекции числа, назначенного сигналами ƒ1, ƒ2 (операцию мультиплексирования). Отметим, что wn-1…w0 - n-разрядное двоичное число, задаваемое двоичными сигналами w0, …, wn-1 ∈ {0,1} (wn-1 и w0 определяют значения старшего и младшего разрядов соответственно). При ƒ1=ƒ2=ƒ4=0, ƒ3=1 с учетом (3) имеем
Согласно (6), (7) предлагаемое устройство реализует операцию wn-1…w0=min(xn-1…х0, yn-1…у0) селекции меньшего из чисел xn-1…х0, yn-1…y0. При этом выполняется идентификация селектируемого числа, поскольку z1n=0 (z2n=0) когда xn-1…х0=min(xn-1…х0, yn-1…у0) (yn-1…у0=min(xn-1…x0, yn-1…y0)). Если ƒ3=1, ƒ4=0 и ƒ1≠ƒ2, то согласно (3) и данных таблицы предлагаемое устройство воспроизводит следующую операцию мультиплексирования:
Отметим, что указанное устройство содержит 5×n мажоритарных элементов и n элементов НЕ.
Вышеизложенные сведения позволяют сделать вывод, что предлагаемое устройство выполняет селекцию и идентификацию меньшего, либо селекцию и идентификацию большего, либо селекцию произвольно назначенного из двух n-разрядных двоичных чисел, задаваемых двоичными сигналами, и обладает меньшими по сравнению с прототипом аппаратурными затратами.
Устройство селекции двоичных чисел, содержащее n групп элементов, каждая из которых содержит пять мажоритарных элементов и элемент НЕ, причем в j-й группе первый вход пятого и третий вход i-го
мажоритарных элементов соединены соответственно с выходом первого и первым входом (i+2)-го мажоритарных элементов, а третий вход i-го мажоритарного элемента первой группы и второй вход i-го мажоритарного элемента j-й группы подключены соответственно к i-му и третьему настроечным входам устройства селекции двоичных чисел, j-й и (n+j)-й, входы которого соединены соответственно с первыми входами первого и второго мажоритарных элементов j-й группы, отличающееся тем, что в j-й группе выход второго и третий вход (i+2)-го, выход пятого и второй вход (i+2)-го мажоритарных элементов соединены соответственно с вторым входом пятого и выходом i-го мажоритарных элементов, входом и выходом элемента НЕ, выход (i+2)-го мажоритарного элемента предыдущей группы подключен к третьему входу i-го мажоритарного элемента последующей группы, а третий вход и выход пятого мажоритарного элемента j-й группы соединены соответственно с четвертым настроечным входом и j-м выходом устройства селекции двоичных чисел.