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

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

 

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

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

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

Устройство селекции двоичных чисел содержит мажоритарные элементы 111, …, 17n, имеющие по три входа, и элементы НЕ 211, …, 22n, причем все элементы сгруппированы в n групп так, что j-я () группа содержит элементы 11j,, 17j,

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

17j соединены соответственно с первыми входами элементов 15j, 16j и объединенными вторым входом элемента 1(i+4)j, четвертым настроечным входом устройства селекции двоичных чисел, подключенного третьим настроечным входом к объединенным вторым входам элементов 11j, …, 14j, выход элемента 1(i+4)k () соединен с третьим входом элемента 1i(k+1), а третий вход элемента 1i1 подключен к i-му настроечному входу устройства селекции двоичных чисел, j-й, (n+j)-й входы и j-й выход которого соединены соответственно с первыми входами элементов 11j, 12j и выходом элемента 17j.

Работа предлагаемого устройства селекции двоичных чисел осуществляется следующим образом. На его первый, …, четвертый настроечные входы подаются соответственно двоичные сигналы f1, …, f4∈{0,1}. На его первый, …, n-й и (n+1)-й, …, (2n)-й входы подаются соответственно двоичные сигналы xn-1, …, x0∈{0,1} и yn-1, …, y0∈{0,1}, которые задают подлежащие обработке n-разрядные двоичные числа xn-1…x0 и yn-1…y0 (xn-1, yn-1 и x0, y0 определяют значения старших и младших pазрядов соответственно). Сигнал на выходе мажоритарного элемента равен 1 (0) только тогда, когда на двух или на всех входах этого элемента действуют сигналы, равные 1 (0). Следовательно, если на втором входе мажоритарного элемента присутствует 1 (0), то этот элемент будет выполнять операцию ИЛИ (И) над сигналами, действующими на его первом и третьем входах. На основании изложенного сигналы на выходах элементов 15j, 16j () и j-м выходе предлагаемого устройства будут определяться выражениями

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

z1(j-1) z2(j-1) xn-j уn-j f3=0, f4=1 f3=1, f4=0
zlj z2j 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

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

1) z1j=0 (z2j=0), когда z1(j-1)=0 (z2(j-1)=0) или z1(j-1)=z2(j-1)=1 и xn-j<yn-j (z1(j-1)=z2(j-1)=1 и yn-j<xn-j);

2) z1j=1 (z2j=1), когда z1(j-1)=1 и z2(j-1)=0 (z2(j-1)=1 и z1(j-1)=0) или z1(j-1)=z2(j-1)=1 и xn-j≥yn-j (z1(j-1)=z2(j-1)=1 и yn-j≥xn-j);

а также, что при f3=1, f4=0:

1) z1j=1 (z2j=1), когда z1(j-1)=1 (z2(j-1)=1) или z1(j-1)=z2(j-1)=0 и xn-j>yn-j (z1(j-1)=z2(j-1)=0 и yn-j>xn-j);

2) z1j=0 (z2j=0), когда z1(j-1)=0 и z2(j-1)=1 (z2(j-1)=0 и z1(j-1)=1) или z1(j-1)=z2(j-1)=0 и xn-j≤yn-j (z1(j-1)=z2(j-1)=0 и yn-j≤xn-j). Таким образом, при f1=f2=f4=1, f3=0 на первом и r-м

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

и

Здесь и далее xn-1…xn-r+1 и yn-1…yn-r+1 - фрагменты n-разрядных двоичных чисел xn-1…x0 и yn-1…y0. Согласно (4), (5) предлагаемое устройство реализует операцию wn-1…w0=mах(xn-1…x0, yn-1…y0) селекции большего из чисел xn-1…x0 и yn-1…y0. При этом z1n=1 (z2n=1) когда xn-1…x0=mах(xn-1…x0, yn-1…y0) (yn-1…y0=mах(xn-1…x0,

yn-1…y0), то есть предлагаемое устройство одновременно с селекцией выполняет идентификацию селектируемого числа. Если f3=0, f4=1 и f1≠f2, то согласно (3) и данным таблицы предлагаемое устройство воспроизводит операцию

селекции числа, назначенного сигналами f1, f2 (операцию мультиплексирования). Отметим, что wn-1…w0 - n-разрядное двоичное число, задаваемое двоичными сигналами w0, …, wn-1∈{0,1} (wn-1 и w0 определяют значения старшего и младшего разрядов соответственно). При f1=f2=f4=0, f3=1 с учетом (3) имеем

Согласно (6), (7) предлагаемое устройство реализует операцию wn-1…w0=min(xn-1

x0, yn-1…y0) селекции меньшего из чисел xn-1…x0, yn-1…y0. При этом выполняется идентификация селектируемого числа, поскольку z1n=0 (z2n=0), когда xn-1…x0=mах(xn-1…x0, yn-1…y0) (yn-1…y0=mах(xn-1…x0, yn-1…y0)). Если f3=1, f4=0 и

f1≠f2, то согласно (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-й группы.



 

Похожие патенты:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Наверх