Способ и ассоциативное матричное устройство параллельного поиска образца по его префиксам Российский патент 2021 года по МПК G11C15/00 G06F17/16 

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

Известен алгоритм СДВИГ-И для поиска вхождений образца в тексте [Максимов, В. Алгоритмы поиска, или как искать неизвестно что / В. Максимов // Монитор. 1995. № 6], состоящий в обработке n-характеристических векторов (двоичных векторов) по m разрядов в каждом векторе и последовательном вычислении характеристической матрицы из n строк и m столбцов (где m – количество символов в образце, n – количество символов в тексте) и позволяющий последовательно отыскивать все вхождения образца в текст. Для каждой позиции текста характеристическая матрица своими двоичными элементами отражает, является ли эта позиция текущим окончанием рассматриваемого образца. Недостатком данного алгоритма является последовательный характер обработки характеристических векторов, описывающих вхождение текущего префикса образца.

Известен подход к матричному поиску вхождений и пересечений слов [Патент 2430408 Российская Федерация, МПК G06F17/30. , опубл. 27.09.2011, Бюл. № 27, 2011 – 14 с.], состоящий в построении характеристической (двоичной) матрицы сравнений и выполнении m шагов обработки элементов, расположенных по m диагоналям матрицы, что позволяет одновременно отыскивать вхождения и пересечения слов своими префиксами и суффиксами. Недостаток данного способа заключается в невозможности выполнения поиска вхождений менее чем за m шагов при обработке элементов матрицы в составе m диагоналей.

Известен диагонально-шахматный способ поиска по образцу [Титенко Е.А. Диагонально-шахматный способ расслоения символов и параллельный поиск по образцу / Е.А. Титенко // Информационно-измерительные и управляющие системы. 2017. Т. 15. № 5. - С. 32-36], состоящий в расслоении ячеек образца длиной m символов на подстроки символов в четных и нечетных позициях и позволяющий в тексте длиной n символов вести параллельный поиск по двум подстрокам одновременно с объединением результатов текущих сравнений. Недостаток данного способа заключается в отсутствии возможности вести поиск в более чем в двух позициях текста одновременно.

Наиболее близким к предлагаемому способу является подход к ассоциативному поиску [Патент № 84615 РФ, МПК G11C 15/00. опубл. 10.07.2009. Бюл. № 19], заключающийся в выполнении m-1 шагов поиска, основанных на циклической реконфигурации исходного текста (строки) из одномерного в двумерный вид, что позволяет совмещать процессы сдвига и параллельного сравнения по столбцам матрицы. Недостатком данного подхода является выполнение сдвига влево текста ровно на 1 символ, что не позволяет выполнять поиск по образцу менее чем за m-1 шагов.

Предлагаемый способ параллельного поиска вхождения образца по его префиксам состоит из не более чем m-1 шагов, включающих на четных шагах параллельное сравнение образца (с учетом маски) с текстом в его матричном представлении и на нечетных шагах - сдвиг текста влево (к начальной позиции текста), отличающийся, во-первых, выполнением на каждом четном шаге дополнительных параллельно выполняемых m-1 сравнений по всем (m-1) его смещенным префиксам с учетом масок, при этом смещение префиксов друг относительно друга на 1 символ позволяет на текущем шаге параллельного поиска вести поиск в нескольких позициях одновременно; во-вторых, введением в рамках каждого четного шага этапа объединения и обработки матрицы сравнений путем выделения в ней номеров строки и столбца приоритетной логической «1», необходимых для вычисления значения сдвига текста, которое определяется по формуле СДВИГ=(d-1)×m+k-1, где d – номер вычисленной строки с приоритетной логической «1» в матрице сравнений, k- номер вычисленного столбца с приоритетной логической «1» в матрице сравнений, что обеспечивает на нечетных шагах сдвиг текста влево на вычисляемое количество символов.

Известна информационно-поисковая система [Патент № 2199778 РФ, МПК G06F17/30. опубл. 27.02. 2003. Бюл. № 6], содержащая блок памяти вхождений, блок памяти слов, блок управления, n блоков определения вхождений. Недостатком этого устройства является последовательный просмотр фрагментов текста c целью обнаружения всех вхождений (начальных позиций) образца, что приводит к избыточным затратам времени при поиске вхождений вследствие возвратов на первую позицию образца для очередного шага сравнения образца и текста.

Известна ассоциативная запоминающая матрица [Патент № 84615 РФ, МПК G11C 15/00. , опубл. 10.07.2009. Бюл. № 19], состоящая из n×m ассоциативных запоминающих элементов, n×m коммутационных элементов, представляющих собой 1-n-полюсники, n×m элементов-селекторов, маскирующего элемента последней строки. При проведении ассоциативного поиска обеспечивается реконфигурация ассоциативной запоминающей матрицы на четных и нечетных шагх за счет динамического перестроения соединений ассоциативных запоминающих элементов матрицы по направлению к первому элементу и организации параллельного поиска всех вхождений образца в исходной строке по столбцам ассоциативной матрицы. Количество шагов при такой параллельной организации поиска равно m-1.

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

Наиболее близким устройством к заявленному является ассоциативная запоминающая матрица маскированного поиска вхождений [Патент № 2469425 РФ, МПК G11C 15/00, опубл. 27.11.2011. Бюл. № 34], состоящая из n×m ассоциативных запоминающих элементов, содержащих n×m элементов исходного текста, n×m коммутационных элементов, представляющих собой 1-n-полюсники, n×m элементов-селекторов, маскирующего элемента последней строки и внешнего m-разрядного входа маскирования, подключенного к n×m ассоциативным запоминающим элементам и обеспечивающего параллельный поиск только по выделенным маской столбцам матрицы. При проведении ассоциативного поиска обеспечивается реконфигурация ассоциативной запоминающей матрицы за счет динамического перестроения соединений ассоциативных запоминающих элементов из матричного вида в одномерный вид (строку) и обратно по шагам поиска вхождений.

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

Технической задачей изобретения является уменьшение времени параллельного поиска вхождений образца в тексте за счет дополнения поискового образца набором его префиксов, смещенных друг относительно друга на 1 символ, что позволяет на текущем шаге поиска параллельно выполнить m сравнений и сделать переход вперед по тексту не менее чем на 1 символ. Как следствие, параллельный поиск реализуется не более чем за m-1 шагов поиска. При этом четный шаг работы состоит из этапа параллельных сравнений образца и его m-1 префиксов с текстом в его матричном представлении и этапа объединения и обработки матрицы сравнений для вычисления позиции следующего возможного вхождения образца на следующем шаге поиска. Нечетный шаг работы состоит из левого сдвига текста в его одномерном (линейном) виде на вычисляемое количество символов. На этапе параллельных сравнений смещение префиксов друг относительно друга на 1 символ позволяет параллельно выполнить m сравнений и при обнаружении вхождения t-го префикса длиной m-t символов (t=1-m) в составе текста на следующем шаге осуществить его сдвиг влево (сдвиг в сторону начальной позиции) на вычисляемое количество символов.

Решение технической задачи достигается тем, что в ассоциативное матричное устройство параллельного поиска образца по его префиксам (далее – устройство), содержащее одну (базовую) ассоциативную запоминающую матрицу маскированного поиска вхождений (далее – матрица), в составе n×m ассоциативных запоминающих элементов, первые входы которых в соответствующих строках матрицы объединены и являются соответствующими внешними адресными входами, четвертые входы ассоциативных запоминающих элементов подключены к внешнему входу синхронизации «CLOCK», пятые входы ассоциативных запоминающих элементов соединены с соответствующими внешними входами маскирования разрядных срезов (столбцов) матрицы, первые выходы ассоциативных запоминающих элементов в соответствующих столбцах матрицы объединены и образуют m-разрядный информационный выход, n×m коммутационных элементов, входы которых подключены ко вторым выходам соответствующих ассоциативных запоминающих элементов, а выходы коммутационных элементов соответственно объединены и являются, соответствующими выходами опроса, кроме n-й строки матрицы, n×m элементов-селекторов, первые и вторые входы которых являются соответственно первыми и вторыми информационными входами матрицы в соответствующих столбцах, третьи входы элементов-селекторов подключены к первым выходам ассоциативных запоминающих элементов соответствующей строки матрицы, при этом третьи входы элементов-селекторов крайнего правого столбца матрицы подключены к первым выходам соответствующих ассоциативных запоминающих элементов крайнего левого столбца матрицы, расположенных строкой ниже, четвертые входы элементов-селекторов подключены к внешнему входу «РЕЖИМ», первые и вторые выходы n×m элементов-селекторов являются соответственно вторыми и третьими информационными входами ассоциативных запоминающих элементов соответствующей строки матрицы, маскирующего элемента, первый вход которого подключен к внешнему входу синхронизации «CLOCK», второй вход – к внешнему входу «РЕЖИМ», третий вход – к внешнему входу «СБРОС», а выход является индикатором произошедших реконфигураций матрицы из двухмерного вида в одномерный и обратно, двухвходового элемента И, первый вход которого подключен к выходу опроса n-й строки матрицы, второй вход – к выходу маскирующего элемента, а выход двухвходового элемента И является маскируемым выходом опроса n-й строки матрицы, ограничительного резистора, соединенного с третьим входом nm-ого элемента-селектора и источником питания, в устройство введены m-1 аналогичных ассоциативных запоминающих матриц маскированного поиска вхождений, имеющих совпадающий состав элементов и связи между ними, введены блок обработки матрицы сравнений, блок вычисления сдвига, также введены управляющие однобитовые входы устройства «ЗАПИСЬ 1», «ЗАПИСЬ 2», «ЗАПИСЬ 3», внешний вход «m» устройства, задающий длину образца в символах, два информационных выхода устройства «ВХОЖД», «СДВИГ», при этом внешний однобитовый вход «РЕЖИМ» подключен к четверым входам n×m элементов-селекторов и ко второму входу маскирующего элемента каждой из введенных m-1 матриц, внешний однобитовый вход «CLOCK» подключен к четверым входам n×m ассоциативных запоминающих элементов и к первому входу маскирующего элемента каждой из введенных m-1 матриц, внешний однобитовый вход «СБРОС» подключен к третьему входу маскирующего элемента, входящего в состав каждой из введенных m-1 матриц, i-й внешний адресный вход (i=1-n) подключен к первым входам ассоциативных запоминающих элементов в i-ых строках каждой из введенных m-1 матриц, jw-ые внешние входы маскирования столбцов подключены к пятым входам ассоциативных запоминающих элементов j-ых столбцов каждой из m-1 введенных матриц (j=1-m, w=1 - m–1), первые и вторые информационные входы разрядностью по m бит каждый вход в соответствующих столбцах подключены к первым и вторым входам n×m элементов-селекторов каждой из m-1 введенных матриц, первые (m-разрядные) выходы, образуемые выходами ассоциативными запоминающих элементов в соответствующих столбцах по каждой из введенных m-1 матриц, дополняются m-разрядным выходом, формируемым выходами ассоциативных запоминающих элементов в соответствующих столбцах базовой матрицы, совместно образуют m внешних информационных выходов устройства разрядностью по m бит каждый выход, вторые (n-разрядные) выходы, образуемые выходами коммутационных элементов в соответствующих строках по каждой из введенных m-1 матриц, дополняются n-разрядным выходом, формируемым коммутационными элементами в соответствующих строках базовой матрицы, совместно образуют m выходов опроса разрядностью по n бит каждый выход; блок обработки матрицы сравнений состоит из m регистров опроса с тремя входами, m многовходовых элементов ИЛИ на n разрядов каждый, арбитра, m-разрядного шифратора столбцов, мультиплексора, n-разрядного шифратора строк, первого выходного регистра для хранения номера столбца приоритетной логической «1» в матрице сравнений, второго выходного регистра для хранения номера строки приоритетной логической «1» в матрице сравнений, имеет m n-разрядных информационных входов, однобитовый вход «СБРОС» начальной установки, однобитовые входы записи данных «ЗАПИСЬ 1» и «ЗАПИСЬ 2», являющиеся внешними входами устройства, два выхода «Номер столбца k», «Номер строки d», которые задают позицию вхождения образца в матричном представлении текста, один однобитовый выход «ВХОЖД», являющийся внешним выходом устройства, при этом каждый из m информационных n-разрядных входов блока обработки матрицы сравнений соединен с соответствующим n-разрядным выходом опроса одной из m ассоциативных запоминающих матриц маскированного поиска вхождений, на первые входы двух выходных регистров, а также на первые входы m регистров опроса подан однобитовый вход «СБРОС» начальной установки, на вторые входы m регистров опроса подан однобитовый вход «ЗАПИСЬ 1», на вторые входы первого и второго выходных регистров подан однобитовый вход «ЗАПИСЬ 2», третий вход v-го регистра опроса соединен с v-ым n-разрядными выходом опроса (11₁-11_n)^v v-й ассоциативной запоминающей матрицы маскированного поиска вхождений (v=1-m), выходы m регистров опроса соединены со входами соответствующих многовходовых элементов ИЛИ на n разрядов каждый, а также поданы на m информационных входов мультиплексора, выходы многовходовых элементов ИЛИ поданы на m входов арбитра, выход первого многовходового элемента ИЛИ является третьим выходом «ВХОЖД» блока обработки матрицы сравнений и внешним выходом устройства, m-разрядный выход арбитра подан на вход m-разрядного шифратора столбцов, выход которого подключен к информационному входу первого выходного регистра, выход которого подключен к адресному входу мультиплексора и является первым выходом «Номер столбца k» блока обработки матрицы сравнений, n-разрядный выход мультиплексора подан на вход n-разрядного шифратора строк, выход которого подан подключен к информационному входу второго выходного регистра, выход которого является вторым выходом «Номер строки d» блока обработки матрицы сравнений; блок вычисления сдвига состоит из двух вычитателей, умножителя, сумматора и выходного регистра на три входа, данный блок имеет три информационных входа, два управляющих однобитовых входа «ЗАПИСЬ 3», «СБРОС» и один информационный выход «СДВИГ», при этом первые входы первого и второго вычитателей подключены соответственно к первому и второму выходам «Номер столбца k» и «Номер строки d» блока обработки матрицы сравнений, на вторые входы первого и второго вычитателей подано значение 1, выход второго вычитателя соединен со вторым входом умножителя, первый вход которого соединен с внешним входом устройства - длина образца «m», выход умножителя соединен со вторым входом сумматора, первый вход которого соединен с выходом первого вычитателя, выход сумматора подан на третий (информационный) вход выходного регистра, на первый вход которого подан однобитовый вход «СБРОС» начальной установки, однобитовый управляющий вход «ЗАПИСЬ 3» подан на второй вход выходного регистра, выход которого является внешним выходом «СДВИГ» устройства; арбитр, имеющий m однобитовых входов и m однобитовых выходов и состоящий из m-1 элементов И c z входами каждый (z=2-m) (из z входов первый вход прямой, а остальные – инверсные), при этом z-й вход арбитра соединен с первым входом каждого z-го элемента И (z=2-m), выход z-го элемента И является z-ым выходом арбитра, и соединен с каждым v-ым входом каждого из z+1 элементов И (v=2 – m-1), кроме z=m, выход m-го элемента И является m-ым выходом арбитра, первый вход арбитра является его первым выходом и соединен с z-ым входом каждого z элемента И (z=2-m).

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

На фигурах 1 а), 1 б), 1 в) демонстрируется пример параллельного поиска для текста S=1000001001011110, образца O=1001. Поиск реализуется за три шага (шаг 0, шаг 1, шаг 2) по образцу O=1001 и трем его префиксам Prf₁=x100, Prf₂=xx10, Prf₃=xxx1 (где x – маскируемая позиция символа) и маскам, соответствующим образцу и префиксам, M0=1111, M1=0111, M2=0011, M3=0001.

На шаге 0 (фиг. 1а) (этап параллельных сравнений) выполняется m=4 сравнений образца O и трех префиксов Prf_1, Prf_2, Prf₃ с соответствующими им масками с текстом S=1000001001011110, имеющим матричное представление 4×4. Векторы-столбцы, полученные для m=4 сравнений, образуют матрицу сравнений размером 4×4, при этом первый и второй векторы-столбцы сравнений, полученные по образцу O и префиксу Prf₁, описывают отрицательные результаты сравнений. Далее на шаге 0 (этап объединения и обработки матрицы сравнений) выполняется обработка матрицы сравнений. В матрице сравнений выделяется приоритетная логическая «1», указывающая следующее возможное вхождение образца. Эта приоритетная логическая «1» имеет координаты, описываемые вектором-столбцом (0 1 0 0)^T и вектором-строкой (0 0 1 0). Вектора соответствуют номерам строки и столбца приоритетной логической «1», равным d=2, k=3. Данные номера преобразуются в значение СДВИГ=(2-1)×4+3-1=6.

На шаге 1 (фиг. 1б) выполняется сдвиг влево текста S на 6 символов.

На шаге 2 (фиг. 1в) (этап параллельных сравнений) выполняется m=4 сравнений образца O и трех префиксов Prf_1, Prf_2, Prf₃ с соответствующими им масками с текстом S=1001011110xxxxxx, имеющим матричное представление 4×4 (x – несущественный символ). Векторы-столбцы, полученные для m=4 сравнений, образуют матрицу сравнений размером 4×4, при этом первый вектор-столбец сравнений, полученный по образцу O, описывает положительный результат сравнений. Далее на шаге 2 (этап объединения и обработки матрицы сравнений) выполняется обработка матрицы сравнений. В матрице сравнений выделяется приоритетная логическая «1», указывающая вхождение образца. Эта приоритетная логическая «1» имеет координаты, описываемые вектором-столбцом (1 0 0 0)^T и вектором-строкой (1 0 0 0). Вектора соответствуют номерам строки и столбца приоритетной логической «1», равные d=1, k=1. Вхождение образца найдено. Формируется сигнал «ВХОЖД»=1, поиск прекращается.

Устройство (фиг. 2) содержит m ассоциативных запоминающих матриц маскированного поиска вхождений, блок обработки матрицы сравнений, блок вычисления сдвига. Устройство имеет m информационных входов
{19₁-19_m}¹ - {19₁-19_m}^m, m информационных входов {20₁-20_m}¹ - {20₁-20_m}^m, m входов масок {45₁-45_m}¹ - {45₁-45_m}^m, n адресных входов устройства 8₁–8_n, m информационных выходов {9₁-9_m}¹ - {9₁-9_m}^m, m выходов {11₁-11_n}¹-{11₁-11_n}^m опроса, информационный вход «m», задающий длину образца в символах, шесть управляющих однобитовых входов «РЕЖИМ», «CLOCK», «СБРОС», «ЗАПИСЬ 1», «ЗАПИСЬ 2», «ЗАПИСЬ 3», информационный выход «СДВИГ», а также однобитовый выход «ВХОЖД», логическая «1» на котором является признаком положительного результата поиска вхождения.

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

Структура ассоциативных запоминающих матриц 46₁-46_m маскиро-ванного поиска вхождений строго соответствует устройству-прототипу в структурном и функциональном отношении, состоит из совпадающих элементов и связей между ними с учетом индексации информационных входов устройства {19₁-19_m} и {20₁-20_m} на m вариантов представления образца и всех его префиксов в соответствующей матрице по ее v-му индексу (v=1-m), входов масок {45₁-45_m} на m вариантов их представлений в соответствующей матрице по ее v-му индексу (v=1-m), адресных входов устройства 8₁–8_n, подаваемых параллельно в m матриц, информационных выходов устройства {9₁-9_m} по каждой из m матриц, выходов опроса {11₁-11_n} по каждой из m матриц, а также совпадающего подключения однобитовых управляющих входов «РЕЖИМ», «CLOCK», «СБРОС» во всех ассоциативных запоминающих матрицах 46₁ – 46_m маскированного поиска вхождений.

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

Блок 47 (фиг. 7) обработки матрицы сравнений состоит из m входных регистров 47₁-47_m опроса, имеющих первый и второй однобитовые управляющие входы, третий n-разрядный информационный вход, m многоразрядных элементов 48 ИЛИ на n разрядов каждый, m-разрядного арбитра 49, m-разрядного шифратора 50 столбцов, выходного регистра 51 с тремя входами (первые два – однобитовые управляющие, третий выход - m-разрядный информационный), m+1-входового мультиплексора 52, где первые m входов являются информационными (по n разрядов каждый) и m+1-ый вход мультиплексор 52 – адресный, n-разрядного шифратора 53 строк, выходного регистра 54 с тремя входами (первые два – однобитовые управляющие, третий выход – n-разрядный информационный). Блок 47 обработки матрицы сравнений имеет m n-разрядных входов, однобитовый управляющий вход «СБРОС» начальной установки, однобитовые управляющие входы записи данных «ЗАПИСЬ 1» и «ЗАПИСЬ 2», являющиеся внешними входами устройства, два выхода «Номер столбца k», «Номер строки d», а также однобитовый выход «ВХОЖД», являющийся выходом устройства.

Каждый из m n-разрядных входов {11₁-11_n}¹-{11₁-11_n}^m блока 47 обработки матрицы сравнений соединен с соответствующим n-разрядным выходом опроса ассоциативных запоминающих матриц 46₁-46_m маскированного поиска вхождений, на первые входы регистров 47₁-47_m опроса, а также на первые входы двух выходных регистров 51, 54 подан управляющий вход «СБРОС» начальной установки, на вторые входы регистров 47₁-47_m опроса подан управляющий вход «ЗАПИСЬ 1», на вторые входы выходного регистра 51 и выходного регистра 54 подан однобитовый вход «ЗАПИСЬ 2», третий вход v-го регистра опроса 47_v соединен с v-ым n-разрядным выходом опроса (11₁-11_n)^v матрицы 46_v (v=1-m), выходы регистров 47₁-47_m опроса соединены со входами соответствующих многовходовых элементов 48₁-48_m ИЛИ, а также поданы на m информационных входов мультиплексора 52, выходы всех многовходовых элементов 48₁-48_m ИЛИ поданы на m-разрядный вход арбитра 49, выход первого многовходового элемента 48₁ ИЛИ является внешним выходом устройства «ВХОЖД», m-разрядный выход арбитра 49 подан на вход m-разрядного шифратора 50 столбцов, выход которого подключен к информационному входу регистра 51, выход регистра 51 подключен к адресному входу мультиплексора 52 и является первым выходом «Номер столбца k» блока 47 обработки матрицы сравнений, n-разрядный выход мультиплексора 52 подан на вход n-разрядного шифратора строк 53, выход которого подключен к информационному входу регистра 54, выход регистра 54 является вторым выходом «Номер строки d» блока 47 обработки матрицы сравнений;

Блок 50 (фиг. 8) вычисления сдвига состоит из первого и второго вычитателей 55 и 56, умножителя 57, сумматора 58 и выходного регистра 59. Блок 50 вычисления сдвига имеет три информационных входа, два управляющих однобитовых входа устройства «СБРОС», «ЗАПИСЬ 3» и один информационный выход «СДВИГ», являющийся выходом устройства. Первые входы первого и второго вычитателей 55 и 56 подключены соответственно к первому и второму выходам «Номер столбца k» и «Номер строки d» блока 47 обработки матрицы сравнений, на вторые входы первого и второго вычитателей 55 и 56 подано значение 1, выход второго вычитателя 56 соединен со вторым входом умножителя 57, первый вход которого соединен с внешним входом устройства - длина образца «m», выход умножителя 57 соединен со вторым входом сумматора 58, первый вход которого соединен с выходом первого вычитателя 55, выход сумматора 58 подан на третий (информационный) вход выходного регистра 59, на первый вход которого подан однобитовый вход «СБРОС» начальной установки, однобитовый управляющий вход «ЗАПИСЬ 3» подан на второй вход выходного регистра 59, выход которого является внешним выходом «СДВИГ» устройства.

Арбитр 49 (фиг. 9) имеет m однобитовых входов и m однобитовых выходов, состоит из m-1 элементов 51_z И c z входами каждый (z=2-m), из z входов элементов 51_z И первый вход прямой, а остальные – инверсные, z-й вход арбитра 49 соединен с первым входом каждого элемента 51_z И, выход элемента 51_z И является z-ым выходом арбитра 49 и соединен с каждым v-ым входом каждого из элементов 51_z+1 И (v=2 – m-1), кроме z=m, выход элемента 51_m И является m-ым выходом арбитра 49, первый вход арбитра 49 является его первым выходом и соединен с z-ым входом каждого 51_z элемента И (z=2-m).

Ассоциативное матричное устройство параллельного поиска образца по его префиксам, как и устройство-прототип, работает в одном из четырех режимов: запись, чтение, ассоциативный маскированный поиск, реконфигурация. Ассоциативный маскированный поиск выполняется одновременно по m ассоциативным запоминающим матрицам маскированного поиска вхождений (одна базовая матрица и m-1 введенные матрицы). Режим ассоциативного маскированного поиска реализуется в два этапа: этап параллельных сравнений по m матрицам, этап объединения и обработки матрицы сравнений. Режим реконфигурации матрицы необходим для ее преобразования в одномерный (линейный) вид и выполнения сдвига влево символов текста на вычисляемое количество символов.

Работа устройства в любом из его режимов начинается с подачи на третьи входы 39₁-39_m маскирующих элементов 36₁ -36_m всех матриц 46₁-46_m сигнала «СБРОС»=1, инициируя сброс двоичных счетчиков 42₁-42_m и получение на выходах 40₁-40_m маскирующих элементов 36₁-36_m значения логической «1» во всех матрицах 46₁-46_m Также сигнал «СБРОС»=1 подается на первые входы регистров 47₁-47_m опроса, выходных регистров 51, 54 блока 47 обработки матрицы сравнений, на первый вход выходного регистра 59 блока 50 вычисления сдвига во всех матрицах 46₁-46_m.

Режим чтения соответствует алгоритму, описанному в устройстве-прототипе, с учетом индексации информационных входов устройства {19₁-19_m} и {20₁-20_m}, входов масок {45₁-45_m} в соответствующей матрице 46_v по ее v-му индексу (v=1-m), адресных входов устройства 8₁–8_n, подаваемых параллельно в m матриц 46₁-46_m, информационных выходов устройства {9₁-9_m} по каждой из m матриц 46₁-46_m, информационных выходов опроса {11₁-11_n} по каждой из m матриц 46₁-46_m, а также совпадающего подключения однобитовых управляющих входов «РЕЖИМ», «CLOCK» в m матрицах 46₁-46_m и установления на этих однобитовых входах значений, соответствующих режиму чтения, а также совпадения всех элементов и связей между ними (элементы-селекторы, ассоциативны запоминающие элементы) в составе m матриц 46₁-46_m. При этом на информационные входы масок {45₁-45_m}¹-{45₁-45_m}^m в m матрицах 46₁-46_m подается m-разрядное значение 11…1, что обеспечивает чтение данных из j-ых строк из m матриц 46₁-46_m (j=1-n). Адрес j-ой строки для всех матриц 46₁-46_m устройства задается по единому адресному входу 8₁–8_n.

Чтение данных из j-ых строк всех матриц 46₁-46_m (j=1-n) реализуется следующим образом. На информационные входы {19₁-19_m}^v и {20₁-20_m}^v (v=1-m) всех матриц 46₁-46_m подается комбинация «00», что обеспечивает перевод RS-триггеров ассоциативных запоминающих элементов 1 соответствующей строки во всех матрицах 46₁-46_m в режим выдачи данных. Во всех матрицах 46₁-46_m данная комбинация поступает на первые 13 и вторые 14 входы всех элементов-селекторов 12 соответствующих строк, выбранных по адресному входу 8₁-8_n. Во всех матрицах 46₁-46_m на четвертый вход 16 соответствующих элементов-селекторов 12 подается сигнал «РЕЖИМ»=0, что осуществляет подключение первых 13 и вторых 14 входов элементов-селекторов 12 к первым 17 и вторым 18 выходам элементов-селекторов 12 и соответственно ко вторым 3 и третьим 4 входам ассоциативных запоминающих элементов 1 соответствующих строк всех матриц 46₁-46_m. Далее для всех матриц 46₁-46_m на соответствующие адресные входы 2 ассоциативных запоминающих элементов 1 соответствующих строк подается логическая «1», на соответствующие четвертые входы 5 ассоциативных запоминающих элементов 1 соответствующих строк матриц 46₁-46_m подается сигнал синхронизации «CLOCK»=1, инициируя тем самым считывание m-разрядного фрагмента текста (битовой строки) в инверсном коде с первых выходов 6 ассоциативных запоминающих элементов 1, соответствующих строк из всех матриц 46₁-46_m, по адресу, задаваемому логической «1» по одному из входов 8₁÷8_n. Считываемые m-разрядные коды параллельно выдаются на соответствующие выходы устройства {9₁-9_m}¹ - {9₁-9_m}^m.

Режим записи соответствует алгоритму, описанному в устройстве-прототипе, с учетом индексации информационных входов устройства {19₁-19_m} и {20₁-20_m}, входов масок {45₁-45_m} в соответствующей матрице 46_v по ее v-му индексу (v=1-m), адресных входов устройства 8₁–8_n, подаваемых параллельно в m матриц 46₁-46_m, информационных выходов устройства {9₁-9_m} по каждой из m матриц 46₁-46_m, информационных выходов опроса {11₁-11_n} по каждой из m матриц 46₁-46_m, а также совпадающего подключения однобитовых управляющих входов «РЕЖИМ», «CLOCK» в m матрицах 46₁-46_m и установления на этих однобитовых входах значений, соответствующих режиму записи, а также совпадения всех элементов и связей между ними (элементы-селекторы, ассоциативны запоминающие элементы) в составе m матриц 46₁-46_m.

Запись данных в j-е строки матриц 46₁-46_m (j=1-n) реализуется следующим образом. На информационные входы {19₁-19_m}^v и {20₁-20_m}^v (v=1-m) всех матриц 46₁-46_m параллельно подаются коды m элементов текста (битовой строки), элемент такого кода задается одной из следующих комбинаций: 10 – код единицы, 01 – код нуля. На входы всех масок {45₁-45_m}¹- {45₁-45_m}^m матриц 46₁-46_m подается m-разрядное значение маски 11 …11. Во всех матрицах на четвертый вход 16 соответствующих элементов-селекторов 12 подается сигнал «РЕЖИМ»=0, что осуществляет подключение первых 13 и вторых 14 входов элементов-селекторов 12 к первым 17 и вторым 18 выходам элементов-селекторов 12 и соответственно ко вторым 3 и третьим 4 информационным входам ассоциативных запоминающих элементов 1 соответствующих строк во всех матрицам 46₁-46_m. Далее для всех матриц 46₁-46_m на соответствующий адресный вход 2 ассоциативных запоминающих элементов 1 соответствующих строк подается логическая «1», на соответствующие четвертые входы 5 ассоциативных запоминающих элементов 1 подается сигнал синхронизации «CLOCK»=1, что обеспечивает запись m элементов текста с учетом масок в j-ые строки матриц 46₁-46_m по адресу, задаваемому логической «1» в одном из входов 8₁÷8_n (j=1-n).

Перед выполнением ассоциативного маскированного поиска выполняется настройка ассоциативных запоминающих элементов 1 в матрицах 46₁-46_m, заключающаяся в предварительной записи в регистры 28 всех коммутационных элементов 10 всех матриц 46₁-46_m настроечных кодов, обеспечивающих подключение вторых выходов 7 соответствующих ассоциативных запоминающих элементов 1 к соответствующим выходам {11₁-11_n}^v опроса в каждой матрице 46_v (v=1-m). В общем случае, настроечный код может быть как униполярным, обеспечивающим подключение выхода 7 ассоциативного запоминающего элемента 1 к одному выбранному выходу 11 опроса, так и k-полярным (k=1...n), где k – число выходов 11 опроса матрицы, к которым подключается выход 7 ассоциативного запоминающего элемента 1. В рассматриваемом устройстве настроечный код коммутационных элементов 10 соответствующих строк всех матриц имеет следующий вид: 29_i1 = 100..0, 29_i2 = 010..0, …, 29_in = 000..1 (i=1-m), что позволяет получить инверсное значение выходов 7 соответствующих ассоциативных запоминающих элементов 1 на выходах {11₁-11_n}^v результатов опросов соответствующих строк в каждой матрице 46_v (v=1-m).

Этап параллельных сравнений реализуется следующим образом. На информационные входы {19₁-19_m}^v и {20₁-20_m}^v (v=1-m) всех матриц 46₁-46_m поступает комбинация сигналов: 00 – код выдачи. Во всех матрицах 46₁-46_m устройства данная комбинация поступает на первые 13 и вторые 14 входы всех элементов-селекторов 12 соответствующих строк, выбранных по адресному входу 8₁-8_n. Во всех матрицах 46₁-46_m на четвертый вход 16 соответствующих элементов-селекторов 12 подается сигнал «РЕЖИМ»=0, что осуществляет подключение первых 13 и вторых 14 входов элементов-селекторов 12 к первым 17 и вторым 18 выходам элементов-селекторов 12 и соответственно ко вторым 3 и третьим 4 входам ассоциативных запоминающих элементов 1 соответствующих строк матриц 46₁-46_m. На входы масок {45₁-45_m}^v для каждой матрицы 46_v (v=1-m) подаются сформированные m-разрядные значения масок 11…11, 01…11, … 00…11, 00…01 соответственно, что обеспечивает проведение параллельных сравнений образца и его m-1 префиксов, поданных на информационные входы {19₁-19_m}¹-{19₁-19_m}^m и {20₁-20_m}¹-{20₁-20_m}^m. При этом интерпретация бит в маске следующая: логическая «1» – разрядный срез (столбец матрицы) не замаскирован, т.е. поиск разрешен, логический «0» – разрядный срез замаскирован (столбец матрицы), т.е. поиск запрещен – результаты сравнения положительные. Затем на соответствующие четвертые входы 5 ассоциативных запоминающих элементов 1 соответствующих строк матриц 46₁-46_m подается сигнал синхронизации «CLOCK»=1, инициируя сравнение с содержимым триггера 21 соответствующего ассоциативного запоминающего элемента 1 с учетом бита маскирования. Если происходит несовпадение i-го кода элемента образца (префикса) и iv-го кода элемента текста или соответствующий разрядный срез (столбец матрицы) в одной из матриц 46_q замаскирован (i=1-m, v=1-m, q∈1-m), то второй выход 7 ассоциативного запоминающего элемента 1 в матрице 46_q сохраняет уровень логического «0» и, следовательно, на соответствующих выходах {11₁-11_n}^q опроса матрицы 46_q, к которым подключен выход 7 этого ассоциативного запоминающего элемента 1, устанавливается уровень логической «1» (q∈1-m). Если происходит совпадение i-го кода элемента образца и iv-го кода элемента текста и соответствующий разрядный срез (столбец матрицы) в одной из матриц 46_q не замаскирован, то на выходе 7 такого ассоциативного запоминающего элемента 1 в матрице 46_q появляется уровень логической «1», и, следовательно, на соответствующих выходах {11₁-11_n}^v опроса матрицы 46_1q, к которым подключен выход 7 этого ассоциативного запоминающего элемента 1, устанавливается уровень логического «0» (q∈1-m). При этом если была произведена хотя бы один раз реконфигурация матрицы, то на выходах 11_n опроса ассоциативных запоминающих элементов 1 n-ой строки каждой матрицы 46_v формируется значение логического «0» в результате установки на выходе маскирующего элемента 36 значения логического «0» (v=1-m).

Этап объединения и обработки матрицы сравнений реализуется следующим способом. В результате m параллельных сравнений в матрицах 46₁-46_m на соответствующих выходах {11₁-11_n}¹-{11₁-11_n}^m формируются результаты сравнений в виде n-разрядных векторов-столбцов, которые поступают в блок 47 обработки матрицы сравнений и по управляющему входу «ЗАПИСЬ 2» записываются в регистры 47₁-47_m. Выход каждого регистра 47_v поступает на вход многоразрядного элемента 48_v ИЛИ, что позволяет определить положительное сравнение в соответствующей матрице 46_v (v=1-m). Одновременно с этим выход каждого регистра 47_v поступает на v-й информационный вход мультиплексора 52. Однобитовые выходы многовходовых элементов ИЛИ 48₁–48_m поступают на m-разрядный вход арбитра, где происходит выделение приоритетной логической «1» среди m столбцов матрицы сравнений. Также однобитовый выход многовходового элемента ИЛИ 48₁ является внешним выходом «ВХОЖД» устройства, логическая «1» на котором является признаком вхождения образца в тексте. Полученный с выхода арбитра 49 m-разрядный код проходит через шифратор 50 столбцов, на выходе которого формируется двоичный весовой код номера столбца приоритетной логической «1». Этот двоичный код по входу «ЗАПИСЬ 3» заносится в регистр 51, двоичное значение на его выходе «Номер столбца k» показывает номер столбца приоритетной логической «1» в матрице сравнений и, соответственно, в матричном представлении текста. Выход регистра 51 также подается на адресный вход мультиплексора 52, который управляет выбором результата сравнений q-ой ассоциативной запоминающей матрицы 46_q маскированного поиска вхождений (q∈1-m), содержащей приоритетную логическую «1». Выбранный q-ой информационный вход результатов сравнений разрядностью n бит с выхода мультиплексора 52 проходит через шифратор 53 строк, формируя на его выходе двоичный весовой код номера строки приоритетной логической «1». Этот двоичный код по входу «ЗАПИСЬ 3» заносится в регистр 54, двоичное значение на его выходе «Номер строки d» показывает номер строки приоритетной логической «1» в матрице сравнений и, соответственно, в матричном представлении текста.

Блок 50 вычисления сдвига выполняет расчет количества сдвигов символов текста в его одномерном представлении согласно формулы СДВИГ=(d-1)×m+k-1, где d – номер вычисленной строки с приоритетной логической «1» в матрице сравнений, k – номер вычисленного столбца с приоритетной логической «1» в матрице сравнений, m – количество символов в образце.

В блоке 50 на первые входы первого и второго вычитателей 55 и 56 соответственно подаются значения с выходов «Номер столбца k» и «Номер строки d» блока 47 обработки матрицы сравнений, на вторые входы первого и второго вычитателей 55 и 56 подается значение 1, выход второго вычитателя 56, содержащий уменьшенный на 1 значение номера строки приоритетной логической «1» в матрице сравнений, соединен со вторым входом умножителя 57, на первый вход которого подано значение длины образца «m», выход первого вычитателя 55, содержащий уменьшенный на 1 значение номера столбца приоритетной логической «1» в матрице сравнений, соединен с первым входом сумматора 58, второй вход которого подключен к выходу умножителя 57, на выходе сумматора 58 вычисляется количество сдвигов влево символов текста, которое записывается в регистр 59, выход которого является внешним выходом «СДВИГ» устройства.

Режим реконфигурации соединений ассоциативных запоминающих элементов 1 в матрицах 46₁-46_m соответствует алгоритму, описанному в устройстве-прототипе с учетом индексации информационных входов устройства {19₁-19_m}¹ - {19₁-19_m}^m и {20₁-20_m}¹ - {20₁-20_m}^m, а также входов масок {45₁-45_m}¹ - {45₁-45_m}^m в m ассоциативных запоминающих матрицах 46₁ - 46_m маскированного поиска вхождений, состава и подключения входов и выходов ассоциативных запоминающих элементов 1, элементов-селекторов 12, коммутационных элементов 10, маскирующего элемента 36, двухвходового элемента 44 И в матрицах46₁ - 46_m, а также подачи во всех матрицах 46₁ - 46_m в структуре элементов-селекторов 12 сигнала «РЕЖИМ»=1 на адресные входы мультиплексоров 33, 34 и подачи сигнала синхронизации «CLOCK»=1, инициируя тем самым запись со сдвигом новых значений ассоциативных запоминающих элементов 1 из предыдущих по строке/столбцу ассоциативных запоминающих элементов 1 в пределах каждой матрицы 46_v (v=1-m). Количество сигналов синхронизации «CLOCK»=1, поданное в режиме реконфигурации, равно вычисляемому в блоке 50 значению выхода «СДВИГ». Таким образом, на каждом нечетном шаге осуществляется переход матрицы из двухмерного вида в одномерный вид и последовательный сдвиг текста влево на вычисляемое количество элементов (по выходу «СДВИГ») по направлению к первому символу текста.

Настоящее техническое решение относится к области вычислительной техники. Технический результат заключается в уменьшении времени операции поиска вхождений образца в тексте на основе ассоциативной памяти. Технический результат достигается за счёт параллельного поиска, который реализуется не более чем за m-1 шагов поиска. При этом четный шаг работы состоит из этапа параллельных сравнений образца и его m-1 префиксов с текстом в его матричном представлении и этапа объединения и обработки матрицы сравнений для вычисления позиции следующего возможного вхождения образца на следующем шаге поиска. Нечетный шаг работы состоит из левого сдвига текста в его одномерном (линейном) представлении на вычисляемое количество символов. На этапе параллельных сравнений смещение префиксов друг относительно друга на 1 символ позволяет параллельно выполнить m сравнений и при обнаружении вхождения t-го префикса длиной m-t символов (t=1-m) в составе текста на следующем шаге осуществить его сдвиг влево (сдвиг в сторону начальной позиции) на вычисляемое количество символов. 2 н.п. ф-лы, 9 ил.

1. Способ параллельного поиска вхождения образца по его префиксам, состоящий из не более чем m-1 шагов, включающих на четных шагах параллельное сравнение образца, с учетом маски, с текстом в его матричном представлении и на нечетных шагах – сдвиг текста влево к начальной позиции текста, отличающийся выполнением на каждом четном шаге дополнительных параллельно выполняемых m-1 сравнений по всем m-1 его смещенным префиксам с учетом масок, при этом смещение префиксов друг относительно друга на 1 символ позволяет на текущем шаге параллельного поиска вести поиск в нескольких позициях одновременно; введением в рамках каждого четного шага этапа объединения и обработки матрицы сравнений путем выделения в ней номеров строки и столбца приоритетной логической «1», необходимых для вычисления значения сдвига текста, которое определяется по формуле

СДВИГ=(d-1)×m+k-1, где

d – номер вычисленной строки с приоритетной логической «1» в матрице сравнений,

k – номер вычисленного столбца с приоритетной логической «1» в матрице сравнений, что обеспечивает на нечетных шагах сдвиг текста влево на вычисляемое количество символов.

2. Ассоциативное матричное устройство параллельного поиска образца по его префиксам, содержащее одну – базовую ассоциативную запоминающую матрицу маскированного поиска вхождений в составе n×m ассоциативных запоминающих элементов, первые входы которых в соответствующих строках матрицы объединены и являются соответствующими внешними адресными входами, четвертые входы ассоциативных запоминающих элементов подключены к внешнему входу синхронизации «CLOCK», пятые входы ассоциативных запоминающих элементов соединены с соответствующими внешними входами маскирования разрядных срезов – столбцов матрицы, первые выходы ассоциативных запоминающих элементов в соответствующих столбцах матрицы объединены и образуют m-разрядный информационный выход, n×m коммутационных элементов, входы которых подключены ко вторым выходам соответствующих ассоциативных запоминающих элементов, а выходы коммутационных элементов соответственно объединены и являются, соответствующими выходами опроса, кроме n-й строки матрицы, n×m элементов-селекторов, первые и вторые входы которых являются соответственно первыми и вторыми информационными входами матрицы в соответствующих столбцах, третьи входы элементов-селекторов подключены к первым выходам ассоциативных запоминающих элементов соответствующей строки матрицы, при этом третьи входы элементов-селекторов крайнего правого столбца матрицы подключены к первым выходам соответствующих ассоциативных запоминающих элементов крайнего левого столбца матрицы, расположенных строкой ниже, четвертые входы элементов-селекторов подключены к внешнему входу «РЕЖИМ», первые и вторые выходы n×m элементов-селекторов являются соответственно вторыми и третьими информационными входами ассоциативных запоминающих элементов соответствующей строки матрицы, маскирующего элемента, первый вход которого подключен к внешнему входу синхронизации «CLOCK», второй вход – к внешнему входу «РЕЖИМ», третий вход – к внешнему входу «СБРОС», а выход является индикатором произошедших реконфигураций матрицы из двухмерного вида в одномерный и обратно, двухвходового элемента И, первый вход которого подключен к выходу опроса n-й строки матрицы, второй вход – к выходу маскирующего элемента, а выход двухвходового элемента И является маскируемым выходом опроса n-й строки матрицы, ограничительного резистора, соединенного с третьим входом nm-го элемента-селектора и источником питания, отличающееся тем, что в устройство введены m-1 аналогичных ассоциативных запоминающих матриц маскированного поиска вхождений, имеющих совпадающий состав элементов и связи между ними, введены блок обработки матрицы сравнений, блок вычисления сдвига, также введены управляющие однобитовые входы устройства «ЗАПИСЬ 1», «ЗАПИСЬ 2», «ЗАПИСЬ 3», внешний вход «m» устройства, задающий длину образца в символах, два информационных выхода устройства «ВХОЖД», «СДВИГ», при этом внешний однобитовый вход «РЕЖИМ» подключен к четверым входам n×m элементов-селекторов и ко второму входу маскирующего элемента каждой из введенных m-1 матриц, внешний однобитовый вход «CLOCK» подключен к четверым входам n×m ассоциативных запоминающих элементов и к первому входу маскирующего элемента каждой из введенных m-1 матриц, внешний однобитовый вход «СБРОС» подключен к третьему входу маскирующего элемента, входящего в состав каждой из введенных m-1 матриц, i-й внешний адресный вход i=1-n подключен к первым входам ассоциативных запоминающих элементов в i-х строках каждой из введенных m-1 матриц, jw-е внешние входы маскирования столбцов подключены к пятым входам ассоциативных запоминающих элементов j-х столбцов каждой из m-1 введенных матриц j=1-m, w=1 - m–1, первые и вторые информационные входы разрядностью по m бит каждый вход в соответствующих столбцах подключены к первым и вторым входам n×m элементов-селекторов каждой из m-1 введенных матриц, первые m-разрядные выходы, образуемые выходами ассоциативными запоминающих элементов в соответствующих столбцах по каждой из введенных m-1 матриц, дополняются m-разрядным выходом, формируемым выходами ассоциативных запоминающих элементов в соответствующих столбцах базовой матрицы, совместно образуют m внешних информационных выходов устройства разрядностью по m бит каждый выход, вторые n-разрядные выходы, образуемые выходами коммутационных элементов в соответствующих строках по каждой из введенных m-1 матриц, дополняются n-разрядным выходом, формируемым коммутационными элементами в соответствующих строках базовой матрицы, совместно образуют m выходов опроса разрядностью по n бит каждый выход; блок обработки матрицы сравнений состоит из m регистров опроса с тремя входами, m многовходовых элементов ИЛИ на n разрядов каждый, арбитра, m-разрядного шифратора столбцов, мультиплексора, n-разрядного шифратора строк, первого выходного регистра для хранения номера столбца приоритетной логической «1» в матрице сравнений, второго выходного регистра для хранения номера строки приоритетной логической «1» в матрице сравнений, имеет m n-разрядных информационных входов, однобитовый вход «СБРОС» начальной установки, однобитовые входы записи данных «ЗАПИСЬ 1» и «ЗАПИСЬ 2», являющиеся внешними входами устройства, два выхода «Номер столбца k», «Номер строки d», которые задают позицию вхождения образца в матричном представлении текста, один однобитовый выход «ВХОЖД», являющийся внешним выходом устройства, при этом каждый из m информационных n-разрядных входов блока обработки матрицы сравнений соединен с соответствующим n-разрядным выходом опроса одной из m ассоциативных запоминающих матриц маскированного поиска вхождений, на первые входы двух выходных регистров, а также на первые входы m регистров опроса подан однобитовый вход «СБРОС» начальной установки, на вторые входы m регистров опроса подан однобитовый вход «ЗАПИСЬ 1», на вторые входы первого и второго выходных регистров подан однобитовый вход «ЗАПИСЬ 2», третий вход v-го регистра опроса соединен с v-м n-разрядными выходом опроса (11₁-11_n)^v v-й ассоциативной запоминающей матрицы маскированного поиска вхождений v=1-m, выходы m регистров опроса соединены со входами соответствующих многовходовых элементов ИЛИ на n разрядов каждый, а также поданы на m информационных входов мультиплексора, выходы многовходовых элементов ИЛИ поданы на m входов арбитра, выход первого многовходового элемента ИЛИ является третьим выходом «ВХОЖД» блока обработки матрицы сравнений и внешним выходом устройства, m-разрядный выход арбитра подан на вход m-разрядного шифратора столбцов, выход которого подключен к информационному входу первого выходного регистра, выход которого подключен к адресному входу мультиплексора и является первым выходом «Номер столбца k» блока обработки матрицы сравнений, n-разрядный выход мультиплексора подан на вход n-разрядного шифратора строк, выход которого подключен к информационному входу второго выходного регистра, выход которого является вторым выходом «Номер строки d» блока обработки матрицы сравнений; блок вычисления сдвига состоит из двух вычитателей, умножителя, сумматора и выходного регистра на три входа, данный блок имеет три информационных входа, два управляющих однобитовых входа «ЗАПИСЬ 3», «СБРОС» и один информационный выход «СДВИГ», при этом первые входы первого и второго вычитателей подключены соответственно к первому и второму выходам «Номер столбца k» и «Номер строки d» блока обработки матрицы сравнений, на вторые входы первого и второго вычитателей подано значение 1, выход второго вычитателя соединен со вторым входом умножителя, первый вход которого соединен с внешним входом устройства – длина образца «m», выход умножителя соединен со вторым входом сумматора, первый вход которого соединен с выходом первого вычитателя, выход сумматора подан на третий – информационный вход выходного регистра, на первый вход которого подан однобитовый вход «СБРОС» начальной установки, однобитовый управляющий вход «ЗАПИСЬ 3» подан на второй вход выходного регистра, выход которого является внешним выходом «СДВИГ» устройства; арбитр, имеющий m однобитовых входов и m однобитовых выходов и состоящий из m-1 элементов И c z входами каждый z=2-m, из z входов первый вход прямой, а остальные – инверсные, при этом z-й вход арбитра соединен с первым входом каждого z-го элемента И z=2-m, выход z-го элемента И является z-м выходом арбитра, и соединен с каждым v-м входом каждого из z+1 элементов И v=2 – m-1, кроме z=m, выход m-го элемента И является m-м выходом арбитра, первый вход арбитра является его первым выходом и соединен с z-м входом каждого z элемента И z=2-m.