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

 

Изобретение относится к вычислительной технике и может быть использовано в системах обработки информации. Целью изобретения является расширение области применения. Устройство содержит блок синхронизации 1, счетчик 2, блок памяти 3, коммутатор 4, регистры 5 и 6, триггер 7, схемы сравнения 8 и 9, элемент ЗИ-2ИЛИ 10. УСТРОЙСТВО ОСУЩЕСТВЛЯЕТ ЗАПОМИНАНИЕ ПОСТУПАЮЩИХ ЧИСЕЛ, ОПРЕДЕЛЕНИЕ МАКСИМАЛЬНОГО И МИНИМАЛЬНОГО ЧИСЕЛ И ВЫДАЧУ ЧИСЕЛ В ПОРЯДКЕ ВОЗРАСТАНИЯ ИЛИ УБЫВАНИЯ. 5 ИЛ.

(s!p 4 С. 06 Г 7/06

ОПИСАНИЕ ИЗОБРЕТЕНИЯ у + б Щ .,- 1 у,".„ф СОЮЗ СОВЕТСНИХ - с, -, -+:,=-

) б - .

ГОСУДАРСТВЕННЫЙ НОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТНРЫТИРМ

ПРИ ГКНТ СССР

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4385318/24-24 (22) 29. 02, 88 (46) 15.08.89. Вюл. У 30 (71) Львовский политехнический институт им.Ленинского комсомола (72) И.Б.Боженко, О.К.Г!ешков и П.А.Кондратов (53) 681.327.66(088.8) (56) Авторское свидетельство СССР

1 "- 1196849, кл, Г 06 F 7/06, 1984.

Авторское свидетельство СССР

И 1183956, кл. С 06 Г 7/06, 1984. (54) УСТРО!!СТВО ЛПЯ СОРТИРОВКИ И!!ФОРИАЦИИ

„„80„„1501039 А 1

2 (57) Изобретение относится к вычислительноц иехн <ке и может б ITb использовано в системах обработки инАомации, Целью изобретения является расширение области применения. Устройство содержит блок синхронизации 1, счетчик 2, блок памяти 3, коммутатор

4, регистры 5 и 6, триггер 7, схемы сравнения 8 и 9, элемент ЗИ-2ИЛИ 10.

Устройство осуцествляет запоминание поступающих чисел, определение максимального и минимального чисел и выдач чисел в порядке возрастания или убывания. 5 ил. низацпи блока 1; ж — сигналы записи в блок 3 памяти; з — сигнал задания режима "Выдача" на входе 12; и — сигналы модиАикации счетчика 2; к — признак окончания выдачи на выходе 18.

Дополнительно обозначены: I — прием данных в устройство; .II — выдача отсортированных данных.

На Аиг.4 обозначены: а — синхроимпульсы на первых входах формирователей 27,28 блока 1 синхронизации; б — сигнал режима на втором входе формирователя; в — инверсный выход триггера 29 формирователя; г — выход Аормирователя.

На фиг.5 обозначены: а,б — синхроимпульсы Т1,Т2; в — сигналы модификации счетчика 2; r — - выход блока 3 памяти; д — сигналы записи в блок 3; е — сигналы идентификации "Строб выдачи" на выходе 19.

Устройство работает следующим образом.

По входам 14, 15 в устройство поступают сдвинутые по Аазе относительно друг друга тактирующие импульсы Т1, Т2 (Аиг. 3a,б). Режим ввода задается сигналом Прием" установкой уровня на входе 11 (фиг.Зв). При этом на входе 12 установлен "0", а вход

13 — в состоянии, зависящем от направления упорядочивания. По уровню "1" на входе 11 коммутатор 4 подключает вход 16 к инАормационному входу счетчика 2, по "0" на входе 12 элемент 10 блокирует поступление на выход 18 признака окончания выдачи.

Сигнал "Прием" поступает на D —вход триггера 29 Аормирователя 28 (фиг.4о) и через элемент 2И 30 — на выход Аормирователя.

Синхроимпульс Т2 поступает на первый вход Аормирователя (фиг.4а) и по его отрицательному фронту на выходе

29 устанавливается "0" (Аиг.4в). Тем самым элемент 30 Аормирователя 28 вырабатывает на выходе блока 1 импульс (Аиг.4г), устанавливающий регистр 5 в нулевое, регистр 6 — в единичное состояние (фиг.3r).

По синхроимпульсам Т1, поступающим через вход 14, элементы 2И- 20 и

2ИЛИ 24 на выход установки блока 1, в счетчик заносятся числа, поступающие по входу 16 (Аиг,Зд)„ по Т2,поступающим через элемент 2И 21 на выход записи блока 1 (Аиг.Зж) в блок 3 памати по адресам, соответствующим сос3

1501039

Изобретение относится к вычислительной технике и может быть использовано в системах обработки инАормации.

Цель изобретения — расширение области применения.

На Аиг.1 изображена Аункциональная схема устройства; на фиг,2 — функциональная схема блока синхронизации; на фиг.3-5 — временные диаграммы работы устройства: фиг ° 3 — работа в режимах ввода и вывода; Аиг.4 — работа формирователя в составе блока синхронизации; Аиг.5 — более подробно ра-15 бота устройства в режиме вывода.

Устройство содержит (Аиг.1) блок 1 синхронизации, .счетчик 2, блок 3 памяти, коммутатор 4, регистры 5 и 6, триггер 7, схемы 8 и 9 сравнения, эле-20 мент 2И-ИЛИ10, управляющие входы 1113 устройства, тактовые входы 14, 15, информационные вход 16 и выход 17, управляющие выходы 18,19 устройства.

По входу 11 поступает сигнал зада- 25 ния режима ввода "ПРИЕИ". По входу 12сигнал задания режима вывода "ВЬЩАЧА".

По входу 13 — сигнал задания направления сортировки "ВОЗРАСТАНИЕ". По входу 16 поступает тп-разрядный код 30 сортируемого числа, по m-разрядному выходу 17 считываются отсортированные числа, сопровождаемые идентификатором "СТРОБ ВЫДАЧИ" на выходе 19. С выхода 18 снимается признак окончания 35 выдачи.

С первых выходов схем 8,9 сравнения снимается сигнал равенства входных операндов A=B. С второго выхода схемы 8 сравнения — сигнал A)B, с 40 второго выхода схемы 9 сравнения

А(В.

Блок 1 синхронизации содержит (фиг.2) элементы 2И 20-22, 2ИЛИ 23, 24, ЗИ-НЕ 25,26 и формирователи 27, 28 им- 45 пульсов, которые содержат триггер 29 и элемент 2И 30. На первые входы Аормирователей 27,28 поступают синхроимпульсы с входов блока 1, соответственно 1 4 1,5 на вторые — сигналы

° у °

50 задания режимов и входов соответственно 1.2,1.1.

На Аиг.3 обозначены: а — синхроимпульсы Т1, поступающие на вход 14 устройства. б — синхроимпульсы Т2 на

55 входе 15; в — сигнал задания режима

"Прием" на входе 11; г — сигнал уста" новки регистров 5,6; д †сигналы установки счетчика 2; е — выход синхростна.

А о р м у л а и з о б р е т е н и я

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

5 150103 таянию счетчика 2, заносится "1", устянонленнная ня инАармяцианном входе блока 3. Вя синхронход регистров 5,6

Т2 поступают через элемент 2И 22 и выход синхрон11зации блока 1 (133иг.3e) .

Состояние счетчика 2 сравнивается схемой 8 сравнения с состоянием регист-. ра 5 и схемой 9 сравнения регистра 6.

Если первое из поступивших по входу

16 чисел не представляет собой единичный либо нулевой код, то по сигналам разрешения записи, которые обе схемы сравнения вырабатывают на своих вторых выходах, и по Т2 это число за- 15 несется в оба регистра. Если величины следующих чисел будут превышать величину числа, занесенного в регистр

5, они будут записываться туда. Если эти числа меньше занесенного в регистр 6, они заносятся в него. Тем самым в конце операции ввода в регистре 5 будет храниться максимальное число из входящих в упорядочиваемый список, в регистре 6 — минимальное.

После передачи в устройство всего списка сигнал "Прием" сбрасывается.

Элемент 20 блокирует поступление Т1 на вход установки счетчика 2, элемен- 30 ты 23,21 блокируют поступление Т2 на вход записи блока 3, элемент И 22— поступление И2 на синхронход регистров 5,6 ° Коммутатор 4 отключает от ин13ормационного входа 16 счетчик 2.

Если на входе 13 — "1" задается режим сортировки по возрастанию, и к информационным входам счетчика 2 подключается выход регистра 6. Если на входе 13 — 0, задана сортировка по 4 убыванию, подключается регистр 5.

Режим вынода задается сигналом

"Выдача" — установкой "1" на входе

13 (!13иг.Зз). Элемент 10 подключает к выходу 18 в зависимости от сигнала !! Возрастание первый выход схем 8

11

45 сравнения или 9. !33армиронатель 27 по импульсу Т1 вырабатывает аналогично формирователю 28 импульс, поступающий через элемент 24 блока 1 на установку счетчика 2 (фиг.Зд, участок

II). В счетчике устанавливается максимальное либо минимальное число списка. Затем счетчик мадоАицируется импульсами Т1 (Anr.3è). При .наличии

55 сигнала Возрастание 71 поступают через элемент ЗИ-HF. 25 и выход блока

1 на суммирующий вход счетчика, при отсутствии — через элемент ЗИ-HE 26 (! F)

И 13ыхад f>. 1Î кя 1 — 11 331 11! т 3311×31!1 !1к а. .

Влак 3 памяти выбирается !1 сп - T!i331313:n счетчика (Лиг.5 в, г) . Г 111 г!!13!!!1!!г из блока 3 "1" (!131!!.. 5е) пэнялягт, чта

ДаННОМУ ЯДРЕСУ СЧИт1!ВЯ!11!Я СПптНЕTC тнует число из списка, и и!> Т2 устанавливается триггер / — с выходя 19 поступает индент13фикятар передаваемого на выход 17 со счетчика числя.

По следующему Т1 триггер 7 сбрасывается (Лиг.5e).

Элементы 23,21 разрек!яют прохождение Т2 на вход записи блока 3. После считывания ин!3ормяции из блока 3 н него по текущему адресу заносится "О", установленный на информационном входе блока 3 — производится очистка памяти (!13иг,5 г,д).

При нормализации списка по возрастанию счетчик 2, последовательно переключаясь, установится в значение максимального числа списка. На первом выходе схемы 8 сравнения установится "1" и на выходе 18 — признак окончания выдачи. При нормализации по убыванию признак окончания поступит с первого выхода схемы 9 сравнения (13иг.3 к). По этому признаку сигнал

"Выдача" сбрасывается, поступление Т1 через элементы 25 или 26 и Т2 через

21 блокируется.

При включении питания ячейки памяти и регистры устанавливаются произвольно. Поэтому дчя их начальной установки необходима произвести подготовительный цикл ввода-вывода. В режиме ввода н устройство "одается нулевой код, который заносится в регистр 6, затем единичный, занося!!1и!1ся в регистр 5. В режиме вывода счетчик 2 последовательно генерирует нсе свои состояния и но нсе ячейки блока 3 заносятся "0" ° После этого устройство готово к работе.

Таким обр,язс м, осуществляется запоминание поступающего списка ч-!сел, определение максимального и минимапьного числа в списке и выдача нормализованного списка в порядке его убывания либо возрастания. Прп этом память опрашин".ñ"тся не полностью, а только в интервале размещения списка, что повышает быстродействие устрой15 11 1 39

Уса.й

Т1

Нач

cm Pi

Юояраои

8ыдача иихр

П асн которОГО подключен к выходам pR3pR дон счетчика и является инАормационHblM выходом устройства, R вход записи подключен к выходу записи блока синхронизации, тактовый вход, первый и второй управляющие входы которого являются соответственнотактовым входоми входами приема и выдачи устройства, о тлич ающе ес я тем,что,сцелью расширения области применения за счет возможности сортировки в определенном диапазоне, в него введены коммутатор, два регистра, две схемы сравнения, триггер, элемент 2И-ИЛИ,выход которого является выходом признака окончания выдачи устройства, первые входы первого и второго элементов И элемента 2И-ИЛИ подключены соответственно к выходам равно первой и второй схем сравнения, вторые входы элементов И элемента 2И-ИЛИ подключены к второму управляющему входу блока синхронизации, а третий вход первого элемента

° И элемента 2И-ИЛИ соединен с инверсным третьим входом элемента И элемента 2И-ИЛИ, первым управляющим входом коммутатора, третьим управляющим входом блока синхронизации и с входом

Возрастание" устройства, тактовый вход устройства соединен с входом сброса триггера, вход которого является выходом строба выдачи устройства, а инАормационный вход соединен с выходом блока памяти, информационный вход которого соединен с перным управляющим входом блока синхронизации и с вторым управляющим нходом коммутатора, первая, вторая и третья группы информационных входов которого подключены соответственно к информационным входам устройств» и к выходам разрядон первого и второго регистров, выходы разрядов которых соединены соответственно с первыми группами входов первой и второй схем сравнения, вторые группы входов которых объединены с инАормациооными входами первого и второго регистра и с выходами разрядов счетчика, второй тактовый вход устройства соединен с синхровходом триггера и вторым тактовым вхо-дом блока синхронизации, выходы задания режима счета и установки счетчика которого соединены соответственно с входами установки сложения, вычитания и начальной установки счетчика, информационные входы которого соеди25 иены с выходами разрядов коммутатора, выход начальной установки блока синхронизации соединен с входами установки в нулевое состояние первого и в единичное — второго регистров, входы разрешения записи которых сое= денены соответственно с выходами

"Больше" первой и "Меньше" второй схем сравнения, а синхронходы подключены к выходу пинхронизации блока синхронизации.

3.5

1 50! 039

1э01039

Составитель В.Козлов

Техред Л. Олийнык

Редактор О:Спесивых

Корректор Т.Палий

Заказ 4868/44 Типаж 668 Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

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

Производственно-издательский комбинат "Патент", r. Ужгород, ул. Гагарина, 101