устройство селекции большего из двух двоичных чисел

Формула изобретения

Устройство селекции большего из двух двоичных чисел, содержащее элемент «ИЛИ», отличающееся тем, что в него дополнительно введены 4(n-1) элементов «Запрет» и 3(n-2)+1 аналогичных упомянутому элементов «ИЛИ», причем все элементы сгруппированы в n групп так, что j-я группа содержит два элемента «Запрет» и элемент «ИЛИ», а m-я группа дополнительно содержит два элемента «Запрет» и два элемента «ИЛИ», в r-й группе выход i-го элемента «Запрет» соединен с i-м входом первого элемента «ИЛИ», в m-й группе выход i-го элемента «Запрет», подключенного инвертирующим входом к первому входу (i+1)-го элемента «ИЛИ», и выход (i+1)-го элемента «ИЛИ», подключенного вторым входом к выходу (3-i)-го элемента «Запрет», соединены соответственно с инвертирующим и неинвертирующим входами (i+2)-го элемента «Запрет», в первой группе инвертирующий и неинвертирующий входы первого элемента «Запрет» подключены соответственно к неинвертирующему и инвертирующему входам второго элемента «Запрет», первому и второму входам первого элемента «ИЛИ», выход i-го элемента «Запрет» первой группы и выход (i+2)-го элемента «Запрет» m-й группы соединены соответственно с инвертирующим входом i-го элемента «Запрет» второй группы и инвертирующим входом i-го элемента «Запрет» (m+1)-й группы, а первый, второй входы первого элемента «ИЛИ» первой группы, неинвертирующие входы первого, второго элементов «Запрет» r-й группы и выход первого элемента «ИЛИ» j-й группы образуют соответственно первый, (n+1)-й, r-й, (n+r)-й входы и j-й выход устройства селекции большего из двух двоичных чисел.

Описание изобретения к патенту

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

Известны устройства селекции большего из двух двоичных чисел (см., например, рис.4 на стр.24 в книге Цифровые и аналоговые интегральные микросхемы: Справочник / С.В.Якубовский, Л.И.Ниссельсон, В.И.Кулешова и др. Под ред. С.В.Якубовского. М.: Радио и связь, 1989 г.), выполняющие операцию mах(x₁,x₂), где x₁,x ₂ {0,1} - одноразрядные двоичные числа, задаваемые двоичными сигналами.

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

Наиболее близким устройством того же назначения к заявленному изобретению по совокупности признаков является, принятое за прототип, устройство селекции большего из двух двоичных чисел (патент РФ 2300135, кл. G06F 7/02, 2007 г.), который содержит элемент «ИЛИ» и выполняет операцию max(x_n-1 x₀, y_n-1 y₀),

где x_n-1 x₀, y_n-1 y₀ - n-разрядные двоичные числа, задаваемые двоичными сигналами x₀, , x_n-1,y₀, ,y_n-1 {0,1}.

К причине, препятствующей достижению указанного ниже технического результата при использовании прототипа, относится сложность устройства, обусловленная тем, что прототип состоит из логических элементов четырех типов (импликаторов, элементов «И», элементов «И-НЕ», элемента «ИЛИ»).

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

Указанный технический результат при осуществлении изобретения достигается тем, что в устройстве селекции большего из двух двоичных чисел, содержащем элемент «ИЛИ», особенность заключается в том, что в него дополнительно введены 4(n-1) элементов «Запрет» и 3(n-2)+1 аналогичных упомянутому элементов «ИЛИ», причем все элементы сгруппированы в n групп так, что j-я группа содержит два элемента «Запрет» и элемент «ИЛИ», а m-я группа дополнительно содержит два элемента «Запрет» и два элемента «ИЛИ», в r-й ( группе выход i-го элемента «Запрет» соединен с i-м входом первого элемента «ИЛИ», в m-й группе выход i-го элемента «Запрет», подключенного инвертирующим входом к первому входу (i+1)-го элемента «ИЛИ», и выход (i+1)-го элемента «ИЛИ», подключенного вторым входом к выходу (3-i)-го элемента «Запрет», соединены соответственно с инвертирующим и неинвертирующим входами (i+2)-го элемента «Запрет», в первой группе инвертирующий и неинвертирующий входы первого элемента «Запрет» подключены соответственно к неинвертирующему и инвертирующему входам второго элемента «Запрет», первому и второму входам первого элемента «ИЛИ», выход i-го элемента «Запрет» первой группы и выход (i+2)-го элемента «Запрет» m-й группы соединены соответственно с инвертирующим входом i-го элемента «Запрет» второй группы и инвертирующим входом i-го элемента «Запрет» (m+1)-й группы, а первый, второй входы первого элемента «ИЛИ» первой группы, неинвертирующие входы первого, второго элементов «Запрет» r-й группы и выход первого элемента «ИЛИ» j-й группы образуют соответственно первый, (n+1)-й, r-й, (n+r)-й входы j-й выход устройства селекции большего из двух двоичных чисел.

На чертеже представлена схема предлагаемого устройства селекции большего из двух двоичных чисел.

Устройство селекции большего из двух двоичных чисел содержит 4(n-1) элементов «Запрет» 1₁₁, 1₂₁, 1₁₂, , 1_4(n-1), 1_1n, 1_2n (третий снизу рис. в табл.3.5 на стр.103 в книге Справочник по цифровой вычислительной технике. Малиновский Б.Н., Александров В.Я., Боюн В.П. и др./ Под ред. Б.Н.Малиновского. Киев: Техника, 1974 г.), элемент «ИЛИ» 2₁₁ и 3(n-2)+1 элементов «ИЛИ» 2₁₂, , 2_3(n-1), 2_1n, причем все элементы сгруппированы в n групп так, что j-я группа содержит элементы 1_1j, 1_2j , 2_1j, a m-я группа дополнительно содержит элементы 1_3m, 1_4m, 2_2m, 2_3m, выход элемента соединен с i-м входом элемента 2_1r, выход элемента 1_im, подключенного инвертирующим входом к первому входу

элемента 2_(i+1)m, и выход элемента 2_(i+1)m, подключенного вторым входом к выходу элемента 1_(3-i)m, соединены соответственно с инвертирующим и неинвертирующим входами элемента 1_(i+2)m, инвертирующий и неинвертирующий входы элемента 1₁₁ подключены соответственно к неинвертирующему и инвертирующему входам элемента 1₂₁ первому и второму входам элемента 2₁₁, выход элемента 1_i1 и выход элемента 1_(i+2)m соединены соответственно с инвертирующим входом элемента 1_i2 и инвертирующим входом элемента 1_i(m+1), а первый, второй входы элемента 2₁₁, неинвертирующие входы элементов 1_1r, 1_2r и выход элемента 2_1j образуют соответственно первый, (n+1)-й, r-й, (n+r)-й входы j-й выход устройства селекции большего из двух двоичных чисел.

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

x_n-1 x₀ и y_n-1 y₀ (x_n-1, y_n-1 и x ₀ y₀ определяют значения старших и младших разрядов соответственно). Тогда сигнал на j-м выходе предлагаемого устройства будет определяться выражением

где

В представленной ниже таблице приведены значения реализуемых выражениями (2), (3) функций на всех возможных наборах значений их аргументов. Жирным в таблице выделены значения функций и их аргументов при j = 2.

z1(j-2)	z2(j-2)	xn-j+1	yn-j+1	z1(j-1)	z2(j-1)
0	0	0	0	0	0
0	0	0	1	1	0
0	0	1	0	0	1
0	0	1	1	0	0
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
-	-	0	0	0	0
-	-	0	1	1	0
-	-	1	0	0	1
-	-	1	1	0	0

Анализ данных, приведенных в таблице, позволяет заключить, что:

1) если z_1(j-2)=z_2(j-2)=0 и x_n-j+1 =y_n-j+1, то z_1(j-1)=z_2(j-1)=0;

2) если z_1(j-2)=z_2(j-2)=0 и x_n-j+1>y_n-j+1 (z_1(j-2)=z _2(j-2)=0 и y_n-j+1>x_n-j+1), то z_1(j-1)=0 и z_2(j-1)=1( z_1(j-1) =1 и z_2(j-1)=0;

3) если z_1(j-2) =0 и z_2(j-2)=1 (z_1(j-2)=1 и z_2(j-2) =0), то z_1(j-1)=0 и z_2(j-1)=1 (z_1(j-1) =1 и z_2(j-1)=0);

4) если x_n-1 =y_n-1 или x_n-1>y_n-1 (y _n-1>x_n-1), то соответственно z₁₁ =z₂₁=0 или z₁₁=0 и z₂₁=1 (z ₁₁=1 и z₂₁=0).

Таким образом, на первом и r-м выходах предлагаемого устройства согласно (1) соответственно получим

и

где x_n-1 x_n-r+1 и y_n-1 y_n-r+1 - фрагменты n-разрядных двоичных чисел x_n-1 x₀ и

y_n-1 y₀. Следовательно, с учетом (4), (5) имеем w _n-1 w₀ = max(x_n-1 x₀, y_n-1 y₀), где

w_n-1 w₀ - n-разрядное двоичное число, задаваемое двоичными сигналами w₀, ,w_n-1 {0,1} (w_n-1 и w₀ определяют значения старшего и младшего разрядов соответственно).

Вышеизложенные сведения позволяют сделать вывод, что предлагаемое устройство выполняет селекцию большего из двух n-разрядных двоичных чисел, задаваемых двоичными сигналами, и является по сравнению с прототипом более простым, так как состоит из логических элементов только двух типов (элементов «Запрет», элементов «ИЛИ»).