RU163442U1 - Устройство параллельного поиска составного образца - Google Patents

Abstract

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

Description

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

Известна параллельная система информационного поиска [Патент 2195015 РФ, МПК G06F 17/30. Параллельная система информационного поиска / В.М. Довгаль, С.С. Шевелев; заявитель и патентообладатель Курск, гос. техн. ун-т. - №2001120172/09: заявл. 18.07.2001; опубл. 20.12.2002, Бюлл. №12], содержащая блок памяти вхождений, блок памяти слов, блок управления, массив блоков определения вхождений, работающих одновременно и имеющих в своем составе, регистр сдвига для хранения текста и ассоциативную память для хранения подстроки образца. Работа системы заключается в параллельном сопоставлении в ассоциативной памяти подстроки образца и текста. В случае отсутствия вхождения осуществляется сдвиг текста на одну позицию и новая итерация поиска. Недостаток данной системы - невозможность учета структурных отношений упорядочения вхождений подстрок составного образца в анализируемом тексте.

Известно устройство для параллельного поиска и обработки данных [Патент 72771 Российская Федерация, МПК G06F 12/00. Устройство для параллельного поиска и обработки данных / Е.А. Титенко, Л.А. Лисицин, В.М. Довгаль; заявитель и патентообладатель Курск, гос. техн. ун-т. - №2007149075/22: заявл. 25.12.2007; опубл. 27.04.2008, Бюлл. №12.], состоящее из двух блоков хранения и сравнения ассоциативных признаков, блока памяти логических векторов, операционного блока и блока матричного поиска, выполняющее параллельную обработку совокупности характеристических векторов, объединенных в двумерную матрицу поиска. Недостатком данного устройства является ограниченная функциональность - устройство позволяет осуществлять только поиск вхождений образца, состоящего только из одной подстроки. Характеристическая матрица поиска имеет геометрическую форму параллелограмма, а связи между смежными элементами диагоналей имеют локальный характер, что не позволяет этому устройству решать задачу поиска составного образца в анализируемой последовательности.

Устройством-прототипом является Способ и устройство поиска составного образца в последовательности / А.Г. Курочкин [и др.]; заявитель и патентообладатель Юго-Зап. гос. ун-т. 15.07.2013 г. №201132666/08(048862)], состоящий из блока хранения и сравнения ассоциативных признаков, блока памяти логических векторов, операционного блока, блока поиска составного образца, содержащего, в том числе, характеристическую матрицу и последовательно вычисляющего стартовые значения ячеек характеристической матрицы в пределах строки через систему последовательно соединенных двухвходовых элементов ИЛИ.

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

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

В i-ой строке, кроме i=n, на первый вход двухвходового ИЛИ подается значение логического «0», а второй вход первого двухвходового элемента ИЛИ соединен с выходом первой поисковой ячейки i-ой строки. Выход первого двухвходового элемента ИЛИ соединен с первым входом второго двухвходового элемента ИЛИ и является первым выходом блока многовходовых элементов ИЛИ. Выход первого двухвходового элемента ИЛИ также соединен с 2-ым, 3-ым и т.д. k-1-ым входами третьего, четвертого и т.д. k-го элементов ИЛИ.

В i-ой строке, кроме i=n, z-ый вход z-го элемента ИЛИ (z=2-k), соединен с выходом z-ой поисковой ячейки i-ой строки. Выход r-го элемента ИЛИ соединен с первым входом r+1-го элемента ИЛИ и является r-ым выходом блока многовходовых элементов ИЛИ (r=2-k-1). Выход k-го элемента ИЛИ является k-ым выходом блока многовходовых элементов ИЛИ. Выход t-го элемента ИЛИ (t=2-k-2), соединен с t-ым, t+1-ым и т.д. k-2-ым входами t+2-го, t+3-го и т.д. k-го элементов ИЛИ.

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

Устройство параллельного поиска составного образца (фиг.1) содержит блоки 1₁ и 1₂ хранения и сравнения ассоциативных признаков, блок 2 памяти логических векторов, операционный блок 3, блок 4 параллельного поиска составного образца, информационные входы 4₁, 4₂, 4₃ и 4₄, информационные выходы 5₁-5₂, входы 6₁-6₆ задания режима работы, входы 7₁ и 7₂ начальной установки.

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

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

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

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

Характеристическая матрица поисковых ячеек 34₁₁-34_nm имеет геометрическую форму параллелограмма, в которой в каждой строке располагается k поисковых ячеек, сдвинутых относительно следующей строки ячеек вправо на 1 позицию, начиная с ячеек первой строки 34₁₁-34_1k. Такая форма матрицы обеспечивает направление поиска по диагоналям, проходящим через ячейки от первой строки к последней строке включительно. Также в каждую строку характеристической матрицы, кроме последней строки, входит блок 40 многовходовых элементов ИЛИ, имеющий k+1 вход и k выходов, состоящий из k элементов 41 ИЛИ: первого двухвходового элемента 41₁ ИЛИ, второго двухвходового элемента 41₂ ИЛИ, третьего трехвходового элемента 41₃ ИЛИ, z-го z-входового элемента 41_z ИЛИ и т.д. k-го k-входового элемента 41_k ИЛИ, обеспечивающих распараллеливание вычисления стартовых значений ячеек в пределах строки.

В i-ой строке, кроме i=n, на первый вход двухвходового 41₁ ИЛИ подается значение логического «0», а второй вход первого двухвходового элемента 41₁ ИЛИ соединен с выходом первой поисковой ячейки 34₁ i-ой строки. Выход первого двухвходового элемента 41₁ ИЛИ соединен с первым входом второго двухвходового элемента 41₂ ИЛИ и является первым выходом блока 40 многовходовых элементов ИЛИ. Выход первого двухвходового элемента 41₁ ИЛИ соединен с 2-ым, 3-ым и т.д. k-1-ым входами третьего, четвертого и т.д. k-го элементов 41 ИЛИ.

В i-ой строке, кроме i=n, z-ый вход z-го элемента 41_z ИЛИ (z=2-k), соединен с выходом z-ой поисковой ячейки 34_z i-ой строки. Выход r-го элемента 41_r ИЛИ соединен с первым входом r+1-го элемента 41_r+1 ИЛИ и является r-ым выходом блока 40 многовходовых элементов ИЛИ (r=2-k-1). Выход k-го элемента 41_k ИЛИ является k-ым выходом блока 40 многовходовых элементов ИЛИ. Выход t-го элемента 41_t ИЛИ (t=2-k-2), соединен с t-ым, t+1-ым и т.д. k-2-ым входами t+2-го, t+3-го и т.д. k-го элементов 41 ИЛИ.

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

Триггера 37₁-37_k позиций хранят результат поиска в виде k-разрядного кода, в котором значением логической «1» отмечены позиции начала вхождений составного образца в текст. Триггер 37_i позиции (i=1-k) содержит три входа (первый и второй управляющие, третий одноразрядный информационный вход) и один выход. Первый вход блока 4 параллельного поиска составного образца соединен соответственно с первыми входами k триггеров 37 позиций, вторые входы k триггеров 37 позиций соединены с выходом элемента 31 задержки. Выходы триггеров 37₁-37_k позиций образуют k-разрядный информационный выход блока 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, подается на третьи входы поисковых ячеек первой строки матрицы и определяет тем самым направление параллельного поиска по всем диагоналям характеристической матрицы от поисковых ячеек первой строки до поисковых ячеек последней строки включительно. Время вычисления стартовых точек сокращается до k/2τ_ИЛИ, где τ_ИЛИ - время задержки на элементе 41 ИЛИ. По завершении процессов поиска импульсный сигнал с выхода элемента 31 задержки через время Т′=m2τ_инв (2τ_инв - время задержки на цепочке инверторов) записывает k-битовый результат поиска составного образца в триггера 37₁-37_k позиций. Выходы триггеров 37₁-37_k позиций являются k-разрядным выходом блока 4 параллельного поиска составного образца и образуют второй выход устройства 5₂.

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

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

Claims (1)

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

   и (n-1) блоков многовходовых элементов ИЛИ для параллельного построчного вычисления стартовых значений,

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

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

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

   причем первый и второй p-разрядные входы поисковой ячейки соединены соответственно с первым и вторым p-разрядными входами двухвходовой схемы сравнения на равенство соответственно, выход которой является первым входом двухвходового элемента И, выход которого является выходом поисковой ячейки, второй вход двухвходового элемента И соединен с третьим входом поисковой ячейки, причем первые p-разрядные входы всех поисковых ячеек i-й строки матрицы, где i=1-n,

   соединены с p-разрядным выходом i-го регистра для хранения символа составного образца, p-разрядный выход j-го регистра для хранения кода символа текста, где j=1-m,

   соединен соответственно со вторыми p-разрядными входами всех поисковых ячеек, входящих в j-й столбец матрицы, выходы поисковых ячеек i-й строки, кроме i=n, последняя строка матрицы,

   соединены с z-ми входами, где z=2-k,

   блока многовходовых элементов ИЛИ, t-е выходы, где t=1-k,

   которого соединены с третьими входами поисковых ячеек (i+1)-й строки, кроме i=n,

   на первый вход блока многовходовых элементов ИЛИ в каждой строке матрицы, подается значение логического «0», выход поисковой ячейки, расположенной в последней строке матрицы, соединен с третьим входом j-го триггера позиции,

   на третий вход каждой поисковой ячейки, расположенной в первой строке матрицы, подано значение логической «1»,

   первый вход блока параллельного поиска составного образца соединен соответственно с первыми входами n регистров для хранения кодов символов составного образца, а также с первыми входами m регистров для хранения кодов символов текста и первыми входами k триггеров позиций,

   второй вход «Запись строк» блока параллельного поиска составного образца соединен со входом элемента задержки и со вторыми входами n регистров для хранения кодов символов составного образца и вторыми входами m регистров для хранения кодов символов текста соответственно,

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

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

   причем i-я группа разрядов, где i=1-n, подается на третий p-разрядный вход i-ого регистра для хранения кода символа составного образца,

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

   причем j-я группа разрядов, где j=1-m, подается на третий p-разрядный вход j-го регистра для хранения кода символов текста,

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

   выходы всех двухвходовых элементов суммы по модулю два с инверсией соединены с p-входовым элементом И, выход которого является одноразрядным выходом двухвходовой схемы сравнения на равенство,

   блок многовходовых элементов ИЛИ, имеющий k+1 вход и k выходов, состоящий из k элементов ИЛИ: первого двухвходового элемента ИЛИ, второго двухвходового элемента ИЛИ, третьего трехвходового элемента ИЛИ, z-го z-входового элемента ИЛИ, …, по k-й k-входового элемента ИЛИ,

   в i-й строке, кроме i=n, на первый вход двухвходового ИЛИ подается значение логического «0», а второй вход первого двухвходового элемента ИЛИ соединен с выходом первой поисковой ячейки i-й строки,

   выход первого двухвходового элемента ИЛИ соединен с первым входом второго двухвходового элемента ИЛИ и является первым выходом блока многовходовых элементов ИЛИ,

   выход первого двухвходового элемента ИЛИ также соединен с 2-м, 3-м,…, по k-1-й входами третьего, четвертого,…, по k-й элементов ИЛИ,

   в i-й строке, кроме i=n, z-й вход z-го элемента ИЛИ, где z=2-k, соединен с выходом z-й поисковой ячейки i-й строки,

   выход r-го элемента ИЛИ соединен с первым входом r+1-го элемента ИЛИ и является r-м выходом блока многовходовых элементов ИЛИ, где r=2-k-1,

   выход k-го элемента ИЛИ является k-м выходом блока многовходовых элементов ИЛИ,

   выход t-го элемента ИЛИ, где t=2-k-2, соединен с t-м, t+1-м,…, по k-2-м входами t+2-го, t+3-го,…, по k-й элементов ИЛИ.

   

Images