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

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

Иллюстрации

Показать все

Реферат

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

Известен способ (патент №2469425, МПК G11C 15/00, «Ассоциативная запоминающая матрица маскированного поиска вхождений», опубликован 10.12.2012), заключающийся в циклической реконфигурации исходной структуры данных из одномерного в двумерный вид, а также маскировании незначимых позиций (разрядов) образца и установлении тем самым отношений следования между элементами структуры данных, что позволяет совмещать последовательные и параллельные процессы над всеми элементами структуры данных. Недостатками данного подхода является ограниченность реализации операции модификации строки ввиду отсутствия возможности локальной вставки элементов строки-модификатора в обрабатываемую строку или локального удаления элементов обрабатываемой строки.

Наиболее близким к предлагаемому способу является способ параллельного поиска и замены строки на основе однородной запоминающей матрицы, отличающийся аппаратной реализацией шагов параллельного сравнения двух строк и сдвига влево, необходимых для операции поиска по образцу, и аппаратной реализацией шагов замещения, вставки элементов строки-модификатора и удаления элементов из обрабатываемой строки, необходимых для операции замены строк (заявка №2012113755 «Способ параллельного поиска и замены строки и однородная запоминающая матрица для его реализации», дата опубликования 20.10.2013). При этом обрабатываемая строка для операции поиска по образцу представляется в виде ассоциативной матрицы, хранящей исходные данные и позволяющей совмещать шаги параллельного сравнения по всем строкам матрицы. Операция замены строки связана с выполнением последовательности 4 аппаратных шагов в исходной строке, циклически реконфигурируемой из одномерного в двумерный вид и обратно. Первый шаг связан с замещением элементов выбранной строки матрицы на фрагмент строки-модификатора. Второй шаг связан с освобождением данной строки матрицы путем реконфигурации части матрицы в одномерный вид и выполнении сдвигов над данной частью матрицы. Третий шаг - вставка следующего фрагмента строки-модификатора. Четвертый шаг связан с получением корректного результата путем реконфигурации остальной части матрицы в одномерный вид и выполнении сдвигов над данной частью. Особенностью данного способа является выделение соответствующих частей матрицы путем динамического формирования масок строк. Вместе с тем недостатками данного способа является ограниченность обработки символьной информации только на основе аппаратных шагов сдвига влево строки, что не позволяет вести двунаправленное перемещение элементов обрабатываемой строки в процессе обработки строковых данных.

Известно устройство поиска и замены произвольных вхождений в словах текста, содержащее блок памяти слов и подстановок, блок памяти вхождений, компаратор, блок хранения адреса вхождений, блок управления (патент № RU 2250493 С2, МПК G06F 17/30, опубликован 2005.04.20). Недостатком этого устройства является последовательное сравнение анализируемых символов и последовательная замена символов подстановки с помощью реверсивных регистров сдвига, что приводит к непродуктивным затратам времени на реализацию операций поиска и замены.

Известна ассоциативная запоминающая матрица (патент №2469425, МПК G11C 15/00, «Ассоциативная запоминающая матрица маскированного поиска вхождений», опубликован 10.12.2012), состоящая из n×m ассоциативных запоминающих элементов, n×m коммутационных элементов, представляющих собой 1-n-полюсники, n×m элементов-селекторов, маскирующего элемента, элемента И. При проведении ассоциативного маскированного поиска обеспечивается реконфигурация ассоциативной запоминающей матрицы за счет динамического перестроения соединений ассоциативных запоминающих элементов матрицы по направлению к первому элементу и реализация операции маскированного поиска всех вхождений образца в обрабатываемую строку. Недостатком этого устройства является невозможность динамического выделения рабочей части матрицы для аппаратного замещения, вставки или удаления символов, что необходимо для операции замены строки.

Наиболее близким устройством к заявленному является однородная запоминающая матрица для параллельного поиска и замены строки (патент №2509383, МПК G11C 15/00 «Способ параллельного поиска и замены строки и однородная запоминающая матрица для его реализации», опубликован 10.03.2014), которая содержит ассоциативные запоминающие элементы, коммутационные элементы, элементы-селекторы, маскирующий элемент, элемент И, ограничительный резистор, преобразователь кода. Управление соединениями ассоциативных запоминающих элементов осуществляется как на основе преобразования из одномерного представления строки в двумерное представление, так и на основе динамического выделения маской рабочей части матрицы, что позволяет выполнять локальные замещения, вставки и удаления элементов строки матрицы при выполнении замены строки. Недостатком данного устройства является односторонний характер соединений ассоциативных запоминающих элементов к первому элементу в матрице в процессе реализации аппаратных шагов операции замены (модификации строки), что определяет однонаправленный характер обработки исходной строки при ее двумерном и одномерном представлении.

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

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

Технический результат состоит в том, что разработаны способ и многофункциональное ассоциативное матричное устройство для параллельной обработки строк и решения задач распознавания образов (далее - способ и устройство). Заявленный способ включает последовательность четырех аппаратных шагов: шаг 1 - символы обрабатываемой строки замещаются первой подстрокой модификатора при двумерном представлении обрабатываемой строки, шаг 2 - выполняется параллельный межстрочный сдвиг влево символов обрабатываемой строки при ее двумерном представлении, шаг 3 - вторая подстрока модификатора вставляется в строку матрицы, шаг 4 - удаляются незначащие символы обрабатываемой строки при ее одномерном представлении в выделенной маской ее части с помощью последовательного сдвига вправо, при этом маска формируется динамически для выделения рабочей части обрабатываемой строки на четвертом шаге. Заявленное устройство содержит матрицу n×m ассоциативных запоминающих элементов, имеющих по четыре входа и два выхода каждый элемент, четвертые входы ассоциативных запоминающих элементов подключены к внешнему входу синхронизации "CLOCK", третьи входы ассоциативных запоминающих элементов подключены к внешнему входу начального сброса устройства, вторые входы ассоциативных запоминающих элементов подключены к выходам соответствующих по столбцу элементов-селекторов, первые входы ассоциативных запоминающих элементов подключены к адресным входам в соответствующей строке матрицы, первые выходы ассоциативных запоминающих элементов первой строки матрицы являются информационными выходами устройства, вторые выходы ассоциативных запоминающих элементов являются входами всех многовходовых элементов И, которые расположены в соответствующих строках матрицы, причем многовходовые элементы И, расположенные с первой по n-1 строки матрицы имеют по m входов каждый, а многовходовой элемент И в последней строке

матрицы имеет m+1 вход, первые m входов многовходовых элементов И подключены ко вторым выходам m ассоциативных запоминающих элементов соответствующей строки матрицы, m+1-ый вход многовходового элемента И в последней строке матрицы подключен к выходу маскирующего элемента, а выходы многовходовых элементов И являются соответствующими выходами результата поиска по образцу, n×m элементов-селекторов, имеющих по шесть входов и одному выходу каждый элемент-селектор, первые входы которых являются соответственно первыми информационными входами ассоциативного матричного устройства в соответствующих столбцах, вторые входы элементов-селекторов, кроме элементов-селекторов в последнем столбце матрицы, соединены с первыми выходами ассоциативных запоминающих элементов, которые расположены справа от соответствующих ассоциативных запоминающих элементов на одну позицию, вторые входы элементов-селекторов крайнего правого столбца матрицы, кроме самого последнего элемента-селектора в матрице, соединены с первыми выходами ассоциативных запоминающих элементов в крайнем левом столбце матрицы, расположенных строкой ниже, второй вход последнего элемента-селектора в матрице является внешним информационным входом устройства, третьи входы n×m элементов-селекторов подключены к внешнему входу «РЕЖИМ», четвертые входы элементов-селекторов подключены к внешнему входу "СДВИГ", пятые входы элементов-селекторов, кроме n-й строки матрицы, подключены в соответствующем столбце к первым выходам ассоциативных запоминающих элементов, расположенных строкой ниже в матрице, пятые входы элементов-селекторов n-й строки матрицы являются внешними входами устройства, шестые входы элементов-селекторов, кроме элементов-селекторов в первом столбце матрицы, соединены с первыми выходами ассоциативных запоминающих элементов, которые расположены слева от соответствующих ассоциативных запоминающих элементов на одну позицию, шестые входы элементов-селекторов крайнего левого столбца матрицы, кроме самого первого элемента-селектора в матрице, соединены с первыми выходами ассоциативных запоминающих элементов в крайнем правом столбце матрицы, расположенных строкой выше, шестой вход первого элемента-селектора является внешним информационным входом устройства, выходы n×m элементов-селекторов подключены ко вторым входам ассоциативных запоминающих элементов в соответствующей позиции матрицы, маскирующий элемент, первый вход которого подключен к внешнему входу синхронизации "CLOCK", второй вход - к внешнему входу "РЕЖИМ", третий вход - к внешнему входу начального сброса устройства, а выход маскирующего элемента является m+1 входом многовходового элемента И в последней строке матрицы, преобразователь кода, имеющий первый однобитовый управляющий вход, второй однобитовый управляющий вход, третий информационный вход разрядностью n бит, информационный выход разрядностью n бит и состоящий из n ячеек, на первый вход преобразователя кода поступает внешний сигнал «СТАРТ 1», на второй вход преобразователя кода поступает внешний сигнал «СТАРТ 2», третьи входы являются внешними адресными входами матрицы, а выходы преобразователя кода являются внутренними адресными входами, каждый из которых подается на первые входы ассоциативных запоминающих элементов в соответствующей строке матрицы, каждая ячейка преобразователя кода, кроме 1-й и n-й ячеек, имеет три однобитовых входа и три однобитовых выхода, первый вход i-й ячейки соединен с первым выходом i-1-й ячейки (i=2÷n), а на первый вход 1-й ячейки подается внешний сигнал «СТАРТ 1», второй вход j-й ячейки соединен с вторым выходом j+1-й ячейки (j=1÷n-1), а на второй вход n-й ячейки подается внешний сигнал «СТАРТ 2», информационные входы преобразователя кода являются третьими входами n ячеек, информационные выходы преобразователя кода являются третьими выходами n ячеек.

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

Устройство содержит следующие внешние входы и выходы: информационные входы 21₁-21_m для подачи m-разрядного поискового слова-образца или записываемого слова, информационные входы 22₁-22_m для записи m-разрядного слова в последнюю строку матрицы ассоциативных запоминающих элементов, информационные выходы 27₁-21_m для выдачи m-разрядного слова из первой строки матрицы ассоциативных запоминающих элементов, информационный вход 20 соединенный с шестым входом первого элемента-селектора матрицы, информационный выход 25 являющийся первым выходом первого ассоциативного запоминающего элемента матрицы, информационный вход 24, который является вторым входом последнего элемента-селектора матрицы, вход 9 начального сброса устройства, выходы 11₁-11_n результата поиска по образцу, внешние адресные входы 46₁-46_m, внутренние адресные входы 8₁÷8_n, управляющие однобитовые входы: синхронизации «CLOCK», управления сдвигом «СДВИГ», управления реконфигурацией «РЕЖИМ», однобитовые сигналы «СТАРТ 1», «СТАРТ 2» для формирования маски.

Под обработкой строк (строковых данных) понимаются аппаратно-выполняемые операции:

- поиск строки-образца;

- замена строк;

- последовательный сдвиг вправо.

Пусть в рабочем алфавите А={0,1} заданы объекты:

- строка-образец О длиной m символов, где О∈А^*, O=o₁o₂…o_m;

- строка-модификатор P длиной r символов, где P∈А^*, P=p₁p₂…p_r, 0<r≤2m;

- обрабатываемая строка S длиной k символов, где S∈A^*, S=S_1s2…S_k, (k≤n·m), n - натуральное число.

Все последующие формализации соответствуют прототипу

Требуется найти первое вхождение О в S, т.е. определить такую позицию p, при которых справедливо выражение

∃i∀j|[S(i)=O(j)],

где i=p…p+m-1, j=1…m, «=» - равенство i-ого и j-ого символов.

С найденной позиции p требуется выполнить осуществить замену строки О на строку P, т.е. разработать такой алгоритм, что справедливо ∃i((O(1,m)=S(i,i+m-1))|(S=s₁s₂…s_i-1p₁p₂…p_rs_i+m…s_k), 1≤ i ≤w, w=k-m+1,

где k>0, m>0, w>0.

При реализации операции замены наиболее общий случай соответствует соотношению длин образца О и модификатора P:m<r, который далее будет рассматриваться.

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

Параллельная обработка строк (строковых данных) осуществляется при представлении исходной битовой строки S длиной до k=n×m разрядов в виде двухмерной матрицы из n строк по m разрядов в каждой строке, где m соответствует разрядности битового образца О. На фиг. 1 представлено пошаговое выполнение операции замены для случая m<r при S=1101100111100110, O=1001 и P=1100010 в найденной позиции вхождения, соответствующей 2-й строке в матрице S. Модификатор P представляется в виде двух подстрок P₁, P₂ по m символов каждый. При этом выравнивание символов в P₂ выполняется по левому краю, а не заполненные разряды P₂ дополняются 0 (на фиг. 1 такие разряды для наглядности отмечены символом «x»).

Параллельная замена строки на матрице реализуется следующим образом. Битовая подстрока P₁ длиной в m символов подается на информационные входы устройства и в параллельном коде замещает данные в i-й строке матрицы, где i - номер строки матрицы, найденной операцией поиска по образцу. Управление номером строки матрицы осуществляется на

основе внешней маски строк М₁ содержащей единственную логическую «1» в i-ой позиции (i=2 на фиг. 1а). После замещения первой подстроки P₁ выполняется загрузка нового значения маски M₁ (фиг. 1б), которая своими логическими «1» выделяет «верхнюю» часть матрицы. На основе установленного значения маски M₁ с подачей одного тактового импульса по внешнему входу синхронизации выполняется параллельный межстрочный сдвиг влево на m бит над элементами строки S только в выделенной части матрицы (фиг. 1в). Процесс параллельного сдвига, отраженные на фиг. 1в, приводит к освобождению i-ой строки матрицы для дальнейших преобразований, а выдвигаемые первые m символов строки S поступают на информационный выход устройства.

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

Заключительный шаг операции замены заключается в удалении незначащих символов подстроки P₂ (они обозначены символом «x»). На заключительном этапе на основе ранее установленного значения маски М₁ с подачей 2m-r тактовых импульсов выполняется сдвиг вправо на 2m-r бит над элементами строки S только в выделенной части матрицы (фиг. 1е). Процессы, отраженные на фиг. 1е, приводят к удалению 2m-r незначащих разрядов из i-ой строки матрицы и формированию корректного результата.

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

Многофункциональное ассоциативное матричное устройство (фиг. 2) состоит из n×m ассоциативных запоминающих элементов 1, (n - количество строк матрицы, необходимых для представления входной битовой строки, m - количество разрядов образца) с входами с первого 2 по четвертый 5 и с выходами с первого 6 по второй 7, четвертые входы 5 ассоциативных запоминающих элементов 1 подключены к внешнему входу синхронизации "CLOCK", третьи входы 4 ассоциативных запоминающих элементов 1 подключены к внешнему входу 9 начального сброса устройства, вторые входы 3 ассоциативных запоминающих элементов 1 подключены к выходам 19 соответствующих по столбцу элементов-селекторов 12, первые входы 2 ассоциативных запоминающих элементов 1 подключены к адресным входам 8₁-8_n в соответствующей строке матрицы, первые выходы 6 ассоциативных запоминающих элементов 1 в первой строке матрицы являются информационными выходами матрицы 27₁-27_m, вторые выходы 7 ассоциативных запоминающих элементов 1 являются входами всех

многовходовых элементов 10, n многовходовых элементов 10 для выполнения операции логического умножения расположены в соответствующих n строках матрицы, причем многовходовые элементы 10, расположенные с первой по n-1 строки матрицы имеют по m входов каждый, а многовходовой элемент 10 в последней строке матрицы имеет m+1 вход, первые m входов многовходовых элементов 10 подключены ко вторым выходам m ассоциативных запоминающих элементов соответствующей строки матрицы, m+1-ый вход многовходового элемента 10 в последней строке матрицы подключен к выходу маскирующего элемента 36, а выходы многовходовых элементов 10 являются выходами 11 устройства, n×m элементов-селекторов 12, первые входы 13 в соответствующих столбцах матрицы являются соответственно первыми информационными входами 21₁-21_m устройства, вторые входы 14 элементов-селекторов 12, кроме n-го столбца в матрице, соединены с первыми выходами 6 ассоциативных запоминающих элементов 1, которые расположены справа от соответствующих ассоциативных запоминающих элементов на одну позицию, вторые входы 14 элементов-селекторов 12 n-го столбца матрицы, кроме самого последнего элемента-селектора 12_nm в матрице, соединены с первыми выходами 6 соответствующих ассоциативных запоминающих элементов 1 крайнего левого столбца матрицы, расположенных строкой ниже, второй вход последнего элемента-селектора 12_nm является внешним входом 24 устройства, третьи входы 15 всех элементов-селекторов 12 подключены к внешнему входу "РЕЖИМ", четвертые входы 16 всех элементов-селекторов 12 подключены к внешнему входу "СДВИГ", пятые входы 17 элементов-селекторов 12, кроме n-й строки матрицы, подключены в соответствующем столбце к первым выходам 6 ассоциативных запоминающих элементов 1, расположенных строкой ниже в матрице, пятые входы 17 элементов-селекторов 12 n-й строки матрицы являются внешним входами 22₁-22_m устройства, шестые входы 18 элементов-селекторов 12, кроме первого столбца в матрице, соединены с первыми выходами 6 ассоциативных запоминающих элементов 1, которые расположены слева от соответствующих ассоциативных запоминающих элементов на одну позицию, шестые входы 18 элементов-селекторов 12 первого столбца, кроме первого элемента-селектора 12₁₁ в матрице, соединены с первыми выходами ассоциативных запоминающих элементов 1 в крайнем правом столбце матрицы строкой выше, шестой вход 18 первого элемента-селектора 12₁₁ является внешним информационным входом 20 устройства, выходы 19 всех элементов-селекторов 12 подключены к вторым входам 3 ассоциативных запоминающих элементов 1 в соответствующей позиции матрицы, маскирующий элемент 36, первый вход 37 которого подключен к внешнему входу синхронизации "CLOCK", второй вход 38 - к внешнему входу «РЕЖИМ», третий вход 39 - к внешнему входу 9 начального сброса устройства, а выход 40 является m+1-ым входом многовходового элемента 10 в последней строке матрицы, преобразователь кода 45, состоящий

из ячеек 53₁÷53_n, каждая ячейка 53₂÷53_n-1 имеет первый 47, второй 50 и третий 49 входы, а также первый 51, второй 48 и третий 52 выходы, ячейка 53₁ имеет такие же входы и выходы, как и выше обозначенные ячейки 53₂÷53_n-1 кроме второго выхода 48, ячейка 53_n имеет такие же входы и выходы, как и выше обозначенные ячейки 53₂÷53_n-1, кроме первого выхода 51, матрица имеет внешние адресные входы 46₁÷46_n, внутренние адресные входы 8₁÷8_n, первый информационный вход 20, внешний вход "РЕЖИМ", определяющий двумерный или одномерный вид структуры матрицы, внешний вход синхронизации «CLOCK», внешний вход 9 начального сброса устройства,, выходы 11₁÷11_n результатов опроса, выход 25 устройства, внешний управляющий вход «СТАРТ 1», который соединен с первым входом 47 ячейки 53₁, внешний управляющий вход «СТАРТ 2», который соединен со вторым входом 50 ячейки 53_n.

Ассоциативный запоминающий элемент (фиг. 3) 1 состоит из двухвходового элемента И 28, D-триггера 29, двухвходового элемента И-НЕ 30, двухвходового элемента И-НЕ 31. Первый вход элемента И 28 подключен к первому входу 2 ассоциативного запоминающего элемента 1, второй вход элемента И 28 подключен к четвертому входу 5 ассоциативного запоминающего элемента 1, а выход элемента И 28 подключен к входу синхронизации D-триггера, информационный вход которого подключен ко второму входу 3 ассоциативного запоминающего элемента 1, а третий вход 4 ассоциативного запоминающего элемента 1 подключен к асинхронному входу сброса D-триггера, прямой выход D-триггера подключен к двум входам элемента И-НЕ 30 и к первому входу элемента И-НЕ 31, на второй вход которого подан второй вход 3 ассоциативного запоминающего элемента 1, выход элемента И-НЕ 30 является первым выходом 6 ассоциативного запоминающего элемента 1, второй выход 7 которого является выходом элемента И-НЕ 31.

Элемент-селектор 12 (фиг. 4) состоит из мультиплексора 35, имеющего четыре однобитовых входа данных и два однобитовых адресных входа, 3 двухвходовых элемента И-НЕ 32, 33, 34. При этом адресные входы мультиплексора 35 подключены к третьему 15 и четвертому 16 входам элемента-селектора 12, т.е. к внешнему входу "РЕЖИМ" и внешнему входу "СДВИГ" соответственно. Первый вход данных мультиплексора 35 подключен к первому входу 13 элемента-селектора 12, второй вход данных мультиплексора 35 подключен к пятому входу 17 элемента-селектора 12 через инвертирующий элемент И-НЕ 32, третий вход данных мультиплексора 35 подключен к второму входу 14 элемента-селектора 12 через инвертирующий элемент И-НЕ 34, четвертый вход данных мультиплексора 35 подключен к шестому входу 18 элемента-селектора 12 через инвертирующий элемент И-НЕ 33, выход мультиплексора 35 является соответственно выходом 19 элемента-селектора 12.

Маскирующий элемент 36 (фиг. 5) строго соответствует устройству-прототипу в структурном и в функциональном отношении, состоит из двухвходового элемента И 41, двоичного счетчика 42 с разрядностью m, элемента ИЛИ-НЕ 43 с m-входами. Первый вход элемента И 41 подключен к первому входу 37 маскирующего элемента 36, второй вход элемента И 41 подключен ко второму входу 38 маскирующего элемента 36. Первый вход двоичного счетчика 42 подключен к выходу элемента И 41, второй вход двоичного счетчика 42 подключен к третьему входу 39 маскирующего элемента 36, а m-выходов счетчика подключены к m-входам элемента ИЛИ-НЕ 43. Выход элемента ИЛИ-НЕ 43 подключен к выходу 40 маскирующего элемента 36.

Преобразователь кода (фиг. 6) строго соответствует устройству-прототипу в структурном и в функциональном отношении, состоит из однородных ячеек 53₁÷53_n, каждая из которых состоит из двухвходовых элементов И 54, И 55 и трехвходового элемента ИЛИ 56. Первый вход элемента И 54 подключен ко второму внешнему входу 50 ячейки 53, второй вход элемента И 54 подключен к третьему внешнему входу 49 ячейки 53. Выход элемента И 54 является вторым внешним выходом 48 ячейки 53 и подключен к первому входу элемента ИЛИ 56. Первый вход элемента И 55 подключен к первому внешнему входу 47 ячейки 53, второй вход элемента И 55 подключен к третьему внешнему входу 49 ячейки 53. Выход элемента И 55 является первым внешним выходом 51 ячейки 53 и подключен к третьему входу элемента ИЛИ 56, а выход элемента ИЛИ 56 является третьим внешним выходом 52 ячейки 53. Второй вход элемента ИЛИ 56 подключен к третьему внешнему входу 49 ячейки 53. Для ячейки 53₁ на первый внешний вход 47 подается внешний сигнал «СТАРТ 1», а для ячейки 53_n на второй внешний вход 50 подается внешний сигнал «СТАРТ 2».

Сущность динамической реконфигурации для параллельной обработки строк, воплощенная на фиг. 2, сводится к подключению первых 13 или вторых 14, или пятых 17, или шестых 18 входов элементов-селекторов 12 к выходу 19 соответственно в зависимости от значений внешних входов «РЕЖИМ» и «СДВИГ». Если входы «РЕЖИМ»=0 и «СДВИГ»=0, то к выходу 19 подключается вход 13, т.е. обеспечивается ассоциативный поиск вхождений или запись в параллельном коде строки-модификатора на двумерном представлении S. Если входы «РЕЖИМ»=0 и «СДВИГ»=1, то к выходу 19 подключается вход 17, т.е. выполняется межстрочный сдвиг на двумерном представлении S (параллельный сдвиг влево). Если входы РЕЖИМ=1 и «СДВИГ»=0, то к выходу 19 подключается вход 14, т.е. выполняется последовательный сдвиг влево на одномерном представлении S. Если входы «РЕЖИМ»=1 и «СДВИГ»=1, то к выходу 19 подключается вход 18, т.е. выполняется последовательный сдвиг вправо на одномерном представлении S.

Элементы-селекторы 12 (фиг. 4) содержат мультиплексоры 35, которые обеспечивают ввод в ассоциативные запоминающие элементы 1 бит образца О (для ассоциативного поиска вхождений), бит модификатора P (для замещения/вставки в параллельном коде), бит от соседнего справа ассоциативного запоминающего элемента 1 (для последовательного сдвига влево) или бит от соседнего слева ассоциативного запоминающего элемента 1 (для последовательного сдвига вправо).

Многофункциональное ассоциативное матричное устройство для параллельной обработки строк и решения задач распознавания образов работает в одном из шести состояний: запись, чтение, ассоциативный поиск, реконфигурация в одномерный вид для последовательного сдвига вправо (реконфигурация 1), реконфигурация в одномерный вид для последовательного сдвига влево (реконфигурация 2), замена строки. При этом работа матрицы в любом из ее состояний начинается с подачи сигнала синхронизации «CLOCK»=1.

При записи битовых данных в матрицу на третьи входы 46₁÷46_n преобразователя кода 45 подается адрес строки, в которую необходимо произвести запись, при этом на внешние входы «СТАРТ 1» и «СТАРТ 2» преобразователя кода 45 подаются значения логического «0», что приводит к подключению третьих 46₁÷46_n входов преобразователя кода к внутренним адресным входам 8₁÷8_n матрицы, при этом только на одном адресном входе 8₁÷8_n матрицы устанавливается значение логической «1», которая соответствует адресу записываемой строки. Затем по заданному адресу строки матрицы на информационные входы 21 матрицы и, следовательно, на первые входы 13 всех элементов-селекторов 12 соответствующей строки матрицы поступает логическая «1» или логический «0». При этом на третьи и четвертые входы 15 и 16 всех элементов-селекторов 12 подаются сигналы «РЕЖИМ»=0 и «СДВИГ»=0, что осуществляет подключение первых 13 входов элементов-селекторов 12 к выходам 19 элементов-селекторов 12 и соответственно ко вторым информационным входам 3 ассоциативных запоминающих элементов 1 соответствующей строки матрицы. Затем на соответствующие четвертые входы 5 ассоциативных запоминающих элементов 1 соответствующей строки матрицы подается сигнал синхронизации «CLOCK»=1, инициируя тем самым запись фрагмента битовой строки в m разрядов по адресу строки матрицы, задаваемому по внешнему адресному входу 46₁÷46_n.

При считывании битовых данных из матрицы на третьи входы 46₁÷46_n преобразователя кода 45 подается адрес строки, из которой необходимо произвести чтение, при этом на внешние входы «СТАРТ 1» и «СТАРТ 2» преобразователя кода 45 подаются значения логического «1», что приводит к подключению третьих входов 46₁÷46_n преобразователя кода к внутренним адресным входам матрицы , которые разрешают выполнять параллельный сдвиг влево по всем строкам матрицы. Затем устанавливаются входы «РЕЖИМ»=0 и «СДВИГ»=1, что приводит к подключению выходов

19 элементов-селекторов 12 через входы 17 к первым выходам ассоциативных запоминающих элементов 1, расположенных строкой ниже в матрице, при этом входы 17 элементов-селекторов 12 последней строки матрицы подключены к внешним входам 22₁-22_m. С подачей n тактовых импульсов по внешнему входу синхронизации «CLOCK» осуществляется построчное считывание матрицы по внешнему выходу 27₁-27_m, начиная с первой строки матрицы.

Перед выполнением ассоциативного поиска на третий вход 39 маскирующего элемента 36 подается сигнал «СБРОС»=1, инициируя сброс двоичного счетчика 42 и получение на выходе 40 маскирующего элемента 36 значения логической «1». На внешние входы «СТАРТ 1» и «СТАРТ 2» преобразователя кода 45 подаются значения логической «1», что приводит к подключению третьих входов 46₁÷46_n преобразователя кода к внутренним адресным входам матрицы , которые разрешают вести поиск по всем строкам матрицы.

При осуществлении циклического ассоциативного поиска вхождений на информационные входы 21 устройства и, следовательно, на первые входы 13 всех элементов-селекторов 12 соответствующей строки матрицы поступает логическая «1» или логический «0». При этом на четвертый вход 16 соответствующих элементов-селекторов 12 подается сигнал «РЕЖИМ»=0, что осуществляет подключение первых входов 13 элементов-селекторов 12 к выходам 19 элементов-селекторов 12 и соответственно ко вторым входам 3 ассоциативных запоминающих элементов 1 соответствующей строки матрицы. Затем на соответствующие четвертые входы 5 ассоциативных запоминающих элементов 1 соответствующей строки матрицы подается сигнал синхронизации «CLOCK=1», инициируя сравнение с содержимым триггера 29 соответствующего ассоциативного запоминающего элемента 1 на двухвходовом элементе И-НЕ 31, первый вход которого подключен к выходу D-триггера 29, второй вход элемента И-НЕ 31 подключен к входу 3 ассоциативного запоминающего элемента 1. Если происходит совпадение, то выход элемента И-НЕ 31, являющийся вторым выходом 7 ассоциативного запоминающего элемента 1, сохраняет уровень логического «0» и, следовательно, на выходе(ах) 11 результатов опроса матрицы, к которому(ым) подключен выход 7 этого ассоциативного запоминающего элемента 1, сохраняется уровень логической «1». Если происходит несовпадение, то на выходе 7 такого ассоциативного запоминающего элемента 1 появляется уровень логической «1», устанавливающий в «0» этот (эти) выход(ы) 11. При этом если была произведена хотя бы одна операция реконфигурации матрицы, на выходе 11_n результатов опроса ассоциативных запоминающих элементов 1 n-ой строки матрицы получается значение логического «0» в результате установки на выходе маскирующего элемента 36 значения логического «0».

Перед выполнением «реконфигурации 1» и «реконфигурации 2» на внешние входы «СТАРТ 1» и «СТАРТ 2» преобразователя кода 45 подаются

значения логической «1», что приводит к подключению третьих входов 46₁÷46_n преобразователя кода к внутренним адресным входам , которые разрешают вести поиск по всем строкам матрицы.

При осуществлении состояния матрицы «реконфигурация 1» на шестые входы 18 всех элементов-селекторов 12, кроме первого столбца в матрице, подается сигнал с первых выходов 6 ассоциативных запоминающих элементов 1, расположенных слева от соответствующих ассоциативных запоминающих элементов на одну позицию, на шестые входы 18 элементов-селекторов 12 первого столбца, кроме первого элемента-селектора 12₁₁ в матрице, подается сигнал с первых выходов ассоциативных запоминающих элементов 1 в крайнем правом столбце матрицы строкой выше, на шестой вход 18 первого элемента-селектора 12₁₁ подается сигнал с внешнего информационного входа 20 устройства, на третьи входы 15 всех элементов-селекторов 12 соответствующей строки матрицы подается сигнал «РЕЖИМ»=1 и на четвертые входы 16 всех элементов-селекторов 12 соответствующей строки матрицы подается сигнал «СДВИГ»=1, что позволяет соединить шестые входы 18 элементов-селекторов 12 с первыми выходами 19 элементов-селекторов 12. Затем на соответствующие четвертые входы 5 ассоциативных запоминающих элементов 1 всех строк матрицы подается сигнал синхронизации «CLOCK»=1, инициируя запись новых логических уровней ассоциативных запоминающих элементов 1 из последующих по строке/столбцу матрицы ассоциативных запоминающих элементов 1 и инкремент двоичного счетчика 42 маскирующего элемента 36. Тем самым осуществляется переход матрицы из двухмерного вида в одномерный вид и сдвиг вправо элементов матрицы по направлению к последнему элементу.

При осуществлении состояния матрицы «реконфигурация 2» на вторые входы 14 всех элементов-селекторов 12, кроме n-го столбца в матрице, подается сигнал с первых выходов 6 ассоциативных запоминающих элементов 1, которые расположены справа от соответствующих ассоциативных запоминающих элементов на одну позицию, на вторые входы 14 элементов-селекторов 12 n-го столбца матрицы, кроме самого последнего элемента-селектора 12_nm в матрице, подается си