параллельная система поиска произвольных вхождений

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

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

Описание изобретения к патенту

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

Известно "Устройство для реализации подстановок с двухкомпонентными вхождениями" (а.с. N1667097, 1991 г., Бюл. 28) [9], позволяющее определить вхождения в представленном слове-образце.

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

Известно "Устройство для морфологического анализа слов естественных языков и языков "деловой прозы" (а.с. 1837327, 1993 г., Бюл. 32) [8], которое позволяет проводить морфологический анализ слов реальных языков на основе логических признаков принадлежности к классам словоформ.

В качестве прототипа выбрано "Устройство поиска вхождений" (патент 2150740, 2000 г. ) [7] , которое позволяет осуществлять поиск вхождений, представленных в четырех видах.

Задача заключалась в следующем:

1) расширить функциональные возможности поисковой системы,

2) упростить алгоритм блока управления,

3) повысить надежность работы параллельной системы поиска произвольных вхождений.

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

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

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

БПС - блок служит для хранения слов, в которых будут определяться вхождения.

БППВn - блоки служат для поиска вхождений произвольной структуры в словах-образцах.

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

Процессы поиска вхождений образца в обрабатываемом слове адекватно описываются в терминах языка регулярных выражений путем использования операций итерации и конъюнктивного следования (конкатенация) [1].

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

Если образец имеет повторение своих начальных фрагментов, то его форма записи будет иметь вид:

S={G}F (1)

где S - образец;

G - начальный повторяющийся фрагмент;

F - собственное окончание образца;

{} - обозначение операции "итерация".

Очевидно, что при существовании итерации фрагмента в середине образца при следующей форме его записи:

S=G{H}F (2)

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

S=G{F} (3)

В случае общего положения структура образца может принимать вид:

S={G}H(F} (4)

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

S=GFGP (5)

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

В выражениях (1), (2), (3), (4) и (5) S, G, F, Н и Р - произвольные непустые слова.

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

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

1) нет повтора одинаковых букв (итерации) в слове-образце, пример - "тиманел";

2) повтор одинаковых букв есть в середине слова-образца, пример - "вчсииииторг", при этом принято обозначение B{W}D;

3) итерация существует в конце слова, пример - "лдшгпсссс", обозначение B{W};

4) итерация в слове-образце существует в начале слова, примером может служить вхождение "ссссапеног", обозначение {W}D;

5) итерация в слове-образце присутствует и в начале слова, и в конце, пример - "нннапрмввв", обозначение {W}P{Y};

6) слово-образец состоит полностью из итераций, пример -"ккккк", обозначение {W}.

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

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

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

1) только итерации, т.е. часть, состоящая из одинаковых символов;

2) остальная часть вхождения, но без итераций в начале слова-образца.

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

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

Алгоритм функционирования системы заключается в следующем. В регистрах слов находятся обрабатываемые слова. В регистрах вхождений записываются слова-образцы. Задача системы заключается в определении вхождений в обрабатываемых словах. Если вхождения найдены, то их адреса записываются в память устройства. Если вхождения не найдены, то в регистрах обрабатываемых слов записываются новые слова для проведения поисковых операций. Сравнение в блоках поиска произвольных вхождений происходит побуквенно. На входы компараторов поступают по одной букве из регистров обрабатываемых слов и из регистров слов-образцов. Если результат сравнения положительный, то происходит сдвиг влево на один разряд информации регистров слов и регистров слов-образцов и на вход компаратора поступают очередные символы из регистров. Возможно возникнет ситуация, когда положительное сравнение произойдет на первой букве, на второй, на третьей и т.д., но на k букве результат сравнения будет отрицательным и при этом конца слов-образцов не будет обнаружено. Двоично-десятичные счетчики блока анализа и формирования сигналов сдвига подсчитывают количество положительных сравнений. Скажем их произошло k совпадений, а на k+1 получен отрицательный результат. В этом случае осуществляется сдвиг вправо на к-1 разрядов регистров, в которых хранятся обрабатываемые слова. Происходит "вычеркивание" первых букв из серии, где произошли положительные сравнения. Дальнейшее сравнение будет происходить, уже начиная со вторых букв обрабатываемых слов и с первых букв вхождений. Вхождения будут переписаны заново из памяти вхождений. Процедуры сдвига возможны при применении реверсивных регистров, которые осуществляют сдвиг информации как влево, так и вправо.

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

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

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

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

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

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

На фиг. 5 показана функциональна схема блока анализа и формирование сигналов сдвига.

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

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

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

На фиг.9 - содержательная ГСА работы блока управления параллельной системы поиска произвольных вхождений.

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

Параллельная система поиска произвольных вхождений (фиг.1) содержит блок 1 памяти вхождений, блок 2 памяти слов, n-блоков поиска произвольных вхождений, блок управления. Блок поиска произвольных вхождений (фиг.3) содержит блок 9 регистров сдвига и компаратора, блок 10 анализа и формирования сигналов сдвига, блок 11 хранения адреса вхождений, блок 12 управления работой блока поиска произвольных вхождений.

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

1. ПРКВ - признак конца вхождения. Это может быть двоичный код, равный 11...1.

2. ПРКС - признак конца слова, равный 11..1.

3. КР - команда, определяющая конец работы устройства.

4. СУ1 - сигналы управления сдвигающим регистром блока поиска произвольных вхождений (сигналы записи, приема, выдачи данных).

5. СУР1 - сигналы управления сдвигающим регистром блока поиска произвольных вхождений (сигналы записи, приема, выдачи данных).

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

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

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

9. СУП2 - команды управления записью, выдачей, хранения блока памяти слов.

10. АД1 - адреса данных выдачи, записи блока памяти вхождения.

11. АД2 - адреса данных выдачи, записи блока памяти слов.

12. ДН1 - данные (двоичные коды букв) блока памяти вхождений.

13. ДН2 - данные (двоичные коды букв) блока памяти слов.

14. ССР - сигнал сравнения, поступающий из компаратора.

15. СИН - команда синхронизации, поступающая на вход Сч DD.23 блока анализа и формирования сигналов сдвига из блока управления.

16. ОБН - команда обнуления двоичного счетчика Сч DD.23 блока анализа и формирования сигналов сдвига.

17. СВА - команда выдачи адреса вхождения из блока анализа и формирования сигналов сдвига в блок хранения адреса вхождений.

18. СЗЩ - команда разрешения записи в триггер Тр DD.19 выходного сигнала из компаратора.

19. СДЛ - команда, поступающая из блока управления, открывающая или запирающая электронный ключ И DD.24 блока анализа и формирования сигналов сдвига.

20. СН - команда синхронизации двоичного счетчика Сч2 DD.25 блока анализа и формирования сигналов сдвига.

21. СО - команда обнуления двоичного счетчика Сч2 DD.25 блока анализа и формирования сигналов сдвига.

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

23. АдСТ - адреса столбцов для записи вхождений в блок хранения адреса вхождений.

24. АдСТР - адреса строк для записи вхождений в блок хранения адреса вхождений.

25. ДАВ - данные адресов вхождений.

26. АВХ - адрес вхождения.

27. ВДВ - выходные данные вхождения блока памяти вхождений.

28. ВДС - выходные данные слова блока памяти слов.

29. ДС - данные слов.

30. ДВ - данные вхождений.

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

32. ТАК - тактовые прямоугольные импульсы, поступающие на информационный вход логического элемента И DD.22.

33. СВП - команда, определяющая количество сдвигов вправо регистра PrC1 DD.14 блока регистров сдвига и компаратора.

34. ДШЕ - команда, определяющая двоичный код 0001 (единицу) на выходе двоичного счетчика Сч1 DD.23.

35. ГИ - генератор импульсов, поступающий из блока управления блоком на суммирующий вход (+) двоичного счетчика Сч ст DD.29.

36. ТИ - тактовые импульсы, поступающие из блока управления блоком на суммирующий вход (+) двоичного счетчика Сч стр DD.30.

37. СБР - команда обнуления двоичного счетчика Сч ст DD.29.

38. СБО - команда обнуления двоичного счетчика Сч стр DD.30.

39. Сч/Зп - команда считывания/записи оперативно-запоминающего устройства.

40. ВК - команда выбора кристалла оперативно-запоминающего устройства.

41. РР - команда признака режима работы системы.

42. СР - команда разрешения работы конкретного блока поиска произвольных вхождений.

43. ПСП - признак "пустого (отсутствие данных)" оперативно-запоминающего устройства блока памяти слов.

44. СРР - команда признака работы системы в различных режимах.

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

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

В блоке 3 по команде "СДi:=1" блок поиска произвольных вхождений получает сигнал разрешения на работу из блока управления системы.

В блоке 4 алгоритма происходит запись в регистр вхождений из памяти вхождений последовательности букв (вхождение) РгВ:=ВДВ, в регистр слов записывается из памяти слов обрабатываемое слово РгС1:=ВДС. D-триггер Тр блока анализа и формирования сигналов сдвига устанавливается в "0" ТР:=0. По этим командам происходит предварительная загрузка блока поиска произвольных вхождений.

В блоке 5 алгоритма по командам СДВ:=0 и СДС:=0 формируется сдвиги влево информации, находящейся в регистрах соответственно РгВ и РгС1 блока 9 регистров сдвига и компаратора (БРСК) (фиг.3, 4).

В блоке 6 алгоритма происходит анализ сигнала сравнения ССР, поступившего с выхода компаратора (фиг.4, 5). Если ССР=1, то произошло совпадение буквы вхождения с буквой слова. В этом случае осуществляется переход на блок 7 алгоритма. Если ССР=0, то совпадения не произошло и переход произошел на блок 10 алгоритма.

В блоке 7 алгоритма на вход D-триггера Тр блока 10 анализа и формирование сигналов сдвига поступает сигнал ССР из компаратора КОМ блока регистров сдвигов и компаратора ТР:=ССР. Триггер устанавливается в единичное состояние. Это означает, что входные символы на входе компаратора равны между собой.

В блоке 8 алгоритма по команде СЗЩ:=1 из блока 12 управления работой блока (БУРБ) происходит разрешение на запись в D-триггер информации с выхода компаратора. По команде ТР:=1 D-триггер блока 10 анализа и формирование сигналов сдвига устанавливается в единицу. На суммирующий вход двоичного счетчика СЧ1 этого же блока поступают тактовые импульсы СЧ1:=ТАК. Счетчик подсчитывает количество совпадений в компараторе.

В блоке 9 алгоритма по командам СДВ:=0 и СДС:=0 формируются сдвиги влево информации, находящейся в регистрах соответственно РгВ и РгС1 блока 9 регистров сдвига и компаратора (БРСК) (фиг.3, 4). При этом осуществляется переход на блок 18 алгоритма.

В блоке 10 алгоритма анализируется содержимое триггера Тр (фиг 5). Если Тр= 0, то это означает, что совпадения на предыдущем шаге не было, в этом случае формируется сигнал сдвига влево информации на один разряд в блоке 9 регистров сдвига и компаратора регистра РгС1. Если Тр=1, то осуществляется переход на блок 12 алгоритма, где анализируется состояние счетчика СЧ1 блока 10 анализа и формирование сигналов сдвига.

В блоке 11 алгоритма формируется командой СДС:=0 сдвиг влево на один разряд информации из регистра РгС1 в регистр РгС2 блока 9 регистров сдвига и компаратора. При этом РгС2: =РгС1. На освободившиеся место в регистр РгС1 записывается очередной символ обрабатываемого слова из блока 2 памяти слов РгС1:=ДС. По выходу из блока формируется переход на блок 18 алгоритма.

В блоке 12 анализируется состояние двоичного счетчика СЧ1 блока 10 анализа и формирование сигналов сдвига. Если состояние счетчика меньше или равно единице, то осуществляется переход на блок 13 алгоритма. Если условие выполняется, т. е. значение счетчика СЧ1 больше единицы, то происходит переход на блок 16 алгоритма.

В блоке 13 алгоритма на вход регистра вхождения РгВ блока 9 регистров сдвига и компаратора из блока 12 управления работой блока поступают управляющие сигналы РгВ:=СУ1. В результате этого в регистр вхождений записывается информация из памяти вхождений РгВ:=ДВ.

В блоке 14 алгоритма регистр слов РгС1 принимает информацию из регистра слов РгС2 РгС1:=РгС2. Обрабатываемое слово сдвигается вправо на п-1 разрядов, где n - количество сдвигов влево этого же слова.

В блоке 15 алгоритма по команде ОБН:=1 происходит обнуление счетчика СЧ1 блока 10 анализа и формирование сигналов сдвига. Двоичный счетчик СЧ1 принимает нулевое значение СЧ1:=0. По выходу из блока формируется переход на блок 18 алгоритма.

В блоке 16 алгоритма формируется подача прямоугольных импульсов из блока 12 управления работой блока ПРИ на вычитающий вход двоичного счетчика СЧ1 блока 10 анализа и формирования сигналов сдвига. По команде СВП:=1 в счетчике происходит арифметическое вычитание единицы до тех пор, пока состояние этого счетчика не будет равно единичному значению СЧ1:=ПРИ.

В блоке 17 алгоритма формируется сдвиг вправо. Командой СДС:=1 информация из регистра РгС2 сдвигается на один разряд в регистр РгС1, РгС1:=РгС2. По команде СУ2:=1 происходит разрешение осуществления операций сдвига в блоке 9 регистров сдвига и компаратора. Информация из регистра РгС2 сдвигается в регистр РгС1 до тех пор, пока состояние счетчика СЧ1 не будет равно единице. Блоки 12, 16, 17 алгоритма формируют цикл. Выходом из цикла является условие, при котором значение счетчика будет не больше единицы. По выходу из блока осуществляется переход на блок 13 алгоритма.

В блоке 18 алгоритма происходит анализ признака конца вхождения ПРКВ (фиг. 4). Если ПРКВ=1, то в регистре вхождения обнаружен двоичный код 11..1. В этом случае вхождение обнаружено в обрабатываемом слове и в блок 11 хранения адреса вхождений записывается адрес вхождения (фиг.6). Если ПРКВ=0, то это означает что процесс сравнения идет побуквенно, но не все буквы вхождения еще просмотрены, при этом осуществляется переход на 19 блок алгоритма.

В блоке 19 алгоритма происходит анализ признака конца слова ПРКС (признаком является двоичный код, равный всем единицам 11...1). Если ПРКС=0, то процесс поиска будет продолжен и при этом осуществляется переход на блок 6 алгоритма. Если обнаружен признак конца слова ПРКС=1, то осуществляется переход на конечный блок 27 алгоритма.

В блоке 20 алгоритма происходит запись адреса в блок хранения адреса вхождений. На управляющий вход электронного ключа Кл блока 10 анализа и формирования сигналов сдвига поступает разрешающий сигнал из блока 12 управления работой блока СВА, Кл:=СВА. Информация с выхода двоичного счетчика СЧ2 через открытый ключ Кл поступает на вход оперативно-запоминающего устройства ОЗУ (фиг. 5, фиг. 6). Сигнал разрешения для записи информации поступает из блока 12 управления работой блока Сч/Зп:=0, ВК:=0. На управляющие входы поступают нулевые значения, что соответствует режиму записи в ОЗУ устройства входной информации, т.е. адреса вхождения АВХ ОЗУ:=АВХ.

В блоке 21 алгоритма происходит анализ режима работы i-ого блока поиска произвольных вхождений системы команды PP. Если команда РР равна нулю, то это означает, что данный блок работает в режиме поиска вхождений с общими частями. В этом случае осуществляется переход на блок 22 алгоритма. Если РР равен единице, то блок работает в режиме поиска вхождений, не имеющих общих частей, при этом осуществляется переход на блок 24 алгоритма.

В блоке 22 алгоритма по команде СРР:=1 выходной сигнал логического элемента DD.30 блока анализа и формирования сигналов сдвига устанавливается в единичное состояние. В этом случае логические элементы DD.29 и DD.21 указанного блока будут открыты. На выходах этих элементов будет сигнал ПРИ - прямоугольные импульсы, поступающие из блока 12 управления работой блока.

В блоке 23 алгоритма по команде СДС:=СВП на вход регистра слов PrC1 DD. 14 блока 9 регистров сдвига и компаратора подаются прямоугольные импульсы СВП, количество которых на единицу меньше количества сигналов, поступивших на суммирующий вход счетчика СЧ1 DD.23. При этом по приходу каждого импульса СВП осуществляется сдвиг информации в этом регистре вправо на один разряд. При этом осуществляется переход на блок 26 алгоритма.

В блоке 24 алгоритма по команде СРР:=0 выходной сигнал логического элемента DD. 30 блока 10 анализа и формирования сигналов сдвига устанавливается в нулевое состояние. В этом случае логические элементы DD.29 и DD.21 указанного блока будут закрыты. На выходах этих элементов будут нулевые состояния.

В блоке 25 алгоритма по команде СДС:=0 на вход регистра слов PrC1 DD.14 блока 9 регистров сдвига и компаратора подается сигнал из блока 12 управления работой блока, равный нулевому значению. При этом осуществляется сдвиг информации в этом регистре на один разряд влево.

В блоке 26 алгоритма происходит запись очередного вхождения в регистр вхождений РгВ блока 9 регистров сдвига и компаратора. Из блока 1 памяти вхождений на вход регистра поступает информация РгВ:=ДВ.

Блок 27 алгоритма является конечным блоком.

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

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

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

В блоке 5 алгоритма происходит загрузка слов-образцов для проведения поисковых операций. По команде ПВ:=СУП1 происходит подача на вход оперативно-запоминающего устройства (ОЗУ) ПВ DD.7 блока памяти вхождений (БПВ) сигналов управления для записи информации в ОЗУ. По команде ПВ:=АД1 подаются адресные входы для записи данных в ОЗУ. По команде ПВ:=ДН1 происходит подача на входы ОЗУ данных для записи (фиг.2).

В блоке 6 алгоритма происходит загрузка слов для проведения поисковых операций. По команде ПС:=СУП2 происходит подача на вход оперативно-запоминающего устройства (ОЗУ) ПС DD.8 блока памяти слов (БПС) сигналов управления для записи информации в ОЗУ. По команде ПС:=АД2 подаются адресные входы для записи данных в ОЗУ. По команде ПС:=ДН2 происходит подача на входы ОЗУ данных для записи (фиг.2).

В блоке 7 счетчик блоков поиска произвольных вхождений i устанавливается в единичное состояние по команде i:=1.

В блоке 8 алгоритма анализируется признак КР - наличие информации в памяти вхождений блока памяти вхождений (БПВ). Если признак КР равен нулю, то это означает, что в памяти вхождений есть информация. В этом случае работа системы продолжается. Если признак КР равен единице, что означает: все слова-образцы в блоке памяти вхождений (БПВ) просмотрены. В этом случае происходит переход на конечный блок 14 алгоритма (фиг.2).

В блоке 9 алгоритма анализируется признак ПСП - наличие информации в памяти слов блока памяти слов (БПС). Если признак ПСП равен нулю. то это означает, что в памяти слов есть информация. В этом случае работа системы продолжается. Если признак ПСП равен единицы, что означает: все обрабатываемые слова в блоке памяти слов (БПС) просмотрены. В этом случае происходит переход на конечный блок 14 алгоритма (фиг.2).

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

В блоке 10 алгоритма анализируется текущее значение счетчика блоков i. Если i<= n где n - общее количество блоков поиска произвольных вхождений в поисковой системе, то процесс загрузки блоков для символьной обработки продолжается. В этом случае происходит переход на блок 11 алгоритма. Если условие в блоке 10 алгоритма не выполняется, т.е. все блоки загружены, то осуществляется переход на блок 8 алгоритма для анализа признаков работы системы.

В блоке 11 алгоритма анализируется признак работы СР i-ого блока поиска произвольных вхождений (БППВi). Если СРi равен единице, то происходит загрузка данного блока информацией для осуществление поисковой операции. Если признак работы СРi равен нулю, то осуществляется переход на блок 13 алгоритма. Сигнал СРi работы блока БППВi формирует блок управления (фиг.1).

В блоке 12 алгоритма по команде БППВi:=ВДС происходит подача на i-блок поиска произвольных вхождений (БППВ) информации из блока памяти вхождений (БПВ). По команде БППВi:=ВДВ на вход i-ого блока поиска произвольных вхождений подается информация из блока памяти слов (БПС). В этом блоке алгоритма осуществляется загрузка блока БППВi словами и словами-образцами для обработки.

В блоке 13 алгоритма по команде i:=i+1 происходит изменение значения счетчика блоков (БППВ) на единицу. При этом осуществляется переход на блок 10 алгоритма.

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

Внешние управляющие сигналы "ПУСК" и "СБРОС" поступают в блок 6 управления.

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

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

Блок 1 памяти вхождений содержит оперативно-запоминающее устройство (ОЗУ) - память вхождений DD.7. (фиг.2). На вход этого блока поступают сигналы из блока управления для осуществления операций выбора кристалла, операции считывания/записи - СУП1, а также адресные данные АД1, по которым записываются в ОЗУ данные. Входными данными ОЗУ памяти вхождений являются слова-образцы (вхождения) - ДН1, которые поступают из блока управления системы. Вхождения записываются заранее перед осуществлением операции поиска. При считывании вхождений с выхода памяти вхождений формируется информационный сигнал ВДВ, соответствующий двоичному коду каждой буквы вхождения. Выходным сигналом является управляющая команда, соответствующая признаку конца работы блока памяти вхождений КР, т.е. ОЗУ блока "пустое". Этот сигнал поступает на вход блока управления. Память вхождений - оперативно-запоминающее устройство ОЗУ ПВ служит для хранения цепочки символов - вхождений.

Блок 2 памяти слов содержит оперативно-запоминающее устройство ОЗУ ПС - память слов DD.8. (фиг.2). На вход этого блока поступает информационный сигнал из блока управления для осуществления операций выбора кристалла, операции считывания/записи - СУП2, а также адресные данные АД2. Входными данными ОЗУ памяти слов являются обрабатываемые слова ДН2, которые поступают из блока управления. Слова записываются заранее перед осуществлением операции поиска. При считывании слов с выхода памяти слов формируется информационный сигнал ВДС, соответствующий двоичному коду каждой буквы слова. Выходным сигналом является управляющая команда, соответствующая признаку конца работы блока памяти слов ПСП. Этот сигнал поступает на вход блока управления, означающий, что ОЗУ ПС "пустое". Память слов ПС служит для хранения слов-образцов.

Блок 3 поиска произвольных вхождений содержит блок 9 регистров сдвига и компаратора БРСК, блок 10 анализа и формирования сигналов сдвига БАФС, блок 11 хранения адреса вхождений БХАВ, блок 12 управления работой блока БУРБ (фиг.3).

Блок 9 регистров сдвига и компаратора БРСК (фиг.4) содержит реверсивный регистр РгВ DD13 (регистр вхождений), в котором будет хранится слово-образец (вхождение), реверсивный регистр РгС1 DD14, (регистр слов), в котором будет хранится обрабатываемое слово, реверсивный регистр сдвига РгС2 DD15, логический элемент И DD16 предназначен для обнаружения признака конца вхождения ПРКВ, логический элемент И DD18 предназначен для обнаружения признака конца слова ПРКС, компаратор DD.17, представляющий собой устройство сравнения на равенство входных величин: выходных данных вхождений ДВ реверсивного регистра РгВ DD. 13 и выходных данных реверсивного регистра слов РгС1 - ДС (фиг. 4). Если входные сигналы равны, то на выходе компаратора формируется единичный сигнал ССР. В обратном случае ССР будет равен нулю. Выходной сигнал компаратора поступает на вход блока 12 управления работой блока и на вход блока 10 анализа и формирования сигналов сдвига (фиг.3). С выхода памяти вхождений информация ВДВ поступает на вход реверсивного регистра вхождений РгВ DD.13, по сигналам управления СУ1 из блока 12 управления работой блока происходит запись символов вхождения в регистр вхождений. Сигнал сдвига вхождений СДВ из блока 12 управления работой блока поступает на вход реверсивного регистра вхождений (фиг.4). Выходная информация из реверсивного регистра вхождений ДВ поступает на первый вход компаратора DD.17 (фиг.4). Реверсивный регистр РгВ выполняет операцию сдвига в любом направлении: слева направо или наоборот. Сдвиг вправо выполняется при значении сигнала СДВ=1. сдвиг влево - при СДВ=0, т.е. направление сдвига осуществляется одним управляющим сигналом [3, 4]. Элемент И DD.16 формирует сигнал признака конца вхождений ПРКВ, равный единице (все единицы на входе). Перед началом работы системы в регистре вхождений находится слово-образец, сигнал признака конца вхождений ПРКВ равен нулю, сигнал сдвига вхождений СДВ равен нулю. С выхода памяти слов информация ВДС поступает на вход реверсивного регистра слов PrC1 DD14, по сигналам управления СУР из блока 12 управления работой блока происходит запись слова в реверсивный регистр слов PrC1 DD.14. Сигнал сдвига слов СДС из блока 12 управления работой блока поступает на вход реверсивного регистра слов PrC1 DD.14 (фиг.4). Выходная информация из реверсивного регистра слов PrC1 ДС поступает на вход логического элемента И DD18, а также на второй вход компаратора КОМ DD. 17. Элемент И DD.18 формирует сигнал признака конца слова ПРКС, равный единице (все единицы на входе). Перед началом работы системы в регистре слов находится слово, сигнал признака конца слова ПРКС равен нулю. Работа системы начинается с установки управляющих сигналов сдвигов СДВ и СДС в нулевое состояние. На вход компаратора КОМ поступают по одному символу из регистров вхождений и слов. Если на выходе компаратора КОМ будет сформирован сигнал сравнения ССР, то сигнал сдвига СДС будет равен нулю, в этом случае будет сформирован сигнал сдвига влево на один разряд. Информация из регистра PrC1 DD.14 сдвинется на один символ влево. Этот символ перейдет по сигналам СУР в регистр РгС2 DD15 (фиг. 4). Процесс сдвига влево будет продолжаться до тех пор, пока не будет получен отрицательный результат сравнения в компараторе КОМ DD.17 или не будет обнаружен признак конца вхождения ПРКВ. Предположим, что было зафиксировано 4 сдвига влево и получен отрицательный сигнал сравнения ССР, равный нулю. Тогда блоком 12 управления работой блока будут сформированы сигналы вправо, при этом сигнал сдвига СДС равен единице. Информация из регистра РгС2 DD.15 будет сдвинута вправо на n-1 разрядов, где n - количество сдвигов влево, в нашем случае 3. Три буквы из регистра РгС2 DD15 перейдут в регистр PrC1 DD14. В этом случае вторая буква будет первой в регистре PrC1, процесс поиска вхождений будет продолжен (фиг.4). Если будет обнаружен признак конца вхождения ПРКВ, то в этом случае вхождение найдено и будет записано в блок хранения адреса вхождений по соответствующему адресу. Работу блока можно представить как хранение вхождений и слов. По приходу сигналов сдвига происходит выдача по одному символу на входы компаратора для осуществления операции сравнения. В зависимости от выходного сигнала компаратора ССР происходит сдвиг информации в обоих регистрах или в регистре слов.

Блок 10 анализа и формирования сигналов сдвига (фиг.5) содержит D-триггер DD19, двухвходовый логический элемент И DD. 20 с инверсным входом, двухвходовый логический элемент И DD.22, двухвходовый логический элемент И DD. 24, трехвходовый логический элемент И DD.21 с инверсным входом, логический элемент И DD.28 с инверсными входами, трехвходовый элемент И DD.27 с инверсным входом, электронный ключ DD.26, двоичный счетчик СЧ1 DD.23, двоичный счетчик СЧ2 DD.25, двухвходовый логический элемент И DD.29, двухвходовый логический элемент ИЛИ DD.30 с инверсными входами. Перед началом работы устройства двоичные счетчики Сч1 DD.23, Сч2 DD.25, а также D-триггер Тр DD. 19 триггер установлены в нулевое состояние. Блок 10 анализа и формирования сигналов сдвига (фиг.5) обрабатывает выходной сигнал ССР с компаратора. Если сигнал ССР равен единице, то это означает, что произошло совпадение двоичного кода символа вхождения с двоичным кодом буквы слова. В этом случае D-триггер Тр DD.19 по приходу из блока 12 управления работой блока разрешающего сигнала СЗЩ устанавливается в единичное состояние. Логический элемент И DD.22, выполняющий функцию электронного ключа, отпирается, тактовые импульсы ТАК из блока 12 управления работой блока поступают на суммирующий (+) вход двоичного счетчика СЧ1 DD.23. В двоичном счетчике СЧ1 DD.23 происходит суммирование тактовых импульсов, количество которых соответствует количеству совпадений в компараторе. На выходе двоичного счетчика СЧ1 DD.23 формируется двоичный код, соответствующий количеству положительных совпадений в компараторе (фиг.5). При каждом положительном совпадении в компараторе происходит формирование сигналов сдвига влево СДВ и СДС, равных нулю, и осуществляется сдвиг на один символ влево в регистре РгВ DD.13 и регистре PrC1 DD.14 блока 9 регистров сдвига и компаратора (фиг.4). Регистр РгС2 DD. 15 блока 9 регистров сдвига и компаратора записывает каждый символ, поступающий из регистра PrC1 DD.14. В случае обнаружения признака конца вхождения ПРКВ, равным единице, логическим элементом И DD.16 блока 9 регистров сдвига и компаратора происходит определение адреса вхождения и запись по соответствующему адресу записи в оперативно-запоминающее устройство ОЗУ DD.33 блока 11 хранения адреса вхождений. Если признак конца слова не обнаружен ПРКС= 0 (равен нулю), то предыдущее вхождение восстанавливается, т.е. переписывается заново из памяти вхождений, и процесс поиска вхождений в слове продолжается. Если совпадений в компараторе не происходит, выходной сигнал ССР равен нулю, то формируется только сигнал СДС, равным нулю, и происходит сдвиг влево на одну позицию информации, находящейся в регистре слов PrC1 DD. 14 блока 9 регистров сдвига и компаратора (фиг.4). При каждом сдвиге влево и отрицательном результате совпадения в компараторе из памяти слов ПС переписывается (дописывается) символ в регистр памяти слов PrC1 DD.14 блока 9 регистров сдвига и компаратора. Возможна ситуация в поисковой операции, когда был получен положительный результат сравнения символов, тогда формируется сдвиг влево на один разряд регистров. После сдвига получен второй раз положительный результат, третий и так далее, но признака конца вхождения еще нет. Допустим на n шаге получен отрицательный результат сравнения, а вхождение полностью не обнаружено. В этом случае D-триггер Тр DD.19 был установлен в состояние единицы, т.е. на выходе элемента единица. На следующем этапе сигнал сравнения равен нулю ССР=0. На выходе логического элемента И DD.20 будет сформирован единичный сигнал. Логический элемент И DD.21 также будет открыт, прямоугольные импульсы из блока 12 управления работой блока ПРИ будут поступать на вычитающий вход двоичного счетчика СЧ1 DD.23. Вычитание происходит до тех пор, пока на выходе счетчика не будет двоичный код, равный единице. На положительный вход счетчика прямоугольные импульсы из блока 12 управления работой блока поступать не будут, т.к. логический элемент И DD. 22, выполняющий функцию электронного ключа, будет заперт установившимся в нулевое состояние D-триггером DD.19. Логический элемент И DD.28 выполняет роль дешифратора единицы. Выход этого элемента равен единице в случае получения на выходе счетчика СЧ1 DD.23 двоичного кода 0001 (фиг.5). При всех других комбинациях на выходе данного элемента будет состояние нуль. При единице на выходе этого элемента логический элемент И DD.21 запирается, т.к. единица поступает на инверсный вход. Прямоугольные импульсы на вычитающий вход счетчика СЧ1 не поступают. Счетчик СЧ1 обнуляется командой ОБН, поступающей из блока 12 управления работой блока. Логический элемент И DD.27 выполняет роль своеобразного "клапана", формирующего количества сдвигов вправо регистра PrC1. Каждый раз, когда происходит вычитание единицы из содержимого счетчика СЧ1, происходит перемещение вправо информации из регистра РгС2 DD. 15 в регистр PrC1 DD.14 блока 9 регистров сдвига и компаратора. Количество сдвигов вправо будет на один меньше, чем количество сдвигов влево. В нашем примере n-1. Вторая буква из полученной серии положительных сдвигов будет первой в регистре PrC1. Вхождение будет заново переписано из памяти вхождений DD. 7 в регистр вхождений РгВ DD.13. Процесс поиска будет продолжен. Логический элемент или DD.30 выполняет функцию распознавания режима работы. Как известно, система работает в двух независимых режимах: определения вхождений с общими частями и определения вхождений и без (пересечений) общих частей. В первом случае признак режима работы РР будет равен нулю. Во втором случае признак РР равен единице. Логический элемент И DD.29 выполняет функцию электронного ключа. В случае, когда признак работы системы РР равен нулю, на выходе элемента ИЛИ DD.30 всегда будет единица. Электронный ключ DD. 29 будет открыт. Прямоугольные импульсы ПРИ из блока 12 управления работой блока через открытый ключ поступают на третий вход логического элемента И DD. 21. Этот режим характеризуется перемещением информации из регистра РгС2 DD.15 в регистр PrC1 DD.14 на n-1 разрядов, т.е. будет сформирован возврат информации, где n - количество положительных сдвигов, всякий раз, когда будет обнаружено вхождение в обрабатываемом слове, при этом признак конца вхождения ПРКВ будет равен единице. Если режим работы системы будет установлен как поиск вхождений без общих частей, то в этом случае РР равен единице. В случае обнаружения вхождения признак вхождений ПРКВ равен также единице. На выходе логического элемента ИЛИ DD.30 установить нулевое значение. Электронный ключ И DD.29 будет заперт. Прямоугольные импульсы ПРИ из блока 12 управления работой блока не будут поступать на вход элемента И DD.21 (фиг.5). Информация из регистра РгС2 не переместится в регистр PrCl. В этом случае будет сформирован сдвиг влево символов из регистра PrC1 в регистр РгС2 т.е. возврата информации не будет (фиг.4).

Блок 11 хранения адреса вхождений БХАВ (фиг.6) содержит оперативно-запоминающее устройство ОЗУ DD.33, двоичный счетчик, формирующий адреса столбцов ОЗУ - Сч ст DD.31, двоичный счетчик, формирующий адреса строк ОЗУ - Сч стр DD.32. Двоичные счетчики вначале работы устройства обнулены управляющими сигналами СБР, СБО. поступающими из блока 12 управления работой блока. На входы счетчиков поступают прямоугольные импульсы ГИ, ТИ из блока 12 управления работой блока. Счетчики формируют адреса строк и столбцов, по которым будут записаны адреса вхождений, поступающие на вход оперативно-запоминающего устройства ОЗУ DD.33 (фиг.6). Сигналы управления оперативно-запоминающего устройства ОЗУ DD.33 считывания/запись и выбора кристалла соответственно при записи принимают значения Сч/Зп=0, ВК=0.

Блок 12 управления работой блока БУРБ (фиг.3) синтезируется на основе ГСА алгоритма управления блоком (фиг.7) известным способом [6]. Размеченная ГСА работы блока 12 управления работой блока приведена на фиг.8, где обозначено:

Логические условия:

X1: "СДi"

Х2: "ССР"

Х3: "ТР"

Х4: "СЧ1"

Х5: "ПРКВ"

Х6: "ПРКС"

Х7: "РР"

Операторы:

У1: "СДi=1"

У2: "РгВ:=ВДВ"

У3: "РгС1:=ВДС"

У4: "Тр:=0"

У5: "Кл:=СBA"

У6: "Сч/Зп:=0"

У7: "ВК:=0"

У8: "ОЗУ:=АВХ"

У9: "СДС:=0"

У10: РгС2:=РгС1"

У11: "СВП:=1"

У12: "СЧ1:="ПРИ"

У13: "СДС:=1"

У14: "PrC1:PrC2"

У15: "CУ2:=1"

У16: ТгВ:=СУ1"

У17: "ОБН:1"

У18: "СЧ1:0"

У19: "ТР:=ССР"

У20: "СЗЩ:=1"

У21: "ТР:=1"

У22: "CЧl:=TAK"

У23: "CДB:=0"

У24: "CPP:=1"

У25: "СРР:=0"

У26: "СДС:=СВП"

Блок 6 управления системой синтезируется на основе ГСА алгоритма управления (фиг.9) известным способом [6]. Размеченная ГСА работы блока 6 управления системой приведена на фиг.10, где обозначено:

Логические условия:

X1: "УОО"

Х2: "ПУСК"

Х3: "КР"

Х4: "ПСП"

Х5: "i<=n"
Операторы:

У1: "СБРОС:=1"

У2: "ПB:=CУП1"

У3: "ПВ:=АД1"

У4: "ПВ:ДН1"

У5: "ПС:=СУП2"

У6: "i:=1"

У7: ПС:АД2"

У8: "ПС:=ДН2"

У9: "БППBi:=BДC"

У 10: "БППВi:=ВДВ"

У11: "i:=1+1"

ИСТОЧНИКИ ИНФОРМАЦИИ

1. Кудрявцев В.Б., Подколзин А.С., Ушчумлич Ш. Введение в теорию абстрактных автоматов. М.: Из-во МГУ, 1985, 174с.

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

3. Успенский В. А., Семенов А.Л. Теория алгорифмов: основные открытия и приложения. - Москва.: Наука, Главная редакция физико-математической литературы. 1987 г., - 210с.

4. Алексенко А. Г. . Шагурин И.И. Микросхемотехника: Учеб. пособие для вузов. - 2-е изд., перераб. и доп. - М.: Радио и связь, 1990, - 496с.: ил.

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

6. Цифровые и налоговые интегральные микросхемы: Справочник под ред. С. В. Якубовского. - М.: Радио и связь,1990, - 496 с.

7. Патент 2150740 (прототип).

8. А.с. СССР 1837327 (аналог).

9. А.с. СССР 1667097 (аналог).

10. А.с. СССР 1277091 (аналог).