Устройство для выделения экстремального из @ , @ -разрядных двоичных чисел

 

Изобретение относится к автоматике и вычислительной технике и может быть использовано в технических средствах для вьщеления экстремального числа из совокупности п , « -разрядных двоичных чисел. Цель изобретения - упрощение устройства. Она достигается новьгм алгоритмом работы устройства при поразрядном анализе чисел. Устройство содержит тх П узлов анализа и многовходовые элементы ИЛИ с элементами НЕ на выходе, причем каждый (1 xj )-й узел анализа, jгде j 1, 2,. ..., п , содержит элемент ИЛИ, каждый ( -i х j )-й узел анализа содержит первь и второй элементы И и элемент ИЛИ, каждый (тх j )-й узел анализа включает элемент И. Каждый (1 xj )й узел анализа и первый элемент ИЛИ-НЕ анализирует старшие разряды чисел. В каждом (t Xj )-м узле анализа производится сравнение i -х разрядов чисел, поданных на j -ю группу входов, со значением, поступающим с выхода i -х элементов ИЛИ-НЕ. При этом учитываются сигналы анализа предыдуищх разрядов . 1 ил. i (Л ч X) СО

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (19) (11) (51) 4 С 06 F 7/02

ОПИСАНИЕ ИЗОБРЕТЕНИЯ,, К ABTOPCHOMY СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3793259/24-24 (22) 24.09.84 (46) 15.03.86. Бюл. У 10 (71) Институт технической кибернетики АН БССР (72) Г.А.Буткин и А.Г.Ярусов (53) 681. 142.07(088.8) (56) Авторское свидетельство СССР

М 514291. кл. G 06 F 7/02, 1976, Авторское свидетельство СССР

N - 752326, кл . С 06 F 7/02, 1980. (54) УСТРОЙСТВО ДЛЯ ВЫДЕЛЕНИЯ ЗКСТРЕИАЛЬНОГО ИЗ )), п1 -РАЗРЯДНЫХ ДВОИЧНЫХ ЧИСЕЛ (57) Изобретение относится к автоматике и вычислительной технике и может быть использовано в технических средствах для выделения экстремального числа из совокупности л

)и-разрядных двоичных чисел. Цель изобретения — упрощение устройства. Она достигается новым алгоритмом работы устройства при поразрядном анализе чисел. Устройство содержит Ф х и узлов анализа и многовходовые элементы ИЛИ с элементами НЕ на выходе, причем каждый (1 х j )-й узел анализа, где I = 1, 2, ..., n, содержит эле мент ИЛИ, каждый (i x j )-й узел анализа содержит первый и второй элементы И и элемент ИЛИ, каждый (н)х j )-й узел анализа включает элемент И. Кажцый (I x j )-й узел анализа и первый элемент ИЛИ-НЕ анализирует старшие разряды чисел. В каждом (1 х 1 ) м узле анализа производит ся сравнение i -х разрядов чисел, поданных на j --ю группу входов, со значением, поступающим с выхода (-х элементов ИЛИ-НЕ, При этом учитываются сигналы анализа предыдущих разрядов. 1 ил.

Ф 1

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

Целью изобретения является упрощение устройства.

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

Устройство содержит узлы анализа 1, которые включают элемент И 2, элемент ИЛИ 3, элемент И 4., tl --входовые элементы ИЛИ 5, (1 х j )-й узел анализа включает элемент ИЛИ 6, (tn x j )-й узел анализа включает .элемент И 7, информационные выходы

8 разрядов экстремального числа,, элементы НЕ 9, входы 10 разрядов анализируемого числа.

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

Анализируемые числа подаются на информационные группы входов устроиства, о,, 0 ..., о причем старшие разряды чисел подаются на входы и,,, и, и одновременно на соответствующие входы элемента ИЛИ 5,.

Группа элементов ИЛИ б<. .. °, 6 „ и элемент ИЛИ 5» с элементом НЕ на выходе анализируют старшие разряды чисел следующим образом.

Если старшие разряды всех чисел равны единице, то на выходе 8 устройства сформируется нулевой сигнал, соответствующий инверсному значению старшего разряда экстремального (максимального) числа.

Ф

Поскольку при этом выделить номер 1 числа по старшим разрядам невозможно, то единичные сигналы сформируются на всех входах элементов

ИЛИ 6 и разрешает анализ следующих разрядов всех чисел в узлах 1 2j.

Если старшие разряды всех чисел равны нулю, то на выходе 8 сформируется единичный сигнал. Поскольку вьделить номер 1 по старшим разрядам в этом случае невозможно, то на выходах элементов ИЛИ 6 аналогично сформируются единицы.

Если старшие разряды анализируемых чисел различны (содержат нули и единицы), то на выходе 81 сформируется нулевой сигнал (инверсное значение старшего разряда экстремума) .

218379 2

На вйходе элемента 6, на входы которого был подан нулевой разряд, сформируется нуль, который в узле 1

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

В каждом (j x j )-м узле анализа производится сравнение 1 -х разря-дов чисел, поданных на.j -ю группу входов со значением, поступающим с выхода 1 -х элементов ИЛИ 5 ;

-НЕ 9 . При этом учитываются сигна1 лы, поступающие на вход элементов

И 2, выработанные в результате ана-

15 лиза предьдущих (старших) разрядов.

Каждый (1 х j )-й узел анализа работает в соответствии со следующей таблицей истинности.

45 элемента 5< формируется значение 1, которое поступает на выходы элементов ИЛИ 6,, 6, 6 и вторые входы элементов И 2 соответствующих узлов анализа 1,, 1 2 1 э.

На первые входы элементов И 2 этих узлов анализа поступают вторые разряды чисел: 1, 1, О. С учетом логики работы блока анализа на выходах узлов анализа 1, 1,, 1 э формируются значения 1, 1, О, кото50

Групповая работа узлов анализа

1;,, ..., 1„., элементом 5; аналогична вышеописанной. работе элементов

6,, ..., 6 с элементами 5,-9

Сигналы, сформированные на выходах узлов анализа 1(m — 1), 1(а- 1)„, управляют- прохождением младших разрядов чисел на элемент

5щ. При этом на выходе 8 > устройства нулевой сигнал сформируется, если на входах хотя бы одного элемента 7 окажутся единичными разряд числа и управляющий сигнал.

В результате работы устройства на выходах 8,, ° .., 8д„ формируется значение экстремального (максимального) числа в инверсном коде.

Рассмотрим работу устройства на примере вьделения максимального числа из 3, 5-разрядных двоичных чисел: 1) 01010, 2) 01101, 3) 00110.

При поступлении старших разрядов (О, О; О) анализируемых чисел на первые входы устройства на выходе

1218379

О рые поступают на входы элемента

ИЛИ 5 . На выходе элемента НЕ 9 формируется значение О, которое поступает на входы элемента ИЛИ 3 узлов анализа 1, 1, 1 >, и на выходах элементов И 4 этих узлов соответственно формируются значения 1, 1, О, которые поступают на входы элементов И 2 узлов анализа 1 „ 1, 1 .

На информационные входы этих узлов поступают третьи разряды анализируемых чисел: О, 1, 1. В соответствии с логикой работы этих узлов на выходах узлов 1>, Д 1, 1. будут значения О, 1, О, которые, поступая на входы элемента ИЛИ 5>, дадут на выходе 8 О, и соответственно на выходах элементов И 4 узлов анализа

1з, 1, у 1 - значения О, 1, О.

91

С учетом значений четвертых разрядов анализируемых чисел: 1, О, 1 и значений О, 1, О на соответствующих входах элементов И 2 узлов анализа

1 1 1 д з на выходах элемента

И 2 этих узлов сформируются: О, О, О, которые на выходе элемента 5 дадут значение 1, а на выходах элементов И блоков анализа 141 ° 142

1 — значения -О, 1, О. С учетом значений младших (пятых) разрядов анализируемых чисел: О, 1, О, поступающих на входы элементов 7,, 7, 7 на их выходах сформируются значения

О, 1, О, которые, поступая на соответствующие входы элемента ИЛИ 5 ,у

НЕ 9, дадут на его выходе значение О. Таким образом, на выходах устройства 84, ..., 8 будет сформирован код 10010, который является инверсным значением максимального

0110 1 из анализируемых чисел.

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

1О

tS

2S

Формула изобретения

Устройство для выделения экстре:мального из n, tn -разрядных двоичных чисел, содержащее щ, и -входовых элементов ИЛИ, щ х и узлов анализа, (i х j )-й узел анализа (где

=2, 3, ..., в — 1,j=1, 2, й) включает первый и второй элементы И, (rn xj )-й узел анализа содержит элемент И, причем первый вход первого элемента И (1 х )-ro u (ю х j )-го узлов анализа является входом соответствующегб разряда анализируемого числа устройства, а выход соединен с -м входом 1 -го и-входового элемента ИЛИ, о т л и— ч а ю щ е е с я тем, что, с целью упрощения устройства, оно содержит ю элементов НЕ, в каждый (f x j )-й узел анализа введен элемент ИЛИ, каждый (1 х j )-й узел анализа содержит элемент ИЛИ, выход которого соединен с вторым входом первого элемента И (2 х j )-го узла анализа, первый вход элемента ИЛИ (1 х j )-ro узла анализа подключен к входу первого разряда j -ro анализйруемого числа устройства, в (i x j) -м узле анализа вьйсод первого элемента И соединен с первым входом элемента

ИЛИ, выход которого соединен с первым входом второго элемента И, второй вход которого объединен с вторым входом первого элемента И, а выход соединен с вторым входом первого элемента И ((I + 1) xj) -го узла анализа, выход q -го g - входового эле-, мента ИЛИ через соответствующий элемент НЕ соединен с вторыми входами элементов ИЛИ соответственно (1 х 1 ) -ro и (1 х j )-ro узлов анали» за, выходы элементов НЕ являются выходами соответствующих разрядов экстремального числа устройства.

1218379

Продолжение таблицы

0

0

Аюн Юпт

Составитель В.Смирнов

Редактор H.Áàíäóðà Техред А.Комарницкая Корректор Г.Решетник

Тираж б71 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д. 4/5

Заказ 1112

Филиал ПНП "Патент", г. Ужгород, ул. Проектная, 4

П р и м е ч а н и е. Ситуация на входах узла, указанная в строке 8, является невозможной (не бывает).