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

 

УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ .МАКСИМАЛЬНОГО ИЗ гт ДВОИЧНЫХ ЧИСЕЛ , содержащее гг групп элементов И по п-1 элементов И в каждой группе, где пчисло разрядов сравниваемых чисел, -tn групп элементов памяти по п элементов памяти в каждой группе, п многовходовых элементов ИЛИ анализа разрядов, m элементов ИЛИ обнуления , управляющие элементы И, регистр результата, причем прямой выход каждого i-ro элемента памяти группы, где i 1,2,...,r,k 1,2,...., m соединен с k-м входом i-ro элемента ШШ анализа разряда , выход которого подключен к первому входу .i-ro управляющего элемента И, выход которого соединен со входом установки в единичное состояние i-ro разряда регистра результата , выход j-ro управляющего элемента И, где j 1,2,...,ri-1 подключен к первым входам i-x элементов И всех групп, второй вход j-ro , элемента И 1с-й группы подключен к инверсному выходу j-ro элемента памяти k-й группы, выход (n-l)-ro элемента И группы соединен с первым входом k-ro элемента ИЛИ обнуления , выход которого подключен к входу установки в нулевое состояние h-ro элемента памяти k-й группы , отличающееся тем, что, с целью повышения быстродействия , в устройство введены п-1 элементов И обнуления, п-2 элементов И анализа разрядов, многовходовый элемент И и генератор импульсов , вход запуска которого подключен к входу запуска устройства, а выход соединен с вторыми входами всех управляющих элементов И, управляющим входом многовходового элемента И и инверсными входами всех i элементов И обнуления, прямой вход j-ro элемента И обнуления подключен, (Л к выходу j-ro разряда регистра резул тата , а выход соединен с первыми входами установки в нулевое состояние J-X элементов памяти всех групп, вторые входы установки в нулевое состояние элементов памя- , ти со второго по (п-1)-й груп 1 пы объединены и подключены к входу со установки в нулевое состояние п-го 4: элемента памяти k-й группы, выход р-го элемента И группы, где р 1,2,...,п-2, соединен с (р-«-1)-м оо входом k-ro элемента ИЛИ обнуления, выходы многовходовых элементов ШШ анализа разрядов подключены к инверсным входам многовходового элемента И, выход которого является выходом окончания поиска устройства, выход первого многовходового элемента ШШ анализа разрядов подключен к инверсному входу второго управляющего элемента И, первый инверсный вход р-го элемента И анализа разрядов подключен к выходу (р+1)-го мно

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

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

РЕСПУБЛИК (51)4 G 06 F 7/04

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

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

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 3697916/24-24 (22) 02 ° 12 ° 83 (46) 15.08.85. Бюл. № 30 (72) А.Н. Мурашко (53) 681.325.5 (088.8) (56) Авторское свидетельство СССР

¹ 514291, кл. G 06 F 7/02, 1973.

Авторское свидетельство СССР № 875376, кл. G 06 F 7/04, 1980. (54) (57) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ . ИАКСИИАЛЬНОГО Из rn ДВОИЧНЫХ ЧИСЕЛ, содержащее m групп элементов И по и-1 элементов И в каждой группе, где n — - число разрядов сравниваемых чисел, .tn групп элементов памяти по и элементов памяти в каждой группе, и многовходовых элементов ИЛИ анализа разрядов, rn элементов ИПИ обнуления, управляющие элементы И, регистр результата, причем прямой выход каждого i-ro элемента памяти

1 -й группы, где 1 = 1,2,...,n,k=

1,2,,..., ъ соединен с 1с -м входом ч-ro элемента ИЛИ анализа разряда, выход которого подключен к первому входу i-ro управляющего элемента И, выход которого соединен со входом установки в единичное состояние 1-ro разряда регистра результата, выход j-го управляющего элемента И, где j = 1 2 ï-1 подключен к первым входам i-x элементов И всех групп, второй вход j-го элемента И %-й группы подключен к инверсному выходу J-го элемента памяти %-й группы, выход (n-1)-го. элемента И 1 -й группы соединен с первым входом Ь-го элемента ИЛИ обнуления, выход которого подключен

„„SU„„ 17З4О8 к входу установки в нулевое состояние и-го элемента памяти k-й группы, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия, в устройство введены и -1 элементов И обнуления, -2 элементов И анализа разрядов, многовходовый элемент И и генератор импульсов, вход запуска которого подключен к входу запуска устройства, а выход соединен с вторыми входами всех управляющих элементов И, управляющим входом многовходового элемента И и инверсными входами всех элементов И обнуления, прямой вход -го элемента И обнуления подключен, к выходу -го разряда регистра ре1 эультата, а выход соединен с первыми входами установки в нулевое состояние >-х элементов памяти всех групп, вторые входы установки в нулевое состояние элементов памя- .ти со второго по (и-1)-й k-й группы объединены и подключены к входу установки в нулевое состояние и-го элемента памяти R-й группы, выход р-го элемента И 1<-й группы, где р =

1,2,...,п-2, соединен с (р+1)-м входом %-ro элемента ИЛИ обнуления, выходы многовходовых элементов ИЛИ анализа разрядов подключены к инверсным входам многовходового элемента И, выход которого является выходом окончания поиска устройства, выход первого многовходового элемента ИЛИ анализа разрядов подключен к инверсному входу второго управляю- . щего элемента И, первый инверсный вход р-ro элемента И анализа разрядов подключен к выходу (р+1)-ro мно1173408 говходового элемента ИЛИ анализа разрядов, второй инверсный вход первого элемента И анализа разрядов подключен к выходу первого многовходового элемента ИЛИ анализа разря1

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

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

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

Устройство содержит rn групп эле1 1 2 2 ментов И 1 12 ° ° ° ° 1»» 11 у I z >

2 m m 1 М

1 ......,, 1, 1,...,, . 1 „, rn — групп и 2 1 1

15 элементов памяти 2„, 2 .... 2„, 2 „, 2 )m

2 ..... °,2„.....2,2 .... ° .2„, и1 эле1 ментов ИЛИ 3",3,... ° .,3 обнуления, п- многовходовых элементов ИЛИ анализа разрядов 4,4 .....4„, управляющие элементы И 5„,5 ....5 » (и -2) ?О элементов И анализа разрядов 6„, 6 .....6„, вход 7 запуска устройства, генератор 8 импульсов, многовходовый элемент И 9, регистр 10 результата, (и-1) элементов И обнуления 11„, 11,,....11 и „,(n-1) выходы 12„, 12 ....12 „, элементов И

11 являются вторыми установками в нулевое. состояние j-ой группы элементов 2 > памяти, 13 — выход окон- 30 чания пойска устройства.

Назначение элементов устройства

1< следующее. Элементы 2„. памяти, где

1с = 1,2, ...) m) 1= 1,2,....,,n, и1количество анализируемых двоичных чисел, и- количество двоичных разрядов в числе, служат для временного хранения двоичных чисел. k -ая груп,па элементов И 1. и В-ый элемент ИЛИ

3 служат для выработки сигнала об- 40

1с нуления k-ой группы элементов 21 памяти. Если при стробировании сигналом с выхода элемента И 5 первого элемента И 1. в соответствующем %-ой

1 группе разряды двоичного числа, храдов, выход р-ro элемента И анализа разрядов соединен с третьим входом (P+2)-ro управляющего элемента И и вторым входом (р+1)-го элемента И анализа разрядов.

2 нимого в соответствующей ячейке памяти, имеют нулевое значение, то все элементы памяти, хранящих 1-ое число, обнуляются. Элементы ИЛИ 4 формируют сигналы разрешения, например "1",если хотя бы в одном из чисел анали.Ъ зируемого разряда в элементах 21 памяти присутствует "I".

Элементы И 5;, где i= 1,2,...,n, и элементы И 6, где р = 1,2,..., (и-2) служат для последовательного анализа разрядов всех чисел и соответствующего стробирования тех разрядов, которые содержат хотя бы в одном из чисел "1" в соответствуюцем разряде.

Элемент И 9 служит для выработки сигнала окончания операции поиска максимального числа на выходе 13 устройства, причем сигнал на выходе элемента И 9 появляется лишь при обнуленных состояниях всех элементов 2". йамяти, т.е. когда отсутству> ют сигналы разрешения с выходов элементов ИЛИ 4,, Элементы И 11, где 1= 1,2,......, Э (n-1) служат для выработки сигнала обнуления соответствующего разряда

1-ой группы элементов 2. памяти по

3 1! 11 ,окончанию такта перезаписи 1 состояния в регистр 10 результата.

Регистр 10 результата служат для формирования двоичного и-разрядного кода максимального из m двоичных чисел.

Генератор 8 импульсов служит для выработки тактов синхронизации, обес. печивающих последовательное формирование стробирующих импульсов при анализе разрядов чисел, начиная со старших разрядов. Запуск генератора 8 происходит по сигналу, поступающему на вход 7 запуска устройства.

i 173408

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

Перед началом работы в элементы 2 . памяти заносятся !!! двоичных

jc ! чисел, причем в первую группу элементов 2 памяти заносят все стар1 шие разряды тн двоичных чисел,далее в последующие группы заносятся все разряды чисел в порядке убывания старшинства разрядов, а в группе элементов 2 памяти заносятся

1< все младшие разряды rn двоичных чи-. сел. Регистр 10 результата обнуляется.

В устройство по входу 7 поступает сигнал начала операции, по которому осуществляется запуск генератора 8 импульсов. Генератор 8 импульсов вырабатывает серию импульсов стробирования для элементов И 5, элемента И 9, элементов И 11, причем сигналом разрешения для элементов И 5. и элемента И 9 является

1 сам тактовый импульс, а для элементов И 11 — отсутствие тактового им1 пульса на их первых входах.

В случае 1, если хотя бы в одном из элементов 2 памяти 1-ой k

1 группы, где 1= 1,2,.....,!!!, в старшем разряде записана "1", то сигнал через элемент ИЛИ 4 поступает на второй вход элемента И 5, разрешая

Э прохождение строб-импульса с генератора 8 импульсов. При этом сигнал поступает в регистр 10 результата и записывает в него "1" в этом разряде, а также этот сигнал поступает на вторые входы элементов И 1„ данного разряда. Если в 1-ом числе, 1 = 1,2,......rn этот разряд установлен в "0" состояние то с инверсного выхода элемента 2„ памяти снимается разрешающий потенциал, открывающий элементы И 1 и через эле1 1 мент ИЛИ 3 поступает сигнал установки в.нулевое состояние по первым

Ф входам элементов 2 памяти, в которых и хранится %-ое число. Данное число исключается из процесса поиска максимального из !!! двоичных чисел. По окончанию первого импульса . генератора 8 импульсов на первом входе элемента И 11„ появится сигнал разрешения, а поскольку по первому такту в старшем разряде регистра 10 уже записана "1", то срабатывает ,элемент И 11„ и на его выходе 12 появляется сйгнал установки в нулевое состояние всех старших разрядов элементов 2 памяти, т.е. проаналиЪ зированные разряды элементов 2, па1 1 ! мяти обнуляются.

В случае 2, когда исследуемые числа имеют нулевые значения в старшем разряде (! =1), то с выхода элемента ИЛИ 4 на второй вход эле1 !! Г! мента И 5„ поступает сигнал " Запре т, 1 О а н а третий вход элемента И 5 этот

z. сигнал уже разрешающий (по входу он инвертируется). При этом, если хотя бы в одном из чисел в следующем разряде (1=2) имеется ™1", то сра15 батывает элемент ИЛИ 4г, разрешая тем самым прохождение первого стробимпульса с генератора 8 через второй элемент И 5 . Срабатывает элемент И 5 и сигнал с его выхода г

2p . поступает в регистр 10 результата и записывает "1" в этом разряде, а

Э также на вторые входы элементов И 1

2! где k = 1,2,....!!!. Если в 1< ом числе данный разряд равен нулю то

25 с инверсного выхода элемента 2 пай мяти данного разряда снимается разрешающий потенциал, открывающий элемент И 1 и через элемент ИПИ 3 и

2 поступает сигнал установки в нулевое

30 состояние по первым входам элемен- . тов 2 памяти, в которых и хранится

k-oe число. Таким образом, уже первым строб-импульсом производится перезапись единичного значения после35 дующего Разряда в Регистр 10 Резуль, тата при наличии во всех самых старших разрядах (1=1) чисел нулевых значений. Обнуляются те элементы памяти тех чисел, которые не имели в данном стробируемом разряде "1"-ых значений как и в предыдущем случае.

По окончании строб-импульса происходит обнуление элементов памяти простробированного разряда всех

Б случае 3, когда и в старшем и .в последующих разрядах (! =1, !=2) во всех исследуемых числах только нулевые значения, то с выхода эле- ментов ИЛИ 4 и 4г постУпает запрет на вторые входы соответствующих элементов И 5„ и 5 . Эти самые

z сигналы с выходов элементов ИЛИ 4 ! и 4, например нулевого потенциала, уже вызывают срабатывание элемента ШИ 6„ за счет инверсии сигналов, поступающих на его входы. Разрешающни потенциал с выхода элемен1173408 та ИЛИ б разрешает срабатывание по

1 третьему входу элемента И 5 и по второму входу элемента И б . Далее, если хотя бы в одном из чисел следующий разряд (i =3) имеет значение

"1", то срабатывает элемент ИЛИ 4 и на второй вход .элемента И 5 постуз пает сигнал разрешения. Первым строб-импульсом происходит переза- !О пись "1" в соответствующий разряд регистра 10 результата, а также обнуляются все элементы памяти тех чисел, которые имели в этом (1=3) разряде нулевое значение как и в 15 предыдущих случаях. По окончанию строб-импульса с выхода 12 элемен3 та И 11з сигнал обнуляет. все элементы 2® памяти (=3). Аналогично з производится анализ и стробирование 20 последующих разрядов.

Далее производится анализ и стробирование последующих j-разрядов t< чисел, запись "1" в соответствующие разряды регистра 10 результата, если 25 хотя бы у одного анализируемого

j-разряда исследуемых 1 чисел была

"1". Если в k-ом числе данный 1-тый разряд имеет нулевое значение, то с инверсного выхода элемента 2" па- 30

3 мяти данного разряда поступает разрешение последовательно в соответствующем такте через элемент И

5, первый элемент И 1 элемент ИЛИ

А

3 " для установки в нулевое состоя- з5

% ние по первым входам элементов 2 . памяти, в которых хранилось k-oe число.. По окончанию стробимпульса происходит обнуление элементов памяти 2" простробированного 1-раэря- 1О

1 да всех N чисел.

Таким образом, осуществляется анализ значащих (ненулевых) разрядов чисел и перенос такта стробировання на первый значащий разряд,тем самым сокращается время формирования результата в регистре 10. Кроме того, в каждом такте еще выбывают из анализа все числа, имеющие в стробируемых разрядах нулевые значения, и обнуляются все проанализированные значащие разряды. Причем в каждом такте импульсов с генератора 8.импульсов производится опрос состояний всех разрядов всех чисел на "0". Если в хдде опроса элемента И 9 по его стробирующему входу поступит импульс в момент, когда выбыли из анализа все числа, а максимальное число имеет в оставшихся разрядах нулевое значение, то на выходе элемента И 9 формируется сигнал об окончании операции. Это позволяет досрочно определить максимальное число, при этом число N тактовых импульсов меньше количества h разрядов исследуемых чисел.В результате поиска по сигналу с выхода 13 устройства в регистре 10 сформированный двоичный код максимального из rq двоичных чисел может быть записан во внешнее устройство.

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

1173408 доходы

12n- f

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

 

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

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

Изобретение относится к электронной системе блокировки для контроля доступа к множеству ячеек

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

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

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

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