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

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

УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ДВОИЧНЫХ ЧИСЕЛ, содержащее генератор тактовых импульсов, счетчики, две группы триггеров, группу элементов И, элемент ИЛИ и элемент Ш1И-НЕ, входы которого соединены с выходами триггеров первой группы, отличающееся тем, что, с целью расширения области применения устройства за счет возможности сортировки равных чисел, в него введены выходной счетчик, преобразователь числа единиц в двоичный код, буферный счетчик, второй элемент ИЛИ, регистр адреса, дешифратор адреса, выходные регистры и блок управления, включающий два триггера, пять элементов И, два элемента НЕ, элемент задержки и формирователь импульсов, причем вход запуска устройства соединен с единичным входом первого триггера блока управления, прямой выход которого соединен с входом управления генератора импульсов, первый выход которого подключен к первым входам первого и второго элементов И блока управления, а второй выход - к первым входам третьего и четвертого элементов И блока зшрав- ления, в блоке управления вторые входы второго и четвертого элементов И соединены с прямым выходом второго триггера, инверсный выход которого подключен к вторьм входам первого и третьего элементов И, третьи входы которых соеди нены соответственно с выходом и входом первого элемента НЕ, выход третьего элемента И через второй элемент НЕ соединен с входом синхронизации второго триггера, информационный вход которого подключен к входу логической единицы устройства, выход элемента задержки соединен с третьем входом четвертого элемента И и вхо-дом формирователя импульсов, выход которого соединен с первым входом пятого элемента И, нулевым входом второго триггера и синхронизирукндими входами триггеров первой группы, выход первого элемента И блока управления соединен с вычитающим входом выходного счетчика и суммирукшщми входами счетчиков, установочные входы которых являются входами соответствующих сортируемых чисел устройстЮ ва, а выходы переполнения подключеСП ны к синхронизирующим входам соответствующих триггеров второй группы, () информационные входы которых подключены к входу логической единицы устройства-, а выходы соединены с информационными входами соответствующих триггеров первой группы и первыми входами соответствующих элементов И группы, вторые входы которых ПОД1СПЮ чены к выходам соответствующих триггеров первой, группы, а выходы соединены с входами: первого элемента ИЛИ и cooтвeтcVвyнж ими входами преобразователя числа единиц в двоичный кодэ выходы которого соединены с соответ

Изобретение относится к вычислительной технике и может быть исполь зовано в вычислительных процессорах ,при выполнении операдай сравнения по величинам кодовых комбинаций по мере возрастания их величин, в устройствах обработки спектров сложных сигналов. Цель изобретения - расширение об лй.сти применения устройства за счет Еозможности сортировки равных чисел На фиг. 1 приведена функциональ ная схема устройства , на фиг. 2 функциональная схема блока управления f на фиг. 3 - временная диаграмма работы блока управления. Устройство содержит счетчики 1,{ - 1(1, выходной счетчик 2, триггеры ,,, триггеры 4i-АИ, группу элеме тов И 5i-5rt, преобразователь 6 числа единиц в двоичньй код, элемент ИЛИ 7, элемент ИЛИ-НЕ 8, буферный счетчик 9, элемент ИЛИ 10, регистр 11 адреса, дешифратор ,.12 адреса, выходные регистры 13,-13|, блок 14 упуавления, входы сортируемых чисел 15 -15tt, вход запуска 16, выход 17 кснца работы, генератор 18 тактовых импул сов. . Блок 14 управления содержит элемент НЕ 19, элементы И 20 и 21, триггер 22, элемент НЕ 23, триггер 24J формирователь импульсов 25, эле менты И 26 и 27, элемент 28 задержsa-j, элемент И 29, выход 30 г,енерато ра тактовых импульсов, входы 31-33, эыходы 34-38. Счетчики 1)-1 служат для ввода и хранения сортируемых чисел. Выходной счетчик 2 слуйсит для формирования текущего значения числа перед записью его в выходные регистры 13 1-13ц. Триггеры 3 (-3 и 4;,- 4 и группа элементов И служат для выработки признака переполнения счетчиков в цикле сортировки. Элемент ИЛИ 7 служит для вьфаботки признака переполнения любого из входных счетчиков 1,-1. Преобразователь 6 служит для преобразования количества переполненных счетчиков в цикле работы в двоичный код. Элемент ИЛИ-НЕ 8 служит для формирования признака установления всех триггеров 4)-4ц в единичное состояние. Буферный счетчик 9 служит для подсчета коли 1ества равных чисел при их сортировке и перезаписи в выходные регистры 13 1-13ц. Элемент ИЛИ 10 служит для выработки признака нулевого состояния буферного счетчика 9. Регистр 11 адреса и дешифратор 12 адреса служат для формирования адреса регистра 13) -13fi, куда записьшаются сортируемые ро величине числа, причем в старшие адреса регистров записываются наименьшие из сортируемых чисел, а в младшие адреса - максимальные в соответствии со своим рангом числе.

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

Элементы устройства выполнены например, на типовых цифровых интегратор ных схемах TTL серии 133, К155, 130, К131, 530, К531, К555.

Формирователь 25 и генератор 18 тактовых импульсов могут быть реализованы, например, на базе типовых формирователей К155АГЗ с учетом логики функционирования и временных параметров. Элемент 28 задержки может быть выполнен на базе интегрирунщей цепочки с пороговым устройством (триггером Шмитта) на ее выходе. Денмфратор 12 адреса реализуется, например, на базе микросхемы К155ИДЗ Регистр 11 адреса вьтолнлется в виде двоичного счетчика. Кодопреобра зователь 6 реализуется, например, на -базе типовых логических элементов .с учетом логики преобразования количества поступивших единиц на его вхо.ды в двоичный код (см. таблицу).

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

В исходном состоянии в счетчики 1,-1 произвольно заносятся сорти- . руемые числа, поступающие по входам 15,-15п. Выходной счетчик 2, триггеры З.-З и 4,-4, а также буферш счетчик 9, регистр 11 адреса и выход ные регистры 13,-l3ji .обнуляются. Триггер 22 установлен в нулевое состояние, так что на его выходе имеется нулевой потенциал и генератор 18 тактовых импульсов заблокирован. Триггер 24 установлен в нулевое состояние так, что на его первом (прямом) выходе нулевой потенциал. (Цепи начальной установки элементов устройства на фиг. 1 и 2 не показаны). Задача состоит в том, что записанные во входных счетчиках числа в конце сортировки перенести в выходные регистры в порядк убывания их величины, начиная с регистра 13I.

В таблице представлено состояние выходов преобразователя 6 в зависимости от состояния его входов.

На входе 16 поступает сигнал пуск устройства, который по первому входу триггера 22 устанавливает последний в ед(1ничное состояние. Генератор 18

разблокируется, и на его первом и втором выходах появляются тактовы импульсы ТИ 1 и ТИ 2, не перекрывающиеся во времени (см. фиг. 3). На первых входах группы элементов И 5| - потенциал нулевого уровня, а на их вторых входах - единичный потенциал, поэтому на выходах группы элементов И (, - нулевые потенциалы и, соответственно, такой же потенциал на выходе первого элемента ИЛИ 7, который поступает на разрешаю1 й вход элемента И 20 блок

управления. f

В такте ТИ1 срабатывает элемент И 20, на выходе которого появляются импульсы, поступающие на вычитаю;;а й вход выходного счетчика 2 к сум -ирующие входы входных счетчиков 1,1, при этом содержимое выходного счетчика 2 уменьшается, а содержимое входных счетчиков 1,-1 увеличивается . Когда на входы счетчиков 1,(-1ц поступит такое количество им.пульсов, что на любом из выходов переполнения входных счетчиков 1j появится сигнал переполнения, устанавливающий соответствующий триггер 3| в единичное состояние, сработает соответствующий- элемент И 5 группы На выходе счетчика 2 при этом устанвится код числа, соответствующего коду чисел, записанных в те входные счетчики 1(-1ц, где произошло переполнение (перенос), поскольку происходил, обратный счет от нулевого значения в счетчике 2 кольцевого типа. На выходе элемента 1ШИ 7 устаналивается единичный потенциал. Количество установленных в 1 триггеров зависит от количества равных максимальных чисел, записанных во входные счетчики 1 .-1j. Соответственно, преобразователь 6 преобразует это число сработанных элементов И 5,-5 группы в двоичный код, который и поступает на информационные входы буферного счетчика 9.

Во втором такте ТИ.2 срабатывает первый элемент И 21, и на выходе 34 блока 14 управления появляется сигнал перезаписи состояния выходов преобразователя 6 в буферньй счетчик 9, который изменяет свое нулево состояние, и на выходе элемента ИЛИ 10 устанавливается единичный потенциал, поступакнций на вход элемента 28 задержки и третий вход третьего элемента И 26. По фронту () импульса с выхода инвертора 23 триггер 24 устанавливается в 1, при этом с его.инверсного выхода нулевым потенциалом.блоки руются по третьим входам первый и второй элементы И 20 и 21. С прямого выхода триггера 24 на вторые входы элементов И 26 и 27 прступает сигнал разрешения. Далее в такте ТИ 1 стробируется элемент И 26, с выхода которого сигнал поступает на соответствунлдий выход деглифратора 12 адреса, на первьй управляющий вход регистра 13( поступает разрешающий потенциал По совпадению разрешения на первом и втором управляюи.щх .входах регистра 13{ по переднему фронту сигнала выхода 36 блока 14 управления происходит запись в регистр 13, содержимо го выходного счетчика 2, т.е. кода тех чисел, которые бьши записаны в счетчики с переполнением. В следующем такте ТИ2 стробируется четвертый элемент И 27, с выхода которого сигнал поступает на выход 35блока 14 управления. По сигналу с выхода 35 блока 14 управления буферHbBi реверсивный счетчик 9 уменьшает содержимое на 1, а содержимое регистра 11 адреса увеличивается на +1. Поскольку ранее в буферньш счетчик 9 бьш записан двоичньш код числа 3 (соответствующего количеству максимальных равных чисел), то в счетчи ке 9 окажется двоичньм код числа 2, В регистре 11 адреса содержимым станет код 00.,„1, следующий в поряд ке возрастания за нулевым адресом. На соответствующем выходе дешифратора 12 адреса выставится разрешение для первого управляющего входа регис ра 132, В последующем такте ТИ 1 стробируется элемент И 26, сигнал с которого поступает на третий выход 36блока 14 управления, И6совпадению разрешения на первом и втором управляющих входах регистра 132 происходит перезапись содержимого выходного счетчика 2. Аналогично происходит перезапись по следующем такту ТИ 1 и третьего рав ного максимального числа в регистр 13з, Однако в следующем такте ТИ 2 стробируется элемент И 27, сигнал с яыхода которого поступает на нычитающий вход буферного счетчика 9. Содержимое счетчика становится нулевым, на выходе второго элемента ИЛИ 10 установится нулевой потенциал. Этот потенциалблокирует по третьему входу элемент И 26 и через (дд элемента 28 задержки элемент И 27. По фронту (1 0) сигнала с выхода элемента 28 задержки запускается формирователь импульсов 25, сигналом с выхода которого происходит установка в нулевое состояние триггера 24, а сигналом с выхода 37 блока 14 управления происходит перезапись состояния выходов триггеров 3 -3f) в группу еоответствующих вторых триггеров 4 -4 1. При этом триггеры 4., которые бьиш соединены с выходами триггеров 3, установленных сигналами переполнения в 1, установятся также в 1, а соответствующие ранее сработанные элементы И 5 заблокируются сигналами с инверсных выходов этих триггеров 4j. Состояние остальных триггеров 4 j-4 не изменится. На всех выходах элементов И установится нулевой потенциал, соответственно на выходе первого элемента ИЛИ 7 - нулевой потенциал, который поступает на вход 31 блока 14 управления. В такте ТИ .1 срабатывает элемент И 20, на выходе которого появляются импульсы, поступающие на выход 37 блока 14 управления и далее на вычитающий вход выходного счетчтка 2 и суммирующие входы входных счетчиков . Эти: импульсы поступают до тех пор, пока на любом из выходов переполнения входных счетчиков 1 -1, появится сигнал переполнения, а в выходном счетчике 2 установится код чис- . ла (чисел), следующего за максимальными в порядке убывания из исходных чисел, записанных в начале сортировки во входные счетчики 1(-1t,. Ци1ш анализа и сортировки повтоярется аналогично предьщущему. При сортировке последнего числа (чисел) в последнем цикле по сигналу с выхода 36 блока 14 управления происходит установка в единичное состояние последних триггеров группы, так что на всех входах элемента ИЛИ-НЕ 8 - нулевой потенциал, поступаюпцй на вход 33 блока управП НИЯ.

На выходе 17 элемента И 29 по-ся. В выходных регистрах i-f,-13.. в

является сигнал об окончании, работы .конце сортировки: значения чиСла, заустройства, триггер 22 устанавливает-писанные в начале сортировки во

ся в нулевое состояние, работа гене- jвходные счетчики, поочередно записыратора тактовых импульсов блокирует:-ваются, начиная с максимального.

продолжение табл,

(