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

1-1444749

Изобретение относится к автомати

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

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

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

Устройство содержит п регистров 1, п триггеров 2, п дешифраторов 3, п элементов И 4 первой группы, (т+1) элементов ИЛИ 5, m элементов 6 запрета первой группы, шифратор 7, п схем 8 сравнения,(п-1) элементов 9 запрета второй группы, п элементов И 10 второй группы, элемент ИЛИ-НЕ 11, регистр 1.2 результата, сумматор 13, элемент 14 задержки, группы выходных элементов И 15 и 16, входы 1 7 сортируемых чисел устройства, входь 18 сопровождения числа, входы 19 начального адреса устройства, выход 20 конца сортировки, выходы 21 отсортированного числа, тактовьй вход 22 и ВЫ35РД 23 адреса устройства.

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

Исходное состояние устройства характеризуется тем, что в регистры 1 по входам 17 принимается массив исходных чисел, а в сумматор 13 - код адреса памяти, начиная с которого необходимо разместить отсортированный массив. По входам 18, соответствующим входам 17, по которым поступили исходные числа, подаются сигналы, переводящие соответствующие триггеры 2 в единичное состояние, которое является признаком наличия числа в регистре 1.

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

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

а,з;

5.

, ,- , ,

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

Из таблиць: видно, что номер выходов дешифраторов 3 и номер элемента ИЛИ 5 однозначно соответствуют значению числа, а выходные единичные сигналы элементов ИЛИ 5 размещены в Порядке возрастания значения чисел. При равных двоичных кодах в массиве чисел () единичный сигнал формируется соответствующим элементом ИЛИ 5 (ИЛИ 5ц).

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

Ь, Ь,1; , b,5,

причем эти числа необходимо разместить в выделенной области памяти, код начального адреса А Анач которой принят в cjT iMaTop 13.

0

0 5

5

5

Позиционный код 11011 выходных сигналов элементов ИЛИ 5 подается на элементы 6 запрета, включенные по приоритетной схеме. Единичный сигнал с выхода элемента ИЛИ 5о закрывает по инверсным входам все последующие элементы 6,-65- запрета. При этом на входе шифратора 7 формируется позиционныйкод 100000 и в регистр 12 результата принимается двоичный код 000. Помимо этого, в схеме 8 сравнения происходит совпадение кодов, единичный сигна л с выхода схемы 8 сравнения поступает на первый вход элемента И 10, минуя элементы 9 запрета. На выходе элемента ШШ-НЕ 1 1 отсутствует единичный сигнал, поэтому из ЭВМ по входу 22 поступает тактовый импульс. По этому импульсу адрес из сумматора 13 через группу элементов И 16 поступает на выходы 23, а двоичный код первого числа из регистра 12 результата через группу элементов И 15 выдается на выходы 21. Через некоторое время, определяемое задержкой в элементе 14 задержки, в сумматоре 13 формируется очередной адрес и устанав- 0 регистр 1

ливается в

и триггер 2 , чем исключается из рассмотрения число а. Время задержки выбирается исходя из необходимого вре- мени приема в ЭВМ адреса и значения числа с выходов 21 и 23.

ч

то в

После установки в О регистра и триггера 2 на выходах элемен- ИЛИ 5 формируется очередной позиционный код 010111, а на входе шифратора 7 - код 010000. При этом в регистр 12 результата принимается двоичный код 001, а в схемах 83 и 8 J сравнения формируется единичный сигнал.

Элемент 9 запрета пропускает сигнал с выхода схемы З сравнения на вход элемента И Юз этот же сигнал закрывает по 1нверсным входам все последующие элементы завыпрета, тем самым не

. 3 5

пропуская с

U44749

ответствовать ных чисел.

последовательность равДвоичный

код ЧИСЛс

Номер выхода дешифраторов 3 ,... 3 (номер элемен та ИЛИ 5)

.Ш}

15

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

хода схемы 85 сравнения.

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

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

а сумматоре 13 формируется очередной адрес . При этом на выходах элементов ИЛИ 5 формируется код 010111, а на входе шифратора 7 - код 010000.

По очередному тактовому импульсу i по.входу 22 значение числа 001 и код

А чего

адреса Aj поступают в ЭВМ, в результате чего в регистр ij и триггер /j устанавливаются в состояние О, при этом в сумматоре 13 формируется адрес очередного числа . По следующему тактовому импульсу происходит запись числа 011 по адресу А в результате чего , в .устройстве регистр 1g и триггер 2 устанавливаются в О.

ilo очередным тактовым импульсам происходит последовательная запись чисел 100 и 101 по и 1

адресам

соответственно и регистры и 1, и триггеры 2 и 2 устанавЧ Ч ливаются в

новки триггера 2 в О

О . При этом после уста- в О все триггеры

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

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

25

0

5

0

5

0

5

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

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

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

5

0

5

выми входами соот ветствующих элементов И второй группы, вторые входы которых соединены с выходами обнаружения нуля соответствующих дешифраторов, а выходы подключены к входам дополнительного элемента ИЛИ, выход которого соединен с допблни- тельным входом шифратора и первыми .инверсными входами элементов запрета, первой группь, выход i-ro элемента ИЛИ (,2,... ,т) соединен ,с прямым входом i-ro элемента запрета первой группы и (1+1)-ым инверсным входом элементов запрета с (i+2)-ro по т-й первой группы, выходы элементов запрета первой группы подключены к соответствующим входам шифратора, выход первой схемы сравнения подключены к первым инверсным входам элементов запрета второй группы, выход k-й схемы сравнения (,3,...,п) соединен с прямым входом (k-1)-ro элемента запрета второй группы и с k-ым инверсным входом элементов запрета второй группы с k-ro по (п-1)-й, вькод (k-1)-ro элемента запрета второй группы подключен к второму входу k-ro элемента И первой группы.