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

«124

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

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

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

Устройство (фиг. 1) содержит, группы входных элементов И 1...4,группы элементов ИЛИ 5.,.8 переписи, группу элементов ИЛИ 9, входные регистры Ю.ЛЗ, первый регистр 14 сдвига, .: первую группу элементов И 15, группы элементов И 16.,.19 перезаписи, блок 20 управления, оперативные регистры 21vo.24, третий регистр 26 сдвига, элементы ИЛИ 27 перезаписи, блок 28 памяти, второй регистр 30 сдвига,, группы элементов 31 и 36 за держки.; группы элементов И 32 и 35, блок 33 определения номера оперативного регистра, первый, второй, третий и четвертый элементы ИЛИ 34, 29j 25 и 37, и элемент 38 задержки.

Блок 20 управления (фиг.2) содержит элементы ЗАПРЕТ 39, элементы ИЛИ 40, счетчик 41, дешифратор 42, элементы .43 задержки, одновибратор 44, генератор 45 тактовых импульсов, Т-триггер 46 и элементы И 47.

Блок 33 определения номера оперативного регистра (фиг.З ) содержит группу элементов ЗАПРЕТ 48, группу элементов И 49, элемент НЕ 50, группу триггеров 51, группу элементов . : ИЛИ 52, группу элементов И 53 и 55 и группу элементов ЗАПРЕТ 54.

Блок 28 памяти (фиг.4) содержит элемент { ШИ 56, элемент 57 задержки, группу триггеров 58, группы элементов ИЛИ 59 и 62, группы элементов И 60 и 63, и группу D-триггеров 61.

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

После подачи сигнала Пуск на одновибратор 44 он вырабатывает пря- моугольньй импульс длительностью t

2

44, который обнуляет счетчик 41 и поступает на элемент 43.1 задержки и на четвертьй выход блока 20 управления. Импульс с четвертого выхода

блока 20 управления обнуляет регистры 14, 26 и 30 сдвига и устанавливает в нулевое состояние триггеры 58.1-58.3 блока 28 памяти через эле-- менты 11ПИ 56 и 59.1-59.3 и в единичное состояние триггер 58.4, таким образом устанавливая блок 28 памяти в исходное состояние. По истечении времени задержки t .43.1 элемента 43.1 задержки импульс с его выхода

поступает на элемент 43.4 задержки и на второй вькод блока управления, про изводит запись 1 в цервые информационные разряды регистров 14, 26 и 30 сдвига через элементы ИЛИ 40.2,

25 и 29, одновременно открывая группы входных элементов И 1 . .%4 и поступая через группу элементов ИЛИ 9 на тактовые входы регистров 10.. .13, тем самым записывая входную информацию с ,

кодовой шины чисел устройства в виде кодов чисел G их адресами в эти ре- гистры .10...13, причем число занимает разряды 1-т, а. адрес - разряды (т+1)-р. По истечении t 43.4 импульс

с выхода элемента 43;4 задержки запускает генератор 45 тактовых импульсов. Прямоугольные импульсы на обоих выходах генератора 45 тактовых импульсов с периодом t43.1 2«t43.4 поступают на элементы И 47.1 и 47.2, а так как только на одном из выходов Т-триггера 46 уровень 1, импульсы проходят через один элемент И (47.1-либо 47.2) и через элемент ИЛИ 40 на четвертый выход блока 20 управления и элементы И 47.3 и ЗАПРЕТ 39.3.

С помощью регистра 14 сдвига, группы элементов И 15 и группы элементов И 16...19 исходный массив перезаписывается в оперативные регистры 21...24 с разбиением на массивы А и В„ причем массивы А и В записываются в регистр 21.,.24 управляющими сигналами соответственно регистров 26 и 30 сдвига, поступающими на тактовые входы регистров 21-. ..24 через группу управляющих элементов ИЛИ 27. При этом группы элементов И 16...19 перезаписи состоят из бистабильных элементов И, т. е. при отсутствии управляющего сигнала имеют большое выходное сопротивление.

Тактовые сигналы для регистров 2 и 30 сдвига вьфабатываются соответственно элементами И 47.4 и ЗАПРЕТ 39.4, так как значение первого разряда очередного числа поступает на второй вход блока 20 управления.

После четвертого такта блок 28 памяти запоминает номер оперативного регистра, в котором хранится последнее число массива А, и регистр 26 сдвига через группу элементов 31 задержки,а регистр 30 сдвига через блок 33, группу И элементов 35 и . группу элементов 36 задержки устанавливаются соответственно на начало и конец массива А. На пятом такте все числа записываются через группы элементов ИЛИ 5...8 в регистры 10.: 13 тактовым сигналом с группы управляющих элементов ИЛИ 9. Числа записываются со сдвигом на один разряд влево, и при перезаписи на второй вход блока 20 управления будет поступать значение второго разряда исходного числа. Адреса датчиков чисел записываются без изменений. Элемент ЗАПРЕТ 39.3 блока 20 управления предотвращает ложное срабатывание регистра 26 и 30 сдвига на пятом такте.

I

На второй серии тактовых импульсов

регистра 14 сдвига и группы элементов И 15 в регистры 21...24 перезаписываются сначала массив А (с разбиением на две части А1 и АО), а затем при окончании массива А массив В (с разбиением на В1 и ВО). После оп- ре деления опроса массива А, регистры 26 и 30, сдвига сбрасываются и устанавливаются соответственно на начало и конец массива В. Затем на пятом такте .второй серии тактовых импульсов полученные массивы А1, АО, В1 и ВО снова записываются в регистры ТО...13, причем блок 28 памяти теперь помнит номера регистров, в которых хранятся последние числа массивов А, А1 и В1. На третьей серии тактовых импульсов каждый из имеющихся ч етырех массивов аналогично разбивается еще на две части. После прохож- дения каждого из массивов А1, АО, В1 и ВО регистры 26 и 30 сдвига устанавливаются соответственно на начало и конец следующего .массива.

Конец очередного массива опреде- .ляется элементами И 32 и ИЛИ 34. Выдается сигнал на очередные сброс и

2412284

установку регистров 26 и 30 сдвига. При этом элемент 38 задержки через элемент ИЛИ 37 сбрасывает регистры 26 и 30 сдвига. Сигнал с элемента 5 ИЛИ 34 разрешает установку регистра 30 сдвига, и сигнал с блока 33 через группы элементов И 35 и элементов 36 задержки устанавливает его на ко- нец массив. Регистр 26 сдвига уста- fO навливается с помощью группы эле- ментов 31 задержки. Сигнал с элемента ИЛИ 34 также поступает на тре- ,тий вход блока 20 управления и далее на элемент И 47.3. Так как на выходе 15 элемента ИЛИ 40.1 в этот момент времени уровень , пришедший сигнал поступает на элемент 43.3. задержки. По истечении времени задержки t 43.3. прямоугольный импульс переводит Т- 20 триггер 46 в противоположное состояние, тем самым обеспечивая задержку прямоугольных импульсов с генератора 45 тактовых импульсов на время t 0,5 Т, необходимое для установки ре- - 25 гистров 26 и 30 сдвига. При этом времена задержки групп элементов 31 и 36 задержки и элемента 38 задержки С31 сЗб 2 t38 t43.3 Т

На (п+1)-м такте т-й серии такто- 2Q вых импульсов, что определяется счетчиком 41, единичный уровень на ш-м выходе дешифратора 42 запрещает запись 1 в регистре 14 сдвига че рез элемент ИЛИ 40.2 и останавливает генератор 45 тактовых импульсов по истечении времени задержки t43.2 элемента 43.2 задержки, причем с43.2 0,5 Т. Теперь во входных регистрах 10-13. расположены числа в убывающем порядке (или в. возрастающем при пос35

40

-ледовательном опросе регистров с 13 по 10).

Блок 28 памяти служит для запоминания номеров регистров, в которых хранятся последние числа получаемых массивов А, А1, В1 и т.д. Импульсы с регистра 26 сдвига поступают на RS- триггеры 58.1- 58.3, поочередно переводя их в едини 1тное состояние. Каждый

(k+1)-й триггер 58.k+1, переходя в единичное состояние, переводит k-й триггер 58.k в исходное нулевое состояние через элементы И 63.k и ИЛИ 59.k.(n+1)-й импульс первой серии тактовых импульсов, поступающий на пятый вход блока 28 памяти через элемент И 60.x устанавливает в единич ное состояние тот D-триггер 61.x,

где х может принят з одно из значений от 1 до k, на D-вход которого подана 1 с RS-триггера 58.x. О на инверсном выходе D-триггера 61.x предотвращает ложный сброс триггера 58.x при работе со следующим массивом на других тактовых сериях. Для предотвращения потери 1 на выходе блока 28 памяти группа элементов ИЛИ 62 объединяет выходы соответствующих RS- и D-триггеров. ,(п+1)-е импульсы всех серий переводят триггеры 58 в исходное состояние через элемент 57 задержки и элемент ИЛИ 56. Через элемент ИЛИ 56 также осуществляется первоначальная установка блока 28 памяти в исходное состояние. На п-м .выходе блока 28 памяти всегда 1 , т,е. информация о номере регистра, в котором хранится последнее число исходного -массива. Триггер 58.3 переводится в нулевое состояние импульсо с последнего () выхода регистра 26 сдвига,

Блок 33 определения номера опера тинного регистра служит для определения номера регистра, в котором хра . нится последнее число следующего массива. При этом, есл:и на j-м ин формадионном входе 1, она запрещает через элементы ЗАПРЕТ 54, И 55 и ИЛИ 52 прохождение остальных 1, на выходы блока 33 и разрешает прохождение 1 на j-й выход блока 33 через элементы И 53 и И 49. Если на J-M информадионном входе О, он через элементы ЗАПРЕТ 54, 11ПИ 52, И 55 разрешает прохождение на выход блока 33 только следующей х-й 1. Триггер 51 слуясит для запрещения появления 1 на J-M выходе блока-33 на остальных тактах данной серии тактовых импульсов. Таким образом, если на J-M информадионном входе 1, она будет на J-M выходе блока 33 до j-ro такта, причем на остальных (j-l)-x выходах будут О. На J-M, . такте на инверсном выходе триггера 51.J устанавливается О, который поступает на элемент И.49.j, запрещая прохождение j-й 1 на выход и разрешая прохождение на выход :х-й

определяемой кондом следующего

Ч

массив.а. Элемент ЗАПРЕТ 48.j пред- 55 отвращает ложное срабатывание блока 33 в момент переключения триггера. 51.jo Элемент НЕ 50 выполняет функQ.

Q

0

5

цию триггера, если в массиве одно число, занимающее первый регистр. На. п-м такте триггер 51 переводится i в кулевое состояние и блок 33 выдает 1 на выходе, соответствующую ном:еру последнего регистра старшего массива,

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

1. Устройство для упорядочивания чисел,, содержащее п групп входных эле ментов И, п входных регистров, п групп элементов И перезаписи, п групп элементов ИЛИ переписи, группу элементов ИЛИ, первую, вторую, третью группы элементов И, блок памяти, первую группу элементов задержки и блок управления, включающий генератор тактовых импзшьсов, триггер,;, счетчик, четыре элемента за.цержки, первый эле- . мев:т И, первый элемент И.ПИ, формирователь импульсов, причем вход за - пуска устройства-соединен с входом формирователя импульсов блока управ- ления,, в блоке управления первый выход генератора тактовькх импульеов соединен с первым входом первого элемента И, причем входы упорядочив, -- ния чисел соединены с информавд-;онны ми входами соответствующих групп входных элементов И, выходы разрядов входных регистров подключены к информационным входам элементов И пере- за.писи соответствующих групп, отличающееся тем, что, с целью повышения быстродействия, в него il... ввб:дены п оперативных регистров, элементы ИЛИ перезаписи, три регистра сдвига, четыре элемента ИЛИ., вторая группа элементов задержки, элемент задержки и блок определения номера оперативного регистра, в блок управления введенъ дешифратор, три элемента ЗАПРЕТ, второй элемент ИЛИ и второй, третий, четвертый элементы И, причем в блоке управления выходы счетчика соединены с входами дешифратора, ш-й выход которого соединен с запрещающим входом первого элемента ЗАПРЕТ и через первый элемент задержки с входом останова генератора тактовых импульсов, второй выход которого соединен с первьм входом -второго элемента И, выходы первого и второго элементов И соединены с входами первого элемента ИЛИ, второй вход первого элемента И сое

динен с прямьм выходом триггера, инверсный выход которого соединен с вторым входом второго элемента И, а счетный вход через второй элемент задержки - с выходом третьего элемента И, выход второго элемента ЗАПРЕТ соединен с информационными входами третьего элемента ЗАПРЕТ и четвертого элемента И, выход первого элемент ЗАПРЕТ соединен с первым входом второго элемента ИЛИ, выход третьего элемента задержки соединен с входом запуска генератора тактовых импульсо выход формирователя импульсов соединен с входом четвертого элемен та задержки, с входом установки в счетчика и.входами установки в ( первого регистра сдвига и блока па- мяти и первым входом первого элемента ИЛИ, выход которого соединен с входом установки в О второго и третьего регистров сдвига, i-й выход где i 1,..., п, третьего регистра сдвига соединен с первым входом (п+1- ,-i)-ro элемента ИЛИ перезаписи, выхо(Ь; i-го элемента ИЛИ перезаписи соединен с синхронизирующим входом i- го оперативного регистра,выход первого разряда ( -го оперативного регистра сое- динен с первым входом т-го элемента ИЛИ j-й группы элементов ИЛИ переписи, где j 1,...,ш; m - число разрядов числа массива, (j+1)-H-разрядный выход i-ro оперативного регистра соединен с первым входом j-ro эле- .мента ИЛИ i-й группы элементов ИЛИ переписи, 1-й разрядный выход .i-ro оперативного регистра,, где f m -(- : + 1),. ., ,р , p-m разрядность адреса шага массива, соединен с первым входом f-ro элемента ИЛИ i-й группы элементов ИЛИ перезаписи, выходы групп элементов ИЛИ переписи соединены с информационньми входами соответствующих входных регистров, выходы входных элементов И каждой i-й группы соединены с вторыми входами элементов ИЛИ переписи соответствующей

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

t5

20

, Q

25

35

0

5

0

5

выход которого соединен с sxoдo i первого разряда первого регистра сдвига, выходы которого соединены 5 с информационными входами элементов И первой группы, выход i-ro элемента И перрзой группы соединен с вторыми входами элементов И переза тиси соответствующей группы и с 1-м управ- 10 ляющим входом блока определен1;я номера оперативного регистра, с первым входом i-ro элемента И второй группы элементов И, выход i-ro элемента И второй группь соединен с входом i-ro элемента задержки первой группы и с i--M входом третьего элемента ИЛИ, выход которого соединен С входом элемента задержки и с управляющими входами элементов И третьей группыJа также с первым входом третьего элемента И блока управления второй вход третьего элемента И которого соединен с выходом первого элемента ИЛИ и с информационным входом второго элемента ЗАПРЕТ блокз управления, атакже соединен с тактовым входом первого регистра сдвига и с управляющими входами элементов И первой группы, выход (п+1)-го элемента И первой группы соединен с вторым входом каждого элемента ИЛИ группы, с (п+1)-м информационным входом блока памяти, с управляющим входом второго элемента ЗАПРЕТ, со счетным входом счетчика и с информа- ционным входом первого элемента ЗА- ПРЕТ блока управления, выходы третьего элемента ЗАПРЕТ и четвертого элемента И блока управления соединены с тактовыми входами соответ.ст- венно второго и третьего регистров сдвига, каждьй i-й выход блока определения номера оперативного регистра Соединен с информационным входом i-ro 3JieMeHTa И третьей группы, выход которого соединен с входом i-ro элемента задержки второй группы, выход k-ro элемента задержки второй группы, где k 1,. . . , п-1,.соединен с (n-f-l-k)-M информационным входом второго регистра сдвига, выход п-го элемент задержки второй группы соединен с вторым входом третьего элемента ИЛИ, выход которого соединен с первым информационным входом третьего регистра сдвига, выход каждого k-ro элемента задержки первой группы соединен с (k+1)-M информационным входом третьего регистра сдвига, выход i-ro элеменга задержки первой группы соединен с; вторым входом второго элемента ИЛИ, выход которого соединен с входом первого разряда второго регистра сдвига, i-й выход которого соединен с вторым входом i-ro элемента ИЛИ пе- 1эезапнси и с i-м информационным входом блока памяти, каждый i-й выход которого соединен.с вторым входом i.ro элемента И второй группы и с информационным входом блока определения номера оперативного регистра, выход элемента задержки соединен с вторым входом четвертого элемента Ш1И, выход i-po элемента ИЛИ группы соединен с тактовым входом соответствующего входного регистра, выходы элементов И перезаписи каждой i-й группы соединены с информационными входами 1-го оперативного регистра, выход первого элемента И перезаписи калсдой группы соединен с управляющими входами соответственно третьего элемента ЗАЛРЕТ и четвертого элемента И блока управления.

2. Устройство по п. 1 , о т л и ч а- ю ш, е е с я тем, что блок определения номера оперативного регистра содержит первую группу из п элемен- тов И, группу RS-триггеров, элемент НЕ, вторую и третью группы по п-2 элементов И, первуб группу из п элементов ЗАПРЕТ, группу элементов ИЛИ, вторую группу из п-2 элементов ЗАПРЕТ, причем 1-й информационный вход блока определения номера оперативног регистра соединен с информационным входом i-ro элемента ЗАПРЕТ первой группь, выход которого соединен с первым входом 1-го элемента И первой группы,- выход которого является i-м выходом блока определения номера оперативного регистра, k-й управляющий вход блока определения номера оперативного регистра соединен с .управляющим входом k-ro элемента ЗАПРЕТ -перв группы и входом установки в 1. k-ro RS-триггера группы, прямой выход которого соединен с первым входом k-ro элемента ИЛИ группы, выход f-ro эле- мента ИЛИ (1,2,..., п-2) соединен с информационным входом f-ro элемента ЗАПРЕТ второй группы и с первым входом F-ГО элемента И второй группы, выход которого соединен с вторым входом )-го элемента И первой группы, п-й упра.вляющий вход блока определения номера оперативного регис

.

с Ю t20 25

п й55

35

40

«5

тра соединен с управляющим входом п-гр элемента ЗАПРЕТ первой группы, и с входами установки в О всех триггеров группы, выхоя (n-l)-ro элемента ИЛИ группы соединен с вторым входом п-го элемента И первой группы, инверсный выход первого RS-триггера группы соединен с вторым входом первого элемента И первой группы, выход г-го элемента ЗАПРЕТ первой группы,. где г 2,... ,11-1, соединен с вторым входом (-г-1)-го элемента И второй группы и с управляющим входом (г-1)- го элемента ЗАПРЕТ второй группы, выходы которых соединены с первым входом элемента И третьей группы, выход которого соединен с вторым входом (r-l)-ro элемента ШШ группы, а второй вход подключен к инверсному выходу Г--ГО RS-триггера группы и к третьему входу г-го элемента И тре- ть.ей группы, выход первого элементаг ЗАПРЕТ первой группы через элемент НЕ подключен к второму входу первого элемента ИЛИ группы.

3. Устройство по П.1, о т л и ч а- ю щ е е с я тем, что,блок памяти содержит группу RS-триггеров, две группы элементов ИЛИ,- группу D-триг- геров, две группы элементов И, элемент задержки, элемент ИЛИ, причем k-й информационный вход блока памяти соединен с входом установки в 1 RS-триггера группы, прямой выход которого соединен с первым входом k-ro элемента И первой группы,син- хровходом k-ro D-триггера и первым входом k-ro элемента ИЛИ первой группы, выход которого является k-м информационным выходом блока памяти, вход установки в О блока памяти ;. подключен к первому входу элемента ИЛИ, первым входам элементов ИЛИ второй группы,, входу установки в 1 п-го RS-триггера группы, выход кото- рого является п-м выходом блока памяти, выход k-ro элемента ИЛИ второй ;группы подключен к входу установки в О k-ro RS -триггера группы (п + + 1 )-й вход блока памяти соединен с вторы ми входами элементов И первой группы и через элемент задержки соединен с вторым входом элемента ИЛИ, выход k-ro элемента И первой группы соединен с информационным входом k-го D - триггера группы, прямой выход которого подключен к второму входу элемента ИЛИ первой группы, а инвер-; сный выход соединен с первым входом ,соединен с вторым входом (k-l)-ro

k-ro элемента И второй группы, вы- элемента И второй группы, второй }зход

ход которого подключен к второму вхо-(r-l)-ro элемента И второй группы

ду k-ro элемента ИЛИ второй группы, 5является п-м информационным входом

прямой выход г-го RS-триггера группыблока памяти.

37

фиг.

Изобретение относится -к вьиис- лительной технике, в частности к устройствам для автоматической сортировки и упорядочивания чисел, и может быть использовано при реализации технических средств систем .автоматического контроля тенхологичес- ких процессов. Цель изобретения - повышение быстродействия устройства. Устройство содержит п групп входных элементов И,п входных регистров,п групп элементов перёзаписи,две группы элементов И, п групп элементов ИЛИ переписи, элементов ИЛИ, первую, вторую и третью группы элементов И, блок памя ти, группу элементов задержки и блок синхронизации, а также дополнительно п оперативных регистров, элементы ИЛИ перезаписи, три регистра сдвига, четыре элемента ИЛИ, группу элементов задержки, элемент задержки и блок определения номера оперативного регистра. Исходный массив чисел сначала разбивается на два массива - А и В, причем в массиве А находятся числа с 1 в первом разряде, в массиве В - с О. Затем каждьм из массивов А и В также разбивается на две части А1 и АО, В1 и ВО, причем в А1 и В1 помещаются числа с 1 во втором разряде, в АО и ВО - с О во втором разряде. Далее каждый из полученных массивов А1, АО, В1, ВО также разбивается на две части - в одной числа с 1 в тр.етьем разряде, в другой -с О. Такое разбиение осуществляется аналогично и по остальным (т-З)-м разрядам чисел, где га - количество разрядов в числе. В итоге получается массив упорядоченно расположенных чисел. 2 з.п. ф-лы, 4 ил. о S

о

-v

Ji

Яц

V7.«

Редактор А.Огар

ffiiji.. if

Составитель В.Смирнов

Техред Н.Бонкало Корректор -А.Зимокосов

Заказ 3489/43 Тираж 671 . . Подписное ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий . 113035, Москва, Ж-35, Раушская наб., д, 4/5

Производс.твенно-полиграфическое предприятие, г.Ужгород,ул.Проектная,4