Устройство для сортировки данных Советский патент 1992 года по МПК G06F7/06 

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

Известно устройство, содержащее блоки управления и памяти, счетчик, элементы 2И. В режиме ввода данные списка являются адресом, по которому в память заносится признак нахождения в списке. В режиме вывода при последовательном считывании из памяти элементы 2И передают на выход устройства те состояния счетчика, которые соответствуют считанному признаку нахождения в списке Быстродействие устройства ограничивается необходимостью опроса в

режиме выдачи всех ячеек памяти независимо от количества и значения данных, составляющих список 1.

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

осуществляет приоритетный опрос разрядов выбранного байта по возрастанию либо по убыванию. При выдаче данных соответствующий им признак нахождения в списке из блока памяти стирается, в результате чего для повторной выдачи списка необходимо произВДдТггь повторную операцию ввода неупо яЦоЧеннбТо списка, что снижает быстродействие устройства 2.

Цель изобретения j повышение быстродействия устройства.

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

информационному входу блока памяти и выходам сумматоров, первые входы которых подключены к соответствующим выходам дешифратора, а вторые входы - к выходу

регистра к Информационному входу блока шифратора.

Новыми существенными признаками заявляемого устройства являются введенные группы сумматоров по модулю два, вто0 рого коммутатора, триггера, четвертого управляющего входа и связей, отражающих новую организацию взаимодействия между элементами устройства.

Новая совокупность элементов позво5 ляет в процессе выдачи упорядоченного списка либо сохранять в памяти признаки нахождения в списке, либо стирать их, что создает возможность многократной выдачи отсортированного списка, что позволяет в

0 режиме выдачи при повторной выдаче списка повысить быстродействие устройства как минимум вдвое.

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

0 очистки памяти.

Устройство содержит (фиг. 1) блок 1 уп- равления, первый коммутатор 2, дешифратор 3, блок 4 памяти, регистр 5, блок 6 шифратора, счетчик 7, группу сумматоров 8

5 по модулю два. второй коммутатор 9, триггер 10, входы задания сортировки 11, приема 12, выдачи 13 и очистки 14, первый 15 и второй 16 тактирующие входы, входы младших 17 и старших 18 разрядов данных,

0 выход 19 сопровождения данных, информационные выходы первой 20 и второй 21 групп, выход 22 конца работы.

Первый 1.1 и второй 1.2 выходы блока 1 управления подключены соответственно ко

5 входам синхронизации и установки счетчика 7, третий 1.3 выход соединен со входом записи блока 4 памяти, четвертый 1,4 - с выходом 19 сопровождения данных устройства, пятый 1.5 - с синхровходом регистра

0 5, шестой 1.11 - со входом сброса регистра 5 и триггера 10, седьмой 1.13 - со входом управления второго коммутатора 9, первый 1.6 и второй 1.7 тактирующие подключены соответственно к первому 15 и второму 16

5 актирующим входам устройства, вход 1.8 управления коммутации соединен с выходом конца работы блока 6 шифратора, вход приема 1.9-со входом 12 приема устройства, вхбд выдачи 1.10 - с входом 13 выдачи устройства, входом управления первого

коммутатора 2 и вторым входом управления блока 6 шифратора, вход очистки 1.12 - с входом 14 Очистка устройства.

Первый вход первой группы информационных входов первого коммутатора 2 подключен к входу 11 задания режима сортировки устройства, входу управления счетом счетчика 7 и первому входу управления блока б шифратора, второй вход- к информационному выходу блока 6 шифратора и информационному выходу 21 второй группы устройства, первый и второй входы второй группы подключены соответственно ко входам младших 17 и старших 18 разрядов данных устройства, первый выход соединен с информационным входом счетчика 7, а второй - со входом дешифратора 3, выходы которого подключены к первым входам соответствующих сумматоров 8 по модулю Два, выходы которых соединены со вторым информационным входом второго коммутатора 9 и с информационным входом блока 4 памяти, адресный вход которого подключен к информационному выходу счетчика 7 и информационному выходу 20 первой группы устройства, а выход - к первому информационному входу коммутатора

9,выход которого соединен с информационным входом регистра 5, вход которого подключен ко вторым входам соответствующих сумматоров 8 и к информационному входу блока 6 шифратора В ыход переноса счетчика 7 подключен ко входу установки триггера

10,выход которого соединен с выходом 22 конца работы устройства

Блок 1 управления содержит (фиг. 2) коммутатор 23, триггер 24, элемент задержки 25 и элементы ИЛИ 26, 27. И 28 и И-ИЛИ 29, 3Q, 31. По выходу 1 1 блока 1 управления поступает сигнал синхронизации счетчика 7, по выходу 1.2 -сигнал записи в счетчик, записи в блок 4 памяти, по выходу 1 4 идентификатор СТРОБ поступает на выход 19 устройства, по выходу 1 5 - сигнал записи в регистр 5, по выходу 1.11- сброс регистра 5 итриггера 10, по выходу 1 13 -управление коммутатора 9. По входу 1 8 поступает сигнал конца работы блока 6 шифратора

Блок 6 шифратора содержит (фиг. 3) коммутатор 32, приоритетный шифратор 33 и группу сумматоров 34 по модулю два. Входы первой группы информационных входов коммутатора 32 объединены с первого по последний со входами второй группы его информационных входов соответственно, с последнего по первый, и являются информационным входом блока Первые входы сумматоров 34 по модулю два объединены и подключены ко входу управления коммутатора 32, который является первым входом

управления блока. Вход управления шифратора 33 является вторым входом управленич блока, выход запроса шифратора 33 - выход конца работы блока, а выходы сумматоров 5 34, которые выполняют функцию управляемых интервалов, - информационные выходы блока.

На фиг. 4 обозначены а - синхросигналы Т1 на входе 15 устройства: б - синхроим0 пульсыТ2 на входе 16 устройства; в-сигнал ПРИЕМ на входе 12; г - состояние счетчика 7; д - младшие разряды поступающих данных на входе 17; е - состояние регистра 5; ж - состояние выхода блока 4/памяти.

5 На фиг. 5 обозначены а, б - сигналы соответственно Т1 и Т2; в - сигнал ВЫД на входе 13 устройства; г - сигнал установки счетчика 7 на выходе 1.2 блока 1; д - выход конца работы блока б шифратора; е - состо0 яние счетчика 7; ж - выход блока 4 памяти- з - состояние регистра 5; и - информационный вход блока 6; к - сигнал СТРОБ на выходе 19; л - синхросигналы счетчика 7 на выходе 1 1; м - выход переноса счетчика 7

5 н - сигнал конца работы на выходе 22.

На фиг. 6 обозначены а, б - сигналы Т1 и Т2, в - сигнал ВЫД на входе 13; г-сигнал ОЧИСТКА на входе 14; д - сигнал установки на выходе 1.2; е - выход конца работы блока

0 б; ж - состояние счетчика 7; з - выход блока 4; и - состояние регистра 5; к - информационный выход блока 6.

Реализованный вариант заявляемого устройства предназначен для упорядочива5 ния списка данных числом до 128. Блок 1 управления выполнен на микросхемах серии К555, коммутаторы 2,9 - на К555КП11, дешифратор 3 - на К555ИД7. блок 4 памяти представляет собой матрицу 8x16, реализо0 ванную на основе микросхем, многоразрядных, статической памяти К531РУ8, регистр 5 выполнен на К555ТМ8, счетчик 7 - на К564ИЕ11, группа сумматоров 8 - на К555ЛП5, приоритетный шифратор 33 блока

5 6 - на основе К555ИВ1.

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

Перед началом ввода списка блок 4 памяти обнулен. Управляющие сигналы на

0 входах 11-14 - в состоянии О, На входы 15, 16 поступают сигналы Т1, Т2. Соответственно в О установлен выход конца работы блоо 6 шифратора, а в блоке 1 управления в О установлен триггер 24, элемент ИЛИ 26 генериру5 ет сигнал сброса регистра 5 и триггера 10, выдача же прочих управляющих сигналов блокируется. Управляющие и информационные сигналы на входах устройства устанавливаются в промежутках между поступлением сигналов Т2 Т1 (фиг. 4 а 6}

Режим ввода списка задается установкой в 1 сигнала ПРИЕМ (фиг. 4в). По информационным входам начинают поступать данные - по входу 17 - младшие, по входу 18 - старшие разряды. Коммутатор 2 подключает вход 17 ко входу дешифратора 3, вход 18 - к информационному входу счетчика 7. Сигнал сброса на выходе 1.1 снимается. По уровню 1 на выходе элемента ИЛИ 27 блока 1 коммутатор 9 подключает выход блока 4 к информационному входу регистра 5.

ПоТ1 (фиг. 4а) элемент И-ИЛИ 29 формирует сигнал установки счетчика 7 в состояние, соответствующее значению старших разрядов поступающих данных (фиг. 4г). По адресу, заданному состоянием счетчика, выбирается бло к 4 памяти. Дешифратор 3 устанавливает на том входе группы сумматоров 8 по модулю два, который соответствует коду на входе 17, уровень 1. Например, при коде 000 на входе 17 на выходе дешифратора устанавливается код 00000001. По Т1 элементы задержки 25 и И-ИЛИ 31 за время, необходимое для выборки памяти, формируют сигнал записи в регистр 5 состояния выхода блока 4 (фиг. 4е). В сумматорах 8 складывается по ИЛИ код на выходах дешифратора 3 и регистра 5. ПоТ2 (фиг. 46) элемент И-ИЛИ 30формирует сигнал записи состояния на выходах сумматоров 8 в блок 4 (фиг. 4ж). С поступлением новых данных блок 4 выбирается по новому адресу и в него заносится новый код. При этом, если блок 4 выбирается по уже поступавшему адресу, новый признак нахождения в списке складывается по ИЛИ с уже имеющимися. Например, при поступлении кодов данных 0000000, 0000001 в блок 4 при записи второго кода заносится код 00000011, По окончании вбода сигнала ПРИЕМ сбрасывается и дальнейшая запись в блок 4 вновь блокируется.

Так, в ячейки блока 4 памяти заносятся признаки нахождения в списке в разряды, соответствующие младшим разрядам кодов данных, байтов, соответствующих старшим разрядам данных.

Вывод упорядоченного списка задается установкой сигнала ВЫД (фиг. 5в). При этом если упорядочивание ведется по возрастанию, сигнал УБ - в состоянии О, если по убыванию- в состоянии 1, Если выдача не сопровождается обнулением памяти, сигнал ОЧИСТКА - в состоянии О.

По установке ВЫД коммутатор 2 подключает ко входу дешифратора 3 информационный блока 6 шифратора, к информационному входу счетчика 7 - вход 11. Поскольку до установки ВЫД регистр 5

был обнулен, выход запроса блока 6 устанавливается в 1 (фиг. 5, д). По совпадению уровней 1 сигнала ВЫД и инверсного выхода триггера 24 в блоке 1 элемент И-ИЛИ

29 формирует сигнал установки счетчика 7 (фиг. 5, г). При сортировке по возрастанию счетчик 7 устанавливается в нулевое состояние и начинает работать в режиме прямого счета (фиг. 5, е), при сортировке по убыва0 нию счетчик устанавливается в единичное значение и работает в режиме инверсного счета. По отрицательному фронту Т2 (фиг. 5, б)триггер 24 устанавливается , и сигнал установки счетчика снимается с выхода 1.2,

5 а элемент И 28 перестает блокировать прохождение сигнала СТРОБ.

По состоянию счетчика из блока 4 памяти выбирается байт признаков нахождения в списке, например по адресу 0000 код

0 10000011 (фиг. 5, ж).

Поскольку при этом выход конца работы блока 6 - в состоянии 1, элемент ИЛИ 27 передает 1 на управляющий вход коммутатора 9, который подключает выход блока

5 4 памяти к информационному входу регистра 5 и по Т2 в регистр заносится выбранный байт признаков (фиг, 5, з), при наличии в котором хотя бы одной 1 сигнал конца блока б сбрасывается, и коммутатор

0 9 подключает к регистру 5 выходы сумматоров 8.

В зависимости от направления сортировки блок 6 формирует код, соответствующий занесенному в регистр 5 байту

5 признаков (фиг. 5, и) и no T1 (фиг. 5. а) коммутатор 23 и элемент И 28 формируют сигнал СТРОБ (фиг. 5, к), сопровождающий коды на выходах 20, 21.

В блоке 6 при сортировке по возраста0 нию коммутатор 32 подключает к первому из информационных входов приоритетного шифратора 33 выход младшего разряда регистра 5, к последнему - выход старшего разряда, присваивая тем самым младшему

5 разряду регистра 5 наивысший приоритет, а сумматоры 34 по модулю 2 передают сформированный шифратором 33 код на информационный выход блока без изменений. Например, при коде 10000011 на выходе

0 регистра 5 блок 6 формирует код 000. При сортировке по убыванию коммутатор 32 присваивает наивысший приоритет старшему из разрядов регистра 5. з сумматоры 34 инвертируют сформированный шифрэ5 тором 33 код. в результате чего при коде 10000011 в регистр 5 блок 6 формирует код 111.

Дешифратор 3 на том из своих выходов, который соответствует коду на выходе 21, устанавливает 1. Сумматоры 8 складывают состояния выходов дешифратора 3 и регистра 5. При совпадении 1 на обоих входах соответствующего сумматора 8 он на своем выходе устанавливает О. В результате код, например, 10000011 на выходе регистра 5 преобразуется на выходах сумматоров 8 в код 10000010, по Т2 заносится в регистр, по нему блок 6 формирует код младших разрядов новых данных и по очередному Т1 с выходов 20, 21 поступают новые данные.

Процесс выдачи продолжается до обнуления регистра 5, в результате чего блок 6 выдает сигнал конца, по которому коммутатор 23 блокирует выдачу сигнала СТРОБ и по И формирует сигнал модификации счетчика (фиг, 5, л). По новому состоянию счетчика из блока 4 выбирается новый байт признаков, который заносится в регистр 5, поскольку по состоянию 1 выхода запроса блока б коммутатор 9 подключает к информационному входу регистра 5 выход блока 4. Если в нововыбранном байте содержатся признаки нахождения в списке, блок 6 сбрасывает сигнал конца и продолжается процесс сортировки, если нет, счетчик ёновь модифицируется и в регистр 5 заносится следующий байт. При установке счетчика 7 в последнее из возможных состояний счетчик 7 выдает сигнал переноса (фиг. 5, м) и после выдачи последующих данных он сбрасывается. По сбросу сигнала переноса взводится триггер 10 (фиг. 5, н) и на выход 22 выдается сигнал КВ. По нему сигнал ВЫД сбрасывается и с выхода 1.11 начинает поступать сигнал сброса Так осуществляется выдача отсортированного списка с сохранением в памяти признаков нахождения в списке.

При необходимости обнуления памяти сигнал ВЫД (фиг 6, в) сопровождается сигналом ОЧИСТКА (фиг б, г). По нему коммутатор 9 подключает к информационному входу регистра 5 выход блока 4, а элемент И-ИЛИ 30 разрешает прохождение сигналов Т1 на вход записи блока 4 с задержкой, необходимой для выборки памяти. Выдача отсортированного списка производится аналогично предыдущему режиму, однако дополняется поступлением в блок 4 сигналов записи, в результате чего с каждой выдачей данных (фиг. б. к) в блоке 4 обнуляется очередной признак (фиг. 6, з). При обнулении регистра 5 (фиг. 6. и) блок выдает сигнал запроса (фиг. 6, е), что блокирует запись в память до модификации счетчика (фиг. 6. ж) и записи в регистр новых признаков. Работа в режиме очистки производится перед введением в устройство нового списка и после включения питания,

когда ячейки блока 4 памяти устанавливаются произвольно.

Таким образом осуществляется запоминание поступающего в устройство неупорп5 доченного списка данных и выдачи нормализованного списка данных в порядке его убывания или возрастания, сопровождаемая либо сохранением в памяти устройства признаков нахождения дан0 ных в списке, либо их обнулением. Такая возможность позволяет существенно повысить быстродействие усгройства при многократной выдаче нормализованного списка. В устройстве-прототипе выдача норма5 лизованного списка сопро вождается обнулением признаков нахождения в списке, в результате чего для повторной выдачи списка необходимо производить повторный ввод неупорядоченного списка. В залв0 ляемом же устройстве осуществлена возможность неоднократной выдачи нормализованного списка, что, сравнительно с прототипом, увеличивает его быстродействие соответственно количеству таких выдач.

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

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

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

5 которого являются информационными выходами первой группы устройства и соединены с адресными входами блока памяти, информационные входы счетчика подключены к выходам первой группы первого

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

5 входов первого коммутатора и с первым управляющим входом блока шифратора, а вход записи - с вторым выходом блока управления, третий выход которого подключен к входу записи блока памяти, четвертый

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

единичное состояние подключен к выходу переноса счетчика, а вход сброса соединен с входом сброса регистра и шестым выходом блока управления, вход Очистка которого является входом Очистка устройства, а седьмой выход соединен с управляющим входом второго коммутатора, выходы которого подключены к информационным входам регистра, информационные входы первой группы - к выходам блока памяти, информационные входы второй группы соединены с соответствующими информационными входами блока памяти и выходами соответствующих сумматоров по модулю два группы, первые входы которых подключены к соответствующим выходам дешифратора, а вторые входы - к соответствующим выходам регистра и соответствующим информационным входам блока шифратора.

Изобретение относится к вычислительной технике и может быть использовано в системах обработки информации. Цель изобретения - повышение быстродействия устройства. Устройство содержит блок управления, первый коммутатор, дешифратор, блок памяти, регистр, блок шифратора, счетчик, группу сумматоров по модулю два, второй коммутатор, триггер, входы задания режима сортировки, приема, выдачи и очибтки, первый и второй тактирующие входы, входы младших и старших разрядов данных, выход сопровождения данных, информационные выходы первой и второй групп, выход конца работы. В устройство вводится неупорядоченный список. Там он запоминается по значениям данных, входящих в список. Затем производится побайтный опрос памяти и выдача данных, отмеченных признаком нахождения в списке. Блок шифратора осуществляв приоритетный .опрос разрядов выбранного байта по возрастанию или убыванию. Поставленная цель достигается введением группы сумматоров по модулю 2. второго коммутатора, триггера и новых связей что позволяет в процессе выдачи упорядоченного списка сохранять в памяти признаки нахождения в списке или стирать их, создавая тем самым возможность многократной выдачи отсортированного списка и повышая таким образом быстродействие устройства в режиме выдачи при повторной выдаче списка. 6 ил (Л С

Шг.1

Шиг.2

ear

IB

05

«er CO

r«o «э

ev t 5

U t C м ( Q,

)

Tt

тг

выл

OV

L

Ј ст us по

CD

..:|00л

ШтП

0...00 I У.. UfOl1 пп Q...OQ

77т LJSLTW

ш

m

ШтП По/Г

ш

Фиг,$

m