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

 

ОП ИСАНИЕ

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

Союз Советскнх

Социалистических

Республик

< ю>1005030 (61) Дополнительное к авт. саид-ву (22) Заявлено 20.08. 81 (21)3327337/18-24 р М gN з с присоединением заявки М—

Государственный комитет .

СССР о делам изобретений: и открытий

G 06 F 7/02 (23) Приоритет (53) УДД.6 81. 325. 5

{088. 8) Опубликовано 1503,83. Бюллетень Йо 10

Дата опубликования описания 15.0383 (72) Авторы изобретения

Е.A.Áðàòàëüñêèé, .В.М.Златников и О.С.Миха (71) Заявитель (54) УСТРОЙСТВО ДЛЯ ВЫДЕЛЕНИЯ..ЭКСТРЕМАЛЬНОГО .

ИЗ и ЧИСЕЛ

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

Известно устройство для сравнения чисел, содержащее триггеры, элементы И, ИЛИ, шины управления и синхронизаций 1 1.

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

Наиболее близким к.предлагаеьЬму является устройство для выделения экстремального из n m-разрядных двоичных чисел, содержащее л регистров, хранящих rn †.разрядные двоичные коды сравниваемых чисел, те -входовых элементов ИЛИ,ПВ -входовых элементов

ИЛИ, m-и трехвходовых элементов И, извходных шин для подачи управляющих сигналов и выходные шины. Прямые выхо:ды регистров поразрядно соединены с входами и -входовых элементов ИЛИ, инверсными выходы каждого регистра соединены с первым входом соответствующих элементов И, второй и третий в оды которых поразрядно соединены с входными шинами управляющих сигналов и с выходами и -входовых элементов

ИЛИ соответственно. Выходы П -входовых элементов ИЛИ соединены также с соответствующими выходными шинами устройства., а выходы элементов И каждого регистра соединены с входа 0 ми тп -входовых элементов ИЛИ, выходы которых подключены к соответству.ющему выходу устройства 2.g.

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

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

i -го элемента И, каждый 1 -й выход регистра маски подключен к первому входу (+и)-го элемента И, вторые входы 1,2,..., и -ro элементов И соединены с первым входом записи устройства, вторые входы (и+1), (n+2), ...,2n-ro элементов И подключены к второму входу записи устройства, выходы каждого i — го и (i+и)-ro элемен:,тов И соединены с входами i -го эле- 30 мента !!ЛИ, выход каждого i-ro элемента ИЛИ подключен к 1-му входу регистра, -й выход которого соединен с вторым входом !-го управляющего элемента И и с i-м входом узла анализа, первый вход записи устройства подключен к управляющему входу регистра результата.

Кроме того, узел анализа содержит элементы И, ИЛИ, ИЛИ-НЕ, элементы запрета, причем первый вход узла соединен с первым входом первого элемента ИЛИ-НЕ и первыми инверсными входами первого, второго, третьего и четвертого элементов запрета, выходы которых подключены к входам первого элемента ИЛИ, второй вход узла соединен с вторым входом первого элемента ИЛИ-НЕ и с пряьым входом первого элемента запрета, третий вход узла подключен к первому входу второго элемента ИЛИ и к вторым инверсным входам второго, третьего и четвертого элементов запрета, четвертый вход узла соединен с вторым входом второго элемента HJIH и с пряьым входом. 35 второго элемента запрета, пятый вход узла подключен к первым входам второго и третьего элементов ИЛИ-НЕ и к третьим инверсным входам третьего и четвертого элементов запрета, щес- 40 то вход узла соединен с вторыми входами второго и третьего элементов

ИЛИ-НЕ и прямым входом третьего элемента запрета, седьмой вход узла подключен к третьему входу второго элемента ИЛИ-НЕ, к первому входу третьего элемента ИЛИ и к четвертому инверсному входу четвертого элемента запрета, восьмой вход узла соединен с четвертым входом второго элемента

ИЛИ, с вторым входом третьего элемента ИЛИ и с прямым входом четвертого элемента запрета, выходы первого элемента ИЛИ-НЕ и второго элемента

ИЛИ подключены к первому и второму входам первого элемента И соответственно, выходы третьего элемента

ИЛИ-НЕ и третьего элемента ИЛИ соединены с первым и вторым входами второго элемента ИЛИ соответственно, выходы первого и второго элемен-, 60 тов И подключены к входам четвертого элемента ИЛИ.

На фиг. 1 приведена блок-схема устрой ств а; на фиг. 2 — пример реалиэ ации узла анализа. 65

Устройство содержит и входных кольцевых регистров 1„,12,..., 1д, и управляющих элементов !! 21, 2

2„, 2п блокирующих элементов И

32,..., 3п, регистр 4 маски, зле= мент ИЛ!! 5, регистр б, узел 7 анализа,регистр 8 результата, и элементов

ИЛИ 9!,9g, ..., 9„, входы 10 и 11 записи, выходы 12 и 13 устройства, установленные входы 14.

Узел 7 анализа содержит элемент

ИЛИ-НЕ 15, элементы ИЛИ-НЕ 16, элементы ИЛИ 17 и 18, элементы ИЛИ 19 и

20, элемент ИЛИ-HE 21, элементы 2225 запрета, элементы Й 26 и 27, входы 28 узла анализа.

На фиг.2 дан пример выполнения узла 7 анализа, обеспечивающего выделение и кодирование первой едини цы. Эта схема построена на стандартных функциональных логических элементах И,ИЛИ, ИЛИ-НЕ..

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

В исходном состоянии во входных кольцевых Регистрах 11,1 2,...,1 находятся сравниваемые коды, а .Регистр маски, регистр фиксации экстремума и регистр результата обнулены.

В начале цикла выделения экстремума по установочным входам 14 в регистр

4 маски записывается код количества сравниваемых чисел, который может определяться типом задачи, выполняемой ЭВМ, в состав которой входит предлагаемое устройство, или результатом проверки работы регистров,т.е. если один из входных регистров 1 неисправен, то с помощью кода, принятого в регистр маски, можно исключить данный регистр из рассмотрения. При поступлении по входу 11 записи управляющего сигнала в регистр 6 с выхода элементов И 3 перезаписывается содержимое регистра маски. Далее, при поступлении по входу 10 записи другого управляющего сигнала начинается процесс поразрядного (начиная со старшего разряда ) сравнения чисел. Если в

j-ом разряде (j =1,2,...,!!!) входных кольцевых регистров 14 присутствуют все единицы или единицы и нули, то управляющий сигнал на выходе элемента ИЛИ 5 равен единице, и информация

) — го сигнала входных регистров принимается в регистр 6, причем если в

j-é разряд регистра б в 1-м такте принялся нуль, то в (! +11-м и в последующих тактах сравнения в j-м разряде регистра б будет нуль, так как 1-й выход регистра б соединен с входом элемента И и запирает его.Если же в 1-ом разряде регистров 11, 1, ..., 1, все нули, то управляющий сигнал на выходе элемента ИЛИ 5 равен нулю, приема информации в регистр б в этом такте не происходит, и в ре1005030 гистре 6 сохраняется результат предндушего(1-1)-го такта сравнения. дале происходит сравнение (j+1) — га разряда и т.д. С выхода элемента ИЛИ 5 информация каждый такт поступает на вход последовательного приема инфор- 5 мации регистра 8 результата. Длительность управляющего сигнала, поданного по входу 10 записи, составляет и> тактов и определяется разрядностью сравниваемых чисел. По истечении m тактов управляющий сигнал па входу

10 записи снимается, и сравнение за— канчивается.

После окончания сравнения в регистре 6 фиксации экстремума присутствуют единицы в тех разрядах, которые соответствуют номерам входных регистров, хранящих экстремальное число. На выходах узла 7 анализа происходит выделение и кодирование "ле--вой" единицы, соединенных с выходными шинами 13 кода номера регистра, где находится код первого по порядку номера регистра, хранящего экстремальное число. На выходах регистра 8 результата, соединенных с выходными

4инами 12 кода экстремума, находится код экстремального числа.

Рассмотрим работу устройства на конкретном примере. Предположим, надо выделить максимальное из восьми

16-разрядных чисел, Все восемь входных регистров исправны, поэтому в восьми разрядах регистра 4 маски записаны единицы. При подаче управляющего сигнала по входу 11 записи мас- 35 ка п резаписывается в регистр 6. Далее, при подаче управляющего сигнала по входу 10 записи начинается поразрядное сравнение. Пусть максимальные числа находятся во втором и в пятом 40 входных регистрах. После 16 тактов сравнения в регистре фиксации экстремума единицы остаются во втором и в пятом разрядах, т.е. в регистре 6 присУтствУет позиционный код 01001000 45

На выходе узла 7 анализа схемы выделения и кодирования "левой" единицы присутствует код 010, а на выходе регистра 8 результата — код максимального числа.

Количество аппаратуры, необходимое для решения этой задачи в устройствепрототипе, составляет: 8 входных регистров, 128 элементов И, 24 элемента ИЛИ. В корпусах микросхем серии

133 ("Логика")это составляет 160 кор-55 пусов.

В предлагаемом устройстве для решения этой задачи требуется 8 входных регистров, 24 элемента И, 1 элемент

ИЛИ, 1 регистр маски, 1 регистр фик- 60 сации экстремума и 1 регистр результата. В корпусах микросхем серии 133 это составляет 48 корпусов.

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

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

1. Устройство для выделения экстремальнога из и чисел, содержащее и входных кольцевых регистров, П управляющих элементов И, элемент ИЛИ, регистр результата, причем выход старшего разряда каждого i --го входного кольцевого .регистра соединен с первым входом i-го управляющего элемента И, где 3 =1,2,...,о, выход каждаго из которых подключен к i -му входу элемента ИЛИ, выход которого соединен с информационным входом регистра разультата, о т л и ч а ю щ е е с я тем, чта, с целью упрощения устройства, в нега введены 2п элементов

И, и элементов ИЛИ, регистр, регистр маски, узел анализа, выход каждого

1 га управляющего элемента И соединен с первым входам i†- ro элемента И, каждый 1-й выход регистра маски подключен к первому входу (n+ i)-го элемента И, вторые входы 1, 2, ..., n — га элементов И. соединены с первым входам записи устройства, вторые входы (и +1), (i>+2),...,2n-го элементов И . подключены к второму входу записи устройства, выходы каждого i-ro u (1 +n)-го элементов И соединены с входами i-го элемента ИЛИ, выход каждого i-го элемента ИЛИ подключен к

1 -му входу регистра, 1-й выход котарага соединен с вторым входам

1 -го управляющего элемента И и с

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

2. Устройство по п.1, о т л и ч аю щ е е с я тем, что в нем узел анализа содержит элементы И, ИЛИ, ИЛИ-ГЕ, элементы запрета, причем первый вход узла соединен с первым входом перво— го элемента ИЛИ-HE и первыми инверсными входами первого, второго, третьего и четвертого элементов запрета, выходы которых подключены к входам первого элемента ИЛИ, второй вход узла соединен с вторым входом первого элемента ИЛИ-НЕ и с прямым входом первого элемента запрета, третий вход узла подключен к первому входу второго элемента ИЛИ и к вторым инверсным входам .второго > третьего и четвертого элементов запрета, четвертый вход узла соединен с вторым входом второго элемента ИЛИ и с прямым входом второго элемента

1005030 IO запрета, пятый вход узла подключен к первым входам второго и третьего элементов ИЛИ-НЕ и к третьим инверсным входам третьего и четвертого элементов запрета, шестой вход узла соединей с вторыми входами второго и третьего элементов ИЛИ-НЕ и прявмм входом третьего элемента запрета, седьмой вход узла подключен к третьему входу второго элемента ИЛИ-НЕ, к первому входу третьего элемента

ИЛИ и к четвертому инверсному входу четвертого элемента запрета, восьмой .вход узла соединен с четвертым входом второго элемента ИЛИ, с вторым входом третьего элемента ИЛИ и с пря- 5 дым входом четвертого элемента эапрета, выходы первого элемента ИЛИ-НЕ и второго элемента ИЛИ подключены к первому и второму входам первого элемента И соответственно, выходы третьего элемента ИЛИ-НЕ и третьего элемента ИЛИ соединены с первым и вторым входамн второго элемента ИЛИ соответственно, выходы первого и второго элементов И подключены к входам четвертого элемента ИЛИ.

Источники информации, принятые во внимание при экспертизе

1. Авторское свидетельство СССР

9 798811, кл. G 06 F 7/02, 1979.

2. Авторское свидетельство СССР

9 514291, кл. G 06 F 7/02, 1973 (прототип).

1005030

Составитель В. Белкин

Редактор Л.Алексеенко Техред О.Неце

Корректор A. ференц

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

Заказ 1899/63 Тираж 704 Подписное

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

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