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

1

(21)4822863/24 (22) 07.05.90

(46)23.12.92. Бюл. №47 (72) С.Н.Макареня, В.И Бенкевич, М.М.Татур и В.М.Булойчик

(56)Авторское свидетельство СССР № 1300459,кл. G 06 F7/08, 1985

Авторское свидетельство СССР Мг 1441384, кл, G 06 F 7/06,1986 (прототип). (54) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ЧИСЕЛ

(57)Изобретение относится к вычислительной технике, в частности к устройствам аппаратурной поддержки вычислительного процесса, и может быть использовано в специализированных вычислительных устройствах для аппаратурной реализации функции сортировки чисел. Целью изобретения является упрощение устройства. Устройство содержит кольцевые регистры сдвига 1, регистры сдвига результата 2, п триггеров 3. счетчик 4,группы элементов И 5, 6, 7, 12, элемент ИЛИ 8. элемент И 9. элементы задержки 10, 11. Устройство выполняет упорядочение чисел по возрастанию. 2 ил.

/J

(Л

С

vi со со ел

ГО

Фиг 1

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

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

Наиболее близким к предполагаемому по технической сущности и достигаемому результату является устройство для сортировки чисел (2), выбранное в качестве про- 20 тотипа.

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

Недостатком указанного устройства является большая сложность.

Целью изобретения является упроще- до ние устройства.

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

мента И первой группы , второй

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

0 5

0

5

о

5 п

е (.

5

рого соединен с первыми входами элементов И третьей группы и через второй элемент задержки с входами установки в единичное состояние триггеров. Выход 1-го триггера соединен с инверсным входом 1-го элемента И четвертой группы и вторым входом элемента И третьей группы, выход которого подключен к входу обнуления 1-го m-разрядного кольцевого регистра сдвига. Прямой вход первого элемента И четвертой группы соединен с третьим входом элемента И третьей группы и входом логической единицы устройства, выход j-ro элемента М

четвертой группы 0 1п-1) соединен с

прямым входом 0+1)-го элемента И четвертой группы и с третьим входом элемента И третьей группы. Выход старшего разряда j-ro регистра сдвига результата соединен с входом младшего разряда Q+1)-ro регистра сдвига результата, выходы регистров сдвига результата являются выходами сортируе- мых чисел устройства.

На фиг. 1 представлена структурная схема устройства; на фиг. 2 - диаграмма работы.

Устройство для сортировки п т-разрядных чисел содержит группу входных кольце- вых сдвиговых регистров 1. группу сдвиговых регистров результата 3, группу триггеров 3, счетчик 4, первую 5, вторую 6, третью 7 группы элементов И, элемент ИЛИ 8, элемент И 9, первый 10, второй 11 элементы задержки, четвертую группу элементов И 12.

Устройство имеет группу входов 13, синхровход 14, группу выходов 15,1-й вход устройства 13 (1 1, п) соединен с информационными входами {-го регистра 1, выход старшего разряда которого соединен с первым входом 1-го элемента И 5, выход которого соединен с i-м входом элемента ИЛИ. 8 и с инверсным входом 1-го элемента И 6, выход которого соединен с нулевым входом 1-го триггера 3, выход которого соединен со вторым входом 1-го элемента И 5, инверсным входом 1-го элемента И 7 и первым входом 1-го элемента И 12, выход которого соединен со входом обнуления 1-го регистра 1. Синхровход устройства 14 соединен со вторым, входом элемента И 9 и со входом элемента задержки 10, выход которого соединен с синхровходами регистров 1, 2 и с суммирующим входом счетчика 4, выход переполнения которого соединен с третьими входами элементов И 12 и со входом элемента задержки 11, выход которого соединен с единичными вхо- дами.триггеров 3. Выход J-ro элемента И 7 О Т, п-1) соединен с прямым входом Q+1)-ro элемента И 7 и со вторым входом (j+1)-ro

элемента И 12, на прямой вход первого элемента И 7 и на второй вход первого элемента И 12 подан потенциал логической единицы. Выход элемента ИЛИ 8 соединен со входом младшего разряда первого регистра 2 и с первым входом элемента И 9. выход которого соединен с прямыми входами элементов И 6. Выход старшего разряда j-ro регистра 2 соединен со входом младшего разряда 0+ 1) го регистра 2. Выходы разрядов j-ro регистра 2 соединены с 1-м выходом устройства 15.

Принцип работы устройства заключается в следующем. В регистры 1 параллельным кодом записываются исходные числа, на синхровход 14 подается последовательность из m.n импульсов, С приходом первых m импульсов (т - разрядность чисел) выделяется максимальное из п чисел и последовательным кодом записывается в первый регистр 2. Выделенное максимальное число исключается из дальнейшего рассмотрения (соответствующий регистр 1 обнуляется), С приходом следующих m импульсов выделяется максимальное из оставшихся (п-1) чисел, которое записывается в первый регистр 2, а его содержимое переписывается последовательным кодом во второй регистр 2 и т.д. Выделение максимального из п чисел заключается в последовательном анализе содержимого одноименных разрядов (начиная со старших) сравниваемых чисел.

Устройствр работает следующим образом В исходном состоянии в регистры 1 по входам 13 записаны исходные числа, счет- чик 4 обнулен, триггеры 3 - в единичном состоянии, элементы И 5 открыты, старшие разряды анализируемых чисел поступают на входы элемента ИЛИ 8. На вход 14 устройства поступает последовательность из m.n импульсов (фиг. 2, эпюра 1), С приходом первого импульса изменяется состояние триггеров 3 по следующему правилу: если старшие разряды всех чисел равны нулю, на выходе элемента ИЛИ 8 нуль, элемент И 9 закрыт, состояние триггеров 3 не изменяется. Если старшие разряды всех чисел равны единицы, на выходе элементы ИЛИ 8 - единица, элемент И 9 открыт, а все элементы И 6 закрыты, состояние триггеров 3 не изменяется.

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

открытые элементы И 6 обнуляет соответствующие триггеры 3.

При переходе 1-го триггера 3 в нулевое

состояние соответствующий ему элемент И

5 5 закрывается, и соответствующее число из

регистра 1 исключается из дальнейшего

рассмотрения.

Через время задержки гю, определяемое элементом 10, синхроимпульс поступа0 ет на синхровходы регистров 1, 2 (фиг. 2, эпюра 2). При этом осуществляется сдвиг информации в регистрах t, 2 на один разряд вправо. В младший разряд первого регистра 2 осуществляется запись информации с

5 выхода элемента ИЛИ 8. В кольцевом сдвиговом регистре 1 значение старшего разряда переписывается в младший разряд. Импульс с выхода элемента задержки 10, кроме того, увеличивает состояние счетчика

0 4 на единицу. Аналогично устройство работает и при поступлении следующих импульсов

С приходом гл-го по счету импульса осуществляется анализ последнего (младшего)

5 разряда исходных чисел и через время задержки по осуществляется сдвиг информации в регистрах. Таким образом, после поступления первых импульсов синхронизации ( моментТ0на фиг. 2, эп. 2) в первом

0 регистре 2 находится выделенное максимальное число, в регистрах 1 - исходные числа в их первоначальном представлении.

С приходом m импульсов на вход счет5 чика 4 на его-выходе переполнения появляется импульс, а счетчик обнуляется. Импульс с выхода переполнения счетчика 4 (см. фиг. 2, эп. 3) поступает на вход элементов И 12 и на вход элемента задержки 11

0 Группа элементов И 12 и на вход элемента задержки 11, Группа элементов И 7, И 12 представляют собой схему приоритета и предназначено для обнуления регистра 1, содержащего выделенное максимальное

5 число, на что указывает единичное состояние соответствующего триггера 3. Если в регистрах 1 содержится два и более одинаковых максимальных чисел, то несколько соответствующих триггеров 3 находится в

Q единичном состоянии. С приходом импульса переполнения с выхода счетчика 4 на входы элементов И 12. на выходе одного из элементов И 12 формируется импульс обнуления и при наличии двух и более одинакос вых максимальных чисел обнуляется соответствующий регистр 1 с минимальным порядковым номером. Таким образом, выделенное максимальное число исключается из дальнейшего анализа.

Через время задержки Гц, определяемое элементом 11 (см, фиг. 2, эп. 4) импульс переполнения устанавливает в единичное состояние триггеры 3 и с приходом (т+1)-го импульса синхронизации начинается выде- ление максимального из оставшихся (п-1) чисел,

По окончании работы в регистрах 2 записана упорядоченная последовательность чисел, причем в первом регистре 2 - мини- мальное из чисел, в n-ом регистре 2 - максимальное из чисел. Регистры 1 обнулены.

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

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

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