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

 

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

СОЮЗ СОВЕТСКИХ . СОЦИАЛИСТИЧЕСНИХ

РЕСПУБЛИН (19) (!! ) (51)4 G 06 F 7/06

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

Н АВТОРСНОМУ СВИД=ТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 3725862/24-24 (22) 13 ° 04.84 (46) 30.09.85, Бюл. Р 36 (72) А ° Н.Мурашко (53) 681.325(088.8) (56) Авторское свидетельство СССР

1)- 1049900, кл. G 06 F 7/02, 1983.

Авторское свидетельство СССР

Ф 638955, кл . G 06 F 7/06, 1977, (54) (57) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ

ДВОИЧНЫХ ЧИСЕЛ, содержащее генератор тактовых импульсов, счетчики, две группы триггеров, группу элементов

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

Цель изобретения — расширение области применения устройства за счет 1О возможности сортировки равных чисел.

На фиг. 1 приведена функциональчая схема устройства, на фиг. 2— функциональная схема блока управления, на фиг. 3 — временная диаграмма работы блока управления.

Устройство содержит счетчики 1, 1п, выходной счетчик 2, триггеры

31 -3» триггеры 41 -4 ь, группу элемен тов И 51-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 reeepavoi

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

ИЛИ-НЕ соединен с вторым входом пятого элемента И блока управления, выход которого подключен к нулевому входу первого триггера блока управления и является выходом конца работы устройства. ра тактовых импульсов, входы 31-33, выходы 34-38.

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

13 -13„. Триггеры 3 1-З„и 4„- 4 „ и группа элементов И 5 -5 служат для выработки признака переполнения счетчиков 11-1 в цикле сортировки, Элемент ИЛИ 7 служит для выработки признака переполнения любого из входных счетчиков 14 -1„. Преобразователь 6 служит для преобразования количества переполненных счетчиков

1 -1д в цикле работы в двоичный код. Элемент ИЛИ-HE 8 служит для формирования признака установления всех триггеров 4 -4 в единичное состояние. Буферный счетчик 9 служит для подсчета количества равных чисел при их сортировке и перезаписи в выходные регистры 13 -13 . Элемент ИЛИ 10 служит для выработки признака нулевого состояния буферного счетчика.9. Регистр 11 адреса и дешифратор 12 адреса служат для формирования адреса регистра 13>—

-13, куда записываются сортируемые по величине числа, причем в старшие адреса регистров записываются наименьшие из сортируемьж чисел, а в младшие адреса — макгимальные в соответствии со своим рангом числа.

11825

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

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

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

Дешифратор 12 адреса реализуется, например, на базе микросхемы К155ЩЗ, 20

Регистр 11 адреса выполняется в виде двоичного счетчика. Кодопреобразователь 6 реализуется, например, на .базе типовых логических элементов

Ъ .с учетом логики преобразования коли- 25. чества поступивших единиц на его входы в двоичный код (см. таблицу).

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

В исходном состоянии в счетчики

1 -1 произвольно заносятся сортируемые числа, поступающие по входам

15,-15 . Выходной счетчик 2, триггеры 3 -3 и 41-4п, а также буферный счетчик 9, регистр 11 адреса и выход-35 ные регистры 13,-13„, .обнуляются.

Триггер 22 установлен в нулевое состояние, так что на его выходе имеется нулевой потенциал и генератор 18 тактовых импульсов заблокирован. 40

Триггер 24 установлен в нулевое состояние так, что на его первом (прямом) выходе нулевой потенциал. (Цепи начальной установки элементов устройства на фиг. 1 и 2 не показа- 45 ны). Задача состоит в том, что записанные во входных счетчиках 1 -1 числа в конце сортировки перенести в выходные регистры 131-13„ в порядке убывания их величины, начиная с ре- 50 гистра 13 .

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

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

09 4 разблокируется, и на его первом и втором выходах появляются тактовые

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

В такте ТИ1 срабатывает элемент

И 20, на выходе которого появляются импульсы, поступающие на вычитающий вход выходного счетчика 2 и суммирующие входы входных счетчиков

1, -1„, при этом содержимое выходного счетчика 2 уменьшается, а содержимое входных счетчиков 1 -1 увелиЧ чивается. Когда на входы счетчиков

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 задержки и третий вход!

182509 третьего элемента И 26. По фронту ("0" — "1") импульса с выхода инвертора 23 триггер 24 устанавливается в 1, при этом с его.инверсного выхода нулевым потенциалом, блокиI руются по третьим входам первый и второй элементы И 20 и 21. С прямого выхода триггера 24 на вторые входы элементов И 26 и 27 прступает сигнал 10 разрешения.

Далее в такте ТИ 1 стробируется элемент И 26, с выхода которого сигнал поступает на соответствующий выход дешифратора 12 адреса, на 15 первый управляющий вход регистра

13 поступает разрешающий потенциал, По совпадению разрешения на первом и втором управляющих входах регистра 131 по переднему фронту сигнала 20 выхода 36 блока 14 управления происхоцит запись в регистр 13< содержимо" го выходного счетчика 2, т.е. кода тех чисел, которые быпи записаны в счетчики 1I-1 с переполнением.

В следующем такте ТИ2 стробируется четвертый элемент И 27, с выхода которого сигнал поступает на выход

35 блока 14 управления. По сигналу с выхода 35 блока 14 управления буфер- 30 ный реверсивный счетчик 9 уменьшает содержимое на "1", а содержимое регистра 11 адреса увеличивается на

+1. Поскольку ранее в буферный счетчик 9 был записан двоичный код числа

3 (соответствующего количеству мак симальных равных чисел), то в счетчике 9 окажется двоичный код числа

2. В регистре 11 адреса содержимым станет код 00...1, следующий в поряд-4О ке возрастания за нулевым адресом.

На соответствующем выходе дешифратора 12 ацреса выставится разрешение для первого управляющего входа регистра 13 . В последующем такте ТИ 1 45 стробируется элемент И 26, сигнал с которого поступает на третий выход

36 блока 14 управления.

Ио совпадению разрешения на первом и втором управляющих входах регистра 13, происходит перезапись содержимого выходного счетчика 2.

Аналогично происходит перезапись по следующему такту ТИ 1 и третьего равного максимального числа в регистр

13, . Оцнако в следующем такте ТИ 2 стробируется элемент И 27, сигнал с выхода которого поступает на вычитающий вход буферного счетчика 9.

Содержимое счетчика становится нулевым, на выходе второго элемента

ИЛИ 10 установится нулевой потенциал. Этот потенциал блокирует по третьему входу элемент И 26 и через ь ц элемента 28 задержки элемент

И 27. По фронту (1 - О) сигнала с выхода элемента 28 задержки запускается формирователь импульсов 25, снгналом с выхода которого происходит установка в нулевое состояние триггера 24, а сигналом с выхоца 37 блока 14 управления происходит перезапись состояния выходов триггеров

3 -3 в группу еаответствующих вторых триггеров 4 -4 „. При этом триг-. геры 4, которые были соединены с

1 выходами триггеров 3, установленных

9 сигналами переполнения в "1", установятся также в "1", а соответствующие ранее сработанные элементы И 5

I заблокируются сигналами с инверсных выходов этих триггеров 4, . Состояние остальных триггеров 4,-4 не изменится. На всех выходах элементов И 5 -5 установится нулевой

1 б потенциал, соответственно на выходе первого элемента ИЛИ 7 — нулевой потенциал, который поступает на вход

31 блока 14 управления. В такте

ТИ .1 срабатывает элемент И 20, на выходе которого появляются импульсы, поступающие на выход 37 блока 14 управления и далее на вычитающий вход выходного счетчтка 2 и суммирующие входы входных счетчиков 1 -1>, Эти импульсы поступают до тех пор, пока на любом из выходов переполнения входных счетчиков 11 -1 появится сигнал переполнения, а в выходном счетчике 2 установится код числа (чисел), следующего за максималь-! ными в порядке убывания из исходных чисел, записанных в начале сортировки во входные счетчики 1 -1>. Цикл анализа и сортировки повтоярется аналогично предыдущему.

При сортировке последнего числа (чисел) в последнем цикле по сигналу с вьг ода 36 блока 14 управления происходит установка в единичное состояние последних триггеров 4 -4 „ группы, так что на всех входах элемента ИЛИ-НЕ 8 - нулевой потенциал, поступающий на вход 33 блока управления, I182509

2 J -2

1 2 3

2о

0

О.

0

О

0

0

0

0

0

0

0

0

0

0

0 1

1 1

На выходе 17 элемента И 29 появляется сигнал об окончании. работы устройства, триггер 22 устанавливается в нулевое состояние, работа генератора тактовых импульсов блокируетВходы преобразователя 6

Г 1 ° t

0 0

0 1

1 0

0 1

1

0 0

0 1

1 0

О 1 ся. В выходных регистрах, -13>. в конце сортиронк- значения числа, записанные в начале сортировки во входные счетчики, поочередно записываются, начиная с максимального.

Выходы преобразователя 6

))82509 (5

2о

1 0. 0

0

Входы преобразователя 6

3 (2 ) 3 I 4

1 0

1 1

Э 1

)0 продолжение табл.

2, 2

1182509

1182509 йиФ аРиЩю22

1 цй АиЫ ееЮмщю27

2-й Юиюй

46%,РЮЩИМ7 мююп

ЕАОа714

1и йааФЛ ййМ Ю

2-йМюй32 йаитж

1-й Аиа1 птрисмра 2Ф

3-й и аУЯ

newn e

М АпУЛ

Юмлаж

Х-й АчИМ

Awй

Я-й 1ий О

Жюле

Ф йФИ77

Вявкою

3НИКПИ Заказ 6107/47 Тираж 709 ПФЮи иоа