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

(56) 1. Авторское свидетельство СССР 9840884, кл. С Об Г 7/02, 1979.2. Авторское свидетельство СССР 9966690, кл, С 06 Р 7/02, 1981 (прототип).(54)(57) 1. УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ МАКСИМАЛЬНОЙ ПОСЛЕДОВАТЕЛЬНОСТИ ИЗ пт-РАЗРЯДНЫХ ДВОИЧНЫХ ЧИСЕЛ, содержащее 11 трехвходовых элементов И, 11 элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, П триггеров, и -входовый элемент ИЛИ, причем шина тактовых импульсов соединена с первыми входами трехвходовых элементов И, вторые входы которых подключены к шинам соответствующих сравниваемых последовательностей выход и -входового элемента ИЛИ соединен с первыми входами элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, выходы которых соединены с входами установки в ноль соответствующих триггеров, выходы которых соединены с третьими входами соответствующих трехвходовых элементов И, входы установки в единичное состояние всех триггеров подключены к шине начальной установки устройства, о т л и ч а ющ е е с я тем, что, с ширения области его при него введены компаратор чатель, регистр и щ -ра сдвиговый регистр, прич трехвходовых элементов с вторыми входами соответствующих элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, выход которого соединен с первым входом компараторного переключателя, второй вход которого соединен с выходом П 1 -разрядного сдвигового регистра, вход которого подключен к информационному выходу компараторного переключателя, управляющий выход которого подключен к входу разрешения записи регистра, входы разрядов которого соединены с выходами соответствующих триггеров, вход управления сдвигом 1 п -р рядного сдвигового регистра соединен с шиной сигналов .сдвига устройс ва, входы установки в нулевое состояние регистра и в -разрядного регистра сдвига подключены к шине начальной установки устройства.2. Устройство по п.1, о т л ич а ю е е с я тем что компа щ раторный переключатель содержит элементы И, ИЛИ, НЕ, ИСКЛЮЧАЮЩЕЕ ИЛИ, элементы задержки, триггеры, причем первый и второй входы.компараторного переключателя через элементзадержки соединены с первыми входами первого и второго элементов И и с входами элемента ИСКЛЮЧАЮЩЕЕ ф, ИЛИ, выход которого подключен к входу установки в ноль первого триг. гера, выход которого соединен с первым входом третьего элемента И, второй вход последнего соединен с первым входом компараторного переключателя, третий вход через элемент НЕ - с вторым входом компа раторного переключателя, а выходс входом установки в ноль второготриггера, инверсный и прямой выходы которого соединены с вторыми.входами соответственно первого ивторого элементов И, выходы которыхсоединены с входами элемента ИЛИ,10966 ЗЗ выход которого является инФормационным выходом компараторного переключателя, инверсный выход второготриггера является управляющим выходом компараторного переключателя.Изобретение относится к вычис- лительной технике и технической кибернетике и может быть использовано в системах корреляционного распознавания изображений или в устройствах распознавания одномерных сигналов.Известно устройство для определения максимального числа, содер" жащее элемент И и й узлов анализа, каждый из которых включает элементы И, элемент НЕ и триггер Я .Недостатком известного устройства является ограниченная область применения.Наиболее близким по техническойсущности к предлагаемому является устройство для введения экстремального из пан -разрядных двоичных чисел, содержащее П Ф -разрядных регистров и групп элементов И, й 1-входовые элементы ИЛИ, триггеры, элементы ИСКЛЮЧАЮЩЕЕ ИЛИ, и -входовой элемент ИЛИ, причем выходы регистров поразрядно соединены с первыми входами элементов И соответствующей группы, выходы которых соединены с входами соответствующего щ -входового элемента ИЛИ, входы установки триггеров в единицу - с входом сброса устройства, вторые входы одноименных элементов И всех групп соединены с соответствующими шинами управления поразрядным сравнением устройства, третьи входы элементов И каждой группы соединены с выходами соответствуюФщих триггеров и с выходами кода номера регистра, содержащего экстремальное число .устройства, выходы М-входных элементов ИЛИ соединены с первыми входами соответствующих . элементов ИСКЛЮЧАЮЩЕЕ ИЛИ и с соответствующими входами П -входового элемента ИЛИ, выход которого соеди нен с вторыми входами элементовИСКЛЮЧАЮЩЕЕ ИЛИ и является выходомкода экстремального числа устройства, выходы элементов ИСКЛЮЧАЮЩЕЕ 5 ИЛИ соединены .с нулевыми входамисоответствующих триггеров 2,Известное устройство, определяетэкстремум одной последовательностииз й двоичных чисел, но во многих 10 корреляционных устройствах распознавания изображений и одномерныхсигналов. Требуется определить эксремум группы последовательности чисел, каждая из которых поступаетпараллельно и содержит и двоичныхчисел. Известное устройствс обладаетбольшим быстродействием, но прибольшом п требует больших аппаратур.ных затрат."О Цель изобретения - расширение области применения устройства за счетопределения максимума группы последовательностей из О 1 -разрядныхчисел . и уменьшение аппаратурных 25затрат за счет исключения из известного устройства П М -разрядныхрегистров и П р -входовых элементовИЛИ. Поставленная цель достигается ЗОтем, что в устройство для определения максимальной последовательностииз па -разрядных двоичных чисел,содержащее Ь трехвходовых элементов И, й элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, З 5 11 триггеров, 11 -входовый элементИЛИ причем шина тактовых импульсовсоединена с первыми входами трехвходовых элементов И, вторые входыкоторых подключены к шинам соответст О вующих сравниваемых последовательностей, выход П -входового элементаИЛИ соединен с первыми входами элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, выходы которыхсоединены с входами установки в ноль 45 соответствующих триггеров, выходы ко20 Компараторный переключатель содержит элементы И, ИЛИ, НЕ, ИСКЛЮЧАЮЩЕЕ ИЛИ, элементы задержки, триггеры, причем первый и второй входы компараторного переключателя через элементы задержки соединены с первыми входами первого и второго элементов И и с входами элемента ИСКЛЮЧАЮЩЕЕ ИЛИ," выход которого подключен к входу установки в ноль пер вого триггера, выход которого соединен с первым входом третьего элемента И, второй вход последнего соединен с первым входом компараторного переключателя, третий вход через 45 элемент НЕ - с вторым входом компараторного переключателя, а выход - с входом установки в ноль второго триггера, инверсный и прямой выходы которого соединены с вторыми входами соответственно первого и второго элементов И, выходы которых соединены с входами элемента ИЛИ, выход которого является информационным. выходом компараторного переключате ля, инверсный выход второго триггера является управляющим выходом компараторного переключателя. торых соединены с третьими входами соответствующих трехвходовых элементов И, входы установки в единичное состояние всех триггеров подключены к шине начальной установки устройства введены компараторный переключатель, регистр и М -разрядный сдвиговый регистр, причем выходы трехвходовых элементов И соединены с вторыми входами соответствующих элементов ИСК ЛЮЧАЮЩЕЕ ИЛИ, выход которого сое" динен с первым входом компараторного переключателя, второй вход которого соединен с выходом В -разрядного сдвигового регистра, вход 15 которого подключен к инФормационному выходу компараторного переключателя, управляющий выход которого подключен к входу разрешения записи регистра, входы разрядов которого соединены с выходами соответствующих триггеров, вход управления сдви. гом, П -разрядного сдвигового регистра соединен с шиной сигналов сдвига устройства, входы установки 25 в нулевое состояние регистра и М-разрядного регистра сдвига подключены к шине начальной установки устройства. На фиг.1 изображена структурная схема предлагаемого устройства; на Фиг.2 - структурная схема компараторного переключателя.Устройство содержит р трехвходовых элементов И 1, 11 -входовый элемент ИЛИ 2, и -элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 3, 11 триггеров 4, компараторный переключатель 5, П -разрядный сдвиговый регистр 6, регистр 7 для хранения кода номера максимального числа, шину 8 управления.Компараторный переключатель содержит две входные шины 9 и 10, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ 11, триггер 12, элемент НЕ 13, трехвходовый элемент И 14, триггер 15, элементы И 1 б и 17, элементы 18 задержки, две выходные шины 19 и 20, элемент ИЛИ 2 1.Устройство работает следующим об" разом.Перед началом поступления на вход устройства кодов сравниваемых чисел а, ,ап выполняется начальная установка устройства - установка в "1" триггеров 4, установка в "0" регистров 6 и 7. При одновременной подаче на вход элементов И 1 управляющих тактовьм импульсов из шины 8 и битов входных чисел, начиная со старшего разряда, через элементы И 1 будут проходить сигналы тех битов чисел, соответствующие триггеры которых находятся в состоянии " 1". Если на вход и -входового элемента ИЛИ 2 поступают коды чисел, в которых хотя бы в одном из данных разрядов есть " 1", то на выходе элемента ИЛИ 2 будет сигнал " 1", который подается на второй вход элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 3, на первый вход которого поступает сигнал из выхода элемента И 1. Тогда на выходах элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 3 будет сигнал " 1" для кодов чисел с нулевым битом . в данном разряде, который изменит состояние триггера из " 1" в состояние "0", Таким образом, исключаются из дальнейшего поиска числа, если соответствующие им триггеры находятся в состоянии "О". С выхода элемента ИЛИ 2 последовательно поступают значения разрядов максимума, последовательности чисел а,а, начиная со старшего разряда, на первый вход компараторного переключателя. Одновременно на второй вход компараторного переключателя поступают30 Первый случай.Код числа на входе 9 больше кода числа на входе 10.В этом случае при первом неравенстве битов чисел на входе трех 45 входового элемента И 14 будут три равных сигнала, соответствующие "1", таккак сигнал "0" на входе 10 инвертируется элементом НЕ 13. Тогда на выходе элемента И 14 будет сигнал "1", который .изменит состоя-. 50 ние триггера 15 из " 1" в состояние "0". Сигнал "1" из инверсного выхода триггера 15 подается на второй вход элемента И 16, на первый вход которого через элемент задержки подается сигнал "1" из входной шины 9. Тогда на выходе элемента И 16 будет сигнал "1". Соответстразряды максимума предыдущей по 11следовательности чисел а ,аначиная со старшего разряда, изсдвигового регистра 6 путем подачиуправляющих сдвиговых импульсов 5нз шины 8, Компараторный переключатель 5 выполняет побитное сравнение входных чисел и выдает на младший разряд сдвигового регистра битыбольшего из двух сравниваемых чисел. 10Если максимум, текущей последовательности чисел а,больше максимумаО предыдущей последовательностиеакчисел, то в регистр 6 записываетсяО и на втором вьиоде компараторщахного переключателя 5 будет сигнал"1", который подается на управляющийвход записи регистра 1 для запиаи содержимого триггеров 4, т.е. номера20максимума последова.ельности а ,а 20Если максимум текаей последователь-,ности а, меньше или. равен макси"а х,муму предыдущей последовательностиа",х Ф то в регистр 6 побитно пе. репишется его содержимое, т.е. 251а махПеред поступлением на вход устройства кодов чисел каждой новойпоследовательности из п чисел выполняется установка триггеров 4в состояние "1".Компараторный переключатель ра-.ботает следующим образом,Перед началом сравнения чиселвыполняется установка триггеров 12и .15 в состояние "1". На входныешины 9 и 10 поступают биты вход-.ных чисел, начиная со старшего разряда. Рассмотрим три возможныхслучая. 40 венно,на выходе элемента И 11в этом случае будет сигнал "0"и на вьиоде элемента ИЛИ 21 будетсигнал " 1". Из входов 9 и 10 входные сигналы поступают на элементИСКЛЮЧАЮЩЕЕ ИЛИ 11, на выходе которого в этом случае при первомнеравенстве входных сигналов будетсигнал "1", который изменит состояние триггера 12 иэ "1" в состояние"0". Тогда на выходе элемента И 14будет сигнал "0" для всех остальных битов сравниваемьичисел, таккак на его вход из триггера 12поступает сигнал "0". Это значит,что на выходной шине 19 компараторного переключателя будут сигналы,соответствующие значениям битов числа на входе 9, т.е. код большего чис.ла из двух сравниваемых чисел.Второй случай. Коды чисел навходных шинах 9 и 10 равны.В этом случае состояние тригге"ров 12 и 15 не изменяется и на выходной шине 19 компараторного переключателя будут последовательнобиты числа на входной шине 10,так как для всех битов сравниваемьи чисел на выходе элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 11 будет сигнал "О".Третий случай. Код числа на входе 1 О больше кода числа на входе 9.В этом случае при первом неравенстве битов сравниваемьи чиселна выходе элемента ИСКЛЮЧАЮЩЕЕ ИЛИ11 будет сигнал "1", который изменит состояние триггера 12 из"1" в"0". Тогда при всех значенияхбитов сравниваемых чисел на выходеэлемента И 14 будет сигнал "0" который не изменит состояние триггера15. Это значит, что на выходнойшине 19 будут последовательно появляться биты числа на входной шине10, т.е. код большего числа. Инверсный вьиод триггера 15 являетсявторым вьиодом компараторного переключателя, на котором будет сигнал"1", если код числа на входной шине9 больше кода числа на входной шине10.Предлагаемое устройство для определения максимума последовательностейиз й е -разрядных чисел имеет следующие технические преимущества.В известном устройстве для вьщеления экстремального иэ 1 и -разрядных двопчньи чисел выполняется выделение экстремального числа из однойпоследовательности из пщ -разряд"ных чисел. Предлагаемое устройствовыполняет выделение максимума груп"пы последовательностей, каждая изкоторых состоит иэ О % -разрядныхчисел, путем запоминания максимумапредыдущей последовательности вЕ-разрядном сдвиговом регистре иего побитного сравнения с максимальным элементом текущей последовательности из о п-разрядных чисел спомощью компараторного переключателя. Если максимум текущей последовательности больше максимума предыдущей последовательности, то он записывается в Э -разрядный сдвиговый регистр. Эта процедура продолжается до тех пор, пока не будутпроанализированы все заданные после- одовательности из Р п -разрядных двоичных чисел. Для достижения экономии аппаратурных затрат при определении максимума последовательности, состоящей из 1 е -разрядных двоичных чисел, эта последовательность разделяется на 3 Опоследовательности. С помощью предлагаемого устройства выполняется параллельно-последовательное. определение максимума последователь,ности из чисел. Если задано время Т, за которое должен быть выполнен поиск максимума последовательности из 1 -разрядных чисел, а время параллельного вычисления максимума в прототипе равно 1 , то при исполь" зовании предлагаемого устройства получаем экономию в аппаратурных затратах в КТ/ 1 раз эа счет умень. шения в К раз числа параллельных входов устройства и, следовательно, уменьшения в К раз элементов И 1, триггеров 4 и элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 3.1096638 Составитель Е ИвановаРедактор С. Пекарь Техред Т.Маточка Корректор А. Тяс дписное филиал ППП "Патент", г, Ужгород, ул. Проектная, 4 Заказ 3826/36 ВНИИПИ Госуд по делам 113035, МоскТираж 69 рственного к зобретений и а, Ж, Рау митета СССРоткрытийская наб., д. 4/5