ассоциативная запоминающая матрица маскированного поиска вхождений

Формула изобретения

Ассоциативная запоминающая матрица маскированного поиска вхождений, содержащая n×m ассоциативных запоминающих элементов, каждый из которых содержит RS-триггер, первый элемент И, элементы И-НЕ с первого по третий, элемент 2И-ИЛИ, при этом первый вход первого элемента И подключен к первому входу ассоциативного запоминающего элемента, второй вход первого элемента И подключен к четвертому входу ассоциативного запоминающего элемента, а выход первого элемента И подключен к первому входу третьего элемента И-НЕ, ко второму входу первого элемента И-НЕ, ко второму входу второго элемента И-НЕ, первый вход первого элемента И-НЕ подключен ко второму входу ассоциативного запоминающего элемента, а выход первого элемента И-НЕ подключен к входу S RS-триггера, первый вход второго элемента И-НЕ подключен к третьему входу ассоциативного запоминающего элемента, а выход второго элемента И-НЕ подключен к входу R RS-триггера, выход Q RS-триггера подключен ко второму входу третьего элемента И-НЕ, а также к первому входу элемента 2И-ИЛИ, выход RS-триггера подключен к третьему входу элемента 2И-ИЛИ, выход третьего элемента И-НЕ является первым выходом ассоциативного запоминающего элемента, второй вход элемента 2И-ИЛИ подключен ко второму входу ассоциативного запоминающего элемента, четвертый вход элемента 2И-ИЛИ подключен к третьему входу ассоциативного запоминающего элемента, первые входы ассоциативных запоминающих элементов в соответствующих строках матрицы объединены и являются соответствующими адресными входами матрицы, четвертые входы ассоциативных запоминающих элементов подключены к внешнему входу синхронизации "CLOCK", первые выходы ассоциативных запоминающих элементов в соответствующих столбцах матрицы объединены и являются соответствующими информационными выходами матрицы, коммутационные элементы, входы которых подключены ко вторым выходам соответствующих ассоциативных запоминающих элементов, а выходы коммутационных элементов соответственно объединены и являются соответствующими выходами результатов опроса, n×m элементов-селекторов, первые и вторые входы которых являются соответственно первыми и вторыми информационными входами матрицы в соответствующих столбцах, третьи входы элементов-селекторов подключены к первым выходам ассоциативных запоминающих элементов соответствующей строки матрицы, при этом третьи входы элементов-селекторов крайнего правого столбца матрицы подключены к первым выходам соответствующих ассоциативных запоминающих элементов крайнего левого столбца матрицы, расположенных строкой ниже, четвертые входы элементов-селекторов подключены к внешнему входу "РЕЖИМ", первые и вторые выходы n×m элементов-селекторов являются соответственно вторыми и третьими информационными входами ассоциативных запоминающих элементов соответствующей строки матрицы, маскирующий элемент, первый вход которого подключен к внешнему входу синхронизации "CLOCK", второй вход - к внешнему входу "РЕЖИМ", третий вход - к внешнему входу "СБРОС", а выход является индикатором произошедших реконфигураций матрицы из двухмерного вида в одномерный и обратно, элемент И, первый вход которого подключен к выходу результата опроса n-й строки матрицы, второй вход - к выходу маскирующего элемента, а выход элемента И является маскируемым выходом опроса n-й строки матрицы, ограничительный резистор, соединенный с третьим входом nm-го элемента-селектора и источником питания, отличающаяся тем, что в состав ассоциативной запоминающей матрицы маскированного поиска вхождений введены внешние информационные входы маскирования разрядных срезов (столбцов), а также в состав ассоциативных запоминающих элементов введены пятые входы, соединенные с внешними информационными входами маскирования разрядных срезов (столбцов) ассоциативной запоминающей матрицы маскированного поиска вхождений, в состав ассоциативного запоминающего элемента введен второй элемент И, первый вход которого подключен к выходу элемента 2И-ИЛИ, а второй вход второго элемента И подключен к пятому входу ассоциативного запоминающего элемента, выход второго элемента И является вторым выходом ассоциативного запоминающего элемента.

Описание изобретения к патенту

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

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

Известна ассоциативная запоминающая матрица, состоящая из n×m ассоциативных запоминающих элементов, содержащих n×m бит исходной битовой строки S, и коммутационных элементов, представляющих собой 1-n-полюсники [2]. Коммутационные элементы с помощью загружаемого в них настроечного кода, обеспечивают статическую настраиваемую реконфигурацию соединительных элементов перед поиском.

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

Наиболее близким устройством к заявленному является ассоциативная запоминающая матрица [3], состоящая из n×m ассоциативных запоминающих элементов, содержащих n×m бит исходной битовой строки S длиной v=n×m бит, коммутационных элементов, представляющих собой 1-n-полюсники, n×m элементов-селекторов, маскирующего элемента, элемента И. При проведении ассоциативного поиска обеспечивается гибкая реконфигурация ассоциативной запоминающей матрицы за счет динамического перестроения соединений ассоциативных запоминающих элементов матрицы по направлению к первому элементу и повышение быстродействия операции поиска всех начал вхождений битового образца в битовую строку за счет исключения операций повторной загрузки данных в ассоциативную матрицу.

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

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

Техническая задача решается тем, что в ассоциативную запоминающую матрицу маскированного поиска вхождений, содержащую n×m ассоциативных запоминающих элементов, первые входы которых в соответствующих строках матрицы объединены и являются соответствующими адресными входами матрицы, четвертые входы ассоциативных запоминающих элементов подключены к внешнему входу синхронизации "CLOCK", первые выходы ассоциативных запоминающих элементов в соответствующих столбцах матрицы объединены и являются соответствующими информационными выходами матрицы, коммутационные элементы, входы которых подключены ко вторым выходам соответствующих ассоциативных запоминающих элементов, а выходы коммутационных элементов соответственно объединены и являются соответствующими выходами результатов опроса, n×m элементов-селекторов, первые и вторые входы которых являются соответственно первыми и вторыми информационными входами матрицы в соответствующих столбцах, третьи входы элементов-селекторов подключены к первым выходам ассоциативных запоминающих элементов соответствующей строки матрицы, при этом третьи входы элементов-селекторов крайнего правого столбца матрицы подключены к первым выходам соответствующих ассоциативных запоминающих элементов крайнего левого столбца матрицы, расположенных строкой ниже, четвертые входы элементов-селекторов подключены к внешнему входу "РЕЖИМ", первые и вторые выходы n×m элементов-селекторов являются соответственно вторыми и третьими информационными входами ассоциативных запоминающих элементов соответствующей строки матрицы, маскирующий элемент, первый вход которого подключен к внешнему входу синхронизации "CLOCK", второй вход - к внешнему входу "РЕЖИМ", третий вход - к внешнему входу "СБРОС", а выход является индикатором произошедших реконфигураций матрицы из двухмерного вида в одномерный и обратно, элемент И, первый вход которого подключен к выходу результата опроса n-й строки матрицы, второй вход - к выходу маскирующего элемента, а выход является маскируемым выходом опроса n-й строки матрицы, ограничительный резистор, соединенный с третьим входом nm-го элемента-селектора и источником питания, дополнительно введены внешние информационные входы маскирования разрядных срезов (столбцов) ассоциативной запоминающей матрицы маскированного поиска вхождений, пятые входы ассоциативных запоминающих элементов, соединенные с соответствующими внешними информационными входами маскирования разрядных срезов (столбцов) ассоциативной запоминающей матрицы маскированного поиска вхождений, двухвходовой элемент И в состав каждого ассоциативного запоминающего элемента, первый вход двухвходового элемента И соединен с выходом элемента 2И-ИЛИ, второй вход двухвходового элемента И соединен с пятым входом ассоциативного запоминающего элемента, а выход двухвходового элемента И является вторым выходом ассоциативного запоминающего элемента.

Стандартные процессы поиска вхождений образца в обрабатываемой битовой строке адекватно описываются в терминах конструктивной логики над линейными конструктивными объектами, в которых каждый разряд является значимым при поиске. Вместе с тем учет отношений следования разрядов во всех позициях позволяет вести только точный поиск вхождений, что ограничивает применение данного подхода для обработки неточных исходных данных. С другой стороны, трактовка обрабатываемых объектов (образец, битовая строка) только как линейных (одномерных) конструкций приводит к непродуктивным затратам времени вследствие последовательного переборного сравнения всех разрядов обрабатываемой битовой строки, что в худшем случае приводит к v×m (v - длина обрабатываемой битовой строки, m - длина битового образца) сравнениям битов и цикличности операции поиска в целом, при этом в случае отрицательного результата сопоставления осуществляется возврат на первый бит образца О для сравнения с очередным битом строки S.

Задача маскированного поиска начал вхождений формулируется следующим образом. Пусть в двоичном алфавите ={0,1} заданы образец О и битовая строка S как последовательности бит длиной в m и v символов соответственно, при этом m<v. Пусть в двоичном алфавите ={0,1} задана маска М как последовательность бит длиной в m символов. Требуется найти все позиции начал вхождений О в S, т.е. определить все позиции р, при которых справедливо выражение , где i=p..p+m-1, j=1..m, «=» - равенство i-го и j-го бит.

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

Ассоциативный маскированный поиск всех начал вхождений обеспечивается путем представления исходной битовой строки S длиной до v=n×m разрядов в виде двухмерной матрицы из n строк по m разрядов в каждой строке, где m соответствует разрядности битового образца О. При таком представлении битовой строки S битовый образец О длиной в m разрядов и битовая маска М длиной в m разрядов подаются на информационные входы ассоциативной запоминающей матрицы и параллельно сравниваются по n строкам матрицы, что обеспечивает параллельный маскированный поиск всех вхождений.

Основу ассоциативного поиска всех вхождений составляет динамическая реконфигурация структуры битовой строки S: двумерная матрица одномерный сдвиговый регистр. Двумерный вид S необходим для организации параллельного поиска всех вхождений по разрядным срезам ассоциативной запоминающей матрицы. Одномерный вид S необходим для выполнения сдвига строки S и переходу к следующей итерации поиска вхождений.

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

Па фиг.1 демонстрируется точный поиск вхождений для S=1100101011001100, O=1001 и М=1111, где М - маска разрядных срезов (столбцов) ассоциативной запоминающей матрицы (значения логических «1» в позициях маски разрешают параллельное сравнение по разрядным срезам (столбцам) ассоциативной запоминающей матрицы. Ассоциативный поиск всех начал вхождений состоит из m-1-циклов, включающих параллельное сравнение с учетом маски и сдвиг битовой строки на 1 разряд в сторону начальной позиции. В текущем цикле процесса поиска после сравнения - положительного (фиг.1в) или отрицательного (фиг.1а, 1д, 1ж) - выполняется сдвиг битовой строки S на 1 разряд в сторону начальной позиции (фиг.1б, 1г, 1е) и осуществляется следующий цикл параллельного сравнения образца О по n строкам матрицы. В случае положительного сравнения фиксируется начальная позиция точных вхождений битового образца О в битовую строку S. При втором и последующих циклах параллельного сравнения результат опроса n-й строки матрицы не учитывается, т.к. последний фрагмент битовой строки S не совпадает (меньше) с разрядностью битового образца О. Для обнаружения всех начал вхождений битового образца О в исходную битовую строку S потребуется не более чем m-1 сдвигов.

На фиг.2 демонстрируется неточный поиск вхождений для S=1100101011001100, O=1001 и М=0101 (значения логических «0» в позициях маски запрещают параллельное сравнение по соответствующим разрядным срезам (столбцам) ассоциативной запоминающей матрицы). В текущем цикле поиска после сравнения - положительного (фиг.2в, 2д) или отрицательного (фиг.2а, 2ж) - выполняется сдвиг битовой строки S на 1 разряд в сторону начальной позиции (фиг.2б, 2г, 2е) и осуществляется следующий цикл параллельного сравнения образца О по n строкам матрицы. В случае положительного сравнения фиксируется начальная позиция неточных вхождений битового образца О в битовую строку S с учетом маски. При втором и последующих циклах параллельного сравнения результат опроса n-й строки матрицы не учитывается, т.к. последний фрагмент битовой строки S не совпадает (меньше) с разрядностью битового образца О. Для обнаружения всех начал вхождений битового образца О в исходную битовую строку S с учетом маски М потребуется не более чем m-1 сдвигов.

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

Матрица (фиг.3) состоит из n×m ассоциативных запоминающих элементов 1 (n - количество битовых строк, необходимых для представления входной битовой строки длиной v=n×m бит, m - количество разрядов битового образца) с входами с первого 2 по четвертый 5 и пятый вход 46 и с выходами с первого 6 по второй 7, коммутационных элементов 10, представляющих собой 1-n-полюсники, элементов-селекторов 12 с входами с первого 13 по четвертый 16 и с выходами с первого 17 по второй 18, маскирующего элемента 36 с входами с первого 37 по третий 39 и с выходом 40, элемента И 44, первый вход которого подключен к выходу результата опроса n-й строки матрицы, второй вход - к выходу 40 маскирующего элемента 36, а выход является маскируемым выходом опроса n-й строки матрицы 11_n, ограничительного резистора 27, соединенного с третьим входом 15 nm-го элемента-селектора 12 и источником питания, и имеет адресные входы 8₁÷8_n, первые 19 ₁÷19_m и вторые 20₁÷20 _m информационные входы, третьи 45₁÷45 _m информационные входы маскирования разрядных срезов (столбцов), внешний вход "РЕЖИМ", определяющий двумерный или одномерный вид структуры матрицы, внешний вход синхронизации "CLOCK", внешний вход "СБРОС", информационные выходы 9₁ ÷9_m, выходы 11₁÷11_n результатов опроса.

Ассоциативный запоминающий элемент 1 (фиг.4) состоит из RS-триггера 21 с инверсными входами установки в "1" и "0", элементов И с первого 22 по второй 47, элементов И-НЕ с первого 23 по третий 25, элемента 2И-ИЛИ 26. Первый вход элемента И 22 подключен к первому входу 2 ассоциативного запоминающего элемента 1, второй вход элемента И 22 подключен к четвертому входу 5 ассоциативного запоминающего элемента 1, а выход элемента И 22 подключен к первому входу элемента И-НЕ 25, ко второму входу элемента И-НЕ 23, ко второму входу элемента И-НЕ 24. Первый вход элемента И-НЕ 23 подключен ко второму входу 3 ассоциативного запоминающего элемента 1, а выход элемента И-НЕ 23 подключен к входу S RS-триггера 21. Первый вход элемента И-НЕ 24 подключен к третьему входу 4 ассоциативного запоминающего элемента 1, а выход элемента И-НЕ 24 подключен к входу R RS-триггера 21. Выход Q RS-триггера 21 подключен ко второму входу элемента И-НЕ 25, а также к первому входу элемента 2И-ИЛИ 26, выход RS-триггера 21 подключен к третьему входу элемента 2И-ИЛИ 26. Выход элемента И-НЕ 25 является первым выходом 6 ассоциативного запоминающего элемента 1. Второй вход элемента 2И-ИЛИ 26 подключен ко второму входу 3 ассоциативного запоминающего элемента 1, четвертый вход элемента 2И-ИЛИ 26 подключен к третьему входу 4 ассоциативного запоминающего элемента 1, выход элемента 2И-ИЛИ 26 подключен к первому входу элемента И 47. Второй вход элемента И 47 подключен к пятому входу 46 ассоциативного запоминающего элемента 1, а выход элемента И 47 является вторым выходом 7 ассоциативного запоминающего элемента 1.

Коммутационный элемент 10 (фиг.4) строго соответствует устройству-прототипу в структурном и в функциональном отношении, состоит из регистра 28 и n-элементов И-НЕ 32 и имеет n-входов данных 29 регистра 28, входы сигналов записи 30 и установки в начальное состояние 31 регистра 28, n-выходов полученного результата опроса ассоциативного запоминающего элемента 1. Первый вход каждого из n-элементов И-НЕ 32 подключен ко второму выходу 7 ассоциативного запоминающего элемента 1, а второй вход каждого из n-элементов И-НЕ 32 подключен к соответствующему выходу данных регистра 28, а выход каждого из n-элементов И-НЕ 32 является соответствующим выходом коммутационного элемента 10.

На фиг.4 также представлены ограничительные элементы 27 в виде резисторов, подключенных к n-выходам коммутационного элемента 10, к первому выходу 6 ассоциативного запоминающего элемента 1 и к источникам питания.

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

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

Сущность динамической реконфигурации, воплощенная на фиг.3, сводится к подключению первых 13 и вторых 14 входов или третьих входов 15 элементов-селекторов 12 к их выходам 17 и 18 соответственно в зависимости от значения внешнего входа РЕЖИМ. Если вход РЕЖИМ=0, то к выходам 17 и 18 подключаются входы 13 и 14 соответственно, т.е. обеспечивается ассоциативный поиск вхождений на двумерном представлении S. Если вход РЕЖИМ=1, то к выходам 17 и 18 подключаются вход 15, т.е. обеспечивается сдвиг на одномерном представлении S. Элементы-селекторы 12 (фиг.4) содержат два мультиплексора 33 и 34, которые обеспечивают ввод в ассоциативные запоминающие элементы 1 бит образца О (для ассоциативного поиска вхождений) или бит от соседнего справа ассоциативного запоминающего элемента (для сдвига).

Ассоциативная запоминающая матрица, как и устройство-прототип, работает в одном из четырех состояний: запись, чтение, ассоциативный маскированный поиск, реконфигурация - при этом работа ассоциативной запоминающей матрицы в любом из ее состояний начинается с подачи сигнала синхронизации "CLOCK"=1. Состояние записи, чтения и реконфигурации строго соответствует алгоритму, описанному в устройстве-прототипе.

Перед выполнением ассоциативного маскированного поиска выполняется настройка ассоциативной запоминающей матрицы, заключающаяся в предварительной записи в регистры 28 всех коммутационных элементов 10 настроечных кодов, обеспечивающих подключение вторых выходов 7 соответствующих ассоциативных запоминающих элементов 1 к соответствующим выходам 11 результатов опроса. В общем случае настроечный код может быть как униполярным, обеспечивающим подключение выхода 7 ассоциативного запоминающего элемента 1 к одному выбранному выходу 11 результатов опроса, так и k-полярным (k=1 n), где k - число выходов 11 результатов опроса матрицы, к которым подключается выход 7 ассоциативного запоминающего элемента 1. В рассматриваемой ассоциативной запоминающей матрице при маскированном поиске начал вхождений образца по строкам матрицы настроечный код коммутационных элементов 10 соответствующих строк матрицы имеет следующий вид: 29₁=100..0, 29₂=010..0, , 29_n=000..1, что позволяет получить инверсное значение выходов 7 соответствующих ассоциативных запоминающих элементов 1 на выходах 11 результатов опросов соответствующих строк матрицы.

Также перед выполнением ассоциативного маскированного поиска на третий вход 39 маскирующего элемента 36 подается сигнал "СБРОС"=1, инициируя сброс двоичного счетчика 42 и получение на выходе 40 маскирующего элемента 36 значения логической "1".

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

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

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

Источники информации

1. Максимов В. Алгоритмы поиска, или как искать неизвестно что [Текст] / В.Максимов // Журнал "Монитор". - М.: Изд.-во "Открытые системы", 1995. - № 6. С.10-15.

2. Пат. № 2025797 РФ, МПК G11C 15/00. Ассоциативная запоминающая матрица [Текст] / Борисов В.В.; заявитель и патентообладатель Борисов В.В.; заявл. 02.09.1992; опубл. 30.12.1994.

3. Пат. № 84615 РФ, МПК G11C 15/00. Ассоциативная запоминающая матрица [Текст] / Титенко Е.А., Евсюков В.С., Семенихин Е.А., Атакищев А.О.; заявитель и патентообладатель. Курск, гос. тех. ун-т. - № 2009104196/22; заявл. 09.02.2009; опубл. 10.07.2009, Бюл. № 19. - 14 с.: ил.