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

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

Иллюстрации

Показать все

Реферат

 

УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ДВОИЧНЫХ ЧИСЕЛ, содержащее генератор тактовых импульсов, счетчики, две группы триггеров, группу элементов И, элемент ИЛИ и элемент Ш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 ПФЮи иоа