Устройство селекции большего из двух двоичных чисел
Владельцы патента RU 2363034:
Государственное образовательное учреждение высшего профессионального образования "Ульяновский государственный технический университет" (RU)
Изобретение относится к вычислительной технике и может быть использовано в системах цифровой вычислительной техники как средство предварительной обработки информации. Техническим результатом изобретения является упрощение устройства за счет уменьшения числа типов используемых логических элементов. Устройство селекции большего из двух двоичных чисел предназначено для обработки n-разрядных двоичных чисел, задаваемых двоичными сигналами. Устройство содержит 4(n-1) элементов «Запрет» (111, 121, 112, … (14(n-1), 11n, 12n) и 3(n-2)+2 элементов «ИЛИ» (212, …, 23(n-1), 211, 21n). За счет указанных элементов и связей между ними повышена однородность состава. В результате достигнуто упрощение устройства. 1 ил., 1 табл.
Изобретение относится к вычислительной технике и может быть использовано для построения средств автоматики, функциональных узлов систем управления и др.
Известны устройства селекции большего из двух двоичных чисел (см., например, рис.4 на стр.24 в книге Цифровые и аналоговые интегральные микросхемы: Справочник / С.В.Якубовский, Л.И.Ниссельсон, В.И.Кулешова и др. Под ред. С.В.Якубовского. М.: Радио и связь, 1989 г.), выполняющие операцию mах(x1,x2), где x1,x2∈{0,1} - одноразрядные двоичные числа, задаваемые двоичными сигналами.
К причине, препятствующей достижению указанного ниже технического результата при использовании известных устройств селекции большего из двух двоичных чисел, относятся ограниченные функциональные возможности, обусловленные тем, что не допускается обработка n-разрядных двоичных чисел, задаваемых двоичными сигналами.
Наиболее близким устройством того же назначения к заявленному изобретению по совокупности признаков является, принятое за прототип, устройство селекции большего из двух двоичных чисел (патент РФ 2300135, кл. G06F 7/02, 2007 г.), который содержит элемент «ИЛИ» и выполняет операцию max(xn-1…x0, yn-1…y0),
где xn-1…x0, yn-1…y0 - n-разрядные двоичные числа, задаваемые двоичными сигналами x0,…, xn-1,y0,…,yn-1∈{0,1}.
К причине, препятствующей достижению указанного ниже технического результата при использовании прототипа, относится сложность устройства, обусловленная тем, что прототип состоит из логических элементов четырех типов (импликаторов, элементов «И», элементов «И-НЕ», элемента «ИЛИ»).
Техническим результатом изобретения является упрощение устройства за счет уменьшения числа типов используемых логических элементов при сохранении функциональных возможностей прототипа.
Указанный технический результат при осуществлении изобретения достигается тем, что в устройстве селекции большего из двух двоичных чисел, содержащем элемент «ИЛИ», особенность заключается в том, что в него дополнительно введены 4(n-1) элементов «Запрет» и 3(n-2)+1 аналогичных упомянутому элементов «ИЛИ», причем все элементы сгруппированы в n групп так, что j-я группа содержит два элемента «Запрет» и элемент «ИЛИ», а m-я 
группа дополнительно содержит два элемента «Запрет» и два элемента «ИЛИ», в r-й (
группе выход i-го 
элемента «Запрет» соединен с i-м входом первого элемента «ИЛИ», в m-й группе выход i-го элемента «Запрет», подключенного инвертирующим входом к первому входу (i+1)-го элемента «ИЛИ», и выход (i+1)-го элемента «ИЛИ», подключенного вторым входом к выходу (3-i)-го элемента «Запрет», соединены соответственно с инвертирующим и неинвертирующим входами (i+2)-го элемента «Запрет», в первой группе инвертирующий и неинвертирующий входы первого элемента «Запрет» подключены соответственно к неинвертирующему и инвертирующему входам второго элемента «Запрет», первому и второму входам первого элемента «ИЛИ», выход i-го элемента «Запрет» первой группы и выход (i+2)-го элемента «Запрет» m-й группы соединены соответственно с инвертирующим входом i-го элемента «Запрет» второй группы и инвертирующим входом i-го элемента «Запрет» (m+1)-й группы, а первый, второй входы первого элемента «ИЛИ» первой группы, неинвертирующие входы первого, второго элементов «Запрет» r-й группы и выход первого элемента «ИЛИ» j-й группы образуют соответственно первый, (n+1)-й, r-й, (n+r)-й входы j-й выход устройства селекции большего из двух двоичных чисел.
На чертеже представлена схема предлагаемого устройства селекции большего из двух двоичных чисел.
Устройство селекции большего из двух двоичных чисел содержит 4(n-1) элементов «Запрет» 111, 121, 112, …, 14(n-1), 11n, 12n (третий снизу рис. в табл.3.5 на стр.103 в книге Справочник по цифровой вычислительной технике. Малиновский Б.Н., Александров В.Я., Боюн В.П. и др./ Под ред. Б.Н.Малиновского. Киев: Техника, 1974 г.), элемент «ИЛИ» 211 и 3(n-2)+1 элементов «ИЛИ» 212, …, 23(n-1), 21n, причем все элементы сгруппированы в n групп так, что j-я 
группа содержит элементы 11j, 12j, 21j, a m-я 
группа дополнительно содержит элементы 13m, 14m, 22m, 23m, выход элемента 
соединен с i-м входом элемента 21r, выход элемента 1im, подключенного инвертирующим входом к первому входу
элемента 2(i+1)m, и выход элемента 2(i+1)m, подключенного вторым входом к выходу элемента 1(3-i)m, соединены соответственно с инвертирующим и неинвертирующим входами элемента 1(i+2)m, инвертирующий и неинвертирующий входы элемента 111 подключены соответственно к неинвертирующему и инвертирующему входам элемента 121 первому и второму входам элемента 211, выход элемента 1i1 и выход элемента 1(i+2)m соединены соответственно с инвертирующим входом элемента 1i2 и инвертирующим входом элемента 1i(m+1), а первый, второй входы элемента 211, неинвертирующие входы элементов 11r, 12r и выход элемента 21j образуют соответственно первый, (n+1)-й, r-й, (n+r)-й входы j-й выход устройства селекции большего из двух двоичных чисел.
Работа предлагаемого устройства селекции большего из двух двоичных чисел осуществляется следующим образом. На его первый, …, n-й и (n+1)-й, …, (2n)-й входы подаются соответственно произвольные двоичные сигналы xn-1…x0∈{0,l) и yn-1,…,y0∈{0,1}, которые задают подлежащие обработке n-разрядные двоичные числа
xn-1…x0 и yn-1…y0 (xn-1, yn-1 и x0 y0 определяют значения старших и младших разрядов соответственно). Тогда сигнал на j-м 
выходе предлагаемого устройства будет определяться выражением
где
В представленной ниже таблице приведены значения реализуемых выражениями (2), (3) функций на всех возможных наборах значений их аргументов. Жирным в таблице выделены значения функций и их аргументов при j = 2.
| z1(j-2) | z2(j-2) | xn-j+1 | yn-j+1 | z1(j-1) | z2(j-1) |
| 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 1 | 1 | 0 |
| 0 | 0 | 1 | 0 | 0 | 1 |
| 0 | 0 | 1 | 1 | 0 | 0 |
| 0 | 1 | 0 | 0 | 0 | 1 |
| 0 | 1 | 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 0 | 0 | 1 |
| 0 | 1 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 0 | 1 | 0 |
| 1 | 0 | 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 | 1 | 0 |
| 1 | 0 | 1 | 1 | 1 | 0 |
| - | - | 0 | 0 | 0 | 0 |
| - | - | 0 | 1 | 1 | 0 |
| - | - | 1 | 0 | 0 | 1 |
| - | - | 1 | 1 | 0 | 0 |
Анализ данных, приведенных в таблице, позволяет заключить, что:
1) если z1(j-2)=z2(j-2)=0 и xn-j+1=yn-j+1, то z1(j-1)=z2(j-1)=0;
2) если z1(j-2)=z2(j-2)=0 и xn-j+1>yn-j+1 (z1(j-2)=z2(j-2)=0 и yn-j+1>xn-j+1), то z1(j-1)=0 и z2(j-1)=1( z1(j-1)=1 и z2(j-1)=0;
3) если z1(j-2)=0 и z2(j-2)=1 (z1(j-2)=1 и z2(j-2)=0), то z1(j-1)=0 и z2(j-1)=1 (z1(j-1)=1 и z2(j-1)=0);
4) если xn-1=yn-1 или xn-1>yn-1 (yn-1>xn-1), то соответственно z11=z21=0 или z11=0 и z21=1 (z11=1 и z21=0).
Таким образом, на первом и r-м 
выходах предлагаемого устройства согласно (1) соответственно получим
и
где xn-1…xn-r+1 и yn-1…yn-r+1 - фрагменты n-разрядных двоичных чисел xn-1…x0 и
yn-1…y0. Следовательно, с учетом (4), (5) имеем wn-1…w0 = max(xn-1…x0, yn-1…y0), где
wn-1…w0 - n-разрядное двоичное число, задаваемое двоичными сигналами w0,…,wn-1 ∈{0,1} (wn-1 и w0 определяют значения старшего и младшего разрядов соответственно).
Вышеизложенные сведения позволяют сделать вывод, что предлагаемое устройство выполняет селекцию большего из двух n-разрядных двоичных чисел, задаваемых двоичными сигналами, и является по сравнению с прототипом более простым, так как состоит из логических элементов только двух типов (элементов «Запрет», элементов «ИЛИ»).
Устройство селекции большего из двух двоичных чисел, содержащее элемент «ИЛИ», отличающееся тем, что в него дополнительно введены 4(n-1) элементов «Запрет» и 3(n-2)+1 аналогичных упомянутому элементов «ИЛИ», причем все элементы сгруппированы в n групп так, что j-я 
группа содержит два элемента «Запрет» и элемент «ИЛИ», а m-я 
группа дополнительно содержит два элемента «Запрет» и два элемента «ИЛИ», в r-й 
группе выход i-го 
элемента «Запрет» соединен с i-м входом первого элемента «ИЛИ», в m-й группе выход i-го элемента «Запрет», подключенного инвертирующим входом к первому входу (i+1)-го элемента «ИЛИ», и выход (i+1)-го элемента «ИЛИ», подключенного вторым входом к выходу (3-i)-го элемента «Запрет», соединены соответственно с инвертирующим и неинвертирующим входами (i+2)-го элемента «Запрет», в первой группе инвертирующий и неинвертирующий входы первого элемента «Запрет» подключены соответственно к неинвертирующему и инвертирующему входам второго элемента «Запрет», первому и второму входам первого элемента «ИЛИ», выход i-го элемента «Запрет» первой группы и выход (i+2)-го элемента «Запрет» m-й группы соединены соответственно с инвертирующим входом i-го элемента «Запрет» второй группы и инвертирующим входом i-го элемента «Запрет» (m+1)-й группы, а первый, второй входы первого элемента «ИЛИ» первой группы, неинвертирующие входы первого, второго элементов «Запрет» r-й группы и выход первого элемента «ИЛИ» j-й группы образуют соответственно первый, (n+1)-й, r-й, (n+r)-й входы и j-й выход устройства селекции большего из двух двоичных чисел.
