Устройство для сортировки информации Советский патент 1989 года по МПК G06F7/06 

(Л

СП

00 со

IS

150

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

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

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

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

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

С первых выходов схем 8,9 сравнения снимается сигнал равенства входных операндов . С второго выхода схемь 8 сравнения - сигнал , с второго выхода схемы 9 сравнения - .

Блок 1 синхронизации содержит (фиг.2) элементы2И 20-22, 2ШТИ 23, 24, ЗИ-НЕ 25,26 и формирователи 27, 28 им- пульсов,которые содержат триггер 29 и элемент 2И 30. На первые входы формирователей 27,28 поступают синхроимпульсы с входов блока 1, соответственно 1.4,1.5, на вторые - сигналы задания режимов и входов соответственно 1.2,1.1.

На фиг.З обозначены: а - синхроимпульсы Т1, поступающие на вход 14 устройства; б - синхроимпульсы Т2 на входе 15; в - сигнал задания режима Прием на входе 11; г - сигнал установки регистров 5,6; д - сигналы установки счетчика 2; е - выход синхронизации блока 1; ж - сигналы записи в блок 3 памяти; з - сигнал задания режима Выдача на входе 12; и - сигналы модификации счетчика 2; к - признак окончания выдачи на выходе 18. Дополнительно обозначены: I - прием данных в устройство; TI - выдача отсортированных данных.

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

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

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

По входам 14,15 в устройство поступают сдвинутые по фазе относительно друг друга тактирующие импульсы 11, Т2 (фиг. За,б). Режим ввода задается сигналом прием установкой уровня Т на входе 11 (фиг.Зв). При этом на входе 12 установлен О, а вход 13-в состоянии,зависящем от направления упорядочивания. По уровню 1 на входе 11 коммутатор 4 подключает вход 16 к информационному входу счетчика 2, по О на входе 12 элемент 10 блокирует поступление на выход 18 признака окончания выдачи.

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

Синхроимпульс Т2 поступает на первый вход формирователя ( фиг.4а) и по его отрицательному фронту на выходе 29 устанавливается О (фиг.4в). Тем самым элемент 30 формирователя 28 вырабатывает на выходе блока 1 импульс (фиг.4г), устанавливакзщий регистр 5 в нулевое, регистр 6 - в единичное состояние (фиг.Зг).

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

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

12поступают через элемент 2И 22 и выход синхронизации блока 1 (фиг.Зе)

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

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

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

Режим вывода задается сигналом Выдача - установкой 1 на входе

13(фиг.Зз). Элемент 10 подключает к выходу 18 в зависимости от сигнала Возрастание первый выход схем 8 сравнения или 9. Лормирователь 27 по импульсу Т1 вырабатывает аналогично формирователю 28 импульс, поступающий через элемент 2А блока 1 на ус- тановку счетчика 2 (фиг.Зд, участок

II) . В счетчике устанавливается максимальное либо минимальное число спика. Затем счетчик модофицируется импульсами Т1 (фиг.Зи). При .наличии сигнала Возрастание Т1 поступают через элемент ЗИ-НЕ 25 и вькод блока 1 на суммирую ций вход счетчика, при отсутствии - через элемент ЗИ-НЕ 26

д 5 0 5

Q

..

0

5

5

)

и выход блока 1 - па пычитм1 11чи|( пхог;. Блок 3 памяти выбирается пг состоянию счетчика (фиг.5 n,iO. Счнтыг1ани.г из блока 3.1 (фиг.5е) пзн,т;пгт, что данному адр.есу считывания соотпетст- вует число из списка, и по Т2 устанавливается триггер 7 - с В1, 19 поступает индентификатор передаваемого на выход 17 со счетчика числа. По следующему Т1 триггер 7 сбрасывается (фиг.5е).

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

При нормализации списка по возрастанию счетчик 2, последовательно переключаясь, установится в значение максимального числа списка. На первом выходе схемы 8 сравнения установится 1 и на выходе 18 - признак окончания выдачи. При нормализации по убыванию признак окончания поступит с первого выхода схемы 9 сравнения (фиг.З к). По этому признаку сигнал Выдача сбрасывается, поступление Т Т через элементы 25 или 26 и Т2 через 21 блокируется.

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

Таким o6pii3e M, осуг(ествляется запоминание поступающего списка чисел, определение максимального и минимального числа в списке и вьутача нормализованного списка в порядке его убывания либо возрастания. При этом память опрашивается не полностью, а только в интервале размещения списка, что повышает быстродействие устройства. форму.л а изобретения

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

которого подключен к пыходам разрядов счетчика н является информационным выходом устройства, а вход записи подключен к выходу записи блока синхронизации, тактовый вход, первый и второй управляюи ие входы которого являются соответственно тактовым входом и входами приема и вьщачи устройства, отличающееся тем,что,с целью расширения области применения за счет возможности сортировки в определенном диапазоне, в него введены коммутатор два регистра, две схемы сравнения, триггер, элемент 2И-ИЛИ,выход кото- рого является выходом признака окончания выдачи устройства, первые входы первого и второго элементов И элемента 2И-ИЛИ подключены соответственно к выходам равно первой и второй схем сравнения, вторые входы элементов И элемента 2И-1Ш11 подключены к второму управляющему входу блока синхронизации, а третий вход первого элемента И элемента 2И-ИЛИ соединен с инверс- ным третьим входом элемента И элемента 2И-ИЛИ, первым управляющим входом коммутатора, третьим управляющим входом блока синхронизации и с входом Возрастание устройства, тактовый вход устройства соединен с входом сброса триггера, вход которого является выходом строба вьщачи устройства, а информационный вход соединен с выходом блока памяти, информационный

вход которог о соединен с первым управляющим входом блока синхронизации и с вторым управляющим входом коммутатора, первая, вторая и третья группы информационных входов которого подключены соответственно к информационным входам устройства и к выходам разрядов первого и второго регистров выходы разрядов которых соединены соответственно с первыми группами входов первой и второй схем сравнени вторые группы входов кот/эрых объединены с информациооными входами первого и второго регистра и с вьпходами разрядов счетчика, второй тактовый вход устройства соединен с синхро- входом триггера и вторым тактовьм вхо- дом блока синхронизации, выходы задания режима счета и установки счетчик которого сгединены соответственно с входами установки сложения, вычитания и начальной установки счетчика, информационные входы, которого соединены с выходами разрядов коммутатора выход начальной установки блока синхронизации соединен с входами установки в нулевое состояние первого и в единичное - второго регистров, входы разрешения -записи которых сое-- денены соответственно с выходами Больше первой , и Меньше второй схем сравнения, а синхровходы подключены к выходу синхронизации блока синхронизации.

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

Возраст Budava

Прием

Фиг.1

Нач . ijcmPf

Синхр

to

3

СЗ а со

Д ejotV) т