Матричное устройство параллельного поиска составного образца

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

 

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

Известно устройство для параллельного поиска и обработки данных [Патент 72771 Российская Федерация, МПК G06 F 12/00. опубл. 27.04.2008, Бюл. №12], состоящее из двух блоков хранения и сравнения ассоциативных признаков, блока памяти логических векторов, операционного блока и блока матричного поиска, выполняющее параллельную обработку совокупности характеристических векторов, объединенных в двумерную матрицу поиска. Недостатком данного устройства является ограниченная функциональность – устройство позволяет осуществлять только поиск вхождений образца, состоящего только из одной подстроки. Характеристическая матрица поиска имеет геометрическую форму параллелограмма, а связи между смежными элементами диагоналей имеют локальный характер, что не позволяет этому устройству решать задачу поиска составного образца в анализируемой последовательности.

Известны способ и устройство поиска составного образца в последовательности [Патент №2549525 РФ, МПК G06F 12/00, G06F 17/30. 013; опубл. 20.01.2015, Бюл. №12], состоящий из блока хранения и сравнения ассоциативных признаков, блока памяти логических векторов, операционного блока, блока поиска составного образца, содержащего в составе каждой строки характеристической матрицы поисковых ячеек последовательность двухвходовых элементов ИЛИ, позволяющих вычислять стартовые значения поисковых ячеек для поиска составного образца. Недостатком данного способа и устройства является последовательный характер вычисления стартовых значений, что приводит к непродуктивным затратам времени на поиск составного образца.

Устройством-прототипом является устройство параллельного поиска составного образца [Патент№ 163442 РФ, МПК G06 F 12/00, опубл. 20.07.2016 г., Бюл. №20], состоящий из блока хранения и сравнения ассоциативных признаков, блока памяти логических векторов, операционного блока, блока параллельного поиска составного образца, содержащего, в том числе, блок многовходовых элементов ИЛИ с избыточным количеством элементов и входов, что приводит к увеличению аппаратных затрат на вычисление стартовых значений ячеек строк матрицы.

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

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

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

Матричное устройство параллельного поиска составного образца (фиг. 1) содержит блоки 11 и 12 хранения и сравнения ассоциативных признаков, блок 2 памяти логических векторов, операционный блок 3, блок 4 параллельного поиска составного образца, информационные входы 41, 42, 43 и 44, информационные выходы 51, 52, входы 61–66 задания режима работы, входы 71 и 72 начальной установки.

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

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

Блок 4 параллельного поиска составного образца содержит элемент 31 задержки, состоящий из m пар инверторов, n регистров 321-32n для хранения кодов символов составного образца, m регистров 331-33m для хранения кодов символов текста, характеристической матрицы поисковых ячеек 3411-34nm, и n-1 блоков 40 многовходовых элементов ИЛИ с регулярной структурой, k триггеров 37 позиций, причем регистр 32i (i=1-n) и регистр 33j (j=1-m) содержат первый и второй управляющие входы, третий p-разрядный информационный вход и один выход соответственно. Первые и вторые входы n регистров 32 для хранения кодов символов составного образца и первые и вторые входы m регистров 33 для хранения кодов символов текста соединены соответственно с первым и вторым управляющими входами блока 4 параллельного поиска составного образца, вход 43 которого разрядностью p×n бит предназначен для параллельной записи составного образца в регистры 321-32n и состоит из n групп разрядов по p разрядов каждая группа, кодирующих символы составного образца, причем i-ая группа разрядов (i=1-n) подается на третий p-разрядный вход регистра 32i (i=1-n), вход 44 блока 4 параллельного поиска составного образца разрядностью p×m бит предназначен для параллельной записи текста в регистры 331-33m и состоит из m групп разрядов по p разрядов каждая группа, кодирующих символы текста, причем j-ая группа разрядов (j=1-m) подается на третий p-разрядный вход регистра 33j (j=1-m). Второй управляющий вход «Запись строк» блока 4 параллельного поиска составного образца также соединен со входом элемента 31 задержки, выход элемента 31 задержки соединен со вторыми входами триггеров 371-37k позиций, выходы которых образуют информационный k-разрядный выход 52 блока 4 параллельного поиска составного образца, выходы поисковых ячеек 34nn-34nm n-й строки характеристической матрицы соединены с третьими входами триггеров 371-37k позиций. Первый управляющий вход 71 блока 4 параллельного поиска составного образца также соединен с первыми входами триггеров 371-37k позиций.

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

Характеристическая матрица поисковых ячеек 3411-34nm имеет геометрическую форму параллелограмма, в которой в каждой строке располагается k поисковых ячеек, сдвинутых относительно следующей строки ячеек вправо на 1 позицию, начиная с ячеек первой строки 3411-341k. Такая форма матрицы обеспечивает направление поиска по диагоналям, проходящим через ячейки от первой строки к последней строке включительно. Также в каждую строку характеристической матрицы, кроме последней строки, входит блок 40 многовходовых элементов ИЛИ с регулярной структурой, имеющий k входов и k выходов, состоящий из k-1 элементов 41 ИЛИ: начального двухвходового элемента 412 ИЛИ, следующего трехвходового элемента 413 ИЛИ, четырехвходового элемента 414 ИЛИ и т.д. k-входового элемента 41k ИЛИ, обеспечивающих параллельное вычисление стартовых значений ячеек в пределах строки.

Z-й вход блока 40 многовходовых элементов ИЛИ с регулярной структурой, кроме z=2, соединен с первым входом соответствующего элемента 412– 41k ИЛИ (z=1-k), второй вход блока 40 многовходовых элементов ИЛИ с регулярной структурой соединен со вторым входом двухвходового элемента 412 ИЛИ, выход v-го элемента 41v ИЛИ является
v-ым выходом блока 40 многовходовых элементов ИЛИ с регулярной структурой и соединен с v+1 входом каждого из элементов 41v+1 – 41k-1 ИЛИ (v=2 – k-1), выход k-го элемента 41k ИЛИ является k-ым выходом блока 40 многовходовых элементов ИЛИ с регулярной структурой, первый вход блока 40 многовходовых элементов ИЛИ с регулярной структурой является его первым выходом и соединен с вторым входом каждого из элементов 413 – 41k ИЛИ.

K выходов поисковых ячеек i-ой строки характеристической матрицы поисковых ячеек, кроме i=n (последняя строка), соединены с соответствующими k входами i-го блока 40 многовходовых элементов ИЛИ с регулярной структурой, k выходов которого соединены с соответствующими третьими входами поисковых ячеек i+1-й строки характеристической матрицы поисковых ячеек.

На третьи входы поисковых ячеек 3411-341k, расположенных в первой строке характеристической матрицы поисковых ячеек, подано значение логической «1», выходы поисковых ячеек 34nn-34nm, расположенных в последней (n-й) строке характеристической матрицы поисковых ячеек, соединены с третьими входами триггеров 371-37k позиций.

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

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

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

Пусть устройство выполняет режим «Операция» с кодом операции «ПСО». На вход 71 «Начальная установка» операционного блока 3 и блока 4 параллельного поиска составного образца подается импульсный сигнал начальной установки, который сбрасывает в нулевое состояние регистр 22 команд по его входу 1, регистр 30 по его входу 1, а также k триггеров 37 позиций по их входу 1, n регистров 32 по их входу 1 и m регистров 33 по их входу 1. После окончания действия сигнала начальной установки на вход 66 режима работы операционного блока 3 подается код операции «ПСО», который обнаруживается дешифратором 23 команд и со второго выхода операционного блока 3 на второй вход «Запись строк» блока 4 параллельного поиска составного образца подается импульсный сигнал. Данный импульсный сигнал по входу «Запись строк» блока 4 параллельного поиска составного образца подается соответственно на вторые входы разрешения записи n регистров 32 для хранения кодов символов составного образца и на вторые входы разрешения записи m регистров 33 для хранения кодов символов текста, обеспечивая тем самым запись n символов составного образца и m символов текста в параллельном коде с входов 43 и 44 устройства. Также импульсный сигнал по входу «Запись строк» блока 4 параллельного поиска составного образца через элемент 31 задержки подается соответственно на вторые входы разрешения записи k триггеров 37 позиций. Элемент 31 задержки, выполненный в виде m пар инверторов, необходим для завершения процессов поиска составного образца по диагоналям характеристической матрицы, состоящей из поисковых ячеек 3411 – 34nm. Поиск начинается с ячеек первой строки характеристической матрицы. Начальный k-битовый характеристический вектор, равный 11…1, подается на третьи входы поисковых ячеек первой строки характеристической матрицы и определяет тем самым направление параллельного поиска по всем диагоналям характеристической матрицы от поисковых ячеек первой строки до поисковых ячеек последней строки включительно. Применение n-1 блоков 40 многовходовых элементов ИЛИ с регулярной структурой, имеющих k-1 элементов ИЛИ, сокращает время вычисления стартовых точек до (k-1)/2τИЛИ, где τИЛИ – время задержки на элементе 41 ИЛИ. По завершении процессов поиска импульсный сигнал с выхода элемента 31 задержки через время T=m2τинв (2τинв – время задержки на паре инверторов) записывает k-битовый результат поиска составного образца в триггера 371-37k позиций. Выходы триггеров 371-37k позиций являются k-разрядным выходом блока 4 параллельного поиска составного образца и образуют второй выход устройства 52.

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

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

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



 

Похожие патенты:

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

Изобретение относится к вычислительным системам на основе микропроцессоров с ассоциативным запоминающим устройством (АЗУ). Техническим результатом является уменьшение площади АЗУ и повышение его помехоустойчивости путем исключения сигналов, предназначенных только для управления предзарядом внутри регистра, и устройств, генерирующих эти сигналы.

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

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

Изобретение относится к архитектуре памяти и, более конкретно, к способам и системам для ассоциативной памяти (САМ). .

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

Изобретение относится к вычислительной технике и может быть использовано в матричных ассоциативных логических устройствах . .

Изобретение относится к области автоматики и вычислительной техники. .

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