Устройство сравнения двоичных чисел
Владельцы патента RU 2363035:
Государственное образовательное учреждение высшего профессионального образования "Ульяновский государственный технический университет" (RU)
Изобретение относится к вычислительной технике и может быть использовано в цифровых компараторах, ассоциативных процессорах и машинах баз данных. Техническим результатом изобретения является повышение быстродействия устройства сравнения двоичных чисел. Устройство сравнения двоичных чисел предназначено для идентификации признаков xn-1…x0>yn-1…y0, xn-1…x0=yn-1…y0,
xn-1…x0<yn-1…y0, где xn-1…х0, yn-1…y0 n-разрядные двоичные числа, задаваемые двоичными сигналами x0,…,xn-1, y0,…,yn-1∈{0,1}. Устройство содержит 4(n-1)+2 импликаторов (111, I21, 112, …, 14n), 2(n-1) конъюнкторов (212,…,22n). За счет указанных логических элементов и новой схемы их соединения уменьшено максимальное время задержки распространения сигнала. 1 ил., 1 табл.
Изобретение относится к вычислительной технике и может быть использовано для построения средств автоматики, функциональных узлов систем управления и др.
Известны устройства сравнения двоичных чисел (см., например, нижний рисунок в табл.3.5 на стр.103 в книге Справочник по цифровой вычислительной технике. Малиновский Б.Н., Александров В.Я., Боюн В.П. и др./ Под ред. Б.Н.Малиновского. Киев: Техника, 1974 г.), выполняющие идентификацию признака х1>х2, где х1,х2∈{0,1} - одноразрядные двоичные числа, задаваемые двоичными сигналами.
К причине, препятствующей достижению указанного ниже технического результата при использовании известных устройств сравнения двоичных чисел, относятся ограниченные функциональные возможности, обусловленные тем, что не допускается сравнение n-разрядных двоичных чисел, задаваемых двоичными сигналами.
Наиболее близким устройством того же назначения к заявленному изобретению по совокупности признаков является принятое за прототип устройство сравнения двоичных чисел (патент РФ 2298220, кл. G06F 7/02, 2007 г.), содержащее логические элементы, среди которых 2n импликаторов и 2(n-1) конъюнкторов, и выполняющее идентификацию признаков xn-1…x0>yn-1…y0, xn-1…x0=yn-1…y0, xn-1…x0<yn-1…y0,
где xn-1…x0, уn-1…y0 - n-разрядные двоичные числа, задаваемые двоичными сигналами х0,…, хn-1, y0,…, уn-1∈{0,1}.
К причине, препятствующей достижению указанного ниже технического результата при использовании прототипа, относится низкое быстродействие, обусловленное тем, что максимальное время задержки распространения сигнала в прототипе определяется выражением τ=(3n-2)τЭ, где τЭ есть длительность задержки, вносимой логическим элементом.
Техническим результатом изобретения является повышение быстродействия при сохранении функциональных возможностей прототипа.
Указанный технический результат при осуществлении изобретения достигается тем, что в устройстве сравнения двоичных чисел, содержащем 2n импликаторов и 2(n-1) конъюнкторов, которые сгруппированы в n групп так, что j-я группа содержит два импликатора, k-я 
группа дополнительно содержит два конъюнктора, а в первой группе неинвертирующий и инвертирующий входы первого импликатора соединены соответственно с инвертирующим и неинвертирующим входами второго импликатора, первым и (n+1)-ым входами устройства сравнения двоичных чисел, особенность заключается в том, что в k-ю группу дополнительно введены два импликатора, причем в k-й группе выход i-го 
импликатора, подключенного неинвертирующим входом к инвертирующему входу (3-i)-го импликатора, и выход (2+i)-го импликатора, подключенного инвертирующим входом к первому входу (3-i)-го конъюнктора, соединены соответственно с неинвертирующим входом (2+i)-го импликатора и вторым входом i-го конъюнктора, выход i-го конъюнктора предыдущей группы подключен к первому входу i-го конъюнктора последующей группы, первый вход i-го конъюнктора второй группы соединен с выходом i-го импликатора первой группы, а выход i-го конъюнктора n-й группы является i-ым выходом устройства сравнения двоичных чисел, k-й и (n+k)-й входы которого образованы соответственно неинвертирующими входами первого и второго импликаторов k-й группы.
На чертеже представлена схема предлагаемого устройства сравнения двоичных чисел.
Устройство сравнения двоичных чисел содержит логические элементы, среди которых 4(n-1)+2 импликаторов 111, I21, 112,…,14n и 2(n-1) конъюнкторов 212,…,22n, причем все импликаторы и конъюнкторы сгруппированы в n групп так, что j-я 
группа содержит импликаторы 11j, 12j, а k-я 
группа дополнительно содержит импликаторы 13k 14k и конъюнкторы 21k, 22k, неинвертирующий и инвертирующий входы импликатора 111 соединены соответственно с инвертирующим и неинвертирующим входами импликатора 121, первым и (n+1)-м входами устройства сравнения двоичных чисел, выход импликатора 1ik 
подключенного неинвертирующим входом к инвертирующему входу импликатора 1(з-i)k, и выход импликатора 1(2+i)k, подключенного инвертирующим входом к первому входу конъюнктора 2(3-i)k соединены соответственно с неинвертирующим входом импликатора 1(2+i)k и вторым входом конъюнктора 2ik, выход конъюнктора 2ir 
подключен к первому входу конъюнктора 2i(r+1), первый вход конъюнктора 2i2 соединен с выходом импликатора 1i1, а выход конъюнктора 2in является i-м выходом устройства сравнения двоичных чисел, k-и и (n+k)-й входы которого образованы соответственно неинвертирующими входами импликаторов 11k и 12k.
Работа предлагаемого устройства сравнения двоичных чисел осуществляется следующим образом.
На его первый,…, 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 определяют значения старших и младших разрядов соответственно). Тогда сигналы на выходах конъюнкторов 21k, 22k 
будут определяться выражениями
где 
В представленной ниже таблице приведены значения реализуемых выражениями (1) функций на всех возможных наборах значений их аргументов. Анализ данных, приведенных в таблице, позволяет заключить, что z1k=0 {z2k=0), когда z1(k-1)=0 (z2(k-1)=0) или z1(k-1)=z2(k-1)=1 и xn-k<yn-k (z1(k-1)=z2(k-1)=1 и yn-k<xn-k), и что z1k=1(z2k=1), когда z1(k-1)=1 и z2(k-1)=0 (z2(k-1)=1 и z1(k-1)=0) или z1(k-1)=z2(k-1)=1 и xn-k≥yn-k (z1(k-1)=z2(k-1)=1 и yn-k≥xn-k).
Дополнительно отметим, что z11=0 (z21=0), когда xn-1<yn-1 (yn-1<xn-1), и что z11=1(z21=1), когда xn-1≥yn-1(yn-1≥xn-1). Таким образом, если xn-1…x0>yn-1…y0, либо xn-1…x0=yn-1…y0, либо хn-1…х0<yn-1…y0, то z1n=1, z2n=0, либо z1n=z2n=1, либо z1n=0, z2n=1 соответственно.
| z1(k-1) | z2(k-1) | xn-k | yn-k | z1k | z2k |
| 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 |
| 1 | 1 | 0 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 | 0 | 1 |
| 1 | 1 | 1 | 0 | 1 | 0 |
| 1 | 1 | 1 | 1 | 1 | 1 |
Вышеизложенные сведения позволяют сделать вывод, что предлагаемое устройство сравнения двоичных чисел выполняет идентификацию признаков xn-1…x0>уn-1…y0, xn-1…x0=уn-1…y0, хn-1…х0<уn-1…y0, где xn-1…x0, yn-1…y0 - n-разрядные двоичные числа, задаваемые двоичными сигналами x0,…,xn-1, y0,…,yn-1∈{0,1}, и обладает более высоким по сравнению с прототипом быстродействием, так как максимальное время задержки распространения сигнала в предлагаемом устройстве определяется выражением τ=(2n-1)τЭ, где τЭ есть длительность задержки, вносимой логическим элементом.
Устройство сравнения двоичных чисел, содержащее 2n импликаторов и 2(n-1) конъюнкторов, которые сгруппированы в n групп так, что j-я (j=1,n) группа содержит два импликатора, k-я 
группа дополнительно содержит два конъюнктора, а в первой группе неинвертирующий и инвертирующий входы первого импликатора соединены соответственно с инвертирующим и неинвертирующим входами второго импликатора, первым и (n+1)-м входами устройства сравнения двоичных чисел, отличающееся тем, что в k-ю группу дополнительно введены два импликатора, причем в k-й группе выход i-го 
импликатора, подключенного неинвертирующим входом к инвертирующему входу (3-i)-го импликатора, и выход (2+i)-го импликатора, подключенного инвертирующим входом к первому входу (3-i)-го конъюнктора, соединены соответственно с неинвертирующим входом (2+i)-го импликатора и вторым входом i-го конъюнктора, выход i-го конъюнктора предыдущей группы подключен к первому входу i-го конъюнктора последующей группы, первый вход i-го конъюнктора второй группы соединен с выходом i-го импликатора первой группы, а выход i-го конъюнктора n-й группы является i-м выходом устройства сравнения двоичных чисел, k-й и (n+k)-й входы которого образованы соответственно неинвертирующими входами первого и второго импликаторов k-й группы.
