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

Поставленная цель достигается тем. что в устройство для сортировки чисел, содержащее два генератора, генератор импульсов, две группы элементов И, группу счетчиков, триггер, счетчик, два элемента И и первый регистр, причем входы счетчмка являются входами задания длины массива устройства, выход второго элемента И подключен к установочному входу триггера, выход первого регистра соединен с входами второго дешифратора и является первым информационным выходом устройства, введены первая и вторая группы регистров, устройство выделения экстремума, второй регистр, элемент НЕ, три элемента задерж- ки, третий элемент И и элемент ИЛИ-НЕ, причем информационные входы разрядов чисел устройства соединены с входами первого дешифратора, выходы которого подключены ко вторым входам соответствующих элементов И первой группы, выходы которых подключены к счетным выходам соответствующих счетчиков группы, входы сброса счетчиков группы объединены и соединены через первый элемент задержки с выходом второго элемента И, соединенным также с входами записи регистров первой группы, и являющегося управляющим выходом устройства, синхровход устройства соединен с первым входом пер- вого элемента И, второй вход которого через элемент НЕ подключен к выходу счетчика и к первому входу второго элемента И, второй вход которого соединён с инверсным выходом триггера, выход первого элемента И соединен с объединёнными входами (вторыми) элементов И соединен с объединенными входами (вторыми) элементов И первой группы и со счётным входом счетчика, выходы счетчиков группы соединены с информационными входами соответствующих регистров первой группы, входы регистров второй группы являются установочными входами устройства, выходы регистров первой и второй групп соеди- нены соответственно с группами первых и вторых входов устройства выделения экстремума, первая группа выходов которого подключена к информационным входам второго регистра, выходы которого подклю- чень: к входам элемента ИЛИ-НЕ, и являются вторым выходом информационного устройства, вторая группа выходов устройства выделения экстремума соединена с информационными входами первого регистра, прямой выход триггера соединен с управляющим входом генератора тактовых импульсов, выход которого соединен с синхровходами первого и второго регистров, и с входом второго элемент задержки,

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

Кроме того, устройство выделения экстремума содержит m групп по р устройств сравнения в 1-й rpynne.jri-разрядость чисел входного массива, I 1m, pi , причем первый и второй выходы j-ro устройства сравнения первой группы соединены с выходами 2j-1-ro и 2J-ro регистров первой группы, третий и четвертый входы j-ro устройства сравнения первой группы соединены, соответственно с выхода ми 2 -1-го регистров второй группы, j 1,, входы с первого по четвертый -го устройства сравнения 1-й группы, I 2, m, k 1,, соединены соответственно с первыми выходами 2k-1-rp и 2k-ro устройства сравнения 1-1-и группы и со вторыми выходами 2k-1-ro и 2k-ro устройств сравнений i-1-й группы.

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

На фиг. 1 приведена структурная схема устройства для сортировки чисел; на фиг. 2 - структурная схема устройства- выделения экстремума; на. фиг. 3 - структурная схема устройства сравнения.

Устройство для сортировки чисел содержит генератор импульсов 1, первый 2 и второй 3 дешифраторы, первую 4 группу

лементов И, группу 5 счетчиков, первую 6 руппу регистров, вторую 7 группу регистов, бпок 8 выделения экстремума, первый и второй 10 регистры, триггер 11, счетчик 1.2, первый 13, второй 14 и третий 15 элемены 1/1, элемент 16 ИЛИ-НЕ, первый 17, второй 18 и третий 19 элементы задержки, вторую 20 группу элементов И, элемент 21 НЕ, входы 22 разрядов чисел устройства, инхровход устройства 23. Входы 24 задаия длина массива. Выходы 25 и 26 являютя информационными выходами стройства. Выход 27 второго элемента И 14 является управляющим выходом устройства и подключен к установочному входу триггера 11, и к входу элемента 17, Входы 28 реп/к стров группы 7 являются установочными, входами устройства. Выходы 29 регистров 7 и выходы 30 регистров б соединены соответственно с входами второй и первой групп блока 8. Выходы 31 блока 20 соединены с входами сброса соответствующих блоков 6. Блок выделения экстремума 8 содержит m групп по р) элементов сравнения.

Блок сравнения 32 содержит схему сравнения 33, первый 34 и второй 35 комутаторы, первый 36, второй 37 и третий 38 элементы ИЛИ, элемент НЕ 39 и элемент 40 И.

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

Предварительно счетчики 5, регистры 6, триггер 11 .регистры 9 и 10, счетчик 12 уста- новлены в нулевое состояние. Условно на чертежах цепи начальной установки не показаны. Перед началом работы в регистры (n 2т), где m - разрядность входных двоичных чисел массива (заносятся двоичные коды соответственно от минимального до максимального значений числа; в регистр 7г- код числа О, в регистр 7а - код числа 1, в регистр 7з двоичный код числа 2, и т.д., в регистр 7П - двоичный код числа п-1. Эти коды хранятся в регистрах 7 неизменными в течение всего времени работы устройства.

В счетчике 12 по входам 24 заносятся разряды ожидаемого числа, соответствующего объему массива сортируемых двоичных чисел.

На фиг. 1 синхровходы, управляющие записью информации перед работой устройства в блоки 7 и 12 отдельно, не выделены в составе соответственно входам 28 и 24.

После занесения в счетчик 12 длины массива сортируемых чисел на входы 22 устройства начинают поступать двоичные ко-ды сортируемых чисел. Каждое число массива сопровождается синхроимпульсом, поступающим на вход 23 с некоторым

запаздыванием относительно сигналов числа (на входах 22); цель организации запаздывания - необходимость к моменту поступления синхроимпульса на вход 23 наличия сформированных сигналов на выходах дешифратора 2.

С приходом каждого сортируемого числа (от 0 до 2т-1) на соответствующем выходе дешифратора 2 появляется сигнал; дешиф0 ратор 2 преобразует двоичный код числа в позиционный код, где единица находится в позиции, номер которой равен значению кода поступившего числа. С приходом синхроимпульса появляется разрешающий сиг5 нал на выходе элемента И 13 (по разрешающему положительному сигналу с выхода элемента НЕ 21 при отсутствии сигнала с выхода счетчика 12, который формируется счетчиком 12 при нулевом его

0 содержимом) и через соответствующий элемент И 4 поступает с дешифратора 2 сигнал на счетный вход соответствующего счетчика 5, Содержимое которого увеличивается на единицу. Сигнал с элемента И 13, кроме

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

0

После окончания ввода массива с вводом последнего числа одновременно с за- писью его (увеличение на единицу соответствующего счетчика 5) сигналом с

5 элемента 13 счетчик 12 устанавливается в нулевое состояние, в результате чего на его выходе появляется положительный потенциал, снимая положительный потенциал с входа элемента И 13 и тем самым запрещая

0 прохождение синхроимпульсов на вход устройства. Этот же положительный сигнал с выхода счетчика поступает на элемент И 14 и, совпадая с, положительным сигналом с триггером (находящегося в нулевом состоя5 нии), формирует сигнал на выходе элемента И 14, который поступает на установочный вход триггера и устанавливает его в единичное состояние, поступает на управляющий выход устройства в виде короткого импуль0 са, длительность.которого ограничена временем срабатывания триггера 11, и сигнализирующего о возможности (разрешении) ввода в устройство следующего массива чисел; этот же сигнал, поступая на

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

Таким образом, первая ступень устройства вновь подготавливается к приему следующего массива чисел (первая ступень устройства содержит блоки 2, 4, 5 и 6).

Положительный потенциал с триггера (с прямого выхода) после его переключения сигналом с элемента 14 (поступает на управляющий вход генератора импульсов 1 и запускает его. Генератор импульсов формирует тактовые импульсы для второй ступени сортировки, содержащей блоки 3, 6-11, 15, 16, 18-20. Вторая ступень сортировки работает следующим образом.

Частости поступления чисел в данном массиве, записанные после окончания первого этапа сортировки на первой ступени в регистры 6, поступают на устройства сравнения устройства выделения экстремума 8 - на его первые входы. На вторые входы устройства сравнения 32 устройства 8 поступают коды чисел, которым соответствуют эти частости с регистров 7. Каждое устройство сравнения работает следующим образом. .

В 1-е устройство сравнения 32 первой ступени на первый вход поступает частость чисел 21-1 от регистра 621-1, а на второй вход - частость числа 2i от регистра 621. Обозначим эти частости соответственно и В. Они поступают на схему сравнения 33, с выхода которой формируется сигнал в том случае, когда А В. На элементах ИЛИ 36 и 37 соответственно формируются положительные потенциалы в тех случаях, когда соответственно А & 0 и В 0, Логика работы элементов 36-40 такова, что реализует приводимую таблицу:

Для первой и последней строк таблицы сигнал с выхода элемента 36 - нулевой, с выхода элемента 39 - единичный и с выхода элемента 38 - также единичный. Для второй строки таблицы сигнала с выходов блоков 33, 36 и 37 - единичные, соответственно, с выходов элементов 40 и 38 - также единичные. Для третьей строки - нулевые сигналы с выходов элементов 33, 40, 39 и 38; для четвертой строки - нулевые сигналы с выходов элементов 37, 38, 39 и 40.

Таким образом, элементы 36-40 реализуют логическую функцию:

С (А ОМА 0) л (В 0) л (А В) При единичном значении функции С коммутатор 34 коммутирует на свои выходы вход В, при нулевом - вход А; коммутатор 35 соответственно коммутирует на свои выходы значение того числа, частость которого поступает на выход коммутатора 34 (первый выход устройства сравнения).

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

0 функцией) коммутируется ненулевая частость. Если же обе частости равны нулю, на выход коммутируется частость В, однако в данном случае более важным является фактор коммутации на первый выход НУЛЕВО5 ГО кода частости; этот момент будет обсуждён далее.

Сформированные попарно меньшие значения частостей по каждой паре из первой ступени, устройства 8 поступают в его

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

Пирамидальное построение устройства 8 (фиг. 2) позволяет после срабатывания по5 следней, m-й ступени, выделить на выходе (первом) устройства 8 наименьшую ненулевую частость среди всех числе массива, а на втором выходе - число, значение которого имеет в данном массиве наименьшую нену0 левую частость. Эти значения формируются на выходах устройства 8 сразу (с естественной задержкой на m ступенях устройства 8) после занесения данных в регистры б.

Первый импульс с выхода генератора 1,

5 формирующийся через определенное время после поступления на его управляющий вход разрешающего сигнала с триггера 1-1 (время задержки первого импульса и период следования импульсов с выхода генератора

0. 1 определяются задержкой срабатывания устройства 8 (всех его ступеней), осуществляет запись в регистры 9 и 10 соответственно значения числа с минимальной- ненулевой частостью и значение его часто5 ты, Тактовый импульс задерживается на элементе 18 и поступает на первые входы элементов И 20 второй группы. На эти же элементы (на вторые входы, вернее - на один из них) поступает позиционный код

0 номера регистра 6, частость которого выведена в данном такте в регистр 40, преобра- зуясь дешифратором 3 из двоичного кода, записанного в регистре 9. Сигнал с соответствующего элемента 20 сбрасывает в нуль

5 значение частости выведенного в данном такте числа.

В следующем такте (к моменту формирования следующего тактового импульса) на выходах устройства выделения экстремума формируется следующая по порядку миимальная ненулевая частость и соответствующее ей число; процесс повторяется анаогично.. --

Таким образом, с каждым тактовым импульсом равномерно последовательно выводятся на выходы 25 и 26 устройства астости чисел и соответствующие им числа. . Если все частости (ненулевые) выведены, на очередном такте на выходах регистра 40 имеет место нулевой код, что вызывает

появление единичного сигнала на выходе элемента 16 ИЛЙ-НЕ; задержанный элементом 19 тактовый импульс поступает на второй вход элемента 1.5 и вызывает появление на его выходе импульса, устанавливающего триггер 11 в нулевое состояние, сигнализируя об окончании второго этапа сортировки чисел, то есть, полного окончания процесса сортировки чисел данного массива. ... : -.

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

В начальном состоянии триггер 11 в нулевом состоянии, счетчик 12 - также; с выхода элемента 14 по сигналам (положительным) с инверсного выхода триггера и счетчика) - формируется на выход 27 сигнал разрешения-ввода следующего массива (в начальном состоянии -первого). При введении первого массива снимается положительный сигнал с выхода счетчика (положительный сигнал на его в ыходе характеризует нулевое состояние счетчика).

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

триггера 11 в единичное состояния, в результате чего на выходе 27 вновь устанавливается запрещающий сигнал. Короткий положительный импульс на выходе 27 устройства сигнализирует внешнему источнику о возможности ввода очередного (например, второго) массива чисел. Во время сортировки на второй ступени первого массива в первую ступень устройства может аналогичным образом вводиться и сортироваться второй массив чисел. Если длина второго массива меньше длины первого, счетчик 12, устанавливаясь в нулевое состояние, не вызывает формирования импульсов на выходе

27 и элемента 14, так как регистры 6 заняты вторичной сортировкой чисел первого массива. После окончания второй ступени сортировки чисел первого массива триггер 11. устанавливается в нулевое состояние, и

лишь в этот момент формируется сигнал на выходе элемента 4, переписывающий рассортированные на первой ступени устройства числа из счетчиков 5 в регистры 6; процесс вторичной сортировки второго и

последующих массивов на второй ступени осуществляется аналогично.

Если длина второго массива больше длины первого, триггер 11 устанавливается в нулевое состояние раньше счетчика 12, но

импульс на выходе 27 элемента 14 появляется в этом случает лишь после полной загрузки второго массива в первую ступень . устройства. Так осуществляется разделение массивов с возможностью одновременной

работы с разными массивами чисел на первой и второй ступенях.

Сигнал об окончаний полной сортировки массива (окончании работы второй ступени устройства) может быть снят-с выхода

элемента 15. .

Если необходимо провести сортировку максимальными значениями частостей вперед, во всех устройствах 32 переключается выход Больше на выход Меньше.

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

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

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

ИЛИ-НЕ, выходы второго дешифратора соединены с вторыми входами соответствующих элементов И второй группы, выходы которых подключены к входам сброса соответствующих регистров первой группы.

2. Устройство по п. 1, о т л и ч а ю ще е- с я тем, .что блок выделения экстремума содержит m групп по р блоков сравнения в 1-й группе, где m - разрядность сортируемых чисел массива, 1 1, т, р| , входы блоков сравнения первой группы являются входами блока, входы с первого по четвертый К-го Щюка сравнения 1-й группы, I 2, m, k Т, 2т соединены соответственно с первыми выходами 2k-1-ro и 2k-ro блоков сравнения (И)-й группы и с вторыми выходами 2k-1-ro и 2k-ro блоков сравнения (И)-й группы, выходы блока сравнения m-й группы являются выходами блока.... . 3. Устройство по п. 1,отличающее- с я тем, что блок сравнения содержит схему сравнения, три элемента ИЛИ. два коммутатора, элемент И и элемент НЕ, причем первый и второй входы блока сравнения соединены соответственно с входами первого, и второго элементов ИЛИ, соответственно с входами первой и второй групп схемы сравнения и соответственно с информационными входами первой и второй групп первого коммутатора, выход которого является первым выходом блока сравнения, третий и четвертый входы блока сравнения соединены соответственно с информационными входами первой и второй групп второго коммутатора, выход которого является вторым выходом блока сравнения, выходы первого и второго элементов ИЛИ и схемы сравнения соединены с входами элемента И, выход которого подключен к первому входу третьего элемента ИЛИ, второй вход которого через элемент НЕ соединен с выходом первого элемента ИЛИ, а выход подключен к управляющим входам первого и второго коммутаторов.