УСТРОЙСТВО ДЛЯ РЕАЛИЗАЦИИ УПОРЯДОЧИВАЮЩИХ ПОДСТАНОВОК Российский патент 1996 года по МПК G06F17/00 

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

Известно "Устройство для сортировки чисел" (а.с. N 1304015, 1987 г. Бюл. N 14), позволяющее упорядочить массив чисел как в возрастающем, так и в убывающем порядке.

Известно также "Устройство для сортировки чисел" (а.с. N 1277091, 1986 г. Бюл. N 46), позволяющее упорядочить числа в возрастающем и в убывающем порядке.

В качестве прототипа выбрано "Устройство для реализации нормальных алгорифмов Маркова" (а. с. N 1455345, G 06 F 15/20, 1987, 1989 г. Бюл. N 4), которое позволяет обрабатывать информационные потоки и массивы данных текстового и числового характеров в соответствии с заданными алгоритмами.

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

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

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

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

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

Блок БК блок компарации служит для сравнения текущей буквы алфавитного порядка букв с буквами слов, поступающих из блока БРС, а также для определения конца слова и конца просмотра регистров блока регистров слов. Признаком конца слова в регистре будет являться нулевая информация, т.е. в конце слова будут записаны нули 000.00. Признаком конца регистров блока регистров слов будет являться единичная информация, т.е в последнем регистре блока БРС будут записаны единицы 111.11.

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

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

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

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

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

Под алгорифмом Маркова понимается конечная последовательность формул, представляющих собой слова вида:
S _→ T,,
где S образец, Т подстановка, S и T произвольные слова в фиксированном алфавите.

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

где знак графического равенства, R1, R2 любые слова в фиксированном алфавите, тогда результат работы формулы будет иметь вид:

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

Размеченный алгорифм Маркова для упорядочения массива слов будет иметь вид:

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

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

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

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

1. БПВ блок поиска вхождений.

2. БРС блок регистров слов.

3. БК блок компарации.

4. БСП блок стековой памяти.

5. БПОС блок подсчета одинаковых слов.

6. БООВ блок определения одноразового вхождения.

7. БОП блок организации и подстановок.

8. СДп сигналы сдвига регистра, содержащего слово.

9. ВДп сигналы выдачи слова из регистра блока регистров слов.

10. СПБ сигнал совпадения первой буквы поступившего слова с заранее определенной буквой алфавитного порядка.

11. ЗАПп сигналы записи слова в блок регистров слов.

12. ГИ1 генератор тактовых импульсов 1.

13. Ссч сигнал сброса счетчика СЧПр.

14. ЗС сигнал засылки адреса в блок стековой памяти.

15. Из сигнал извлечения адреса из блока стековой памяти.

16. БПЛ сигнал, означающий, что буфер стековой памяти полон.

17. БПС сигнал, означающий, что буфер стековой памяти пуст.

18. СУР команда "защелки" в регистре RG1 блока стековой памяти.

19. СВ команда, определяющая выбор информационного сигнала в регистре RG2 блока стековой памяти.

20. ЗСЧ первая команда управления выбора информации в RG3 ключа блока стековой памяти.

21. ЗВ вторая команда управления выбора информации в RG3 ключа блока стековой памяти.

22. КС команда, определяющая конец слова, т.е. в регистре блока регистров слов обнаружена нулевая информация.

23. КР команда, определяющая конец регистра блока регистров слов, т.е. все регистры этого блока просмотрены. В последнем регистре блока БПС записана единичная информация.

24. ГИ2 генератор тактовых импульсов 2.

25. ГИ3 генератор тактовых импульсов 3.

26. ГИ4 генератор тактовых импульсов 4.

27. ГИ5 генератор тактовых импульсов 5.

28. ПКС команда "защелки", поступающая на С-вход Д-триггера блока БПОС.

29. СОВ сигнал совпадения букв, следующих в алфавитном порядке с буквами слов, находящихся в блоке регистров слов.

30. ВК1 команда выбора кристалла ЗУ1 блока организации подстановок.

31. ЗП/СЧ1 команда записи/считывания ЗУ1 блока организации подстановок.

32. УВ команда, определяющая выбор информационного сигнала в регистре - ключе RG блока организации подстановок.

33. ВК2 команда выбора кристалла ЗУ2 блока организации подстановок.

34. ЗП/СЧ2 команда записи/считывания ЗУ2 блока организации подстановок.

35. ВС команда, определяющая одноразовые совпадающие буквы алфавитного порядка с буквами слов блока регистров слов.

36. СБ1 команда сброса счетчика строк ЗУ1 и ЗУ2 блока организации подстановок.

37. СБ2 команда сброса счетчиков столбцов ЗУ1 и ЗУ2 блока организации подстановок.

38. СУ1 команда управления 1, поступающая на управляющий вход схемы конъюнкции 1 блока организации подстановок.

39. СУ2 команда управления 2, поступающая на управляющий вход схемы конъюнкции 2 блока организации подстановок.

40. МАГ информационная магистраль, по которой идут слова текста.

41. СЛ информационный вход, поступающий от информационной магистрали в блок регистров слов.

42. ПБ кодовая комбинация буквы алфавита, поступающая на вход RG регистра ключа блока организации подстановок.

43. МС кодовая комбинация буквы, поступающая из блока регистров слов в блок компарации.

44. ВСИ информационный выход стековой памяти блока стековой памяти.

45. ПМР информационный выход счетчика СчПР, поступающий на вход регистра RG2 блока стековой памяти.

46. ЧПС информационный выход блока подсчета одинаковых слов и представляет собой подсчет количества одинаковых слов в тексте.

47. АСЛ адреса столбцов, поступающих в ЗУ1 и ЗУ2.

48. АСК адреса строк, поступающих в ЗУ1 и ЗУ2.

49. АВАР.ОСТ. аварийный останов устройства.

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

51. ОСП признак отсутствия информации в блоке регистров слов.

52. МИХ мультиплексор устройства блока регистров слов.

53. СП стековая память устройства блока стековой памяти.

54. ВДП информационный выход регистра-ключа блока стековой памяти, поступающего на вход "данные" стековой памяти.

55. СчПР счетчик, синтезирующий адресные входы.

56. СчПС счетчик, определяющий количества совпадений буквы алфавита и букв слов блока регистров слов.

57. БМП информативный выход регистра ключа RG блока организации подстановок.

58. ВПР информационный выход регистра RG2 блока стековой памяти.

59. СбСч сигнал сброса счетчика блока определения одноразового вхождения.

60. ПРБ признак пробела, т.е. код (знак), обозначающий расстояние между концом одного слова и началом другого.

61. ГИ6 генератор тактовых импульсов 6.

62. СОТ информационный выход системы ключей блока поиска вхождений.

63. БС информационные выходы регистров блока регистров слов.

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

65. ВИС информационный выход регистра RG1 блока стековой памяти.

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

67. СБР сигнал сброса счетчика-регистра блока компаратора.

68. ОСТ информационный выход канала, поступающий на вход блока поиска вхождений и представляющий собой код первой буквы слова в тексте.

69. ВПР адресный вход, поступающий на управляющие входы мультиплексора блока 2 регистров слов.

70. СчАз счетчик, синтезирующий адреса стековой памяти.

71. СчЧПС счетчик подсчета одинаковых слов в тексте.

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

Содержательная ГСА управления приведена на (фиг.11) и отражает работу блока управления (фиг.1). По сигналам управления "УОО" или "ПУСК" (блоки 2,4
ГСА) происходит установка в нуль всех элементов памяти устройства по командам "СБРОС:1", "ПУСК:1" соответственно (блоки 3,5).

В блоке 6 по команде "СОБ:0" происходит установка в нуль компаратора в блоке 3 компарации, т.е. компаратор готов к работе, на его выходе нуль, последовательный "опрос" регистров блока регистров слов еще не начался. По команде "ВС:0" происходит обнуление счетчика Сч.ПС, определяющего количество совпадений букв алфавита и букв регистров слов. По команде "КР:0" происходит первоначальная установка в нуль счетчика СчПР блока стековой памяти, т.е. на мультиплексор не подаются управляющие сигналы, "опроса" данных регистра блока БРС не происходит. По команде "РП:0" происходит обнуление регистра блока регистров слов (фиг.1). По команде "БПС:1" происходит анализ стековой памяти. Буфер стековой памяти пуст и готов к работе.

В блоке 7 происходит анализ признака конца текста. Если "КТ=0", то это означает, что текст весь просмотрен, и, если обнаружены слова на заданную букву алфавита, то происходит сортировка слов в алфавитном порядке. Если "КТ=1" это означает, что текст еще не закончился и идет процесс отбора слов, начинающихся на определенную букву. При "КТ:0" осуществляется переход на блок 14 алгоритма управления.

В блоке 8 происходит анализ признака пробела между словами текста. Если "ПРБ= 0", т. е. нет пробела (идет слово по магистрали), то при этом осуществляется переход на блок 9, в котором по команде "СКЛ:0" происходит подача на управляющие входы системы ключей блока поиска вхождений нуля и тем самым пpоисходит блокировка системы ключей. Из блока 9 осуществляется переход на блок 8 до тех пор, пока не "придет" пробел. Если "ПРБ=1", т.е. пришел по тексту пробел между словами текста, это означает, что необходимо сравнение первой буквы "идущего" слова с заданной буквой алфавита.

В блоке 10 по команде "СКЛ:1" происходит подача на управляющий вход системы ключей единицы, при этом первая буква слова поступает на вход компаратора блока поиска вхождений.

В блоке 11 происходит анализ признака сравнения поступившей первой буквы слова с заданной буквой алфавита, хранящейся в регистре RG блока поиска вхождений. Если "СПБ=0", т.е. совпадения букв не произошло, то осуществляется переход на блок 8. Если "СПБ=1", т.е. совпадение букв произошло, то происходит загрузка этого слова в регистр блока регистров слов (фиг.3).

В блоке 12 по команде "ВК1:1" происходит подача единицы на вход, выбор кристалла запоминающего устройства 1 блока организации подстановок (фиг.1). По команде "ЗП/Сч1:1" происходит подача единицы на вход "запись/считывание" запоминающего устройства 1 блока организации подстановок (фиг.10). По команде "УВ: 1" происходит подача единицы на управляющий вход регистра RG блока организации подстановок и означающий, что на вход регистра поступает информационный сигнал "ПБ". По команде "УП1:1" происходит подача единицы на управляющий вход схемы коньюнкции 1 блока организации подстановок (фиг.10). По команде "УП2: 1" происходит подача единицы на управляющий вход схемы конъюнкции 1 блока организации подстановок (фиг.10). По команде "УП2:1" происходит подача единицы на управляющий вход схемы конъюнкции 2 блока организации подстановок (фиг.10). По команде "БОП:ПБ" происходит запись в ЗУ1 блока организации подстановок первой буквы поступившего слова в блок регистров слов (фиг.1).

В блоке 13 происходит подача по команде "ЗАП:"=1" единицы на вход "ЗАПИСЬ" блока регистров слов. По команде "БРС:Сл" происходит запись в блок регистров слов поступившего слова, первая буква которого совпадает с заданной буквой алфавита. Из блока 13 осуществляется переход на блок 7.

В блоке 14 алгоритма происходит анализ признака РСП т.е. наличие информации (слов) в блоке регистров слов. Если "РСП=0", это означает, что регистр блока БРС пуст и при этом осуществляется переход на блок 42 алгоритма. Если "РСП=1", это означает, что в регистре блока регистров слов есть слова и их необходимого упорядочить в алфавитном порядке, т.е. начало процесса сортировки.

В блоке 15 алгоритма по команде "СВ:1" происходит выбор информации, при этом на выход регистра RG2 блока стековой памяти поступит информационный сигнал ПМР, представляющий собой управляющие входы мультиплексора блока регистров слов (фиг.5).

В блоке 16 алгоритма по команде "ГИ2:1" происходит подача тактовых импульсов на вход счетчика-регистра блока компарации. По команде "БК:КБ" происходит подача на вход компаратора блока компарации информационного сигнала КБ, который является выходом счетчика-регистра блока компарации (фиг.4).

В блоке 17 алгоритма по команде "ГИ2:0" происходит прекращение подачи тактовых импульсов на вход счетчика-регистра блока компарации. По команде "ГИ1: 1" происходит подача тактовых импульсов на вход счетчика СчПр блока стековой памяти для формирования адресов, которые являются управляющими входами мультиплексора блока регистров слов.

В блоке 18 алгоритма происходит анализ признака "СВ" выбора информации, поступающей на вход RG2 блока стековой памяти. Если "СВ=1", то на выходе регистра RG2 блока стековой памяти будет информационный сигнал "ПМР", являющийся выходом счетчика СчПР блока стековой памяти (фиг.5). Если "СВ=0", то на выходе регистра RG2 блока стековой памяти будет информационный сигнал "ВСИ", являющийся выходом стековой памяти (фиг.5).

В блоке 19 алгоритма по команде "МИХ:ПМР" происходит подача на управляющие входы мультиплексора адреса "ПМР" опроса регистра блока регистров слов. По команде "БК:МС" происходит подача мультиплексором информационного сигнала (код буквы) и принятие этой информации компаратором блока компарации.

В блоке 20 алгоритма происходит анализ признака КР (конец регистров), который определяет конец просмотра всех регистров блока регистров слов. В последний регистр блока будет записана единичная информация, которая и является признаком конца опроса всех регистров блока регистров слов. Если "КР= 1", то это означает признак конца регистров, т.е. все регистры просмотрены. Если "КР=0", то это означает, что не все регистры блока регистров слов просмотpены и "просмотр" продолжается, при этом осуществляется переход на блок 30 алгоритма.

В блоке 21 алгоритма происходит анализ признака ВС, определяющий одноразовое совпадение буквы алфавита с буквами слов блока регистров слов. Если "ВС= 0", то либо совпадений совсем не было, либо были совпадения, но более одного раза, при этом происходит переход на блок 23 алгоритма. Если "ВС=1", то совпадение букв произошло только один раз, и это означает, что это слово, в котором произошло совпадение один раз, сразу может быть записано в блоке организации подстановок (фиг.1), т.е. место этого слова в алфавитном упорядочении слов найдено.

В блоке 22 алгоритма по команде "ВД:1" происходит подача единицы на вход регистра блока регистров слов, при этом осуществляется выдача из регистра блока всей информации (всего слова) в блок организации подстановок. По команде "УВ:0" происходит передача на выход регистра RG блока организации подстановок информационного сигнала "СЧ", т.е. с выхода мультиплексора блока регистров слов. По команде "ИЗ: 1" происходит подача единицы на вход "ИЗВЛЕЧЬ" счетчика адреса (Сч Ад) блока стековой памяти для извлечения адреса из блока стековой памяти. По команде "ЗC:0" происходит подача нуля на вход "ЗАСЛАТЬ" счетчика адреса (Сч Ад) блока стековой памяти. По команде "СВ:0" происходит подача нуля на управляющие входы регистра RG2 блока стековой памяти. При этом на выход регистра RG2 поступает информационный сигнал "ВСИ", являющийся выходом стековой памяти. По команде "БОП:МС" происходит прием блоком организации подстановок информационного сигнала "МС", являющегося выходом мультиплексора блока регистров слов (фиг.3).

В блоке 23 алгоритма происходит анализ признака СОВ, при котором определяется, было ли совпадение буквы алфавита с буквами слов, находящихся в регистрах блока регистров слов. Если "СОВ=1", это означает, что совпадение было, и при этом осуществляется переход на блок 29 алгоритма. Если "СОВ=0", это означает, что совпадений не было и следует дальше продолжать просмотр букв слов, находящихся в регистрах блока регистров слов.

В блоке 24 алгоритма по команде "ССч:1" происходит обнуление счетчика СчПР.

В блоке 25 алгоритма происходит анализ признака БПС, при котором происходит анализ содержимого стековой памяти. Если "БПС=1", это означает, что буфер стековой памяти пуст. Если "БПС=0", это означает, что буфер стековой памяти не пуст, в нем находится информация (адреса слов), при этом осуществляется переход на блок 27 алгоритма.

В блоке 26 алгоритма происходит анализ признака БПЛ, при котором происходит анализ содержимого стековой памяти. Если БПЛ=0", это означает, что буфер стековой памяти неполон, при этом осуществляется переход на блок 29 алгоритма. Если "БПЛ= 1", это означает, что буфер стековой памяти полон, поэтому осуществляется при этом переход на блок 28 (перестраховаться от переполнения).

В блоке 27 алгоритма по команде "СВ:1" происходит подача единицы на управляющий вход регистра RG2 блока стековой памяти. При этом осуществляется передача на выход этого регистра (RG2) входного информационного сигнала ПМР, который является выходной информацией счетчика СчПР блока стековой памяти. При этом осуществляется переход на блок 16 алгоритма.

В блоке 28 алгоритма вырабатывается сигнал АВАР.ОСТ (аварийный останов работы устройства), это выполняется в случае переполнения буфера стековой памяти.

В блоке 29 алгоритма по команде "СВ:0" происходит подача нуля на управляющий вход регистра RG2 блока стековой памяти. При этом осуществляется передача на выход этого регистра (RG2) входного информационного сигнала "ВСИ", который является выходной информацией буфера стековой памяти (фиг.6). При этом осуществляется переход на блок 18 алгоритма.

В блоке 30 алгоритма происходит анализ признака СОВ, при котором определяется, было ли совпадение буквы алфавита с буквами слов, находящимися в регистрах блока регистров слов. Если "СОВ=1", это означает, что совпадение было. Если "СОВ= 0", это означает, что совпадений не было, и при этом осуществляется переход на блок 33 алгоритма.

В блоке 31 алгоритма происходит анализ признака "СВ" выбора информации, поступающей на вход регистра RG2 блока стековой памяти. Если "СВ=1", то на выходе регистра RG2 блока стековой памяти будет информационный сигнал "ПМР", являющийся выходом счетчика СчПР блока стековой памяти (фиг.5). Если "СВ=0", то на выходе регистра RG2 блока стековой памяти будет входной информационный сигнал "ВСИ", являющийся выходом стековой памяти (фиг.1). При этом осуществляется переход на блок 34 алгоритма.

В блоке 32 алгоритма по команде "ЗСЧ:1" происходит подача на один из управляющих входов регистра-ключа (RC-КЛ) блока стековой памяти единицы. По команде "ЗВ:0" происходит подача на второй управляющий вход регистра-ключа (RG-КЛ) блока стековой памяти нуля. В результате действия этих команд на выход регистра-ключа (RG=КЛ) поступает входной информационный сигнал +ПМР", т. е. происходит выбор входной информации на выход регистра-ключа блока стековой памяти. По команде "ЗС:1" происходит подача на вход "ЗАСЛАТЬ" счетчика адресов стековой памяти единицы. При этом осуществляется засылка в стековую память данных с входа регистра-ключа блока стековой памяти. По команде "СП: ВДП" происходит принятие информации с выхода регистра-ключа в стековую память блока стековой памяти. По команде "СчПС:ГИЗ" происходит подача тактовых импульсов на вход счетчика, определяющего количество совпадений буквы алфавита и букв блока регистров слов, блока определения одноразового вхождения (фиг.9).

В блоке 33 алгоритма по команде "ГИ1:1" происходит подача тактовых импульсов на вход счетчика (СчПР) блока стековой памяти. По команде "СВ:1" происходит подача единицы на управляющий вход регистра RG2 блока стековой памяти. При этом осуществляется передача на выход этого регистра входного информационного сигнала "ПМР", который является выходной информацией счетчика СчПр блока стековой памяти. При этом осуществляется переход на блок 18 алгоритма.

В блоке 34 алгоритма по команде "СУР:1" происходит подача на С входы регистра RG1 блока стековой памяти единичного разрешающего сигнала для записи в этот регистра информационного сигнала "ВСИ", являющегося выходом стековой памяти. По команде "RG1:ВСИ", происходит загрузка регистра RG1 блока стековой памяти информационным сигналом "ВСИ". В этом регистре содержится информация, поступившая из стековой памяти (фиг.5).

В блоке 35 алгоритма по команде "СУР:0" происходит подача на С входы регистра RG1 блока стековой памяти нулевого запрещающего сигнала. Регистр RG1 хранит поступившую на его входы информацию. По команде "ЗСЧ:0" происходит подача на первый управляющий вход регистра-ключа блока стековой памяти нуля (фиг. 5). По команде "ЗВ:0" происходит подача на второй управляющий вход регистра-ключа блока стековой памяти нуля (фиг.5). В результате этих команд на выходе регистра-ключа блока стековой памяти формируется нулевая информация, т. е. на выходе регистра нули. По команде "ВДП:0" происходит подача на вход "ДАННЫЕ" стековой памяти нулевой информации.

В блоке 36 алгоритма по команде "ЗС: 1" происходит подача на вход "ЗАСЛАТЬ" счетчика адресов блока стековой памяти единицы. При этом нулевая информация с выхода регистра-ключа записывается в стековую память. Происходит пересылка адресов, данные которых (буквы слов в регистре блока регистров слов) "совпали" с буквой алфавита при компарации. При этом таких совпадений было не одно. По команде "ЗВ:1"происходит подача на второй управляющий вход регистра-ключа блока стековой памяти единицы (фиг.5). При этом на выход этого регистра поступит информация "ВСИ" с выхода регистра RG1 блока стековой памяти. По команде "ВДП:ВСИ" происходит подача на вход "ДАННЫЕ" стековой памяти информационного сигнала "ВСИ", который хранился в регистре RG1 блока стековой памяти (фиг. 5). По команде "СУР:1" происходит подача на С входы регистра RG1 блока стековой памяти единичного разрешающего сигнала для того, чтобы содержимое этого регистра перезаписалось через регистр-ключ в буфер стековой памяти (фиг. 5). По команде "СчПС:ГИЗ" происходит подача на вход счетчика СчПС блока определения одноразового вхождения (фиг.9) тактовых импульсов. Это необходимо для подсчета количества совпадений в блоке компарации. По команде "СД:1" происходит сдвиг содержимого слова в регистре блока регистров слов на один разряд вправо. Это происходит тогда, когда произошло совпадение буквы алфавита с буквой этого слова. Поэтому содержимое регистра сдвигается на один разряд вправо. При этом осуществляется переход на блок 41 алгоритма.

В блоке 37 алгоритма по команде "ИЗ:1" происходит подача единицы на вход "ИЗВЛЕЧЕНИЕ" счетчика адресов блока стековой памяти для извлечения из буфера стековой памяти очередного адреса слова, находящегося в блоке регистров слов. По команде "БРС:ВСИ" происходит прием блоком регистров слов информационного сигнала "ВСИ" с выхода стековой памяти. При этом происходит подача на управляющие входы мультиплексора блока БРС адреса слова, в котором произошло совпадение одной из его букв с буквой алфавита. По команде "БК:МС" происходит прием блоком компарации информационного выхода мультиплексора для сравнения с буквой алфавита (фиг.4).

В блоке 38 алгоритма происходит анализ признака "КС" конца слова. Конец слова в регистре блока регистров слов будет закодирован нулевой информацией. Как только на выходе схемы ИЛИ блока компарации возникнет нуль это и является признаком конца слова, находящегося в регистре блока регистров слов (фиг.4). Если "КС=1", это означает, что конца слова нет, в этом регистре еще находится слово и необходимо вести дальнейшую обработку этого слова. При этом осуществляется переход на блок 20 алгоритма. Если "КС=0", это означает, что данное слово все просмотрено (все буквы этого слова "просмотрены"), т.е. на выходе схемы ИЛИ блока компарации нулевая информация.

В блоке 39 алгоритма по команде "ПКС:1" происходит подача на вход С D-триггера единичного сигнала, т.е. разрешения для записи в этот триггер информационного сигнала, поступающего с выхода схемы ИЛИ блока подсчета одинаковых слов, на вход которой поступает информационный сигнал "ВСИ" с выхода стековой памяти (фиг.8) блока стековой памяти. По команде "БПОС:ВСИ" происходит прием блоком подсчета одинаковых слов информационного сигнала "ВСИ", являющегося выходом стековой памяти блока стековой памяти. По команде СчЧПС: ГИ4 происходит подача на вход счетчика СчЧПС блока подсчета одинаковых слов тактовых импульсов через схему И, управляющим входом которой является выход D-триггера, а информационным входом является выход генератора тактовых импульсов четвертый.

В блоке 40 алгоритма по команде "БОП:СчЧПС" происходит прием блоком организации подстановок ЗУ2 информационного сигнала, являющегося выходом счетчика СчЧП блока подсчета одинаковых слов. В блок организации подстановок в ЗУ2 поступает информация о частоте поторяемости одного слова в тексте. При считывании слов, упорядоченных в алфавитном порядке, из ЗУ1 блока организации подстановок также будет считана информация из ЗУ2 о частоте повторяемости этих слов в тексте.

В блоке 41 алгоритма по команде "СВ:0" происходит подача нуля на управляющий вход регистра RG2 блока стековой памяти. При этом осуществляется передача на выход этого регистра RG2 входного информационного сигнала "ВСИ", который является выходной информацией буфера стековой памяти (фиг.5). При этом осуществляется переход на блок 18 алгоритма.

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

Все 31 единичные устройства соединены между собой общим каналом, по которому поступают слова текста в закодированном виде, т.е. каждая буква алфавита будет иметь свой код. Знаки препинания (запятая, точка и т.д.) при этом не рассматриваются. Свой определенный код имеет пробел между словами, который разрешит поступление кода первой буквы очередного слова текста в единичное устройство.

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

Из канала в блок 1 поиска вхождений поступает информационный сигнал "ОСТ" (код первой буквы слова) (фиг.2). Канал представляет собой шины, по которым поступают коды букв в устройство. В регистре RG1 блока 1 поиска вхождений находится код пробела. Если на второй вход компаратора 1 поступил код пробела из текста, а на первом входе компаратора 1 постоянно находится код пробела, то единичный выход (при этом компаратор выдает сигнал "единицу") "откроет" систему ключей этого блока (подачей на управляющие входы системы ключей отпирающего единичного сигнала). В регистре RG2 блока 1 поиска вхождений содержится код определенной заранее первой буквы слова. К примеру, код буквы "П". Это означает, что данное единичное устройство будет отбирать из текста только слова, начинающиеся на букву "П", то система ключей блока будет заперта нулевым сигналом, поступившим с выхода компаратора 1 блока 1. Если первая буква слова "П", то код этой буквы через систему ключей подается на второй вход компаратора 2 блока 1 поиска вхождений. На первом входе компаратора 2 находится код буквы "П". Тогда компаратор 2 блока 1 вырабатывает единичный сигнал СПБ (сигнал совпадения первой буквы поступившего слова текста с определенной буквой алфавита). Этот сигнал поступает на вход блока управления 8. При этом из регистра RG2 блока 1 код первой буквы поступит в блок 7 организации подстановок. Всегда первая буква слова (в нашем случае буква "В") будет поступать в блок 7 организации подстановок, минуя блок 2 регистров слов. По приходу единичного сигнала СПБ в блок управления остальные буквы этого слова (без первой буквы) должны быть записаны и храниться в блоке 2 регистров слов.

Блок 2 регистров слов (фиг.3) представляет собой регистровую память, состоящую из n сдвигающих регистров, на входы которых поступают слова, начинающиеся, например, на букву "А". Каждое слово будет записано в один определенный регистр. Все регистры будут сдвигающими информацию на один разряд вправо. Незадействованные разряды регистра, т.е. область памяти слева от слова, будут заполнены нулями. Итак, содержимое каждого регистра будет разбито на две части: первую информационную и вторую нулевую. Нулевая информация используется для определения конца первой информационной части, т.е. для определения конца слова.

На вход каждого регистра из блока управления поступают сигналы ЗАП, ВД, СД, которые означают: ЗАП1 запись в первый регистр, ВД1 выдача информации из регистра 1, СД1 сдвиг информации регистра 1 на одну позицию вправо и т.д. При обнаружении первого слова, начинающегося на букву "П" (пример), сигнал ЗАП1 будет установлен в единичное состояние и произойдет запись первого слова в регистр RG1 блока 2 регистров слов. Второе слово будет записано во втором регистре RG2 этого блока и т.д. до тех пор, пока все слова текста на букву "П" не будут записаны в регистры блока 2. Канал информационными выходами СЛ1, СЛ2.СЛn соединен с каждым регистром блока 2. Все информационные выходы регистров блока 2 являются информационными входами мультиплексора "МИХ" этого же блока.

На управляющие входы мультиплексора подается сигнал "ВПР", который будет адресным входом мультиплексора. Сигнал "ВПР" будет представлять собой номер выбранного регистра, в котором находится слово. Работа этого блока заключается в следующем: все слова текста, начинающиеся, например, на букву "П", будут записаны в блок 2 регистров слов, но без первой буквы "П". Порядок записи букв слова в регистр обычный (вторая буква слова будет записана первой и будет занимать самое крайнее правое положение, третья буква будет второй справа и т.д.). При поступлении на вход мультиплексора адресного сигнала "ВПР" на выход мультиплексора поочередно будут поступать коды букв. На первом этапе будет проходить поочередный "опрос" вторых букв слов, начиная с первого регистра и до предпоследнего. В самом последнем регистре блока 2 регистров слов будет находиться единичная информация, т.е. все единицы (111. 1). Эта информация необходима для определения признака конца слов, начинающихся на букву "П" (пример). В регистре RGn будут только единицы признак конца слов на определенную букву алфавита. ИНформационный выход мультиплексора блока 2 будет являться информационным входом блока компарации, а также блока организации подстановок.

Блок 3 компарации (фиг.4) представляет собой: компаратор КОМ, счетчик-регистр СчРг, комбинационную схему ИЛИ и комбинационную схему И. По приходу из блока 8 управления сигнала "ГИ2" в блок 3 компарации на вход счетчика-регистра "СчРг" подаются тактовые импульсы от генератора. В исходном состоянии на счетчике-регистре будет записан код первой буквы алфавита. Информационный выход счетчика-регистра СчРг является первым входом компаратора "КОМ". На второй вход компаратора поступают коды букв слов, находящихся в блоке 2 регистров слов (фиг.3). На этом этапе происходит сравнение первой буквы алфавита со вторыми буквами слов, находящихся в регистрах блока 2 (фиг.3). Происходит последовательное сравнение букв со всеми первыми по записи в регистры ( в слове они являются вторыми по порядку) буквами слов. Осуществляется поиск тех слов, у которых вторая буква (после "П") является первой буквой алфавита. При сортировке слов в алфавитном порядке, если первые буквы одинаковы, то рассматриваются следующие по порядку буквы. Итак, при мультиплексировании букв в блоке 2 регистров слов они в блоке 3 компарации будут сравниваться с буквами, идущими в алфавитном порядке.

Сигнал "СОВ", являющийся выходом компаратора, поступает на вход блока 8 управления. Если "СОВ" равен единице, это означает, что произошло совпадение первой буквы алфавита (рассматривается этот этап) со второй буквой слов, находящихся в регистрах RG1 RGn, номер которого определяет адресный вход мультиплексора.

Комбинационная схема ИЛИ определяет признак "КС" конца слова (фиг.1,4) в каждом из регистров блока 2 регистров слов. Как известно, признаком конца слова является нулевая информация. Если сигнал "КС" будет равен нулю, то это означает, что буквы слова закончились. При этом информационная часть закончена, т.е. все буквы слова просмотрены ("опрошены") и в блоке 3 компарации откомпарированы с последовательностью идущих букв алфавита. Если сигнал "КС" равен единице, то в регистре находятся еще буквы слова и процесс опроса регистров будет продолжен.

Комбинационная схема И осуществляет поиск признака конца слов. Как уже отмечалось выше, в последнем регистре блока 2 регистров слов будет помещен признак конца слов единичная информация (111.1). Если сигнал "КР" будет равен единице, это означает, что все, скажем, вторые буквы слов просмотрены и процесс должен повториться заново. Если "КР" равен нулю, то это означает, что не все буквы просмотрены и процесс опроса должен продолжаться. Сигналы "КС" и "КР" поступают на вход блока 8 управления.

Сигнал "СБР" является сигналом сброса счетчика-регистра блока 3 компарации, и по приходу этого сигнала из блока 8 управления счетчик-регистр обнуляется. Сигнал "СБР" установка в нулевое состояние счетчика-регистра.

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

Блок 4 стековой памяти (фиг.5) представляет собой счетчик адресов СчПР; регистр RG1 (фиг.6); регистр RG2 (фиг.6); ключ-регистр RG-КЛ (фиг.7); счетчик СчАЗ, формирующий адреса стековой памяти; стековую память СП; инкрементор INC. выполняющий роль сдвига на единицу адреса записи относительно адреса чтения; комбинационную схему И, выполняющую роль обнаружения состояния "Буфер полон"; комбинационную схему ИЛИ-НЕ, выполняющую роль обнаружения состояния "Буфер пуст".

Стековая память реализует буфер типа "магазин" (типа LIFO). По приходу из блока 8 управления сигнала "ГИ1" счетчик СчПР формирует адреса (номера регистров в блоке 2 регистров слов), которые поступают на первый вход регистра RG2 блока стековой памяти и на первый вход регистра-ключа RG-КЛ блока стековой памяти (фиг.5). По приходу сигнала Ссч из блока 8 управления счетчик СчПР сбрасывается в нуль, т.е. на выходе нулевая информация. По приходу из блока 8 управления сигнала "ЗС" будет выполнена команда "Заслать в стек". По приходу из блока 8 управления сигнала "ИЗ" будет выполнена команда "Извлечь из стека".

Сигналы "ЗВ" и "ЗСЧ", поступающие из блока 8 управления, являются управляющими сигналами регистра-ключа RG-КЛ блока 4 стековой памяти (фиг.7). При "ЗСЧ"= 1, а "Зв"=0 на выходе регистра-ключа будет первый информационный вход "ПМР", являющийся выходом счетчика адресов СчПр. При "ЗСЧ"=0, а "Зв"=1 на выходе регистра-ключа будет второй информационный вход "ВИС". При "ЗСЧ"=0 и "ЗВ"= 0 на выходе регистра-ключа будет нулевая информация, также необходимая для записи в стековую память. Итак, при двоичной комбинации 1 0 управляющих сигналов на входе стековой памяти адреса счетчика, при 0 1 на входе стековой памяти информация регистра RG1, при 0 0 на входе нулевая информация, комбинация 1 1 исключена.

Регистр-ключ RG-КЛ блока стековой памяти (фиг.7) состоит из комбинационных схем И и комбинационных схем ИЛИ. Информационный сигнал "ПМР" подается на входы схем И, обозначенных как И11, И12,И11. Управляющим сигналом для этих схем И является сигнал "ЗСЧ", формирующийся в блоке 8 управления (фиг. 1). Поэтому, когда "ЗСЧ"=1, на входах схем ИЛИ будет информационный сигнал "ПМР", соответствующие комбинационные схемы И при этом открыты, они выполняют роль ключа "ВДП:ПМР" (фиг.7). Информационный сигнал "ВИС" подается на входы схем И, обозначенных как И21, И22,И21. Управляющим сигналом для этих схем И является сигнал "ЗВ", формирующийся в блоке 8 управления (фиг.1). При "ЗВ"= 1 на выходах схем ИЛИ будет информационный сигнал "ВИС", соответствующие комбинационные схемы И при этом открыты, они также выполняют роль ключа "ВДП: ВИС". При "ЗВ" и "ЗСЧ", равных нулю, на выходах всех комбинационных схем И будут нули, на выходах схем ИЛИ также нули, при этом "ВДП:0" (фиг.7).

Сигнал "СУР", поступающий из блока 8 управления, является сигналом "защелки" регистра RG1. Регистр RG1 представляет собой D-триггера. Сигнал "СУР" подается на управляющие входы с D-триггеров регистра. На входы D-триггеров поступает информационный выход стековой памяти.

Блок 8 управления формирует единичный сигнал "СВ", являющийся управляющим входом регистра RG2 блока стековой памяти. Регистр RG2 (фиг.6) состоит из комбинационных схем И с прямыми входами, комбинационных схем И с одним инверсным входом и комбинационных схем ИЛИ. Если "СВ"=1, то для схем И с прямыми входами этот сигнал будет разрешающий (отпирающий схему). А для схем И с одним инверсным входом этот сигнал будет запрещающий (запирающий схему). При этом на выходе этого регистра будет информационный сигнал "ПМР", поступающий только на входы схем И с прямыми входами. Если "СВ"=0, то схемы И с прямыми входами будут "заперты", т.к. на управляющие входы схем И подается 0, а схемы И с инверсным входом будут "открыты". В этом случае на выходе регистра RG2 будет информационный сигнал "ВСИ", который поступает только на входы схем И с инверсным входом. Информационный сигнал "ПМР" поступает на входы схем И, имеющих обозначение на фиг.6 И11, И12.И1k. Информационный сигнал "ВСИ" поступает на входы схем И с одним инверсным входом, имеющих обозначение на фиг.6 И21, И22,И2k. На вход схемы ИЛИ1 поступают выходы схем И11 и И12. Поэтому на выходе схемы ИЛИ1 будет функция .

Работа блока стековой памяти (фиг. 5) заключается в следующем: после того, как в блоке 3 компарации будет обнаружено совпадение, т.е. сигнал "СОВ=1" (фиг.4) адрес этого регистра, в котором произошло совпадение блока 2 регистров слов (фиг. 3), будет записан в стековую память (фиг.5) блока 4 стековой памяти при одном и том же цикле "опроса". Циклом "опроса" мы будем называть цикл, при котором происходит опрос всех регистров блока 2 регистров слов (фиг. 3) от начала до последнего регистра, в котором находится признак конца слов (111.1) при неизменном коде счетчика-регистра СчРг блока 3 компарации (фиг.4). Происходит сравнение, скажем, всех вторых (третьих, четвертых и т. д. ) букв слов, находящихся в регистрах блока 2 регистров слов с кодом одной определенной буквы алфавита, находящимся в счетчике-регистре СчРг блока 3 компарации (фиг.4).

Всякий раз в одном цикле "опроса", как только произошло сравнение, адрес (номер) регистра этого слова будет записан в стековую память блока 4 стековой памяти (фиг.5). Работу блока 4 на этом цикле хорошо иллюстрирует пример. Мы отобрали из текста слова, начинающиеся на букву П. Скажем, это слова:
П А Р Т А
П О Р Т Р Е Т
П О Л Е
П А Р
П И Р
П А Р А Ш Ю Т
П Е Н А Л
П И Р О Г
П О Л Е
Конечная наша цель упорядочение этих слов в алфавитном порядке. В счетчик-регистр СчРг блока 3 компарации будет записан код буквы А. Эти слова на букву П будут записаны в регистрах блока 2 регистров слов (фиг.3) в виде:
А Т Р А
Т Е Р Т Р О
Е Л О
Р А
Р И
Т Ю Ш А Р А
Л А Н Е
Г О Р И
Е Л О
Буквы П при этом (их 9, т.к. 9 слов) будут сразу же записаны в блок 7 организации подстановок. На первом этапе, в течение одного цикла "опроса", мы будем иметь три раза совпадения буквы А со вторыми буквами слов: это первое, четвертое и шестое слово. Все эти три адреса первый, четвертый и шестой будут записаны в стековую память блока 4 стековой памяти (фиг.5). Нам необходимо упорядочить в алфавитном порядке сначала только эти три слова. Поэтому, как только мы опросим все регистры, обнаружим признак конца слов. В счетчик-регистр ЧсРг блока 3 компарации будет занесен код второй буквы алфавита Б. Теперь происходит считывание адресов (номеров) регистров из стековой памяти и сравнение третьих букв этих трех слов с буквой Б. При этом, как только произошло совпадение в каком-либо регистре, происходит сдвиг информации этого регистра вправо на один разряд. Сдвиг произошел в регистрах первом, четвертом и шестом. В остальных регистрах информация в первоначальном состоянии:
0 0 0 0 0 А Т Р
0 0 Т Е Р Т Р О
0 0 0 0 0 Е Л О
0 0 0 0 0 0 0 Р
0 0 0 0 0 0 Р И
0 0 0 Т Ю Ш А Р
0 0 0 0 Л А Н Е
0 0 0 0 Г О Р И
0 0 0 0 0 Е Л О
На адресные входы мультиплексора поступит номер шесть, т.к. он будет записан первым в стековую память (тип LIFO) и считан будет первым. При этом в блоке 4 стековой памяти "ВПР:ВСИ" (фиг.5). Вторая буква шестого слова будет сравниваться в блоке 3 компарации с буквой Б. Сравнение не произошло. Считывается из стековой памяти вторая буква четвертого слова. Сравнения тоже нет. Считывается вторая буква первого слова. Сравнения тоже нет. Считывать из стековой памяти будем столько раз, сколько раз произошло совпадение. Блок 8 управления ведет подсчет количества совпадений. В нашем случае совпадений было 3, поэтому считали три раза. Если было бы одно совпадение и только одно из трех слов, то при этом сразу же это слово (где возникло совпадение) было бы переписано в блок 7 организации подстановок. В этом регистре блока 2 регистров слов будут записаны нули и по соответствующему адресу стековой памяти тоже будут записаны нули. Каждый раз, когда будет считан адрес из стековой памяти, он также будет записан в регистр RG1 блока 4 стековой памяти в D-триггера (фиг.6). После сравнения этот же адрес из регистра RG1 будет записан в стековую память под уже другим адресом, а прежний адрес при этом обнуляется (запишется нулевая информация при "ЗВ"=0 и "ЗСЧ"=0 в стековую память). В нашем примере пока совпадений нет. Как только будет выставлен код буква Р в счетчике-регистре СчРг, из стековой памяти будет считан адрес (номер) регистра, записанного в стековую память последним (тип LIFO), при этом в блоке 3 компарации (фиг.4) произойдет совпадение. Адрес при этом будет записан в стековую память под другим адресом. Считали второй адрес тоже совпадение, записали под другим адресом в стековую память. Считали третий адрес тоже совпадение, записали под другим адресом. При этом каждый раз будет осуществляться сдвиг вправо на одну позицию в регистрах, где содержатся первое, четвертое и шестое слова. Информация в регистрах блока 2 регистров слов будет следующей:
0 0 0 0 0 0 А Т
0 0 Т Е Р Т Р О
0 0 0 0 0 Е Л О
0 0 0 0 0 0 0 0
0 0 0 0 0 0 Р И
0 0 0 0 Т Ю Ш А
0 0 0 0 Л А Н Е
0 0 0 0 Г О Р И
0 0 0 0 0 Е Л О
Каждый раз, как будет обнаружено совпадение буквы алфавита с очередной буквой слова блока 2 регистров слов, эта буква из блока 2 будет записана в блоке 7 организации подстановок. Итак, как совпадение так запись этой буквы в блок 7 (фиг.1). При этом содержимое блока 7 организации подстановок будет иметь вид:

(Учитываются только те этапы, где произошли совпадения).

Первоначально должны быть отправлены в блок 7 те слова, у которых:
1) произошло совпадение буквы слова с буквой алфавита и только одно совпадение при просмотре, а затем сравнение в блоке 3 компарации всех регистров. Как только будет обнаружен признак конца слов в регистрах блока 2 регистров слов единичная информация (111.1) и было только одно совпадение это пеpвый признак, чтобы сразу же отослать это слово (где произошло совпадение) в блок 7 организации подстановок.

Слово уже будет находиться в блоке 7 организации подстановок (в процессе переписывания из блока 2 в блок 7). Если обнаружен признак конца этого же слова, т. е. нулевая информация (000.0). Все буквы этого же слова просмотрены, поэтому в этом регистре, где находилось это слово, будет нулевая информация и в стековой памяти блока 4 стековой памяти по последнему адресу, где находился адрес, будет записана нулевая информация.

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

Вернемся в нашему примеру. В четвертом регистре схемой ИЛИ блока 3 компарации обнаружен признак конца слова, сигнал "КС". Поэтому на первом месте (по первому адресу) в блоке 7 организации подстановок будет стоять слово, находящееся в четвертом регистре блока 2. Это слово ПАР. Остальные 2 слова имеют буквы, поэтому алфавитная сортировка будет продолжена между двумя этими словами до тех пор, пока не будет выполнен пункт 2 (см.выше).

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

Коротко говоря о работе блока 4 стековой памяти, можно отметить следующее. В блок 4 стековой памяти записываются номера регистров слов, имеющих одинаковую вторую букву слова. До тех пор, пока эти слова не будут преобразованы в алфавитном порядке по основным двум пунктам, мы не может обрабатывать остальные слова. Коды номеров этих регистров (где произошли совпадения) являются адресными входами мультиплексора блока 2 регистров слов (фиг.3). При этом происходит выборочный процесс считывания букв из регистров блока 2 (фиг. 3). Считываются буквы слов, имеющих одинаковую вторую букву. Сдвиг в регистре происходит всякий раз, как произошло совпадение буквы слова с буквой алфавита, при этом происходит запись этой буквы из регистров в блок 7 организации подстановок. Тем самым все слова в блоке 7 (фиг.10) как бы составляются из букв слов, находящихся в регистрах блока 2 регистров слов (фиг.3). После упорядочения этих слов (имеющих одинаковую вторую букву) соответствующие регистры в блоке 2 обнуляются, номера этих регистров в стековой памяти, записанные всякий раз под новым адресом также обнуляются в стековой памяти. Блок 4 стековой памяти снова готов к рабочему циклу. Если слово оказалось одно в регистрах с определенной буквой алфавита, то оно после записи номера регистра в стековую память сразу же записывается в блок 7 организации подстановок 9 (по пункту 1, см. выше). Адрес, по которому записан номер регистра, в стековой памяти тоже обнуляется. Остановкой работы единичного устройства является наличие нулей во всех регистрах блока 2 регистров слов (фиг.3).

Блок 5 подсчета одинаковых слов (фиг.8) представляет собой: комбинационную схему ИЛИ, D-триггер, комбинационную схему И и счетчик подсчета числа одинаковых слов в тексте, линию задержки. Как только будет обнаружен признак конца слова в регистре блока 2 регистров слов, необходимо подсчитать количество номеров регистров, в которых находятся одинаковые слова. Сколько номеров находится в стековой памяти, столько одинаковых слов в регистрах блока 2. Здесь имеются в виду номера регистров, в которых обнаружен признак конца слова "КС" (т.е. 000.0).

Информационный выход стековой памяти подается на вход комбинационной схемы ИЛИ, выход которой подается на вход D-триггера. Прямой выход триггера подается на первый вход схемы И, выход которой подается на суммирующий вход счетчика подсчета числа одинаковых слов в тексте. По приходу из блока 8 управления сигнала "ПКС= 1" в D-триггер записывается единица с выхода схемы ИЛИ. D-триггер переходит в единичное состояние, на прямом выходе триггера 1, которая является отпирающим потенциалом для схемы И. По приходу из блока 8 управления тактовых импульсов "ГИ4" и при высоком уровне на управляющем входе схемы И тактовый импульс поступает на суммирующий вход счетчика СчЧПС, который подсчитывает количество этих импульсов. Схема И играет роль ключа, управляющим входом является признак конца слова. Сигнал "КС" является признаком конца слова. Эот сигнал через линию задержки обнуляет счетчик СчЧПС после того, как информация "ЧПС", количество номеров, имеющих одинаковые буквы (тем самым одинаковые слова), будет записана в ОЗУ1 блока 7 организации подстановок, Итак, сколько номеров регистров, имеющих одинаковые слова, столько импульсов в счетчике СчЧПС подсчета числа одинаковых слов.

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

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

По приходу сигнала ЗП/Сч2 из блока 8 управления, который также является сигналом "Записи-Считывания" ОЗУ2. Если "Зп/Сч2:1" режим записи данных в ОЗУ2. Если "ЗП/Сч2:0" режим считывания данных из ОЗУ2.

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

Блок 8 управления синтезируется на основе ГСА алгоритма управления (фиг. 11) известным способом /2/. Размеченная ГСА работы блока 8 управления приведена на фиг.12. Обозначения представлены в табл.2 и 3. ТТТ1 ТТТ2 ЫЫЫ2 ЫЫЫ4 ЫЫЫ6 ЫЫЫ8 ЫЫЫ10

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

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