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

(51)4 С 06 Р 7/06 ЕТЕН К АВТОРСКОМУ СВИД.:ТЕЛЬСТВУ единены с выходамигруппы, о т л и -1 которого в триггеров перво ч а ю щ е е с я тем, что, с целью и применения устозможности сортира ширения обла тва за счет рои ОСУДАРСТВЕННЫЙ НОМИТЕТ СССР ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТ ОПИСАНИЕ ИЗО(54)(57) УСТРОЙСТВО ДЛЯ СОРТИРОВКИДВОИЧНЫХ ЧИСЕЛ, содержащее генераттактовых импульсов, счетчики, двегруппы триггеров, группу элементовИ, элемент ИЛИ и элемент ИЛИ-НЕ,ровки равных чисел, в него введенывыходной счетчик, преобразовательчисла единиц в двоичный код, буферный счетчик, второй элемент ИЛИ,регистр адреса, дешифратор адреса,выходные регистры и блок управлениявключающий два триггера, пять элементов И, два элемента НЕ, элементзадержки и формирователь импульсов,причем вход запуска устройства соединен с единичным входом первоготриггера блока управления, прямойвыход которого соединен с входомуправления генератора импульсов,первый выход которого подключен кпервым входам первого и второго элементов И блока управления, а второйвыход - к первым входам третьего ичетвертого элементов И блока управления, в блоке управления вторыевходы второго и четвертого элементов И соединены с прямым выходом второго триггера, инверсный выход которого подключен к вторым входам первогои третьего элементов И, третьи входы которых соединены соответственно с выходом и входом первого элемента НЕ, выход третьего элемента И через второй элемент НЕ соединен с входом синхронизации второго триггера, информационный вход которого подключен к входу логической единицы устройства, выход элемента задержки соединен с третьем входом четвертого элемента И и входом формирователя импульсов, выход которого соединен с первым входом пятого элемента И, нулевым входом второго триггера и синхронизируюцими в входами триггеров первой группы, выход первого элемента И блока управления соединен с вычитаюцим входом выходного счетчика и суммирующимивходами счетчиков, установочные входы которых являются входами соответствующих сортируемых чисел устройства, а выходы переполнения подключены к синхронизирующим входам соответствующих триггеров второй группы, информационные входы которых подключены к входу логической единицы устройства, а выходы соединены с информационными входами соответствующих триггеров первой группы и первымв входами соответствующих элементов И группы, вторые входы которых подключены к выходам соответствующих триггеров первой .группы, а выходы соединены с входами: первого элемента ИЛИ и соответс 1 гвуюцими входами преобразователя числа единиц в двоичный код, выходы которого соединены с соответ1182509 ствующими информационнымивходами буферного счетчика, выходы разрядовкоторого соединены с входами второгоэлемента ИЛИ, выход которого подключен к входу элемента задержки итретьему входу второго элемента иблока управления, выход которого соединен с первыми входами разрешениязаписи выходных регистров, информационные входы которых соединены свыходами выходного счетчика и вторыевходы разрешения записи подключенык соответствующим выходам дешифратора адреса, входы которого соединеныс соответствующими выходами регистИзобретение относится к вычислительной технике и может быть использовано в вычислительных процессорах при выполнении операций сравнения по величинам кодовых комбинаций по 5 мере возрастания их величин, в устройствах обработки спектров сложных сигналов.Цель изобретения - расширение об. ласти применения устройства за счет 1 О возможности сортировки равных чисел,На Фиг. 1 приведена функциональчая схема устройства, на фиг. 2 - функциональная схема блока управления, на фиг. 3 - временная диаг рамма работы блока управления. Устройство содержит счетчики 1,11 п, выходной счетчик 2, триггеры 31 -3, триггеры 41 -4 , группу элемен тов И 5,-5, преобразователь 6 числа единиц в двоичный код, элемент ИЛИ 7, элемент ИЛИ-НЕ 8, буферный счетчик 9, элемент ИЛИ 10, регистр 11 адреса, дешифратор 12 адреса, 2 вьжодные регистры 13 -13, блок 14 упавления, входы сортируемых чисел 15-15, вход запуска 16, выход 17 конца работы, генератор 18 тактовых импул сов.ЗОБлок 14 управления содержит элемент НЕ 19, элементы И 20 и 21, триггер 22, элемент НЕ 23, триггер .24 Формирователь импульсов 25, элементы И 26 и 27, элемент 28 задержгл. элемент И 29, выход 30 генерато35 ра адреса, суммирующий вход которогосоединен с вычитающим входом буферного счетчика и выходом четвертогоэлемента И блока управления, выходпервого элемента ИЛИ подключен ктретьему входу третьего элемента Иблока управления, выход которогоподключен к синхронизирующему входубуферного счетчика, выход элементаИЛИ-НЕ соединен с вторым входом пятого элемента И блока управления, выходкоторого подключен к нулевому входупервого триггера блока управленияи является выходом конца работыустройства,ра тактовых импульсов, входы 31-33,выходы 34-38. Счетчики 1 -1 служат для ввода и хранения сортируемых чисел. Выходной счетчик 2 служит для Формирования текущего значения числа перед записью его в выходные регистры 13 -13. Триггеры 3 1-Зи 4- 4и группа элементов И 5 -5 служат для выработки признака переполнения счетчиков 11-1 в цикле сортировки, Элемент ИЛИ 7 служит для выработки признака переполнения любого из входных счетчиков 1-1. Преобразователь 6 служит для преобразования количества переполненных счетчиков 1-1 д в цикле работы в двоичный код. Элемент ИЛИ-НЕ 8 служит для формирования признака установления всех триггеров 4-4 в единичное состояние, Буферный счетчик 9 служит для подсчета количества равных чисел нри их сортировке и перезаписи в выходные регистры 13-13. Элемент ИЛИ 10 служит для выработки признака нулевого состояния буферного счетчика.9. Регистр 11 адреса и дешифратор 12 адреса служат для формирования адреса регистра 13 - -13 , куда записываются сортируемые по величине числа, причем в старшие адреса регистров записываются наименьшиеиз сортируемьж чисел, а в младшие адреса - макгимальные в соответствии со своим рангом числа.11825 Блок 14 управления служит для выработки импульсов синхронизации для элементов устройства с.учетом условий, сформированных в предыдущем такте. 5Элементы устройства выполнены например, на типовых цифровых интеграторных схемах ТТ 1. серии 133, К 155, 130, К 131, 530, К 53 1, К 555.Формирователь 25 и генератор 18 10 тактовых импульсов могут быть реализованы, например, на базе типовых Формирователей К 155 АГЗ с учетом логики функционирования и временных параметров. Элемент 28 задержки мо жет быть выполнен на базе интегрирующей цепочки с пороговым устройством (триггером Шмитта) на ее выходе. Дешифратор 12 адреса реализуется, например, на базе микросхемы К 155 ИДЗ, 20 Регистр 11 адреса выполняется ввиде двоичного счетчика. Кодопреобразователь 6 реализуется, например, на базе типовых логических элементов .с учетом логики преобразования коли. чества поступивших единиц на его входы в двоичный код (см. таблицу). Устройство работает следующим образом.В исходном состоянии в счетчики 1 -1 произвольно заносятся сортируемые числа, поступающие по входам 15,-15 я, Выходной счетчик 2, триггеры 3 -3 и 41-4, а также буферный счетчик 9, регистр 11 адреса и выходные регистры 13-13, .обнуляются. Триггер 22 установлен в нулевое состояние, так что на его выходе имеется нулевой потенциал и генератор 18 тактовых импульсов заблокирован, 40 Триггер 24 установлен в нулевое состояние так, что на его первом (прямом) выходе нулевой потенциал. (Цепи начальной установки элементов устройства на фиг, 1 и 2 не показа ны). Задача состоит в том, что записанные во входных счетчиках 1 -1 числа в конце сортировки перенести в выходные регистры 131-13 в порядке убывания их величины, начиная с ре гистра 13.В таблице представлено состояние выходов преобразователя 6 в зависимости от состояния его входов.На входе 16 поступает сигнал пуска 55 устройства, который по первому входу триггера 22 устанавливает последний в единичное состояние. Генератор 18 09 4разблокируется, и на его первом и втором выходах появляются тактовые импульсы ТИ 1 и ТИ 2, не перекрывающиеся во времени (см, фиг. 3). На первых входах группы элементов И 5- - 5 - потенциал нулевого уровня, а на их вторых входах - единичный потенциал, поэтому на выходах группы элементов И 5-5 и - нулевые потенциалы и, соответственно, такой же потенциал на выходе .первого элемента ИЛИ 7, который поступает на разрешающий вход элемента И 20 блока управления.В такте ТИ 1 срабатывает элемент И 20, на выходе которого появляются импульсы, поступающие на вычитающий вход выходного счетчика 2 и суммирующие входы входных счетчиков 1, -1, при этом содержимое выходного счетчика 2 уменьшается, а содержимое входных счетчиков 1 -1 увели 4 О чивается, Когда на входы счетчиков 1 -1 поступит такое количество импульсов, что на любом из выходов переполнения входных счетчиков 1 появится сигнал переполнения, устанавливающий соответствующий триггер 3, в единичное состояние, сработает соответствующий элемент И 5 группы,4 На выходе счетчика 2 при этом устано. вится код числа, соответствующего коду чисел, записанных в те входные счетчики 1-1, где произошло переполнение (перенос), поскольку происходил. обратный счет от нулевого значения в счетчике 2 кольцевого типа, На выходе элемента ИЛИ 7 устанавливается единичный потенциал, Количество установленных в " 1" триггеров 3, зависит от количества равных максимальных чисел, записанных во входные счетчики 1 -1 . СоответстИвенно, преобразователь 6 преобразует это число сработанных элементов И 51-5группы в двоичный код, который и поступает на информационные входы буферного счетчика 9.Во втором такте ТИ.2 срабатывает первый элемент И 21, и на выходе 34 блока 14 управления появляется сигнал перезаписи состояния выходов преобразователя 6 в буферный счетчик 9, который изменяет свое нулевое состояние, и на выходе элемента ИЛИ 10 устанавливается единичный потенциал, поступанщий на вход элемента 28 задержки и третий вход("0" "1") импульса с выхода инвертора 23 триггер 24 устанавливается в "1", при этом с его.инверсного выхода нулевым потенциалом. блокируются по третьим входам первый ивторой элементы И 20 и 21. С прямоговыхода триггера 24 на вторые входыэлементов И 26 и 27 прступает сигнал 1 Оразрешения,Далее в такте ТИ 1 стробируетсяэлемент И 26, с выхода которого сигнал поступает на соответствующийвыход дешифратора 12 адреса, на 15первый управляющий вход регистра13 поступает разрешающий потенциал,По совпадению разрешения на первоми втором управляющих входах регистра 131 по переднему фронту сигнала 20выхода 36 блока 14 управления происхоцит запись в регистр 13 содержимо"го выходного счетчика 2, т.е. кодатех чисел, которые быпи записаныв счетчики 1-1 с переполнением. . 25В следующем такте ТИ 2 стробируется четвертый элемент И 27, с выходакоторого сигнал поступает на выход35 блока 14 управления. По сигналу свыхода 35 блока 14 управления буферный реверсивный счетчик 9 уменьшаетсодержимое на "1", а содержимое регистра 11 адреса увеличивается на+1. Поскольку ранее в буферный счетчик 9 был записан двоичный код числа3 (соответствующего количеству максимальных равных чисел), то в счетчике 9 окажется двоичный код числа2, В регистре 11 адреса содержимымстанет код 001, следующий в поряд ке возрастания за нулевым адресом.На соответствующем выходе дешифратора 12 ацреса выставится разрешениедля первого управляющего входа регистра 13. В последующем такте ТИ 1 45стробируется элемент И 26, сигнал скоторого поступает на третий выход36 блока 14 управления.Иосовпадению разрешения на первом и втором управляющих входах регистра 13 происходит перезапись содержимого выходного счетчика 2.Аналогично происходит перезапись по следующему такту ТИ 1 и третьего рав" ного максимального числа в регистр 13, . Оцнако в следующем такте ТИ 2 стробируется элемент И 27, сигнал с выхода которого поступает на вычитающий вход буферного счетчика 9. Содержимое счетчика становится нулевым, на выходе второго элемента ИЛИ 10 установится нулевой потенциал. Этот потенциалблокирует по третьему входу элемент И 26 и через ь ц элемента 28 задержки элемент И 27. По Фронту (1 -ь О) сигнала с выхода элемента 28 задержки запускается формирователь импульсов 25, снгналом с выхода которого происходит установка в нулевое состояние триггера 24, а сигналом с выхоца 37 блока 14 управления происходит перезапись состояния выходов триггеров 31 -31 в группу еаответствующих вторых триггеров 4 -4 . При этом триггеры 4 , которые были соединены с1выходами триггеров 3, установленныхф фсигналами переполнения в "1", установятся также в "1", а соответствующие ранее сработанные элементы И 51 заблокируются сигналами с инверсных выходов этих триггеров 4,. Состояние остальных триггеров 4 -4не изменится, На всех выходах элементов И 5 -5 установится нулевой1 Опотенциал, соответственно на выходе первого элемента ИЛИ 7 - нулевой потенциал, который поступает на вход 31 блока 14 управления. В такте ТИ .1 срабатывает элемент И 20, на выходе которого появляются импульсы, поступающие на выход 37 блока 14 управления и далее на вычитающий вход выходного счетчтка 2 и суммирующие входы входных счетчиков 11-1,. Эти импульсы поступают до тех пор, пока на любом из выходов переполне" ния входных счетчиков 11 -1 появится сигнал переполнения, а в выходном счетчике 2 установится код числа (чисел), следующего за максимальными в порядке убывания из исходных чисел, записанных в начале сортировки во входные счетчики 1-1. Цикл анализа и сортировки повтояретсяаналогично предыдущему При сортировке последнего числа(чисел) в последнем цикле по сигналус вьг"ода 36 блока 14 управленияпроисходит установка в единичноесостояние последних триггеров 4-4группы, так что на всех входах элемента ИЛИ-НЕ 8 - нулевой потенциал,поступающий на вход 33 блока управпения,1182509 22 1 2 3 2 о 0 О 0 О 0 О О О 0 0 0 О О 0 О 0 0 0 0 0 0 0 0 0 0 О О О 0 0 0 0 0 0 О 0 О О 0 О О О О 0 О О 0 О О О О 0 1 1 О 0 1 0 О 1 1 1 О 0 0 На выходе 17 элемента И 29 появляется сигнал об окончании, работы устройства, триггер 22 устанавливается в нулевое состояние, работа генератора тактовых импульсов блокируетВходы преобразователя 6Г 1 1 О О О 1 1 0 О 1 О 1 О 0 0 1 1 0 О 1ся. В выходных регистрах 5, -13. вконце сортиронк значения числа, записанные в начале сортировки вовходные счетчики, поочередно записываются, начиная с максимального. Выходы преобразователя 6.й Аирй рцсгера Всадяааэю е М Жал Уманью Я-й Рой ОЖою э Ф йриФР6 явкою Йчрй аж 709 Подаисао ИИПИ Заказ ь 107/47 фвафеаффее Уйгоро йиФарищюИЬрй Вилеещюийюй