Патент на изобретение №2363035

(54) УСТРОЙСТВО СРАВНЕНИЯ ДВОИЧНЫХ ЧИСЕЛ

(57) Реферат:

Изобретение относится к вычислительной технике и может быть использовано в цифровых компараторах, ассоциативных процессорах и машинах баз данных. Техническим результатом изобретения является повышение быстродействия устройства сравнения двоичных чисел. Устройство сравнения двоичных чисел предназначено для идентификации признаков x_n-1x₀>y_n-1y₀, x_n-1x₀=y_n-1y₀,

x_n-1x₀n-1y₀, где x_n-1х₀, y_n-1y₀ n-разрядные двоичные числа, задаваемые двоичными сигналами x₀,,x_n-1, y₀,,y_n-1{0,1}. Устройство содержит 4(n-1)+2 импликаторов (1₁₁, I₂₁, 1₁₂, , 1_4n), 2(n-1) конъюнкторов (2₁₂,,2_2n). За счет указанных логических элементов и новой схемы их соединения уменьшено максимальное время задержки распространения сигнала. 1 ил., 1 табл.

Изобретение относится к вычислительной технике и может быть использовано для построения средств автоматики, функциональных узлов систем управления и др.

Известны устройства сравнения двоичных чисел (см., например, нижний рисунок в табл.3.5 на стр.103 в книге Справочник по цифровой вычислительной технике. Малиновский Б.Н., Александров В.Я., Боюн В.П. и др./ Под ред. Б.Н.Малиновского. Киев: Техника, 1974 г.), выполняющие идентификацию признака х₁>х₂, где х₁,х₂{0,1} – одноразрядные двоичные числа, задаваемые двоичными сигналами.

К причине, препятствующей достижению указанного ниже технического результата при использовании известных устройств сравнения двоичных чисел, относятся ограниченные функциональные возможности, обусловленные тем, что не допускается сравнение n-разрядных двоичных чисел, задаваемых двоичными сигналами.

Наиболее близким устройством того же назначения к заявленному изобретению по совокупности признаков является принятое за прототип устройство сравнения двоичных чисел (патент РФ 2298220, кл. G06F 7/02, 2007 г.), содержащее логические элементы, среди которых 2n импликаторов и 2(n-1) конъюнкторов, и выполняющее идентификацию признаков x_n-1x₀>y_n-1y₀, x_n-1x₀=y_n-1y₀, x_n-1x₀n-1y₀,

где x_n-1x₀, у_n-1y₀ – n-разрядные двоичные числа, задаваемые двоичными сигналами х₀,, х_n-1, y₀,, у_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 импликаторов 1₁₁, I₂₁, 1₁₂,,1_4n и 2(n-1) конъюнкторов 2₁₂,,2_2n, причем все импликаторы и конъюнкторы сгруппированы в n групп так, что j-я группа содержит импликаторы 1_1j, 1_2j, а k-я группа дополнительно содержит импликаторы 1_3k 1_4k и конъюнкторы 2_1k, 2_2k, неинвертирующий и инвертирующий входы импликатора 1₁₁ соединены соответственно с инвертирующим и неинвертирующим входами импликатора 1₂₁, первым и (n+1)-м входами устройства сравнения двоичных чисел, выход импликатора 1_ik подключенного неинвертирующим входом к инвертирующему входу импликатора 1_(з-i)k, и выход импликатора 1_(2+i)k, подключенного инвертирующим входом к первому входу конъюнктора 2_(3-i)k соединены соответственно с неинвертирующим входом импликатора 1_(2+i)k и вторым входом конъюнктора 2_ik, выход конъюнктора 2_ir подключен к первому входу конъюнктора 2_i(r+1), первый вход конъюнктора 2_i2 соединен с выходом импликатора 1_i1, а выход конъюнктора 2_in является i-м выходом устройства сравнения двоичных чисел, k-и и (n+k)-й входы которого образованы соответственно неинвертирующими входами импликаторов 1_1k и 1_2k.

Работа предлагаемого устройства сравнения двоичных чисел осуществляется следующим образом.

На его первый,, n-й и (n+1)-й, , (2n)-й входы подаются соответственно произвольные двоичные сигналы x_n-1,, x₀{0,1} и y_n-1,, y₀{0,1}, которые задают подлежащие сравнению n-разрядные двоичные числа x_n-1x₀ и y_n-1y₀ (x_n-1, y_n-1 и x₀, y₀ определяют значения старших и младших разрядов соответственно). Тогда сигналы на выходах конъюнкторов 2_1k, 2_2k будут определяться выражениями

где

В представленной ниже таблице приведены значения реализуемых выражениями (1) функций на всех возможных наборах значений их аргументов. Анализ данных, приведенных в таблице, позволяет заключить, что z_1k=0 {z_2k=0), когда z_1(k-1)=0 (z_2(k-1)=0) или z_1(k-1)=z_2(k-1)=1 и x_n-kn-k (z_1(k-1)=z_2(k-1)=1 и y_n-kn-k), и что z_1k=1(z_2k=1), когда z_1(k-1)=1 и z_2(k-1)=0 (z_2(k-1)=1 и z_1(k-1)=0) или z_1(k-1)=z_2(k-1)=1 и x_n-ky_n-k (z_1(k-1)=z_2(k-1)=1 и y_n-kx_n-k).

Дополнительно отметим, что z₁₁=0 (z₂₁=0), когда x_n-1n-1 (y_n-1n-1), и что z₁₁=1(z₂₁=1), когда x_n-1y_n-1(y_n-1x_n-1). Таким образом, если x_n-1x₀>y_n-1y_0, либо x_n-1x₀=y_n-1y₀, либо х_n-1х₀n-1y₀, то z_1n=1, z_2n=0, либо z_1n=z_2n=1, либо z_1n=0, z_2n=1 соответственно.

Вышеизложенные сведения позволяют сделать вывод, что предлагаемое устройство сравнения двоичных чисел выполняет идентификацию признаков x_n-1x₀>у_n-1y₀, x_n-1x₀=у_n-1y₀, х_n-1х₀<у_n-1y₀, где x_n-1x₀, y_n-1y₀ – n-разрядные двоичные числа, задаваемые двоичными сигналами x₀,,x_n-1, y₀,,y_n-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-й группы.

РИСУНКИ