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

 

Всесо ю

-С-ЖМ Й и и 424 I4I

ОП И

ИЗОБРЕТЕНИЯ

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

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

Республик

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (61) Зависимое от авт. свидетельства (22) Заявлено 07.12,71 (21) 1722078/18-24 с присоединением заявки ¹ (32) Приоритет

Опубликовано 15.04.74. Бюллетень ¹ 14

Дата опубликования описания 11.09.74 (51) М. Кл. G 06f 7/00

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

Сгветв Министров СССР па делан изааретений и аткрытий (53) УДК 681.322(088.8) (72) Автор изобретения

Я. И. Фет (71) Заявитель

Институт математики Сибирского отделения АН СССР (54) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ИНФОРМАЦИИ

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

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

Предложенное устройство отличается тем, что входы схем «И» каждой ячейки соединены с первым логическим входом этой ячейки, выход первой схемы «И» соединен со входами схем «ИЛИ». Вторые входы первой и второй схем «ИЛИ» соединены соответственно со вторым логичсским входом ячейки и выходом второй схемы «И». Выход второй схемы

«ИЛИ» соединен с первым логическим выходом ячейки, соединенным с первым логическим входом первой смежной ячейки матрицы.

Выход второй схемы «ИЛИ» соединен со вторым логическим выходом ячейки, соединенным со вторым логическим входом второй смежной ячейки матрицы. Вход второй схемы «И» соединен через инвертор с третьим логическим входом ячейки, который соединен с третьим логическим выходом той же ячейки, соединенным с третьим логическим входом третьей смежной ячейки матрицы. Первые входы входных схем «И» триггера соединены с управляющей шиной соответствующей строки матрицы, а вторые входы соединены соответственно со вторым логическим входом ячейки и выходом пнвсртора. Выход триггера соединен с информационным входом ячейки, 1р соединенным со входом первой схемы «И».

Это позволяет упростить устройство и повысить его быстродействие.

Сортировка осуществляется путем последовательного выделения максимальных признаков, причем каждьш просмотр всех сортируем ых признаков вьшолlIяется параллельно.

Пусть в некотором запоминающем устройстве, имеющем Л строк по л двоичных разрядов каждая, хранятся в произвольном поряд2р ке A n-разрядных двоичных признаков

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

/ его младших разрядов (j = 1,2, ..., n), называют J ûм остатком признака.

Алгоритм выделения максимальных приЗО знаков состоит г следующем.

424141

15

zl,J 1, f (При псриом шаге просматривается содержимое левого (n-ro) столбца матрицы запоминающих элементов (т. е. старшие разряды признаков).

Если для всех строк а, =0 или а,,„ = 1, то, слсдовагсльпо, данныи шаг не сокращает множсстBo признаков, среди которых могут оказаться максимальныс, и на следующем IIIB ге должны проверяться (n — 1) -е разряды ьсех Л" остатков, каждый из которых содержит (n — 1) разрядов.

Если же для некоторых строк а; = О, а для других а; „= 1, то первые дальше не рассматриваются, а последние составляют мно>кество строк, просматриваемых на следующем шаге.

При )-o» шаге просматривается содержимое

j-го столбца матрицы запоминающих элеменI ов для выделенного на предыдущем шаге множества строк.

Если все а,; = О или все а;, = 1, то на следующем шаге проверяются все (j — 1)-ые остатки того же множества, Если >ке а,, = 1 только для некоторых строк, то выделяемое для следующего шага множество соответственно сокращается.

Выделенное па последнем (n-м) шаге мно>кество строк (в частном случае оно состоит из одной строки) содержит все (равные) максимальныс признаки.

Для аппаратной реализации описанного алгоритма, которая составляет суть изобретения, достаточно построить комбинационную логическую сеть, реализующую для каждого разряда а;,; функцию

X (а,-,, V,,,zi,,,V,,/а,,,V,,V,,,,), (1) где zi — «входной» сигнал 1-го столбца (шага), равный «1» для тех строк, которые входят в проверяемое на /-ом шаге множество, г i, — «выходной» сигнал J ãî столбца (шага), равный «1» для тех строк, которые выделяются для проверки íà (j+ 1)-ом шаге.

На фиг. 1 изображена структурная схема предложенного устройства (без управляющих IHH строк матрицы); на фиг. 2 — схема ячейки предло>кенного устройства; на фиг. 3— схема ячейки для случая, когда предложенное устройство выполняется без совмещения с запоминающим устройством хранения признаков.

Устройство выполнено в виде матрицы, состоящей из Л п одинаковых ячеек 1.

1(а>кдая ячейка имеет вход 2 переменной z, выход 3 переменной z . вход 4 переменной х, выход 5 переменной х, выход 6 переменной у, выход 7 переменной у, а также информационный вход 8.

Входы 8 каждой ячейки соединены с соответствующими выходами запоминающего устройства хранения признаков.

1(а>кдая ячейка содержит инвертор 9, схемы

«И» 10 и 11, схемы «ИЛИ» 12 и 13, триггер (или какой-либо другой запоминающий элемент) 14 со входными схемами «И» 15 и 16.

Входные схемы «И» всех ячеек данной строки матрицы соединены с управляющей и иной 17 этой строки матрицы.

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

1(омбинационная часть каждой ячейки реализует функции: х =- х /га, (2) у =-у, (3)

z —: — za / zi/ = z (а,/ у) — z (а,/ а у) (4)

Подадим на все входы 4 верхней строки ячеек х,, = О. Тогда на выходах 5 верхней строки, согласно выражению (2), получим:

xi,;: z,,à, 1 а на выходах 5 нижней (У-ой) строки: х,= — г,.а, . /з а,,/,..., /з,, а (о)

Соединим во всех ячейках нижней строки выходы 5 со входами 6. Тогда, согласно выражению (3), на входах 6 всех ячеек каждого столбца получим у,, =-= х„,.= z,,à, Qz, à, 1/,...,,/з .а, (6)

Теперь подадим на все входы левого столбца ячеек zi >=1. Поскольку в каждом столббс, согласно (4), з = — (а Н а 1/) а у определяется выражением (б), то на выходе 3 каждой ячейки получим функцию z, соответствующую выражению (1).

Таким образом, для выделения максимального признака необходимо: в нижней строке матрицы соединить все выходы 5 со входами б соответствующих ячеек; на все входы 4 верхней строки подать константу «О»; на все входы 2 левого столбца — константу «1».

После окончания переходных процессов сигнал «1» появляется на выходах 3 ячеек правого столбца в тех строках, где содержатся максимальные признаки.

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

Другой способ исключения выделенных признаков состоит в том, что на выделенные ранее строки в дальнейшем подается z;,< — — О.

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

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

424141

S = qx (7) установка «нуля»

R=-qy (8) каждой ячейки вместо прямого сигнала соответствующего двоичного разряда подавать

его инверсию. То;да на каждом шаге будут выделяться макс..мальные обратные коды признаков, что соответствует минимальным прямым кодам. ,При совмещении устройства для сортировки с запоминающим устройством хранения признаков каждая ячейка помимо функций (2), (3), (4) реализует также следующие функции: установка единицы» где q — сигнал по управляющей шине 17.

Данный вариант устройства имеет три режима работы: запись, чтение и сортировка.

При записи и-разрядное слово

Х=х, ..., х, ь которое подлежит записи, подается на соответствующие входы 4 ячеек верхней строки матрицы.

На входы 2 всех ячеек правого столбца матрицы подаются z;, < — — О.

С помощью переменной q указывается адрес записи, а именно: на шину 17 той строки, в которую необходимо записать слово Х, подается q; = 1.

Поскольку все z = О, то х = х, и слово Х поступает на вторые входы схем «И» 15 всех строк матрицы.

Так как в нижней строке матрицы выходы 5 соединены со входами 6, то на входак 6 ячеек всех строк также имеются значения соответствующих разрядов слова Х, а следовательно, на вторых входах схем «И» 16 всех строк— инверсии соответствующих разрядов слова Х.

В результате при подаче в некоторую строку сигнала q = 1 происходит парафазная запись слова Х в запоминающие элементы этой строки.

Если слово Х необходимо записать одновременно в несколько строк, то достаточно подать во все эти строки сигнал q = 1.

Сброс информации в какой-либо строке (или в любом множестве строк, в том числе — общий сброс) производится путем записи слова Х = «00 ... О».

При чтении считывание выделенного (максимального) признака выполняется следующим образом.

На вход 2 ячейки левого столбца той строки, где выделен максимальный признак, подается сигнал z=1, а на входы 2 всех остальных строк-сигнал z = О. На входы 4 всех ячеек верхней строки подается сигнал х = О. Тогда, 5

55 согласно (2) и (3), на выходах 5 ячеек нижней строки матрицы (а при наличии соединений выходов 5 со входами 6 — также и на выходах 7 ячеек верхней строки) будет прочитано данное слово.

Если в массиве имеется несколько одинаковых максимальных признаков, то для Нх раздельного считывания необходимо отметить все выделенные (т. е. содержащие максимальные признаки) строки, а затем прочитать их по очереди в произвольном установленном порядке (например, сверку вниз). Каждое считывание выполняется так, как описано выше.

Сортировка выполняется точно так же, как и в рассмотренном выше варианте с посторонним запоминающим устройством.

Предлагаемое устройство обладает полной однородностью (как в смысле однотипности ячеек, так и в смысле соединений между ячейками; все соединения выполнены по принципу близкодействия). Это сообщает предложенному устройству все известные положительные свойства одпороднык структур (вычислительнык сред).

Предмет изобретения

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

424141

° ° °

° ° ° Риг 1

Фиг. 4

1РИг 2

Составитель В. Игнатущенко

Техред Е. Борисова Корректор H. Аук

Редактор Е. Семанова

Типография, пр. Сапунова, 2

Заказ 2311/10 Изд. № 1491 Тираж 624 Подписное

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

Москва, Ж-35, Раушская наб., д. 4/5