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

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

Известно "Устройство сортировки информации" (а.с. №1594521, 1990 г. Бюл. 35), позволяющее упорядочить массивы данных.

Известно также "Устройство сортировки информации" (пат. №2034327, 1995 г. Бюл. 2), позволяющее упорядочить данные.

В качестве прототипа выбрано "Устройство сортировки информации" (пат. №2128855, 1999 г. Бюл. 10), позволяющее упорядочить данные и осуществить отбор слов из потока данных на основании сопоставления их с заданными образцами.

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

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

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

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

ВХК - входной канал служит для приема данных.

БОП - блок оперативной памяти служит для временного хранения принятого слова или числа.

ЭС - элемент сравнения символов принятого слова и уже упорядоченных слов или образцов.

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

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

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

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

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

Теория нормальных алгорифмов универсальна по отношению к любым алгоритмическим схемам [1]. Под алгорифмом Маркова понимается конечная последовательность формул вида

где S - образец; Т - подстановка; S и Т - произвольные слова в фиксированном алфавите.

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

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

В основу работы предлагаемого устройства положен модифицированный алгоритм, который содержит образец и подстановку с указанными выше особенностями. Устройство сортировки информации реализует формулы вида (2, 3, 4)

S1, S2 - компаранды образца; © - символ, обозначающий операцию компарации на "больше", "меньше" и "равно"; ©' - символ, обозначающий операцию компарации на "больше" и "меньше" с "равно" с учетом маски образца при сопоставлении (который показан в качестве компаранда образца в формуле вида (1)), а также сопоставление длины компарандов; Т1 - указатель позиции в частично упорядоченном массиве одного из компарандов в зависимости от результата компарации или сопоставления длин слов; Т2 - указатель следующего (текущего) компаранда или правила построения образца по результатам сравнения слов; → - разделители в форме служебных символов, не входящих в основной алфавит; Т3 - фрагмент подстановки, означающий выдачу на выходной канал принятого слова.

n - количество образцов; S3 - множество образцов; Т4 - множество подстановок; i - номер образца и соответствующей ему подстановки.

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

Формула вида (2) задает рекурсивную реализацию процесса упорядочения; формула вида (3) - процесса селекции, формула вида (4) задает реализацию процесса селекции с подстановкой, при этом сопоставление текста с образцами происходит последовательно.

На фиг.1 изображена структурная схема устройства сортировки информации;

на фиг.2 представлен вариант технической реализации блока оперативной памяти;

на фиг.3 - вариант технической реализации элемента сравнения;

на фиг.4 - вариант технической реализации второго стекового блока памяти;

на фиг.5 - вариант технической реализации первого стекового блока памяти;

на фиг.6 - вариант технической реализации блока коммутации и идентификации;

на фиг.7 А-В - содержательная граф-схема алгоритма (далее по тексту ГСА) работы блока управления.

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

Для описания алгоритма работы блока 8 управления используются следующие идентификаторы.

1. ЗАГР - сигнал записи в устройство.

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

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

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

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

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

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

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

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

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

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

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

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

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

15. ОБСЧА - сигнал обнуления счетчика адреса СЧА блока СБП1.

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

17. ЗПРГА - сигнал записи в регистр адреса РГА блока СБП1 информации из счетчика адреса СЧА блока СБП1.

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

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

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

21. KM - признак конца массива, находящегося в блоке СБП1 в режиме селекции.

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

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

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

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

26. РСЕЛ - внешний признак режима селекции.

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

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

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

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

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

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

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

34. МС - признак маскированного символа в режиме селекции.

35. РПОД - внешний признак режима подстановки.

36. НЕРПОД - инверсия признака РПОД.

37. ПОД - сигнал выбора нечетного адреса ОЗУ блока СБП1 в режиме подстановки.

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

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

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

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

42. И3 - выходные данные ОЗУ блока СБП1.

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

44. И5 - выходные данные коммутатора блока БКиИ, поступающие на вход стека СБП2.

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

46. И7 - выходные данные коммутатора КМ2 блока БКиИ.

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

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

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

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

В узле 6 ГСА осуществляется анализ сигнала "ЧТОБ", по этому сигналу осуществляется переход на узел 63 ГСА.

В узле 7 ГСА осуществляется анализ сигнала "ЧТПР", по этому сигналу осуществляется переход на узел 58 ГСА.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В блоке 24 ГСА анализируется признак границы слов в стековых блоках памяти "ГС".

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

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

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

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

В блоке 29 ГСА анализируется признак "ГС", по которому осуществляется переход на блок 40 ГСА.

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

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

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

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

В блоке 34 ГСА анализируется признак "КС", по которому осуществляется переход на блок 40 ГСА, иначе на блок 29 ГСА.

В блоке 35 ГСА анализируется признак "РАВНО", если "РАВНО=0", осуществляется переход на блок 44 ГСА.

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

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

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

В блоке 39 ГСА анализируется признак "КС", если "КС=0", осуществляется переход на блок 45 ГСА.

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

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

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

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

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

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

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

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

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

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

В блоке 50 ГСА анализируется признак "РАВНО", по признаку осуществляется переход на блок 52 ГСА.

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

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

В блоке 53 ГСА анализируется признак "ГС" или "С2ПТ". Если признак равен нулю, осуществляется переход на блок 55 ГСА.

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

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

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

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

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

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

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

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

В блоке 62 ГСА выдача символа из СБП1 на ВЫХК по командам "ЧТС1:=1", "РВ:=1" и одновременно выдача сигнала "СИН:=1".

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

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

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

В блоке 66 ГСА анализируется признак "С2ПТ", по признаку осуществляется переход на блок 115 ГСА.

В блоке 67 анализируется признак "ГС", по которому осуществляется переход на блок 69 ГСА.

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

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

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

В блоке 71 ГСА анализируется наличие сигнала "ЗАГР". Если "ЗАГР=0", осуществляется переход на блок 71 ГСА.

В блоке 72 ГСА по команде "ОБСЧА:=1" обнуляется содержимое счетчика СЧА (фиг.5).

В блоке 73 ГСА по командам "ЗПС1:=1", "А0:=1" в СБП1 загружается символ с ВХК, что стробируется сигналом "СИН" (фиг.1).

В блоке 74 ГСА по команде "ИНСЧА" увеличивается на единицу содержимое СЧА (фиг.5).

В блоке 75 ГСА анализируется наличие сигнала "ЗАГР", по которому осуществляется переход на блок 77 ГСА.

В блоке 76 ГСА по команде "ЗПРГА:=1" содержимое СЧА записывается в регистр РГА (фиг.5).

В блоке 77 ГСА анализируется наличие сигнала "ЧТОБ". Если "ЧТОБ=0", осуществляется переход на блок 79 ГСА.

В блоке 78 ГСА по команде "ОБСЧА:=1" обнуляется содержимое СЧА (фиг.5), осуществляется переход на блок 63 ГСА.

В блоке 79 ГСА анализируется наличие сигнала "ЧТПР", если "ЧТПР=0", осуществляется переход на блок 81 ГСА.

В блоке 80 ГСА по команде "ОБСЧА:=1" обнуляется содержимое СЧА (фиг.5), осуществляется переход на блок 58 ГСА.

В блоке 81 ГСА анализируется наличие сигнала "ЗАГР". Если "ЗАГР=0", осуществляется переход на блок 81 ГСА.

В блоке 82 ГСА по команде "ОБСЧ:=1" обнуляется содержимое СЧ (фиг. 2).

В блоке 83 ГСА анализируется наличие сигнала "ЗАГР". Если "ЗАГР=0", осуществляется переход на блок 86 ГСА.

В блоке 84 ГСА по команде "ЗПОЗУ:=1" в БОП записывается символ с входного канала (фиг.1), что стробируется сигналом "СИН".

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

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

В блоке 87 ГСА по командам "ОБСЧ:=1", "ОБСЧА:=1" обнуляется содержимое СЧ (фиг.2), СЧА (фиг.5).

В блоке 88 ГСА анализируется признак "БОЛЬШЕ", по которому осуществляется переход на блок 117 ГСА.

В блоке 89 ГСА анализируется признак "МЕНЬШЕ", по которому осуществляется переход на блок 114 ГСА.

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

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

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

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

В блоке 94 ГСА анализируется признак "МЕНЬШЕ", по которому осуществляется переход на блок 118 ГСА.

В блоке 95 анализируется признак "БОЛЬШЕ", по которому осуществляется переход на блок 114 ГСА.

В блоке 96 ГСА анализируется признак "ГС", по которому осуществляется переход на блок 114 ГСА.

В блоке 97 ГСА анализируется признак "КС", по которому осуществляется переход на блок 118 ГСА.

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

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

В блоке 100 ГСА анализируется признак конца массива образцов в СБП1 "КМ" (фиг.5), по признаку осуществляется переход на блок 114.

В блоке 101 ГСА анализируется признак "РАВНО" или маскированный символ "МС". Если признак равен нулю, осуществляется переход на блок 118 ГСА.

В блоке 102 по командам "ИНСЧ:=1", "ИНСЧА:=1" увеличивается на единицу содержимое СЧ (фиг.2) и содержимое СЧА (фиг.5).

В блоке 103 ГСА анализируется признак "ГС" или "КМ", по признаку осуществляется переход на блок 105 ГСА.

В блоке 104 ГСА анализируется признак "КС", по признаку осуществляется переход на блок 118 ГСА, иначе на блок 101 ГСА.

В блоке 105 ГСА анализируется признак "КС". Если "КС=1", осуществляется переход на блок 118 ГСА.

В блоке 106 ГСА по команде "ОБСЧ:=1" содержимое СЧ обнуляется (фиг.1).

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

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

В блоке 109 ГСА анализируется признак "КС". Если "КС=0", осуществляется переход на блок 107 ГСА.

В блоке 110 ГСА по командам "А2:=1", "ЗПС2:=1" производится запись кода границы между словами в стек СБП2 (фиг.1, 4).

В блоке 111 анализируется признак "С1ПН" или "С2ПН". Если признак равен нулю, осуществляется переход на блок 114 ГСА.

В блоке 112 ГСА по команде "ОБСЧА:=1" обнуляется содержимое СЧА (фиг.5), выдается внешний сигнал "ГТ", осуществляется переход на блок 58 ГСА.

В блоке И3 ГСА анализируется наличие сигнала "РСЕЛ", по которому осуществляется переход на блок 71 ГСА, иначе на блок 6 ГСА.

В блоке 114 ГСА выдается сигнал "СИН", переход на блок 77 ГСА.

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

В блоке 116 ГСА выдается сигнал "ГТ" (фиг.1).

В блоке 117 ГСА анализируется признак "ГС или КМ", по которому осуществляется переход на блок 94 ГСА, иначе на блок 93 ГСА, из которого осуществляется переход на блок 117 ГСА.

В блоке 118 ГСА анализируется признак "ГС или КМ", по которому осуществляется переход на блок 100 ГСА, иначе на блок 99 ГСА, из которого осуществляется переход на блок 118 ГСА.

В блоке 119 ГСА анализируется признак "РПОД", если признак равен нулю, осуществляется переход на блок 88 ГСА.

В блоке 120 ГСА анализируется признак "РАВНО", если признак равен нулю, осуществляется переход на блок 125 ГСА.

В блоке 121 ГСА анализируется признак "КМ", если признак равен нулю, осуществляется переход на блок 129 ГСА.

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

В блоке 123 ГСА анализируется признак "С2ПН", по которому осуществляется переход на блок 131 ГСА.

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

В блоке 125 ГСА по командам "ЗПС2:=1", "А1:=1", "А2:=1", "ПОД:=1" в СБП2 производится запись символа - подстановки из СБП1 (фиг.1).

В блоке 126 ГСА анализируется признак "С2ПН", по которому осуществляется переход на блок 131 ГСА.

В блоке 127 ГСА анализируется признак "КС", по которому осуществляется переход на блок 77 ГСА.

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

В блоке 129 ГСА по команде "ИНСЧА:=1" содержимое СЧА увеличивается на единицу.

В блоке 130 ГСА по команде "ИНСЧА:=1" содержимое СЧА увеличивается на единицу, переход на блок 120 ГСА.

В блоке 131 ГСА по команде "ОБСЧА:=1" обнуляется содержимое СЧА (фиг.5), выдается внешний сигнал "ГТ", осуществляется переход на блок 58 ГСА.

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

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

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

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

Селекция данных происходит из входного потока слов на основе результатов их сопоставления с образцами. На вход устройства посимвольно поступают и записываются образцы, разграниченные символами с кодами 11...1, в СБП1, причем сначала подаются образцы - нижняя и верхняя границы, а затем образцы для сопоставления на равно, в которых отдельные позиции символов образца могут быть маскированы путем записи в них символов с кодами 00...0.

Далее на вход устройства посимвольно поступает и записывается в БОП текущее слово, подлежащее обработке. Осуществляется сопоставление принятого слова с образцами. С первым образцом осуществляется сопоставление на больше, при этом первый символ текущего слова сравнивается ЭС с первым символом образца и т.д., пока результатом сравнения не станет больше или образец не кончится первым, и тогда слово считается больше образца, или результатом сравнения не станет меньше или слово в БОП не закончится, тогда слово считается меньшим или равным образцу и неудовлетворяющим условию выбора (т.к. первый образец должен являться нижней границей). Если слово больше образца, оно сопоставляется со вторым образцом на меньше, при этом первый символ текущего слова сравнивается ЭС с первым символом образца и т.д., пока результатом сравнения не станет меньше или слово не кончится первым, и тогда считается, что слово меньше образца, или результатом сравнения не станет больше или образец не кончится, тогда слово считается большим или равным образцу и неудовлетворяющим условию.

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

Если слово равно образцу, оно отбирается, т.е. записывается в СБП2, если оно не равно ни одному образцу, слово считается неудовлетворяющим условию.

Далее и в случае, если слово не удовлетворяет условию, снова осуществляется загрузка очередного слова в БОП и сопоставление и т.д.

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

В режиме подстановки работа заключается в следующем. На вход устройства поступают и записываются в СБП1 образцы и подстановки, причем сначала подается первый символьный образец, затем соответствующая ему подстановка, второй и т.д., таким образом, образцы размещаются в ОЗУ СБП1 по четным адресам, а подстановки по нечетным. Далее на вход устройства посимвольно поступает и записывается в БОП фрагмент текста, подлежащий обработке. Осуществляется сопоставление первого принятого символа фрагмента текста на равно ЭС с первым, вторым и т.д. образцами до тех пор, пока символ не окажется равным образцу и тогда в СБП2 записывается соответствующая подстановка. Либо пока символ не будет сопоставлен со всеми образцами и окажется не равным ни одному, и тогда в СБП2 записывается текущий символ сопоставляемого фрагмента текста. То же самое выполняется и для других принятых символов фрагмента текста. Далее в БОП записывается следующий фрагмент текста и также осуществляется его обработка и так далее до окончания текста. По мере переполнения СБП2, в котором хранится обработанный фрагмент текста, а также по окончанию работы осуществляется выдача информации из СБП2 на выходной канал.

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

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

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

Первый стековый блок 4 памяти содержит счетчик адреса СЧА, оперативное запоминающее устройство ОЗУ, регистр адреса РГА, компаратор КП, элементы И, ИЛИ, ИЛИ-НЕ (фиг.3). Информация И7 поступает на вход данных ОЗУ. По сигналу "ЗПС1=1", поступающему на вход СЧА и вход записи в ОЗУ, по переднему фронту символ И7 записывается в ОЗУ по адресу, хранящемуся в СЧА, содержимое которого увеличивается на единицу по заднему фронту. По сигналу "ЧТС1=1" содержимое СЧА уменьшается на единицу по заднему фронту, при этом сигналом "ЗПС1=0" осуществляется чтение по переднему фронту из ОЗУ символа И3, адресуемого содержимым СЧА. По сигналу "ОБСЧА=1" содержимое СЧА обнуляется. По сигналу "ИНСЧА=1" содержимое СЧА увеличивается на единицу. Выход AM счетчика СЧА соответствует его младшему разряду. На вход младшего разряда адреса ОЗУ с элемента ИЛИ подается сигнал АМ&НЕРПОД∨ПОД&РПОД. По сигналу "ЗПРГА=1", выдаваемому по окончании записи массива образцов в режиме селекции, содержимое СЧА записывается в РГА. На инверсный вход ОЗУ выбор кристалла "не ВК" подается константа "0". Компаратор КП осуществляет сравнение содержимых СЧА и РГА, выходы которых подаются на его входы и при их равенстве выдает признак конца массива "КМ=1". Элементы И и ИЛИ-НЕ выдают признаки, соответственно, стек полон "С1ПН" и стек пуст "С1ПТ".

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

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

Источники информации:

1. Марков А.А., Нагорный Н.М. Теория алгорифмов. - Москва: Наука, - 318 с. Главная редакция физико-математической литературы, 1984 г.

2. Баранов С.И. Синтез микропрограммных автоматов. - Энергия. Ленинградское отделение. 1974 г. - 184 с.

3. Лебедев О.Н. Микросхемы памяти и их применение. - Москва: Радио и связь, 1990 г. - 184 с.

4. Пат. №2128855, 1999 г. Бюл. 10 (прототип).

5. Пат. №2034327, 1995 г. Бюл. 2 (аналог).

6. А.С. №1594521, 1990 г. Бюл. 355 (аналог).

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

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