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

(5 4 С Об Г 7/06 ОПИСАНИЕ ИЗОБРЕТЕНИЯ ГОСУДАРСТВЕННЫЙ НОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТНРЫТИРМПРИ ГКНТ СССР К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ(71) Львовский политехнический институт им.Ленинского комсомола (72) И.Б.Боженко, О.К.ешков и П,А.Кондратов(56) Авторское свидетельство СССР Р 1196849, кл, С 06 Р 7/06, 1984,Авторское свидетельство СССР (: 1183956, кл, С 06 Г 7/06, 1984. (54) УСТРОСТВО Д 31 Я СОРТИРОВКИ ИФОР- ИАЦИИ 8 О, 1501039 А 1 2(57) Изобретение относится к вычислительноц иехн гке и может быть использовано в системах обработки ицАомации, Целью изобретения является расширение области применения. Устройство содержит блок синхронизации 1, счетчик 2, блок памяти 3, коммутатор 4, регистры 5 и 6, триггер 7, схемы сравнения 8 и 9, элемент ЗИИЛИ 10. Устройство осуцествляет запоминание поступающих чисел, определение максимального и минимального чисел и выдач чисел в порядке возрастания илиубывания, 5 ил,разом.По входам 14, 15 в устройство поступают сдвинутые по Аазе относительнодруг друга тактирующие импульсы Т 1,Т 2 (Аиг. За,б), Режим ввода задаетсясигналом Прием" установкой уровняна входе 11 (фиг.Зв). При этомна входе 12 установлен "0", а вход13 - в состоянии, зависящем от направления упорядочивания. По уровню "1"на входе 11 коммутатор 4 подключаетвход 16 к инАормационному входу счетчика 2, по "0" на входе 12 элемент 10блокирует поступление на выход 18признака окончания выдачи,Сигнал "Прием" поступает на П -вход триггера 29 Аормирователя 28(Фиг,4 о) и через элемент 2 И 30 - навыход Аормирователя.Синхроимпульс Т 2 поступает на первыйвход Аормирователя ( Аиг.4 а) и поего отрицательному Аронту на выходе29 устанавливается "0" (Аиг,4 в). Темсамым элемент 30 Аормирователя 28 вырабатывает на выходе блока 1 импульс(Аиг,4 г), устанавливающий регистр 5в нулевое, регистр 6 - в единичноесостояние (Фиг,Зг).По синхроимпульсам Т 1, поступающимчерез вход 14, элементы 2 И. 20 и2 ИЛИ 24 на выход установки блока 1,в счетчик заносятся числа, поступающие по входу 16 (Аиг,Зд) по Т 2,поступающим через элемент 2 И 21 на выходзаписи блока 1 (Аиг,Зж) в блок 3 памати по адресам, соответствующим сос 3 1501039Изобретение относится к вычислительной технике и может быть использовано в системах обработки инАормации.Цель изобретения - расширение области применения.На Аиг.1 изображена Аункциональная схема устройства; на иг,2 - Аункциональная схема блока синхронизации; на Аиг.3-5 - временные диаграммыработы устройства: Фиг3 - работа врежимах ввода и вывода; Аиг,4 - работа Формирователя в составе блока синхронизации; Аиг,5 - более подробно ра бота устройства в режиме вывода.Устройство содержит (Аиг,1) блок 1синхронизации, счетчик 2, блок 3 памяти, коммутатор 4, регистры 5 и 6,триггер 7, схемы 8 и 9 сравнения, эле мент 2 И-ИЛИ 10, управляющие входы 1113 устройства, тактовые входы 14, 15,информационные вход 16 и выход 17,управляющие выходы 18,19 устройства.По входу 11 поступает сигнал задания режима ввода "ПРИЕИ". По входу 12 сигнал задания режима вывода "ВЬЩАЧА".По входу 13 - сигнал задания направления сортировки "ВОЗРАСТАНИЕ". Повходу 16 поступает тп-разрядный код 30сортируемого числа, по ш-разрядномувыходу 17 считываются отсортированные числа, сопровождаемые идентификатором "СТРОБ ВЫДАЧИ" на выходе 19. Свыхода 18 снимается признак окончания 35выдачи.С первых выходов схем 8,9 сравнения снимается сигнал равенства входных операндов А=В. С второго выхода схемы 8 сравнения - сигнал А)В, с 40 второго выхода схемы 9 сравнения А(В.Блок 1 синхронизации содержит (фиг.2) элементы 2 И 20-22, 2 ИЛИ 23, 24, ЗИ-НЕ 25,26 и формирователи 27, 28 им пульсов, которые содержаттриггер 29 и элемент 2 И 30. На первые входы Аормирователей 27,28 поступают синхроимпульсы с входов блока 1, соответственно 1 4 1.5 на вторые - сигналыу50 задания режимов и входов соответственно 1,2,1.1.На Аиг,З обозначены: а - синхроимпульсы Т 1, поступающие на вход 14 устройства б - синхроимпульсы Т 2 на955 входе 15; в - сигнал задания режима "Прием" на входе 11; г - сигнал уста" новки регистров 5,6; д всигналы установки счетчика 2; е - выход синхронизацпи блока 1; ж - сигналы записи в блок 3 памяти; з - сигнал задания режима "Выдача" на входе 12; и - сигналы модиАикации счетчика 2; к - признак окончания выдачи на выходе 18.Дополнительно обозначены: 1 - прием данных в устройство; 11 - выдача отсортированных данных,На Аиг,4 обозначены: а - синхроимпульсы на первых входах Аормирователей 27,28 блока 1 синхронизации;б - сигнал режима на втором входе формирователя; в - инверсный выход триггера 29 Формирователя; г - выход АормирователяНа Фиг,5 обозначены: а,б - синхроимпульсы Т 1,Т 2; в - сигналы модификации счетчика 2; г - выход блока 3 памяти; д - сигналы записи в блок 3; е - сигналы идентификации "Строб выдачи" на выходе 19.Устройство работает следующим обства.формула изобретенияУстройство для сортировки информации, содержащее счетчик, блок синхронизации, блок памяти, адресчый вход 5 150103тоянию счетчика 2, заносится "1", установленнная на инАормационном входеблока 3. На синхровход регистров 5,6Т 2 поступают через элемент 2 И 22 ивыход синхронизации блока 1 (оиг.Зе),5Состояние счетчика 2 сравниваетсясхемой 8 сравнения с состоянием регистра 5 и схемой 9 сравнения регистра 6,Если первое из поступивших по входу16 чисел не представляет собой единичный либо нулевой код, то по сигналам разрешения записи, которые обесхемы сравнения вырабатывают на своихвторых выходах, и по Т 2 это число занесется в оба регистра, Если величины следующих чисел будут превышатьвеличину числа, занесенного в регистр5, они будут записываться туда. Если эти числа меньше занесенного врегистр 6, они заносятся в него, Темсамым в конце операции ввода в регистре 5 будет храниться максимальное число из входящих в упорядочиваемый список, врегистре 6 - минимальное,После передачи в устройство всегосписка сигнал "Прием" сбрасывается.Элемент 20 блокирует поступление Т 1на вход установки счетчика 2, элементы 23,21 блокируют поступление Т 2 навход записи блока 3, элемент И 22 -поступление И 2 на синхровход регистров 5,6Коммутатор 4 отключает отинормационного входа 16 счетчик 2.Если на входе 13 - "1" задаетсярежим сортировки по возрастанию, и кинАормационным входам счетчика 2 подключается выход регистра 6. Если навходе 13 - О , задана сортировка по 40убыванию, подключается регистр 5.Режим вывода задается сигналом"Выдача" - установкой "1" на входе13 (Лиг,Зз). Элемент 10 подключает квыходу 18 в зависимости от сигналаВозрастание первый выход схем 845сравнения или 9, формирователь 27 поимпульсу Т 1 вырабатывает аналогичноформирователю 28 импульс, поступающий через элемент 24 блока 1 на установку счетчика 2 (Лиг.Зд участок11). В счетчике устанавливается максимальное либо минимальное число списка, Затем счетчик модоАицируется импульсами Т 1 (Аиг,Зи), При .наличии55сигнала Возрастание Т 1 поступаютчерез элемент ЗИ-НЕ 25 и выход блока1 на суммирующий вход счетчика, приотсутствии - через элемент ЗИ-НЕ 26/и выход 6,ока 1 -в 1 т;ич ко.,Блок 3 памяти выбирается . сотрлнюсчетчика (Лиг,5 в, г) . Гчт,;г изблока 3 "1" (фг, 5 е) .а гт чтоданному адресу считваия скотетствует число из списка, и по Т 2 устанавливается триггер 7 - с вьхода 19поступает индентификатор передаваемого на выход 17 со счетчика числа,По следующему Т 1 триггер 7 сбрасывается (Лиг.5 е),Элементы 23,21 разрекают прохождение Т 2 на вход записи блока 3. Послесчитывания инйорьаци из блока 3 внего по текущему адресу заносится Оустановленный на индормационном входе блока 3 - производится очистка памяти (Лиг,5 г,д).При нормализации списка по возрастанию счетчик 2, последовательно переключаясь, установится в значениемаксимального числа списка. На первом выходе схемы 8 сравнения установится 1 и на выходе 18 - признакокончания выдачи, При нормализации поубыванию признак окончания поступитс первого выхода схемы 9 сравнения(Аиг.З к). По этому признаку сигнал"Выдача" сбрасывается, поступление Т 1через элементы 25 или 26 и Т 2 через21 блокируется,При включении питания ячейки памяти и регистры устанавливаются произвольно. Поэтому для их начальной установки необходимо произвести подготовительный цикл ввода-вывода. В режимеввода в устройство "одается нулевойкод, который заносится в регистр 6,затем единичны, заносяяйся в регистр 5, В режиме вывода счетчик 2последовательно генерирует все своисостояния и во все ячейки блока 3 заносятся "0"После этого устройствоготово к работе,Таким образсм, осуществляется запоминание поступающего списка чисел,определение максимального и иималь.ного числа в списке и выдача нормализованного списка в порядке его убывания либо возрастания. Прп этомпамять опрашивается не полностью, атолько в интервале размещения списка,что повышает быстродействие устрой151039 Т 1 НачсеР иихр Присн которого подключен к выходам рязрядон счетчика и является инАормационным выходом устройства, а вход записи подключен к выходу записи блокасинхронизации, тактовый вход, первыйи второй управляющие входы которого являются соответственнотактовым входоми входами приема и выдачи устройства,о тл и ч а ю ще е с я тем,что,с цельюрасширения области применения за счетвозможности сортировки в определенномдиапазоне, в него введены коммутатор,два регистра, две схемы сравнения,триггер, элемент 2 И-ИЛИ,выход котоРого является выходом признака окончания выдачи устройства, первые входыпервого и второго элементов И элемента 2 И-ИЛИ подключены соответственнок выходам равно первой и второй схемсравнения, вторые входы элементов Иэлемента 2 И-ИЛИ подключены к второму управляющему входу блока синхронизации, а третий вход первого элементаИ элемента 2 И-ИЛИ соединен с инверсным третьим входом элемента И элемента 2 И-ИЛИ, первым управляющим входомкоммутатора, третьим управляющим входом блока синхронизации и с входомВозрастание" устройства, тактовыйвход устройства соединен с входомсброса триггера, вход которого является выходом строба выдачи устройства,а инАормационный вход соединен с выходом блока памяти, информационный вход которого соединен с перным управляющим входом блока синхронизации ис вторым управляющим нходом коммутатора, первая, вторая и третья группыинформационных входов которого подключены соответственно к информационным входам устройств и к выходамразрядон первого и второго регистров,выходы разрядов которых соединенысоответственно с первыми группамивходов первой и второй схем сравнения,вторые группы входов которых объединены с инАормациооными входами первого и второго регистра и с выходамиразрядов счетчика, второй тактовыйвход устройства соединен с синхровходом триггера и вторым тактовым вхо дом блока синхронизации, выходы задания режима счета и установки счетчикакоторого соединены соответственно свходами установки сложения, вычитания и начальной установки счетчика,информационные входы которого соеди 25 иены с выходами разрядов коммутатора,выход начальной установки блока синхронизации соединен с входами установки в нулевое состояние первогои в единичное - второго регистров,входы разрешения записи которых соеденены соответственно с выходами1 э 01039 оставитель В,Козлехред Л. Олийнык едактор О:Спесивых Коррект алий изводственно-издательский комбинат "Патент", г. Ужгород, ул. Гагарина, 10 Заказ 4868/44 Типаж 668 ПодписноеВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР113035, Москва, Ж, Раушская наб., д. 4/5