Устройство для сортировки информации

Устройство для сортировки информации

Иллюстрации

Показать все

Реферат

 

()599728

ОПИСАНИЕ

ИЗОБРЕТЕН ИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

Союз Советских

Социалистических.

Республик

Воесоюзнатт

531 i l : - е " . н л т-.,,. ° ;:,e о ";.. а,Ф» с! !1 Л (61) Дополнительное к-авт. свид-ву— (22) Заявлено 02.04.76 (21) 2343121/18-24 с присоединением заявки №вЂ” (51) Ч Кл г б 06 Г 7/00

Государственный комитет

Совета Министров СССР ло делам изобретений и открытий (23) Приоритет— (43) Опубликовано 30.01.78. Бюллетень ¹ 4 (45) Дата опубликования описания 20.01.78 (53) УДК 681.327 (088.8) (72) Авторы изобретения (71) Заявитель

А. А. Метешкин и К. С. Барашев (54) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ИНФОРМАЦИИ

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

Известны устройства для сортировки информации. Одно из них содержит элементы памяти, схемы сравнения и мажоритарный элемент, причем сортировка осуществляется последовательным анализом одноименных разрядов сортируемых чисел. Это устройство обладает низким быстродействием (1). 10

Наиболее близким к изобретению является устройство для сортировки информации, содержащее ячейки, каждая из которых содержит триггер, единичный и нулевой входы которого соединены соответственно с выходами IS первого и второго входных элементов И; первый вход второго входного элемента И соединен с выходом элемента НЕ, вторые входы входных элементов И соединены с первым управляющим входом устройства, а выход 20 триггера подключен к первому входу первого выходного элемента И, с вторым входом которого соединен второй управляющий вход устройства (2).

Недостатком такого устройства также является низкое быстродействие, Целью изобретения является повышение быстродействия. Это достигается тем, что каждая ячейка дополнительно содержит (n — 1) триггеров (и — количество разрядов З0 в сортируемых числах), группу из 2(n — 1) входных элементов И, группу из (и — 1) выходных элементов И, дешифратор, имеющий и входов и m выходов, (m — 2) элементов I-IF., группу из т элементов И и m элементов

ИЛИ. В каждой ячейке выход k-ro триггера (k=1 —;n) соединен с k-ым входом дешифратора, первый вход /-ro элемента И группы (j=1 —;т) соединен с j-ым выходом дешифратора, второй выход /-го элемента И группы соединен с третьим управляющим входом устройства, остальные (j — 1) входов j-r o элемента И группы соединены соответственно с выходами первого, второго, (j — 1) -го элементов НЕ, выход /-го элемента И группы соединен с первым выходом j-го элемента ИЛИ, со входом (т j+1) m-го элемента ИЛИ, причем первый вход входного (2й — 1)-го элемента И группы соединен со входом k-го элемента НЕ, выходом k-ro выходного элемента И группы, с й-ым входом первой группы входов устройства и с k-ым выходом первой группы выходов устройства; входы остальных элементов НЕ каждой ячейки сое,динены соответственно с (и+ 1) †: (т — 11 входами первой группы входов устройства и выходами (и+ 1) —: (m — 1) первой группы выходов устройства; второй вход l-ro элемента ИЛИ (l=l —:т — 1) каждой ячейки соединен с выходом 1-го элемента ИЛИ предыду590728

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

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

Устройство содержит ячейку 1 с первой и второй группами входов, первой и второй группами выходов и группой выходов результата. Каждая ячейка содержит п-триггеров

2, группу из 2(п — 1) входных элементов И:3, группу из (и — 1) выходных элементов И 4, дешифратор 5 с п входами и т выходами, (т — 2) элементов НЕ б, группу из т, элементов И 7, т элементов ИЛИ 8, первый, второй и третий управляющие входы 9, 10 и 11 и выход результата 12.

Устройство может работать в режимах:

«Сортировка», «Запись», «Чтение». Для работы устройства в указанных режимах выходы второй группы соединены с одноименными входами первой группы.

В режиме «Сортировка» необходимо на третий управляющий вход 11 всех ячеек подать единичный потенциал, а на первый и второй управляющие входы 9 и 10 — нулевой потенциал. Если среди анализируемых признаков, хранящихся в ячейках 1, найдется хотя бы один признак с максимальным значением, равным 2", то на выходе первого элемента И 7 тех ячеек, где это имеет место, образуется единичный сигнал, который через т-ый элемент ИЛИ 8 поступает на выход результата 12 и через первый элемент ИЛИ

8 на первый выход второй труппы выходов.

Так как первый выход второй группы выходов соединен с первым входом первой группы входов, то единичный сигнал поступает на вход первого элемента НЕ б всех ячеек устройства. Выходной сигнал первого элемента

НЕ б поступает на вход второго и всех последующих элементов И 7 в качестве запрещающего сигнала. Единичный сигнал возникает только в тех ячейках, где анализируемые признаки имеют максимальные значения, равные 2".

Если среди анализируемых признаков не чайдется ни одного признака со значением равным 2", но найдется хотя бы один признак со значением равным 2" — 1, то на выходе второго элемента И 7 тех ячеек, где это имеет место, образуется единичный сигнал, который через т-ый элемент ИЛИ 8 поступает на выход результата 12 и через второй элемент ИЛИ 8 на второй выход второй группы выходов. Так как второй выход второй группы выходов соединен с вторым входом первой группы входов, то единичный игнал поступает на вход второго элемента

НЕ б всех ячеек устройства. Выходной сигнал второго элемента НЕ б поступает на вход третьего и всех последующих элементов И 7 в качестве запрещающего сигнала.

Единичный сигнал на выходе результата 12 возникает только в тех ячейках, где анализируемые признаки имеют максимальные значения, равные 2" — 1. Для выделения признака с очередным максимальным значением необходимо исключить выделенные ранее признаки. Это можно осуществить путем подачи нулевого потенциала на третий управляющий вход И тех ячеек, в которых хранятся ранее выделенные признаки.

Для сортировки путем выделения минимальных значений признаков необходимо на входы дешифратора 5 подать инверсные выходы соответствующих триггеров 2.

В режиме «Запись» на второй управляющий вход 10 и третий управляющий вход 11 подаетая,нулевой потенциал.

При записи п-разрядное слово подается на соответствующие входы первой группы входов. Адрес записи указывается подачей единичного потенциала на первый управляющий вход 9 той ячейки, в которую необходимо записать слово. При этом через группу входных элементов И 8 произойдет парафазная запись слова в запоминающие элементы 2 ячейки. Если требуется записать п-разрядное слово одновременно в несколько ячеек, то необходимо на первые управляющие входы

9 соответствующих ячеек подать единичный потенциал. Для стирания информации в какой-либо ячейке (или в множестве ячеек) необходимо произвести запись и-разрядного слова: А = «00... 0».

В режиме «Чтение» на первый управляющий вход 9 и третий управляющий .вход 11 всех ячеек необходимо подать нулевой потенциал. Считывание выделенного признака осуществляется путем подачи единичного потенциала на второй управляющий вход 10 соответствующей ячейки. При этом на второй управляющий вход 10 остальных ячеек подается нулевой потенциал. В этом случае на соответствующих выходах первой группы выходов будет считано п-разрядное слово.

Если в массиве имеется несколько признаков с одинаковыми значениями, то их считывание производится по очереди в произвольно установленном порядке.

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

Устройство для сортировки информации, содержащее ячейки, каждая из которых содержит триггер, единичный и нулевой входы которого соединены соответственно с выходами первого и второго входных элементов

И; первый вход второго входного элемента

И соединен с выходом элемента НЕ, вторые входы входных элементов И соединены с первым управляющим входом устройства, а выход триггера подключен к первому входу первого выходного элемента И, с вторым

590728

Втсрая zppn- Переспи гролоо бхоооВ new Умй ЬР——

1 входом которого соединен второй управляющий вход устройства, отлич ающееся тем, что, с целью повышения быстродействия устройства, каждая ячейка дополнительно содержит (n — 1) триггеров (п — количество разрядов в сортируемых числах), группу из 2 (п — 1) входных элементов И, группу из (n — 1) выходных элементов И, дешифратор, имеющий п входов и т выходов, (т — 2) элементов НЕ, группу из т элементов И и т элементов ИЛИ, причем в каждой ячейке выход k-го триггера (k=1-;n) соединен с

k-ым входом дешифратора, первый вход j-ro элемента И группы (j= l — . m) соединен с

j-ым выходом дешифратора, второй вход j-го элемента И группы соединен с третьим управляющим входом устройства, остальные (1 — 1) входов 1-го элемента И группы соединены соответственно с выходами первого, второго, (j — 1) элементов НЕ, выход /-го элемента И группы соединен с первым выходом

/-го элемента ИЛИ, со входом (т — /+1) m-го элемента ИЛИ, причем,первый вход входного (2k — 1) элемента И группы соединен со входом k-го элемента НЕ, выходом k-ro выходного элемента И группы, с k-тым входом первой группы входов устройства, с Й-тым выходом первой группы выходов устройства, входы остальных элементов НЕ каждой ячей5 ки соединены соответственно с (и+1) —; (m — 1) входами первой группы входов устройства и выходами (и+1) —: (т — 1) первой группы выходов устройства, второй вход l-го элемента ИЛИ (l=l —;т — 1) каждой ячейки соеди10 нен с выходом 1-го элемента ИЛИ предыдущей ячейки, второй вход l-ro элемента ИЛИ соединен с 1-тым входом второй группы входов устройства, выход 1-ro элемента ИЛИ соединен с 1-тым выходом второй группы вы15 ходов устройства, выход т-ro элемента ИЛИ каждой ячейки соединен с соответствующим выходом группы выходов результата устройства.

20 Источники информации, принятые во внимание при экспертизе:

1. Авторское свидетельство СССР № 463968, кл. G 06 F 7/08, 1973.

2. Авторское свидетельство СССР

25 № 424141, кл. G 06 F 7/00, 1972.