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

СОЮЗ СОВЕТСКИХСОЦИА ЛИСТ ИЧ ЕСНИ 87(19) (И УБЛИН 6 Г 7/ КОМИТЕТ ОТКРЫТИЯ ГОСУДАРСТВЕННЫПО ИЗОБРЕТЕНИЯМПРИ ГКНТ СССР САНИЕ РЕТЕН ИДЕТЕЛЬСТ 35(54) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ИНАЦИИ(57) Изобретение относится к автоматике и вычислительной технике. Цель изобретения - расширение области применения устройства путем обеспечения возможности сортировки информации по признакам, Устройство содержит блоки памяти (БП) 1, 2, счетчики 3, 4, входной регистр 5, регистры признака 6, размера 7, адреса 8, перезаписи 9, коррекции адреса 10, группу элементов И 11, мультиплексор 12,триггер 13, блок синхронизации 14 и имеет информационные входы 15,входы разрешения записи информации 16, признака 17,15 2размера 18, количества страниц 19, входывыбора режима 20, вход окончания записи-считывания 21, информационные выходы 22, выходы готовности 23 и синхронизации 24. Устройство последовательно принимает пачки слов, первоеиз которых является признаком, а следующие - данными, относящимися к этому признаку. Данные размещаются вБП 1, логически разбитом на страницы,количество которых не меньше, чем количество возможных значений признака,Адрес первой свободной ячейки каждойстраницы содержится в БП 2 и увеличивается по мере поступления данных ссоответствующим признаком. При заполнении страницы в ее последнююячейку и по соответствующему адресуБП 2 записывается адрес перехода насвободную страницу БП 1, в которуютеперь будут записываться данные, относящиеся к этому признаку, и т,д.При считывании происходит выборкаданных из нужной страницы до ор,пока не будет обнаружен конец данныхтекущего признака или адрес переходана новую страницу. 1 ил, 1509871Изобретение относится к автоматикеи вычислительной технике и можетбыть использовано при реализации систем обработки данных.5Цель изобретения - расширение области применения путем обеспечениявозможности сортировки информации попризна кам.На чертеже приведена схема устрой- Оства.Устройство содержит блоки 1 и 2памяти, счетчики 3 и 4, входной регистр 5, регистры признака 6, размера 7, адреса 8, перезаписи 9, коррекции адреса 10, группу элементов И 11,мультиплексор 12, триггер 13, блок 14синхронизации, информационные, входы15, входы разрешения записи информации 16, признака 17, размера 18, количества страниц 19, входы выбора 20,и 20 режима, вход 21 окончания записи-считывания, информационные выходы 22, выходы готовности 23 и синхронизации 24, Е 5Входной регистр 5 предназнацен дляпромежуточного хранения сортируемойинформации перед записью ее в блок 1памяти в режиме сортировки, а такжедля записи адресов начала страниц ЗОпамяти в блок 2 памяти в режиме подготовки, и"разрядный регистр 6 признака служит для Фиксации первогослова, являющегося признаком сортируемой информации, поступающей навходы 15, в-разрядный регистр 7 размера хранит информацию о размере области на числовой оси, в пределахкоторой сортируемая информация идентифицируется одним признаком. Инфор Омация о размере области условно названа кодом размера, а размер областина числовой оси - Фрагментом, приэтом размер фрагмента может быть от2 до 2 . Регистры признака 6 и размера 7 совместно с группой элементовИ 11, содержащей ш элементов И, Формируют в младших разрядов адреса блока 2 памяти, который предназначендля хранения адресов начала страницпамяти в блоке 1 памяти,Блок 14 синхронизации вырабатываеттактовые сигналы, необходимые для работы устройства. Этот блок может бытьвыполнен по стандартной схеме микропрограммного управления и содержатьПЗУ, регистр и генератор импульсов.1-разрядный счетчик 3 слов Формирует 1 младших разрядов адреса блока 1 памяти. От значения 1 зависитразмер страницы памяти в блоке 1 памяти, Кроме этого, данный счетчик вы"дает сигнал заполнения страницы информацией, что является признаком перехода к свободной странице.Е-разрядный регистр 8 адреса необходим для формирования Ь старших разрядов адреса блока 1 памяти. ЗначениеЬ определяет количество страниц, которые можно сформировать в блоке 1памяти, 1.-разрядный счетчик 4 страницпредназначен для хранения в начальный момент времени сортировки числазарезервированных страниц, равногоколичеству возможных значений признака, а в дальнейшем для подсчета числазанятых страниц в блоке 1 памяти, сучетом первоначально зарезервированных.Е-разрядный регистр 9 перезаписии мультиплексор 12 служат для организации записи адреса первой свободнойячейки страницы в блок 2 памяти впроцессе сортировки; кроме этого, по"средством мультиплексора 12 по сигналу переполнения счетчика 3 слов производится запись содержимого счетчика 4 страниц (адреса перехода) в пос"леднюю ячейку страницы.Блок 1 памяти используется для записи отсортированной информации. Предварительно определенная часть блока1 памяти условно разбивается на стра"ницы посредством записи в блок 2 памяти адресов первых ячеек страниц.1.-разрядный регистр 10 коррекцииадреса служит для записи адреса перехода, считанного из последней ячейкистраницы (по сигналу переполнениясчетчика 3 слов), в регистр 8 адресав процессе чтения отсортированной информации из блока 1 памяти.Триггер 13 по выходу 23 готовностиуведомляет внешнее устройство о готовности устройства сортировки к приему информации,Устройство работает следующим образом,Режим подготовки.В данном режиме идет подготовкаблока 2 памяти для сортировки информации. В блок 2 памяти по адресам,определяемым кодами признака и размера, записываются данные, являющиесяпри начале сортировки адресами началастраниц, на которые разбивается блок1 памяти, а в дальнейшем блок 2 памя 1509871ти содержит текущие адреса первых свободных ячеек страниц памяти, в которые будет производиться запись сортируемой информации.В исходном состоянии все регистры и счетчики обнулены (цепи нулевых установок на чертежах не показаны). Внешнее устройство по входам 20 устанавливает код режима подготовки, По О входу 15 последовательно в устройство поступают данные о коде размера, о коде признака и адреса блока 1 памяти, которые последовательно сигналами по входам 18, 17 и 16 записываются 5 в регистры размера 7, признака 6 и входной регистр 5, одновременно по К-входу происходит сброс триггера 13 (сброс готовности) и устанавливается на его втором выходе сигнал нНачало 20 цикла", который разрешает работу блока 14 синхронизации - происходит запись информации в блок 2 памяти по адресу, определяемому содержимым регистров размера 7 и признака 6, Пос ледовательность записи: в первом такте выдаются сигналы С и С синхронизации входного регистра 5 и регистра 9 перезаписи, во втором такте выдается сигнал выбора С и А записи блока 2 памяти, затем вырабатывается сигнал, поступающий на вход триггера 13 и устанавливает устройство.в состояние готовности к приему следующей информации, Далее внешнее устройство изменяет код признака и информацию во входном регистре 5 (адрес блока 2 памяти) и снова повторяет цикл записи адреса начала следующей страницы в блок 2 памяти. Количество таких цик лов записи равно количеству возможных значений признакаРежим сортировки.Внешнее устройство по входам 20 устанавливает код режима сортировки, по входу 15 данных - число страниц, зарезервированных в блоке 1 памяти (в начальный момент сортировки число страниц равно числу возможных значений признака), которое по сигналу с входа 19 записывается в счетчик 4 страниц, затем на вход 15 поступает признак информации и сигналом с входа 17 записывается в регистр 6 признака. Далее на вход 15 последовательно поступает сортируемая информация, относящаяся к данному признаку. При поступлении первого слова сигналом с входа 6 происходит запись его во входной регистр 5, сброс триггера 13, и блок 14 синхронизации начинает отрабатывать цикл записи вблок 1 памяти в следующей последовательности;такт первый - выдается сигнал разрешения считывания Сиз блока 2 памяти - происходит считывание адресаблока 1 памяти;такт второй - устанавливаются сигналы А, А записи в счетчик 3 слови регистр 8 адреса,такт третий - выдаются сигналы Си С 8 синхронизации разрешения входного регистра 5 и регистра 8 адреса - установка информации на входеданных блокапамяти и адреса, одновременно снимается сигнал Сразрешения считывания из блока 2 памяти;такт четвертый - вЫдается сигналА, записи - запись информации в блок1 памяти,такт пятый - устанавливаются сигналы У на счетном входе счетчика 3эслов;такт шестой - вырабатывается сигнал "Конец цикла" - установка готовности устройства,При поступлении последнего словатекущего признака внешнее устройствовыставляет сигнал по входу 21 "Конецзаписи/чтения", При наличии этогосигнала, по окончании записи в блок 1памяти блоком 14 синхронизации в пятом такте снимается сигнал С синхронизации входного регистра 5 и устанавливается сигнал У на счетном входе счетчика 3 слов, далее устанавливаются сигналы А э записи в регистр 9перезаписи, С э синхронизации регистра 9 перезаписи, У, и С, управленияи синхронизации мультиплексора 12,происходит запись информации из счетчика 3 слов в регистр 9 перезаписии установка ее на двунаправленных инФормационных шинах блока 2 памяти,а в седьмом такте сигналами Азаписии С синхронизации информация записывается в блок 2 памяти, т.е. происхо-дит запись адреса следующей незанятойячейки данной страницы в блоке 1 памяти, В восьмом такте устанавливаетсятриггер 13, и внешнее устройство выдает новый код признака.При заполнении страницы в блоке 1памяти счетчик 3 слов выдает в блок 14синхронизации сигнал переполнения, Поэтому сигналу происходит следующее;снимается сигнал С синхронизации входного регистра 5, устанавливается сигнал Ссинхронизации мультиплексора 12 и в следующем такте сигналом А, записи происходит запись содержимого счетчика 4 блоков в блок 1 памяти (запись адреса перехода на начало свободной страницы), далее сигналом Азаписи происходит запись этого же адреса в регистр 8 адреса. Если по заполнении страницы внешнее устройство выдало сигнал "Конец записи/чтений", то одновременно с записью адреса перехода в блок 1 памяти происхо дит его запись в блок 2 памяти сигналами Лзаписи и Ссинхронизации.По окончании сортировки ячейки блока 1 памяти с адресами, хранящимися в блоке 2 памяти, внешнее устрой ство прописывает кодом-признаком конец информации (код-признак представляет собой ключевое слово, которое идентифицируется внешним устройством).Режим чтения, 25Данный режим включает в себя режим подготовки со всеми его операциями и собственно режим чтения, который начинается установкой внешним устройством по входу 20 кода режима чтения, 30 затем в регистр 6 признака внешним устройством записывается признак первого фрагмента информации (адрес ячейки блока 2 памяти, в которой находится адрес первой страницы блока 1 памяти, относящейся к данному признаку). По этому адресу происходит выборка из блока 2 памяти и перезапись в счетчик 3 слов и регистр 8 адреса. В следующем такте происходит чтение 40 блока 1 памяти и затем тактирование сигналом синхронизации с выхода 24 выдачи информации во внешнее устройство, а также прибавление в счетчик 3 слав единицы для формирования следую щего адреса блока 1 памяти. При переполнении счетчика 3 слов считываемое из блока 1 памяти слово записывается в регистр 10 коррекции адреса, далее это слово передается на вход регистра 8 адреса, записывается в него, и на адресных входах блока 1 памяти устанавливается следующий адрес информации, принадлежащей данному признаку, и продолжается считывание из блока 1 памяти во внешнее устройство.По окончании чтения информации, относящейся к данному признаку, что определяется по считыванию внешним устройством кода-признака конца информации, внешнее устройство выставляет на входе сигнал "Конец записи/ /чтения, устройство выдает сигнал 23 готовности к приему, внешнее устройство меняет код признака, сбрасывает триггер 13 готовности, происходит чтение следующего фрагмента информации и т,д.Формула изобретенияУстройство для сортировки информации, содержащее два блока памяти, два счетчика, блок синхронизации и группу элементов И, причем первый и второй входы выбора режима устройства соединены соответственно с первым и вторым входами блока синхронизации, первый, второй, третий и четвертый выходы которого соединены соответственно с входами управления записью первого и второго блоков памяти и первого счетчика и счетным входом первого счетчика, пятый выход блока синхронизации является выходом синхронизации устройства, выходы первого блока памяти являются информационными выходами устройства, о т л и - ч а ю щ е е с я тем, что, с целью расширения области применения путем обеспечения возможности сортировки информации по признакам, в него введены входной регистр, регистр признака, регистр размера, регистр перезаписи, регистр коррекции адреса, мультиплексор и триггер, причем группа информационных входов устройства соединена с информационными входами входного регистра, регистра признака, регистра размера и второго счетчика, входы разрешения записи которых подключены к входам разрешения записи соответственно информации, признака, размера и количества страниц устройства, выходы разрядов входного регистра соединены с информационными входами первого блока памяти, выход 1-го разряда регистра признака, начиная с младшего ( = 1, 2, , в; ш - количество разрядов регистра размера), и выход -го разряда регистра размера соединены соответственно с первым и вторым входами -го элемента И группы, выходы которой и выходы групп из и - п 1 старших разрядов регистра признака, где и - количество разрядов регистра признака, соединены соответственно с группами младших и старших разрядов адреса второго блока памяти1509871 Составитель В.ГороховРедактор А.Шандор Техред А.Кравчук Корректор М.Иароши жжещ ж шшшшшше 1 Шж жщв ж Юж ш евшавееж Заказ 5812/45 Тираж 668 Подписное ВНИИХИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж, Раушская наб д. 4/5Производственно-издательский комбинат "Патент", г. Ужгород, ул. Гагарина,101 группа из 1 младших двунаправленныхинформационных шин которого, где 1 -количество разрядов регистра перезаписи, соединена с группой выходовразрядов регистра перезаписи и информационными входами первого счетчика,выходы разрядов которого соединеныс группой информационных входов регистра перезаписи и с группой иэ 10младших адресных входов первого блокапамяти, группа иэ Ь выходов старшихразрядов которого, где Ь - количестворазрядов регистра коррекции адреса,соединена с группой информационныхвходов регистра коррекции адреса,группа из Ь старших двунаправленныхинформационных шин второго блока памяти соединена с группой выходовстарших разрядов входного регистра, 20выходами разрядов регистра коррекцииадреса, выходами мультиплексора игруппой информационных входов регистра адреса, выходы разрядов которогосоединены с группой из Ь старших раз-"25рядов адреса первого блока памяти ипервой группой информационных входов мультиплексора, вторая группа информационных входов которого подключенак выходам разрядов второго счетчика,счетный вход которого. подключен к выходу переполнения первого счетчика итретьему входу блока синхронизации,выходы которого с шестого по шестнадцатый соединены соответственно с входами разрешения записи регистра адреса, регистра перезаписи, регистракоррекции адреса, входами синхронизации входного регистра, второго блокапамяти, регистра адреса, регистра пе"резаписи, мультиплексора, регистракоррекции адреса, управляющим входоммультиплексора и входом установкитриггера в единичное состояние, входустановки в нулевое состояние которого объединен с входом разрешения записи информации устройства, прямой иинверсный выходы триггера подключенысоответственно к выходу готовностиустройства и четвертому входу блокасинхронизации, пятый вход которогоподключен к входу окончания записисчитывания устройства.