СПОСОБ И МНОГОФУНКЦИОНАЛЬНОЕ АССОЦИАТИВНОЕ МАТРИЧНОЕ УСТРОЙСТВО ДЛЯ ОБРАБОТКИ СТРОКОВЫХ ДАННЫХ И РЕШЕНИЯ ЗАДАЧ РАСПОЗНАВАНИЯ ОБРАЗОВ Российский патент 2016 года по МПК G11C15/04 G06F17/30 G06K9/62 

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

Известен способ (патент №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 в матрице, подается сигнал с первых выходов 6 соответствующих ассоциативных запоминающих элементов 1 крайнего левого столбца матрицы, расположенных строкой ниже, на второй вход 14 элемента-селектора 12_nm подается сигнал с внешнего входа 24 устройства, на третьи входы 15 всех элементов-селекторов 12 соответствующей строки матрицы подается сигнал «РЕЖИМ»=1 и на четвертые входы 16 всех элементов-селекторов 12 соответствующей строки матрицы подается сигнал «СДВИГ»=0, что позволяет соединить вторые входы 14 элементов-селекторов 12 с первыми выходами 19 элементов-селекторов 12. Затем на соответствующие четвертые входы 5 ассоциативных запоминающих элементов 1 всех строк матрицы подается сигнал синхронизации «CLOCK»=1,

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

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

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

Второй этап - параллельный межстрочный сдвиг влево в матрице над ее «верхней» частью - содержательно соответствует вышеописанному состоянию считывания битовых данных. Вместе с тем различие в задании значения по внутренним адресным входам 8₁÷8_n и использование двух управляющих сигналов «РЕЖИМ», «СДВИГ» для параллельного межстрочного сдвига влево в матрице определяют необходимость детально описать второй этап.

Перед выполнением этапа параллельного межстрочного сдвига влево в матрице преобразователь кода 45 получает следующие значения: на внешние входы 46₁÷46_n поступает код с единственной логической «1», соответствующей адресу изменяемой строки матрицы, входы «СТАРТ 1»=1 и «СТАРТ 2»=0, что приводит к формированию следующего значения на входах , где 1÷i - «верхняя» часть матрицы. Таким образом, на втором этапе выделяется только часть матрицы, над которой далее будет выполнен параллельный межстрочный сдвиг влево.

При осуществлении параллельного межстрочного сдвига влево над выделенной частью матрицы устанавливаются входы «РЕЖИМ»=0 и «СДВИГ»=1, что приводит к подключению выходов 19 элементов-селекторов 12 через входы 17 к первым выходам ассоциативных запоминающих элементов 1, расположенных строкой ниже в матрице, при этом входы 17 элементов-селекторов 12 последней строки матрицы подключены к внешним входам 22₁-22_m устройства. Затем на соответствующие четвертые входы 5 ассоциативных запоминающих элементов 1 всех строк матрицы с учетом сформированного значения на входах , где 1÷i - «верхняя» часть матрицы, один раз подается сигнал синхронизации "CLOCK"=1, инициируя

межстрочный сдвиг и выдачу первой строки матрицы на внешние выходы 27₁-27_m. Тем самым осуществляется освобождение строки матрицы для следующих этапов за один сигнал "CLOCK"=1.

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

Четвертый этап - 2m-r сдвигов вправо над «верхней» частью матрицы - содержательно соответствует вышеописанному состоянию «реконфигурации 1», выполняемому 2m-r раз. Вместе с тем различие в задании значения по внутренним адресным входам 8₁÷8_n определяют необходимость детально описать четвертый этап.

Перед выполнением операции «реконфигурации 1» устанавливаются входы «СТАРТ 1»=1 и «СТАРТ 2»=0, что приводит к формированию следующего значения на входах , где 1÷i - «верхняя» часть матрицы. Таким образом, на четвертом этапе выделяется только часть матрицы, над которой далее будет вышеописанное состояния матрицы «реконфигурация 1», т.е. выполняется 2m-r последовательных сдвигов вправо.

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

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

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

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

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

2. Многофункциональное ассоциативное матричное устройство для параллельной обработки строк и решения задач распознавания образов содержит n×m ассоциативных запоминающих элементов, имеющих по четыре входа и два выхода каждый элемент, четвертые входы ассоциативных запоминающих элементов подключены к внешнему входу синхронизации "CLOCK", третьи входы ассоциативных запоминающих элементов подключены к внешнему входу 9 начального сброса устройства, вторые входы ассоциативных запоминающих элементов подключены к выходам соответствующих по столбцу элементов-селекторов, первые входы ассоциативных запоминающих элементов подключены к адресным входам в соответствующей строке матрицы, первые выходы ассоциативных запоминающих элементов первой строки матрицы являются информационными выходами устройства, вторые выходы ассоциативных запоминающих устройств являются входами n многовходовых элементов И, которые расположены в соответствующих n строках матрицы, причем многовходовые элементы 10, расположенные с первой по n-1 строки матрицы, имеют по m входов каждый, а многовходовой элемент 10 в последней строке матрицы имеет m+1 вход, первые m входов многовходовых элементов 10 подключены ко вторым выходам m ассоциативных запоминающих элементов соответствующей строки матрицы, m+1-й вход многовходового элемента 10 в последней строке матрицы подключен к выходу маскирующего элемента 36, а выходы многовходовых элементов 10 являются выходами 11₁-11_n устройства, n×m элементов-селекторов, первые входы которых являются соответственно первыми информационными входами ассоциативного матричного устройства в соответствующих столбцах, вторые входы элементов-селекторов, кроме элементов-селекторов в последнем столбце матрицы, соединены с первыми выходами ассоциативных запоминающих элементов, которые расположены справа от соответствующих ассоциативных запоминающих элементов на одну позицию, вторые входы элементов-селекторов крайнего правого столбца матрицы, кроме самого последнего элемента-селектора в матрице, соединены с первыми выходами ассоциативных запоминающих элементов в крайнем левом столбце матрицы, расположенных строкой ниже, второй вход последнего элемента-селектора в матрице является внешним информационным входом устройства, третьи входы n×m элементов-селекторов подключены к внешнему входу "РЕЖИМ", четвертые входы элементов-селекторов подключены к внешнему входу "СДВИГ", пятые входы элементов-селекторов, кроме n-й строки матрицы, подключены в соответствующем столбце к первым выходам ассоциативных запоминающих элементов, расположенных строкой ниже в матрице, пятые входы элементов-селекторов n-й строки матрицы являются внешними входами устройства, шестые входы элементов-селекторов, кроме элементов-селекторов в первом столбце матрицы, соединены с первыми выходами ассоциативных запоминающих элементов, которые расположены слева от ассоциативных запоминающих элементов на одну позицию, шестые входы элементов-селекторов крайнего левого столбца матрицы, кроме самого первого элемента-селектора в матрице, соединены с первыми выходами ассоциативных запоминающих элементов в крайнем правом столбце матрицы, расположенных строкой выше, шестой вход первого элемента-селектора является внешним информационным входом устройства, выходы n×m элементов-селекторов являются вторыми входами ассоциативных запоминающих элементов соответствующей строки матрицы, маскирующий элемент, первый вход которого подключен к внешнему входу синхронизации "CLOCK", второй вход - к внешнему входу "РЕЖИМ", третий вход - к внешнему входу начального сброса устройства, а выход является дополнительным входом n-го многовходового устройства, преобразователь кода, имеющий первый однобитовый управляющий вход, второй однобитовый управляющий вход, третий информационный вход разрядностью 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», а для n-й ячейки преобразователя кода на ее второй вход подается внешний сигнал «СТАРТ 2».