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

-СЖЪ "Й и и 424141 ОП ИИЗОБРЕТЕНИЯ Союз СоветскиХСоциалистическихРеспублик К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ) Приорит Гаоударотвенныи комитеСовета Министров СССРпо делан изооретенийи открытий убликовано 15.04.74 та опубликования о 53) УДК 681,322(0 ллетень Ле 1 исания 11,09.7) Автор изобретения Я 1) Заявитель нститут математики Сибирского отделения АН СССР УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ИНФОРМАЦИИ Для определенности старший гг-ый разряд слева, Любой отрезок у его младших разряда вают 1-ым остатком приАлгоритм выделения О знаков состоит г следу можно считать, что признаков находится признака, содержащий в (/ = 1,2п), назызнака.максимальных при- ощем Предложение относится к области автоматики и вычислительной техники и предназначено для логической обработки информации по признакам.Известны устройства для сортировки информации, работающие по принципу упорядоченной выборки с использованием свойств ассоциативной памяти. Для поиска и выделения очередного сортируемого признака необходимо выполнить большое число элементарных логических операций, что требует значительного времени и обуславливает сложность схем управления устройством.Предложенное устройство отличается тем, что входы схем И каждой ячейки соединены с первым логическим входом этой ячейки, выход первой схемы И соединен со входами схем ИЛИ. Вторые входы первой и второй схем ИЛИ соединены соответственно со вторым логичсским входом ячейки и выходом второй схемы И. Выход второй схемы ИЛИ соединен с первым логическим выходом ячейки, соединенным с первым логическим входом первой смежной ячейки матрицы. Выход второй схемы ИЛИ соединен со вторым логическим выходом ячейки, соединенным со вторым логическим входом второй смежной ячейки матрицы. Вход второй схемы И соединен через инвертор с третьим логическим входом ячейки, который соединен с третьим логическим выходом той же ячейки, соединенным с третьим логическим входом третьей смежной ячейки матрицы. Первые входы входных схем И триггера соеди иены с управляющей шиной соответствующейстроки матрицы, а вторые входы соединены соответственно со вторым логическим входом ячейки и выходом пнвертора. Выход триггера соединен с информационным входом ячейки, 10 соединенным со входом первой схемы И.Это позволяет упростить устройство и повысить его быстродействие.Сортировка осуществляется путем последовательного выделения максимальных призна ков, причем каждьш просмотр всех сортируемых признаков выполняется параллельно.Пусть в нскотором запоминающем устройстве, имеющем Л строк по и двоичных разрядов каждая, хранятся в произвольном порядке Х )г-разрядивк двоичных признаковА,: и а, а;,; а;, г.При псриом шаге просматривается содержимое левого (и-го) столбца матрицы запоминающих элементов (т. е. старшие разряды признаков),Если для Всех строк ап -- 0 или а 1,п -- 1, то, слсдовагсльпо, данныи шаг не сокращает множество признаков, среди которых могут окязятьс 51 мяксимальныс, и на слсдующсм шаге должны проверяться (и - 1) -е разряды ьсех Л" остатков, каждый из которых содержит (и - 1) разрядов.Если же для некоторых строк а; = О, а для других а;= 1, то первые дальше не рассматриваются, а последние составляют множество строк, просматриваемых на следующем шаге,При 1-ом шаге просматривается содержимое 1.го столбца матрицы запоминающих элемен 1 ов для выделенного на предыдущем шаге множества строк.Если все а,; = 0 или все а;, = 1, то на следующем шаге проверяются все (1 - 1)-ые остатки того же множества,Если же а = 1 только для некоторых строк, то выделяемое для следующего шага множество соответственно сокращается.Выделенное па последнем (и-м) шаге множество строк (в частном случае оно состоит из одной строки) содержит все (равные) максимальныс признаки.Для аппаратной реализации описанного алгоритма, которая составляет суть изобретения, достаточно построить комбинационную логическую сеть, реализующую для каждого разряда а; функциюгг,. Х где г - входной сигнал 1-го столбца (шага), равный 1 для тех строк, которые входят в проверяемое на 1-ом шаге множество, г; - выходной сигнал 1-го столбца (шага), равный 1 для тех строк, которые выделяются для проверки на (1+1)-ом шаге.На фиг, 1 изображена структурная схема предложенного устройства (без управляющих шин строк матрицы); на фиг, 2 - схема ячейки предложенного устройства; на фиг. 3 - схема ячейки для случая, когда предложенное устройство выполняется без совмещения с запоминающим устройством хранения признаков,Устройство выполнено в виде матрицы, состоящей из Л 1 и одинаковых ячеек 1.Еаждая яс 1 ейка имеет вход 2 переменной г, выход 3 переменной г, вход 4 переменной х, выход 5 переменной х, выход 6 переменной у, выход 7 переменной у, а также информационный вход 8.Входы 8 каждой ячейки соединены с соответствующими выходами запоминающего устройства хранения признаков.5 10 15 го 25 Зо 35 40 45 50 55 60 65 Кажда 51 ячейка содержит инвертор 9, схемы И 10 и 11, схемы ИЛИ 12 и 13, триггер (или какой-либо другой запоминающий элемент) 14 со входными схемами И 15 и 16.Входные схемы И всех ячеек данной строки матрицы соединены с управляющей п 1 иной 17 этой строки матрицы,Устройство работает следующим образом.комбинационная часть каждой ячейки реализует функции:х =:х/га, (2)у : у) (3)г . в : - ги / гу = г (а ,/ у) - г (а ,/ а у) (4)Подадим на все входы 4 верхней строки ячеек х = О, Тогда на выходах 5 верхней строки, согласно выражению (2), получим: х 1,;: га1а на выходах 5 нижней (У-ой) строки:х,.= - га,/г 2 а 2,/ /г/а, (5)Соединим во всех ячейках нижней строки выходы 5 со входами 6. Тогда, согласно выражению (3), на входах 6 всех ячеек каждого столбца получиму =: х = га, /г 2,а 2 /Гг,.а, (6)Теперь подадим на все входы левого столбца ячеек г;1=1, Поскольку в каждом столббс, согласно (4),г г(аНау) я у определяется выражением (б), то на выходе 3 каждой ячейки получим функцию г,соответствующую выражению (1),Таким образом, для выделения максимального признака необходимо: в нижней строкематрицы соединить все выходы 5 со входамиб соответствующих ячеек; на все входы 4верхней строки подать константу 0; на всевходы 2 левого столбца - константу. 1.После окончания переходных процессов сигнал 1 появляется на выходах 3 ячеек правого столбца в тех строках, где содержатсямаксимальные признаки.Для продолжения сортировки (выделенияследующего по порядку максимального признака) необходимо исключить из рассмотрения уже выделенные признаки, Это можносделать путем замены их в запоминающемустройстве минимальными возможными признаками 000.Другой способ исключения выделенныхпризнаков состоит в том, что на выделенныеранее строки в дальнейшем подается г;1= 0.Этот способ обеспечивает дальнейшее ускорение сортировки, Другое преимущество этогоспособа заключается в том, что хранимая взапоминающем устройстве информация в процессе сортировки не изменяется.Для выполнения сортировки путем последовательного выделения минимальных признаков достаточно на информационный вход(8) каждой ячейки вместо прямого сигнала соответствующего двоичного разряда подавать его инверсию, То;да на каждом шаге будут выделяться макс; мальные обратные коды признаков, что соответствует минимальным прямым кодам.,При совмещении устройства для сортировки с запоминающим устройством хранения признаков каждая ячейка помимо функций (2), (3), (4) реализует также следующие функции: установка единицы где д - сигнал по управляющей шине 17.Данный вариант устройства имеет три режима работы: запись, чтение и сортировка.При записи и-разрядное словоХ=хг хг, ь которое подлежит записи, подается на соответствующие входы 4 ячеек верхней строки матрицы.На входы 2 всех ячеек правого столбца матрицы подаются г;, г = О.С помощью переменной о указывается адрес записи, а именно: на шину 17 той строки, в которую необходимо записать слово Х, подается д; = 1.Поскольку все г = О, то х = х, и слово Х поступает на вторые входы схем И 15 всех строк матрицы.Так как в нижней строке матрицы выходы 5 соединены со входами 6, то на входах 6 ячеек всех строк также имеются значения соответствующих разрядов слова Х, а следовательно, на вторых входах схем И 16 всех строк - инверсии соответствующих разрядов слова Х.В результате при подаче в некоторую строку сигнала О = 1 происходит парафазная запись слова Х в запоминающие элементы этой строки.Если слово Х необходимо записать одновременно в несколько строк, то достаточно подать во все эти строки сигнал О = 1.Сброс информации в какой-либо строке (или в любом множестве строк, в том числе - общий сброс) производится путем записи слова Х = 000.При чтении считывание выделенного (максимального) признака выполняется следующим образом.На вход 2 ячейки левого столбца той строки, где выделен максимальный признак, подается сигнал я=1, а на входы 2 всех остальных строк-сигнал г = О, На входы 4 всех ячеек верхней строки подается сигнал х = О. Тогда,5 10 15 20 25 30 35 40 45 50 55 согласно (2) и (3), на выходах 5 ячеек ниж. ней строки матрицы (а при наличии соединений выходов 5 со входами 6 - также и на выходах 7 ячеек верхней строки) будет прочитано данное слово.Если в массиве имеется несколько одинаковых максимальных признаков, то для их раздельного считывания необходимо отметить все выделенные (т. е. содержащие максимальные признаки) строки, а затем прочитать их по очереди в произвольном установленном порядке (например, сверху вниз). Каждое считывание выполняется так, как описано выше.Сортировка выполняется точно так же, как и в рассмотренном выше варианте с посторонним запоминающим устройством.Предлагаемое устройство обладает полной однородностью (как в смысле однотипности ячеек, так и в смысле соединений между ячейками; все соединения выполнены по принципу близкодействия). Это сообщает предложенному устройству все известные положительные свойства однородных структур (вычислительных сред). Предмет изобретения Устройство для сортировки информации, содержащее матрицу ячеек, каждая из которых состоит из триггера со входными схемами И, инвертора, схем И и ИЛИ, отличающееся тем, что, с целью упрощения устройства и повышения его быстродействия, входы схем И каждой ячейки соединены с первым логическим входом этой ячейки, выход первой схемы И соединен со входами схем ИЛИ, вторые входы первой и второй схем 1 ЛЛИ соединены соответственно со вторым логическим входом ячейки и выходом второй схемы И, выход второй схемы ИЛИ соединен с первым логическим выходом ячейки, соединенным с первым логическим входом первой смежной ячейки матрицы, выход второй схемы ИЛИ соединен со вторым логическим выходом ячейки, соединенным со вторым логическим входом второй смежной ячейки матрицы, вход второй схемы И соединен через инвертор с третьим логическим входом ячейки, который соединен с третьим логическим выходом той же ячейки, соединенным с третьим логическим входом третьей смежной ячейки матрицы, первые входы входных схем И триггера соединены с управляющей шиной соответствующей строки матрицы, а вторые входы соединены соответственно со вторым логическим входом ячейки и выходом инвертора, выход триггера соединен с информационным входом ячейки, соединенным со входом первой схемы И.424141иг гг оставитель В. Игнатущенк ектор Н. Ау ехред Е. Борисо Подписи Типография, пр. Сапунова, 2 едактор Е. Семано Заказ 2311/10ЦНИИ Изд.1491Государственного комитпо делам изобретенМосква, Ж, Раушс Тираж 624а Совета Министров Си открытийая наб., д, 4/5