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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИН Г 7/08 АНИЕ ИЗ РЕТЕНИ ТЕЛЬСТВ ВТОРСИОМ 2/24-248485. Бюлрашко5(088.8кое свидл. С 06(21) 37119 (22) 16.03 (46) 15.09 (72) А.НМ (53) 681. 3 (56) Автор йд 637810,Авторск Р 993251,ф 34 етельство Г 7/08, 1 ельство СС Р 7/08, 1 е свиде л. С Об ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИ(54)(57) УСТРОЙСТВО ДЛЯ СОРТИРОВКИЧИСЕЛ, содержащее входные счетчики,выходной счетчик, группу элементов ИЛИ, группу формирователей импульсов, группу выходных элементов И, группу запрещающих элементов И, элемент ИЛИ, входной элемент И, первый вход которого подклю.чен к. входу тактовых импульсов устройства, а выход соединен с суммиру.ющим входом выходного счетчика ипервыми входами запрещающих элементов И группы, выходы которых соединены с вычитающими входами соответ"ствующих входных счетчиков, выходыкоторых поразрядно подключены к входам соответствующих элементов ИЛИгруппы, выходы которых соединены свходами соответствующих формирователей импульсов группы, вторыми входами соответствующих запрещающих элементов И группы и с соответствующими входами элемента ИЛИ, выходывыходного счетчика поразрядно соединены с информационными входамивыходных элементов И группы, выходыкоторых являются информационнымивыходами устройства, о т л и ч а -ю щ е е с я тем, что, с целью повышения достоверности при сортировке ЯО 179317 равных чисел, в него введены первыии второй триггеры, регистр, преобразователь числа единиц в двоичныйкод, счетчик равных чисел, первый ивторой элементы ИЛИ-НЕ, первый ивторой элементы И, формирователь импульса сброса, элемент задержки,причем выходы формирователей импульсовгруппы соединены с соответствующимиразрядными входами регистра, выходыразрядов которого соединены с входами первого элемента ИЛИ ви с соответствующими входами преобразовате.ля числа единиц в двоичный код, выхо.ды которого соединены с соответствующими информационными входами счетчика равных чисел, выходы которогосоединены с входами второго элемента ИЛИ-НЕ, выход которого соединенчерез формирователь импульса сбросас синхронизирующим входом первоготриггера и входами установок в нулевое состояние регистра и второготриггера, информационный вход которого соединен с входом логическойединицы устройства, инверсный выходвторого триггера соединен с первымвходом первого элемента И, второйвход которого соединен с выходом первого элемента ИЛИ-НЕ и через элементзадержки - с вторым входом входногоэлемента И, третий вход которого соединен с прямым выходом. первого триггера, информационный вход которогосоединен с выходом элемента ИЛИ, входтактовых импульсов устройства подключен к третьему входу первого элемента И и первому входу второго элемента И, второй вход которого соединен спрямым выходом второго триггера, а1179317 выход является выходом разрешения выдачи и подключен к управляющим входамвыходных элементов И группы и вычита-.ющим входам счетчика равных чисел,Изобретение относится к вычислительной технике и может быть использовано в устройствах обработки сигналов, в системах связи и др.Цель изобретения - повышение достоверности при сортировке равных чисел.На фиг.1 приведена функциональнаясхема предлагаемого устройства нафиг.2 - временная диаграмма работыэлементов устройства.Таблица состояния выходов преобразователя числа единиц в двоичный кодв зависимости от состояния его входов(на примере пяти входов) приведена в 15табл.1,Устройство содержит входные счетчики 11 выходной счетчик 2,группу элементов ИЛИ 31 ф Зфэлемент ИЛИ 4, триггер 5, группу запрещающих элементов И 6, , 61,входной элемент И 7, группу выходныхэлементов И 8 , , 8, группу формирователей 9 , , 9 щ импульсов,регистр 10, элемент ИЛИ-НЕ 11, элемент 12 задержки, элемент И 13, триггер 14, преобразователь 15 числа единиц в двоичный код, счетчик 16 равныхчисел, элемент ИЛИ-НЕ 17, элемент И18, формирователь 19 импульса сброса, 30тактовый вход 20 устройства, информационные выходы 21 устройства, выход 22 разрешения выдачи.Назначение элементов устройстваследующее. Счетчики 1ф 1 д сл.жат для временного запоминания исходных сортируемых чисел. Элементы ИЛИ31, , 3, служат для фиксированиянулевого состояния соответствующегосчетчика 11 у 1 ппРичем ПРи НУ 40левом содержимом счетчика 1 .1 щна выходе соответствующего элемента ИЛИ 3 1,, 3" нулевой потенциал. Выходной счетчик 2 служит дляформирования кода на выходах 21 устройства при сортировке чисел. Элемент ИЛИ 4 и триггер 5 служат для вход разрешения записи которого подключен к выходу первого элемента И исинхронизирующему входу второго триггера. фиксирования нулевого состояния всех счетчиков 1, , 1 щ в конце сортировки и выработки запрещающего потенциала по второму входу элемента И 7 для дальнейшей блокировки тактовых импульсов. Формирователи 9 , , 9 д и регистр 10 служат для фиксирования количества счетчиков 1 , 1, установленных в нулевое состояние в последнем цикле. Преобразователь 15 служит для преобразования числа установленных разрядов регистра 10 в единичное состояние в двоичный код (табл.1). Счетчик 16 равных чисел служит для подсчета выдаваемых устройством синхроимпульсов. Элемент ИЛИ-НЕ 17 служит для фиксирования нулевого состояния счетчика 16. Элемент И 13 и элемент ИЛИ-НЕ 11 служат для выработки сигнала перезаписи информации с выходов преобразователя 15 в счетчик 16 равных чисел и установки триггера 14 в единичное состояние. По первому и второму входам элемента И 13 осуществляется инверсия поступающих сигналов. По синхровходу триггера 14 осуществляется инверсия входного сигнала. Элемент И 18 служит для выработки синхросигнала на втором выходе устройства и вычитающих импульсов для счетчика 16 равных чисел. Элемент задержки 12 служит для обес" печения устойчивой перезаписи информации в регистр, 10 путем задержки сигнала запрета по третьему входу входного элемента И 7 после срабатывания первого элемента ИЛИ-НЕ 11 (появление нулевого потенциала), причем величина задержки озд, элемента 12 выбирается например, иззцД где ото длительность тактового импульса. Фор мирователь 19 служит для формирования сигнала установки в нулевое состояние второго триггера 14, регистра 10 и синхросигнала для перво 1179317го триггера 5, причем сигнал на выходе формирователя 19 задержан относительно переднего фронта единичного сигнала с выхода элемента ИЛИ-НЕ 17лна время оа , которое определяется, например, исходя из устойчивой работы устройства из соотношениял лтц 2 ти" ЗаД 2Временные интервалы между тактовыми О импульсами составляют при этом, надпример, изад 2Исполнение элементов устройства может быть, например, следующее.Счетчики, триггеры, регистр, эле менты И, ИЛИ, ИЛИ-НЕ, группы элемен 1 тов И являются типовыми, например, для цифровых интегральных схем ТТ. серий 133, К 155, 130, К 131, 530, К 531, К 555. Преобразователь 15 реали зуется, например, на базе типовых логических элементов с учетом таблицы состояний. Формирователи 9 9, 19 могут быть реализованы, например на базе типовых формирователей 25 К 155 АГЗ с учетом логики функционирования и временных параметров, приведенных в материалах заявки.Устройство работает следующим образом. 30Во входные счетчики 11, , 1заносятся сортируемые числа. Регистры 10 и счетчик 16 обнулены, триггер 14 установлен в нулевое состояние, при этом на инверсном выходе 35 последнего - потенциал логической единицы, Триггер 5 устанавливается в единичное состояние, при этом с его выхода на второй вход элемента И 7 поступает единичный потенци ал (цепи начальной установки элементов устройства на фиг.1 не показаны). В исходном состоянии на выходах элементов ИЛИ-НЕ 1.1 и 17 - единичные потенциалы, поскольку регистр 45 10 и счетчик 16 обнулены, а на выходах элементов ИЛИ 3 Зщ- единичные потенциалы, поскольку содержимое счетчиков 1, , 1, не равно "0", и следовательно, на первые 50 входы группы запрещающих элементов И 6,6 и на второй и третий.входы элемента И 7 поступают разрешающие единичные потенциалы.На вход 20,устройства подаются 55 тактовые импульсы (фиг.2 д), которые через элемент И 7 поступают на суммирующий вход выходного счетчика 2 и через группу элементов И 616на вычитающие входы счетчиков 11 . При этом содержимое счетчиков1 1 щ уменьшается, а выходногосчетчика 2 - увеличивается,При поступлении на вход 20 устрой.ства количества тактовых импульсов,соответствующего минимальному числу(или нескольким числам) из сортируемых чисел в счетчиках 1 1 содержимое соответствующего счетчика1 (или нескольких счетчиков, 1),Ув котором (в которых) было записайоминимальное число, становится равным ."0. На выходе соответствующих элементов ИЛИ 3 появляется нулевой потенциал (фиг.2 Ы), закрывающий соответствующие элементы И б группы, блокируя дальнейшее поступление вычитающих импульсов на входы тех счетчиков 1 в которых содержимое сталоравным 110". На выходах формирователей 9;, подключенных к тем элементам ИЛИ 3 на которых выставился нулевой потенциал, появляются импульсызаписи "1" в регистр 10 (фиг.22),причем количество записанных "1"по всем разрядам регистра 10 соответствует числу счетчиков 1, установленных в нулевое состоянйе. Срабатывает элемент ИЛИ-НЕ 11, на выходе которого выставится нулевой полтенциал, Далее через1 ад, срабатывает . элемент 12 задержки и на третьем. входе элемента И 7 выставляется запрещающий нулевой потенциал, по которому поступление тактовых импульсов на выход элемента И 7 блокируется (фиг.25). По концу тактового импульса срабатывает элемент И 13, на выходе которого появляется импульс перезаписи двоичного кода числа, например 3, установленных в нулевое состояние счетчиков 1, в счетчик 16 равных чисел по его синхровходу (фиг.2 е). По концу сигнала перезаписи (поскольку по синхровходу триггера 14 осуществляется инверсия сигнала) триггер 14 устанавливается в единичное состояние, так что с его инверсного выхода на третий вход элемента И 13 поступает запрет, а с его прямого выхода на второй вход элемента И 18 - разрешение (фиг.2 я). На выходе элемента ИЛИ-НЕ 17 уста- навливается нулевой потенциал. Тактовый импульс с первого входа элемента И 18 поступает на его выход(фиг,2) и далее - на вычитающий вход счетчика 16, на вторые входы группы элемент-ов И 8, , 8 и и на второй выход 22 устройства. При этом с выхода счетчика 2 на выход 21 устройства поступает код минимального числа (чисел). По следующему тактовому импульсу также поступает с выхода элемента И 18 строб-импульс о выдаче на выход 21 устройства такого же содержимого счетчика 2 (фиг.2. Поскольку в счетчике 16 было записано число 3", то с поступлением с выхода элемента И 18 третьего вычитающего импульса счетчик 16 устанавливается в нулевое состояние,срабатывает второй элемент ИЛИ-НЕ 17 и на его выходе выставляется единичный потенциал (фиг.2 и). Таким образом, на выход 21 устройства поступает код минимальных чисел столько раз, сколько было записано в счетчики 1 , 1 этих равных чисел.По переднему фронту (О-ф 1) сигнала с выхода элемента ИЛИ-НЕ 17 запускается формирователь 19 через лна выходе которого появляется импульс (фиг.2 к), по которому триггер 14 сбрасывается в нулевое состояние и триггер 5 устанавливается в то же состояние, что и на выходе второго элемента ИЛИ 4, сигнал с которого поступает на информационный З -вход триггера 5. Поскольку не все счетчики 11, , 1 обнулились в первом циклс работы устройства, то на некоторых входах элеменВходы кодопреобразователя 1513 4 та ИЛИ 4 - единичные потенциалы ина выходе последнего - также единичньк потенциал. Триггер 5 поэтому неизменяет по синхроимпульсу с выходаформирователя 19 своего состояния(единичного).По следующему тактовому импульсуначинается следующий цикл определе О ния чисел, следующих по рангу за минимальными в порядке возрастания.Цикл повторяется аналогично предыдущему: определяется количество установленных счетчиков 1 ,, 1 в ну левое состояние в последнем цикле,а затем на выход 21 поступает кодэтих чисел с выхода счетчика 2 столько же раз, Причем коды сопровождаютсясинхроимпульсами с выхода 22 устрой ства. Циклы сортировки повторяются дотех пор, пока все записанные числа всчетчиках 11, , 1 щ не будут отсортированы, т.е. все счетчики 1,1 обнуляются. В конце последнегоцикла элемент ИЛИ 4 выставляет насвоем выходе нулевой потенциал, а попереднему фронту сигнала с выхода формирователя 19 триггер 5 устанавливается в нулевое состояние и блокирует 30 дальнейшее поступление тактовых импульсов через элемент И 7.Сортировка чисел окончена. Для проведения сортировки чисел З 5 устройством, начиная с максимальногочисла, достаточно записать числа во входные счетчики 1.1 и в обратном коде и результат получать с нулевых выходов выходного счетчика 2. Выходы кодопреобразователя 15/50 Тираж 710ВНИИПИ Государственного комитпо делам изобретений и откр 113035, Москва, Ж, Раушская н Заказ 5676 4/5 б.,Филиал ППП "Патент", г.ужгород, ул.Проектная,Составитель Е.Ивановаимохина Техред Т.фанта Корректор М.Самборская