Устройство для выделения экстремального из @ чисел Советский патент 1983 года по МПК G06F7/02 

Изобретение относится к автома-Г тике и вычислительной технике, и может быть использовано при реализации технических средств для выделения экстремального из совокупности чисел. Известно устройство для сравнения чисел, содержащее триггеры,элементы И, ИЛИ, ишны. управления и синхронизации tilНедостатком известного устройства является отсутствие на его выходах кодов экстремального числа и но.мера регистра, хранящего экстремальное число. Наиболее близким к. предлагае1)му является устройство для выделения экстремального из n m-разрядных двоичных чисел, содержащее n регистров хранящих m-разрядные двоичные коды сравнивэемлх чисел, тл-входовых элементов ИЛИ,грг -входовых элементо ИЛИ,т«п трехвходовых элементов И, mвходных шин для подачи управляющи сигналов Ивыходные ишны. Прямые вы ;ды регистров поразрядно соединены с входами n -входовых элементов ИЛИ, инверснь выходы каждого регистра соединены с первым вхоДом соответствующих элементов И, второй и трет Входы которых поразрядно соединены с входными шинами управляющих сигналов и с выходами n -входовых элементов ИЛИ соответственно. Выходы n -входовых элементов ИЛИ соединены также с соответствующими выходными шинами устройства,, а выходы элементов И каждого регистра соединены с входами т-входовых элементов ИЛИ, выходы которых подключены к соответствующему выходу устройства t2-. Цель изобретения заключается в упрощении устройства. Поставленная цель достигается тем, что в устройство для выделения экстремального числа из n чисел, содер7 жащее n входных кольцевых регистров, И управляющих элементов И, элемент ИЛИ, регистр результата, причем выход старшего разряда каждого -го входного кольцевого регистра соединён с первым входом f-ro управляющего элемента И, где i 1/2,. ..n р выход каждого из KOTojAax подключен к i-му- входу элемента ИЛИ, выход которого соединен с информационным входом регистра результата, введе- ны 2n элементов И, n элементов ИЛИ, регистр, регистр маски, узел анализа выход каждого i-го управляющего элемента И соединен с первым входом т-го элемента И, каждый f-и выход регистра маски подключен к первому входу (i + n)-ro элемента И, вторые входы 1,2 ,. . . , п -го элементов И сое динены с первым входом записи устройства, вторые входы (.n+lj, (п+2), ...,2п-го элементов И подключены к второму входу записи устройства, вы ходы каждого i-го и (i+п)-го элемен jTOB И соединены с входами i -го эле мента ИЛИ, выход каждого i-ro элемента ИЛИ подключен к 1-му входу ре гистра, i-и выход которого соединен с вторым входом -t-ro управляющего элемента И и с i-м входом узла анализа, первый вход записи устройства подключен к управляющему входу регистра результата. Кроме того, узел анализа содержи элементы И, ИЛИ, ИЛИ-НЕ, элементы запрета, причем первый вход узла соединен с первым входом первого эл мента ИЛИ-НЕ и первыми инверсными входами первого, второго, третьего и четвертого элементов запрета, выход которых подключены к входам первого элемента ИЛИ, второй вход узла соед нен с вторым входом первого элемента ИЛИ-НЕ и с прямым входом первого .элемента запрета, третий вход узла подключен к первому входу второго элемента ИЛИ и к вторым инверсным входам второго, третьего и четверто элементов запрета, четвертый вход узла соединен с вторым входом второго элемента ИЛИ и с прямым входом. второго элемента запрета, пятый вход узла подключен к первым входам второго и третьего элементов ИЛИ-НЕ и к третьим инверсным входам третьего и четвертого элементов запрета, шеето1 вход узла соединен с вторыми входами второго и третьего элементов ИЛИ-НЕ и прямым входом третьего элемента запрета, седьмой вход узла под ключен к третьему входу второго элемента ИЛИ-НЕ, к первому входу третье го элемента ИЛИ и к четвертому инверсному входу четвертого элемента запрета, восьмой вход узла соединен с четвертым входом второго элемента ИЛИ, с вторым входом третьего элемен та ИЛИ и с прямым входом четвертого элемента запрета, выходы первого элемента ИЛИ-НЕ и второго элемента ИЛИ подключены к первому и второму входам первого элемента И соответственно, выходы третьего элемента ИЛИ-НЕ и третьего элемента ИЛИ соединены с первым и вторым входами второго элемента ИЛИ соответственно, выходы первого и второго элементов И подключены к входам четвертого элемента ИЛИ, На фиг. 1 приведена блок-схема устройства-, на фиг. 2 - пример реализации узла анализа. Устройство содержит п входных кольцевых регистров 1,12,..., Ip/ П управляющих элементовИ 2, 20, ... 2, 2р блокирующих элементов И 3, 32,..., 3п, регистр 4 маски, элемент ИЛИ 5, регистр 6, узел 7 анализа, регистр 8 результата, п элементов ИЛИ 9-,,9 2, ..., 9п, входы 10 и 11 записи, выходы 12 и 13 устройства, установленные входы 14. . Узел 7 анализа содержит элемент ИЛИ-НЕ 15, элементы ИЛИ-НЕ 16, элементы ИЛИ 17 и 18, элементы ИЛИ 19 и 20, элемент ИЛИ-НЕ 21, элементы 2225 запрета, элементы И 26 и 27, входы 28 узла анализа. На фиг.2 дан пример выполнения узла 7 анализа, обеспечивающего вы.деление и кодирование первой единиЬы. Эта схема .построена на стандартных функциональных логических элементах И, ИЛИ, ИЛИ-НЕ., Устройство работает следующим образом. В исходном состоянии во входных кольцевых регистрах 1., ,1 2 .. . ,1 ц находятся сравниваемое коды, а рег-истр маски, регистр фиксации экстремума и регистр результата обнулены. В начале цикла выде:ления экстремума по установочным входам 14 в регистр 4 маски записывается код количества сравнивaet e x чисел, который может определяться типом задачи, выполняемой ЭВМ, в состав которой входит предлагаемое устройство, или результатом проверки работы регистров,т.е. если один из входных регистров. 1 -неисправен, то с помощью кода, принятого в регистр маски, можно исключить данный регистр из рассмотрения. При поступлении по входу 11 записи управляющего сигнала в регистр 6 с выхода элементов И 3 перезаписывается содержимое регистра маски. Далее, при поступлении по входу 10 записи другого управляющего сигнала начинается процесс поразрядного (начиная со старшего разряда ) сравнения чисел. Если в J-OM разряде (,j 1,2 ,... ,ТП) входных кольцевых регистров 1 присутствуют все единицы или единищл и нули, то управляющий сигнал на выходе элемента ИЛИ 5 равен единице, и информация j-ro сигнала входных регистров принимается в регистр б, причем если в j-й разряд регистра 6 в i-м такте принялся нуль, то в (J+1)-м и в последующих тактах сравнения в i-м разряде регистра 6 будет нуль, так как i-и выход регистра 6 соединен с входом элемента И и запирает его.Если же в J-OM разряде регистров 11,, 12, . . . , 1, все нули, то управляющий сигнал на выходе элемента ИЛИ 5 равен нулю, приема информации в регистр 6 в этом такте не происходит, и в регистре б сохраняется результат предндушёго(j-l)-ro уакта сравнения. Далее происходит сравнение (j+l)-ro разряда и т.д. С выхода элемента ИЛИ 5 информация каждый -такт поступает на вход последовательного приема информации регистра 8 результата. Длительность управляющего сигнала, поданного по входу 10 записи, составляет m тактов и определяется разрядностью сравниваемых чисел. По истечении т тактов управляющий сигнал по входу 10 записи снимается, и сравнение заканчивается.

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

Рассмотрим работу устройства на конкретном примере. Предполо5: им, надо выделить максимальное из восьми 16-разрядных чисел. Все восемь входных регистров исправны, поэтому в восьми разрядах регистра 4 маски записаны единицы. При подаче управляющего сигнала по входу 11 записи маека перезаписывается в регистр б. Далее/ при подаче управляющего сигнала по входу 10 записи начинается поразрядное сравнение. Пусть максимальные числа находятся во втором и в пятом входНЕЛХ регистрах. После 16 тактов сравнения в регистре фиксации экстремума единицы остаются во втором и в пятом разрядах, т.е. в регистре б присутствует позиционный код 01001000 На выходе узла 7 анализа схемы выделения и кодирования левой единицы присутствует код 010, а на выходе регистр 8 результата - код максимального числа.

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

В предлагаемом устройстве для решения этой задачи требуется 8 входны регистров, 24 элемента И, 1 элемент ИЛИ, 1 регистр маски, 1 регистр фиксации экстремума и 1 регистр результата. В корпусах микросхем серии 133 это составляет 48 корпусов.

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

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

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

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

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

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

1. Авторское свидетельство СССР 798811, кл. G Об F 7/02, 1979.

2. Авторское свидетельство СССР 514291, кл. G 06 F 7/02, 1973 (прототип) .

/л

1

1

n

Lr

сгпг

i ш И МЫ j

%

«JLI ь nil i II III iM«i ir iliii. . «J iL шяЛ

9i

Iff

i ТН

TIM

n

w

-ff.

11

3n

11

n

13

28

13

Риг.2