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

 

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

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

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

РЕСПУБЛИК (su 4 б 06 Е 7 04

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

К ABTOPCHGMV СВИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3746126/24-24 (22) 28.05.84 (46) 15.06.88. Бюл. № 22 (72) В. А. Титов, A. А. Есетов, А. И. Гаврилов и Е. Г. Мельников (53) 681.325.66 (088.8) (56) Справочник по интегральным микросхемам/ Под ред. Б. В. Тарабрина. М.:

Энергия, 1980, с. 746.

Авторское свидетельство СССР № 1086425, кл. G 06 F 7/06, 1982.

Авторское свидетельство СССР № 997028, кл. G 06 F 7/04, 1981.

„„SU„„1403059 А1 (54) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ

МАССИВОВ ЧИСЕЛ (57) Изобретение предназначено для выделения из массива чисел, равных, больших или меньших заданного числа, путем последовательного сравнения двух разрядов кодов чисел массива с кодом заданного числа. Целью изобретения является расширение функциональных возможностей устройства. Устройство для сортировки массивов чисел содерж ит регистр контрольного кода, m регистров контролируемых кодов, mсхем анализа,,m схем сравнения и блок управления с соответствуюгцими связями между ними. 3 з.п. ф-лы, 4 ил.

1403059

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

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

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

Устройство содержит (фиг. ) ) регистр 1.! контрольного кода, регистры 1.2, ..., ).m+) контролируемых кодов, где m -- количест во кодов в массиве, схемы 2.1, ..., 2.п1

,анализа, схемы 3.1, ..., З.m сравнения и олок 4 управления. Запись кодов в, регистры 1.1, ..., 1.гп+1 осуществляется по кодовым шипам числа (КШЧ). Входами ,:устройства (блок" 4 управления) являются также входы для сигналов установки в

,нуль («Уст.0»), пускового сигнала («Пуск») и входы кода запроса. Выходами устройст ва являются выход «Окончание», на кото:ром появляется сигнал окончания работы устройства, а также выходы схем сравнения, единичный сигнал на выходе каждой из которых означает принадлежность данного кода к выбранной группе запроса.

Каждая схема 2.i анализа ()= — 1, ..., m) содержит элементы И 5 — 8, ИЛИ-НЕ 9 ,и 10, И вЂ” HE 11, И 2, триггер 13, элемент ИЛИ 14 и триггер 15. Триггеры 13 и 15, а также регистры 1.1, ..., 1.гп+1 устанавливаются предварительно в нуль сиг налом с выхода «Уст. О» блока управле,ния (фиг. 2).

Каждая схема З.i сравнения (i=), ..., m)

:содержит элемент ИЛИ-HF 16, элементы

ИЛИ 17, И 18, ИЛИ 19, И 20, ИЛИ HE

21, ИЛИ 22, И 23, ИЛИ 24, И 25 и 26. Выход элемента И 26 является i-м выходом устройства (фиг. 3) .

Блок 4 управления (фиг. 4) образуют генератор 27 тактовых импульсов, элемент

И 28, вычитающий счетчик 29, элемент НЕ

30, регистр 31 запроса, триггер 32 и элемент 33 задержки. Входами блока 4 управления являются вход 34, на который подается сигнал «Г!уск» устройства, вход двухразрядного кода запроса, по которому устанавливается регистр 31, а также вход «Уст. О», по которому устанавливается в единичное состояние триггер 32, и с его прямого выхода выдается единичный сигнал «Уст. О», после чего через элемент 33 задержки этим же сигналом триггер 32 сбрасывается в нуль. Выходом блока 4 управления также является шина

«Окончание»„единичный сигнал на которой свидетельствует об окончании работы устройства. тов И 6 и 8 равен единице, если соответствующие разряды кода i-го числа больше одноименных разрядов контрольного кода, и нулю в противном случае.

Если старший разряд j-ro кода больше

» старшего разряда контрольного кода, то на выходе второго элемента И 8 формируется сигнал единицы, и если второй по старшешинству разряд j-го кода равен одно5

)О

)5

ЗО

3 )

В исходном состоянии на регистре 1.! (фиг. 1) хранится код контрольного числа

X=(xi, ..., x„j, где х, — значение j-го (j= 1, ..., и) разряда кода контрольного числа. Числа A;=(a

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

На вход 34 поступает сигнал запуска, после чего сигналы с выхода генератора 27 тактовых импульсов через элемент И 28, на третий вход которого подается единичный сигнал с выхода элемента НЕ 30, могут поступать на входы регистров 1.1, ..., 1.m+1 для сдвига содержимого регистров на два разряда в сторону старц:их разрядов.

I1редварительно в устройстве пр исходит анализ первых двух старших разрядов. Для этого на схемах 2.i (i=1, ..., m) происходит одновременное суммирование flo гпос)2 двух старших одноименных разрядов кодов сравниваемых чисел Лг с двумя старшими разрядами контрольного числа Х на элементах И 5, 6 и ИЛИ-НЕ 9 и элементах И 7, 8 и ИЛИ HE 10, IlpH этом результаты сложения по гпос12 поступают на входы элемента И-HE 11 соответствующей схемы сравнения. Сигнал на выходе элемента И-НЕ 11 р" âåí нулю, если два старших разряда i-го числа равны соответствующим разрядам контрольного числа. и равен единице в противном случае. Если сигнал HB выходе элемента И-НЕ )1 равен нулю, то триггер 13 остается в исходном нулевом состоянии. Далее с выхода

t åHåðàòoðà 27 импульс сдвига через элемент И 28 поступает на входы регистров

1.1, ..., 1.m+ 1, после чего происходит сдвиг содержимого этих регистров на два разряда; процесс сравнения кодов повторяется. Сигнал с инверсного выхода триггера !3 поступает на входы элементов И 6 и 8 и на вход элемента И-НЕ 11, запрещая дальнейшее сравнение, если триггер 13 установится в единичное состояние.

На вторые входы элементов И 6 и 8 поступают прямые значения (n — ) -v и п-х разрядов j-x (j=1, ..., m) кодов и обратные значения (и — 1)-х и и-х разрядов контрольного кода. Сигнал на выходах элемен

1403059

35

55 именному разряду контрольного кода, то на выходе элемента ИЛИ-HE 10 формируется сигнал единицы, который поступает на вход элемента И 12. В результате на выходе элемента ИЛИ 14 формируется сигнал единицы, который устанавливает триггер !5 в единичное состояние. Если значение двух очередных разрядов j-r-o кода больше или меньше значений двух одноименных разрядов контрольного кода, то на выходе элемента И-НЕ ll устанавливается сигнал единицы, который устанавливает триггер 13 в единичное состояние. Процесс сравнения кодов повторяется до тех пор, пока содержимое регистров 1.1, ..., 1лп+1 не будет сдвинуто (g — 1) раз (этот код записывается перед работой устройства в счетчик 29, установочный вход не показан). Как только на вычитающем счетчике 29 появится нулевое состояние, о чем свидетельствует единичный сигнал этого состояния, который подается на вход элемента

НЕ 30, на выходе последнего появляется низкий сигнал, который поступает на третий вход элемента И 26 и запрещает дальнейшую подачу сигналов сдвига. Кроме того, единичный сигнал с выхода счетчика 29 подается на выходную шину

«Окончание» устройства. Код результата сравнения, снимаемый с прямых выходов триггеров 13 и 15, поступает на схемы

З.i сравнения. Для идентификации равных, меньших или больших кодов по отношению к кодам, хранящимся на регистрах ! .1, ..., l.гп+1, с выхода регистра 31 на схемы 31 сравнения поступает двухразрядный код запроса. Если код запроса равен коду на выходах триггеров 3 и 15, то на выходе элемента И 26 устанавливается сигнал логической единицы, в противном случае — нуль.

Значение кодов запроса следующее:

00 — контрольный код равен сравниваемому коду;

10 — контрольный код меньше сравниваемого кода;

11 — контрольный код больше сравниваемого кода.

Схема 3 сравнения работает следующим образом.

Пусть, например, на триггерах 13 и 15 хранятся коды единиц, а на регистре 31 находится код 11, тогда на выходе элемента ИЛИ-HE 16 появляется сигнал логического нуля, который поступает на входы элементов ИЛИ 17 и 19, на вторые входы которых поступают сигналы с прямого выхода триггера 13 и прямого выхода триггера (не показан) первого разряда регистра 31 запроса соответственно. Следовательно, на выходах элементов ИЛИ 17 и

19 устанавливаются сигналы логической единицы, которые поступают соответственно на входы элементов И 18 и 20 и элементов

23 и 25. На вторые входы элементов И 18 и 20 поступают сигналы логических единиц с выхода триггера 15 и выхода триггера второго разряда регистра 31 запроса соответственно. В результате на выходах элементов И 18 и 20 устанавливаются высокие потенциаль.*, которые поступают на входы элемента ИЛИ-HE 21 и элемента ИЛИ

22 с выхода элемента И 18, а на вход элемента ИЛ И 24 — с выхода элемента

И 20. Следовательно, на выходе элемента

ИЛИ-НЕ 2! появляется низкий потенциал, который поступает на первые входы элементов ИЛИ 22 и 24, на вторые входы которых поступают сигналы с выходов элементов И 8 и 20 соответственно.

В результате на выходах элементов ИЛИ

22 и 24 устанавливаются сигналы логической единицbl, которые поступают на первые входы элементов И 23 и 25. на вторые входы которых поступают высокие потенциалы с выходов элементов ИЛИ !7 и 19 соответственно. Далее на выходаi элементов И 23 и 25 появляются высокие потенциалы, которые поступают на входы элемента И 26, после чего на выходе схемы З.i сравнения появляется сигнал логической единицы, который поступает на выход устройства. Если код запроса не равен коду на выходах триггеров 13 и 5, то на выходе соответствующей схемы сравнения устанавливается сигнал логического нуля.

Сигналом окончания работы устройства является единичный сигнал с выхода счетчика 29, который возникает при нулевом состоянии счетчика 29 и подается на выходную шину «Окончание».

Пример. Пусть заданы контрольный код

11!01100 и сравниваемые коды 11101100, 11!11101, 11011110, которые заносятся на регистры 1.1, .... 1.4 соответственно. Триггеры 13 и 15 установлены в нулевое состояние. Для организации сравнения кодов необходимо выполнить три дополнительных сдвига кодов, поэтому код числа 3 устанавливается на счетчике 29.

В результате всех анализов триггеры 13 и 15 в соответствующих схемах 2.1, ..., 2.3 анализа установлены в следующие состояния: в схеме 2.1 — в состояние 00; в схеме 2.2 —— в состояние 11 и в схеме 2 3 — — в состояние 10. Далее эти сигналы поступают на входы соответствующих схем 3.1, ..., 3.3 сравнения. В зависимости от кода запроса на двухразрядном регистре 31 запроса возбуждаются соответствующие выходные шины устройства. Так, при коде 00 на регистре 31 воздуждается первая выходная шина (код, равный контрольному), при коде

10 — третья выходная шина (код, меньший контрольного), при коде 11 — вторая выходная шина (код, больший контрольного).

1403059

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

1. Устройство для сортировки массивов чисел, содержащее и-разрядный сдвиговый регистр контрольного кода, mn-разрядных сдвиговых регистров контролируемых кодов, m схем анализа, причем первые входы ре гистра контрольного кода и регистров контролируемых кодов соединены.с первым выходом «Установка B О» блока управления, вторые входы регистров соединены с кодовой шиной чисел, а третьи входы регист. ров соединены с вторым выходом «Сдвиг» блока управления, первые входы схем анализа соединены с первым выходом «Установка в «О» блока управления, второй вход схемы анализа соединен с инверсным выходом триггера (и 1) -го разряда г-го (1=1, ..., ITI) регистра KoIITpoëI",ðóåìoãо кода, третий вход схемы аггализа соединен с прямым выходом триггера (и+1) -го разряда регистра контролируемого кода, четвертый вход схемы анализа соединен с прямым выходом триггера (и-I)-го разряда

I-го регистра контрольного кода, п ятг>г и вход схемы анализа соединен с инверсным вьгходом триггера и-го разряда регистра контролируемого кода, шестои вход схемы анализа соединен с инвсрсг:ым Выходо vl триггера и-го разряда I-го регистра контролируемого кода, седьмой вход схемы а laлиза соединен с прямым выходом триггера и го разряда р I èoTpa контрольного кода, восьмой вход схемы анализа соединен с инверсным выходом триггера и-го разряда регистра контрольного кода, девятый вход схемы анализа соединен с прямым выходом триггера и-го разряда г-го регистра контролируемого кода, отличающееся тем. что„с целью расширения функциональных возможностей, в него введены m схем сравнения и блок управления, причем первый и второй входы схем сравнения соединены с третьим и четвертым выходами блока управления соответственно, третий и четвертый входы схем сравнения соединены с первым и вторым выходами схемы анализа соответственно, первый вход блока управления является входом установки устройства в исходное состояние, второй и третий входы блока управления являются входами поступления кода запроса, четвертый вход блока управления является входом «Пуск» устройства.

2. Устройство по п. 1, отличающееся тем, что схема анализа содержит пять элементов И, два двухвходовых элемента

ИЛИ-НЕ, элемент И-НЕ, трехвходовый элемент ИЛИ и два триггера, причем первый и второй входы первого элемента И соединены с вторым и третьим входами схемы анализа соответственно, первый и второй входы второго элемента И соединены с четвертым и пятым входами схемы анализа соответственно, а третий вход соединен с инверсным выходом первого триггера, третьим входом элемента И-НЕ и третьим входом четвертого элемента И, первый и второй входы третьего элемента И соединены с шестым и седьмым входами схемы анализа соответственно, первый и второй входы четвертого элемента И соединены с восьмым и девятым входами схемы анализа соответственно, выход первого элемента И соединен с первым входом первого элемента ИЛИ-НЕ, второй вход которого соединен с выходом второго элемента И и первым входом пятого элемента

И, первый вход второго элемента ИЛИ-НЕ соединен с выходом третьего элемента И, а второй вход соединен с выходом четвертого элемента И и третьим входом элемента ИЛИ, выход первого элемента ИЛИ-НЕ соединен с первым входом элемента И-НЕ, второй вход которого соединен с выходом второго элемента ИЛИ-НЕ и вторым входом пятого элемента И, выход элемента И-НЕ соединен с единичным входом первого триггера, нулевой вход которого соединен с первым входом схемы анализа и нулевым входом второго триггера, выход пятого элемента И соединен с первым входом элемента ИЛИ, второй вход которого соединен с прямым ВыхОдОм Bropol o триггера, выход элемента ИЛИ соединен с единичным входом второго триггера. прямые выходы первого и второго триггеров соответственно соединены с первым и вторым выходами схемы анализа.

30 3. Устройство llo п. 1, отличающееся тем, что схема сравнения содержит два двухвходовых элемента ИЛИ-НЕ, четыре двухвходовых элемента ИЛИ, пять двухвходовых элементов И, причем первый вход первого элемента ИЛИ-НЕ соединен с первым входом схемы сравнения, второй вход первого элемента ИЛИ-НЕ соединен с третьим входом схемы сравнения и вторым входом первого элемента ИЛИ, первый вход которого соединен с выходом первого элемента ИЛИ-НЕ и первым входом второго элемента ИЛИ, второй вход которого соединен с первым входом схемы сравнения, выход первого элемента ИЛИ соединен с вторым входом первого элемента И и вторым входом третьего элемента И, первый вход первого элемента И соединен с четвертым входом схемы сравнения, первый вход третьего элемента И соединен с выходом третьего элемен" à ИЛИ, первый вход второго элемента И соединен с выходом второго элемента ИЛИ и вторым входом

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

ИЛИ соединен с выходом второго элемен5> та ИЛИ-НЕ и первым входом третьего элемента ИЛИ, выход первого элемента И соединен с первым входом Второго элемента ИЛИ-НЕ и вторым входом третье1403059

ro элемента ИЛИ, выход второго элемента

И соединен с вторым входом второго элемента ИЛИ-НЕ и вторым входом четвертого элемента ИЛИ, выход третьего элемента И соединен с первым входом пятого элемента И, второй вход которого соединен с выходом четвертого элемента И, выход пятого элемента И является i-v выходом устройства.

4. Устройство по п. 1, отличающееся тем, что блок управления содержит генератор тактовых импульсов, трехвходовый элемент И, (log> n) -разрядный вычитающий счетчик, элемент НЕ, регистр кода запроса, триггер и элемент задержки, причем выход генератора тактовых импульсов соединен с первым входом элемента И, второй вход которого соединен с четвертым входом блока управления «Пуск», а третий вход соединен с выходом элемента НЕ, выход элемента И соединен с вторым выходом блока управления «Сдвиг» и входом вычитающего счетчика, выход которого соединен с входом элемента НЕ и пятым выходом блока управления «Окончание», первый и второй входы регистра запроса соединены с вторым и третьим входами блока. управления, а первый и второй BblxoJû соединены с третьим и четвертым выходами блока управления соответственно, единичный вход триггера соединен с первым входом блока управления «Установка в «О», а прямой выход триггера соединен с первым выходом «Установка в «О» блока Hp38ления н через элемент задержки с нулевым входом триггера. пыл

1403059 АЗ &.4

Составитель Н. Васильев

Редактор Л. Огар Текред И. Верее Корректор А. Тяско

3 а каз 2861, 40 Тираж 704 Подписное

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

113035, Москва, Ж--35, Раушская наб., д. 4, 5 (1роизводственн«-полиграфическо< предприятие, г. Ужгород, ул. Проектная, 4