Устройство поиска заданного числа

Номер патента: 1462292

Авторы: Молошаг, Смирнов

ZIP архив

Текст

СОЮЗ СОВЕТСНИХСОЦИАЛИСТИЧЕСНИХРЕСПУБЛИК 292 91 (111 ИЗОБРЕТВИДЕТЕЛЬСТВУ И ОПИСАН И АВТОРСНОМ с поль блока СУДАРСТВЕННЫЙ НОМИТЕТИЗОБРЕТЕНИЯМ И ОТНРЫТИЯМИ ГКНТ СССР(56) Авторское свидетельство СССРФ 997029, кл. С 06 Р 7/06, 1982.Авторское свидетельство СССРУ 1183955, кл. С 06 Р 7/06, 1984,(54) УСТРОЙСТВО ПОИСКА ЗАДАННОГО ЧИСЛА(57) Изобретение относится к вычислительной технике и может быть изовано в качестве автономногоЗВМ при поиске заданных чисел в упор доченном массиве. Цель изобретенияповышение быстродействия, Устройствосодержит регистры числа 1,2, регистры адреса 3,4, схемы сравнения 5,6,7,блок вычитания 14, блок 15 определенияначального шага поиска, регистр сдвига 16, триггер 19, коммутатор 20,сумматоры 21, 22, регистр 23 относительного адреса, элементы И, ИЛИ.Устройство выполняет поиск заданногочисла в упорядоченном массиве данныхс предварительным автоматическимопределением грубого шага поиска, чтпозволяет повысить его быстродействие. 1 з.п.ф-лы, 2 ил.Изобретение относится к вычислительной технике и может быть использовано в качестве автономного блока ЭВМпри поиске заданных чисел в упорядо 5ченном массиве.Цель изобретения - повышениебыстродействия,На фиг.1 представлена блок-схемапредлагаемого устройства поиска заданного числа; на Фиг.2 - схема блокаОпределения начального шага поиска,Устройство поиска заданного числасодержит регистры 1 и 2 числа,.регистры 3 и 4 адреса, схемы 5-7 срав ения, элементы И 8-10, элемент 11Задержки, элементы ИЛИ 12 и 13, блок14 вычитания, блок 15 определенияначального шага поиска, регистр 16сдвига, элемент НЕ 17, группу элементов НЕ 18, триггер 19 коммутатор 20,сумматоры 21 и 22 регистр 23 относи-,.т 1 ельного адреса, вход 24 тактовых импульсов, вход 25 начальной установки,выход 26 разрешения считывания устрой тва, выход 27 конца поиска устройства, выход 28.наличия числа, входы29 числа устройства, информационныевыходы 30 устройства.Блок 15 определения начального 30щага поиска и-разрядного входногоКода адреса содержит (и) элементовИ-НЕ 31 и элемент НЕ 32.Устройство работает следующим образом,35В исходном состоянии в регистр 2 Заносится значение числа, которое требуется найти в упорядоченном по возрастанию массиве данных, в регистр 3 - адрес начала массива, а в регистр А - адрес конца массива упорядоченных данных, Блок 14 вычитания(с группой инверторов по второй группе входов) формирует объем исследуемого массива, значение которого поступает на вход блока 15 определения начального Шага поиска, причем выходы младших разрядов блока 14 вычитания поступают на вход старших разрядов блока 15 определения начального шага поиска, а выходы старших разрядов блока 14 вычитания поступают на вход младших разрядов блока 15 определения начального шага поиска. Вход "Перенос" блока 14 вычитания имеет единичное Значение (не показан), вследствие чего начальный шаг поиска И будет принимать значения 0,5 Ы ( И = 2с М,где И - объем упорядоченного массива,в котором производитсяпоиск;п - разрядность информационноговыхода 30 устройства,С выхода блока 15 определения начального шага поиска инверсный кодпоступает на информационные входырегистра 16 последовательного сдвига.На вход 25 подается импульс начальнойустановки, который устанавливаеттриггер 19, регистры 16 и 23 в нулевое состояние, и проходя через элемент ИЛИ 13, Формирует сигнал 26 .разрешения считывания, по которомусчитывается первое число из ячейки садресом, сформированным на выходе30 (адрес начала массива), и данноечисло записывается по входам 29 врегистр 1, Нулевое состояние триггера19 устанавливает параллельный режимзаписи в регистр ,16. Далее при поступлении первого тактового импульса на вход 24 устройства производится запись начального шага поиска в регистр 16, а через некоторое время, определяемое элементом 11 задержки, триггер 19, устанавливается в единичное состояние, что определяет режим последовательного сдвигадля регистра 16, а также производится запись относительного адреса в регистр 23. На выходе сумматора 22 Формируется абсолютное значение адреса, по которому считывается значение второго числа . с последующей .записью в регистр 1., В дальнейшем с приходом последующих импульсов направлением поиска управляет схема 5 сравнения, Если значение считываемого числа (регистр 1)меньше, чем значение числа,.которое требуется найти (регистр 2), то на первый управляющий вход коммутатора 20 поступает единичный, уровень, что разрешает прохождение значение шага поиска в прямом коде на первую группу входов, сумматора 21., на вторую группу входов которого поступает предыдущее значение кода адреса. ТаКим образом, осуществляется модификация адреса в сторону увеличения на величину шага в два раза меньше, чем в предыт дущем цикле, Если значение считываемого числа больше, чем значение искомого числато на второй управляющий вход коммутатора 20 поступает еди1462292 1. Устройство поиска заданного50 числа, содержащее регистры чисел, регистры адресов, схемы сравнения, три элемента И, два элемента ИЛИ, триггер, элемент задержки, причем входы числа устройства подключены к информационным входам первого регистра числа, выходы разрядов которого соединены с входами первой группы первой схемы сравнения, входы второй группыничный уровень, что разрешает прохождение инверсного кода шага поискачерез коммутатор 20 и на сумматоре21 практически выполняется операциявычитания. Таким образом, осуществля 5ется модификация адреса в сторонууменьшения на величину шага в два ра"за меньше, чем в предыдущем цикле,После каждого такта считыванияосуществляется анализ поступающихчисел в регистр 1, а также соблюдениеграниц поиска. При считывании числаиз ячейки с адресоМ начала массива,на выходе Равно схемы 7 формируется единичный сигнал. При этом, еслисчитываемое число меньше, чем значе-,ние искомого числа, то на выходеэлемента И 8 формируется единичныйсигнал, который через элемент ИЛИ 12поступает на выход 27 конца поиска.При совпадении считываемого числас искомым (единичный сигнал на выходе "Равно" схемы 5 сравнения) исоблюдении границ (единичный сигнал 25на выходе "Меньше" схемы 6 сравнения)на выходе элемента И 9 формируетсяединичный сигнал, который поступаетна выход 28 наличия поиска и черезэлемент ИЛИ 12 на выход 27 конца,поиска,При несоблюдении границ поиска навыходе "Меньше" схемы 6 сравненияформируется нулевой сигнал, которыйчерез элементы И 10, НЕ 17 поступаетединичным уровнем на второй .входуправления коммутатора 20 и на вход ."Перенос" сумматора 21, в результатечего осуществляется модификацияадреса в сторону уменьшения,При отсутствии искомого числа вупорядоченном массиве, после (и+1)циклов поиска с выхода "2-1" регистра 16 нулевой сигнал через элементИЛИ 12 единичным уровнем поступит на 45выход 27 конца поиска. Формула изобретения которой соединены с выходами разрядов второго регистра числа, информационные входы которого являются входами заданного числа устройства, выходМеньше первой схемы сравнения соединен с первым входом первого элемента И, второй вход которого соединен с выходом второй схемы сравнения, а выход соединен с первым входом первого элемента ИЛИ, выход которого является выходом конца поиска устройства, а второй вход является выходом наличия числа устройства и соединен с выходом второго элемента И, первый вход которого соединен с выходом равенства первой схемы сравнения, а второй вход подключен к выходу третьей схемы сравнения и первому входу третьего элемента И, второй вход. которого соединен с выходом "Больше" первой схемы сравнения, выход второго элемента ИЛИ является выходом разрешения считывания устройства, а первый вход соединен с входом начальной установки устройства и входом установки в ноль триггера, выходы разрядов первого и второго регистровГ адре сов подключены к входам пер вых групп, второй и третьей схем сравнения, входы вторых групп которых соединены с информационными выходами устройства, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия, в него введены блок вычитания, блок определения начального шага поиска, регистр сдвига, группа элементов НЕ, коммутатор, два сумматора, регистр относительного адреса, элемент НЕ, причем вход начальной установки устройства подключен к входам установки в ноль регистра относительного адреса и регистра сдвига, выход (и+1)-го разряда которого соединен с третьим входом первого элемента ИЛИ, а вход установки в единичное состояние подключен к выходу триггера, синхровход которого соединен с синхровходом регистра относительного адреса и через элемент задержки подключен к входу тактовых импульсов устройства, который соединен также с синхровходом регистра сдвига и вторым входом второго элемента ИЛИ, выходы разрядов второго и первого регистров адресов соединены соответ- . ственно с входами уменьшаемого и вычитаемого блока вычитания, выходы которого соединены с соответствующими1462292 входами блока определения начального шага поиска, выходы которого соединены с информационными входами регистра сдвига, выходы разрядов которого с5 первого по и-й соединены с информационными входами первой группы коммутатора и через соответствующие элемен= ты НЕ группы - с информационными входами второй группы коммутатора, 10 первый управляющий вход которого подключен к выходу третьего элемента Ки через элемент НЕ - к второму управляющему входу коммутатора н входу перенбса первого сумматора, входы 15 1 йервой группы которого соединены с выходами коммутатора, а выходы подключены к информационным входам реистра относительного адреса, выходы азрядов которого подключены к входам 2 ОВ 4Ф Ф 1 оставитель Е.Ивановехред Л. Олийнык с Середректор С.Черн Подписно ираж 66 Заказ 712/46 изобретениям и открытиям при Г 1(НТ ССС Раушская наб., д. 4/5 льский комбинат "Патент", г. Ужгород, ул. Гагарина,( роизводственно ВНИИПИ Государственного комитета п 113035, Москва, Ж второй группы первого сумматора и входам первой группы второго сумматора, входы второй группы которого соединены с входами вычитаемого блока вычитания, а выходы являются информационными выходами устройства.2. Устройство по п.1, о т л и ч аю щ е е с я тем, что блок определения начального шага поиска содержит (и) элементов И-НЕ и элемент НЕ,причем входы блока соединены с входом элемента НЕ и первыми входами элементов И-НЕ, выход элемента НЕ является, первым выходом, блока и соединен с вторыми входами элементов И-НЕ, выход -го элемента И"НЕ соединен с (+2)- ми входами элементов И-НЕ с (д+1)-го по (и)-й и является 1.-ым выходом блока.

Смотреть

Заявка

4308065, 21.09.1987

ПРЕДПРИЯТИЕ ПЯ В-2445

МОЛОШАГ ВАЛЕРИЙ ВИКТОРОВИЧ, СМИРНОВ АНАТОЛИЙ ПЕТРОВИЧ

МПК / Метки

МПК: G06F 7/06

Метки: заданного, поиска, числа

Опубликовано: 28.02.1989

Код ссылки

<a href="https://patents.su/4-1462292-ustrojjstvo-poiska-zadannogo-chisla.html" target="_blank" rel="follow" title="База патентов СССР">Устройство поиска заданного числа</a>

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