устройство селекции двоичных чисел

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

Устройство селекции двоичных чисел, содержащее 2n входов и n выходов, отличающееся тем, что в него введены 7n мажоритарных элементов, имеющих по три входа, и 2n элементов НЕ, причем все элементы сгруппированы в n групп так, что

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

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

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

Известны устройства селекции двоичных чисел (см., например, патент РФ 2300130, кл. G06F 7/02, 2007 г.), выполняющие селекцию меньшего из двух n-разрядных двоичных чисел, задаваемых двоичными сигналами.

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

Наиболее близким устройством того же назначения к заявленному изобретению по совокупности признаков является принятое за прототип устройство селекции двоичных чисел (патент РФ 2300135, кл. G06F 7/02, 2007 г.), которое содержит 2n входов, n выходов и выполняет селекцию большего из двух n-разрядных двоичных чисел, задаваемых двоичными сигналами.

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

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

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

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

Устройство селекции двоичных чисел содержит мажоритарные элементы 1₁₁, , 1_7n, имеющие по три входа, и элементы НЕ 2 ₁₁, , 2_2n, причем все элементы сгруппированы в n групп так, что j-я ( ) группа содержит элементы 1_1j, , 1_7j,

2_1j, 2_2j, выход элемента 1_ij ( ), подключенного третьим входом к первому входу элемента 1_(i+2)j, выход элемента 1_(i+2)j, подключенного третьим входом к выходу элемента 2_ij, и вход элемента 2_ij соединены соответственно с первым, третьим входами элемента 1_(i+4)j и выходом элемента 1_(3-i)j , а первый, третий и второй входы элемента

1 _7j соединены соответственно с первыми входами элементов 1_5j, 1_6j и объединенными вторым входом элемента 1_(i+4)j, четвертым настроечным входом устройства селекции двоичных чисел, подключенного третьим настроечным входом к объединенным вторым входам элементов 1_1j, , 1_4j, выход элемента 1_(i+4)k ( ) соединен с третьим входом элемента 1_i(k+1) , а третий вход элемента 1_i1 подключен к i-му настроечному входу устройства селекции двоичных чисел, j-й, (n+j)-й входы и j-й выход которого соединены соответственно с первыми входами элементов 1_1j, 1_2j и выходом элемента 1 _7j.

Работа предлагаемого устройства селекции двоичных чисел осуществляется следующим образом. На его первый, , четвертый настроечные входы подаются соответственно двоичные сигналы f₁, , f₄ {0,1}. На его первый, , n-й и (n+1)-й, , (2n)-й входы подаются соответственно двоичные сигналы x_n-1, , x₀ {0,1} и y_n-1, , y₀ {0,1}, которые задают подлежащие обработке n-разрядные двоичные числа x_n-1 x₀ и y_n-1 y₀ (x_n-1, y_n-1 и x _0, y₀ определяют значения старших и младших pазрядов соответственно). Сигнал на выходе мажоритарного элемента равен 1 (0) только тогда, когда на двух или на всех входах этого элемента действуют сигналы, равные 1 (0). Следовательно, если на втором входе мажоритарного элемента присутствует 1 (0), то этот элемент будет выполнять операцию ИЛИ (И) над сигналами, действующими на его первом и третьем входах. На основании изложенного сигналы на выходах элементов 1_5j, 1_6j ( ) и j-м выходе предлагаемого устройства будут определяться выражениями

где z₁₀=f₁, z ₂₀=f₂. В представленной ниже таблице приведены значения реализуемых выражениями (1), (2) функций на всех возможных наборах значений их аргументов.

z 1(j-1)	z2(j-1)	xn-j	уn-j	f3=0, f4=1	f3=1, f4=0
zlj	z 2j	z1j	z2j
0	0	0	0	0	0	0	0
0	0	0	1	0	0	0	1
0	0	1	0	0	0	1	0
0	0	1	1	0	0	0	0
0	1	0	0	0	1	0	1
0	1	0	1	0	1	0	1
0	1	1	0	0	1	0	1
0	1	1	1	0	1	0	1
1	0	0	0	1	0	1	0
1	0	0	1	1	0	1	0
1	0	1	0	1	0	1	0
1	0	1	1	1	0	1	0
1	1	0	0	1	1	1	1
1	1	0	1	0	1	1	1
1	1	1	0	1	0	1	1
1	1	1	1	1	1	1	1

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

1) z_1j=0 (z_2j =0), когда z_1(j-1)=0 (z_2(j-1)=0) или z _1(j-1)=z_2(j-1)=1 и x_n-j<y _n-j (z_1(j-1)=z_2(j-1)=1 и y_n-j <x_n-j);

2) z_1j=1 (z _2j=1), когда z_1(j-1)=1 и z_2(j-1)=0 (z_2(j-1)=1 и z_1(j-1)=0) или z_1(j-1) =z_2(j-1)=1 и x_n-j y_n-j (z_1(j-1)=z_2(j-1)=1 и y_n-j x_n-j);

а также, что при f ₃=1, f₄=0:

1) z_1j=1 (z_2j=1), когда z_1(j-1)=1 (z_2(j-1) =1) или z_1(j-1)=z_2(j-1)=0 и x_n-j >y_n-j (z_1(j-1)=z_2(j-1)=0 и y_n-j>x_n-j);

2) z _1j=0 (z_2j=0), когда z_1(j-1)=0 и z _2(j-1)=1 (z_2(j-1)=0 и z_1(j-1)=1) или z_1(j-1)=z_2(j-1)=0 и x_n-j y_n-j (z_1(j-1)=z_2(j-1)=0 и y_n-j x_n-j). Таким образом, при f₁=f ₂=f₄=1, f₃=0 на первом и r-м

( ) выходах предлагаемого устройства с учетом (3) соответственно получим

и

Здесь и далее 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₀=mах(x_n-1 x₀, y_n-1 y₀) селекции большего из чисел x_n-1 x₀ и y_n-1 y₀. При этом z_1n=1 (z_2n =1) когда x_n-1 x₀=mах(x_n-1 x₀, y_n-1 y₀) (y_n-1 y₀=mах(x_n-1 x₀,

y_n-1 y₀), то есть предлагаемое устройство одновременно с селекцией выполняет идентификацию селектируемого числа. Если f₃=0, f₄=1 и f₁ f₂, то согласно (3) и данным таблицы предлагаемое устройство воспроизводит операцию

селекции числа, назначенного сигналами f₁, f₂ (операцию мультиплексирования). Отметим, что w_n-1 w₀ - n-разрядное двоичное число, задаваемое двоичными сигналами w₀, , w_n-1 {0,1} (w_n-1 и w₀ определяют значения старшего и младшего разрядов соответственно). При f₁ =f₂=f₄=0, f₃=1 с учетом (3) имеем

Согласно (6), (7) предлагаемое устройство реализует операцию w_n-1 w₀=min(x_n-1

x₀, y_n-1 y₀) селекции меньшего из чисел x_n-1 x₀, y_n-1 y₀. При этом выполняется идентификация селектируемого числа, поскольку z_1n=0 (z_2n=0), когда x _n-1 x₀=mах(x_n-1 x₀, y_n-1 y₀) (y_n-1 y₀=mах(x_n-1 x_0, y_n-1 y₀)). Если f₃=1, f₄=0 и

f₁ f₂, то согласно (3) и данным таблицы предлагаемое устройство воспроизводит следующую операцию мультиплексирования:

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