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

Изобретение относится к области вычислительной техники и может быть использовано в цифровых компараторах, ассоциативных процессорах и машинах баз данных. Техническим результатом является расширение функциональных возможностей устройства за счет обеспечения распознавания отношений A>B, A=В, A<B. Устройство содержит n-1 элементов И, 2×n элементов ИСКЛЮЧАЮЩЕЕ ИЛИ-НЕ и n мажоритарных элементов. 1 ил.

 

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

Известны устройства сравнения двоичных чисел (см., например, рис. 4.18 на стр. 163 в книге Бибило П.Н. Основы языка HHDL. М.: Солон-Р, 2000 г.), при варьировании размерности выполняющие распознавание отношений A≥B, A<B, где A=a_n-1…a₀, B=b_n-1…b₀ есть n-разрядные двоичные числа, задаваемые двоичными сигналами a₀, …, a_n-1, b₀, …, b_n-1∈(0,1}.

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

Наиболее близким устройством того же назначения к заявленному изобретению по совокупности признаков является принятое за прототип устройство сравнения двоичных чисел (патент РФ 2329530, кл. G06F 7/02, 2008 г.), которое содержит n мажоритарных элементов и выполняет распознавание отношений A≥B, A<B, где A=a_n-1…a₀, B=b_n-1…b₀ есть n-разрядные двоичные числа, задаваемые двоичными сигналами a₀, …, a_n-1, b₀, …, b_n-1 ∈ {0,1}.

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

Техническим результатом изобретения является расширение функциональных возможностей за счет обеспечения распознавания отношений A>B, A=B, A<B, где A=a_n-1…a₀, B=b_n-1…b₀ есть n-разрядные двоичные числа, задаваемые двоичными сигналами a₀, …, a_n-1, b₀, …, b_n-1 ∈ {0,1}.

Указанный технический результат при осуществлении изобретения достигается тем, что в устройстве сравнения двоичных чисел, содержащем я мажоритарных элементов, выход предыдущего мажоритарного элемента подключен к второму входу последующего мажоритарного элемента, а выход n-го мажоритарного элемента является выходом устройства сравнения двоичных чисел, особенность заключается в том, что в него дополнительно введены 2×n элементов ИСКЛЮЧАЮЩЕЕ ИЛИ-ИЕ и n-1 элементов И, второй вход и выход i-го элемента ИСКЛЮЧАЮЩЕЕ ИЛИ-ИЕ соединены соответственно с третьим входом i-го мажоритарного элемента и первым входом (n+i)-го элемента ИСКЛЮЧАЮЩЕЕ ИЛИ-НЕ, первый и второй входы i-го мажоритарного элемента соединены соответственно с выходом и вторым входом (n+i)-го элемента ИСКЛЮЧАЮЩЕЕ ИЛИ-НЕ, второй вход первого мажоритарного элемента и второй вход j-го элемента И соединены соответственно с шиной нулевого потенциала и выходом (j+1)-го элемента ИСКЛЮЧАЮЩЕЕ ИЛИ-НЕ, выход предыдущего элемента И соединен с первым входом последующего элемента И, а первый вход первого и выход (n-1)-го элементов И соединены соответственно с выходом первого элемента ИСКЛЮЧАЮЩЕЕ ИЛИ-НЕ и дополнительным выходом устройства сравнения двоичных чисел, i-й и (n+i)-й входы которого соединены соответственно с первым и вторым входами i-го элемента ИСКЛЮЧАЮЩЕЕ ИЛИ-НЕ.

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

Устройство сравнения двоичных чисел содержит элементы И 1₁, …, 1_n-1, элементы ИСКЛЮЧАЮЩЕЕ ИЛИ-НЕ 2₁, …, 2_n+n и мажоритарные элементы 3₁, …, 3_n, причем второй вход и выход элемента 2_i соединены соответственно с третьим входом элемента 3_i и первым входом элемента 2_n+i, первый и второй входы элемента 3_i соединены соответственно с выходом и вторым входом элемента 2_n+i, вторые входы элементов 3₁ и 1_j соединены соответственно с шиной нулевого потенциала и выходом элемента 2_j+1, выходы элементов 3_j и 1_k соединены соответственно с вторым входом элемента 3_j+1 и первым входом элемента 1_k+1, а первый вход элемента 1₁ и выход элемента 1_n-1 соединены соответственно с выходом элемента 2₁ и дополнительным выходом устройства сравнения двоичных чисел, i-й, (n+i)-й входы и выход которого соединены соответственно с первым, вторым входами элемента 2_i и выходом элемента 3_n.

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

где есть символы операций ИСКЛЮЧАЮЩЕЕ ИЛИ, И, НЕ, Maj; z₀=0. В представленных ниже таблицах приведены значения реализуемых выражениями (1), (2) функций на всех возможных наборах значений их аргументов.

Анализ данных, приведенных в таблицах, позволяет заключить, что: 1) если y_j-1=0 или y_j-1=1 и a_j≠b_j, то y_j=0; 2) если y_j-1=1 и a_j=b_j, то y_j=1; 3) если a_i-1<b_i-1 или a_i-1=b_i-1 и z_i-1=0, то z_i=0; 4) если a_i-1>b_i-1 или a_i-1=b_i-1 и z_i-1=1, то z_i=1. Таким образом, когда A>B, либо A=В, либо A<B соответственно получим y_n-1=0, z_n=1 , y_n-1=1, z_n=0, либо y_n-1=z_n=0.

Вышеизложенные сведения позволяют сделать вывод, что предлагаемое устройство сравнения двоичных чисел обладает более широкими по сравнению с прототипом функциональными возможностями, так как выполняет распознавание отношений A>B, A=В, A<B, где A=a_n-1…a₀, B=b_n-1…b₀ есть n-разрядные двоичные числа, задаваемые двоичными сигналами a₀, …, a_n-1, b₀, …, b_n-1 ∈ {0,1}.

Устройство сравнения двоичных чисел, содержащее n мажоритарных элементов, причем выход предыдущего мажоритарного элемента подключен к второму входу последующего мажоритарного элемента, а выход n-го мажоритарного элемента является выходом устройства сравнения двоичных чисел, отличающееся тем, что в него дополнительно введены 2×n элементов ИСКЛЮЧАЮЩЕЕ ИЛИ-НЕ и n-1 элементов И, второй вход и выход i-го элемента ИСКЛЮЧАЮЩЕЕ ИЛИ-НЕ соединены соответственно с третьим входом i-го мажоритарного элемента и первым входом (n+i)-го элемента ИСКЛЮЧАЮЩЕЕ ИЛИ-НЕ, первый и второй входы i-го мажоритарного элемента соединены соответственно с выходом и вторым входом (n+i)-го элемента ИСКЛЮЧАЮЩЕЕ ИЛИ-НЕ, второй вход первого мажоритарного элемента и второй вход j-го элемента И соединены соответственно с шиной нулевого потенциала и выходом (j+1)-го элемента ИСКЛЮЧАЮЩЕЕ ИЛИ-НЕ, выход предыдущего элемента И соединен с первым входом последующего элемента И, а первый вход первого и выход (n-1)-го элементов И соединены соответственно с выходом первого элемента ИСКЛЮЧАЮЩЕЕ ИЛИ-НЕ и дополнительным выходом устройства сравнения двоичных чисел, i-й и (n+i)-й входы которого соединены соответственно с первым и вторым входами i-го элемента ИСКЛЮЧАЮЩЕЕ ИЛИ-НЕ.