Устройство для параллельного поиска и обработки данных

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

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

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

Задача поиска вхождения формулируется следующим образом. Пусть в общем алфавите мощностью заданы образец О и текст Т как последовательности кодов символов из алфавита длиной в n и m символов (n<m) соответственно и пусть каждый символ образца и текста кодируется p=log ₂w разрядами соответственно. Требуется найти все позиции начала вхождений О в Т.

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

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

Известна система поиска слов в произвольном тексте [1], основанная на хранении текста в виде так называемых характеристических векторов длиной в m бит каждый вектор. Каждый элемент такого вектора принимает значение логической «1» или «0» в зависимости от того, присутствует ли текущий символ образца в тексте в данной позиции. При таком представлении исходных данных операция поиска вхождения сводится к последовательной обработке нуль-единичных векторов. Данная система может быть реализован алгоритмом обработки характеристических векторов на основе операции побитового умножения логических векторов со сдвигом.

Смысл данной операции заключается в том, что при перемножении двух характеристических векторов X, Y текущего и предыдущего символов образца результирующий вектор Z имеет единицу в h-ой позиции в том случае, если единицы содержатся в h-ой позиции вектора Х и в h-1 позиции вектора Х одновременно. Другими словами, поиск вхождений образца заключается в последовательном логическом умножении m характеристических векторов. Результатом поиска на характеристических векторах является m-ый характеристический вектор, в котором единицы соответствуют позициям вхождения последнего символа образца.

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

Также известен алгоритм поиска СДВИГ-И [2], основанный на поиске всех возможных префиксов образца в тексте с помощью логических векторов-столбцов длиной в n бит каждый. Каждый элемент такого вектора-столбца принимает значение логической «1» или «0» в зависимости от того, присутствует ли текущий префикс образца в тексте в данной позиции. При такой организации исходных данных операция поиска вхождения сводится к последовательной обработке нуль-единичных векторов-столбцов (битовых срезов).

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

Устройством-прототипом является устройство [3] для адресации по содержанию блока памяти, состоящее из двух блоков ассоциативных признаков, блока памяти логических векторов и операционного блока. Работа устройства основана на обработке элементов двух множеств (признаков и объектов) с помощью логических векторов-строк или векторов столбцов. Вектор-строка является характеристическим вектором, описывающим определенное подмножество признаков, принадлежащих множеству объектов. В качестве элементарных операций над векторами реализованы логические операции умножения, сложения, суммы по модулю 2, инверсии и т.д., а также операции идентификации логического вектора-строки (поиск по столбцу).

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

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

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

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

что в него дополнительно введены во-первых, дополнительный однобитовый выход в дешифраторе команд операционного блока, дополнительно введенный однобитовый выход в дешифраторе команд является вторым выходом операционного блока, во-вторых, блок матричного поиска, имеющий четыре входа и один выход, причем первый вход начальной установки устройства подключен к первому входу блока матричного поиска, второй вход которого соединен со вторым выходом операционного блока, третий и четвертый входы блока матричного поиска являются соответственно третьим и четвертым информационными входами устройства, а выход блока матричного поиска является вторым выходом устройства, при этом блок матричного поиска содержит элемент задержки, n регистров для хранения кодов символов образца разрядностью р бит каждый, m регистров для хранения кодов символов текста разрядностью р бит каждый, k триггеров позиций, а также характеристическую матрицу, состоящую из поисковых ячеек и имеющую геометрическую форму параллелограмма, размер матрицы - n×k поисковых ячеек (k=m-n+l - количество строк, а также диагоналей в матрице), при этом каждый регистр для хранения кодов символов образца и каждый регистр для хранения кодов символов текста имеют соответственно три входа (первый и второй управляющие входы и третий информационный р-разрядный вход) и один р-разрядный выходу, каждая поисковая ячейка имеет три информационных входа (первый и второй входы разрядностью р бит каждый, третий - одноразрядный вход) и один выход, каждый триггер позиции имеет соответственно три входа (первый и второй управляющие входы и третий информационный вход) и один выход, каждая поисковая ячейка содержит двухвходовую схему сравнения на равенство р-разрядных кодов символов образца и текста и двухвходовой элемент И, причем первый и второй р-разрядные входы поисковой ячейки соединены соответственно с первым и вторым р-разрядными входами двухвходовой схемы сравнения на равенство соответственно, выход которой является первым входом двухвходового элемента

И, второй вход которого соединен с третьим входом поисковой ячейки, выходом которой является выход двухвходового элемента И, причем первые р-разрядные входы всех поисковых ячеек i-ой строки матрицы (1=1-n) соединены с р-разрядным выходом i-ого регистра для хранения символа образца, р-разрядный выход j-ого регистра для хранения кода символа текста (j=1-m) соединен соответственно со вторыми р-разрядными входами всех поисковых ячеек, входящих в j-ый столбец матрицы, выход (i, j)-ой поисковой ячейки, кроме i=1 (первая строка матрицы), соединен с третьим входом (i-1, j-1)-ой поисковой ячейки, кроме i=n (последняя строка матрицы), выход i-ой (i=1-k) поисковой ячейки, расположенной в первой строке матрицы, соединен с третьим входом i-ого триггера позиции, на третий вход каждой поисковой ячейки, расположенной в последней строке матрицы, подано значение логической «1», первый вход блока матричного поиска соединен соответственно с первыми входами n регистров для хранения кодов символов образца, а также с первыми входами m регистров для хранения кодов символов текста и первыми входами k триггеров позиций, второй вход «Запись строк» блока матричного поиска соединен со входом элемента задержки и со вторыми входами n регистров для хранения кодов символов образца и вторыми входами m регистров для хранения кодов символов текста соответственно, выход элемента задержки соединен со вторыми входами k триггеров позиций, выходы которых образуют информационный k-разрядный выход блока матичного поиска, третий вход блока матричного поиска состоит из n групп по р разрядов каждая группа, кодирующих символы образца, причем i-ая группа разрядов (i=1-n) подается на третий р-разрядный вход i-ого регистра для хранения кода символа образца, четвертый вход блока матричного поиска состоит из m групп разрядов по р разрядов каждая группа, кодирующих символы текста, причем j-ая группа разрядов (j=1-m) подается на третий р-разрядный вход j-ого регистра для хранения кода символов текста, каждая двухвходовая схема сравнения на равенство в составе поисковой ячейки состоит

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

На фиг.1 показана функциональная схема устройства для параллельного поиска и обработки данных; на фиг.2 - функциональная схема операционного блока; на фиг.3 - функциональная схема блока матричного поиска, на фиг.4 -функциональная схема двухвходовой схемы сравнения на равенство, на фиг.5 - пример параллельного поиска вхождений по диагоналям характеристической матрицы, на фиг.6 - временные диаграммы работы на операции «ПОИСК ВХОЖДЕНИЙ» («ПВ»). Устройство содержит блоки 1 ₁ и 1₂ хранения и сравнения ассоциативных признаков, блок 2 памяти логических векторов, операционный блок 3, блок 4 матричного поиска, информационные входы устройства 4₁, 4₂, 4 ₃ и 4₄, первый и второй информационные выходы устройства 5₁ и 5 ₂ соответственно, входы 6₁-6 ₆ задания режима работы, входы 7₁ и 7₂ начальной установки.

Структура блоков 1₁, 1₂, 2 строго соответствуют устройству-прототипу в схемном и в функциональном отношении, состоит из совпадающих элементов и связей между ними.

В операционный блок 3 по сравнению с устройством-прототипом введены незначительные изменения в связи с подключением к нему блока 4, но в функциональном отношении он соответствует устройству-прототипу. Изменение в составе операционного блока 3 связано с добавлением операции «ПВ», задаваемой по входу 6₆ соответствующим кодом, и состоит во введении дополнительного однобитового выхода в дешифраторе 23 команд. Операция

«ПВ» не может выполняться на элементах 27 побитовой обработки логических векторов, поэтому дешифратор 23 команд только обнаруживает на входе 6 ₆ код, соответствующий данной операции. После этого подается единичный импульс на дополнительно введенный однобитовый выход дешифратора 23 команд, который является вторым выходом операционного блока 3. Все блоки - 19, 20, 21, 22, 23, 24, 25, 26, 27 (1...n), 28, 29, 30 - строго соответствуют по структуре и выполняемым функциям описанию в устройстве-прототипе.

Блок 4 матричного поиска содержит два управляющих входа: «Начальная установка» 7₁ (первый вход) и вход «Запись строк» (второй вход), третий и четвертый входы для подачи символов образца и текста в параллельном коде через информационные входы 4 ₃ и 4₄ устройства, а также один информационный выход, являющийся вторым выходом 5₂ устройства. При этом второй управляющий вход блока 4 соединен со вторым выходом операционного блока 3.

Блок 4 матричного поиска содержит элемент 31 задержки, состоящий из n пар инверторов, n регистров 32₁-32_n для хранения кодов символов образца, m регистров 33₁ -33m для хранения кодов символов текста, характеристической матрицы поисковых ячеек 34₁₁-34 _nm и k триггеров 37 позиций, причем регистр 32 _i(i=1-n) и регистр 33_j(j=1-m) содержат первый и второй управляющие входы, третий р-разрядный информационный вход и один выход соответственно. Первые и вторые входы n регистров 32 для хранения кодов символов образца и первые и вторые входы m регистров 33 для хранения кодов символов текста соединены соответственно с первым и вторым управляющими входами блока 4 матричного поиска, третий вход которого разрядностью р·n бит предназначен для параллельной записи образца в регистры 32₁ -32_n и состоит из n групп разрядов по р разрядов каждая группа, кодирующих символы образца, причем i-ая группа разрядов (i=1-n) подается на третий р-разрядный вход регистра 32_i (i=1-n), четвертый вход блока 4 матричного

поиска разрядностью p·m бит предназначен для параллельной записи текста в регистры 31₁-33 _m и состоит из m групп разрядов по р разрядов каждая группа, кодирующих символы текста, причем j-ая группа разрядов (j=1-m) подается на третий р-разрядный вход регистра 33j (j=1-m). Второй управляющий вход блока 4 матричного поиска также соединен со входом элемента 31 задержки.

Характеристическая матрица поисковых ячеек 34₁₁-34 _nm имеет размер n×k ячеек (k=m-n+l - количество строк, а также диагоналей в матрице), причем каждая поисковая ячейка 34_ij имеет три входа и один выход и содержит двухвходовую схему 35_ij сравнения на равенство р-разрядных кодов символов образца и текста и двухвходовой элемент 36 И, каждая двухвходовая схема 35_ij сравнения на равенство в составе поисковой ячейки 34_ij состоит из р двухвходовых элементов 38₁ -38_p суммы по модулю два с инверсией, на первые входы которых подается соответствующий разряд из i-ой р-разрядной группы третьего входа блока 4 матричного поиска, а на вторые входы двухвходовых элементов 38₁ -38_p суммы по модулю два с инверсией - соответствующий разряд из j-ой р-разрядной группы четвертого входа блока 4 матричного поиска, все выходы двухвходовых элементов 38₁-38_p суммы по модулю два с инверсией в составе двухвходовой схемы 35 _ij сравнения на равенство соединены с р-входовым элементом 39 И, выход которого является выходом двухвходовой схемы 35 _ij сравнения на равенство. Первый и второй р-разрядные входы поисковой ячейки 34_ij соответственно соединены с первым и вторым р-разрядными входами двухвходовой схемы 35_ij сравнения на равенство, выход которой является первым входом двухвходового элемент 36 И, второй вход которого является третьим входом поисковой ячейки 34 _ij, выходом которой является выход двухвходового элемента 36 И.

Характеристическая матрица поисковых ячеек 34 ₁₁-34_nm имеет геометрическую форму параллелограмма, в которой в каждой строке располагается k поисковых ячеек, сдвинутых относительно следующей строки ячеек влево

на 1 позицию, начиная с ячеек последней строки 34 _nn-34_nm. Такая форма матрицы обеспечивает направление поиска по диагоналям, проходящим через ячейки от последней строки к первой строке включительно. Первые р-разрядные входы k поисковых ячеек i-ой строки матрицы (i=1-n) соединены с р-разрядным выходом регистра 32_i. Р-разрядный выход регистра 33_j (j=1-m) соединен со вторыми р-разрядными входами всех поисковых ячеек, входящих B j-ый столбец матрицы. Выход каждой поисковой ячейки 34 _ij, кроме i=1 (первая строка матрицы), соединен с третьим входом поисковой ячейки 34_i-1j-1, кроме i=n (последняя строка матрицы). Выход поисковой ячейки 34 _1v (v=l-k), расположенной в первой строке матрицы, соединен с информационным входом 3 триггера 37_v позиции. На третий вход каждой поисковой ячейки, расположенной в последней строке матрицы, подается значение логической «1», задавая тем самым направление поиска по соответствующей диагонали от последней строки матрицы к первой строке включительно.

Триггера 37₁-37_k позиций хранят результат поиска в виде k-разрядного кода, в котором значением логической «1» отмечены позиции начала вхождений образца в текст. Триггер 37_i позиции (i=1-k) содержит три входа (первый и второй управляющие, третий одноразрядный информационный вход) и один выход. Первый вход блока 4 матричного поиска соединен соответственно с первыми входами k триггеров 37 позиций, вторые входы k триггеров 37 позиций соединены с выходом элемента 31 задержки. Выходы триггеров 37₁ -37_k позиций образуют k-разрядный информационный выход блока 4 матричного поиска.

Данное устройство, как и устройство-прототип, работает в режимах «Запись» и «Операция». Режим "Запись" строго соответствует алгоритму, описанному в устройстве-прототипе.

В алгоритме режима "Операция" дополнительно к выполняемым в устройстве-прототипе вводится операция, обозначаемая как «ПВ» и имеющая собственный код операции, который подается на соответствующий вход режима

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

Пусть устройство выполняет режим «Операция» с кодом операции «ПВ». На вход 7₁ «Начальная установка» операционного блока 3 и блока 4 матричного поиска подается импульсный сигнал начальной установки, который сбрасывает в нулевое состояние регистр 22 команд по его входу 1, регистр 30 по его входу 1, а также k триггеров 37 позиций по их входу 1, n регистров 32 по их входу 1 и m регистров 33 по их входу 1. После окончания действия сигнала начальной установки на вход 6 ₆ режима работы операционного блока 3 подается код операции «ПВ», который обнаруживается дешифратором 23 команд и со второго выхода операционного блока 3 на второй вход «Запись строк» блока 4 матричного поиска подается импульсный сигнал. Данный импульсный сигнал по входу «Запись строк» блока 4 матричного поиска подается соответственно на вторые входы разрешения записи n регистров 32 для хранения кодов символов образца и на вторые входы разрешения записи m регистров 33 для хранения кодов символов текста, обеспечивая тем самым запись n символов образца и m символов текста в параллельном коде с входов 4₃ и 4₄ устройства. Также импульсный сигнал по входу «Запись строк» блока 4 матричного поиска через элемент 31 задержки подается соответственно на вторые входы разрешения записи k триггеров 37 позиций. Элемент 31 задержки, выполненный в виде n пар инверторов, необходим для завершения процессов параллельного поиска вхождений по диагоналям характеристической матрицы, состоящей из поисковых ячеек 34₁₁-34_nm. Поиск начинается с ячеек последней строки характеристической матрицы. Начальный k-битовый характеристический вектор, равный 11...1, подается на третьи входы поисковых ячеек последней строки матрицы и определяет тем самым направление параллельного поиска по всем диагоналям характеристической матрицы от поисковых ячеек последней строки до поисковых

ячеек первой строки включительно. Время параллельного поиска вхождений не зависит от количества диагоналей, а определяется величиной Т=n_И, где _И - время задержки в элементе 36 И. По завершении процессов поиска импульсный сигнал с выхода элемента 31 задержки через время Т'=n2_инв (2_инв - время задержки на паре инверторов) записывает k-битовый результат поиска начала вхождений в триггера 37₁-37_k позиций. Выходы триггеров 37₁-37 _k позиций являются k-разрядным выходом блока 4 матричного поиска и образуют второй выход устройства 5₂ .

Выполнение алгоритма в режиме «Операция» на остальных операциях строго соответствует устройству-прототипу.

Однородная структура поисковых ячеек 34₁₁-34 _nm, составивших основу блока 4 матричного поиска, обусловливает реализацию устройства для параллельного поиска и обработки данных на СБИС программируемой логики (FPGA, CPLD, FLEX и др.) для необходимых разрядностей n, m образца и текста соответственно.

Используемые источники

1. Кулик, Б.А. Система поиска слов в произвольном тексте /Б.А.Кулик// Программирование. 1987. №1. С.49-50.

2. Максимов, В. Алгоритмы поиска, или как искать неизвестно что /В. Максимов// Монитор. 1995. №6. С.10-15.

3. А.с. 1485254 СССР, МКИ G06F 12/00. Устройство для адресации по содержанию блока памяти / А.Кулик, Э.В.Рахов, Н.Н.Востров, Т.П.Кониец - №4313200/24-24, заявл. 05.10.87; опубл. 07.06.89, Бюл.№21. 10 с., ил.

Устройство для параллельного поиска и обработки данных, содержащее первый и второй блоки хранения и сравнения ассоциативных признаков, блок памяти логических векторов и операционный блок, причем информационные входы первого и второго блоков хранения и сравнения ассоциативных признаков являются соответственно первым и вторым информационными входами устройства, а выходы блоков хранения и сравнения ассоциативных признаков соединены соответственно с первым и вторым адресными входами блока памяти логических векторов, входы задания режимов первого и второго блоков хранения и сравнения ассоциативных признаков и вход записи-считывания блока памяти логических векторов являются соответственно первым, вторым и третьим входами задания режимов устройства, а четвертый, пятый, шестой входы задания режимов устройства соответственно соединены с тремя входами кодов операций операционного блока, первый выход которого является первым выходом устройства, первый вход начальной установки устройства подключен к входу начальной установки операционного блока, второй вход начальной установки - к входам начальной установки первого и второго блоков хранения и сравнения ассоциативных признаков, первый и второй выходы блока памяти логических векторов подключены соответственно к первому и второму информационным входам операционного блока, отличающееся тем, что в него дополнительно введены, во-первых, дополнительный однобитовый выход в дешифраторе команд операционного блока, дополнительно введенный однобитовый выход в дешифраторе команд является вторым выходом операционного блока, во-вторых, блок матричного поиска, имеющего четыре входа и один выход, причем первый вход начальной установки устройства подключен к первому входу блока матричного поиска, второй вход которого соединен со вторым выходом операционного блока, третий и четвертый входы блока матричного поиска являются соответственно третьим и четвертым информационными входами устройства, а выход блока матричного поиска является вторым выходом устройства, при этом блок матричного поиска содержит элемент задержки, n регистров для хранения кодов символов образца разрядностью р бит каждый, m регистров для хранения кодов символов текста разрядностью р бит каждый, k триггеров позиций, а также характеристическую матрицу, состоящую из поисковых ячеек и имеющую геометрическую форму параллелограмма, размер матрицы - n×k поисковых ячеек (k=m-n+1 - количество строк, а также диагоналей в матрице), при этом каждый регистр для хранения кодов символов образца и каждый регистр для хранения кодов символов текста имеют соответственно три входа (первый и второй управляющие входы и третий информационный р-разрядный вход) и один р-разрядный выходу, каждая поисковая ячейка имеет три информационных входа (первый и второй входы разрядностью р бит каждый, третий - одноразрядный вход) и один выход, каждый триггер позиции имеет соответственно три входа (первый и второй управляющие входы и третий информационный вход) и один выход, каждая поисковая ячейка содержит двухвходовую схему сравнения на равенство р-разрядных кодов символов образца и текста и двухвходовой элемент И, причем первый и второй р-разрядные входы поисковой ячейки соединены соответственно с первым и вторым р-разрядными входами двухвходовой схемы сравнения на равенство соответственно, выход которой является первым входом двухвходового элемента И, второй вход которого соединен с третьим входом поисковой ячейки, выходом которой является выход двухвходового элемента И, причем первые р-разрядные входы всех поисковых ячеек i-й строки матрицы (i=1-n) соединены с р-разрядным выходом i-го регистра для хранения символа образца, р-разрядный выход j-го регистра для хранения кода символа текста (j=1-m) соединен соответственно со вторыми р-разрядными входами всех поисковых ячеек, входящих в j-й столбец матрицы, выход (i,j)-й поисковой ячейки, кроме i=l (первая строка матрицы), соединен с третьим входом (i-1,j-1)-й поисковой ячейки, кроме i=n (последняя строка матрицы), выход i-й (i=1-k) поисковой ячейки, расположенной в первой строке матрицы, соединен с третьим входом i-го триггера позиции, на третий вход каждой поисковой ячейки, расположенной в последней строке матрицы, подано значение логической «1», первый вход блока матричного поиска соединен соответственно с первыми входами n регистров для хранения кодов символов образца, а также с первыми входами m регистров для хранения кодов символов текста и первыми входами k триггеров позиций, второй вход «Запись строк» блока матричного поиска соединен со входом элемента задержки и со вторыми входами n регистров для хранения кодов символов образца и вторыми входами m регистров для хранения кодов символов текста соответственно, выход элемента задержки соединен со вторыми входами k триггеров позиций, выходы которых образуют информационный k-разрядный выход блока матичного поиска, третий вход блока матричного поиска состоит из n групп по р разрядов каждая группа, кодирующих символы образца, причем i-я группа разрядов (i=1-n) подается на третий р-разрядный вход i-го регистра для хранения кода символа образца, четвертый вход блока матричного поиска состоит из m групп разрядов по р разрядов каждая группа, кодирующих символы текста, причем j-я группа разрядов (j=1-m) подается на третий р-разрядный вход j-го регистра для хранения кода символов текста, каждая двухвходовая схема сравнения на равенство в составе поисковой ячейки состоит из р двухвходовых элементов суммы по модулю два с инверсией, на первые входы которых подается соответствующий разряд из i-й р-разрядной группы третьего входа блока матричного поиска, а на вторые входы двухвходовых элементов суммы по модулю два с инверсией - соответствующий разряд из j-й р-разрядной группы четвертого входа блока матричного поиска, выходы всех двухвходовых элементов суммы по модулю два с инверсией соединены с р-входовым элементом И, выход которого является выходом двухвходовой схемы сравнения на равенство.