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

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

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

Устройство для сортировки п чисел содержит генератор импульсов 1, элемент И 2, триггер 3, группу из п регистров .,.,4| и счетчиков 5,.,., 5, первый элемент И-НЕ 6,элемент задержки 7, первую группу из h элементов ИЗ., ..., 8, группу из элементов ИЛИ 9, ,. .., 9,. вторую группу из п элементов И 10,,„.., 10 группу из птриггеров 11,.. о, 11, второй элемент И-НЕ 12, входы 13,, ..,, 13 сортируемых чисел, выходы регистров, выходы 15;| , ..., 15 счетчиков, вход 16 запуска, выход 17 конца сортировки. Величина задержки импульсов элемента 7 меньше периода следования сигналов генератора 1. Разрядность регистров 4 и счетчиков 5 определяет максимальную величину подлежащего сортировке числ-а,,которая, равна .

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

Перед сортировкой в регистры 4 и счетчики 5 по входам 13,..., 13, записываются числа, подлежащие сортировке, причем в одноименные регистры и счетчики (, ..., , записываются одинаковые числа.

Входы 13 включают информадаонные и управляющие шины. Запись чисел в регистры 4 и счетчики 5 может осуществляться как параллельным, так и последовательным способом в зависимости от конкретных условий применання устройства.

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

приходу импульсного пускового сигнала отрицательной полярности, который с входа 16 поступает на единичjuie входы триггеров 3, 11|,..., 11(, устаиа вливая их в единичное состояние, С прямого выхода триггера 3

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

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

При возникновении импульса переполнения в счетчике, где записано 3 наименьшее число по нулевому входу, сбрасывается в нулевое состояние оставшийся соответствующий триггер 11, с инверсного выхода.которого сиг нал разрешения поступает на второй вход соответствующего элемента И 10 и на соответствующий вход элемента И-НЕ 12. При этом на входы элемента И-НЕ 12 с инверсных выходов всех триггеров 11 поступают сигналы 1, и по задержанному импульсу переполнения с выхода элемента 7 на выходе элемента И-НЕ 12 появляется сигнал Сортировка завершена отрицательной полярности, который по нулевому входу сбрасывает в нулевое -состояние триггер 3. Сигнап О с прямого выхода триггера 3 поступает на первый вход элемента И 2 и запрещает про}сождение импульсов генератора 1 на счетчики 5,, ..., 5. Одновременно задержанный импульс переполнения с выхода элемента 7 через открытые элементы И 10, элементы ИЛИ 9 увеличивает состояние счетчиков 5, ..., 5 на 1, Таким образом, в счетчике, где находилось наименьшее число, записан наименьший код, в счетчике, где находилось максимально число, записан наибольший код, а в остальных счетчиках - промежуточные коды в соответствии с положением числа на числовой оси. Если все чис ла, подлежащие сортировке, разные, то в счетчиках 5,,..., 5 записан код от О до - 1. Наименьшему числу соответствует код О, наибольшему Если из состава чисел, подлежащих сортировке, будет несколько чисел с одинаковыми значениями, то после cop тировки в соответствующих счетчиках будут записаны одинаковые значения. Пример. Необходимо произвес ти сортировку четьфех чисел, которы записаны в следующем порядке: в регистре 4 и счетчике 5., находится максимальное число, в регистре 4 и счетчике 5 находится второе по величине число, минимальное число находится в регистре 4 и счетчике 5 Счетчики 5 вьфабатывают сигнал переполнения в случае, когда во всех разрядах будут 1. После прихода импульса запуска с входа 16 импульсы генератора 1 начи нают поступать на счетные входы сче чиков 5 , ..., 5, как описьшалось 104 выше. Импульс переполнения, в первую очередь, появится на выходе счетчика 5j, так как в нем было записано максимальное число. Импульс переполнения по нулевому входу сбросит в нулевое состояние триггер 11j, в результате чего элемент И 8j закроется для прохождения иьшульсов генератора, а с инверсного выхода триггера llj на второй вход элемента И lOj и на третий вход элемента И-НЕ 12 поступит сигнал Г . Одновременно импульс переполнения поступит черёу элемент И-НЕ 6 на элемент задержки 7. Задержанный импульс переполнения через элемент И 10, элемент КПИ Ч, запишет О в счетчик 5 . Следующий импульс переполнения возникнет на выходе счетчика 5, по которому сбросится в нулевое состояние триггер 11. Элемент И 8 закроется для прохождения импульсов генератора, с инверсного выхода триггера 114j сигнал 1 поступит на второй вход элемента И на второй вход элемента И-НЕ 12, Задержанньй импульс переполнения с выхода элемента 7 через элементы И ., ИЛИ 9 запишет О в счетчик 5, а через элементы И lOj, ИЛИ 9з - Ч в счетчике 5з . Следующий импульс переполнения появится на втором выходе счетчика 5, по которому сбросится в нулевое состояние триггер 11. Элемент И 8 закроется для прохождения импульсов генератора 1 на счетчик 5. Сигнал 1 с инверсного выхода триггера 112 поступит на второй вход элемента И 10 и на четвертый вход элемента И-НЕ 12. Задержанный импульс . переполнения с выхода элемента 7 через соответствующие элементы запишет О в счетчик 52, 1 - в счетчик 54, 2 - в счетчик 5. Последний И1.шульс переполнения будет выработан на втором выходе счетчика 5, по которому установится в нулевое состояние триггер 11j и будет запрещено прохождение импульсов генератора 1 через элемент И 8, С инверсного выхода триггера сигнал 1 поступит на второй вход элемен-та И 10 и на пятый вход элемента И-НЕ 12. Так как на входы элемента И-НЕ 12 с инверсных выходов триггеров 11, ,. о ., 114 поступают сигналы 1, tio сигналу с выхода элемента 7 на выходе элемента И-НЕ 12 выра

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