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

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

Иллюстрации

Показать все

Реферат

 

Изобретение относится к области вычислительной техники и может буть использовано в информационно-поисковых системах и системах статистической обработки данных. Цель изобретения - расширение функциональных возможностей за счет интегрального и дифференциального распределения чисел. Устройство содержит входной регистр

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК

„„SU„„144

А1 (51) 4 G 06 F 7/06

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (2 1) 4261405/24-24 (22) 12.06.87 (46) 30. 11.88. Вюл. У 44 (72) А.Ю.Ивакин, А.Г.Данилин и Н,П.Тульнев (5 3) 681. 325 (088. 8) (56) Авторское свидетельство СССР

У 1073770, кл. С 06 F 7/06, 1982.

Авторское свидетельство СССР

9 1277091, кл. G 06 F 7/06, 1985. (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 saдержки, элемент И-НЕ 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 onроса увеличивается на единицу. Таким образом, информация с информационного выхода счетчика 2 опроса через регистр 3 опроса поступает на адресный вход блока 6 памяти, в котором по следующим синхросигналам, идущим от генератора 1 тактовых импульсов, перебираются адреса ячеек, начиная с нулевого, и тем самым в 30 массив памяти записываются нули. Блок

6 памяти обнуляется. По окончании цикла обнуления памяти на втором выходе счетчика 2 опроса формируется отрицательный импульс, который через второй элемент ИЛИ 9 устанавливает этот же счетчик в начальное состояние. Этим же сигналом сбрасывается триггер 7 начальной установки, который запрещает работу генератора 1 тактовых импульсов . Также сбрасывается счетчик 4 циклов и триггер 13 выбора регистра, при коТором разрешена работа входного регистра 5 и первого регистра суммы 16. Регистр

3 опроса устанавливается в высокоимпедансное состояние . В обнуленном состоянии удерживается второй регистр

17 сумма. Блок памяти 6 устанавливается в режим чтение-.запись информации. На этом подготовка устройства к работе заканчивается.

1О

0 A M, 15

35

45 считывается, сколько чисел одной градации состоит в ряду данного цикла.

По окончании цикла приема и обра ботки входной информации счетчик 4

50 цикла, подсчитав количество принятых значений в пакете (N-значений), формирует отрицательный импульс, который через третий элемент ИЛИ 10 устанавливает первый выход триггера

13 выбора регистра в состояние лог.1, а второй выход — в состояние лог.О.

Разрешена работа регистра 3 опроса и второго регистра 17 суммы. Входной регистр 5 устанавливается в высокоВ схеме первый элемент ИЛИ 8 управляется высокими уровнями входных сигналов, второй элемент ИЛИ 9 и третий элемент ИЛИ 10 управляются низкими уровнями входных сигналов (ИЛИ по-нулю).

Пикл приема информации (см.фиг.4) .

Входная информация "ИНФ" в двоичном преДставлении одновременно с синхроимпульсами "СИ" фиксируется по фронту "СИ" во входном регистре

5 и далее поступает на адресный вход блока 6 памяти. Количество поступающих чисел (пакет данных) определяет счетчик 4 цикла, и эта величина равна N. Текущее А; -е число может принимать значение от О до И, т.е. где А= 1, 2, 3... °... 1 1ю

M — максимальное А;-е число (определяет объем памяти), И (М.

Из блока 6 памяти по адресу поступившего значения читается число (на управляющем входе блока 6 памяти в данный момент положительный потенциал), которое поступает на первый вход (первое текущее слагаемое) первого сумматора 14 текущего числа.

Это число суммируется с единицей, постоянно находящейся на втором входе этого же сумматора (второе слагае мое). Далее по спаду сигнала "СИ" результат cymar запоминается на первом регистре 16 сумма и затем по отрицательному потенциалу, поступающему на управляющий вход блока 6 памяти,.записывается в ячейку памяти по этому же адресу и в этом же такте сннхроимпульса "СИ". Такой режим чтение-запись по данному адресу в данном такте "СИ" формируется на формирователе 12 импульсов через элемент И 11. Таким образом в блоке

6 памяти запоминается количество чисел, пришедших к каждому иэ значений адресов, т.е. в блоке 6 памяти под5 144 импедансное состояние. И обнуленном состоянии удерживается первый регистр

16 суммы, который непосредственно соединен с информационным входом блока 6 памяти. Последний остается в режиме чтение-запись.

Цикл опроса информации (см.фиг.5).

По сигналу опроса "ОПР" через первый элемент ИЛИ 8 включается в работу счетчик 2 опроса. Через регистр

3 опроса производится чтение информации из блока 6 памяти, которое осуществляется следующим образом.

При поступлении первого сигнала

"0IIP" через первый элемент ИЛИ 8 по фронту сигнала в регистр 3 опроса записывается значение нуля, так как счетчик 2 опроса был обнулен в цикле приема информации и на его пер вом информационном выходе в данный момент находится нуль. По этому адресу из блока 6 памяти читается значение, соответствующее количеству чисел нулевой градации. Это первое значение дифференциальной функции.

Одновременно это же значение из блока 6 памяти поступает на первый вход второго сумматора 15 текущего числа (первое текущее слагаемое) .

Оно складывается с числом, которое находится на втором входе этого же сумматора (второе текущее слагаемое) .

На втором входе сумматора 15 текущего числа в данный момент находится число нуль, так как второй регистр -17 суммы был обнулен в цикле приема информации. Результат суммы по спаду сигнала "ОПР" запоминается на втором регистре 17 суммы и поступает на первыи вход вычитателя 18.

На вычитателе 18 поступившее значение суммы вычитается из числа N, которое .постоянно находится на его втором входе (число N по значению равно количеству чисел в пакете данных).

Это первое значение интегральной функции. В ячейку блока 6 памяти, из которой производился опрос дифференциального и интегрального значения, по спаду сигнала "ОПР" с некоторой задержкой отрицательным потенциалом записывается нуль, так как в данном цикле (в цикле опроса) в обнуленном состоянии удерживается первый регистр 16 суммы, выход которого непосредственно соединен с информационным входом блока 6 памяти. Таким образом, обнуление данной ячейки

1385 6 блока 6 памяти происходит сразу после того, как были получены дифференциальная и интегральная функции. Ре5 дим чтение-запись по данному адресу в данном такте сигнала "ОПР" формирует формирователь 12 импульсов. Одновременно по спаду сигнала "ОПР" а данном такте на выходе счетчика 2 onроса устанавливается значение едини» цы. При поступлении второго сигнала

"0IIP" по его фронту на регистре 3 опроса запоминается значение единицы. Из блока 6 памяти читаетсь значение, соответствующее количеству чисел первой градации. Это второе значение дифференциальной функции. Одновременно это же значение суммируется на втором сумматоре 15 текущего числа с первым значением дифференциальной функции, которое в данный момент находится на втором входе этого сумматора, и по спаду сигнала

"ОПР" запоминается на втором регист25 ре 17 суммы. Искомая сумма вычитается из .числа вычитателя 18. Это второе значение интегральной функции.

Ячейка памяти, как и в предыдущем случае, по данному адресу в данном

3О такте сигнала ОПР" обнуляется при помощи режима чтение-запись, сформированного формирователем 12 режима.

По спаду второго сигнала "ОПР" на выходе счетчика 2 опроса устанавлива35 ется число два. Аналогично получа-. ются последуюшие значения дифференциальной и интегральной функций и аналогично происходит обнуление ячеек блока 6 памяти. Каждое значение

4О дифференциальной и интегральной функций по каждому сигналу "ОПР" поступает на вход устройства с последую- щим выводом на печать. По окончании цикла опроса (цикл опроса по значе45 нию равен М+1) на управляющем выходе счетчика 2 опроса формируется отрицательный сигнал, который через второй элемент ИЛИ 9 обнуляет сам себя.

Счетчик 4 цикла также обнуляется и устанавливается я режиме приема информации. Триггер 13 выбора регистра устанавливается в положение, при котором работает входной регистр 5.

Регистр 3 опроса информации переходит в высокоимпедансное состояние °

Устройство готово к приему очередного пакета данных.

Таким образом, если обозначить количество чисел, которое принимает

О (А ) = Р(А ) 55

А;-я градация через D, то функция

Р(А;) соответствует закону дифференциального распределения и показывает, какая доля из общего количества зафиксированных величин приходится на один из выбранных уров- 10 ней (фуикцйя повторяемости). Значения

И.20(А;) являются функцией, которая соответствует закону интегрального распределения

Mil ss 15

F(A, ) = N —, D(A;)C, C I которая показывает, какая доля из общего количества чисел приходится на величины вышезаданного уровня 20 (функция обеспеченности).

Формирователь 12 импульсов представлен на фиг. 2 ° Формирователь 12 импульсов работает следующим образом (см. фиг. 6) . 25

На первый или второй вход элемента 19 поступают импульсы. С инвертирующего выхода этого элемента сигнал поступает на первый вход элемента

И-НЕ 21. С неинвертирующего внхода 30 элемента 19 сигнал через элемент 20, задержки поступает на второй вход элемента И-НЕ 21. На выходе элемента И-НЕ 21 формируется импульс лог. О, который несколько задержан по отношению к спаду входного сигнала. Формируется сигнал "Чтение-запись", который поступает на управляющий вход блока 6 памяти.

Таким образом, по фронту сигнала 40

"СИ" или "ОПР" по положительному потенциалу на управляющем входе блока 6 памяти информация читается, по спаду сигнала "СИ" или "ОПР" по потенциалу лог. 0 информация записы- 45 вается в память, т.е. за один такт входного сигнала происходит переключение сигнала "Чтение-запись" блока 6 памяти.

Формула изобретения

Устройство для сортировки чисел, содержащее генератор тактовых импульсов, счетчик опроса, блок памяти, два.блока сложения, элемент И и элемент ИЛИ, о т л и ч а ю щ е е с я тем, что, с целью расширения области применения за счет интегрального и. 38 5 Я дифференциального распределения чисел, оно содера:ит триггер начальной установки, два элемента ИЛИ, триггер выбора регистра, два регистра суммы, вычитатель, счетчик цикла, входной регистр, регистр опроса, формирователь импульсов, причем вход установки в единичное состояние триггера начальной установки является входом начальной установки устройства и соединен с первыми входами первого и второго элементов ИЛИ,а прямой выход соединен с входом запуска генератора тактовых импульсов, выход которого соединен с первым входом третьего элемента ИЛИ, второй вход которого является входом опроса устройства, а выход соединен с первым входом формирователя импульсов, с синхровходами счетчика опроса,регистра опроса и первого регистра суммы, выходы разрядов которого соединены с входами вычитаемого вычитателя и входами первой группы первого сумматора, выходы суммы которого соединены с информационными входами первого регистра сумма, а входы второй группы соединены с информа-. ционными выходами блока памяти, выходами дифференциального распределения чисел устройства и с входами первой группы второго сумматора,входы второй группы которого являются входами заданного числа устройства, а выходы суммы соединены с информаци онными входами второго регистра суммы, выходы разрядов которого соединены с информационными входами блока памяти, управляющий вход кото рого соединен с выходом элемента И, первый вход которого соединен с выходом формирователя импульсов, а второй вход с инверсным выходом триггера начальной установки, вход установки в "0" которого соединен с вторым входом первого элемента ИЛИ, с выходом переполнения счетчика опроса, с входами установки в нулевое состояние счетчика цикла и триггера выбора регистра, вход установки в единичное состояние которого соединен с выходом второго элемента ИЛИ, второй вход которого,соединен с выходом переполнения счетчика цикла, счетный вход которого является входом синхронизации устройства и соединен с вторым входом формирователя импульсов, с входом синхронизации

9 144)385 1Р входного регистра и с входом синхро- ты устройства, а выходы - интегральнизации второго регистра сумма, вход ного распределения чисел устройства, -установки в нулевое состояние кото- информационные входы устройства рого соединен с входом установки в соединены с информационными входами

5 нулевое состояние входного регистра входного регистра, выходы разрядов и с инверсным выходом триггера выбора счетчика опроса соединены с информарегистра, прямой выход которого еое- ционными входами регистра опроса, динен с входами установки в нулевое выходы разрядов входного регистра и состояние регистра опроса и первого 0 регистра опроса соединены с соответрегистра сумки, входы уменьшаемого ствующими адресными входами блока вычитателя являются входами констан- памяти.

7(®х1)

13 (чьи.1)

0(йя .2) б (Юх. упр.)

E(k.ум)

Р(Рык)

1 (lou.1)

1 (Й/х.)

6 (Й. адр.)

Р (АР) ! 441385

ghfP. e

N ю(&. аур)

6(Й уюр.) ф (Q рц «r1+1 @+1 rS+-1

Q(80u t)

15 (Й/х.7) р (дух.)

4 (Аа.) р Ню uneem знспнюя

Фиг.4

ОПР

Я (INJ.Д

Дйа3

b 6(. напр. е(ku.)

17(й х.)

1дфы)

E(Atm)

J(lnrx.1)

O(krs2)

8®аг) м йеuneem яаченаяВЪг. S

144! 385

1 !

4 О а 6 ф ц ь

4о в ъ с

E Ж

Составитель В.Козлов

Техред М.Дидык Корректор М.Демчик с

Редактор Е.Копча

Заказ 6289/52

Тираж 704 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д, 4/5

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4