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

СОЮЗ СОВЕТСКИХСОЦИАЛ ИСТИЧ Е СКИХРЕСПУБЛИК(55 6 06 Р 7/06 ГОС ПО ПРИ К(21) (22) (46) (71) им, сти (72) вич (53) (56) М 9 М (54 ЧИ (57 ной ои ач ск вх не уст о по с 9 з д ше и ск гру ДАРСТВЕННЫЙ КОМИТЕТЗОБРЕТЕНИЯМ И ОТКРЫТИЯМГКНТ СССР ВТОРСКОМУ СВИДЕТЕЛЬСТВ 647757/24-243.12.883.11.90, Бюл. М 43Киевский политехнический институт 0-летия Великой Октябрьской социалиеской революцииА.Г.Горбунов, С.М.Баронов, Н,Г.ПопоВ.А,Сидоров681.325 (088,8)вторское свидетельство СССР 7029, кл, 6 06 Р 7/06, 1978. Авторское свидетельство СССР 183955, кл. 6 06 Р 7/06, 1985. УСТРОЙСТВО ПОИСКА ЗАДАННОГО ЛАИзобретение относится к вычислитель- технике и может быть использовано в Изобретение относится к вычислитель- технике и может быть использовано в стве автономного блока ЭВМ при по- заданных чисел в упорядоченном масЦель изобретения - повышение быстействия устройства.На фиг,1 и 2 представлена схема предемого устройства,Устройство содержит информационныеы 1 устройства, регистр 2, схему 3 сравия, регистр 4, выход 5 наличия числайства, элемент ИЛИ 6, выход 7 концака устройства, элемент ИЛИ 8, элементержки, элемент И 10, выход 11 разрея считывания устройства, вход 12 эапуустройства, триггер 13, регистр 14,пу элементов И 15, регистр 16, элемент качестве автономного блока ЭВМ при поиске заданного числа в упорядоченном массиве. Цель изобретения - повышение быстродействия устройства. Устройство содержит регистры, схему сравнения, выход наличия числа устройства, элементы ИЛИ, выход конца поиска устройства, элемент задержки, элементы И, выход разрешения считывания устройства, вход запуска устройства, триггеры, группы элементов И, регистр сдвига адреса, вход тактовых импульсов, сумматор, элемент ИЛИ-НЕ, формирователи дополнительного кода, группы элементов ИЛИ, регистр сдвига, формирователи импульсов, элементы ИЛИ, информационные вход и выход устройства.2 ил. И 17, элемент И 18, группу элементов И 19, группу элементов И 20, элементы И 21 и 22, элемент 23 задержки, регистр 24 сдвига адреса, элементы И 25 - 27, вход 28 тактовых импульсов, триггер 29, сумматор 30, элемент ИЛИ-НЕ 31, формирователь 32 дополнительного кода, группу элементов ИЛИ 33, сумматор 34, регистр 35, информационные выходы 36 устройства, группу элементов И 37, группу элементов ИЛИ 38, группу элементов И 39, формирователь 40 дополнительного кода, регистр 41 сдвига, элемент 42 задержки, формирователь 43 импульсов, элемент ИЛИ 44, формирователь 45 импульсов, элемент 46 задержки, элемент ИЛИ 47 и элементы 48 и 49 задержки.Устройство работает следующим образом.В исходном состоянии в регистр 4 заносится значение числа, которое требуется найти в упорядоченном по возрастанию массиве данных, в регистр 14- адрес начала массива, а в регистр 16 - адрес конца массива упорядоченных данных. Адрес начала массива с выходов регистра 14 поступает на вход формирователя 40 дополнительноо кода, с выхода которого дополнительный код адреса начала массива поступает на вторую группу входов сумматора 30, на первую группу входов которого подается адрес конца массива с выходов регистра 16. С выходов сумматора 30 относительный код адреса конца массива поступает на информационные входи регистра 24 сдвига адреса, Нэ вход 12 устройства подается импульс запуска, который поступает на вход записи регистра 24 сдвига адреса и записывает в него относительный код адреса конца массива, устанавливает триггер 29 в единичное состояние, а триггер 13 - в нулевое состояние. С выхода триггера 29 единичный уровень поступает на второй вход элемента И 27, разрешая прохождение через него тактовых импульсов, которые подаются на его первый вход с входа 28 устройства. Тактовые импульсы с выхода элемента И 27 поступают на первые входы 26 и 25 элементов И, На второй вход элемента И 25 поступает запрещающий нулевой уровень с прямого выхода триггера 13, а на второй вход элемента И 26 поступает единичный уровень с его инверсного выхода, тем самым запрещая прохождение тактовых импульсов через элемент И 25 и разрешая их прохождение через элемент И 26 на регистр 41 сдвига. С первого выхода регистра 41 сдвига единичный уровень поступает на элемент 46 задержки и через формирователь 45 импульсов на второй вход элемента ИЛИ 44 в виде единичного импульса и на первые входы группы элементов И 39., разрешая прохождение адреса конца массива с выхода регистра 16 через группу элементов И 39 на вторую группу входов группы элементов ИЛИ 38, с выходов которой он поступает на входы регистра 35,Единичный импульс с выхода элемента ИЛИ 44 через элемент ИЛИ 47 поступаег на вход записи регистра 35, записывая в него адрес конца массива, находящийся на его входах, Одновременно этот единичный импульс поступает на второй вход элемента ИЛИ 8, с выхода которого через элемент 9 задержки (задержка осуществляется на время формирования адреса на сумматоре 34) и элемент И 10 поступает на выход 11 устройства как импульс считывания и на вход элемента 49 задержки (задержка осуществ 5 10 1520 2530 ляется на время считывания числа из ЗУ ЭВМ). По адресу, сформированному на выходах сумматора 34, поступающему ца выходы Зб устройства, из ЗУ ЭВМ считывается значение последнего числа, которое записывается по входам 1 устройства в регистр 2, С выхода элемента 49 задержки единичный импульс через элемент 48 задержки и элемент ИЛИ 47 поступает на вход записи регистра 35 и на разрешающие входы группы элементов И 37, на информационные входы которой поступает адрес с выходов 36 устройства,С выхода элемента 46 задержки (задержка осуществляется на время формирования адреса на сумматоре 34, считывания числа из ЗУ ЭВМ и сравнения содержимого регистров 2 и 4 на схеме 3 сравнения) единичный уровень поступает на второй вход элемента И 17, на первый вход которого подается сигнал с выхода "Больше" схемы 3 сравнения,Если заданное число больше, чем любое в массиве, то на выходе "Больше" схемы 3 сравнения появится единичный уровень, проходящий через элемент И 17 на третий вход элемента ИЛИ б, с прямого выхода которого он поступает нэ инверсный вход элемента И 10 и на выход 7 устройства -конец поиска, э с инверсного - на вход сброса триггера 29, нулевой уровень на выходе которого запрещает прохождение тактовых импульсов на устройство, Если заданное числс равно числу в массиве, то на выходе 35 40 45 50 который поступает на элемент 42 задержки, и через формирователь 43 импульсов - на первый вход элемента ИЛИ 44 и на разрешающие входы группы элементов И 15, разрешая прохождение адреса начала массива с выходов регистра 14 через группу элементов И 15 нэ первые входы группы элементов ИЛИ 38, с выходов которой этот адрес поступает на,входы регистра 35, Единичный импульс с выхода элемента ИЛИ 44 поступает на первый вход элемента ИЛИ 47 и с его выхода - на вход записи регистра 35, разрешая запись в него адреса начала массива, Одновременно этот единичный импульс поступает на второй вход элемента ИЛИ 8, с выхода которого через элемент 9"Равенство" схемы 3 сравнения появится единичный уровень, который поступает на выход 5 устройства - число найдено, и на первый вход элемента ИЛИ б, с прямого выхода которого на выход 7 устройства - конец поиска, Если заданное число меньше последнего числа в массиве, то с приходом второго тактового импульса на вход регистра 41 сдвига на его втором выходе появляется единичный логический уровень,1608643 зад хо ин сф 34, ну вы тр го уст ны "О" "1" 22 на Ес ма ср пр вх ко эл по 6 тр то им чи лпу ьна ивх джиге аэл мля тщ гсзвыси еегчи лре ис иэл м32 дре ареинфИ 0вьйи рн вст емвляиэл ржки и элемент И 10 поступает на вы устройства как импульс считывания вход элемента 49 задержки. По адресу, рмированному нв выходах сумматора на первые входы которого поступает код я, а на вторые - адрес начала массива с одов регистра 35, из запоминающего усйства ЭВМ считывается значение первоисла, которое записывается по входам 1 ойства в регистр 2,С выхода элемента 42 задержки единичуровень поступает на вход установки в регистра 41 сдвига, на вход установки в триггера 13 и на второй вход элемента И на первый вход которого поступает сигс выхода "Меньше" схемы 3 сравнения, и заданное число меньше, чем любое в сиве, то на выходе "Меньше" схемы 3 внения появится единичный уровень, ходящий через элемент И 22 на второй д элемента ИЛИ б, с прямого выхода орого он поступает на инверсный вход мента И 10 и выход 7 устройства - конец ска. С инверсного выхода элемента ИЛИ игнал поступает на вход сброса в "0" ггера 29, нулевой уровень на выходе коого запрещает прохождение тактовых ульсов на устройство.Если заданное число больше первого а массива, то следующий тактовый имс с выхода элемента И 27, поступающий ервый вход элемента И 25, на второй которого подается открывающий полоельный уровень с прямого выхода триг 13, поступает через него на вход ента 23 задержки (задержка осуществся на время считывания из запоминаюо устройства ЭВМ числа и сравнения его данным), С выхода элемента И 25 тактоимпульс поступает нз вход сдвига отнольно адреса в регистре 24 и сдвигает вправо, осуществляя тем самым целоенное деление его на два, С выходов стра 24 сдвига относительный адрес поает на информационные входы группы ентов И 19 и на входы формирователя ополнительного кода относительно ад, с выходов которого относительный здв дополнительном коде поступает на ормационные входы группы элементов . С выхода элемента 23 задержки тактоимпульс поступает соответственно на вый и второй входы элементов И 18 и 21, торой и первый входы которых соответнно поступают сигналы с выходов схе 3 сравнения "Больше" и Меньше". Находе "Больше" схемы 3 сравнения появтся единичный уровень, разрешающийохождение тактового импульса с выхода мента 23 задержки через элемент И 18 5 10 15 20 25 30 35 40 45 50 55 6на третий вход элемента ИЛИ 8 и на разрешающие входы группы элементов И 19, разрешая прохождение через нее относительного адреса, который через группу элементов ИЛИ 33 поступает на первые входы сумматора 34, на вторые входы которого подается адрес начала массива с выходов регистра 35, записанный в него на предыдущем такте,На выходе сумматора 34 формируется новый адрес, равный адресу начала массива плюс половина первоначального относительного адреса. Тактовый импульс с выхода элемента ИЛИ 8 поступает на вход элемента 9 задержки, с выхода которого через элемент И 10 поступает на вход элемента 49 задержки и на выход 11 устройства - импульс считывания. Из запоминающего устройства ЭВМ считывается значение числа по адресу, сформированному на выходах 36 устройства, которое записывается по входам 1 устройства в регистр 2.С выхода элемента 49 задержки тактовый импульс поступает на разрешающие входы группы элементов И 37. разрешая прохождение адреса с выхода Зб устройства на входы регистра 35, Одновременно этот тактовый импульс через элемент 48 задержки (задержка осуществляется на время появления адреса на входах регистра 35) и элемент ИЛИ 47 поступает на вход записи регистра 35, записывая в него этот адрес.Если с выхода "Меньше" схемы 3 сравнения нз первый вход элемента И 21 поступает единичный уровень, то разрешается прохождение тактового импульса с выхода элемента 23 задержки нз первый вход элемента ИЛИ 8 и на разрешающие входы группы элементов И 20, разрешая тем самым прохождение дополнительноо кода нового относительного адреса через группу элементов И 20, поступающего с выходов формирователя 32 дополнительного кода адреса, Этот дополнительный код нового относительного адреса через группу элементов ИЛИ 33 поступает на первые входы сумматора 34, на выходе которого Формируется новый адрес, поступающий на выход Зб устройства.Новый адрес равен предыдущему адресу минус половина предыдущего относительного адреса,С приходом импульса считывания на выход 11 устройства из ЗУ ЭВМ считывается значение первого числа, которое записывается по входам 1 устройства в регистр 2, а в регистр 35 записывается новый адрес. С приходом следующих тактовых импульсов, в зависимости от того, на каком выходе "Больше" или "Меньше" схемы 3 сравненияпоявляется единичный уровень, на выходе 36 устройства формируется новый адрес,С каждым тактом все повторяется до тех пор, пока не будет найдено число, равное заданному, или до тех пор, пока на выходе регистра 24 сдвига адреса не появится относительный адрес, равный нулю, который поступает на элемент и ИЛИ-НЕ 31 (где и - максимальное количество разрядов в адресе), с выхода которого единичный уровеньпоступает на четвертый вход элемента ИЛИ 6. При этом на прямом выходе элемента ИЛИ 6 появляется единичный уровень, поступающий на инверсный вход элемента И 10, запрещая прохождение импульса считывания на выход 11 устройства и на выход 7 устройства - конец поиска, Одновременно с инверсного выхода элемента ИЛИ 6 нулевым уровнем, поступающим на вход сброса триггера 29, блокируется прохождение тактовых импульсов на устройство через элемент И 25.Таким образом, за первые два такта устройство определяет, попадает заданное число в рамки массива или нет, если нет, то на выходе 7 устройства появляется единичный логический уровень, свидетельствующий об окончании анализа. Если попадает, то устройство максимум за 12 тактов найдет заданное число, при этом на выходах 5 и 11 устройства соответственно "Число есть" и "Конец анализа" появляются единичные уровни. Если числа в массиве нет, то через и тактов на выходе 7 устройства появляется единичный уровень, а на выходе 5 - отсутствует, что свидетельствует о том, что число не найдено и анализ окончен.Формула изобретенияУстройство поиска заданного числа, содержащее схему сравнения, четыре регистра, пять элементов И, элемент задержки, два элемента ИЛИ, группу элементов И, триггер, причем информационные входы устройства подключены к информационным входам первого регистра, выходы разрядов которого подключены к входам первой группы схемы сравнения, входы второй группы которой подключены к выходам разрядов второго регистра, информационные входы которого являются входами заданного числа устройства, выход равенства схемы сравнения является выходом наличия числа устройства и соединен с первым входом элемента ИЛИ, прямой выход которого является выходом конца поиска устройства, выход второго элемента ИЛИ через элемент задержки подключен к прямому входу второго элемента И, выход которого является выходом разрешения считывания устройства, выходы разрядов третьего регистра под 5 10 15 20 25 30 35 40 45 50 55 ходы которого соединены с информационными входами элементов И третьей группы, выходы которых подключены к первым входам элементов ИЛИ первой группы, вторые входы которых подключены к выходам элементов И второй группы, а выходы - к входам первой группы сумматора, входы второй группы которого подключены к выходам разрядов пятого регистра, информационные входы которого подключены к выходам элементов ИЛИ второй группы,ключены к информационным входам соответствующих элементов И группы, управляющие входы которых объединены, информационные входы третьего и четвертого регистров являются соответственно входами адреса конца массива и адреса начала массива устройства, выход "Меньше" схемы сравнения подключен к первому входу второго элемента И, выход "Больше" схемы сравнения подключен к первым входам третьего и четвертого элементов И, прямой выход триггера подключен к первому входу пятогоэлемента И, отл ича ющееся тем, что, с целью повышения быстродействия, в него введены пятый регистр, регистр сдвига, регистр сдвига адреса, два сумматора, четыре группы элементов И, две группы элементов ИЛИ, три элемента И, пять элементов задержки, два элемента ИЛИ, второй триггер, элемент ИЛИ-НЕ, два формирователя дополнительного кода, два формирователя импульсов, причем тактовый вход устройства подключен к первому входу шестого элемента И, выход которого подключен к второму входу пятого элемента И и первому входу седьмого элемента И, второй вход которого соединен с инверсным выходом первого триггера, входы установки в "0" первого и в "1" второго триггера объединены и соединены с входом запуска устройства и с входом установки в "0" регистра сдвига адреса, а вход установки в "1" первого триггера подключен к входу сброса регистра сдвига адреса, к первому входу восьмого элемента И, через второй элемент задержки к первому выходу регистра сдвига адреса, к управляющим входам элементов И первой группы и через первый формирователь импульсов к первому входу третьего элемента ИЛИ, выход которого соединен с первым входом второго элемента ИЛИ, второй и третий входы которого подключены соответственно к выходам второго и третьего элементов И и к управляющим входам элементов И второй и третьей групп, информационные входы элементов И второй группы подключены к соответствующим выходам регистра сдвига адреса и входам формирователя дополнительного кода, вы1608643 10 гв д перв един мен вых дин мен перв втор мир ныс вых инф адре вых элем рого ше" вход под та И вых кото ки сдв эле е, вторые и третьи входы которых саны соответственно с выходами элет в И первой, четвертой и пятой групп, о ы разрядов четвертого регистра соеа ы с информационными входами элеов И четвертой группы и входами й группы второго сумматора, входы й группы которого через второй форватель дополнительного кода соединевыходами разрядов третьего регистра, о ы второго сумматора подключены к рмационным входам регистра сдвига а, вход сдвига которого соединен с ом пятого элемента И и через третий ент задержки с вторыми входами втои третьего элементов И, выход "Меньхемы сравнения подключен к второму восьмого элемента И, выход которого лючен к второму входу первого элеменИ, третий вход которого подключен к ду четвертого элемента И, второй вход ого через четвертый элемент задержоединен с вторым выходом регистра га адреса, с управляющими входами ентов И четвертой группы и через второй формирователь импульсов с вторым входом третьего элемента ИЛИ, выход которого соединен с первым входом четвертого элемента ИЛИ, выход которого соединен с 5 входом записи пятого регистра, а второйвход четвертого элемента И через пятый элемент задержки соединен с управляющими входами элементов И пятой группы и через шестой элемент задержки соединен с 10 выходом первого элемента И, инверсныйвход которого подключен к прямому выходу первого элемента ИЛИ, инверсный выход которого подключен к входу сброса второго триггера, выход которого соединен с вто рым входом шестого элемента И, четвертыйвход первого элемента ИЛИ подключен к выходу элемента ИЛИ-НЕ, входы которого подключены к сответствующим входам регистра сдвига адреса, выходы первого сум матора соединены с информационнымивходами соответствующих элементов И пятой группы и являются выходами адреса устройства, выход седьмого элемента И соединен с входом сдвига регистра сдвига 25 адреса.1608643 Составитель В;КозловТехред М,Моргентал Корректор А,Обруча едактор А,Шан гарина, 101 изводственно-издательский комбинат "Патент", г. Ужго аказ 3616 Тираж 565 Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СС 113035, Москва, Ж, Раушская наб., 4/5