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

 

Изобретение относится к автоматике и вычислительной технике и может найти применение в специализированных вычислительных машинах и устройствах обработки данных. Целью rr, ts, ,7. изобретения является расширение области применения устройства за счет возможности сортировки нулевых и равных чисел. Устройство содержит п регистров 1, п триггеров 2, группы элементов И 4, 10, 15, 16, дешифраторы 3 элементы ИЛИ 5, группы элементов 6, 9 запрета, шифратор 7, п схем 8 сравнения , регистр 12 результата, элемент Ш1И-НЕ 11, сумматор 13.Устройство сортирует массив чисел по возрастанию и вьщает его для занесения в ЭВМ, начиная с заданного адреса без потери нулевых и равных чисел. 1 табл., 1 ил. .W с (Л fUr tSn

СОЮЗ СОВЕТСНИХ

СОЦИАЛИСТИЧЕСНИХ

РЕСПУБЛИК

Ai (l9) (111 (51) 4 G 06 F 7/06

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

:Ь»

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

ПО.ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ

К А ВТОРСНОМУ СВИДЕТЕЛЬСТВУ (21) 4229297/24-24 (22) 13.04.87 (46) 15.12.88. Вюл. Р 46 (72) Г.А.Лукашева и И.А.Сычев (53) 681.325 (088 ° 8) (56) Авторское свидетельство СССР

11 1168927, кл. G 06 F 7/06, 1984.

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

Ф 12117 18, кл. G 06 F 7/06, 1984. (54) УСТРОЙСТВО ДЛЯ COPTHPOBKH ЧИСЕЛ . (57) Изобретение относится к автоматике и вычислительной технике и может найти применение в специализированных вычислительных машинах и устройствах обработки данных. Целью изобретения является расширение области применения устройства за счет возможности сортировки нулевых и равных чисел. Устройство содержит и регистров 1, и триггеров 2, группы элементов И 4, 10, 15, .16, дешифраторы

3 элементы ИЛИ 5, группы элементов 6, 9 запрета, шифратор 7, п схем 8 сравнения, регистр 12 результата, элемент ИЛИ-НЕ 11, сумматор 13.Устройство сортирует массив чисел по возрастанию и выдает его для занесения в 3ВМ, начиная с заданного адреса без потери нулевых и равных чисел.

1 табл., 1 ил.

14447 .Изобретение относится к автоматике и вычислительной технике и может найти применение в специализированных вычислительных машинах и устройствах обработки данных.

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

На чертеже изображено предлагаемое устройство.

Устройство содержит и регистров 1, и триггеров 2, и дешифраторов 3, и элементов И 4 первой группы, (m+1) элементов ИЛИ 5, ш элементов 6 запрета первой группы, шифратор 7, и схем 8 сравнения,(п-1) элементов 9 запрета второй группы, п элементов

И 10 второй группы, элемент ИЛИ-НЕ 20

11, регистр 1.2 результата, сумматор

13, элемент 14 задержки, группы выходных элементов И 15 и 16, входы 17 сортируемых чисел устройства, входа

18 сопровождения числа, входы 19 на- 25 чального адреса устройства, выход 20 конца сортировки, выходы 21 отсортированного числа, тактовый вход 22 и выхрд 23 адреса устройства.

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

Исходное состояние устройства характеризуется тем, что в регистры 1 по входам 17 принимается массив исходных чисел, а в сумматор 13 — код адреса памяти, начиная с которого необходимо разместить отсортированный массив. По входам 18, соответствующим входам 17, по которым поступили исходные числа, подаются сигналы, переводящие соответствующие триггеры 2 в единичное состояние, которое является признаком наличия числа в регистре 1., Исходные числа, в том числе и равные О, преобразуются дешифраторами 3, выходные сигналы с одноименных выходов 45 которых, кроме нулевого,.объединяются соответствующими элементами HJIH 5, сигналы с нулевых выходов дешифратора

3 выделяются элементами И 4 и на вход элемента ИЛИ 5 поступают сигналы толь-50 ко с тех элементов И 4, которые соответствуют регистрам 1, принявшим нулевые числа. Сигналы с триггеров 2 позволяют отличить исходное состояние регистров 1 от наличия в них нулевых чисел.

Пусть массив исходных чисел имеет следующий вид:

49 2

a,=3; à =0; а =1; а =4, а„=1; а =5.

При этих исходных данных работа дешифраторов 3 и элементов ИЛИ 5 поясняется таблицей.

Из таблицы видно, что номер выходов дешифраторов 3 и номер элемента

ИЛИ 5 однозначно соответствуют значению числа,. а выходные единичные сигналы элементов ИЛИ 5 размещены в

Порядке возрастания значения чисел.

При равных двоичных кодах в массиве чисел (а =а =001) единичный сигнал формируется соответствующим элементом ИЛИ 5 (ИЛИ 5,) .

Упорядоченный массив должен иметь вид:

Ь „=От Ь x=1; Ь =1; Ъ,= 3; Ь =4, Ь,=5э причем эти числа необходимо разместить в выделенной области памяти, код начального адреса А=Анач которой принят в сумматор 13.

Позиционный код 11011 выходных сигналов элементов ИЛИ 5 подается на элементы 6 запрета, включенные по приоритетной схеме. Единичный сигнал с выхода элемента ИЛИ 5 закрывает по инверсным входам все последующие элементы 6,-6 запрета. При этом на входе шифратора 7 формируется позиционный код 100000 и в регистр 12 результата принимается двоичный код 000. Помимо этого, в схеме

8 сравнения происходит совпадение кодов, единичный сигнал с выхода схемы

8 сравнения поступает на первый вход элемента И 10, минуя элементы 9 запрета. На выходе элемента ИЛИ-НЕ 11 отсутствует единичный сигнал, поэтому из ЭВМ по входу 22 поступает тактовый импульс. По этому импульсу адрес

А=Анач из сумматора 13 через группу

I элементов И 16 поступает на выходы

23, а двоичный код первого числа из регистра 12 результата через группу элементов И 15 выдается на выходы

21. Через некоторое время, определяемое задержкой в элементе 14 задержки, в сумматоре 13 формируется очередной адрес А =А „+1 и устанавливается в "0" регистр 1„ и триггер 2, чем исключается из рассмотрения число а . Время задержки выбирается исходя из необходимого вре- мени приема в ЭВМ адреса и значения. числа с выходов 21 и 23.

1444749

4 ответствовать последовательность равных чисел.

Двоичный код числ а,=011 а =000 а =001 а, =100 а =001 а =101

После установки в "0" регистра

1 и триггера 2 на выходах элементов. ИЛИ 5 формируется очередной позиционный код 010111, а на входе шифратора 7 — код 010000. При этом

5 в регистр 12 результата принимается двоичный код 001, а в схемах 8З и 8 сравнения формируется единичный сигнал.

Элемент 9 запрета пропускает сигнал с выхода схемы 8з сравнения на вход элемента И 10з, этот же сигнал закрывает по инверсным входам все последующие элементы 9>-9> запрета, тем самым не пропуская с выхода схемы 8> сравнения.

По очередному тактовому импульсу с входа 22 значение числа 001 и код адреса А поступают в ЭВМ, в ре- 20 зультате чего в устройстве регистр

1 и триггер 2 устанавливаются в

"0", а сумматоре 13 формируется очередной адрес А =А +1. При этом на выходах элементов ИЛИ 5 формируется 25 код 010111, а на входе шифратора 7— код 010000.

По очередному тактовому импульсу

; по,входу 22 значение числа 001 и код адреса Аз поступают в ЭВМ, в результате чего в регистр 1 и триггер 25 устанавливаются в состояние "0", при . этом в сумматоре 13 формируется адрес очередного числа А =А +1. По следующему тактовому импульсу происходит запись числа 011 по адресу А в результате чего, в устройстве регистр 18 и триггер 2 „ устанавливаются в "0".

По очередным тактовым импульсам 40 происходит последовательная запись чисел 100 и 101 по адресам А =А +1 и А =А +1 соответственно и регистры

1 и 1 и триггеры 2 < и 2 устанавлив ются в "0" ° При этом после уста- 45 ковки триггера 2 в "0" все триггеры оказываются в состоянии "0", в результате чего на выходе элемента

ИЛИ-НЕ 11 формируется единичный сиг- нал, поступающий в ЭВМ в качестве сигнала конца сортировки.

Таким образом, в результате работы устройства массив исходных чисел будет отсортирован по возрастанию и отсортированная последовательность будет занесена в память ЭВМ, 55 начиная с заданного начального адреса, причем, если в массиве есть рав-. ные числа, то на выходе нм будет соНомер выхода дешифраторов

3,...3„ (номер элемента

ИЛИ 5) (J Г11

0 1 2 3 4 5

0 0 0 1 0 0

1 0 0 0 0 0

0 1 0 0 0 0

0 0 0 0 1 0

0 1 0 0 0 0

0 0 0 0 0 1

Формула изобретения

Устройство для сортировки чисел, содержащее и регистров, где n — - число сортируемых чисел, и дешифраторов, и элементов И первой группы, m элементов ИЛИ, где ш = 2, (ш-1) элементов запрета, шифратор, и схем сравнения, регистр результата, сумматор, две группы выходных элементов И, элемент задержки, элемент HJIH-НЕ, причем входы сортируемых чисел устройства соединены с информационными . входами соответствующих регистров, выходы которых соединены с входами соответствующих регистров и входами первых групп соответствующих схем сравнения, i-й выход j-ro дешифратора,гдеi=1,2, °,ш,j=1, 2,...,n, соединен с j- ûì входом i-го элемента ИЛИ, i-e инверсные входы элементов запрета с i-ro по (m"1)-й объединены, выходы шифратора.соединены с входами вторых групп всех схем сравнения и информационными входами регистра результата, выходы разрядов которого подключены к пер. вым входам соответствующих выходных элементов И первой группы, выходы которых являются выходами отсортиро- ванного числа устройства, входы начального адреса устройства подключеСоставитель Е.Иванова

Редактор А.Ревин Техред M.Ходанич Корректор В.Бутяга

Заказ 6506/47 Тираж 704 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д, 4/5

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4

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

10 сумматора и первым входам. всех элементов И первой группы, второй вход первого элемента И первой группы соединен с выходом первой схемы сравнения выход элемента ИЛИ-НЕ явФ

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

ИЛИ (i=1,2,...,ø) соединен,с прямым входом i-ro элемента запрета первой группы и (i+1)-ым инверсным входом элементов запрета с (i+2) — ro no m-й первой группы, выходы элементов запрета первой группы подключены к соответствующим входам шифратора, выход первой схемы сравнения подключены к первым инверсным входам элементов запрета второй группы, выход

k-й схемы сравнения (k=2 Ç,...,n) соединен с прямым входом (k-1)-ro элемента запрета второй группы и с

k-ым инверсным входом элементов запрета второй группы с k-ro по (n-1)-й, выход (k-1)-ro элемента запрета второй группы подключен к второму входу

k-ro элемента И первой группы.