УСТРОЙСТВО СОРТИРОВКИ ИНФОРМАЦИИ Российский патент 1995 года по МПК G06F7/08 

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

Известны устройства для сортировки чисел [1,2] позволяющие упорядочить массив чисел в возрастающем и убывающем порядке.

В качестве прототипа выбрано устройство сортировки информации [3] позволяющее упорядочить массивы данных.

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

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

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

Решение задачи достигается тем, что в устройство сортировки информации, содержащее два стековых блока памяти, элемент сравнения, блок управления, введены входной и выходной каналы, блок оперативной памяти, блок коммутации и идентификации, причем с первого по пятый управляющие выходы блока управления соединены соответственно с первым по пятый управляющими входами блока оперативной памяти, информационный вход которого соединен с входным каналом, управляющий выход соединен с четвертым управляющим входом блока управления, информационный выход соединен с первым информационным входом элемента сравнения и вторым информационным входом блока коммутации и идентификации, управляющий выход последнего соединен с четырнадцатым управляющим входом блока управления, с первого по третий управляющие входы соединены соответственно с десятого по двенадцатый управляющими выходами последнего, второй информационный выход соединен с выходным каналом, первый информационный выход соединен с информационным входом второго стекового блока памяти, первый и второй управляющие входы последнего соединены соответственно с шестым и седьмым управляющими выходами блока управления, первый и второй управляющие выходы соединены соот- ветственно с десятым и одиннадцатым управляющими входами последнего, информационный выход соединен с информационным входом первого стекового блока памяти, первый и второй управляющие входы которого соединены соответственно с восьмым и девятым управляющими выходами блока управления, первый и второй управляющие выходы соединены соответственно с двенадцатым и тринадцатым управляющими входами последнего, информационный выход соединен с первым информационным входом блока коммутации и идентификации и с вторым информационным входом элемента сравнения, с первого по третий управляющие выходы последнего соединены соответственно с управляющими входами с пятого по седьмой, блока управления, с первого по третий управляющие входы блока управления "ЗАГР", "ЧТПР", "ЧТОБ", а также восьмой и девятый управляющие входы "СБРОС" и "ПУСК" последнего являются внешними входами устройства, тринадцатый и четырнадцатый управляющие выходы "ГТ" и "СИН" блока управления являются внешними выходами устройства.

Входной канал (ВХК) служит для приема данных, блок оперативной памяти (БОП) для временного хранения принятого слова (числа).

Элемент сравнения (ЭС) сравнивает символы принятого слова (числа) и уже упорядоченных слов (чисел).

Стековые блоки памяти 1 и 2 (СБП1 и СБП2) служат для хранения части отсортированного массива и организации сортировки.

Блок коммутации и идентификации (БКиИ) служит для коммутации информации с различных источников на информационный вход блока СБП2, коммутации информационного выхода блока СБП1 на выходной канал, а также для определения границ слоев упорядоченного массива.

Выходной канал (ВЫХК) служит для выдачи данных.

Блок управления (БУ) управляет другими блоками устройства.

Теория нормальных алгоритмов универсальна по отношению к любым алгоритмическим схемам. Известны алгоритмы, позволяющие упорядочивать слова из массива, например, по признаку алфавитного порядка. Известны универсальные устройства для реализации формул подстановок в виде алгорифмов Маркова (1). Под алгорифмом Маркова понимается конечная последовательность формул вида: S ->> T, где S образец, Т подстановка, S и T произвольные слова в фиксированном алфавите. Работа формулы заключается в обнаружении в слове фрагмента, совпадающего с образцом, и замене обнаруженного фрагмента на слово-подстановку. Следовательно, когда обрабатываемое слово представлено в виде:
Р R₁ S R₂, где знак графического равенства; R₁, R₂ любые слова в фиксированном алфавите, результат работы формулы имеет вид: РR₁ T R₂.

Обнаружение фрагмента, совпадающего с образцом осуществляется слева направо по обрабатываемому слову.

Упорядочение (сортировка) слов в теории нормальных алгорифмов занимает особое место, поскольку относится к труднореализуемым задачам, в которых используются формулы (продукции), содержащие образцы с заданными в их структуре операциями. В данном случае речь идет об операции компарации на "больше", "меньше" и "равно". Подстановка в формулах "S ->> T" также имеет свою специфику и семантически не совпадает с обрабатываемым словом, а представляет собой вспомогательное служебное слово, указывающее позицию слова среди других слов в заданном правиле упорядочения.

В основу работы предлагаемого устройства сортировки информации положен модифицированный алгоритм, который содержит образец и подстановку с указанными выше особенностями. Устройство сортировки информации реализует формулы следующего вида:
S₁ ⊗ S₂ ->> T₁/T₂ (1) где S₁ и S₂ компаранды образца; ⊗- символ, обозначающий операцию компарации на "больше", "меньше" и "равно", а также сопоставление длины компарандов; Т₁ указатель позиции в частично упорядоченном массиве одного из компарандов в зависимости от результата компарации или сопоставления длин слов; Т₂ указатель следующего (текущего) компаранда или правила построения образца по результатам сравнения слов; /, разделители в форме служебных символов, не входящих в основной алфавит.

В предлагаемом устройстве смысл фрагмента подстановки Т₂заключается в приеме очередного символа с входного канала.

Формула вида (1) задает рекурсивную реализацию процесса упорядочения.

На фиг.1 изображена структурная схема устройства сортировки информации; на фиг.2 схема блока оперативной памяти; на фиг.3 схема элемента сравнения; на фиг.4 схема СБП2; на фиг.5 схема СБП1; на фиг.6 схема блока коммутации и идентификации; на фиг.7 и 8 содержательная ГСА работы блока управления; на фиг.9 размеченная ГСА работы блока управления.

Устройство сортировки информации (фиг.1) содержит входной канал 1, блок 2 оперативной памяти, элемент 3 сравнения, стековый блок 4 памяти (СБП2), стековый блок 5 памяти (СБП1), блок 6 коммутации и идентификации, выходной канал 7, блок 8 управления.

Для описания алгоритма работы блока 8 управления используются следующие идентификаторы:
1. ЗАГР сигнал записи в устройство.

2. ЧТПР сигнал выдачи устройством упорядоченного массива в возрастающем порядке.

3. ЧТОБ сигнал выдачи устройством упорядоченного массива в убывающем порядке.

4. ОБСЧ сигнал обнуления, поступающий на вход счетчика блока БОП.

5. ИНСЧ сигнал инкрементации содержимого счетчика блока БОП.

6. ЗПРГ сигнал записи в регистр РГ блока БОП информации из счетчика СЧ блока БОП.

7. ЗПОЗУ сигнал записи/не чтения ОЗУ блока БОП.

8. ВК1 сигнал выбора кристалла ОЗУ блока БОП (инверсный).

9. КС признак конца слова, находящегося в блоке БОП.

10. БОЛЬШЕ признак того, что символ И2 больше символа И3.

11. РАВНО признак того, что символ И2 равен символу И3.

12. МЕНЬШЕ признак того, что символ И2 меньше символа И3.

13. СБРОС сигнал сброса устройства.

14. ПУСК сигнал пуска устройства.

15. ЗПС2 сигнал записи в стек блока СБП2.

16. ЧТС2 сигнал чтения из стека блока СБП2.

17. С2ПН признак того, что стек блока СБП2 полон.

18. С2ПТ признак того, что стек блока СБП2 пуст.

19. ЗПС1 сигнал записи в стек блока СБП1.

20. ЧТС1 сигнал чтения из стека блока СБП1.

21. С1ПН признак того, что стек блока СБП1 полон.

22. С1ПТ признак того, что стек блока СБП1 пуст.

23. ГС признак границы между словами упорядоченного массива.

24. А1 адрес 1, подаваемый на вход коммутатора КМ блока БКиИ.

25. А2 адрес 2, подаваемый на вход коммутатора КМ блока БКиИ.

26. РВ сигнал разрешения выдачи информации на выходной канал.

27. ГТ сигнал готовности устройства.

28. СИН внешний выходной синхронизирующий сигнал.

29. И1 входные данные ОЗУ блока БОП.

30. И2 выходные данные ОЗУ блока БОП.

31. И3 выходные данные стека блока СБП1.

32. И4 выходные данные стека блока СБП2.

33. И5 выходные данные коммутатора КМ блока БКиИ.

34. И6 выходные данные шинного формирователя ШФ блока БКиИ.

Работа алгоритма управления устройства.

Содержательная ГСА управления приведена на фиг.7 и отражает работу блока управления (фиг.1).

По сигналу "СБРОС" (блок 2 граф-схемы алгоритма) происходит сброс информации, хранящейся в стеках блоков СБП1 и СБП2, по командам "ЧТС2:1" и "ЧТС1: 1" (блок 4 ГСА) до тех пор, пока стеки не станут пусты и не установятся признаки "С1ПТ=1" и "С2ПТ=1" (блок 3 ГСА) (фиг.7).

По сигналу "ПУСК" (блок 5 ГСА) осуществляется переход на блок 6 ГСА, иначе на блок 5 ГСА.

По сигналу "ЧТОБ" (блок 6 ГСА) осуществляется переход на блок 63 алгоритма. По сигналу "ЧТПР" (блок 7 ГСА) осуществляется переход на блок 58 ГСА.

По сигналу "ЗАГР" (блок 8 ГСА) происходит загрузка входного слова в БОП (фиг.1), иначе осуществляется переход на блок 6 ГСА.

В блоке 9 ГСА по команде "ОБСЧ:1" обнуляется счетчик (СЧ) блока БОП (фиг. 2). До тех пор, пока не будет снят сигнал "ЗАГР" (блок 10 ГСА), по команде "ЗПОЗУ:1" происходит запись входного символа в ОЗУ по адресу, хранящемуся в счетчике СЧ (фиг.2) и одновременно выдача внешнего синхронизирующего сигнала "СИН: 1" (блок 11 ГСА) (фиг.1). В блоке 12 ГСА по команде "ИНСЧ:1" содержимое счетчика СЧ увеличивается на единицу (фиг.2), осуществляется переход на блок 10 ГСА.

В блоке 13 ГСА по команде "ЗПРГ:1" происходит запись в регистр РГ состояния счетчика СЧ (фиг.2), в данном случае равного количеству символов в принятом слове.

В блоке 14 ГСА анализируется признак пустоты стека блока СБП1 (фиг.5) "С1ПТ=1". По этому признаку осуществляется переход на блок 16 алгоритма.

В блоке 15 ГСА по команде "ОБСЧ:1" происходит обнуление счетчика СЧ (фиг. 2), по командам "ЧТС1:1", "А1:1", "А2:1" и "ЗПС2:1" происходит запись символа из блока СБП1 в блок СБП2, при этом сигналы "А1" и "А2", подаваемые на адресные входы коммутатора (КМ), соединяют его выход со входом И3 (фиг. 6). Осуществляется переход на блок 19 ГСА.

В блоке 16 ГСА анализируется признак пустоты стека бока СБП2 (фиг.4) "С2ПТ= 1". По этому признаку осуществляется переход на блок 40 ГСА, иначе происходит запись слова из СБП2 в СБП1 (фиг.1).

В блоке 17 ГСА анализируется признак границы между словами в стековых блоках памяти (фиг.1) "ГС=1", идентифицируемый специальным служебным кодом. По этому признаку осуществляется переход на блок 15 ГСА.

В блоке 18 ГСА по командам "ЧТС2:1" и "ЗПС1:1" происходит запись очередного символа из стека блока СБП2 в стек блока СБП1 (фиг.4,5). Осуществляется переход на блок 17 ГСА.

В блоке 19 ГСА анализируется признак того, что И2 меньше И3 "МЕНЬШЕ=1", выдаваемый элементом сравнения (фиг. 1). По этому признаку осуществляется переход на блок 20 ГСА, иначе на блок 35 ГСА.

В блоке 20 ГСА анализируется признак границы между словами в стеках (фиг.4,5) "ГС=1". По этому признаку осуществляется переход на блок 22 ГСА.

В блоке 21 ГСА по командам "ЧТС2:1" и "ЗПС1:1" происходит запись символа из СБП2 в СБП1 (фиг.1). Осуществляется переход на блок 20 ГСА.

В блоке 22 ГСА анализируется признак пустоты стека блока СБП2 (фиг.4) "С2ПТ=1". По этому признаку осуществляется переход на блок 40 ГСА.

В блоке 23 ГСА по командам "ЧТС2:1" и "ЗПС1:1" происходит запись символа из СБП2 в СБП1 (фиг.1).

В блоке 24 ГСА анализируется признак границы слов в стеках блоков СБП2 и СБП1 (фиг. 4,5) "ГС=1". По этому признаку осуществляется переход на блок 25 ГСА, иначе на блок 23 алгоритма.

В блоке 25 ГСА по команде "обсч:1" происходит обнуление счетчика СЧ блока БОП (фиг. 2), по командам "ЧТС1:1", "ЗПС2:1", "А1:1", "А2:1" происходит запись символа из СБП1 в СБП2 (фиг.1).

В блоке 26 ГСА анализируется признак того, что И2 меньше И3 "МЕНЬШЕ=1", по которому осуществляется переход на блок 20 ГСА.

В блоке 27 ГСА анализируется признак того, что И2 равно И3 "РАВНО=1", по которому осуществляется переход на блок 31 ГСА.

В блоке 28 ГСА анализируется признак того, что И2 больше И3 "БОЛЬШЕ=1", выдаваемый элементом сравнения ЭС (фиг.1). По этому признаку осуществляется переход на блок 29 ГСА, иначе на блок 26 ГСА, и признаки проверяются заново.

В блоке 29 ГСА анализируется признак границы слов в стеках (фиг.4,5) "ГС=1", по которому осуществляется переход на блок 40 ГСА.

В блоке 30 ГСА по командам "ЧТС1:1", "А1:1", "А2:1", "ЗПС2:1" происходит запись в СБП2 символа из блока СБП1 (фиг.1). Осуществляется переход на блок 29 ГСА.

В блоке 31 ГСА по команде "ИНСЧ:1" содержимое счетчика СЧ увеличивается на единицу (фиг.2). По командам "ЧТС1:1", "А1:1", "А2:1", "ЗПС2:1" происходит запись в СБП2 символа из СБП1 (фиг.1).

В блоке 32 ГСА анализируется признак границы слов в стеках (фиг.4,5) "ГС=1" или пустоты стека блока СБП2 "С2ПТ" (фиг.4). По этому признаку осуществляется переход на блок 34 ГСА.

В блоке 33 ГСА анализируется признак конца слова, хранящегося в БОП "КС= 1" (фиг. 1), выдаваемый при равенстве состояний счетчика СЧ и регистра РГ блока БОП (фиг.2). По этому признаку осуществляется переход на блок 20 ГСА, иначе на блок 26 ГСА.

В блоке 34 ГСА анализируется признак конца слова в БОП "КС=1" (фиг.1). По этому признаку осуществляется переход на блок 40 ГСА, иначе на блок 29 ГСА.

В блоке 35 ГСА анализируется признак того, что И2 равна И3 "РАВНО=1" (фиг.1). Если "РАВНО=0", осуществляется переход на блок 44 ГСА.

В блоке 36 ГСА по команде "ИНСЧ:1" содержимое счетчика СЧ увеличивается на единицу (фиг.2). По командам "ЧТС1:1", "А1:1", "А2:1", "ЗПС2:1" происходит запись в СБП2 символа из СБП1 (фиг.1).

В блоке 37 ГСА анализируется признак границы слов в стеках или пустоты стека блока СБП2, соответственно "ГС= 1" и "С2ПТ=1" (фиг.4,5). По этому признаку осуществляется переход на блок 39 ГСА.

В блоке 38 ГСА анализируется признак конца слова в БОП "КС=1" (фиг.1). По этому признаку осуществляется переход на блок 20 ГСА, иначе на блок 19 ГСА.

В блоке 39 ГСА анализируется признак конца слова в БОП "КС=1" (фиг.1). По этому признаку осуществляется переход на блок 40 ГСА, иначе на блок 45 ГСА.

В блоке 40 ГСА по команде "ОБСЧ:1" обнуляется счетчик СЧ (фиг.2), по командам "ЗПС2: 1" и "А2:1" в стек блока СБП2 (фиг.4) записывается служебный код границы между словами, причем сигналом "А2", поступающим на адресный вход коммутатора (КМ) блока БКиИ, коммутируется выход формирователя кодов ФК, генерирующего служебный код, на выход коммутатора КМ (фиг.6).

В блоке 41 ГСА анализируется признак конца слова в БОП "КС=1" (фиг.1). По признаку осуществляется переход на блок 71 ГСА.

В блоке 42 ГСА по командам "ЗПС2:1" и "А1:1" происходит запись символа из ОЗУ с адресом, хранящимся в счетчике СЧ (фиг.2), в СБП2 (фиг.1), при этом на адресный вход коммутатора КМ блока БКиИ поступает сигнал "А1" и коммутирует вход И2 на выход КМ (фиг.6).

В блоке 43 ГСА по команде "ИНСЧ:1" происходит увеличение на единицу содержимого счетчика СЧ (фиг.2). Осуществляется переход на блок 41 ГСА.

В блоке 44 ГСА анализируется признак того, что И2 больше И3 "БОЛЬШЕ=1" (фиг.1). Если "БОЛЬШЕ=0", осуществляется переход на блок 19 ГСА.

В блоке 45 ГСА анализируется признак границы слов "ГС=1" в стеках или пустоты стека блока СБП2 "С2ПТ=1" (фиг.4,5). По этому признаку осуществляется переход на блок 47 ГСА.

В блоке 46 ГСА по командам "ЧТС1:1", "ЗПС2:1", "А1:1", "А2:1" происходит запись в СБП2 символа из СБП1 (фиг.1). Осуществляется переход на блок 45 ГСА.

В блоке 47 алгоритма анализируется признак пустоты СБП1 "С1ПТ=1" (фиг. 1). По признаку осуществляется переход на блок 40 ГСА.

В блоке 48 ГСА по команде "ОБСЧ:1" происходит обнуление счетчика СЧ (фиг. 2), по командам "ЧТС1:1", "ЗПС2:1", "А1:1", "А2:1" происходит запись в СБП2 символа из СБП1 (фиг.1).

В блоке 49 ГСА анализируется признак того, что И2 меньше И3 "МЕНЬШЕ=1" (фиг.1). По признаку осуществляется переход на блок 56 ГСА.

В блоке 50 ГСА анализируется признак того, что И2 равно И3 "РАВНО=1" (фиг.1). По признаку осуществляется переход на блок 52 ГСА.

В блоке 51 ГСА анализируется признак того, что И2 больше И3 "БОЛЬШЕ=1" (фиг.1). По признаку осуществляется переход на блок 45 ГСА, иначе на блок 49 ГСА.

В блоке 52 ГСА по команде "ИHСЧ:1" cодержимое cчетчика СЧ увеличиваетcя на единицу (фиг. 2), по командам "ЧТС1:1", "ЗПС2:1", "А1:1", "А2:1" проиcходит запиcь cимвола в СБП2 из СБП1 (фиг. 1).

В блоке 53 ГСА анализируется признак границы слов "ГС=1" в стеках или пустоты стека блока СБП2 "С2ПТ=1" (фиг.4,5). Если признак равен нулю, осуществляется переход на блок 55 ГСА.

В блоке 54 ГСА анализируется признак конца слова в БОП "КС=1" (фиг.1). По этому признаку осуществляется переход на блок 40 ГСА,иначе на блок 45 ГСА.

В блоке 55 ГСА анализируется признак конца слова в БОП "КС=1". Если "КС= 0", осуществляется переход на блок 49 ГСА.

В блоке 56 ГСА анализируется признак границы между словами в стеках "ГС= 1" (фиг.4,5). По признаку осуществляется переход на блок 40 алгоритма.

В блоке 57 ГСА по командам "ЧТС2:1" и "ЗПС1:1" переписывается символ из СБП2 в СБП1 (фиг.1). Осуществляется переход на блок 56 ГСА.

В блоке 58 ГСА анализируется признак пустоты СБП2 "С2ПТ". Если "С2ПТ=1", осуществляется переход на блок 60 ГСА.

В блоке 59 ГСА по командам "ЧТС2:1" и "ЗПС1:1" переписывается символ из СБП2 в СБП1 (фиг.1). Осуществляется переход на блок 58 ГСА.

В блоке 60 ГСА анализируется признак наличия сигнала "ЧТПР" (фиг.1). Если "ЧТПР=1", осуществляется переход на блок 61 ГСА, иначе на блок 60 ГСА.

В блоке 61 ГСА анализируется признак пустоты СБП1 "С1ПТ=1" (фиг.1). По признаку осуществляется переход на блок 72 ГСА.

В блоке 62 ГСА происходит выдача символа из СБП1 на выходной канал по командам "ЧТС1:1" и "РВ:1" и одновременно выдача выходного синхронизирующего сигнала "СИН: 1". При этом сигналом "РВ" выход шинного формирователя подключается к его входу (фиг.6).

В блоке 63 ГСА анализируется признак пустоты СБП1 "С1ПТ=1" (фиг.1). По признаку осуществляется переход на блок 65 ГСА.

В блоке 64 ГСА по командам "ЧТС1:1", "ЗПС2:1", "А1:1", "А2:1" происходит запись символа из СБП1 в СБП2 (фиг.1). Осуществляется переход на блок 63 ГСА.

В блоке 65 ГСА анализируется наличие сигнала "ЧТОБ=1" (фиг.1). Если "ЧТОБ=1", осуществляется переход на блок 66 ГСА, иначе на блок 65 ГСА.

В блоке 66 ГСА анализируется признак пустоты СБП2 "С2ПТ=1" (фиг.1). По признаку осуществляется переход на блок 72 ГСА.

В блоке 67 ГСА анализируется признак границы между словами в стеках (фиг.4,5) "ГС". Если "ГС=1", осуществляется переход на блок 69 ГСА.

В блоке 68 ГСА по командам "ЧТС2:1", "ЗПС1:1" переписывается символ из СБП2 в СБП1 (фиг.1). Осуществляется переход на блок 67 ГСА.

В блоке 69 ГСА анализируется признак пустоты СБП1 "С1ПТ" (фиг.1). Если "С1ПТ=1", осуществляется переход на блок 65 ГСА.

В блоке 70 ГСА происходит выдача символа на выходной канал из СБП1 по командам "РВ:1", "ЧТС1:1 и одновременно выдача сигнала "СИН:1". Осуществляется переход на блок 69 ГСА.

В блоке 71 ГСА анализируется признак СБП1 или СБП2 полон "С1ПН или С2ПН" (фиг. 1). Если признак равен нулю, происходит переход на блок 6 ГСА, иначе сортировка экстренно прекращается и осуществляется переход на блок 72 ГСА.

В блоке 72 ГСА выдается внешний сигнал готовности устройства "ГТ:1" (фиг.1).

Работа устройства сортировки информации заключается в следующем.

Внешние управляющие сигналы "ЗАГР", "ЧТПР", "ЧТОБ", "ПУСК" и "СБРОС" поступают в блок 8 управления, сигналы "ГТ" и "СИН" из блока 8 управления. Входной канал представляет собой интерфейс, по которому посимвольно поступают слова, подлежащие сортировке. Выходной канал-интерфейс, по которому посимвольно поступающие отсортированные слова выдаются на внешнее устройство.

Основная идея работы заключается в следующем.

Сортировка данных происходит по мере их поступления. На вход устройства сортировки посимвольно поступает и записывается в БОП текущее слово (число), где символом является составляющая слова, имеющая фиксированную длину. Началом отсортированного массива считается первый символ наименьшего числа (слова), концом последний символ наибольшего, при этом массив хранится в стеках блоков СБП1 и СБП2 (фиг.1). Указанные стеки (фиг.4,5) организованы в виде очередей типа LIFO (последним пришел первым ушел), причем начало отсортированного массива является первым пришедшим в стек блока СБП2, а конец первым пришедшим в стек блока СБП1. Осуществляется поиск весового места слова текущего) в массиве уже упорядоченных данных посредством посимвольных сравнений элементом сравнения ЭС текущего слова со словами массива упорядоченных данных. Весовое место слова такая позиция текущего слова в упорядоченном массиве, когда ближайшее к нему стоящее на позицию раньше слово меньше либо равно ему, а стоящее на позицию позже слово больше либо равно ему.

Поиск весового места слова (текущего) осуществляется следующим образом. Первый символ текущего слова сравнивается элементом сравнения (ЭС) с первым символом первого слова из стека блока СБП1 (фиг.1).Если результатом сравнения является равенство, сравниваются вторые символы и т.д. до тех пор, пока результатом сравнения не станет "больше" или "меньше", или одно из слов не кончилось. Причем сравненные символы переписываются из СБП1 в СБП2. Результат сравнения двух слов: если слова кончились одновременно они равны, если элементом сравнения (ЭС) был выдан сигнал "БОЛЬШЕ=1" (т.е. символ слова из БОП больше символа слова из СБП1), либо слово блока СБП1 кончилось, а слово БОП нет текущее слово, находящееся в БОП, больше исследованного числа из СБП1. Если элементом сравнения выдан сигнал "МЕНЬШЕ=1" (т.е. символ слова из БОП меньше символа слова из СБП1), либо текущее слово кончилось, а исследуемое (из СБП1) нет текущее слово больше исследованного. Далее, если текущее слово равно исследованному, оно записывается за ним в СБП2, если текущее слово больше, оно сравнивается с ближайшим большим исследованному слову, пока текущее слово не станет равно очередному слову из стека, тогда оно записывается за очередным исследованным словом, либо не станет меньше очередного, тогда текущее слово из БОП записывается перед ним, либо не будет достигнут конец массива, при достижении конца массива текущее слово из БОП записывается в конец. Если текущее слово меньше исследованного, то оно сравнивается с очередным ближайшим меньшим исследованному, пока не станет равно очередному, либо больше его, тогда слово из БОП записывается в массив за исследованным словом (т.е. на позицию ближе к концу массива), либо не будет достигнуто начало массива, при достижении начала слово из БОП записывается в массив первым.

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

Блок 2 оперативной памяти содержит счетчик (СЧ), регистр (РГ), оперативное запоминающее устройство (ОЗУ) и компаратор (КП) (фиг.2). На инверсный вход ОЗУ выбор кристалла подается константа "0" (не ВК). Входная информация И1 поступает на вход ОЗУ. По сигналу "ОБСЧ=1" происходит обнуление счетчика. По сигналу "ЗПОЗУ=1" записывается входной символ в ОЗУ по адресу, хранящемуся в счетчике. По сигналу "ИНСЧ=1" содержимое счетчика увеличивается на единицу. По сигналу "ЗПРГ=1", выдаваемому по окончании загрузки слова, содержимое счетчика, в данном случае равно количеству символов в слове, записывается в регистр. Если "ЗПОЗУ=0", на выход ОЗУ И2 выдается символ, находящийся по адресу, хранящемуся в счетчике. Компаратор (КП), входами которого являются выходы регистра и счетчика, определяет признак конца слова "КС", выдаваемый в блок 8 управления при равенстве этих кодов (фиг.1).

Элемент 3 сравнения содержит компаратор (КП) (фиг.3), который сравнивает поступающие на его входы символы И2 и И3 и выдает в блок 8 управления (фиг. 1) сигналы "БОЛЬШЕ=1" (если И2 больше И3), "МЕНЬШЕ=1" (если И2 меньше И3), "РАВНО=1" (если И2 равно И3).

Стековый блок 4 памяти содержит стек (фиг.4) и служит для хранения части отсортированного массива. По сигналу "ЗПС2=1" в вершину стека записывается символ И5, по сигналу "ЧТС2=1" из вершины стека считывается символ на выход И4. При этом стеком выдаются сигналы в блок 8 управления (фиг.1) "С2ПН=1" (если стек полон) и "С2ПТ=1" (если стек пуст).

Стековый блок 5 памяти содержит стек (фиг.5) и служит для хранения другой части отсортированного массива. По сигналу "ЧТС1=1" из вершины стека считывается символ на выход И3, по сигналу "ЗПС1=1" в вершину стека записывается символ И4. При этом стеком выдаются сигналы в блок 8 управления (фиг. 1) "С1ПН=1" (если стек полон) и "С1ПТ=1" (если стек пуст).

Блок 6 коммутации и идентификации (фиг.6) содержит шинный формирователь (ШФ) с тремя состояниями на выходе, компаратор (КП), коммутатор (КМ), формирователь кодов (ФК). Служит для выдачи упорядоченного массива слов на выходной канал ВЫХК и коммутации сигналов от трех источников на вход СБП2 (фиг. 1). По сигналу "РВ=1" информация со входа ШФ И3 передается на его выход И6. Когда "РВ=0", его выход находится в высокоимпедансном состоянии. Сигналы А1 и А2 поступают на адресные входы коммутатора КМ, И5 является его выходом, на который передается входная информация И3 по "А1=1", "А2=1", передается И2 по "А1=1", "А2=0", либо передается служебный код границы между словами, генерируемый формирователем кодов (ФК), указанное подключение осуществляется при "А1=0", "А2=1". Выход И5 коммутатора поступает на вход СБП2 (фиг.1). Компаратор, на входы которого поступают И3 и выход ФК, определяет признак границы между упорядоченными словами "ГС", выдаваемый в блок 8 управления (фиг.1) при равенстве символа, находящегося в вершине стека СБП1, служебному коду.

Блок 8 управления синтезируется на основе ГСА управления (фиг.7) известным способом (2).

Размеченная ГСА работы блока 8 управления приведена на фиг.8, где обозначено.

Логические условия:
Х1: "СБРОС"
Х2: "ПУСК"
Х3: "С2ПТ и С1ПТ"
Х4: "ЧТОБ"
Х5: "ЧТПР"
Х6: "ЗАГР"
Х7: "С2ПТ"
Х8: "МЕНЬШЕ"
Х9: "ГС"
Х10: "ГС или С2ПТ"
Х11: "БОЛЬШЕ"
Х12: "РАВНО"
Х13: "КС"
Х14: "С1ПТ"
Х15: "С2ПН или С1ПН"
Операторы:
У1: "ЧТС1:1"
У2: "ЧТС2:1"
У3: "ОБСЧ:1"
У4: "РВ:1"
У5: "ЗПОЗУ:1"
У6: "СИН:1"
У7: "ИНСЧ:1"
У8: "ЗПРГ:1"
У9: "А1:1"
У10: "А2:1"
У11: "ЗПС1:1"
У12: "ГТ:1"
У13: "ЗПС2:1"

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

УСТРОЙСТВО СОРТИРОВКИ ИНФОРМАЦИИ, содержащее два стековых блока памяти, элемент сравнения, блок управления, отличающееся тем, что в него введены входной и выходной каналы, блок оперативной памяти, блок коммутации и идентификации, причем с первого по пятый управляющие выходы блока управления соединены соответственно с первого по пятый управляющими входами блока оперативной памяти, информационный вход которого соединен с входным каналом, управляющий выход с четвертым управляющим входом блока управления, информационный выход с первым информационным входом элемента сравнения и вторым информационным входом блока коммутации и идентификации, управляющий выход последнего соединен с четырнадцатым управляющим входом блока управления, с первого по третий управляющие входы соединены соответственно с десятого по двенадцатый управляющими выходами последнего, второй информационный выход с выходным каналом, первый информационный выход с информационным входом второго стекового блока памяти, первый и второй управляющие входы последнего соединены соответственно с шестым и седьмым управляющими выходами блока управления, первый и второй управляющие выходы соответственно с десятым и одиннадцатым управляющими входами последнего, информационный выход с информационным входом первого стекового блока памяти, первый и второй управляющие входы которого соединены соответственно с восьмым и девятым управляющими выходами блока управления, первый и второй управляющие выходы - соответственно с двенадцатым и тринадцатым управляющими входами последнего, информационный выход с первым информационным входом блока коммутации и идентификации и с вторым информационным входом элемента сравнения, с первого по третий управляющие выходы последнего соединены соответственно с пятого по седьмой управляющими входами блока управления, с первого по третий управляющие входы блока управления, а также восьмой и девятый управляющие входы последнего являются внешними входами устройства, тринадцатый и четырнадцатый управляющие выходы блока управления являются внешними выходами устройства.