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

Чертежи

Описание

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

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

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

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

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

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

Указанный технический результат при осуществлении изобретения достигается тем, что в устройстве селекции большего из двоичных чисел, содержащем 2×(n-2) элементов 2И, особенность заключается в том, что в него дополнительно введены n+1 элементов 2И, n элементов 3ИЛИ, n-1 элементов НЕ и 3×(n-1) мажоритарных элементов, причем все элементы сгруппированы в n групп так, что k-я (

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

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

Устройство селекции большего из двоичных чисел содержит элементы 2И 1₁₂,…,1_3n, элементы 3ИЛИ 2₁,…,2_n, элементы НЕ 3₁,…,3_n-1, мажоритарные элементы 4₁₁,…,4_3(n-1), причем все элементы сгруппированы в n групп так, что k-я (

) и n-я группы содержат соответственно элементы 2_k, 3_k, 4_1k, 4_2k 4_3k и элемент 2_n, а r-я ( ) группа дополнительно содержит элементы 1_r, 1_2r, 1_3r второй вход элемента 4_ik ( ), подключенного третьим входом к выходу элемента 3_k, и вход элемента 3_k соединены соответственно с i-ым входом и выходом элемента 2_k, выход элемента 1_ir, первый вход элемента 1_im ( ) и выход элемента 4_ik подключены соответственно к i-му входу элемента 2_r, первому входу элемента 4_im и первому входу элемента 1_i(k+1), а второй вход элемента 4_i1, подключенного первым входом к шине единичного потенциала, второй вход элемента 1_ir и выход элемента 2_j ( ) соединены соответственно с (n×i-n+1)-ым, (n×i-n+r)-ым входами и j-ым выходом устройства селекции большего из двоичных чисел.

Работа предлагаемого устройства селекции большего из двоичных чисел осуществляется следующим образом. На его первый,…,n-й, (n+1)-й,…, (2×n)-й, (2×n+1)-й,…, (3×n)-й входы подаются соответственно произвольные двоичные сигналы x_n-1,…,х₀∈{0,1}, y_n-1,…,у₀∈{0,1}, g_n-1,…,g₀∈{0,1}, которые задают подлежащие обработке n-разрядные двоичные числа x_n-1…х₀, y_n-1…у₀, g_n-1…g₀ (x_n-1, y_n-1, g_n-1 и х₀, y_0, g₀ определяют значения старших и младших разрядов соответственно). Тогда сигнал на j-ом (

) выходе предлагаемого устройства будет определяться выражением

где

Здесь ∨, ⋅,^⎯, # есть символы операций ИЛИ, И, НЕ, Maj. Отметим, что сигнал на выходе трехвходового мажоритарного элемента равен 1 (0) только тогда, когда на двух или на трех входах этого элемента действуют сигналы, равные 1 (0). В представленной ниже таблице приведены значения реализуемых выражениями (2), (3), (4) функций на всех возможных наборах значений их аргументов. Жирным в таблице выделены значения функций и их аргументов при j=2.

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

1) если x_n-1=y_n-1=g_n-1 либо x_n-1>y_n-1=g_n-1 либо y_n-1>x_n-1=g_n-1 либо g_n-1>x_n-1=y_n-1 либо x_n-1=y_n-1>g_n-1 либо x_n-1=g_n-1>y_n-1 либо y_n-1=g_n-1>x_n-1, то соответственно z₁₁=z₂₁=z₃₁=1 либо z₁₁=1, z₂₁=z₃₁=0 либо z₂₁=1, z₁₁=z₃₁=0 либо z₃₁=1, z₁₁=z₂₁=0 либо z₁₁=z₂₁=1, z₃₁=0 либо z₁₁=z₃₁=1, z₂₁=0 либо z₂₁=z₃₁=1, z₁₁=0;

2) если z_1(j-2)=z_2(j-2)=z_3(j-2)=1 и x_n-j+1=y_n-j+1=g_n-j+1, либо z_1(j-2)=z_2(j-2)=z_3(j-2)=1 и x_n-j+1>y_n-j+1=g_n-j+1 либо z_1(j-2)=z_2(j-2)=z_3(j-2)=1 и y_n-j+1>x_n-j+1=g_n-j+1 либо z_1(j-2)=z_2(j-2)=z_3(j-2)=1 и g_n-j+1>x_n-j+1=y_n-j+1 либо z_1(j-2=z_2(j-2)=z_3(j-2)=1 и x_n-j+1=y_n-j+1>g_n-j+1 либо z_1(j-2)=z_2(j-2)=z_3(j-2)=1 и x_n-j+1=g_n-j+1>y_n-j+1 либо z_1(j-2)=z_2(j-2)=z_3(j-2)=1 и y_n-j+1=g_n-j+1>x_n-j+1, то соответственно z_1(j-1)=z_2(j-1)=z_3(j-1)=1 либо z_1(j-1)=1, z_2(j-1)=z_3(j-l)=0 либо z_2(j-1)=1, z_1(j-1)=z_3(j-1)=0 либо z_3(j-1)=1, z_1(j-1)=z_2(j-1)=0 либо z_1(j-1)=z_2(j-1)=1, z_3(j-1)=0 либо z_1(j-1)=z_3(j-1)=1, z_2(j-1)=0 либо z_2(j-1)=z_3(j-1)=1, z_1(j-1)=0;

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

4) если z_1(j-2)=z_2(j-2)=1, z_3(j-2)=0 и x_n-j+1=y_n-j+1 либо z_1(j-2)=z_2(j-2)=1, z_3(j-2)=0 и x_n-j+1>y_n-j+1 либо z_1(j-2)=z_2(j-2)=1, z_3(j-2)=0 и x_n-j+1n-j+1, то соответственно z_1(j-1)=z_2(j-1)=1, z_3(j-1)=0 либо z_1(j-1)=1, z_2(j-1)=z_3(j-1)=0 либо z_2(j-1)=1, z_1(j-1)=z_3(j-1)=0;

5) если z_1(j-2)=z_3(j-2)=1, z_2(j-2)=0 и x_n-j+1=g_n-j+1 либо z_1(j-2)=z_3(j-2)=1, z_2(j-2)=0 и x_n-j+1>g_n-j+1 либо z_1(j-2)=z_3(j-2)=1, z_2(j-2)=0 и x_n-j+1n-j+1, то соответственно z_1(j-1)=z_3(y-1)=1, z_2(j-1)=0 либо z_1(j-l)=1, z_2(j-1)=z_3(j-l)=0 либо z_3(j-l)=1, z_1(j-1)=z_2(j-1)=0;

6) если z_2(j-2)=z_3(j-2)=1, z_1(j-2)=0 и y_n-j+1=g_n-j+1 либо z_2(j-2)=z_3(j-2)=1, z_1(j-2)=0 и y_n-j+1>g_n-j+1 либо z_2(j-2)=z_3(j-2)=1, z_1(j-2)=0 и y_n-j+1n-j+1, то соответственно z_2(j-1)=z_3(j-1)=1, z_1(j-1)=0 либо z_2(j-l)=1, z_1(j-l)=z_3(j-l)=0 либо z_3(j-l)=1, z_1(j-l)=z_2(j-1)=0.

Таким образом, на первом и r-ом (

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

и

,

где x_n-1…x_n-r+1, y_n-1…y_n-r+1, g_n-1…g_n-r+1 - фрагменты n-разрядных двоичных чисел x_n-1…x₀, y_n-1…y₀, g_n-1…g₀. Следовательно, с учетом (5), (6) имеем w_n-1…w₀=max(x_n-1…x₀, y_n-1…y₀, g_n-1…g₀), где w_n-1…w₀ есть n-разрядное двоичное число, задаваемое двоичными сигналами w₀,…,w_n-1∈{0,1} (w_n-1 и w₀ определяют значения старшего и младшего разрядов соответственно).

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

Реферат

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

Формула