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

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

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

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

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

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

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

Наиболее близким по технической сущности к предлагаемому является устройство для введения экстремального из п ш -разрядных двоичных чисел, содержащее п m -разрядных регистров и групп элементов И, 1л-входовые элементы ИЛИ, триггеры, элементы ИСКЛЮЧАЮЩЕЕ ИЛИ, П -входовой элемент ИЛИ, причем выходы регистров поразрядно соединены с первыми входами элементов И рбответствующей группы, выходы которых соединены с входами соответствующего ГЦ -входового элемента ИЛИ, входы установки триггеров в единицу - с входом сброса устройства, вторые входы одноименных элементов И Bfcex групп соединены с соответствующими шинами управления поразрядным сравнением устройства, третьи входы элементов И каждой группы соединены с выходами соответствующих триггеров и с выходами кода номера регистра, содержащего экстремальное число устройства, выходы m-входных элементов ИЛИ соединены с первыми входами соответствующих элементов ИСКЛЮЧАЮЩЕЕ ИЛИ и с соответствующими входами п -входового элемента ИЛИ, выход которого соеди ней с вторыми входами элементов ИСКЛЮЧАЮЩЕЕ ИЛИ и является выходом кода экстремального числа устройства, выходы элементов ИСКЛЮЧАЮДЕЕ 5 ИЛИ соединены .с нулевыми входами соответствующих триггеров 21.

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

0 Цель изобретения - расширение области применения устройства за счет определения максимума группы последовательностей КЗ Л -разрядных чисел . и уменьшение аппаратурных затрат за счет исключения из известного устройства п Hi -разрядных регистров и п П1 -входовых элементов ИЛИ.

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

5 Я триггеров, П -входовый элемент ИЛИ, причем шина тактовых импульсов соединена с первыми входами трехвходовых элементов И, вторые входы которых подключены к шинам соответствующих сравниваемых последовательностей, выход и -входового элемента ИЛИ соединен с первыми входами элементов ИСКПЮЧАКЩЕЕ ИЛИ, выходы которых соединены с входами установки в ноль

соответствующих триггеров, выходы которьгх соединены с третьими входами ответствующих трехвходовых элементо И, входы установки в единичное состояние всех триггеров подключены к шине начальной установки устройства введены компараторный переключатель регистр и tn -разрядный сдвиговый регистр, причем выходы трехвходовых элементов И соединены с вторыми вхо дами соответствующих элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, выход которого соединен с первым входом компараторного переключателя, второй вход которого соединен с выходом т -разрядного сдвигового регистра, вход которого подключен к информационному выходу компараторного переключателя, управляющий выход которого подключен к входу разрешения записи регистра, входы разрядов которого соединены с выходами соответствующих триггеров, вход управления сдви гом , tn -разрядного сдвигового регистра соединен с шиной сигналов сдвига устройства, входы установки в нулевое состояние регистра и т-разрядного регистра сдвига подклю чены к шине начальной установки уст ройства. Компараторный переключатель содержит элементы И, ИЛИ, НЕ, ИСКПЮЧАНХЦЕЕ ИЛИ, элементы задержки, триггеры, причем первый и второй входы компараторного переключателя через элементы задержки соединены с первыми входами первого и второго элементов И и с входами элемента ИСКЛЮЧАЮЩЕЕ ИЛИ выход которого под ключен к входу установки в ноль пер вого триггера, выход которого соеди нен с первым входом третьего элемента И, второй вход последнего сое динен с первым входом компараторног переключателя, третий вход через элемент НЕ - с вторым входом компараторного переключателя, а вькод с входом установки в ноль второго триггера, инверсный и прямой выходы которого соединены с вторыми входами соответственно первого и второго элементов И, выходы которых соединены с входами элемента ИЛИ, выход которого является информационны выходом компараторного переключателя, инверсный выход второго триггер является управляющим выходом компараторного переключателя. 6384 На фиг.1 изображена структурная схема предлагаемого устройства; на фиг.2 - структурная схема компараторного переключателя. Устройство содержит п трехвходовьк элементов И 1, t -входовый элемент ИЛИ 2, П -элементов ИСКЛЮЧАЮЩЕЕ I-UIH 3, t триггеров 4, компараторный переключатель 5, m -разрядный сдвиговьш регистр 6, регистр 7 для хранения кода номера максимального числа, шину 8 управления. Компараторный переключатель содержит две входные шины 9 и 10, элемент ИСКЛЮЧАЩЕЕ ИЛИ 11, триггер 12, элемент НЕ 13, трехвходовый элемент И 1А, триггер 15, элементы И 16 и 17, элементы 18 задержки, две выходные шины 19 и 20, элемент ИЛИ 21. Устройство работает следующим образом. Перед началом поступления на вход устройства кодов сравниваемых чисел а|,...,а выполняется начальная установка устройства - установка в 1 триггеров А, установка в О регистров 6 и 7. При одновременной подаче на вход элементов И 1 уттравляющих тактовых импульсов из шины 8 и битов входных чисел, начиная со старшего разряда, через элементы И 1 будут проходить сигналы тех битов чисел, соответствующие триггеры которых находятся в состоянии 1. Если на вход п -входового элемента ИЛИ 2 поступают коды чисел, в которых хотя бы в одном из данных разрядов есть 1, то на выходе элемента ИЛИ 2 будет сигнал 1, который подается на второй вход элемента ИСКЛЮЧАЩЕЕ ИЛИ 3, на первый вход которого поступает сигнал из выхода элемента И 1, Тогда на выходах элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 3 будет сигнал 1 для кодов чисел с нулевым битом в данном разряде, который изменит состояние триггера из 1 в состояние О. Таким образом, исключаются из дальнейшего поиска числа, если соответствующие им триггеры находятся в состоянии О. С выхода элемента ИЛИ 2 последовательно поступают значения разрядов максимума,последовательности чисел а ная со старшего разряда, на первый вход компараторного переключателя. Одновременно на второй вход компараторного переключателя поступают разряды максимума предыдутцей последовательности чисел ,.. .а начиная со старшего разряда, из сдвигового регистра 6 путем подачи управляющих сдвиговых импульсов из шины 8. Компараторный переключатель 5 вьтолняет побитное сравнение входных чисел и выдает на младший разряд сдвигового регисггра биты большего из двух сравниваемых чисел Если максимум, текущей последователь ности чисел а ,х больше максимума предьщущей последовательности чисел, то в регистр 6 записывается втором выходе компараторного переключателя 5 будет сигнал 1, который подается на управляющи вход записи регистра 7 для записи с держимого триггеров 4, т.е. номера максимума последова.ельности а .. Если максимум последователь ностй .. меньше или равен макси;Муму предыдущей последовательности гпах регистр 6 побитно перепишется его содержимое, т.е. . та X Перед поступлением на вход устройства кодов чисел,каждой новой последовательности из Г7 чисел выполняется установка триггеров 4 в состояние 1. Компараторный переключатели работает следующим образом. Перед началом сравнения чисел выполняется установка триггеров 12 и J5 в состояние 1. На входные шины 9 и 10 поступают биты входг ных чисел, начиная со старш,его разряда. Рассмотрим три возможных случая. Первый случай.Код числ-а на входе 9больше кода числа на входе 10. В этом слунае при первом неравенстве битов чисел на входе трехвходового элемента И 14 будут три равных сигнала, соответствующие 1, так как сигнал О на входе 10инвертируется элементом НЕ 13. Тогда на выходе элемента И 14 будет сигнал 1, которьй изменит состояние триггера 15 из 1 в состояние О. Сигнал 1 из инверсного выхода триггера 15 подается на второй вход элемента И 16, на первый вход которого через элемент задержки подается сигнал 1 из входной шины 9. Тогда на выходе элемента И 16 будет сигнал 1. Соответственно,на выходе элемента И 17 в этом случае будет сигнал О и на выходе элемента ИЛИ 21 будет сигнал 1. Из входов 9 и 10 входные сигналы поступают на элемент ИСКЛЮЧАЮЩЕЕ ИЛИ 11, на выходе которого в этом случае при первом неравенстве входных сигналов будет сигнал 1, который изменит состояние триггера 12 из 1 в состояние О. Тогда на выходе элемента И 14 будет сигнал О для всех остальных битов сравниваемых чисел, так как на его вход из триггера 12 поступает сигнал О. Это значит, что на выходной шине 19 компараторного переключателя будут сигналы, соответствующие значениям битов числа на входе 9, т.е. код большего числа из двух сравниваемых чисел. Второй случай. Коды чисел на входных шинах 9 и 10 равны. В этом случае состояние триггеров 12 и 15 не изменяется и на выходной шине 19 компараторного переключателя будут последовательно биты числа на входной шине 10, так как для всех битов сравниваемых чисел на выходе элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 11 будет сигнал О. Третий случай. Код числа на входе 10 больше кода числа на входе 9. В этом случае при первом неравенстве -битов сравниваемых чисел На выходе элемента ИСКЛЮЧЛрЦЕЕ ИЛИ 11 будет сигнал 1, который изменит состояние триггера 12 из 1 в О. Тогда при всех значениях битов сравниваемых чисел на выходе элемента И 14 будет сигнал который не изменит состояние триггера 15. Это значит, что на выходной шине 19 будут последовательно появляться биты числа на входной шине 10, т.е. код большего числа. Инверсньй выход триггера 15 является вторым выходом компараторного переключателя, на котором будет сигнал 1, если код числа на входной шине 9 больше кода числа на входной шине 10. Предлагаемое устройство для определения максимума последовательностей из И m-разрядных чисел имеет следующие технические преимущества. В известном устройстве для вьаделения экстремального из П m -разрядных двоичных чисел выполняется выделение экстремального числа из одной последовательности из п m -разрядных чисел. Предлагаемое устройство вьтолняет вьщеление максимума группы последовательностей, каждая из которых состоит из nm-разрядных чисел, путем запоминания максимуна предьщущей последовательности в т-разрядном сдвиговом регистре и его побитного сравнения с максималь ным элементом текущей последователь ности из nm-разрядных чисел с помощью компараторного переключателя. Если максимум текущей последова тельности больше максимума предвдущей последовательности, то он записывается в гп -разрядный сдвиговый регистр. Эта процедура продолжается до тех пор, пока не будут проанализированы все заданные после довательности из п m-разрядных двои ных чисел. 38 Для достижения экономии аппаратурных затрат при определении максимума последовательности, состоящей из cm-разрядных двоичных чисел, эта последовательность разделяется на /е/п| последовательности. С помЪщью предлагаемого устройства вьтолняется параллельно-последовательное определение максимума последователь.ности из чисел. Если задано время Т, за которое должен быть выполнен поиск максимума последовательности из с -разрядных чисел, а время параллельного вычисления максимума в прототипе равно t , то при использовании предлагаемого устройства получаем экономию в аппаратурных затратах в К«Т/t раз за счет уменьшения в К раз числа параллельных входов устройства и, следовательно, уменьшения в К раз элементов И 1,триггеров 4 и элементов ИСКЛЮЧАЮЩЕЕ ШШ 3.

9 Ою

го

fS

ВхоВ

13

-

2i

fo О-4Ж}

б Уст../

17

Фиг. 2