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

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

 

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

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

Известно устройство выбора минимальной или максимальной величины, содержащее сумматор, усилитель знака разности, коммутатор (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 и bi - i-ые разряды двух n-разрядных двоичных чисел А и В, причем ai и bi - старшие разряды чисел, a an и bn - младшие разряды чисел, при этом блок формирования выбирающих стробов для выбора минимального или максимального числа реализует для каждого разряда следующие две логические функции:

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

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

min1=a1b1 - для первого разряда,

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

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

max1=a1+b1 - для первого разряда,

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

, где 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, ai и bi - i-ые разряды n-разрядных двоичных чисел А и В.

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

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

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

min1=a1b1 - для первого разряда,

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

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

max1=a1+b1 - для первого разряда,

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

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

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

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

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

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

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

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

min1=a1b1

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

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

Так как и , и l1 равно "1", если старший разряд числа А меньше, чем старший разряд числа В, g1 равно "1", если старший разряд числа А больше, чем старший разряд числа В, то выражение для min2 примет вид:

min2=a2l1+b2g1+a2b2

Таблица 1
a1a2b1b2min1min2max1max2
00000000
00010001
00100010
00110011
01000001
01010101
01100110
01110111
10000010
10010110
10101010
10111011
11000011
11010111
11101011
11111111

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

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

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

mini=aiLi-1+biGi-1+aibi,

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

Так как Gsi-1=g1+g2+...+gi-1, то

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

Последнее выражение можно реализовать на мультиплексоре с двух направлений, на управляющий вход которого подается сигнал Li-1, а на информационные входы ai и bi(Gsi-1+a1) соответственно.

Использование функций Li-1, Gi-1 и Gsi-1 позволяет распараллелить анализ сравниваемых чисел (см. фиг.3). Вычислим для каждой k-разрядной группы групповые функции Ligr, Gigr и Gisgr (здесь индекс i обозначает номер группы), при этом функции используют все разряды только своей группы. Так, для первой группы L1gr=Lk, G1gr=Gk, G1sgr=Gsk функции второй группы используют разряды с номера k+1 до 2k, функции третьей группы используют разряды с номера 2k+1 до 3k и так далее. Для третьей группы справедливо следующее выражение для вычисления разрядов минимальной величины:

Так как выражение в первой и второй скобках равно L3res и G3res соответственно, то

min2k+1-3k=a2k+1-3kL3res+b2k+1-3kG3res+a2k+1-3kb2k+1-3k.

Это выражение можно разложить по L3res, избавляясь от функции G3res и заменяя ее более простой функцией :

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

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

max1=a1+b1

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

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

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

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

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

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

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

и , где i=1, 2,..., n, аi и bi - i-е разряды двух n-разрядных двоичных чисел А и В, причем a1 и b1 - старшие разряды чисел, a an и bn - младшие разряды чисел.

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

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

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

min1=a1b1 - для первого разряда,

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

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

max1=a1+b1 - для первого разряда,

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

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

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

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



 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Изобретение относится к способам обработки листового материала с сортировкой листов. .

Изобретение относится к устройствам ВТ, а точнее к устройствам сортировки данных. .

Изобретение относится к вычислительной технике. .

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

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

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

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

Наверх