410453

410453 опиС"жнио ИЗОБРЕТЕНИЯ Союз Советских Сэциалистицеских РеспубликК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ ависимое от авт. свидетельстваМ Кл 6 11 с 7/00 б 11 с 15/ОХ,19721786697(18-24ением заявкиявлено 2 соед Государственный кокитеСовета Министров СССРоо делам нэооретенийи открытий орит 327 2(088 8) 05.,1974ования о юллетень М ания 14 Т.19 публико Дата оп Авторызобретения Л. М. Метрик и А, О ев аявит СТРОЙСТВО ДЛЯ УПОРЯДОЧЕННОЙ ВЪБОРК ИНФОРМАЦИИ2 Изобретение относится к запоминающим устройствам.Известно устройство для упорядоченной выборки информации, содержащее матрицу ассоциативных признаков, подключенную к регистру результата опроса, схему формирования признака опроса, подсоединенную к регистру опроса и регистру маски, схемы И, Оно реализует алгоритм упорядоченной выборки, в котором число обращений не зависит от разрядности ассоциативного признака и определяется только числом элементов массива. Это устройство имеет следующий недостаток; при удвоенной разрядности ассоциативного признака процесс формирования признаков опроса при повторных упорядоченных выборках без изменения массива полностью повторяется, и количество обращений к ассоциативному запоминающему устройству остается равным удвоенному количеству элементов массива. Это снижает быстродействие устройства.Целью изобретения является устранение указанного недостатка,Поставленная цель достигается тем, что в устройство упорядоченной выборки введен дополнительный регистр опроса, позволяющий при второй и последующих упорядоченных выборках массива исключить формирование признака опроса для каждого элемента упорядочиваемого массива и сократить вдвоечисло обращений к матрице ассоциативныхпризнаков. Входы дополнительного регистраопроса подключены через одни схемы И кБ выходам регистра результата опроса, а выходы через другие схемы И - ко входамматрицы ассоциативных признаков.На чертеже изображена блок-схема устройства,О Устройство содержит матрицу ассоциативных признаков 1, регистр маски 2, регистр опроса 3, дополнительный регистр опроса 4, схему формирования признака опроса 5,регистр результата опроса 6, схемы И 7 - 12,5 Входы дополнительного регистра опроса 4подключены через схемы И 9 к выходам регистра 6, а выходы через другие схемы И10 - ко входам матрицы ассоциативных признаков 1.О Устройство для упорядоченной выборки информации работает следующим образом. Упорядоченная выборка начинается с поискастроки матрицы ассоциативных признаков 1,которая содержит ассоциативный признак с5 минимальным значением, Схема формирования признака опроса 5 через схемы И 11заносит в регистр опроса 3 признак опроса,а через схемы И 12 заносит код маски врегистр маски 2. Признак опроса и маскаО определяются значением информации, посту40 45 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 10 15 20 25 30 35 кончена упорядоченная выборка массива, После этого в каждой строке матрицы ассоциативных признаков 1, кроме строки, соответствующей минимальному ассоциативному признаку массива, в рабочих разрядах будет записан ассоциативный признак этой строки, а во вспомогательных разрядах - ближайший меньший ассоциативный признак,При последующих упорядоченных выборках массива, ассоциативные признаки которого размещены в матрице ассоциативных признаков 1 указанным образом, поиск минимального ассоциативного признака осуществляется так же, как и при первой выборке с занесением содержимого рабочих разрядов регистра результата опроса 6 через схемы И 9 в дополнительный регистр опроса 4 (после того, как признак найден). Затем на входе матрицы ассоциативных признаков 1 рабочие разряды маскируются с помощью регистра маски 2 через схемы И 8, а на вспомогательные разряды из дополнительногорегистраопроса 4 через схемы И 10 подается признак опроса, что позволяет методом простого ассоциативного поиска найти строки матрицы ассоциативных признаков 1 с ближайшим большим, после минимального, значением ассоциативного признака. Далее содержимое разрядов регистра результата опроса 6 через схемы И 9 заносится в дополнительный регистр опроса 4, и процесс упорядоченной выборки с помощью простого ассоциативного поиска продолжается до тех пор, пока не будет найден последний элемент упорядочиваемого массива. Предмет изобретения Устройство для упорядоченной выборки информации, содержащее матрицу ассоциативных признаков, подключенную к регистру результата опроса, схему формирования признака опроса, подсоединенную к регистру опроса и регистру маски, схемы И, отлич а ю щ е е с я тем, что, с целью увеличения быстродействия устройства, оно содержит дополнительный регистр опроса, входы которого подключены через одни схемы И к выходам регистра результата опроса, а выходы через другие схемы И - ко входам матрицы ассоциативных признаков.Корректор 3, Тарасова Редактор Т. Орловская Типография, пр. Сапунова, 2 Заказ 1049/б Изд Мз 355 Тираж 591 ПодписноеЦНИИПИ Государственного комитета Совета Министров СССРпо делам изобретений и открытийМосква, Ж, Раушская наб., 4/5