RU1783512C - Устройство дл сортировки чисел - Google Patents

Description

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 обнулены.

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

Claims (1)

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

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