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

 

УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ЧИСЕЛ, содержащее входные счетчики, выходной счетчик, группу элементов ИЛИ, группу формирователей импульсов , группу выходных элементов И, группу запрещающих элементов И, элемент ИЛИ, входной элемент И, первый вход которого подключен к. входу тактовых импульсов устройства , а выход со.единен с суммирующим входом выходного счетчика и первыми входами запрещающих элементов И группы, выходы которых соединены с вычитающими входами соответствующих входных счетчиков, выходы которых поразрядно подключены к входам соответствующих элементов ИЛИ группы, выходы KOTopbtx соединены с входами соответствующих формирователей импульсов группы, вторыми входами соответствующих запрещающих элементов И группы и с соответствующими входами элемента ИЛИ., выходы выходного счетчика поразрядно соединены с информационными входами выходных элементов И группы, выходы которых являются информационными выходами устройства, отличающееся тем, что, с целью повышения достоверности при сортировке равных чисел, в него введены первьш и второй триггеры, регистр, преобразователь числа единиц в двоичный код, счетчик равных чисел, первьй и второй элементы ШЖ-НЕ, первый и второй элементы И, формирователь импульса сброса, элемент задержки,причем выходы формирователей импульсов группы соединены с соответствующими разрядными входами регистра, выходы разрядов которого соединены с входами первого элемента ИЛИ-НЕ и с соответствующими входами преобразователя числа единиц в двоичный код, выхос S ды которого соединены с соответствующими информационными входами счетчика равных чисел, выходы которого С соединены с входами второго элемента ИЛИ-НЕ, выход которого соединен через формирователь импульса сброса с синхронизирующим входом первого триггера и входами зстановок в нулевое состояние регистра и второго триггера, информационный вход которого соединен с входом логической . единицы устройства, инверсный выход второго триггера соединен с первым входом первого элемента И, второй вход которого соединен с выходом первого элемента ИЛИ-НЕ и через элемент задержки - с вторым входом входного элемента И, третий вход которого сое-, динен с прямым выходом, первого триггера , информационный вход которого соединен с выходом элемента ИЛИ, вход тактовых импульсов устройства подключен к третьему входу первого элемента И и первому входу второго элемента И, второй вход которого соединен с прямым выходом второго триггера, а

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

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

РЕСПУБЛИК (51)4 С 06 Р 7/08

/Q ...:

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

Н ABTOPCHOMY СВИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3711902/24-24 (22) 16.03.84 (46) 15.09.85. Бюл. ¹ 34 (72) А.Н.Мурашко (53) 681.325(088.8) (56) Авторское свидетельство СССР

Ф 637810, кл. G 06 F 7/08, 1976.

Авторское свидетельство СССР № 993251, кл. G Об F 7/08, 1981 . (54)(57) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ

ЧИСЕЛ, содержащее входные счетчики. выходной счетчик, группу элементов ИЛИ, группу формирователей импульсов, группу выходных элементов И, группу запрещающих элементов И, элемент ИЛИ, входной элемент И, первый вход которого подключен к. входу тактовых импульсов устройства, а выход соединен с суммирующим входом выходного счетчика и первыми входами запрещающих элементов И группы, выходы которых соединены с вычитающими входами соответ" ствующих входных счетчиков, выходы которых поразрядно подключены к входам соответствующих элементов ИЛИ группы, выходы которых соединены с входами соответствующих формирователей импульсов группы, вторыми входами соответствующих запрещающих элементов И группы и с соответствующими входами элемента ИЛИ, выходы выходного счетчика поразрядно соединены с информационными входами выходных элементов И группы, выходы которых являются информационными выходами устройства, о т л и ч а— ю щ е е с я тем, что, с целью повышения достоверности при сортировке равных чисел, в него введены первый и второй триггеры, регистр, преобразователь числа единиц в двоичный код, счетчик равных чисел, первый и второй элементы ИЛИ-НЕ, первый и второй элементы И, формирователь импульса сброса, элемент задержки,причем выходы формирователей импульсов группы соединены с соответствующими разрядными входами регистра, выходы разрядов которого соединены с входами первого элемента ИЛИ вЂ  и с соответствующими входами преобразователя числа единиц в двоичный код, выходы которого соединены с соответствующими информационными входами счетчика равных чисел, выходы которого соединены с входами второго элемента ИЛИ-НЕ, выход которого соединен через формирователь импульса сброса с синхронизирующим входом первого триггера и входами установок в нулевое состояние регистра и второго триггера, информационный вход которого соединен с входом логической . епиницы устройства, инверсный выход второго триггера соединен с первым входом первого элемента И, второй вход которого соединен с выходом первого элемента ИЛИ-НЕ и через элемент задержки — с вторым входом входного элемента И, третий вход которого соединен с прямым выходом. первого триггера, информационный вход которого соединен с выходом элемента ИЛИ, вход тактовых импульсов устройства подключен к третьему входу первого элемента И и первому входу второго элемента И, второй вход которого соединен с прямым выходом второго триггера, а

1179317 выход является выходом разрешения выдачи и подключен к управляющим входам выходных элементов И группы и вычита-. ющим входам счетчика равных чисел, Изобретение относится к вычислительной технике и может быть использовано в устройствах обработки сигналов, в системах связи и др.

Цель изобретения — повышение до- 5 стоверности при сортировке равных чисел.

На фиг.1 приведена функциональная схема предлагаемого устройства на фиг.2 — временная диаграмма работы элементов устройства.

Таблица состояния выходов преобразователя числа единиц в двоичный код в зависимости от состояния его входов (на примере пяти входов) приведена в табл. 1.

Устройство содержит входные счетчики 1,...,1,„, выходной счетчик 2, группу элементов ИЛИ 3< ..., 3,„, элемент ИЛИ 4, триггер 5, группу за- 20 прещающих элементов И 6, ..., 6, входной элемент И 7, группу выходных элементов И 8, ..., 8» группу Фор мирователей 9, ..., 9m импульсов, регистр 10, элемент ИЛИ-НЕ 11, эле- 25 мент 12 задержки, элемент И 13, триггер 14, преобразователь 15 числа еди ниц в двоичный код, счетчик 16 равных чисел, элемент ИЛИ-НЕ 17, элемент И

18, формирователь 19 импульса сброса, ga тактовый вход 20 устройства, информационные выходы 21 устройства, выход 22 разрешения выдачи.

Назначение элементов устройства следующее. Счетчики 1, ..., 1 „ слу- З5 жат для временного запоминания исходных сортируемых чисел. Элементы ИЛИ

31, ..., 3 служат для фиксирования нулевого состояния соответствующего счетчика 1,..., 1,„, причем-при ну- 40 левом содержимом счетчика 1, ...,1щ на выходе соответствующего элемента ИЛИ .3, ° ° °, 3 „„ " нулевой потенциал. Выходной счетчик 2 служит для формирования кода на выходах 21 устройства при сортировке чисел. Элемент ИЛИ 4 и триггер 5 служат для вход разрешения записи которого подключен к выходу первого элемента И и синхронизирующему входу второго триггера. фиксирования нулевого состояния всех счетчиков 1, ..., 1> в конце сортировки и выработки запрещающего потенциала по второму входу элемента И 7 для дальнейшей блокировки тактовых импульсов. Формирователи

9, ..., 9 1и регистр 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 и на время о ц42, которое определяется, например, исходя из устойчивой работы устройства из соотношения л л тц „2< ти

gQД

Временные интервалы между тактовыми 1О импульсами составляют при этом, наи пример, >qggz

Исполнение элементов устройства может быть, например, следующее.

Счетчики, триггеры, регистр, эле- !5 менты И, ИЛИ, ИЛИ-НЕ, группы элемен1тов И являются типовыми, например, для цифровых интегральных схем TTL серий 133, К155, 130, К131, 530, К531 К555. Преобразователь 15 реали. зуется, например, на базе типовых логических элементов с учетом таблицы состояний. Формирователи 9,..., 9

19 могут быть реализованы, например на базе типовых формирователей 25

К155АГЗ с учетом логики функционирования и временных параметров, приведенных в материалах заявки.

Устройство работает следующим образом. 30

Во входные счетчики 11, ..., 1 „ заносятся сортируемые числа. Регистры 10 и счетчик 16 обнулены, триггер 14 установлен в нулевое состояние, при этом на инверсном выходе 35 последнего — потенциал логической единицы. Триггер 5 устанавливается в единичное состояние, при этом с его выхода на второй вход элемента И 7 поступает единичный потенци- 40 ал (цепи начальной установки элементов устройства на фиг.1 не показаны). В исходном состоянии на выходах элементов ИЛИ-НЕ 1.1 и 17 — единичные потенциалы, поскольку регистр 45

10 и счетчик 16 обнулены, а на выходах элементов ИЛИ 3,..., Зщ- единичные потенциалы, поскольку содержимое счетчиков 1„, ..., 1> не равно "0", и следовательно, на первые 50 входы группы запрещающих элементов И

6 „...,6 „ и на второй и третий входы элемента И 7 поступают разрешающие единичные потенциалы.

На вход 20,устройства подаются тактовые импульсы (фиг.2д), которые через элемент И 7 поступают на суммирующий вход выходного счетчика 2 и через группу элементов И 61,...,6 на вычитающие входы счетчиков 1

1 . При этом содержимое счетчиков

1,...,1щ уменьшается, а выходного счетчика 2 - увеличивается.

При поступлении на вход 20 устрой. ства количества тактовых импульсов, соответствующего минимальному числу (или нескольким числам) из сортируемых чисел в счетчиках 1,...,t „ содержимое соответствующего счетчика

1 (или нескольких счетчиков 1, 1 ), 1 У в котором (в которых) было записайо минимальное число, становится равным"0". На выходе соответствующих элементов ИЛИ 3„ появляется нулевой потенциал (фиг.2 ), закрывающий соответствующие элементы И 6 группы, блокируя дальнейшее поступление вычитающих импульсов на входы тех счетчиков 1,, в которых содержимое стало равным "0" На выходах формирователей 9;, подключенных к тем элементам ИЛИ 3,, на которых выставился нулевой потенциал, появляются импульсы записи "1" в регистр 10 (фиг.22), причем количество записанных "1" по всем разрядам регистра 10 соответствует числу счетчиков 1„, установленных в нулевое состоянйе. Срабатывает элемент ИЛИ-НЕ 11, на выходе которого выставится нулевой пол тенциал. Далее через 1 Д, срабатывает . элемент 12 задержки и на третьем. входе элемента И 7 выставляется запрещающий нулевой потенциал, по которому поступление тактовых импульсов на выход элемента И 7 блокируется (фиг.25). По концу тактового импульса срабатывает элемент И 13, на выходе которого появляется импульс перезаписи двоичного кода числа, например "3, установленных в нулевое состояние счетчиков 1„, в счетчик

16 равных чисел по его синхровходу (фиг.2e) . По концу сигнала перезаписи (поскольку по синхровходу триггера 14 осуществляется инверсия сигнала) триггер 14 устанавливается в единичное состояние, так что с его инверсного выхода на третий вход элемента И t3 поступает запрет, а с

его прямого выхода на второй вход элемента И 18 — разрешение (фиг.2ж).

На выходе элемента ИЛИ-НЕ 17 уста- навливается нулевой потенциал. Тактовый импульс с первого входа элемента И 18 поступает на его выход

1179317

2 22

0

0

0

0

0

0

0 (фиг. 2 ) и далее — на вычитающий вход счетчика 16, на вторые входы группы элемер-ов И 84, ..., 8 и и на второй выход 22 устройства. При этом с выхода счетчика 2 на выход

21 устройства поступает код минимального числа (чисел). По следующему тактовому импульсу также поступает с выхода элемента И 18 строб-импульс о выдаче на выход 21 устройства такого же содержимого счетчика 2 (фиг.2)).

Поскольку в счетчике l6 было записано число 3", то с поступлением с выхода элемента И 18 третьего вычитающего импульса счетчик 16 устанавливается в нулевое состояние,срабатывает второй элемент ИЛИ-НЕ 17 и на его выходе выставляется единичный потенциал (фиг.2И). Таким образом, на выход 21 устройства поступает код минимальных чисел столько раз, сколько было записано в счетчики

1,, ..., 1„„ этих равных чисел.

По переднему фронту (О- 1) сигнала с выхода элемента ИЛИ-HE 17 запускается формирователь 19 через и на выходе которого появляется импульс (фиг.2 k), по которому триггер 14 сбрасывается в нулевое состояние и триггер 5 устанавливается в то же состояние, что и на выходе второго элемента ИЛИ 4, сигнал с которого поступает на информационный З -вход триггера 5. Поскольку не все счетчики 11, ..., 1 „ обнулились в первом циклс работы устройства, то на некоторых входах элеменВходы кодопреобразователя 15

? I 3 4 та ИЛИ 4 — единичные потенциалы и на выходе последнего — также единичньй потенциал. Триггер 5 поэтому не изменяет по синхроимпульсу с выхода формирователя 19 своего состояния (единичного).

По следующему тактовому импульсу начинается следующий цикл определе10 ния чисел, следующих по рангу за минимальными в порядке возрастания.

Цикл повторяется аналогично предыдущему: определяется количество установленных счетчиков 1, °, 1„„ в ну15 левое состояние в последнем цикле, а затем на выход 21 поступает код этих чисел с выхода счетчика 2 столько же раз. Причем коды сопровождаются синхроимпульсами с выхода 22 устрой20 ства. Циклы сортировки повторяются до тех пор, пока все записанные числа в счетчиках 1, ..., 1щ не будут отсортированы, т.е. все счетчики 1,...

1„ обнуляются. В конце последнего цикла элемент ИЛИ 4 выставляет на своем выходе нулевой потенциал, а по переднему фронту сигнала с выхода фор. мирователя 19 триггер 5 устанавливается в нулевое состояние и блокирует

З0 дальнейшее поступление тактовых импульсов через элемент И 7.

Сортировка чисел окончена.

Для проведения сортировки чисел

35 устройством, начиная с максимального числа, достаточно записать числа во входные счетчики 1, ..., 1m в обратном коде и результат получать с нулевых выходов выходного счетчика 2.

Выходы кодопреобразователя 15

1179317

0 0

0 .

Входы кодопреобраэователя l5

Т11

2 3 4:. 5

Продолжение таблицы

Выходы кодопреобразователя 15

1179317

11793)7

Составитель Е.Иванова

Редактор С.Тимохина Техред Т.Фанта Корректор М.Самборская

Заказ 5676/50 Тираж 710 Подписное

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

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

Филиал ППП "Патент", г.ужгород, ул.Проектная, 4