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

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

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

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

Устройство содержит (фиг. 1) коммутатор 1, преобразователь 2 кода данных, регистр 3, блок А памяти, управляемый шифратор 5, преобразователь 6 кода данных, регистр 7, управляемый шифратор 8, зходы 9-13, информационные выходы 14 и 15, выход 16 конца ввода и вход 17 установки.

По входу 9 поступает сигнал задания режима сортировки по убыванию, по входу 10 - сигнал задания приема списка. По входам 11 и 12 поступают синхросигналы Т1 и Т2 соответственно. На вход 13 поступает код данных списка D. На выходы 14 и 15 поступают соответственно младшие (ОМл) и старшие (ОСт) коды данных упорядоченного списка, на выход 16 - сигнал конца выдачи, а на вход 17 - сигнал начальной установки,

Преобразователи 2 и 6 кодов данных содержат (фиг. 2) дешифратор 18, группы элементов ИЛИ 19 и И 20 и коммутатор 21. Управляемые шифраторы 5 и 8 содержат (фиг. 3) коммутатор 22, приоритетный шифратор 23 и группу сумматоров 24 по модулю два.

На фиг. 4 обозначены: а, б - синхроимпульсы Т1 и Т2 соответственно;

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

д, е - первый и второй разряды регистра 7;

ж-и - соответственно первый, второй и последний разряды выхода блока 4 памяти;

к-м - первый, второй и последний выходы преобразователя 2;

н-п - первый, второй и последний разряды регистра 3;

На фиг, 5 обозначены;

а, б - синхроимпульсы Т1 и Т2:

-в - сигнал приема списка на входе 10;

г, д- первый и второй разряды регистра 7; е - информационный выход шифратора 8; ж - выход конца работы шифратора 8; з, и - первый и второй выходы преобразователя 6;

к-м - выходы блока 4 памяти;

н - информационный выход шифратора 5;

о - выход конца работы шифратора 5;

0 п-с - выходы преобразователя 2; т-ф - выходы регистра 3. Предлагаемое устройство предназначено для упорядочивания списка из максимум 27 данных разрядностью 7. В качестве

5 старших принято 4 разряда. Блок 4 памяти представляет собой матрицу 8 х 16, реализованную на основе К531РУ8. Первый преобразователь 2 выполнен как преобразователь трехразрядного двоичного в

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

5 как преобразователи 4-16 и 16-4. Устройство реализовано на основе серии К555, в частности коммутаторы 1,21 - на К555КП11, регистры 3, 7 - на К555ТМ8, дешифратор 18 - на К555ИД7, шифратор 23 - на К555ИВ1,

0 сумматоры 24 - на К555ЛП5.

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

Режим ввода списка задается установкой единичного сигнала на входе 10 и по5 ступлением синхросигналов Т1 (фиг. 4а) и Т2 (фиг, 46). В промежутках между сигналами Т2 и Т1 поступают коды данных (фиг. 4, в, г) по входу 13, которые коммутатор 1 подключает на свой выход.

0 В преобразователе 6 дешифратор 18 преобразует значение старших разрядов данных в унитарный код, который элементами ИЛИ 19 складывается в предыдущим состоянием регистра 7, и это новое значе5 ние через коммутатор 21 поступает на информационные входы регистра 7, куда записывается по заднему фронту J2 (фиг. 4, д, е). При этом по 1 на своем втором управляющем входе шифратор 5 поддер0 живает 1 на своем выходе конца работы, подключенном к входу разрешения записи регистра 7. Так, в регистре 7 устанавливаются признаки нахождения в списке, соответствующие старшим разрядам поступающих

5 кодов данных.

Из блока 4 по состоянию старших разрядов данных выбирается соответствующий байт признаков (фиг. 4 ж-и), В преобразователе 2 этот байт складывается по ИЛИ с унитарным кодом, сформированным дешифратором 18 преобразователя 2 из младших разрядов кода данных (фиг, 4, к-м) и через коммутатор 21 передается на информационный вход регистра 3, куда и заносится по переднему фронту Т1 (фиг. 4, н-п). Затем вновь сформированный байт признаков по Т2 заносится в блок 4 памяти. Так,в информационных байтах блока 4 памяти в соответствии со сначениями младших раз- рядов данных упорядочиваемого списка размещаются признаки нахождения в списке, в сами эти байты адресуются в соответствии со значениями старших разрядов данных упорядочиваемого списка.

Выдача упорядочиваемого списка задается сбросом в О сигнала ПР (фиг. 5, в). При этом информационный выход шифтора 5, находившийся по единичному значению сигнала ПР в состоянии все единицы, переходит в состояние, соответствующее состоянию выхода блока 4 (фиг. 5, н). Если на выходе блока 4 присутствует хотя бы один признак присутствия в списке, выход конца работы шифтора 5 сбрасывается (фиг. 5, о) и запись в регистр 7 запрещается.

Сортировка списка по возрастанию задается уровнем О на входе 9. По нему в управляемых шифраторах 5 и 8 коммутатор 22 передает входной код на информационные входы приоритетного шифратора 23, который на своих информационных выходах формирует код, соответствующий признаку, которому присвоен наибольший приоритет. Сумматоры 24 при наличии О на своих первых входах передают этот код на информационный выход управляемого шифратора. Сортировка по убыванию задается установкой 1 на входе 9. По ней коммутатор 22 передает младший разряд на своем входе на старший разряд своего выхода, и наоборот. Например, код 10000011 на входе коммутатора 22 передается на вход шифратора 23 как код 11000001. Тем самым признаку с наименьшим приоритетом присваивается наибольший приоритет. По уровню 1 на своих первых входах сумматоры 24 инвертируют сформированный шифратором 23 код. Тем самым при изменении приоритетов признаков коды, присвоенные этим признакам, сохраняются. На фиг. 5 отображена сортировка по возрастанию.

На информационном выходе шифратора 8 присутствует код, соответствующий тому из признаков, хранящихся в регистре 7. которому присвоен наивысший приоритет. Например, уровню 1, в первом разряде регистра 7 (фиг. 5, г) соответствует код 0000 (фиг. 5, е). Этот код коммутатор 1 передает на вход дешифратора 18 преобразователя 6, в результате чего соответствующий элемент И 20 блокирует передачу признака на выход коммутатора 21 (фиг. 5, з).

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

По переднему фронту Т1 (фиг. 5, а) модифицированный байт признаков младших разрядов заносится в регистр 3 (фиг. 5, т-ф). Кроме того, поТ1 с информационных

5 выходов устройства принимается код отсортированных данных: с выхода 14 - младшие разряды, с выхода 15 - старшие. По Т2 (фиг. 5, б) модифицируется байт признаков блока 4.

0 После того.-как все признаки на выходе блока 4 оказываются сброшенными, на информационном выходе шифратора 5 устанавливается единичный код, а на его выходе запроса - уровень 1. По нему разрешает5 ся запись задним фронтом Т2 модифицированного байта признаков старших разрядов в регистр 7. Код на выходе шифратора 8 изменяется. Например, после сброса признака в первом разряде регист0 ра 7 по 1 в его втором разряде (фиг. 5, д) шифратор 8 формирует код 0001. По нему из блока 4 выбирается следующий байт признаков, и процесс выдачи отсортированного списка продолжается.

5 После того, как из блока 4 будет выбран байт, соответствующий последней из Г, в регистре 7, и все его разряды будут обнулены, по заднему фронту 12 последняя из 1 регистра 7 сбрасывается. Информаци-0 онный выход шифратора 8 устанавливается в состояние 1111. На выходе конца работы шифратора 8 устанавливается 1 (фиг. 5, ж), которая передается на выход 16 как сигнал конца выдачи. Выдача сигналов

5 Т1 и Т2 прекращается. Все разряды регистров 3 и 7 и ячейки блока 4 обнулены, и устройство готово к приему очередного списка.

При включении питания ячейки памяти

0 устанавливаются произвольно. Для их начального обнуления проводится предварительная операция вывода, для чего на вход 17 подается сигнал начальной установки регистра 7 в единичное состояние. Затем

5 на входе ТО устанавливается О, а на входы 11 и 12 начинают поступать Т1. В про-, цессе выдачи происходит поочередная выборка всех байтов блока 4 и их обнуление. Окончание обнуления определяется по сигналу KB на выходе 16.

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

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

Изобретение относится к вычислительной технике и может быть использовано в системах обработки информации. Цель изобретения - повышение быстродействия. Устройство содержит коммутатор 1, блок 4 памяти, преобразователи 2 и 6 кода данных, регистры 3 и 7, управляемые шифраторы 5 и 8 В устройство вводится неупорядоченный список Признак нахождения в списке запоминается в байте признаков по адресу, соответствующему младшим разрядам кода данных, а сам байт запоминается по адресу, соответствующему старшим разрядам кода данных. Дополнительно по старшим разрядам кода данных запоминается признакбайта, содержащего признак нахождения в списке Затем производится приоритетная выборка байтов, содержащих признаки нахождения в списке и в соответствии с их значениями, приоритетный опрос разрядов этих байтов. Управляемые шифраторы позволяют вести выдачу упорядоченного списка как по возрастанию, так и по убыванию 5 ил.

Фиг,1

V

ФагЗ

Фиг.4

rfl

О ЕМЛ

п FpiftlpFvflt-S FMjfl- mRGfvi- yR&wl: qpRWФиг.5