УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ИНФОРМАЦИИ Советский патент 1974 года по МПК G06F7/06 

1

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

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

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

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

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

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

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

AI - и;, п, о/, п-1, -, а,у, . -1 Ог, 1Для определеппости можно считать, что старший /г-ый разряд прпзнаков находится слева. Любой отрезок признака, содержащий / его младших разрядов (/ 1,2,..., п), называют/-ым остатко: 1 признака.

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

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

Если для всех строк Яг, « 0 или 1,

то, следовагелыю, данный шаг не сокращает множество нризнаков, среди которых могут оказаться максимальные, и на следующем шаге должны проверяться (п-1)-е разряды всех Л остатков, каждый из которых содержит (п-1) разрядов.

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

При /-ОМ щаге просматривается содержимое /-ГО столбца матрицы запоминающих элемен10В для выделепного на предыдущем шаге множества строк.

Если все Oi.j О или все ajj 1, то на следующем щаге проверяются все (/-1)-ые остатки того же множества.

Если же uij 1 только для некоторых строк, то выделяемое для следующего щага множество соответственно сокращается.

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

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

./Х

X (а,, V a.jZij «i,;V Z2.(h.jV . V 2;vjV/)

где Zi,j- «входной сигнал /-го столбца (шага), равный «1 для тех строк, которые входят в проверяемое на /-ом щаге множество, zi,i - «выходной сигнал /-го столбца (шага), равный «1 для тех строк, которые выделяются для проверки па (/+1)-ом щаге.

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

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

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

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

Каждая ячейка содержит инвертор 9, схемы «И 10 и 11, схемы «ИЛИ 12 и 13, триггер (или какой-либо другой запоминающий элемент) 14 со входными схемами «И 15 и 16. Входные схемы «И всех ячеек данной строки матрицы соединены с управляющей П1ИНОЙ 17 этой строки матрицы. Устройство работает следующим образом. Комбинационная часть каждой ячейки реализует функции:

х га,(2)

у - У,(3)

г :- га V Щ/ - z (а V у) :-:-- z() (4)

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

x,,,.a,.,

а па выходах 5 нижней (/V-ой) строки:

.,,... -. ,/ (5)

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

У1,1 -Ы; i.i-h,i V 22,;a2jV,.. .,V2;v.А ,/ (6)

Теперь подадим на все входы левого столбца ячеек 2,-,. Поскольку в каждом столббе, согласно (4),

z z()

а у определяется выражением (6), то па выходе 3 каждой ячейки получим функцию z, соответствующую выражению (1).

Таким образом, для выделения максимального признака необходимо: в нижней строке

матрицы соединить все выходы 5 со входами

6 соответствующих ячеек; на все входы 4

верхней строки подать константу на все

входы 2 левого столбца - константу «1.

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

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

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

способа заключается в том, что хранимая в запоминающем устройстве информация в процессе сортировки пе изменяется.

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

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

Лрн совмещении устройства для сортировки с запоминающим устройством хранения признаков каждая ячейка помимо функций (2), (3), (4) реализует также следующие функции: установка единицы

S qx(7)

установка «нуля

R qy(8)

где q - сигнал но управляющей щине 17.

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

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

X , , Xi I,

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

На входы 2 всех ячеек правого столбца матрицы подаются Zi, i 0.

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

Поскольку все 2 0, то х х, и слово X поступает на вторые входы схем «И 15 всех строк матрицы.

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

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

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

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

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

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

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

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

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

и в рассмотренном выше варианте с посторонним запоминающим устройством.

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

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

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

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

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

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

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

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

1 17 ,. ч I |7

3 2

/

/

1 I 7

J 2

Пб

5 б

41 |7iJlZ

/7

I

7Г15

2 TT

Риг.Ъ