Патент ссср 410453

 

4l0453 оп и Си н ио

ИЗОБРЕТЕНИЯ

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

С эциалистинеских

Республик

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

Зависимое от авт. свидетельства №

Заявлено 22Х.1972 (№ 1786697/18-24) с присоединением заявки №

Приоритет

Опубликовано 05.1.1974. Бюллетень № 1

Дата опубликования описания 14Х.1974

М. Кл. G llc 7/00

G llс 15/00

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

Совета Министров СССР оо делам нэооретений и открытий

УДК 681.327.2 (088.8) Авторы изобретения

Л. М. Метрик и А. Ю. Гурьев

Заявитель

УСТРОЙСТВО ДЛЯ УПОРЯДОЧЕННОЙ ВЪ|БОРКИ

ИНФОРМАЦИИ

Изобретение относится к запоминающим устройствам.

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

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

Целью изобретения является устранение указанного недостатка.

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

На чертеже изображена блок-схема устройства.

1О Устройство содержит матрицу ассоциаTHBHbIx признаков l, регистр маски 2, регистр опроса 3, дополнительный регистр опроса 4, схему формирования признака опроса 5, регистр результата опроса 6, схемы «И»7 — 12.

15 Входы дополнительного регистра опроса 4 подключены через схемы «И» 9 к выходам регистра 6, а выходы через другие схемы «И»

10 — ко входам матрицы ассоциативных признаков 1.

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

25 минимальным значением. Схема формирования признака опроса 5 через схемы «И» ll заносит в регистр опроса 3 признак опроса, а через схемы «И» 12 заносит код маски в регистр маски 2. Признак опроса и маска

ЗО определяются значением информации, посту410453

50 пающей на входы схемы формирования признака опроса 5 из регистра маски 2, регистра опроса 3 и регистра результата опроса 6.

Признак опроса из регистра опроса 3 через регистр маски 2 и схемы «И» 7 подается на вход матрицы ассоциативных признаков 1.

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

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

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

После того, как в регистре результата опроса

6 будет зафиксировано отсутствие признаков смешанных столбцов, содержимое дополнительного регистра опроса 4 через схемы «И»

10 заносится во вспомогательные разряды той строки матрицы ассоциативных признаков, которая соответствует найденному ассоциативному признаку, а содержимое вспомогательных разрядов регистра результата опроса 6 заносится через схемы «И» 9 в дополнительный регистр опроса 4. Процесс поиска увеличивающихся ассоциативных признаков и перезаписи информации в соответствующих строках матрицы ассоциативных признаков 1 продолжается до тех пор, пока не будет за5

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

При последующих упорядоченных выборках массива, ассоциативные признаки которого размещены в матрице ассоциативных признаков 1 указанным образом, поиск минимального ассоциативного признака осуществляется так же, как и при первой выборке с занесением содержимого рабочих разрядов регистра результата опроса 6 через схемы «И» 9 в дополнительный регистр опроса 4 (после того, как признак найден). Затем на входе матрицы ассоциативных признаков 1 рабочие разряды маскируются с помощью регистра маски 2 через схемы «И» 8, а на вспомогательные разряды из дополнительногорегистраопроса 4 через схемы «И» 10 подается признак опроса, что позволяет методом простого ассоциативного поиска найти строки матрицы ассоциативных признаков 1 с ближайшим большим, после минимального, значением ассоциативного признака. Далее содержимое разрядов регистра результата опроса 6 через схемы

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

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

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

410453

Составитель В. Рудаков

Техред Е. Борисова

Корректор 3. Тарасова

Редактор Т. Орловская

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

Заказ 1049/б Изд л1 . 355 Тираж 591 Подписное

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

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