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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИН 51)4 С ГОСУДАРСТ 8 ЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ ОБРЕТЕНИ ОПИСН АВТО МУ СВИДЕТЕЛЬСТВУ У 44(54) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ЧИСЕЛ(57) Изобретение относится к областивычислительной техники и может бытьиспользовано в информационно-поисковых системах и системах статистическойобработки данных. Цель изобретениярасширение функциональных возможностей за счет интегрального и дифференциального распределения чисел.Устройство содержит входной регистр144 5, регистр опроса 3, блок памяти 6, сумматоры 14 и 15, регистры суммы 16 и 17, вычитатель 18 и элементы управления. Очередной пакет данных через входной регистр 5 поступает на адресный вход блока памяти 6, из которого читается число, и поступает на входы сумматора 14, Это число суммируется с единицей, постоянно находящейся на втором входе этого сумматора, Результат сумрак запомнится на регистре суммы 16 и далее запишется в блок памяти 6 по этому адресу. Таким образом, в блоке памяти 6 подсчитывается количество чисел, пришедших по каждому из значений адресов из очередного пакета данных. Опрос информации происходит через регистр опроса 3 по порядку, начиная со значения нуля. По адресу текущего числа опроса из блока памяти 6 читается текущее значение дифференциальной функции. Одновременно это же значение поступает на входы первой группы сумматора 15, где скла 1385дывается с предыдущим значением, которое находится на его входах второй группы. Результат суммы запоми-.нается на регистре 17 и далее поступает на входы вычитаемого вычитателя 18. Данная сумма вычитается из числа, равного количеству чисел, находящихся в пакете данных. Это текущее значение интегральной функции, После каждого опроса текущих значений дифференциальной и интегральной функций в ячейку памяти блока 6, откуда проводился опрос, записывается нуль. Таким образом, функция дифференциального распределения показывает, какая доля из общего количесФ- ва зафиксированных величин приходит ся на один из выбранных уровней (функция повторяемости). Функция интегрального распределения показывает, какая доля из общего количества чисел приходится на величины выше заданного уровня (функция обеспеченности). 6 ил.Изобретение относится к вычислительной технике и может быть использовано в информационно-поисковых системах и системах статистической обработки данных.Целью изобретения является расширение функциональных возможностей за счет интегрального и дифференциального распределения чисел.На фиг. 1 представлена схема устройстваф на фиг. 2 - схема формирователя режима.На фиг. 3-6 временные диаграммы работы устройства.Устройство содержит генератор 1 тактовых импульсов, счетчик 2 опроса, регистр 3 опроса, счетчик 4 цикла, входной регистр 5, блок 6 памяти, триггер 7 начальной установки, ,элементы ИЛИ 8-10, элемент И 11, формирователь 12 имрульсов, триггер 13 выбора регистра, сумматоры 14 и 15, регистры 16 и 17 суммы, вычитатель 1,8. Формирователь 12 импульсов содержит элемент ИЛИ 19, элемент 20 задержки, элемент И-НЕ 21Устройство работает следующим5 образом.Начальная установка (см. фиг. 3).При первоначальном включении илипри подаче отрицательного сигналаначальной установки "НУ" срабатываеттриггер 7 начальной установки. Сигналом "НУ" через второй элементИЛИ 9 обнуляется счетчик 2 опроса ичерез третий элемент ИЛИ 10 устанавливается триггер 13 выбора регистрав положение раэрешающего работу регистра 3 опроса, так как на первомвыходе триггера 13 устанавливаетсялог. 1, Потенциал второго выходатриггера 13 выбора регистра лог. О,запрещающий работу входного регистра 5 (регистр находится в высокоимпедансном состоянии, что соответствует состоянию оборванной цепи) идержит в обнуленном состоянии первый1441385 регистр 16 суммы, выход которогосвязан с информационным входом блока6 памяти.На первом выходе триггера 7 начальной установки устанавливаетсялог. 1, которая разрешает работу генератора 1 тактовых импульсов . Лог.Овторого выхода триггера 7 начальнойустановки через элемент И 11 устанавливает блок 6 памяти в режим записи.Сигналы с генератора 1 тактовыхимпульсов через первый элемент ИЛИ 8поступают на счетные входы счетчика2 опроса и регистра 3 опроса. Пофронту синхросигнала записываетсяинформация с информационного выходасчетчика 2 опроса в регистр 3 опроса, а по спаду этого же импульсаинформационный выход счетчика 2 опроса увеличивается на единицу. Такимобразом, информация с информационного выхода счетчика 2 опроса черезрегистр 3 опроса поступает на адресный вход блока 6 памяти, в котором по следующим синхросигналам,идущим от генератора 1 тактовых импульсов, перебираются адреса ячеек,начиная с нулевого, и тем самым в 30массив памяти записываются нули. Блок6 памяти обнуляется. По окончаниицикла обнуления памяти на втором выходе счетчика 2 опроса формируетсяотрицательный импульс, который черезвторой элемент ИЛИ 9 устанавливаетэтот же счетчик в начальное состояние. Этим же сигналом сбрасываетсятриггер 7 начальной установки, который запрещает работу генератора 1тактовых импульсов . Также сбрасывается счетчик 4 циклов и триггер 13выбора регистра, при коТором разрешена работа входного регистра 5 ипервого регистра суммы 16. Регистр3 опроса устанавливается в высокоимпедансное состояние . В обнуленномсостоянии удерживается второй регистр17 суюи. Блок памяти 6 устанавливается в режим чтение-.запись информации. На этом подготовка устройствак работе заканчивается,51 О 0 сАсМ,15 20 25 35 40 45 считывается, сколько чисел однойградации состоит в ряду данного цикла.По окончании цикла приема и обра ботки входной информации счетчик 4 50 цикла, подсчитав количество принятыхзначений в пакете (М-значений), формирует отрицательный импульс, который через третий элемент ИЛИ 10устанавливает первый выход триггера13 выбора регистра в состояние лог.1,а второй выход - в состояние лог.О.Разрешена работа регистра 3 опросаи второго регистра 17 суммы. Входнойрегистр 5 устанавливается в высокоВ схеме первый элемент ИЛИ 8 управляется высокими уровнями входных сигналов, второй элемент ИЛИ 9 и третий элемент ИЛИ 10 управляются низкими уровнями входных сигналов (ИЛИ по-нулю). Пикл приема информации (см.фиг.4),Входная информация "ИНФ" в двоичном преДставлении одновременно с синхроимпульсами "СИ" фиксируется по фронту "СИ" во входном регистре 5 и далее поступает на адресный вход блока 6 памяти. Количество поступающих чисел (пакет данных) определяет счетчик 4 цикла, и эта величина равна И. Текущее А; -е число может принимать значение от 0 до М, т.е. гдеА=1,2, ЗЙ,М - максимальное А,-е число(определяет объем памяти),ИсМ.Из блока 6 памяти по адресу поступившего значения читается число(на управляющем входе блока 6 памятив данный момент положительный потенциал), которое поступает на первыйвход (первое текущее слагаемое) первого сумматора 14 текущего числа.Это число суммируется с единицей,постоянно находящейся на втором входе этого же сумматора (второе слагае мое). Далее по спаду сигнала "СИф результат сумма запоминается на первом регистре 16 сумма и затем по отрицательному потенциалу, поступающему на управляющий вход блока 6 памяти,.записывается в ячейку памятипо этому же адресу и в этом же тактесннхроимпульса "СИ". Такой режимчтение-запись по данному адресу вданном такте "СИ" формируется на формирователе 12 импульсов через элемент И 11. Таким образом в блоке 6 памяти запоминается количество чисел, пришедших к каждому иэ значений адресов, т,е. в блоке 6 памяти под 5 144 импедансное состояние. И обнуленном состоянии удерживается первый регистр 16 суммы, который непосредственно соединен с информационным входом блока 6 памяти. Последний остается в режиме чтение-запись.Цикл опроса информации (см.фиг,5).По сигналу опроса "ОПР" через первый элемент ИЛИ 8 включается в работу счетчик 2 опроса, Через регистр 3 опроса производится чтение информации из блока 6 памяти, которое осуществляется следующим образом.При поступлении первого сигнала "ОПР" через первый элемент ИЛИ 8 по фронту сигнала в регистр 3 опроса записывается значение нуля, так как счетчик 2 опроса был обнулен в цикле приема информации и на его пер вом информационном выходе в данный момент находится нуль. По этому адресу из блока 6 памяти читается значение, соответствующее количеству чисел нулевой градации. Это первое значение дифференциальной функции. Одновременно это же значение из блока 6 памяти поступает на первый вход второго сумматора 15 текущего числа первое текущее слагаемое). Оно складывается с числом, которое находится на втором входе этого же сумматора (второе текущее слагаемое) . На втором входе сумматора 15 текущего числа в данный момент находится число нуль, так как второй регистр 17 суммы был обнулен в цикле приема информации, Результат суммы по спаду сигнала "ОПР" запоминается на втором регистре 17 суммы и поступает на первыи вход вычитателя 18. На вычитателе 18 поступившее значение суммы вычитается из числа Й, которое .постоянно находится на его втором входе (число И по значению равно количеству чисел в пакете данных). Это первое значение интегральной функции. В ячейку блока 6 памяти, из которой производился опрос дифференциального и интегрального значения, по спаду сигнала "ОПР" с некоторой задержкой отрицательным потенциалом записывается нуль, так как в данном цикле (в цикле опроса) в обнуленном состоянии удерживается первый регистр 16 суммы, выход которого непосредственно соединен с информационным входом блока 6 памяти. Таким образом, обнуление данной ячейки 1385 6блока 6 памяти происходит сразу после того, как были получены дифференциальная и интегральная Функции. Редим чтение-запись по данному адресув данном такте сигнала "ОПР" формирует формирователь 12 импульсов. Одновременно по спаду сигнала "ОПР" вданном такте навыходе счетчика 2 опроса устанавливается значение единицы. При поступлении второго сигналаОПР" по его фронту на регистре 3опроса запоминается значение единицы, Из блока 6 памяти читаетсь значение, соответствующее количеству чисел первой градации. Это второе значение дифференциальной функции. Одновременно это же значение суммируется на втором сумматоре 15 текущегочисла с первым значением дифференциальной функции, которое в данныймомент находится на втором входе этого сумматора, и по спаду сигнала"ОПР" запоминается на втором регист ре 17 суммы. Искомая сумма вычитается из .числа вычитателя 18. Это второе значение интегральной функции.Ячейка памяти, как и в предыдущемслучае, по данному адресу в данном ЗО такте сигналаОПР" обнуляется припомощи режима чтение-запись, сформированного Формирователем 12 режима.По спаду второго сигнала "ОПР" на выходе счетчика 2 опроса устанавливается число два. Аналогично получа".ются последуюшие значениядифференциальной и интегральной функций ианалогично происходит обнуление ячеек блока 6 памяти. Каждое значение 4 О диФференциальной и интегральнойФункций по каждому сигналу "ОПР" поступает на вход устройства с последующим выводом на печать, По окончаниицикла опроса (цикл опроса по значе нию равен М+1) на управляющем выходесчетчика 2 опроса формируется отрицательный сигнал, который через второй элемент ИЛИ 9 обнуляет сам себя.Счетчик 4 цикла также обнуляется иустанавливается я режиме приема информации, Триггер 13 выбора регистраустанавливается в положение, при котором работает входной регистр 5.Регистр 3 опроса информации переходит в высокоимпедансное состояниеУстройство готово к приему очередного пакета данных.Таким образом, если обозначитьколиче ство чисел, которое принимаетО (А ) = Р(А ) и показывает, какая доля из общегоколичества зафиксированных величинприходится на один из выбранных уровней (фуикцйя повторяемости). ЗначенияИ Р(А;) являются функцией, котораясоответствует закону интегральногораспределенияМв 15Р(Аф ) = Н - , Р(А; ),Ю з которая показывает, какая доля из общего количества чисел приходитсяна величины вышезаданного уровня 20(функция обеспеченности),Формирователь 12 импульсов представлен на фиг. 2Формирователь 12импульсов работает следующим образом(см. фиг. 6) . 25На первый или второй вход элемента 19 поступают импульсы. С инвертирующего выхода этого элемента сигналпоступает на первый вход элементаИ-НЕ 21, С неинвертирующего внхода 30элемента 19 сигнал через элемент 20,задержки поступает на второй входэлемента И-НЕ 21, На выходе элемента И-НЕ 21 формируется импульслог. О, который несколько задержанпо отношению к спаду входного сигнала. Формируется сигнал "Чтение-запись", который поступает на управляющий вход блока 6 памяти,Таким образом, по фронту сигнала"СИ" или "ОПР" по положительномупотенциалу на управляющем входе блока 6 памяти информация читается, поспаду сигнала "СИф или "ОПР" по потенциалу лог. О информация записивается в память, т.е. за один тактвходного сигнала происходит переключение сигнала "Чтение-запись" блока 6 памяти. 50Формула изобретения А;-я градация через П, то функцияР(А;) соответствует закону дифференциального распределения Устройство для сортировки чисел, содержащее генератор тактовых импульсов, счетчик опроса, блок памяти, два.блока сложения, элемент И и элемент ИЛИ, о т л и ч а ю щ е е с я тем, что, с целью расширения области применения за счет интегрального и.38 5 Ядифференциального распределения чисел, оно содера:ит триггер начальнойустановки, два элемента ИЛИ, триггервыбора регистра, два регистра суммы,вычитатель, счетчик цикла, входнойрегистр, регистр опроса, формирователь импульсов, причем вход установкив единичное состояние триггера начальной установки является входомначальной установки устройства исоединен с первыми входами первогои второго элементов ИЛИ,а прямой выход соединен с входом запуска генератора тактовых импульсов, выход которого соединен с первым входомтретьего элемента ИЛИ, второй входкоторого является входом опроса устройства, а выход соединен с первымвходом формирователя импульсов, ссинхровходами счетчика опроса,регистра опроса и первого регистра суммы, выходы разрядов которого соединены с входами вычитаемого вычитателя и входами первой группы первогосумматора, выходы суммы которогосоединены с информационными входамипервого регистра сумма, а входывторой группы соединены с информационными выходами блока памяти, выходами дифференциального распределения чисел устройства и с входамипервой группы второго сумматора,входы второй группы которого являютсявходами заданного числа устройства,а выходы суммы соединены с информационными входами второго регистрасуммы, выходы разрядов которого соединены с информационными входамиблока памяти, управляющий вход кото.рого соединен с выходом элемента И,первый вход которого соединен с выходом формирователя импульсов, авторой вход с инверсным выходомтриггера начальной установки, входустановки в "О" которого соединен свторым входом первого элемента ИЛИ,с выходом переполнения счетчика опроса, с входами установки в нулевоесостояние счетчика цикла и триггеравыбора регистра, вход установки вединичное состояние которого соединен с выходом второго элемента ИЛИ,второй вход которого ,соединен с вы ходом переполнения счетчика цикла,счетный вход которого является входом синхронизации устройства и соединен с вторым входом формирователяимпульсов, с входом синхронизации441385 фут, Ю 1 СИ Юх аур 6 ф, уюр.) 6(Ь.урн) ф ю 1 1 кИ и 1 13(дьюи 13 Оих.7 р гх. 4 Иа.)Ню стев знсцгнц 0 ПЮ/52 Тираж 704ВНИИПИ Государственного комитетапо делам изобретений и открытий113035, Москва, Ж, Раушская наб. одписно д. 4/5 Проект роиэводственно-полиграфическое предприятие, г. Ужгород