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

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

Известны устройства селекции двоичных чисел (см., например, патент РФ 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) функций на всех возможных наборах значений их аргументов.

Анализ данных, приведенных в таблице, позволяет заключить, что при 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-разрядных двоичных чисел, задаваемых двоичными сигналами.

Устройство селекции двоичных чисел, содержащее 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-й группы.