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

N

о

со о

сл

со

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

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

На фиг. 1 представлена структурная схема устройства для сортировки .массивов чисел; на фиг. 2 - структурная :схема блока анализа; на фиг. 3 - структурная схема блока сравнения; на фиг. 4 - структурная схе.ма блока управления. ; УстройстЕК) содержит (фиг. 1) регистр 1.1 контрольного кода, регистры 1.2, ..., 1.гп + 1 |контролируемых кодов, где m - количест- 1во кодов в массиве, схемы 2.1, ..., 2.т анализа, схемы 3.1, ..., З.т сравнения и блок 4 управления. Запись кодов в |регистры 1.1, ..., l.m + 1 осуществляется по |кодовым Ц1инам числа (КШЧ). Входами устройства (блоке 4 управления) являются гакже входы для сигналов установки в |нуль («Уст.О), пускового сигнала («Пуск) |и входы кода запроса. Выходами устройст- |ва являются выход «Окончание, на кото- ipOM появляется сигнал окончания работы устройства, а также выходы схем срав- ;нения, единичный сигнал на 1}ыходе каждой из которых означает принадлежность данного кода к выбранной группе запро- ;са.

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

I Каждая схема 3.1 сравнения (, ..., т) 1сод,ержит элемент ИЛИ-НЕ 16. элементы ИЛИ 17, И 18, ИЛИ 19, И 20, ИЛИ-НЕ 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 управления также является шина «Окончание, единичный сигнал на которой свидетельствует об окончании работы устройства.

В исходном состоянии на регистре 1.1 (фиг. 1) хранится код контрольного числа , ..., х„), где X, - значение j-ro (, ..,, п) разряда кода контрольного

числа. Числа , ..., airi}, где а,-/ - значение j-ro разряда i-ro числа, предварительно заносятся на регистры 1.2, ..., l.m-|-l для последующего сравнения с числом X. Триггеры 13 и 15 схем 2.1, ..., 2т анализа установлены в нуль. На счетчике 29

находится код числа сдвигов, необходимых для сравнения кодов (установочный вход счетчика 29 на фиг. 4 не показан).

Устройство работает следующим образом. На вход 34 поступает сигнал запуска,

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

0 разряда в сторону старших разрядов. Предварительно в устройстве присходит ана.лиз первых двух старших разрядов. Для этого на схемах 2.1 (, ..., т) происходит одновременное суммирование по mod2

5 ДВУ одноименных разрядов кодов сравнивае.мых чисел А/ с двумя старшими разрядами контрольного числа X на элементах И 5, 6 и ИЛИ-НЕ 9 и эле.мен- тах И 7, 8 и ИЛИ-НЕ 10, при этом результаты сложения по mod2 поступают

Q на входы элемента И-НЕ 11 соответствующей схемы сравнения. Сигнал на выходе элемента И-НЕ 11 равен нулю, если два старших разряда i-ro числа равны соответствующим разрядам контрольного числа, и равен- единице в противном случае. Ес5 ли сигнал на выходе элемента И-НЕ 11. равен нулю, то триггер 13 остается в исходном нулевом состоянии. Далее с выхода 1 енератора 27 импульс сдвига через элемент И 28 поступает на входы регистров 1.1, ..., l.m-|-l, после чего происходит сдвиг содержимого этих регистров на два разряда; процесс сравнения кодов повторяется. Сигнал с инверсногс выхода триггера 13 поступает на входы элементов И 6 и 8 и на вход элемента И-НЕ И, запрещая даль5 нейшее сравнение, если триггер 13 установится в единичное состояние.

На вторые входы элементов И б и 8 поступают прямые значения (п-1)-х и п-х разрядов J-X (, ..., m) кодов и обратные значения (п-1)-х и п-х разрядов конт0 рольного кода. Сигнал на выходах элементов И 6 и 8 равен единице, если соответствующие разряды кода 1-го числа больше одноименных разрядов контрольного кода, и нулю в противном случае.

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

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

именному разряду контрольного кода, то на выходе элемента ИЛИ-НЕ 10 формируется сигнал единицы, который поступает на вход элемента И 12. В результате на выходе элемента ИЛИ 14 формируется сигнал единицы, который устанавливает триггер 15 в единичное состояние. Если значение двух очередных разрядов j-ro кода бoльuJe или меньше значений двух одноименных разрядов контрольного кода, то на выходе элемента И-НЕ 11 устанавливается сигнал единицы, который устанавливает триггер 13 в единичное состояние. Процесс сравнения кодов повторяется до тех пор, пока содержимое регистров 1.1, ..., l.m+1 не будет сдвинуто ( - 1) раз (этот код записывается перед работой устройства в счетчик 29, установочный вход не показан). Как Только на вычитающе.м счетчике 29 появится нулевое состояние, о чем свидетельствует единичный сигнал этого состояния, который подается на вход элемента НЕ 30, на выходе последнего появляется низкий сигнал, который поступает на третий вход элеме11та И 26 и запрещает дальнейшую подачу сигналов сдвига. Кроме того, единичный сигнал с выхода счетчика 29 подается на выходную шину «Окончание устройства. Код результата сравнения, снимаемый с прямых выходов триггеров 13 и 15, поступает на схемы 3.i сравнения. Для идентификации равных, меньших или больших кодов по отношению к кодам, хранящимся на регистрах 1.1, ..., l.m+1, с выхода регистра 31 на схемы 3.i сравнения поступает двухразрядный код запроса. Если код запроса равен коду на выходах триггеров 13 и 15, то на выходе элемента И 26 устанавливается сигнал логической единицы, в противном случае - нуль. Значение кодов запроса следующее:

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

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

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

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

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

0

5

0

5

0

5

0

5

0

5

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

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

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

Пример. Пусть заданы контрольный код 11101100 и сравниваемые коды 11101100, 11111101, 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 - третья выходная Н1ина (код, меньший контрольного), при коде 11 - вторая выходная шина (код, больший контрольного).

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

1.Устройство для сортировки массивов чисел, содержащее п-разрядный сдвиговый регистр контрольного кода, пш-разрядных сдвиговых регистров контролируемых кодов, m схем анализа, причем первые входы регистра контрольного кода и регистров коптролируемых кодов соединены.с первым выходом «Установка в О блока угфавления, вторые входы регистров соединень) с кодовой П1ИНОЙ чисел, а третьи входы регистров соединены с вторым выходом «Сдви блока управления, первые входы схем ана- ;1иза соединены с первым выходом «Установка в «О блока управления, второй вход схемы анализа соединен с инверсным выходом триггера (п -1)-го разряда i-ro (, ..., гп) регистра контролируемого кода, третий вход схемы анализа соединен с прямым выходом тригге|:)а {п-|-1)-го разряда регистра контролируемого кода, четвертый вход схемы анализа соединен с прямым выходом триггера (п-1)-го разряда i-ro регистра контрольного кода, пятый вход схемы анализа соединен с инверсным выходом триггера п-го разряда регистра контролируемого кода, Н1естой вход схемы ана;1иза соединен с инверс11ым выходом триггера п-го разряда i-ro регистра контролируемого кода, седьмой вход схемы анализа соединен с прямым выходом триггера п-го разряда регистра контрольного Kozia, восьмой вход схемы ана;и1за соединен с инверсным выходом триггера п-го разряда регистра контрольного кода, девятый вход схемы ана.1иза соединен с прямым выходом триггера п-го разряда 1-го ре1 истра контро- .лируемого кода, отличающееся тем, что, с ие;1ью расн1ирения функциональных возможностей, в него введены m схем сравнения и блок управления, причем первый и второй входы схем сравнения соединены с третьим и четвертым выходами блока управления соответственно, третий и четвертый входы схем сравнения соединены с первым п вторым выходами схемы анализа соответственно, первый вход блока управления является входом установки устройства в исходное состояние, второй и третий входы блока управления являются входами поступления кода запроса, четвертый вход блока управления является входом «Пуск устройства.

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

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

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

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

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

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

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

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

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

блока управления «Пуск, а третий вход соединен с выходом элемента НЕ, выход элемента И соединен с вторым выходом блока управления «Сдвиг и входом вычитающего счетчика, выход которого соединен с входом элемента НЕ и пятым выходом блока управления «Окончание, первый и второй входы регистра запроса соединены с вторым и третьим входами блока-управления, а первый и второй выходы соединены с третьим и четвертым выходами блока управления соответственно, единичный вход триггера соединен с первым входом блока управления «Установка в «О, а прямой выход триггера соединен с пер- г вым выходом «Установка в «О блока управления и через элемент задержки с нулевым входом триггера.

0

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

,

Ф Ф

срагА