Устройство для сортировки массивов чисел

(д 4 б 06 1- 7 04 Вг;.с ПИСАНИЕ ИЭОБРЕТЕНИАВТОРСКОМУ СВИДЕТЕЛЬСТВУ ОРТИРОВКИ етов,ельников гральным микроТарабрина. М.: о СССР06, 1982.о СССР4, 1981. ОСУДАРСТВЕННЫИ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ(54) УСТРОЙСТВО ДЛЯ СМАССИВОВ ЧИСЕЛ(57) Изобретение предназначено для выде. ления из массива чисел, равных, больших или меньших заданного числа, путем последовательного сравнения двух разрядов кодов чисел массива с кодом заданного числа. Целью изобретения является расширение функциональных возможностей устройства. Устройство для сортировки массивов чисел содержит регистр контрольного кода, гп регистров контролируемых кодов, гп схем анализа, гп схем сравнения и блок управления с соответствуюгцими связями между ними. 3 з.п. ф-лы, 4 ил.Изобретение относится к вычислительной технике и может быть использовано при реализации средств вычислительной техники для сортировки массивов чисел, а также в ассоциативных процессорах.Цель изобретения - расширение функциональных возможностей устройства.На фиг. 1 представлена структурная схема устройства для сортировки массивов чисел; на фиг. 2 -- структурная схема блока анализа; на фиг. 3 - структурная схема блока сравнения; на фиг. 4 -- структурная схема блока управления.Устройство содержит (фиг, 1) регистр 1.1 контрольного кола, регистры 1.2, , 1.гп+1 контролируемых кодов, где гпколичество кодов в массиве, схемы 2.1, , 2 ап ,анализа, схемы 3.1, , З.п сравнения и олок 4 управления. Запись кодов в регистры 1.1, , 1.гп+1 осуществляется по ,кодовым шипам числа (КШЧ). Входами устройства (блока 4 управления) являются также входы для сигналов установки в ,нуль (Уст.О), пускового сигнала (Пуск) ,и входы кода запроса. Выходами устройства являются выход Окончание, на котором появляется сигнал окончания работы устройства, а также выходы схем сравнения, единичный сигнал на выходе каждой из которых означает принадлежность данного кода к выбранной группе запроса.Каждая схема 2. анализа ,1= - 1, , гп) содержит элементы И 5 - 8, ИЛИ-НЕ 9 ,и 1 О, И - НЕ 11, И2, триггер 13, элемент ИЛИ 14 и триггер 15. Триггеры 13 и 15, а также регистры 1,1, , 1.гп+1 ,устанавливаются предварительно в нуль сигналом с выхода Уст. 0 блока управле,ния (фиг. 2).Каждая схема 3.1 сравнения (1=1, , гп) содержит элемент ИЛИ-НЕ 16, элементы ИЛИ 17, И 18, ИЛИ 19, И 20, ИЛИ-НЕ 21, ИЛИ 22, И 23, ИЛИ 24, И 25 и 26. Выход элемента И 26 является 1-м выходом устройства (фиг. 3).Блок 4 управления (фиг. 4) образуют генератор 27 тактовых импульсов, элемент И 28, вычитающий счетчик 29, элемент НЕ 30, регистр 31 запроса, триггер 32 и элемент 33 задержки. Входами блока 4 управления являются вход 34, на который подается сигнал Гуск устройства, вход двухразрядного кода запроса, по которому устанавливается регистр 31, а также вход Уст. О, по которому устанавливается в единичное состояние триггер 32, и с его прямого выхода выдается единичный сигнал Уст. 0, после чего через элемент 33 задержки этим же сигналом триггер 32 сбрасывается в нуль. Выходом блока 4 управления также является шина Окончаниеединичный сигнал на которой свидетельствует об окончании работы устройства.тов И б и 8 равен единице, если соответствующие разряды кода 1-го числа больше одноименных разрядов контрольного кода, и нулю в противном случае.Если старший разряд )-го кода больше 55 старшего разряда контрольного кода, то навыходе второго элемента И 8 формируется сигнал единицы, и если второй по старшешинству разряд )-го кода равен одно 5 О 5 20 25 ЗО 3 ) 40 45 В исходном состоянии на регистре 1. (фиг. 1) хранится код контрольного числа Х=(х, , х(, где х, - значение )-го = 1, , и) разряда кода контрольного числа. Числа А;=(ас, , а,), где а значение )-го разряда -го числа, предварительно заносятся на регистры 1.2, 1 лп+1 для последующего сравнения с числом Х. Триггеры 3 и 15 схем 2.1, , 2 гп анализа установлены в нуль. На счетчике 29 находится код числа сдвигов, необходимых для сравнения кодов (установочный вход счетчика 29 на фиг. 4 не показан).Устройство работает следующим образом.На вход 34 поступает сигнал запуска, после чего сигналы с выхода генератора 27 тактовых импульсов через элемент И 28, на третий вход которого подается единичный сигнал с выхода элемента НЕ 30, могут поступать на входы регистров 1.1, , 1.гп+ 1 для сдвига содержимого регистров на два разряда в сторону старц:их разрядов. Предварительно в устройстве присходит анализ первых двух старших разрядов. Для этого на схемах 2.1 (1= 1, , гп) происходит одновременное суммирование по гное 2 двух старших одноименных разрядов кодов сравниваемых чисел Лг с двумя старшими разрядами контрольного числа Х на элементах И 5, 6 и ИЛИ-НЕ 9 и элементах И 7, 8 и ИЛИ-НЕ 10, при этом результаты сложения по п 1 ос(2 поступают на входы элемента И-ЯЕ 11 соответствующей схемы сравнения. Сигнал на выходе элемента И-НЕ 11 равен нулю, если два старших разряда 1-го числа равны соответствующим разрядам контрольного числа, и равен единице в противном случае. Если сигнал на выходе элемента И-НЕ 11 равен нулю, то триггер 13 остается в исходном нулевом состоянии. Далее с выхода генератора 27 импульс сдвига через элемент И 28 поступает на входы регистров 1.1, , 1.гп+ 1, после чего происходит сдвиг содержимого этих регистров на два разряда; процесс сравнения кодов повторяется. Сигнал с инверсного выхода триггера 13 поступает на входы элементов И б и 8 и на вход элемента И-НЕ 11, запрещая дальнейшее сравнение, если триггер 13 установится в единичное состояние.На вторые входы элементов И 6 и 8 поступают прямые значения (и -) -х и п-х разрядов )-х = 1, , гп) кодов и обратные значения (ив 1)-х и и-х разрядов контрольного кода. Сигнал на выходах элемен51015 20 25 30 35 40 45 50 55 именному разряду контрольного кода, то на выходе элемента ИЛИ-НЕ 10 формируется сигнал единицы, который поступает на вход элемента И 12. В результате на выходе элемента ИЛИ 14 формируется сигнал единицы, который устанавливает триггер 5 в единичное состояние. Если значение двух очередных разрядов )-го кода больше или меньше значений двух одноименных разрядов контрольного кода, то на выходе элемента И-НЕ 11 устанавливается сигнал единиць 1, который устанавливает триггер 13 в единичное состояние. Процесс сравнения кодов повторяется до тех пор, пока содержимое регистров 1.1, , 1 дп+1 не будет сдвинуто ( - 1) раз (этот код записывается перед работой устройства в счетчик 29, установочный вход не показан). Как только на вычитающем счетчике 29 появится нулевое состояние, о чем свидетельствует единичный сигнал этого состояния, который подается на вход элемента НЕ 30, на выходе последнего появляется низкий сигнал, который поступает на третий вход элемента И 26 и запрещает дальнейшую подачу сигналов сдвига. Кроме того, единичный сигнал с выхода счетчика 29 подается на выходную шину Окончание устройства. Код результата сравнения, снимаемый с прямых выходов триггеров 13 и 15, поступает на схемы 3.1 сравнения. Для идентификации равных, меньших или больших кодов по отношению к кодам, хранящимся на регистрах 1.1, , 1.гп+1, с выхода регистра 31 на схемы 31 сравнения поступает двухразрядный код запроса. Если код запроса равен коду на выходах триггеров 13 и 15, то на выходе элемента И 26 устанавливается сигнал логической единицы, в противном случае - нуль.Значение кодов запроса следующее:00 - контрольный код равен сравниваемому коду;10 - контрольный код меньше сравниваемого кода;11 - контрольный код больше сравниваемого кода.Схема 3сравнения работает следующим образом.Пусть, например, на триггерах 13 и 15 хранятся коды единиц, а на регистре 31 находится код 11, тогда на выходе элемента ИЛИ-НЕ 16 появляется сигнал логического нуля, который поступает на входы элементов ИЛИ 1 и 19, на вторые входы которых поступают сигналы с прямого выхода триггера 13 и прямого выхода триггера (не показан) первого разряда регистра 31 запроса соответственно. Следовательно, на выходах элементов ИЛИ 17 и 19 устанавливаются сигналы логической единицы, которые поступают соответственно на входы элементов И 18 и 20 и элементов 23 и 25. На вторые входы элементов И 18 и 20 поступают сигналы логических единиц с выхода триггера 15 и выхода триггера второго разряда регистра 31 запроса соответственно. В результате на выходах элементов И 18 и 20 устанавливаются высокие потенциаль., которые поступают на входы элемента ИЛИ-НЕ 21 и элемента ИЛИ 22 с выхода элемента И 8, а на вход элемента ИЛ И 24 - с выхода элемента И 20. Следовательно, на выходе элемента ИЛИ-НЕ 2 появляется низкий потенциал, который поступает на первые входы элементов ИЛИ 22 и 24, на вторые входы которых поступают сигналы с выходов элементов И 8 и 20 соответственно. В результате на выходах элементов ИЛИ 22 и 24 устанавливаются сигналы логической единицы, которые поступают на первые входы элементов И 23 и 25, на вторые входы которых поступают высокие потенциалы с выходов элементов ИЛИ 7 и 19 соответственно. Далее на выходах элементов И 23 и 25 появляются высокие потенциалы, которые поступают на входы элемента И 26, после чего на выходе схемы 3.1 сравнения появляется сигнал логической единицы, который поступает на выход устройства. Если код запроса не равен коду на выходах триггеров 13 и 5, то на выходе соответствующей схемы сравнения устанавливается сигнал логического нуля. Сигналом окончания работы устройства является единичный сигнал с выхода счетчика 29, который возникает при нулевом состоянии счетчика 29 и подается на выходную шину Окончание. Пример. Пусть заданы контрольный код 11101100 и сравниваемые коды 11101100, 11111101, 11011110, которые заносятся на регистры 1.1, , 1.4 соответственно. Триггеры 13 и 15 установлены в нулевое состояние. Для организации сравнения кодов необходимо выполнить три дополнительных сдвига кодов, поэтому код числа 3 устанавливается на счетчике 29.В результате всех анализов триггеры 13 и 15 в соответствующих схемах 2.1, , 2.3 анализа установлены в следующие состояния: в схеме 2.1 - в состояние 00; в схеме 2.2 -- в состояние 11 и в схеме 2 3 -- в состояние 1 О. Далее эти сигналы поступают на входы соответствующих схем 3.1, , 3.3 сравнения. В зависимости от кода запроса на двухразрядном регистре 31 запроса возбуждаются соответствующие выходные шины устройства. Так, при коде 00 на регистре 31 воздуждается первая выходная шина (код, равный контрольному), при коде 10 - третья выходная шина (код, меньший контрольного), при коде 11 - вторая выходная шина (код, больший контрольного).Формула изобретения1. Устройство для сортировки массивов чисел, содежащее и-разрядный сдвиговый регистр контрольного кода, пгп-разрядных сдвиговых регистров контролируемых кодов, гп схем анализа, причем первые входы ре гистра контрольного кода и регистров контролируемых кодов соединецы.с первым выходом Установка в О блока управления, вторые входы регистров соединены с кодовой шиной чисел, а третьи входы регист ров соединены с вторым выходом Сдвиг блока управления, первые входы схем анализа соединены с первым выходом Установка в О блока управления, второй вход схемы анализа соединен с инверсным выходом триггера (и 1) -го разряда 1-го (1=1, , гп) регистра контролируемого кода, третий вход схемы анализа соединен с прямым выходом триггера 1 и+1) -го разряда регистра контролируемого кода, четвертый вход схемы анализа соединен с прямым выходом триггера (и-.го разряда -го регистра контрольного кода, пятый вход схемы анализа соединен с инверсным выходом триггера и-го разряда регистра контролируемого кода, шестой вход схемы анализа соединен с инверсным выходом трипера и-го разряда -го регистра контролируемого кода, седьмой вход схемы ана. лиза соединен с прямым выходом триггера и-го разяда регистра контрольного кода, восьмой вход схемы анализа соединен с инверсным выходом триггера и-го разряда регистра контрольного кода, девятый вход схемы анализа соединен с прямым выходом триггера и-го разряда 1-го ре истра контролируемого кода, отличающееся тем, чтос целью расширения функциональных возможностей, в него введены гп схем сравнения и блок управления, причем первый и второй входы схем сравнения соединены с третьим и четвертым выходами блока управления соответственно, третий и четвертый входы схем сравнения соединены с первым и вторым выходами схемы анализа соответственно, первый вход блока управления является входом установки устройства в исходное состояние, второй и третий входы блока управления являются входами поступления кода запроса, четвертый вход блока управления является входом Пуск устройства.2. Устройство по п. 1, от,гглнающееся тем, что схема анализа содержит пять элементов И, два двух входовых элемента ИЛИ-НЕ, элемент И-НЕ, трехвходовый элемент ИЛИ и два триггера. причем первый и второй входы первого элемента И соединены с вторым и третьим входами схемы анализа соответственно, первый и вто. рой входы второго элемента И соединены с четвертым и пятым входа ли схемы анализа соответственно, а третий вход соединен с инверсным выходом первого триггера, третьим входом элемента И-НЕ и третьим входом четвертого элемента И, первый и второй входы третьего элемента И соединены с шестым и седьмым входами схемы анализа соответственно, первый и второй входы четвертого элемента И соединены с восьмым и девятым входа.ли схемы анализа соответственно, выход первого элемента И соединен с первым входом первого элемента ИЛИ-НЕ, второй вход которого соединен с выходом второго элемента И и первым входом пятого элемента И, первый вход второго элемента ИЛИ-НЕ соединен с выходом третьего элемента И, а второй вход соединен с выходом четвертого элемента И и третьим входом элемента ИЛИ, выход первого элемента ИЛИ-НЕ соединен с первым входом элемента И-НЕ, второй вход которого соединен с выходом второго элемента ИЛИ-НЕ и вторым входом пятого элемента И, выход элемента И-НЕ соединен с единичным входом первого тригге ра, нулевой вход которого соединен с первым входом схемы анализа и нулевым входом второго триггера, выход пятого элемента И соединен с первым входом элемента ИЛИ, второй вход которого соединен с прямым выходом второго триггера, выход элемента ИЛИ соединен с единичным входом второго триггера. прямые выходы первого и второго триг геров соответственно соединены с первым и вторым выходами схемы анализа.З 0 3. Устройство цо п. 1, отличающеесятем, что схема сравнения содержит два двухвходовых элемента ИЛИ-НЕ, четыре двухвходовых элемента ИЛИ, пять двухвходовых элементов И, причем первый вход первого элемента ИЛИ-НЕ соединен с первым входом схемы сравнения, второй вход первого элемента ИЛИ-НЕ соединен с третьим входом схемы сравнения и вторым входом первого элемента ИЛИ, первый вход которого соединен с выходом первого элемента ИЛИ-НЕ и первым входом второго элемента ИЛИ, второй вход которого соединен с первым входом схемы сравнения, выход первого элемента ИЛИ соединен с вторым входом первого элемента И и вторым входом третьего элемента И, первый вход первого элемента И соединен с четвертым входом схемы сравнения, первый вход третьего элемента И соединен с выходом третьего элемента ИЛИ, первый вход второго элемента И соединен с выходом второго элемента ИЛИ и вторым входом 50 четвертого элемента И, первый вход которого соединен с выходом четвертого элемента ИЛИ, второй вход второго элемента И соединен с вторым входом схемы сравнения, первый вход четвертого элемента ИЛИ соединен с выходом второго элемен та ИЛИ-НЕ и первым входом третьегоэлемента ИЛИ, выход первого элемента И соединен с первым входом второго элемента ИЛИ-НЕ и вторым входом третье 1403059го элемента ИЛИ, выход второго элемента И соединен с вторым входом второго элемента ИЛИ-НЕ и вторым входом четвертого элемента ИЛИ, выход третьего элемента И соединен с первым входом пятого элемента И, второй вход которого соединен с выходом четвертого элемента И, выход пятого элемента И является 1-м выходом устройства.4. Устройство по п. 1, отличающееся тем, что блок управления содержит генератор тактовых импульсов, трехвходовый элемент И, (1 ор и)-разрядный вычитающий счетчик, элемент НЕ, регистр кода запроса, триггер и элемент задержки, причем выход генератора тактовых импульсов соединен с первым входом элемента И, второй вход которого соединен с четвертым входом блока управления Пуск, а третий вход соединен с выходом элемента НЕ, выход элемента И соединен с вторым выходом блока управления Сдвиг и входом вычитающего счетчика, выход которого соединен с входом элемента НЕ и пятым выходом блока управления Окончание, первый и второй входы регистра запроса соединены с вторым и третьим входами блока управления, а первый и второй выходы соединены с третьим и четвертым выходами блока управления соответственно, единичный вход триггера соединен с первым входом блока управления Установка в О, а прямой выход триггера соединен с первым выходом Установка в О блока управления н через элемент задержки с нулевым входом триггера.1403059ЮыхЗЕл.4Составитель Н. Васильев Редактор Л. Огар Текред И. Верее Корректор А. Тяско Заказ 2861,40 Тираж 704 Подписное ВНИИПИ Гос 1 дарственного комитета СССР по делам изобретений и открытий113035, Москва, Ж 35, Раушская наб., д. 4,5Г 1 роизводственн-полиграфическо предприятие, г. Ужгород, ул. Проектная, 4