Устройство для сортировки данных

ЮЭ СОВЕТСКИХЦИАЛИСТИЧЕСКИХСПУБЛИК 1784967 06 Г 7/06 Е ГОСУДАРСТВЕННОЕ ПАТЕНТНОЕВЕДОМСТВО СССР(ГОСПАТЕНТ СССР) ПИСАНИЕ ИЗОБР АВТОРСКОМУ СВИДЕТЕЛЬСТВ 1(71) Львовский политехнический институт им. Ленинского комсомола(56) 1. Авторское свидетельство СССР В 1183956, кл. 6 06 Р 7/06, 1985.2. Авторское свидетельство СССР В 1546962, кл. О 06 Р 7/06, 1988 (прототип). (54) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ДАННЫХ(57) Изобретение относится к вычислительной технике и может быть использовано в системах обработки информации, Цель изобретения - повы шейие быстродейст. вия устройства. Устройство содержит блок управления, первый коммутатор, дешифратор, блок памяти,.регистр. блок шифратора, счетчик, группу сумматоров по модулю два, второй коммутатор, триггер, входы задания режима сортировки, приема. выдачи и "очиИзобретение относится к вычислительной технике и может быть использовано в системах обработки информации.Известно устройство, содержащее блоки.управления и памяти, счетчик, элементы 2 И. В режиме ввода данные списка являются адресом, по которому в память заносится: признак нахождения в списке, В режиме вывода при последовательном считывании из памяти элементы 2 И передают на выход устройства те состояния счетчика. которые соответствуют считанному признаку нахождения в списке. Быстродействие устройства ограничивается необходимостью опроса в стки", первый и второй тактирующие входы, входы младших и старших разрядов данных, выход сопровождения данных; информационные выходы. первой и второй групп, выход конца работы, В устройство вводится неупорядоченный список. Там он запоминается по эначеййям данных, входящих в список. Затем производится побайтный опрос памяти и выдача дайных, отмечейных признаком нахождения в списке. Блок шифратора осуществляе 1."ЪЗйорйетный опрос разрядов выбранного байта по возрастанию или убыванию, Поставленная цель достигается введением группы сумматоров по модулю 2, второго коммутатора, триггера и новых связей, что позволяет в процессе выдачи упорядочен його списка сохранять в па- ф мяти признаки нахождения в списке или стирать их. создавая тем самым возмож- Ш ность многократной вйдачи отсортированното списка и повышая таким образом быстродействие устройства в режиме выда чи при повторнойвыдаче списка, 6 ил. режиме выдачи всех ячеек памяти независимо от количества и значения данных, составляющих список (1,Ближайшим к заявляемому, является устройство, содержащее блоки управления, памяти й шифратора, элементы И-НЕ, коммутатор, дешифратор, группу функциональных преобразователей и регистр, Неупорядоченный список запоминается по адресам, соответствующим значениям данных, входящих в список. Признаки нахождения в списке группируются побайтно. В режиме вывода производится побайтный опрос памяти, при этом блок шифратора3 , 1784967 . 4осуществляет приоритетный опрос разря- инФормационному входу блока памяти и выдоввыбранногобайтэповозрастаниюлибо ходам сумматоров, первые входы которых по убыванию, При выдаче данйых сбответ- подключены к соответствующим выходам. ствующий им признак нахождения в списке дешифратора, а вторые входы - к выхбду из блока памяти стирается, в результате че регистра к информационному входу блока го для повторной выдачи списка необходи- шифратора.мв проиэвЪдить повторную операцию ввода Новыми существенными признаками йеупорядоченйбго списка, что снижает бы- заявляемого устройства являются введенстродействие устройства 21, . ные группы сумматоров по модулю два, втоЦель изобретения-"повышение быстро рого коммутатора, триггера, четвертого действия устройства, -управляющего входа и связей, отражающихПоставленнаяцель достигается тем, что новую"организацию взаимодействия между в устройство для сортировки данных, содер- элементами устройства.жащее блок управления, коммутатор, де- Новая совокупность элементов позвошифратор, блок памяти, регистр, блок 15 ляет в процессе выдачи упорядоченного шифратора и счетчик, выходы разрядов ко- списка либо сохранять в памяти признаки торого - информационные выходы первой нахождения.в списке, либо стирать их, что группы устройства и,соединены с адресны- создает возможность многократной выдачи ми входами блока памяти, информацион- отсортированного списка, что позволяет в, ные входы - с выходами первой группы 20 режиме выдачи при повторной выдаче спикоммутатора, синхровход - с первым выхо- ска повысить быстродействие устройства дом блока управления, вход управления - скак мийимум вдвое.входом задания режима сортировки устрой- На фиг. 1 приведена схема предлагае-. ства, первым входом первой группы входов мого устройства; на фиг. 2 - функциональ-. коммутатора и с первым входом управления 25 ная схема блока управления; на фиг, 3 - блока.шифратора, а вход записи - со вто- схема блока шифратора; на фиг. 4-6- пред-. рым выходом блока управления, третйй ставлены временные диаграммы работы выход которого подключен ко входу запи- устройства: на фиг. 4- в режиме ввода, фиг, си блока памяти, четвертый - выходсопро - в режиме вывода, фиг. 6 - в рекиме вождения данных устройства, пятый 30 очистки памяти.соединен с синхровходом регистра, первый и Устройство содержит (фиг, 1) блок 1 упвторой тактовые входы - соответствующие равления, первый коммутатор 2, дешифравходь 1 устройства, вход управления комму- гор 3, блок 4 памяти, регистр 5, блок 6 тации, подключен к выходу конца работы шифратора, счетчик 7, группу сумматоров 8 блока шифратора, вход приема - соответст по модулю два. второй коммутатор 9; тригвующий вход устройства, входразрешения гер 10, вгоды "задания сортировки 11, при- коммутации - вход выдачиустройства и под- ема 12, выдачи 13 и очистки 14, первый 15 и ключен ко второму входу управления блока второй 16 тактирующие входы, входы шифратора и входу управления коммутато- младших 17 и старших 18 разрядов данных, ра, второй вход первой группы которого 40 выход 19 сопровожденияданных, информасоединен с йнформационКьв "выходом ционнйе выходы первой 20 и второй 21 блока шифратора и является информаци- групп, выход 22 конца работы,онным входом второй группы устройства, Первый 1,1 и второй 1.2 выходы блока 1 первый и второй входы второй группы - управления подключены соответственно ко соответственно входы младших и старших 45 входам синхронизации и установки счетчиразрядов данных устройства, а выходы ка 7, третий 1.3 выход соединен со входом второй группы соединены со входом де- записи блока 4 йамяти, четвертый 1,4 - с шифратора, введены группа сумматоров выходом 19 сопровокдения данных устрой- по модулю 2, второй коммутатор и триггер, ства, пятый 1.5 - с синхровходом регистра выход которого - выход крнца работы уст 5, шестой 1 Л 1 - со входом сбросарегистра ройства; вход установки соединен с выхо- .5 и триггера 10, седьмой 1.13 - со входом дом переноса счетчика, а вход сброса - со управления второго коммутатора 9, первходом сброса:регйстра и шестым выходом вый 1.6 и второй 1,7 тактирующие подключеблока управления, вход "Очистка" которого ны соответственно к первому 15 и второму 16 - соответствующий вход управления уст тактирующим входамустройства; вход 1,8 ройства, а седьмой выход соединен со вхо- управления коммутации соединен с выходом управления второго коммутатора, дом конца работы блока 6 шифратора, вход выход которого йодключен к информацион- приема 1,9 - со входом 12 приема устройстному входу регистра, вход первой группы - ва, вход выдачи 1,10 - с входом 13 выдачи к выходу блока памяти, а второй группы - к устройства, входом управления первогокоммутатора 2 и вторым входом управления блока 6 шифратора,вход "очистки" 1.12 - с входом 14 "Очистка" устройства.Первый вход первой группы информационных входов первого коммутатора 2 5 подключен к входу 11 задания режйма сортировки устройства, входу управления счетом счетчика 7 и первому входу управденияблока 6 шифратора, второй вход - к информационному выходу блока 6 шифратора и информационному выходу 21 второй группы устройства, первый и второй входы второй группы подключены соответственно ко входам младших 17 и старших 18 разрядов данных устройства, первый выход соединен с информационным входом счетчика 7, а второй - со входом дешифратора 3, выходы которого подключены к первым входам соответствующих сумматоров 8 по модулю 20 два, выходы которых соединены со вторым информационным входом второго коммутатора 9 и с информационным входом блока 4 памяти, адресный вход которого подключен к информационному выходу счетчика 7 и информационному выходу 20 25 первой группы устройства, а выход - к первому информационному входу коммутатора 9, выход которого соединен с информационным входом регистра 5, вход которого под 30 ключен ко вторым входам соответствующих сумматоров 8 и к информационному входу блока 6 шифратора, Выход переноса счетчика 7 подключен ко входу установки триггера 10, выход которогосоединен с выходом 22 Блок 1 управления содержит (фиг. 2) коммутатор 23, триггер 24, элемент задержки 25 и элементы ИЛИ 26, 27, И 28 и И-ИЛИ 29, 30, 31, По выходу 1.1 блока 1 управлейия поступает сигнал синхронизации счетчика 7, по выходу 1.2 - сигнал записи в счетчик 7, записи в блок 4 памяти, по выходу 1,4 идентификатор СТРОБ поступает на выход 19 устройства, по выходу 1,5 - сигнал записи в регистр 5, по выходу 1.11 - сброс регистра 5 и триггера 10, по выходу 1.13 - управлениекоммутатора 9. По входу 1.8 поступает сигнал конца работы блока 6 шифратора,Блок 6 шифратора содержит (фиг. 3) 50 коммутатор 32, приоритетный шифратор 33 и группу сумматоров 34 по модулю два, Входы.первой группы информационных входов коммутатора 32 обьединены с первого по последний со входами второй группы его информационных входов соответственно, с последнего по первый. и являются информационным входом блока, Первые входы сумматоров 34 по модулю два объединены и подключены ко входу управления коммутатора 32, который является первым входом конца работы устройства, . 35 управления блока. Вход управленйя шифратора 33 является вторым входом управления . блока, выход зайроса шифратора 33 - выход конца работы блока, а выходы сумматоров 34, которые выйолняют функциЮуправляемых интервалов, - информациоййые выходы блока.На фиг.4 обозначены а - синхросигналы Т 1 на входе 15 устройства; б - синхроимпульсы Т 2 на входе 16 устройр ва, в - сигнал ПРИЕМ на входе 12; г. - состояние счетчйка : 7; д - младшие разряды поступающих дан-. ных на входе 17; е- состояние регистра 5," ж - состояние выхода блока 4 памяти,На фиг. 5 обозначены а, б - сигналы соответственно Т 1 и Т 2; в - сигнал ВЫД на входе 13 устройства; г - сигнал уСтановки счетчика 7 на выходе 1,2 блока 1; д в . выход конца работы блока 6 шифратора; е - состояние счетчика 7; ж - выход блока 4 памяти;3 - состояние регистра 5; и - информационный вход блока 6; к - . сигнал СТРОБ на выходе 19; л - синхросигйалы счетчика 7 на выходе 1,1; м- выход переноса счетчика 7, н - сигнал конца работы на выходе 22.На фиг. 6 обозначены а, б - сигналы Т 1 и Т 2; в - сигнал ВЫДна входе 13;г - сигнал ОЧИСТКА на входе 14; д - сигнал установки на выходе 1,2; е - выходконцаработы блока 6, ж - состояние счетчика 7; з - выход блока 4; и - состояние регистра 5; к - информацион н ый выход блока 6.. Реализованный вариант заявляемого устройства предназначен для упорядочивания списка данных числом до 128. Блок 1 управления выполнен на микросхемах се-рий К 555, коммутаторы 2,9 - на К 555 КП 11, дешифратор 3 - на К 555 ИД 7, блок 4 памяти представляет собой матрицу 8 х 16; реализованную на основе микросхем, многоразрядных, статической памяти К 531 РУ 8, регистр 5 выполнен йа К 555 ТМ 8, счетчик 7 - на К 564 ИЕ 11, группа сумматоров 8: - на К 555 ЛП 5, приоритетный шйфратор 33 блока 6 - на основе К 555 ИВ 1.Устройство работает следующим образом.Перед началом:ввода списка блок 4 памяти, обнулен. Управляющие сигналы на входах 11 - 14 - в состоянии "0", На входы 15, 16 поступают сигналыТ 1, Т 2;Соответственно в "О" установлен выход конца работы блока 6 шифратора, а в блоке 1 управления в "0" установлен триггер 24, злемейт ИЛИ 26 генерирует сигнал сброса регйстра 5 и триггера 10, выдача же прочих управляющих сигналов блокируется. Управляющие и информационные сигналы на входах устройства устанавливаются в промежутках между поступлением сигналов Т 2. Т 1 фиг. 4 а. б).Режим ввода списка задается установ- был обнулен, выход запроса блока 6 устакой в "1" сигнала ПРИЕМ (фиг, 4 в). По ин- навливается в "1" (фиг, 5, д). По совпадениюФормационным входзм н чизм нэчинают поступать уровней "1" сигнала ВЫД и инверсного вы 17 - младшие .по входу хода триггера 24 в блоке 1 элемент И-ИЛИ18 - старшие .разряды. Коммутатор 2 под 29 формирует сигнал установки счетчика 7ключэет вход 17 ко входу дешифрэтора 3, (Фиг, 5, г). При сортировке по возрастанию18 - ф а онному входу счетчи- счетчик 7 устанавливается в нулевое состока 7, Сигнал с роса на вь х7, С б оса на выходе 1,1 снимает- яние и начинает работать в режиме прямого. П н "1" нэ выходе элемента ИЛИ счета (фиг, 5, е), при сортировке по убыва 27 блока 1 коммутатор 9 подключает выход 10 нию счетчик устэнавливэется в ед иничное-. блока 4 к,информационному входу регист- значение и работает,в режиме инверсногосчета. По отрицательному фронту Т 2 (фиг. 5,По Т 1 (фиг, 4 а) элемент И-ИЛИ 29 фор- б)триггер 24 устанавливается в "1", и сигналмирует сигнал установкановки счетчика 7 в состо- установки счетчика снимается с выхода 1яние, соответствующее значению старших 15 э элемент И 28 перестает блокировать проразрядов поступающих данных (фиг. 4 г). По хождение сигнала СТРОБ,состоянием счетчика вы- По состоянию счетчика из блока 4 пэмябирается блок 4 памяти. ДешиФратор 3 ус- ти выбирается байт признаков нахождениятэнэвливэет на том входе группы в списке, например по адресу 0000 кодсумматоров 8 по модулю двэ, который соот 10000011 (Фиг. 5, ж).ветствует коду нэ входеэ входе 17, уровень "1". Поскольку при этом выход конца работы, п и коде 000 на входе 17 на блока 6 - в состоянии "1", элемент ИЛИ 27Например, при кодевыходе дешифраторэ устанавливается код передает "1" нэ управляющий вход комму 00000001. По Т 1 элементы зэдержки 25 и таторэ 9, который подключает выход блокаИ-ИЛИ 31 за время, необходимое для вы 4 памяти к информационному входу регистборки памяти, формируют сигнал записи в ра 5 и по Т 2 в регистр заносится выбранрегистр 5 состояния выхода блока 4 (фиг. ный байт признаков (фиг, 5, з), при4 е). В сумматорах 8 складывается по ИЛИ наличии в котором хотя бы одной "1" сигналкод на выходах дешифрэтора 3 и регистра 5. конца блока 6 сбрасывается, и коммутаторПо Т 2(фиг. 4 б) элемент И-ИЛИ 30 формирует 30 9 подключает к регистру 5 выходы сумматосигнал записи состояния на выходах сумма- ров 8,торов 8 в блок 4 (фиг, 4 ж). С поступлением В зависимости от направления сортиновых данных блок 4 выбирается по новому ровки блок 6 формирует код, соответствуюэдресу и в него заносится новый код. При щий занесенному в регистр 5 байтуэтом, если блок 4 выбирается по уже посту признаков (фиг, 5, и) и по Т 1 (фиг, 5, а) компавшему адресу, новый признак нэхожде- мутатор 23 и элемент И 28 формируют сигйия в списке складывается по ИЛИ с уже нал СТРОБ (фиг. 5, к), сопровождающийимеющимися. Например.при поступлении коды на выходах 20, 21,кодов данных 0000000, 0000001 в блок 4 В блоке 6 при сортировке по воэрастапри записи второго кода заносится код 40 нию, коммутатор 32 подключает к первому00000011, По окончании ввода сигнала из инФормационных входов приоритетногоПРИЕМ сбрасывается и дальнейшая запись шифратора.33 выход младшего разряда рев,блок 4 вновь блокируется.гистра 5, к последнему - выход старшегоТэк, в ячейки блока 4 памяти заносятся разряда, присваивая тем самым младшемупризнаки нахождения в списке в разряды, 45 разряду регистра 5 наивысший приоритет, а,.соответствующие младшим разрядам кодов сумматоры 34 по модулю 2 передают сфорданных, байтов, соответствующих старшим мировэнный шифратором 33 код нэ инфорразрядам данных, . мационный выход блока без изменений.Выводупорядоченногоспискэзадается Например, при коде .10000011 на выходестановкой сигнэла ВЫД(фиг, 5 в), При этом 50 регистра 5 блок 6 формирует код 000. Приустановк йесли упорядочивание ведется повозраста-сортировке по убывани 1 о коммута ор 3нию, сигнал УБ - в состоянии "0", если по присваивает наивысший приоритет старубыванию - в состоянии "1", Есливыдача не шему из разрядов регистра 5. э сумматорысопровождается обнулением памяти. сиг инвертируют сформированный шифранэл ОЧИСТКА - в состоянии "0". 55 тором 33 код. в результате чего при кодеПо установке ВЫД коммутатор 2 под в регистр 5 блок 6 формирует кодключает ко входу дешифратора 3 информа.ционный выход блока 6 шифрэтора, к Дешифратор 3 на том из своих выходов,информационному входу счетчика 7 - входкоторый соответствует коду на выходе 21,11, Поскольку до установки ВЫД регистр 5 устанавливает "1". Сумматоры 8 склэдывают состояния выходов дешифратора 3 и регистра 5. При совпадении "1" на обоих входах соответствующего сумматора 8 он на своем выходе устанавливает "0". В результате код, например, 10000011 на выходе регистра 5 преобразуется на выходах сумматоров 8 в код 10000010, по Т 2 заносится в регистр, по нему блок 6 формирует код младших разрядов новых данных и по очередному Т 1 с выходов 20, 21 поступают новые данные.Процесс выдачи продолжается до обнуления регистра 5, в результате чего блок б выдает сигнал конца, по которому коммутатор 23 блокирует выдачу сигнала СТРОБ и по Т 1 формирует сигнал модификации счетчика (фиг, 5, л). По новому состоянию счетчика из блока 4 выбирается новый байт признаков, который. заносится в регистр 5, поскольку по состоянию "1" выхода запроса блока 6 коммутаторподключает к информационному входу регистра 5 выход блока 4. Если в нововыбранном байте содержатся признаки нахождения в списке, блок б сбрасывает сигнал конца и продолжается процесс сортировки. если нет, счетчик"Вйовь модифицируется и в регистр 5 зано ится следующий байт, При установке счетчика 7 в последнее из воэмокных состояний счетчик 7 выдает сигнал переноса (фиг, 5, м) и после выдачи последующих данных он сбрасывается, По сбросу сигнала переноса взводится триггер 10 (фиг, 5, н) и на выход 22 выдается сигнал КВ, По нему сигнал ВЫД сбрасывается и с выхода 1.11 начинает поступать сигнал сброса, Так осуществляется выдача отсортированного списка с сохранением в памяти признаков нахождения в списке.При необходимости обнуления памяти сигнал ВЫД (фиг, б, в) сопровождается сигналом ОЧИСТКА (фиг, 6, г). По нему коммутатор 9 подключает к информационному входу регистра 5 выход блока 4, а элемент И-ИЛИ 30 разрешает прохокдение. сигналов Т 1 на вход записи блока 4 с задержкой; необходимой для выборки памяти, Выдача отсортированного списка производится аналогично предыдущему режиму, однако дополняется поступлением в блок 4 сигналов записи, в результате чего с каждой выдачей данных (фиг, б, к) .в блоке 4 обнуляется очередной признак (фиг. б, з). При обнулении регистра 5 (фиг. 6, и) блок выдает сигнал запроса (фиг. 6, е), что блокирует запись в память до модификации счетчика (фиг. 6. Ж) и записи в регистр новых признаков. Работа в режиме очистки производится перед введением в устройство нового списка и после включения питания, когда ячейки блока 4 памяти устанавливаются произвольно,Таким образом осуществляется запоминание поступающего в устройство неупорядоченного списка данных и выдачи нормализованного списка дайных в порядке его убывания или возрастания, сопровождаемая либо сохранением в памяти устройства признаков нахождения дан 10 ных в списке. либо их обнулением. Такая возможность позволяет существенно повысить быстродействие ус; ройства при многократной выдаче нормализованного списка.В устройстве-прототипе выдача нормализованного списка -сопровождается обну 15 лением признаков нахождения в списке, в результате чего для повторной выдачи списка необходимо производить повторный ввод неупорядоченного списка, В заяв ляемом же устройстве осуществлена возмокность неоднократной выдачи нормализованного списка, что, сравнительно с прототипом, увеличивает его быстродействие соответственно количеству таких выдач,25 При допущении равенства во времени процессов"ввода и выдачи и хотя бы двукратной . выдаче списка и образуется минимальный выигрыш в быстродействии вдвое,Формула изобретения Устройство для сортировки данных, содержащее блок управления, первый комму 30 татор, дешифратор, блок памяти, регистр, блок шифратора и счетчик, выходы разрядов которого являются информационными выходами первой группы устройства и соединены с адресными входами блока памяти,информационные входы счетчика подключечы к выходам первой группы первого 40 коммутатора, синхровход счетчика соедиуправляющим входом блока шифратора, а вход записи - с вторым выходом блока управления, третий выход которого подключен к входу записи блока памяти, четвертый выход блока управления является выходом соп ровождения данных устройства, а пятый выход подключен к синхровходу регистра, первый и второй тактовые входы блока управления являются первым и вторым тактовы ми входами устройства, вход управления коммутации блока управления подключен к выходу конца работы блока шифратора, вход приема блока управления является входом приема информации устройства, вход разрешения коммутации -нен с первым выходом блока управления, вход управления счетом - с входом задания режима сортировки устройства, с первым входом первой группы информационных 45 входов первого коммутатора и с первымвходом выдачи устройства и подключен к второму управляющему входу блока шифратора и управляющему входу первого коммутатора, информационные входы первой группы которого, кроме первого. соединены с информационными выходами блока шифратора и являются информационными выходами второй группы устройства, информационные входы первой и второйподгрупп первого коммутатора второйгруппы являются соответственно входами младших и старших разрядов данных устройства, а выходы второй группы первого коммутатора соединены с соответствующими входами дешифрэтора, о т л и ч а ю щ ее с я тем, что, с целью повышения быстродействия, в него вверены группа сумматоров по модулю два, второй коммутатор и триггер, выход которого является выходом конца работы устройства, вход установки в единичное состояние подключен к выходу .переноса счетчика. а вход сброса соединенс входом сброса регистра и шестым выходом блока управления, вход "Очйстка" кото 5 рого является входом "Очистка" устройства.а седьмой выход соединен с управляющимвходом второго коммутатора, выходы которого подключены к информационным входам регистра, йнформационные входы10 первой группы - . к выходам блока памяти,информацйонные входы второй группы соединенн ы с соответствующими и нформаци- .онйыми входами блока памяти и выходамисоответствующих сумматоров по модулю:15 два группы, первые входы которых подключены к соответствующим выходамдешифратора, а вторые входы - к соответствующим выходам регистра и соответствующим информационным входам блока20 шифратора,17849 Б 7 фф ОИ акто ректор О. Кравцов Производственно-издательский комбинат "Патент город, ул. Гагарин ВЬ О Заказ 4365 ВНИИПИ Составитель И. боже Техред М.Моргентал Тираж . Подписноедарственного комитета по изобретениям и открытиям при ГКНТ СС 113035, Москва, Ж, Раушская наб 4/5