УСТРОЙСТВО ВЫБОРА МИНИМАЛЬНОГО ИЛИ МАКСИМАЛЬНОГО ЧИСЛОВОГО ЗНАЧЕНИЯ ИЗ ДВУХ n-РАЗРЯДНЫХ ЧИСЕЛ Российский патент 2005 года по МПК G06F7/02 G06F7/06 

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

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

Известно устройство выбора минимальной или максимальной величины, содержащее сумматор, усилитель знака разности, коммутатор (US №5515306, кл. G 06 F 7/00, 1996).

Недостатком известного устройства является большая задержка усилителя знака разности и то, что решение о том, какое из чисел надо пропустить через коммутатор, принимается только после того, как перенос в сумматоре пробежит от младшего разряда к старшему разряду.

Наиболее близким по технической сущности к заявляемому изобретению является устройство выбора максимального значения из n-разрядных чисел, содержащее блок анализа величины чисел, выход которого подключен через усилитель сигнала выбора к блоку выбора минимального числа, выход которого является выходом устройства (US №5721809, кл. G 06 F 7/00, 1998).

Недостатком этого устройства является относительно большое время анализа одного разряда (около 5 логических уровней), а также то, что решение о том, какое из чисел надо пропустить через коммутатор, принимается только после анализа всех разрядов чисел. Кроме того, необходимо учесть задержку усилителя сигнала выбора.

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

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

и ,

где i=1, 2, ..., n, а_i и b_i - i-ые разряды двух n-разрядных двоичных чисел А и В, причем a_i и b_i - старшие разряды чисел, a a_n и b_n - младшие разряды чисел, при этом блок формирования выбирающих стробов для выбора минимального или максимального числа реализует для каждого разряда следующие две логические функции:

или для каждой группы по k разрядов:

а коммутатор выбора минимального или максимального числа реализует следующие логические функции:

min₁=a₁b₁ - для первого разряда,

- для второго разряда,

, где i=3, 4, 5,..., n, - для 3÷n разрядов,

max₁=a₁+b₁ - для первого разряда,

- для второго разряда,

, где i=3, 4, 5, ..., n, - для 3÷n разрядов,

или для каждого разряда каждой группы по k разрядов реализует следующие логические функции:

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

Сравнение предлагаемого устройства с ближайшим аналогом позволяет утверждать о соответствии критерию «новизна», а отсутствие отличительных признаков в аналогах говорит о соответствии критерию «изобретательский уровень».

Предварительные испытания позволяют судить о возможности широкого промышленного использования.

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

Устройство выбора минимальной или максимальной числовой величины из двух n-разрядных чисел содержит блок 1 преобразования чисел в поразрядные сигналы, блок 2 формирования выбирающих стробов и коммутатор 3 выбора минимального или максимального числа. Входы блока 1 являются входами 4-1 и 4-2 устройства, выход 5 через блок 2 формирования выбирающих стробов, имеющий вход 6 и выход 7, подключен к входу 8 управления коммутатора 3 выбора минимального или максимального числа. Выход коммутатора 3 является выходом 9 устройства, а первый и второй информационные входы 10-1 и 10-2 подключены к соответствующим входам 4-1 и 4-2 устройства.

Блок 1 преобразования чисел в поразрядные сигналы обеспечивает формирование в каждом разряде чисел двух сигналов

и , где i=1, 2,..., n, a_i и b_i - i-ые разряды n-разрядных двоичных чисел А и В.

Блок 2 формирования выбирающих стробов для выбора минимального или максимального числа реализует для каждого разряда чисел следующие логические функции:

или для каждой группы по k разрядов:

Коммутатор 3 выбора минимальной или максимальной величины реализует следующие логические функции:

min₁=a₁b₁ - для первого разряда,

- для второго разряда,

, где i=3, 4, 5,..., n - для 3÷n разрядов,

max₁=a₁+b₁ - для первого разряда,

- для второго разряда,

, где i=3, 4, 5, ..., n - для 3-n разрядов,

или для каждого разряда каждой группы по k разрядов реализует следующие логические функции:

Устройство работает следующим образом.

При поступлении на входы 4-1 и 4-2 устройства, например, двух двоичных чисел А и В блок 1 преобразования чисел в поразрядные сигналы формирует для каждого разряда поразрядные сигналы l_i и g_i, которые поступают на вход 6 блока 2 формирования выбирающих стробов, который формирует для каждого разряда или для каждой группы выбирающие стробы для коммутатора 3 выбора минимального или максимального числа согласно вышеуказанным формулам.

Следует отметить, что выбор старших разрядов минимального или максимального значения осуществляется, не дожидаясь сравнения младших разрядов этих чисел.

Табл.1 представляет собой таблицу истинности для определения двух старших разрядов минимальной и максимальной величин по двум старшим разрядам чисел А и В.

Из табл.1 получаем выражение для min₁:

min₁=a₁b₁

Действительно, если старший разряд хотя бы одного из чисел равняется "0", то и старший разряд минимальной величины будет равняться "0"; min₁="1", только в случае равенства "1" старших разрядов обоих чисел.

Для второго разряда минимальной величины получаем:

Так как и , и l₁ равно "1", если старший разряд числа А меньше, чем старший разряд числа В, g₁ равно "1", если старший разряд числа А больше, чем старший разряд числа В, то выражение для min₂ примет вид:

min₂=a₂l₁+b₂g₁+a₂b₂

Таблица 1a₁a₂b₁b₂min₁min₂max₁max₂00000000000100010010001000110011010000010101010101100110011101111000001010010110101010101011101111000011110101111110101111111111

а это выражение имеет следующий смысл: если старший разряд числа А меньше, чем старший разряд числа В, то в качестве второго разряда минимальной величины выбирается а₂. Если старший разряд числа А больше, чем старший разряд числа В, то в качестве второго разряда минимальной величины выбирается b₂. Если старший разряд числа А не меньше и не больше, чем старший разряд числа В (то есть, они равны), то второй разряд минимальной величины равен "1", только если вторые разряды обоих чисел равны "1".

Для следующих разрядов минимальной величины по аналогии с предыдущей формулой можно считать, что

Так как выражение в первых скобках равно L_i-1, а во вторых скобках - G_i-1, то выражение для min_i примет вид:

min_i=a_iL_i-1+b_iG_i-1+a_ib_i,

а после разложения по L_i-1 получим:

Так как G^s _i-1=g₁+g₂+...+g_i-1, то

т.е. выражение для i-ого разряда минимальной величины примет вид:

Последнее выражение можно реализовать на мультиплексоре с двух направлений, на управляющий вход которого подается сигнал L_i-1, а на информационные входы a_i и b_i(G^s _i-1+a₁) соответственно.

Использование функций L_i-1, G_i-1 и G^s _i-1 позволяет распараллелить анализ сравниваемых чисел (см. фиг.3). Вычислим для каждой k-разрядной группы групповые функции L_i ^gr, G_i ^gr и G_i ^sgr (здесь индекс i обозначает номер группы), при этом функции используют все разряды только своей группы. Так, для первой группы L₁ ^gr=L_k, G₁ ^gr=G_k, G₁ ^sgr=G^s _k функции второй группы используют разряды с номера k+1 до 2k, функции третьей группы используют разряды с номера 2k+1 до 3k и так далее. Для третьей группы справедливо следующее выражение для вычисления разрядов минимальной величины:

Так как выражение в первой и второй скобках равно L₃ ^res и G₃ ^res соответственно, то

min_2k+1-3k=a_2k+1-3kL₃ ^res+b_2k+1-3kG₃ ^res+a_2k+1-3kb_2k+1-3k.

Это выражение можно разложить по L₃ ^res, избавляясь от функции G₃ ^res и заменяя ее более простой функцией :

Полученное выражение также реализуется на мультиплексоре с двух направлений, управляемом сигналом L₃ ^res.

Из табл. 1 следует, что старший разряд максимальной величины равен логической сумме старших разрядов чисел А и В:

max₁=a₁+b₁

Для второго разряда получаем:

Используя вышеприведенные рассуждения, аналогичные для определения разрядов минимальной величины, получим следующие выражения для максимальной величины:

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

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

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

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

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

и , где i=1, 2,..., n, а_i и b_i - i-е разряды двух n-разрядных двоичных чисел А и В, причем a₁ и b₁ - старшие разряды чисел, a a_n и b_n - младшие разряды чисел.

или для каждой группы по k разрядов следующие логические функции:

min₁=a₁b₁ - для первого разряда,

- для второго разряда,

, где i=3, 4, 5,..., n, - для 3÷n разрядов,

max₁=a₁+b₁ - для первого разряда,

- для второго разряда,

где i=3, 4, 5,..., n, - для 3÷n разрядов,

или для каждого разряда каждой группы по k разрядов реализует следующие логические функции:

- для n/k группы из k разрядов.