Устройство для сортировки чисел Советский патент 1987 года по МПК G06F7/06 

ИзОбрСТГЛГИС О ПНКЧГГСЯ к ПМЧИГЛИTCJii ifui трхникг н может исполь- зо1 ,а;1о для аГтализа процессов, в частности определения функции расп- рс делеиия случаГшых процессов и для других вычислений, требующих сортировки значений переменных в зависимости от их пеличины, и является усо- рершенствованием устройства по авт. св. № 1182510.

Цель изобретения - повышение бы- строде1 1ствия устройства.

На чертеже представлена схема предлагаемого устройства.

Устройство для сортировки п чисел содержит генератор I импульсов, элемент И 2, триггер 3, группу из п реГИС ТрОВ - 4

,4

и сче -чиков ;х

олемент И-НЕ 6, э.лемонт

7

K1U группу из п элементов И 8 8)|, rpyimy из элементов ШП

1

,,...,

9,,...

вторую группу из п плс мсш ол и .„.,0„, группу н:/ Г1Ш.Ггерои . , 1 1г| , элемент 12, входы ,,13„ сортируемых чисел, вы - I

ai;;i i 14,,.,., 14, регистров, выходы 1 5,| , . , . , 1 5,.| счетчиков, г руппу эле- М( итпв И 16, элемент НЕ 17, дополни rcjifiHi-rfi элемент 18 з 1держки, вход 1 з;и;уска и выход 20 конца сортировки Ijyjnjtinna задержки иг-;пульсов зле- MC irra 7 меныче периода следования сигналов генератора 1 , Tancpxiva эле Mf/irra 13 должна uFiiTb JTOCT: точной

НаДе;КН1 ГО СрП бп 1,1Ио НИИ СЧе Ч1;KOI 5. Разрядное , регистров 4 и счс Г чичсои 5 равн;1 m и ОПредезгяет маг спмя.тп.иу.: тюлг.чину подле/кащего со15тпрорке числа, paiiFiyio 2 - 2.

ycTpoi icTiiO работает следующим образом.

Перед сортировкой в регистры 4 и счетчики 3 по входам 13., ,...,13, запипывпютси числа, подлежащие сортровке, П1ТПЧРМ в одноименные регист- pi- ij счетчр1К -1 4 ,| - 5 .,,.,, 4 „ - 5. заиигьпзаются одинаковые чис.ча.

В;чо;д1)1 13 вк:гючают информационные и ) пл 1к:1ЛИ( НИНЫ. Sanncjj исел в pt i iiCTpi, 4 и счетчики 5 мо)е г осу- ще(::твлят1 ся как параллельным, так и Г1Ос .иедо1 а Г1: 1П1Ным способом в завмси- iM U- ii oT конкретных примене пич ycTi joficTBa.

При поступлении на вход 19 импул снОго irycjcoiioro сигнала О трицатель- ной полярности на выходе элемента III-; 17 (;, 0рмнру(т( я единичный сигт1ал.

fO

5

20

25

поступающий на первые входы всрх элементов И 16. Если все сортируемые числа в каком-либо или нескольких разрядах содержат О, то за счет сигналов на инверсных выходах регистров 4 откроются соответствующие элементы И 16. Это обеспечивает установку в 1 определенных разрядов всех счетчиков 5,

Через время задержки элемента 18 сигнал отрицательной полярности поступает на единичные входы триггеров 3 и 11, ,...1 If, , устанавливая их Б единичное состояние. С прямого выхода триггера 3 на первый вход элемента И 2 поступает сигнал 1. С прямых выходов триггеров 1Ц ,..., llf, поступают сигналы на вторые входы элементов И 8.,,...,8,,. Импульсы с выхода генератора 1 поступают через И 2, элементы И 8,,..,8 и элементы ИЛИ 9 ,..,,9 на счетные

входы счетчиков .

По каждому импульсу счетчики 5 увеличивают свое состояние на 1., Импульс переполнения, в первую очередь, появляется на выходе счетчика, в котором было записано максимальное число. Этот отрицательный импульс по нулевому входу переключает в нулевое состояние соответствующий триггер 11 группы триггеров. -С инверсного выхода этого триггера разрешающий сигнал поступает на второй вход со- 35 ветствующего элемента И 10 и на вход элемента И-НЕ 12.

Одновременно отрицательный импульс переполнения поступает на соответствующий вход элемента И-НЕ 6. С его выхода положительный импульс, задержанный на элементе 7 задержки через открытый соответствующий элемент И 10, соответствующий элемент ИЛИ 9 поступает на счетный вход со- ответствующего счетчика 5 и увеличивает ег о состояние на 1. Если счетчик 5 вырабатывает сигнал переполнения при единичных сигналах во всех разрядах,он переходит в состояние, 50 когда во всех разрядах нулевые сигналы.

Следующий импульс переполнения возникает на выходе того счетчика, в котором записано число, являющееся максимальным из оставшихся. Этим отрицательным импульсом по нулевому входу сбрасывается в нулевое состояние следующий соответствующий триггер 1I из группы триггеров. С его

30

40

45

55

инверсного выхода разрешающий сигнал поступает на соответствующий вход элемента И-НЕ 12 и на второй вход соответствующего элемента И 10. С выхода элемента 7 задержанный импульс переполнения через открытые элементы И 10 группы, через элементы ИЛИ 9 группы увеличивает на 1 состояние счетчиков, в которых вырабртался сигнал переполнения. Аналогично про- цесс сортировки продолжается для других чисел.

При возникновении импульса переполнения в счетчике, где записано наименьшее число по нулевому входу, срабатывается в нулевое состояние оставшийся соответствующий триггер II, с инверсного выхода которого сигнал разрешения поступает на второй вход соответствующего элемента И 10 и на соответствующий вход элемента И-НЕ 12. При этом на входы элемента И-НЕ 12 с инверсных выходов всех триггеров 11 поступают сигналы 1 и по задержанному импульсу перепол- нения с выхода элемента 7 на выходе элемента И-НЕ 12 появляется сигнал Сортировка завершена отрицательной полярности, который по нулевому входу сбрасывает в нулевое состояние триггер 3.

Сигнал О с прямого выхода триггера 3 поступает на первый вход элемента И 2 и запрещает прохождение импульсов генератора 1 на счетчики 5 ,..,,5. Одновременно задержанный импульс переполнения с выхода элемента 7 через открытые элементы И 10, элементы ИЛИ 9 увеличивает состояние счетчиков 5,...,5 на 1. Таким образом, в счетчике, где находилось наименьшее число, записан наименьший код, в счетчике, где находилось максимальное число, записан наибольший код, а в остальных счет- чиках - промежуточные коды в соответствии с положением числа на числовой оси. Если из состава чисел, подлежащих сортировке, несколько чисел с одинаковыми значениями, то по еле сортировки в соответствующих счетчиках будут записаны одинаковые значения.

Пример. Необходимо произвести сортировку четырех чисел, которые записаны в следующем порядке: в регистре А, и счетчике 5, находится

/

максимальное число 00110 (.младший

разряд справа) , в регистре А и счетчике 5 - второе по величине число 00101, в регистре А и счетчике 52 - число 00010, минимальное число 00001 находится в регистре А и счетчике 5, , Счетчики 5 вырабатывают сигнал переполнения в случае, когда во всех разрядах будут 1.

При поступлении на вход 19 импульсного пускового сигнала отрицательной полярности на выходе элемента НЕ 17 формируется единичный сигнал, поступающий на первые входы всех элементов И 16. Так как в двух старших разрядах сортируемых чисел содержится код О, то за счет сигналов на инверсных выходах регистров А открываются два соответствующих элемента И 16. Это обеспечивает установку в l двух старших разрядов всех счетчиков 5: в счетчике 5jнаходится число 11110, в счетчике 5 число 11101, в счетчике 52 число 11010 и в счетчике 5, - число 11001.

Через время задержки элемента 18 импульсы генератора 1 начинают поступать на счетные входы счетчиков 5,...,5. Импульс переполнения, в первую очередь, появится на выходе счетчика 5,, так как в нем было записано максимальное число. Импульс переполнения по нулевому входу сбросит в нулевое состояние триггер 1I, , в результате чего элемент И 8 закроется для прохождения импульсов генератора, а с инверсного выхода триггера 1Ц на второй вход элемента И 10J и на третий вход элемента И-НЕ 12 поступит сигнал l.

Одновременно импульс переполнения поступит через элемент И-НЕ 6 на элемент 7 задержки. Задержанный импульс переполнения через элемент И 10, , элемент ИЛИ 9 запишет О в счетчик 5j. Следующим импульс переполнения возникнет на выходе счетчика 5,, по которому сбросится в нулевое состояние триггер 1Ц. Элемент И 8 закроется для прохождения импульсов генератора с инверсного выхода триггера 11, сигнал 1 поступит на второй вход элемента И 10 и на второй вход элемента И-НЕ 12.

Задержанный импульс переполнения с выхода элемента 7 через элементы И 10 и ИЛИ 9, запишет О в счетчик 5 , а через элементы И

в

счетчик 5 . Следующий импульс переполнения появится на второ выходе счетчика 5-, по которому сбросится в нулевое состояние триггер 11., Элемент И 8. закроется для прохождения импульсов генератора 1 на счетчик 5л. Сигнал 1 с инверсного выхода триггера 11 поступит на второй вход элемента И 10 и на четвертый вход элемента И-НЕ 12.

Задержанный импульс переполнения с выхода элемента 7 через соответст п

в счет 9 -

I вующие элементы запишет О чин 5, 1 - в счетчик 5. в счетчик 5j . Последний импульс пе- реполнения будет выработан на втором выходе счетчика 5,, по которому устанавливается в нулевое состояние триггер 11 и будет запрещено прохождение .импульсов генератора 1 через элемент И 8,.

С инверсного выхода триггера сигнал 1 поступит на второй вход элемента И 10, и на пятый вход элемента И-НЕ 12. Так как на входы элемента И-НЕ 12 с инверсных выходов триггеров 1 1 ,...,11 поступают сигналы 1, по сигналу с выхода элемента 7 на выходе элемента И-НЕ 12 вырабатывается отрицательный сигнал Сорти- ровка завершена, по которому по нулевому входу сбрасывается в нулевое

Редактор П. Гереши

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

Техред А. Кравчук Корректор С. Шекмар

Заказ 2864/44Тираж 672Подписное

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д.4/5

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

o

-5 0

5

состояние триггер 3 и запрещается прохождение 1 мпульсов генератора 1 через элемент И 2.

Одновременно задержанный импульс переполнения с выхода элемента 7 через соответствующие элементы запишет О в счетчик 5

чик

2 - в счетчик 5

- в

ИпИ

счетчик

3 - в счет-г

5g . Таким образом, в счетчик 5

будут записаны коды, соответствующие величине подлежащих сортировке чисел.

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

Устройство для сортировки чисел по.авт.св. № 1182510, отличающееся тем, .что, с целью повышения быстродействия, в него введены третья группа из м элементов И, элемент НЕ и дополнительный элемент задержки, выход которого соединен с единичными входами всех триггеров, а вход является входом запуска устройства и соединен через элемент НЕ с первыми входами элементов И третьей группы, инверсные выходы i-х разрядов регистров группы, где ,2

m, подключены к входам с второго по (п+1)-й элемента И третьей группы, выход которого соединен с дополнительными входами установки в 1 i-x разрядов всех счетчиков.

Изобретение относится к вычислительной технике и может быть использовано для анализа процессов, в частности для определения функции распределения случайных процессов и для других вычислений, требующих сортировки значений переменных в зависимости от их величины и является усовершенствованием устройства Т... по а.с. № 1182510. Цель изобретения - повышение быстродействия устройства. Устройство содержит генератор I импульсов, группу регистров 4 и счетчиков 5, триггер 3, элемент И 4, группы элементов И 8, 10 и 16, два элемента И-НЕ 6 и 12, элемент задержки, группу триггеров 11 и группу элементов ИЛИ 9, элемент НЕ 17, дополнительный элемент 18 задержки. Введение третьей группы элементов И 16 позволяет производить предварительный анализ сортируемых чисел, если все они содержат в i-м разряде код О, то происходит увеличение содержимого всех счетчиков на вели чину 2. Соответственно количество тактов, затрачиваемых на сортировку, уменьшается на 2, что повышает быстродействие устройства. 1 ил. ел 14)