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

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

 

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

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

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

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

К причине, препятствующей достижению указанного ниже технического результата при использовании прототипа, относятся большие аппаратурные затраты, обусловленные тем, что прототип содержит 7×n мажоритарных элементов и 2×n элементов НЕ.

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

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

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

Устройство селекции двоичных чисел содержит мажоритарные элементы 1₁₁, …, 1_5n и элементы НЕ 2₁, …, 2_n, которые сгруппированы в n групп так, что j-я группа содержит элементы 1_1j, …, 1_5j, 2_j, причем третий вход элемента 1_ij подключенного выходом к i-му входу элемента 1_5j, третьему входу элемента 1_(i+2)j, выход и вход элемента 2_j соединены соответственно с первым, вторым входами элемента 1_(i+2)j и выходом элемента 1_5j, выход элемента 1_(i+2)k подключен к третьему входу элемента 1_i(k+1), а третий вход элемента 1_i1, второй вход элемента 1_ij, третий вход и выход элемента 1_5j соединены соответственно с i-ым, третьим, четвертым настроечными входами и j-ым выходом устройства селекции двоичных чисел, j-й и (n+j)-й входы которого подключены соответственно к первым входам элементов 1_1j и 1_2j.

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

и

где ∨, ⋅, # есть символы операций ИЛИ, И, НЕ, Maj; z₁₀=ƒ₁; z₂₀=ƒ₂. В представленной ниже таблице приведены значения реализуемых выражениями (1), (2) функций на всех возможных наборах значений их аргументов.

Анализ данных, приведенных в таблице, позволяет заключить, что при ƒ₃=0, ƒ₄=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); a также, что при ƒ₃=1, ƒ₄=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). Таким образом, при ƒ₁=ƒ₂=ƒ₄=1, ƒ₃=0 на первом и r-ом выходах предлагаемого устройства с учетом (3) соответственно получим

и

Здесь и далее x_n-1…x_n-r+1 и y_n-1…y_n-r+1 - фрагменты n-разрядных двоичных чисел x_n-1…х₀ и y_n-1…y₀. Согласно (4), (5) предлагаемое устройство реализует операцию w_n-1…w₀=max(x_n-1…х₀, y_n-1…у₀) селекции большего из чисел x_n-1…х₀, y_n-1…у₀. При этом z_1n=1 (z_2n=1) когда x_n-1…х₀=max(x_n-1…х₀, y_n-1…у₀) (y_n-1…у₀=max(x_n-1…х₀, y_n-1…у₀)), то есть предлагаемое устройство одновременно с селекцией выполняет идентификацию селектируемого числа. Если ƒ₃=0, ƒ₄=1 и ƒ₁≠ƒ₂, то согласно (3) и данных таблицы предлагаемое устройство воспроизводит операцию

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

Согласно (6), (7) предлагаемое устройство реализует операцию w_n-1…w₀=min(x_n-1…х₀, y_n-1…у₀) селекции меньшего из чисел x_n-1…х₀, y_n-1…y₀. При этом выполняется идентификация селектируемого числа, поскольку z_1n=0 (z_2n=0) когда x_n-1…х₀=min(x_n-1…х₀, y_n-1…у₀) (y_n-1…у₀=min(x_n-1…x₀, y_n-1…y₀)). Если ƒ₃=1, ƒ₄=0 и ƒ₁≠ƒ₂, то согласно (3) и данных таблицы предлагаемое устройство воспроизводит следующую операцию мультиплексирования:

Отметим, что указанное устройство содержит 5×n мажоритарных элементов и n элементов НЕ.

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

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