Устройство селекции двоичных чисел
Владельцы патента RU 2363038:
Государственное образовательное учреждение высшего профессионального образования "Ульяновский государственный технический университет" (RU)
Изобретение относится к вычислительной технике и может быть использовано в системах цифровой вычислительной техники как средство предварительной обработки информации. Техническим результатом является расширение функциональных возможностей устройства. Устройство содержит 7n мажоритарных элементов, имеющих по три входа, и 2n элементов НЕ. 1 ил., 1 табл.
Изобретение относится к вычислительной технике и может быть использовано для построения средств автоматики, функциональных узлов систем управления и др.
Известны устройства селекции двоичных чисел (см., например, патент РФ 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-й группы.
На чертеже представлена схема предлагаемого устройства селекции двоичных чисел.
Устройство селекции двоичных чисел содержит мажоритарные элементы 111, …, 17n, имеющие по три входа, и элементы НЕ 211, …, 22n, причем все элементы сгруппированы в n групп так, что j-я (
) группа содержит элементы 11j, …, 17j,
21j, 22j, выход элемента 1ij (
), подключенного третьим входом к первому входу элемента 1(i+2)j, выход элемента 1(i+2)j, подключенного третьим входом к выходу элемента 2ij, и вход элемента 2ij соединены соответственно с первым, третьим входами элемента 1(i+4)j и выходом элемента 1(3-i)j, а первый, третий и второй входы элемента
17j соединены соответственно с первыми входами элементов 15j, 16j и объединенными вторым входом элемента 1(i+4)j, четвертым настроечным входом устройства селекции двоичных чисел, подключенного третьим настроечным входом к объединенным вторым входам элементов 11j, …, 14j, выход элемента 1(i+4)k (
) соединен с третьим входом элемента 1i(k+1), а третий вход элемента 1i1 подключен к i-му настроечному входу устройства селекции двоичных чисел, j-й, (n+j)-й входы и j-й выход которого соединены соответственно с первыми входами элементов 11j, 12j и выходом элемента 17j.
Работа предлагаемого устройства селекции двоичных чисел осуществляется следующим образом. На его первый, …, четвертый настроечные входы подаются соответственно двоичные сигналы f1, …, f4∈{0,1}. На его первый, …, n-й и (n+1)-й, …, (2n)-й входы подаются соответственно двоичные сигналы xn-1, …, x0∈{0,1} и yn-1, …, y0∈{0,1}, которые задают подлежащие обработке n-разрядные двоичные числа xn-1…x0 и yn-1…y0 (xn-1, yn-1 и x0, y0 определяют значения старших и младших pазрядов соответственно). Сигнал на выходе мажоритарного элемента равен 1 (0) только тогда, когда на двух или на всех входах этого элемента действуют сигналы, равные 1 (0). Следовательно, если на втором входе мажоритарного элемента присутствует 1 (0), то этот элемент будет выполнять операцию ИЛИ (И) над сигналами, действующими на его первом и третьем входах. На основании изложенного сигналы на выходах элементов 15j, 16j (
) и j-м выходе предлагаемого устройства будут определяться выражениями
где z10=f1, z20=f2. В представленной ниже таблице приведены значения реализуемых выражениями (1), (2) функций на всех возможных наборах значений их аргументов.
| z1(j-1) | z2(j-1) | xn-j | уn-j | f3=0, f4=1 | f3=1, f4=0 | ||
| zlj | z2j | z1j | z2j | ||||
| 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 |
Анализ данных, приведенных в таблице, позволяет заключить, что при f3=0, f4=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);
а также, что при f3=1, f4=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). Таким образом, при f1=f2=f4=1, f3=0 на первом и r-м
(
) выходах предлагаемого устройства с учетом (3) соответственно получим
и
Здесь и далее xn-1…xn-r+1 и yn-1…yn-r+1 - фрагменты n-разрядных двоичных чисел xn-1…x0 и yn-1…y0. Согласно (4), (5) предлагаемое устройство реализует операцию wn-1…w0=mах(xn-1…x0, yn-1…y0) селекции большего из чисел xn-1…x0 и yn-1…y0. При этом z1n=1 (z2n=1) когда xn-1…x0=mах(xn-1…x0, yn-1…y0) (yn-1…y0=mах(xn-1…x0,
yn-1…y0), то есть предлагаемое устройство одновременно с селекцией выполняет идентификацию селектируемого числа. Если f3=0, f4=1 и f1≠f2, то согласно (3) и данным таблицы предлагаемое устройство воспроизводит операцию
селекции числа, назначенного сигналами f1, f2 (операцию мультиплексирования). Отметим, что wn-1…w0 - n-разрядное двоичное число, задаваемое двоичными сигналами w0, …, wn-1∈{0,1} (wn-1 и w0 определяют значения старшего и младшего разрядов соответственно). При f1=f2=f4=0, f3=1 с учетом (3) имеем
Согласно (6), (7) предлагаемое устройство реализует операцию wn-1…w0=min(xn-1…
x0, yn-1…y0) селекции меньшего из чисел xn-1…x0, yn-1…y0. При этом выполняется идентификация селектируемого числа, поскольку z1n=0 (z2n=0), когда xn-1…x0=mах(xn-1…x0, yn-1…y0) (yn-1…y0=mах(xn-1…x0, yn-1…y0)). Если f3=1, f4=0 и
f1≠f2, то согласно (3) и данным таблицы предлагаемое устройство воспроизводит следующую операцию мультиплексирования:
Вышеизложенные сведения позволяют сделать вывод, что предлагаемое устройство обладает более широкими по сравнению с прототипом функциональными возможностями, так как обеспечивает селекцию и идентификацию меньшего, либо селекцию и идентификацию большего, либо селекцию произвольно назначенного из двух 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-й группы.
