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

 

1. УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ МАКСИМАЛЬНОЙ ПОСЛЕДОВАТЕЛЬНОСТИ ИЗ nm-РАЗРЯДНЫХ ДВОИЧНЫХ ЧИСЕЛ, содержащее П трехвходовых элементов И, ц элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, П триггеров, ц -входовый элемент ИЛИ, причем шина тактовых импульсов соединена с первыми входами трехвходовых элементов И, вторые входы которых подключены к шинам соответствуюиих сравниваемых последовательностей, выход ц -входового элемента ИЛИ соединен с первыми входами элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, выходы которых соединены с входами установки в ноль соответствующих триггеров, выходы которых соединены с третьими входами соответствующих трехвходовых элементов И, входы установки в единичное состояние всех триггеров подключены к шине начальной установки устройства, отличающее с я тем, что, с целью расширения области его применения, в него введены компараторный переключатель , регистр и m -разрядный сдвиговьш регистр, причем выходы трехвходовых элементов И соединены . с вторыми входами соответствующих элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, выход которого соединен с первым входом компараторного переключателя, второй вход которого соединен с выходом m -разрядного сдвигового регистра, вход которого подключен к информационному выходу компараторного переключателя, управляющий выход которого подключен к входу разрешения записи региЬтра, входы разрядов которого соединены с выходами соответствующих триггеров , вход управления сдвигом Ш -разрядного сдвигового регистра соединен с шиной сигналов сдвига устройства , входы установки в нулевое состояние регистра и т -разрядного регистра сдвига подключены к шине начальной установки устройства. 2. Устройство по П.1, отличающееся тем, что компараторный переключатель содержит элементы И, ИЛИ, НЕ, ИСКЛЮЧАЮЩЕЕ ИЛИ, СО элементы задержки, триггеры, приat чем первый и второй входы.компара торного переключателя через элемент IX) задержки соединены с первыми вхо30 дами первого и второго элементов И и с входами элемента ИСКЛЮЧАЮЩЕЕ о . ИЛИ, выход которого подключен к входу установки в ноль первого триггера , выход которого соединен с первым входом третьего элемента И, второй вход последнегосоединен с первым входом компараторного переключателя , третий вход через элемент НЕ - с вторым входом компа раторного переключателя, а выход с входом установки в ноль второго

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

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

1ЕСПжЛИК (1% (11) зш G 06 F 7/02 (21) 3561079/18- 24 (22) 03.03.83 (46) 07.06.84. БюлМ21 (72) P.М. Паленичка (71) Физико-механический институт им. Г.В. Карпенко (53) 681 ° 325(088.8) (56) 1. Авторское свидетельство СССР

N840S84, кл. G 06 F 7/02, 1979.

2. Авторское свидетельство СССР 966690, кл. G 06 F 7/02, 1981 (прототип). (54)(57) 1. УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ МАКСИМАЛЬНОЙ ПОСЛЕДОВАТЕЛЬНОСТИ

ИЗ nm-РАЗРЯДНЫХ ДВОИЧНЫХ ЧИСЕЛ, содержащее 11 трехвходовых элементов

И, 11 элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, ll триггеров, и -входовый элемент ИЛИ, причем шина тактовых импульсов соединена с первыми входами трехвходовых элементов И, вторые входы которых подключены к шинам соответствующих сравниваемых последовательностей, выход g -входового элемента ИЛИ соединен с первыми входами элементов . ИСКЛЮЧАЮЩЕЕ ИЛИ, выходы которых соединены с входами установки в ноль соответствующих триггеров, выходы которых соединены с третьими входами соответствующих трехвходовых элементов И, входы установки в единичное состояние всех триггеров подключены к шине начальной установки устройства, о т л и ч а ющ е е с я тем, что, с целью расширения области его применения, в него введены компараторный переключатель, регистр и nl --разрядный сдвиговый регистр, причем выходы трехвходовых элементов И соединены с вторыми входами соответствующих элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, выход которого соединен с первым входом компараторного переключателя, второй вход которого соединен с выходом N -разрядного сдвигового регистра, вход которого подключен к информационному выходу компараторного переключателя, управляющий выход которого подключен к входу разрешения записи реги тра, входы разрядов которого соединены с выходами соответствующих триггеров, вход управления сдвигом 1п -разрядного сдвигового регистра соединен с шиной сигналов .сдвига устройст- Е ва, входы установки в нулевое состояние регистра и m -разрядного регистра сдвига подключены к шине С: начальной установки устройства.

2. Устройство по п.1, о т л ич а ю щ е е с я тем, что компараторный переключатель содержит элементы И, ИЛИ, НЕ, ИСКЛЮЧАЮЩЕЕ ИЛИ, элементы задержки, триггеры, причем первый и второй входы.компараторного переключателя через элемент задержки соединены с первыми входами первого и второго элементов И и с входами элемента ИСКЛЮЧАЮЩЕЕ

ИЛИ, выход которого подключен к входу установки в ноль первого триггера, выход которого соединен с первым входом третьего элемента И, второй вход последнего- соединен с первым входом компараторного переключателя, третий вход через элемент НŠ— с вторым входом компа. раторного переключателя, а выходс входом установки в ноль второго триггера, инверсный и прямой выходы которого соединены с вторыми. входами соответственно первого и второго элементов И, выходы которых соединены с входами элемента ИЛИ, 10966 ЗЗ выход которого является информационным выходом компараторного переключателя, инверсный выход второго триггера является управляющим выходом компараторного переключателя.

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

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

И, элемент HE и триггер Я .

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

Наиболее близким по технической сущности к предлагаемому является устройство для введения экстремального из и m -разрядных двоичных чисел, содержащее A N -разрядных регистров и групп элементов И, й1-входовые элементы ИЛИ, триггеры, элементы ИСКЛЮЧАЮЩЕЕ ИЛИ, и -входовой элемент ИЛИ, причем выходы регистров поразрядно соединены с первыми входами элементов И соответствующей группы, выходы которых соединены с входами соответствующего щ -входового элемента ИЛИ, входы установки триггеров в единицу — с входом сброса устройства, вторые входы одноименных элементов

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

М-входных элементов ИЛИ соединены с первыми входами соответствующих . элементов ИСКЛЮЧАЮЩЕЕ ИЛИ и с соответствующими входами П -входового элемента ИЛИ, выход которого соеди° нен с вторыми входами элементов

ИСКЛЮЧАЮЩЕЕ ИЛИ и является выходом кода экстремального числа устройства, выходы элементов ИСКЛЮЧАЮЩЕЕ

5 ИЛИ соединены с нулевыми входами соответствующих триггеров (2) .

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

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

"0 Цель изобретения — расширение области применения устройства за счет определения максимума группы последовательностей из 0 у -разрядных чисел . и уменьшение аппаратурных

25 затрат за счет исключения из известного устройства П g -разрядных регистров и и П -входовых элементов

ИЛИ.

Поставленная цель достигается

ЗО тем, что в устройство для определения максимальной последовательности из am -разрядных двоичных чисел, содержащее 11 трехвходовых элементов И, Il элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, 11 триггеров, 11 -входовый элемент

ИЛИ, причем шина тактовых импульсов соединена с первыми входами трехвходовых элементов И, вторые входы которых подключены к шинам соответст40 вующих сравниваемых последовательностей, выход I) -входового элемента

ИЛИ соединен с первыми входами элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, выходы которых соединены с входами установки в ноль

4 соответствующих триггеров, выходы ко1096638

Компараторный переключатель содержит элементы И, ИЛИ, НЕ, ИСКЛЮЧАЮЩЕЕ ИЛИ, элементы задержки, триггеры, причем первый и второй входы компараторного переключателя через элементы задержки соединены с первыми входами первого и второго элементов И и с входами элемента

ИСКЛЮЧАЮЩЕЕ ИЛИ," выход которого подключен к входу установки в ноль пер- 4р вого триггера, выход которого соединен с первым входом третьего элемента И, второй вход последнего соединен с первым входом компараторного переключателя, третий вход через 4S элемент HE — с вторым входом компараторного переключателя, а выход— с входом установки в ноль второго триггера, инверсный и прямой выходы которого соединены с вторыми входами соответственно первого и второго элементов И, выходы которых соединены с входами элемента ИЛИ, выход которого является информационным. выходом компараторного переключателя, инверсный выход второго триггера является управляющим выходом компараторного переключателя. торых соединены с третьими входами соответствующих трехвходовых элементов

И, входы установки в единичное состояние всех триггеров подключены к шине начальной установки устройства, введены компараторный переключатель, регистр и N -разрядный сдвиговый регистр, причем выходы трехвходовых элементов И соединены с вторыми входами соответствующих элементов ИСК- 10

ЛЮЧАЮЩЕЕ ИЛИ, выход которого соединен с первым входом компараторного переключателя, второй вход которого соединен с выходом 1П -разрядного сдвигового регистра, вход 15 которого подключен к информационному выходу компараторного переключателя, управляющий выход которого подключен к входу разрешения записи регистра, входы разрядов которого соединены с выходами соответствующих триггеров, вход управления сдви. гом . N -разрядного сдвигового регистра соединен с шиной сигналов сдвига устройства, входы установки 25 в нулевое состояние регистра и

m-разрядного регистра сдвига подключены к шине начальной установки устройства.

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

Устройство содержит р трехвходовых элементов И 1, g --входовый элемент ИЛИ 2, и -элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 3, 11 триггеров 4, компараторный переключатель 5, П1 -разрядный сдвиговый регистр 6, регистр 7 для хранения кода номера максимального числа, шину 8 управления.

Компараторный переключатель содержит две входные шины 9 и 10, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ 11, триггер

12, элемент НЕ 13, трехвходовый элемент И 14, триггер 15, элементы И 1б и 17, элементы 18 задержки, две выходные шины 19 и 20, элемент ИЛИ 2t.

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

Перед началом поступления на вход устройства кодов сравниваемых чисел а,,а выполняется начальная установка устройства — установка в "1" триггеров 4, установка в "0" регистров 6 и 7. При одновременной подаче на вход элементов И 1 управляющих тактовьм импульсов из шины 8 и битов входных чисел, начиная со старшего разряда, через элементы И t будут проходить сигналы тех битов чисел, соответствующие триггеры которых находятся в состоянии " 1". Если на вход и -входового элемента ИЛИ 2 поступают коды чисел, в которых хотя бы в одном из данных разрядов есть " 1", то на выходе элемента ИЛИ

2 будет сигнал " 1", который подается на второй вход элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 3, на первый вход которого поступает сигнал из выхода элемента И 1. Тогда на выходах элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 3 будет сигнал

" 1" для кодов чисел с нулевым битом . в данном разряде, который изменит состояние триггера из " 1" в состояние "0", Таким образом, исключаются из дальнейшего поиска числа, если соответствующие им триггеры находятся в состоянии "0". С выхода элемента ИЛИ 2 последовательно поступают значения разрядов максимума, последовательности чисел а,...а„, начи1

° ° ° ц ф ная со старшего разряда, на первый вход компараторного переключателя.

Одновременно на второй вход компараторного переключателя поступают

1096638

Первый случай.Код числа на входе

9 больше кода числа на входе 10.

В этом случае при первом неравенстве битов чисел на входе трех45 входового элемента И 14 будут три равных сигнала, соответствующие

"1", так как сигнал "0" на входе

10 инвертируется элементом HE 13.

Тогда на выходе элемента И 14 будет сигнал "1", который изменит состоя-. ние триггера 15 из " 1" в состояние

"0". Сигнал "1" из инверсного выхода триггера 15 подается на второй вход элемента И 16, на первый вход которого через элемент задержки подается сигнал "1" из входной шины 9. Тогда на выходе элемента

И 16 будет сигнал "1". Соответстразряды максимума предыдущей по1-f 1-( следовательности чисел а,...а

1 начиная со старшего разряда, из сдвигового регистра 6 путем подачи управляющих сдвиговых импульсов 5 нз шины 8, Компараторный переключатель 5 выполняет побитное сравнение входных чисел и выдает на младший разряд сдвигового регистра биты большего из двух сравниваемых чисел. 10

Если максимум. текущей последовательности чисел a a„ больше максимума

0 предыдущей последовательности еак чисел, то в регистр 6 записывается

g и на втором выходе компараторmqx ного переключателя 5 будет сигнал

"1", который подается на управляющий вход записи регистра 7 для запиои содержимого триггеров 4, т.е. номера

20 максимума последова. ельности а,...а„ 20

Если максимки тек ятей последователь-. ности а, меньше или. равен макси àк ,муму предыдущей последовательности а„",м Ф то в регистр 6 побитно пе. репишется его содержимое, т.е. 25

1-1

Рmax °

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

Компараторный переключатель ра-. ботает следующим образом, Перед началом сравнения чисел выполняется установка триггеров 12 35 и .15 в состояние "1™. На входные шины 9 и 10 поступают биты вход-. ных чисел, начиная со старшего разряда. Рассмотрим три возможньи случая. 40 венно,на выходе элемента И 17 в этом случае будет сигнал "0" и на вьиоде элемента ИЛИ 21 будет сигнал " 1". Из входов 9 и 10 входные сигналы поступают на элемент

ИСКЛЮЧАЮЩЕЕ ИЛИ 11, на выходе которого в этом случае при первом неравенстве входных сигналов будет сигнал "1", который изменит состояние триггера 12 иэ "1" в состояние

"0". Тогда на выходе элемента И 14 будет сигнал "0" для всех остальных битов сравниваемьи чисел, так как íà его вход из триггера 12 поступает сигнал "0". Это значит, что на выходной шине 19 компараторного переключателя будут сигналы, соответствующие значениям битов числа на входе 9, т.е. код большего числа из двух сравниваемых чисел.

Второй случай. Коды чисел на входных шинах 9 и 10 равны.

В этом случае состояние триггеров 12 и 15 не изменяется и на выходной шине 19 компараторного переключателя будут последовательно биты числа на входной шине 10, так как для всех битов сравниваемых чисел на выходе элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 11 будет сигнал "0".

Третий случай. Код числа на входе 10 больше кода числа на входе 9.

В этом случае при первом неравенстве битов сравниваемьи чисел на выходе элемента ИСКЛЮЧАЮЩЕЕ ИЛИ

11 будет сигнал "1", который изменит состояние триггера 12 из

"1" в "0". Тогда при всех значениях битов сравниваемых чисел на выходе элемента И 14 будет сигнал "0" ко1 торый не изменит состояние триггера

15, Это значит, что на выходной шине 19 будут последовательно появляться биты числа на входной шине

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

"1", если код числа на входной шине

9 больше кода числа на входной шине

10.

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

В известном устройстве для вьщеления экстремального иэ ll и! -разрядных двоичных чисел выполняется вьщеле1096638 ние экстремального числа из одной последовательности из пщ -разрядных чисел. Предлагаемое устройство выполняет выделение максимума груп" пы последовательностей, каждая из которых состоит иэ Р и) -разрядных чисел, путем запоминания максимума предыдущей последовательности в

:В-разрядном сдвиговом регистре и его побитного сравнения с максимальным элементом текущей последовательности из A m-разрядных чисел с помощью компараторного переключателя. Если максимум текущей последовательности больше максимума предыдущей последовательности, то он записывается в Ю -разрядный сдвиговый регистр. Эта процедура продолжается до тех пор, пока не будут проанализированы все заданные последовательности из Р а -разрядных двоичных чисел.

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

3m -разрядных двоичных чисел, эта последовательность разделяется на

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

Т, за которое должен быть выполнен поиск максимума последовательности из 1 -разрядных чисел, а время параллельного вычисления максимума в прототипе равно t, то при использовании предлагаемого устройства получаем экономию в аппаратурных затратах в КТ/ t раз эа счет уменьшения в К раз числа параллельных входов устройства и, следовательно, уменьшения в К раз элементов И 1,триггеров 4 и элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 3.

1096638

Составитель Е .. Иванова

Редактор С. Пекарь Техред Т.Маточка Корректор А. Тяско

Заказ 3826/36 Тираж 699 Подписное

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

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

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