Устройство сравнения двоичных чисел

Изобретение относится к устройствам для сравнения n-разрядных двоичных чисел А, В, задаваемых двоичными сигналами, и может быть использовано в цифровых компараторах, ассоциативных процессорах и машинах баз данных. Технический результат заключается в расширении функциональных возможностей устройства. Устройство содержит 2×n-2 элементов НЕ (1₁, …, 1_n+n-2) и 2×n-2 мажоритарных элементов (2₁, …, 2_n+n-2). За счет указанных элементов и новой схемы их соединения обеспечивается распознавание отношений А>В, А<В и четности, нечетности чисел А, В при А=В. 1 ил

 

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

Известны устройства сравнения двоичных чисел (патент РФ 2298220, кл. G06F 7/02, 2007 г.; патент РФ 2353966, кл. G06F 7/02, 2009 г.; патент РФ 2363035, кл. G06F 7/02, 2009 г.), выполняющие распознавание отношений X>Y, X=Y, X<Y, где X, Y - n-разрядные двоичные числа, задаваемые двоичными сигналами.

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

Наиболее близким устройством того же назначения к заявленному изобретению по совокупности признаков является принятое за прототип устройство сравнения двоичных чисел (патент РФ 2329530, кл. G06F 7/02, 2008 г.), которое содержит n элементов НЕ, n мажоритарных элементов и выполняет распознавание отношений А≥В, А<В, где А, В - n-разрядные двоичные числа, задаваемые двоичными сигналами.

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

Техническим результатом изобретения является расширение функциональных возможностей за счет обеспечения распознавания отношений А>В, А<В, где А, В - n-разрядные двоичные числа, задаваемые двоичными сигналами, и четности, нечетности чисел А, В при А=В.

Указанный технический результат при осуществлении изобретения достигается тем, что в устройстве сравнения двоичных чисел, содержащем n элементов НЕ и n мажоритарных элементов, третьи входы j-го (n-1)-го и выход j-го мажоритарных элементов соединены соответственно с выходами j-го, (n-1)-го элементов НЕ и вторым входом (j+1)-го мажоритарного элемента, особенность заключается в том, что в него дополнительно введены n-2 элементов НЕ и n-2 мажоритарных элементов, первые входы (n-1+j)-го, (n+n-2)-го и выход (n-1+j)-го мажоритарных элементов соединены соответственно с выходами (n-1+j)-го, (n+n-2)-го элементов НЕ и вторым входом (n+j)-го мажоритарного элемента, входы i-го и (n-1+i)-го элементов НЕ подключены соответственно к вторым входам (n-1+i)-го и i-го мажоритарных элементов, а первый вход i-го, третий вход (n-1+i)-го мажоритарных элементов и выходы (n-1)-го, (n+n-2)-го мажоритарных элементов являются соответственно (n-i)-ым, (n+n-i)-ым входами и первым, вторым выходами устройства сравнения двоичных чисел, n-й и (n+n)-й входы которого соединены соответственно с входами n-го и первого элементов НЕ.

На чертеже представлена схема предлагаемого устройства сравнения двоичных чисел.

Устройство сравнения двоичных чисел содержит элементы НЕ 1₁, …, 1_n+n-2 и мажоритарные элементы 2₁, …, 2_n+n-2, причем третьи входы элементов 2_j 2_n-1 и выход элемента 2_j соединены соответственно с выходами элементов 1_j, 1_n-1 и вторым входом элемента 2_j+1, первые входы элементов 2_n-1+j, 2_n+n-2 и выход элемента 2_n-1+j соединены соответственно с выходами элементов 1_n-1+j, 1_n+n-2 и вторым входом элемента 2_n+j, входы элементов 1_i и 1_n-1+i подключены соответственно к вторым входам элементов 2_n-1+i и 2_i, а первый вход элемента 2_i, третий вход элемента 2_n-1+i и выходы элементов 2_n-1, 2_n+n-2 являются соответственно (n-i)-ым, (n+n-i)-ым входами и первым, вторым выходами устройства сравнения двоичных чисел, n-й и (n+n)-й входы которого соединены соответственно с входами элементов 1_n и 1₁.

Работа предлагаемого устройства сравнения двоичных чисел осуществляется следующим образом. На его первый, …, n-й и (n+1)-й, …, (n+n)-й входы подаются соответственно произвольные двоичные сигналы а₀, …, a_n-1∈{0,1} и b₀, …, b_n-1∈{0,1}, которые задают подлежащие сравнению n-разрядные двоичные числа А=a_n-1…а₀ и B=b_n-1…b₀ (a_n-1, b_n-1 задают значения старших, a а₀, b₀ - младших разрядов). Тогда сигналы на выходах элементов 2_i 2_n-1+i будут определяться выражениями

где # есть символы операций НЕ, Maj; z₀=a_n-1; y₀=b_n-1. В представленной ниже таблице приведены значения реализуемых выражениями (1) функций на всех возможных наборах значений их аргументов.

Анализ данных, приведенных в таблице, позволяет заключить, что: 1) если z_i-1=y_i-1 и a_n-1-i=b_n-1-i=0 или z_i-1=y_i-1 и a_n-1-i=b_n-1-i=1, то z_i=y_i=0 или z_i=y_i=1; 2) если z_i-1=y_i-1 и a_n-1-i>b_n-1-i или z_i-1=y_i-1 и a_n-1-i<b_n-1-i, то z_i=1, y_i=0 или z_i=0, y_i=1; 3) если z_i-1=1, y_i-1=0, то z_i=1, y_i=0; 4) если z_i-1=0, y_i-1=1, то z_i=0, y_i=1. Таким образом, когда А>В либо А<В соответственно получим z_n-1=1, y_n-1=0 либо z_n-1=0, y_n-1=1, когда А=В и А, В четные либо нечетные соответственно имеем z_n-1=y_n-1=0 либо z_n-1=y_n-1=1.

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

Устройство сравнения двоичных чисел, содержащее n элементов НЕ и n мажоритарных элементов, причем третьи входы j-го (n-1)-го и выход j-го мажоритарных элементов соединены соответственно с выходами j-го, (n-1)-го элементов НЕ и вторым входом (j+1)-го мажоритарного элемента, отличающееся тем, что в него дополнительно введены n-2 элементов НЕ и n-2 мажоритарных элементов, первые входы (n-1+j)-го, (n+n-2)-го и выход (n-1+j)-го мажоритарных элементов соединены соответственно с выходами (n-1+j)-го, (n+n-2)-го элементов НЕ и вторым входом (n+j)-го мажоритарного элемента, входы i-го и (n-1+i)-го элементов НЕ подключены соответственно к вторым входам (n-1+i)-го и i-го мажоритарных элементов, а первый вход i-го, третий вход (n-1+i)-го мажоритарных элементов и выходы (n-1)-го, (n+n-2)-го мажоритарных элементов являются соответственно (n-i)-ым, (n+n-i)-ым входами и первым, вторым выходами устройства сравнения двоичных чисел, n-й и (n+n)-й входы которого соединены соответственно с входами n-го и первого элементов НЕ.