RU2841043C1

RU2841043C1 - Device for comparing binary numbers

Info

Publication number: RU2841043C1
Application number: RU2024133319A
Authority: RU
Inventors: Дмитрий Васильевич Андреев; Артём Юрьевич Дороднов
Filing date: 2024-11-07
Publication date: 2025-06-02

Abstract

FIELD: computer equipment.

SUBSTANCE: device for comparing binary numbers is intended for recognition of ratios X>Y, X=Y, X<Y, where X, Y are n-bit binary numbers set by binary signals, and can be used in digital computer systems as a comparator information processing means. Device for comparing binary numbers comprises 2×n implicators (1₁₁, 1₂₁, …, 1_1n, 1_2n) and 4×n-4 NAND elements (2₁₂, 2₂₂, 2₃₂, 2₄₂, …, 2_1n, 2_2n, 2_3n, 2_4n). Due to the said elements connection new scheme, which price according to Quine is equal to 14×n-8, the maximum signal propagation delay time in the disclosed device is determined by the expression τ=(2×n-1)×τ_E, where τ_E is the duration of the delay introduced by the logic element.

EFFECT: faster operation while preserving functional capabilities and Quine price of the prototype.

1 cl, 1 dwg, 1 tbl

Description

Изобретение относится к вычислительной технике и может быть использовано для построения средств автоматики, функциональных узлов систем управления и др.The invention relates to computer technology and can be used for constructing automation equipment, functional units of control systems, etc.

Известно устройство сравнения двоичных чисел (патент РФ 2353966, кл. G06F7/02, 2009г.), содержащее логические элементы, среди которых импликаторов, и выполняющее распознавание отношений X>Y, X=Y, X<Y, где X, Y есть n-разрядные двоичные числа, задаваемые двоичными сигналами.A device for comparing binary numbers is known (RU patent 2353966, class G06F7/02, 2009), containing logical elements, among which implicators, and performing recognition of relations X>Y, X=Y, X<Y, where X, Y are n-bit binary numbers specified by binary signals.

К причине, препятствующей достижению указанного ниже технического результат при использовании известного устройства сравнения двоичных чисел, относятся схемная сложность и низкое быстродействие, обусловленные тем, что цена по Квайну схемы упомянутого аналога равна и максимальное время задержки распространения сигнала в упомянутом аналоге определяется выражением , где τ_Э есть длительность задержки, вносимой логическим элементом.The reason preventing the achievement of the technical result specified below when using the known binary number comparison device is the circuit complexity and low speed, due to the fact that the Quine price of the circuit of the mentioned analogue is equal to and the maximum delay time of signal propagation in the mentioned analog is determined by the expression , where τ _E is the duration of the delay introduced by the logic element.

Наиболее близким устройством того же назначения к заявленному изобретению по совокупности признаков является принятое за прототип устройство сравнения двоичных чисел (патент РФ 2298220, кл. G06F7/02, 2007г.), содержащее логические элементы, среди которых элементов И-НЕ, импликаторов, и выполняющее распознавание отношений X>Y, X=Y, X<Y, где X, Y есть n-разрядные двоичные числа, задаваемые двоичными сигналами. При этом цена по Квайну схемы прототипа равна .The closest device for the same purpose to the claimed invention in terms of its features is the binary number comparison device adopted as a prototype (RU Patent 2298220, class G06F7/02, 2007), containing logical elements, among which NAND elements, implicators, and performing recognition of relations X>Y, X=Y, X<Y, where X, Y are n-bit binary numbers specified by binary signals. In this case, the Quine price of the prototype scheme is equal to .

К причине, препятствующей достижению указанного ниже технического результата при использовании прототипа, относится низкое быстродействие, обусловленное тем, что максимальное время задержки распространения сигнала в прототипе определяется выражением, где τ_Э есть длительность задержки, вносимой логическим элементом.The reason preventing the achievement of the technical result specified below when using the prototype is the low speed, due to the fact that the maximum delay time of signal propagation in the prototype is determined by the expression , where τ _E is the duration of the delay introduced by the logic element.

Техническим результатом изобретения является повышение быстродействия при сохранении функциональных возможностей и цены по Квайну прототипа.The technical result of the invention is an increase in performance while maintaining the functional capabilities and price according to Quine of the prototype.

Указанный технический результат при осуществлении изобретения достигается тем, что в устройстве сравнения двоичных чисел, содержащем импликаторов и элементов И-НЕ, которые сгруппированы в n групп так, что j-я () группа содержит два импликатора, а k-я () группа дополнительно содержит два элемента И-НЕ, в первой группе неинвертирующий и инвертирующий входы первого импликатора соединены соответственно с инвертирующим и неинвертирующим входами второго импликатора, первым и (n+1)-ым входами устройства сравнения двоичных чисел, выход i-го () импликатора первой группы подключен к второму входу i-го элемента И-НЕ второй группы, особенность заключается в том, что в k-ю группу дополнительно введены два элемента И-НЕ, в k-й группе выход i-го импликатора, подключенного неинвертирующим входом к инвертирующему входу (3-i)-го импликатора, и выход i-го элемента И-НЕ, подключенного вторым входом к первому входу (5-i)-го элемента И-НЕ, соединены соответственно с первым входом i-го и вторым входом (i+2)-го элементов И-НЕ, выход (i+2)-го элемента И-НЕ предыдущей группы подключен к первому входу (5-i)-го элемента И-НЕ последующей группы, а выход (i+2)-го элемента И-НЕ n-й группы является i-ым выходом устройства сравнения двоичных чисел, k-й и (n+k)-й входы которого образованы соответственно неинвернтирующими входами первого и второго импликаторов k-й группы.The specified technical result in the implementation of the invention is achieved by the fact that in the device for comparing binary numbers, containing implicators and NAND gates that are grouped into n groups such that the j-th ( ) the group contains two implicators, and the k-th ( ) the group additionally contains two AND-NOT elements, in the first group the non-inverting and inverting inputs of the first implicator are connected respectively to the inverting and non-inverting inputs of the second implicator, the first and (n+1)th inputs of the binary number comparison device, the output of the i-th ( ) the implicator of the first group is connected to the second input of the i-th AND-NOT element of the second group, the peculiarity is that two AND-NOT elements are additionally introduced into the k-th group, in the k-th group the output of the i-th implicator, connected by the non-inverting input to the inverting input of the (3-i)-th implicator, and the output of the i-th AND-NOT element, connected by the second input to the first input of the (5-i)-th AND-NOT element, are connected respectively to the first input of the i-th and the second input of the (i+2)-th AND-NOT elements, the output of the (i+2)-th AND-NOT element of the previous group is connected to the first input of the (5-i)-th AND-NOT element of the subsequent group, and the output of the (i+2)-th AND-NOT element of the n-th group is the i-th output of the binary number comparison device, the k-th and (n+k)-th inputs of which are formed respectively by the non-inverting inputs of the first and second implicators of the k-th groups.

На чертеже представлена схема предлагаемого устройства сравнения двоичных чисел.The drawing shows a diagram of the proposed binary number comparison device.

Устройство сравнения двоичных чисел содержит импликаторов 1₁₁, 1₂₁, …, 1_1n, 1_2n и элементов И-НЕ 2₁₂, 2₂₂, 2₃₂, 2₄₂, …, 2_1n, 2_2n, 2_3n, 2_4n, причем все импликаторы и элементы И-НЕ сгруппированы в n групп так, что j-я группа содержит импликаторы 1_1j, 1_2j, а k-я () группа дополнительно содержит элементы 2_1k, 2_2k, 2_3k, 2_4k, неинвертирующий и инвертирующий входы импликатора 1₁₁ соединены соответственно с инвертирующим и неинвертирующим входами импликатора 1₂₁, первым и (n+1)-ым входами устройства сравнения двоичных чисел, выход импликатора 1_i1 подключен к второму входу элемента 2_i2, выход импликатора 1_ik, подключенного неинвертирующим входом к инвертирующиму входу импликатора 1_(3-i)k, и выход элемента 2_ik, подключенного вторым входом к первому входу элемента 2_(5-i)k, соединены соответственно с первым входом элемента 2_ik и вторым входом элемента 2_(i+2)k, выход элемента 2_(i+2)r подключен к первому входу элемента 2_(5-i)(r+1), а выход элемента 2_(i+2)n является i-ым выходом устройства сравнения двоичных чисел, k-й и (n+k)-й входы которого образованы соответственно неинвертирующими входами импликаторов 1_1k и 1_2k.The binary number comparator contains implicators 1 ₁₁ , 1 ₂₁ , …, 1 _1n , 1 _2n and NAND gates 2 ₁₂ , 2 ₂₂ , 2 ₃₂ , 2 ₄₂ , …, 2 _1n , 2 _2n , 2 _3n , 2 _4n , where all the implicators and NAND gates are grouped into n groups so that the j-th the group contains implicators 1 _1j , 1 _2j , and the k-th ( ) the group additionally contains elements 2 _1k , 2 _2k , 2 _3k , 2 _4k , the non-inverting and inverting inputs of the implicator 1 ₁₁ are connected respectively to the inverting and non-inverting inputs of the implicator 1 ₂₁ , the first and (n+1)th inputs of the binary number comparison device, the output of the implicator 1 _i1 connected to the second input of element 2 _i2 , the output of implicator 1 _ik , connected by the non-inverting input to the inverting input of implicator 1 _(3-i)k , and the output of element 2 _ik , connected by the second input to the first input of element 2 _(5-i)k , are connected respectively to the first input of element 2 _ik and the second input of element 2 _(i+2)k , the output of element 2 _(i+2)r connected to the first input of element 2 _(5-i)(r+1) , and the output of element 2 _(i+2)n is the i-th output of the binary number comparison device, the k-th and (n+k)-th inputs of which are formed by the non-inverting inputs of implicators 1 _1k and 1 _2k , respectively.

Работа предлагаемого устройства сравнения двоичных чисел осуществляется следующим образом. На его первый, …, n-й и (n+1)-й,…,(2×n)-й входы подаются соответственно произвольные двоичные сигналы x_n-1,…,x₀∈{0,1} и y_n-1,…,y₀∈{0,1}, которые задают подлежащие сравнению n-разрядные двоичные числа X=x_n-1…x₀, Y=y_n-1…y₀ (x_n-1, y_n-1 и x₀, y₀ определяют значения старших и младших разрядов соответственно). В представленной ниже таблице приведены значения формируемых элементами 2_3k, 2_4k () сигналов z_1k, z_2k, полученные для всех возможных наборов значений сигналов z_1(k-1), z_2(k-1), x_n-k, y_n-k, причем , .The proposed binary number comparison device operates as follows. Its first, …, n-th and (n+1)-th,…,(2×n)-th inputs are supplied with arbitrary binary signals x _n-1 ,…,x ₀ ∈{0,1} and y _n-1 ,…,y ₀ ∈{0,1}, which specify the n-bit binary numbers to be compared X=x _n-1 …x ₀ , Y=y _n-1 …y ₀ (x _n-1 , y _n-1 and x ₀ , y ₀ determine the values of the senior and junior digits, respectively). The table below shows the values formed by the elements 2 _3k , 2 _4k ( ) signals z _1k , z _2k , obtained for all possible sets of signal values z _1(k-1) , z _2(k-1) , x _nk , y _nk , and , .

z_1(k-1) z _1(k-1) z_2(k-1) z _2(k-1) x_n-k x _nk y_n-k y _nk z_1k from _1k z_2k from _2k 00 11 00 00 00 11 00 11 00 11 00 11 00 11 11 00 00 11 00 11 11 11 00 11 11 00 00 00 11 00 11 00 00 11 11 00 11 00 11 00 11 00 11 00 11 11 11 00 11 11 00 00 11 11 11 11 00 11 00 11 11 11 11 00 11 00 11 11 11 11 11 11

Анализ данных, приведенных в таблице, позволяет заключить, что 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-k<y_n-k (z_1(k-1)=z_2(k-1)=1 и y_n-k<x_n-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-k≥y_n-k (z_1(k-1)=z_2(k-1)=1 и y_n-k≥x_n-k). Дополнительно отметим, что z₁₁=0 (z₂₁=0), когда x_n-1<y_n-1 (y_n-1<x_n-1), и что z₁₁=1 (z₂₁=1), когда x_n-1≥y_n-1 (y_n-1≥x_n-1). Таким образом, если X>Y либо X=Y либо X<Y, то z_1n=1, z_2n=0 либо z_1n=z_2n=1 либо z_1n=0, z_2n=1 соответственно.An analysis of the data presented in the table allows us to conclude that z _1k =0 (z _2k =0) when z _1(k-1) =0 (z _2(k-1) =0) or z _1(k-1) =z _2(k-1) =1 and x _nk <y _nk (z _1(k-1) =z _2(k-1) =1 and y _nk <x _nk ), and that z _1k =1 (z _2k =1) when z _1(k-1) =1 and z _2(k-1) =0 (z _2(k-1) =1 and z _1(k-1) =0) or z _1(k-1) =z _2(k-1) =1 and x _nk ≥y _nk (z _1(k-1) =z _2(k-1) =1 and y _nk ≥x _nk ). Additionally, note that z ₁₁ =0 (z ₂₁ =0) when x _n-1 <y _n-1 (y _n-1 <x _n-1 ), and that z ₁₁ =1 (z ₂₁ =1) when x _n-1 ≥y _n-1 (y _n-1 ≥x _n-1 ). Thus, if X>Y or X=Y or X<Y, then z _1n =1, z _2n =0 or z _1n =z _2n =1 or z _1n =0, z _2n =1, respectively.

Вышеизложенные сведения позволяют сделать вывод, что предлагаемое устройство сравнения двоичных чисел выполняет распознавание отношений X>Y, X=Y, X<Y, где X, Y есть n-разрядные двоичные числа, задаваемые двоичными сигналами, и обладает более высоким по сравнению с прототипом быстродействием, поскольку максимальное время задержки распространения сигнала в предлагаемом устройстве определяется выражением , где τ_Э есть длительность задержки, вносимой логическим элементом. При этом цена по Квайну схемы предлагаемого устройства равна .The above information allows us to conclude that the proposed device for comparing binary numbers performs recognition of the relations X>Y, X=Y, X<Y, where X, Y are n-bit binary numbers specified by binary signals, and has a higher speed compared to the prototype, since the maximum delay time of signal propagation in the proposed device is determined by the expression , where τ _E is the duration of the delay introduced by the logic element. In this case, the Quine price of the proposed device circuit is equal to .

Claims

A binary number comparison device comprising implicators and NAND gates that are grouped into n groups such that the j-th ( ) the group contains two implicators, and the k-th ( ) the group additionally contains two AND-NOT elements, where in the first group the non-inverting and inverting inputs of the first implicator are connected respectively to the inverting and non-inverting inputs of the second implicator, the first and (n+1)th inputs of the binary number comparison device, and the output of the i-th ( ) the implicator of the first group is connected to the second input of the i-th AND-NOT element of the second group, characterized in that two AND-NOT elements are additionally introduced into the k-th group, in the k-th group the output of the i-th implicator, connected by the non-inverting input to the inverting input of the (3-i)-th implicator, and the output of the i-th AND-NOT element, connected by the second input to the first input of the (5-i)-th AND-NOT element, are connected respectively to the first input of the i-th and the second input of the (i+2)-th AND-NOT elements, the output of the (i+2)-th AND-NOT element of the previous group is connected to the first input of the (5-i)-th AND-NOT element of the subsequent group, and the output of the (i+2)-th AND-NOT element of the n-th group is the i-th output of the binary number comparison device, the k-th and (n+k)-th inputs of which are formed respectively by the non-inverting inputs of the first and second implicators of the k-th group.