Устройство для фильтрации информации

(51) МПК НАЦИОНАЛЬНЫЙ ЦЕНТР ИНТЕЛЛЕКТУАЛЬНОЙ СОБСТВЕННОСТИ УСТРОЙСТВО ДЛЯ ФИЛЬТРАЦИИ ИНФОРМАЦИИ(71) Заявитель Государственное научное учреждение Объединенный институт проблем информатики Национальной академии наук Беларуси(72) Авторы Прокопович Григорий Александрович Сычев Владислав Анатольевич(73) Патентообладатель Государственное научное учреждение Объединенный институт проблем информатики Национальной академии наук Беларуси(57) Устройство для фильтрации информации, содержащее блок сравнения, первый информационный вход которого является информационным входом устройства, второй вход блока сравнения соединен с первым выходом блока управления, а выход соединен с первым входом счетчика адреса и является также выходом признака сравнения устройства, второй вход счетчика адреса соединен со вторым выходом блока управления, а первый выход соединен с первым входом блока памяти, второй и третий входы которого соединены с третьим и четвертым выходами блока управления соответственно, выход блока памяти является информационным выходом устройства, второй выход счетчика адреса является выходом признака переполнения, а третий выход является выходом признака пустого накопителя,первый информационный вход блока управления является адресным входом устройства,отличающееся тем, что содержит блок признака, блок маски, блок дискретного нелинейного элемента, первый и второй элементы задержки, причем первый вход блока признака и вход первого элемента задержки являются информационными входами устройства, выход первого элемента задержки соединен с четвертым входом блока памяти, второй и третий входы блока признака соединены с пятым и шестым выходами блока управления соответственно, а выход соединен с первым входом блока маски, второй и третий входы которого соединены с седьмым и восьмым выходами блока управления соответственно, выход блока 90742013.04.30 маски соединен с первым входом блока дискретного нелинейного элемента, второй и третий входы которого соединены с девятым и десятым выходами блока управления соответственно, выход блока дискретного нелинейного элемента соединен со входом второго элемента задержки, выход которого соединен с третьим входом блока сравнения, второй и третий информационные входы блока управления являются соответственно входами управления данными и управления записью/считыванием устройства. Предлагаемое техническое решение относится к вычислительной технике и может быть использовано в специализированных системах фильтрации и поиска неслучайных комбинаций элементов в одномерном информационном массиве, который может содержать текстовые, графические, аудио- и другие данные. Известно устройство поиска информации детерминированных комбинаций в информационном массиве 1, содержащее формирователь сигналов текущей оценки, дискриминатор зон значений оценки, распределитель импульсов, счетчик временных интервалов,коммутатор, формирователи переменной поиска, суммирующие счетчики, блоки памяти,блок деления, классификатор, регистр стратегии поиска, формирователь сигналов сброса,блок индикации, блок изменения пороговых сигналов, таймер текущих суток, блок формирования порога усечения. Данное устройство основано на математическом методе половинного деления (дихотомии), эффективность которого зависит от общего количества блоков в массиве и числа искомых блоков. Недостатком данного устройства является рекурсивный принцип анализа секторов массива, что отрицательным образом влияет на скорость обработки информации. Известна ассоциативная запоминающая среда 2, используемая в устройствах обработки сигналов в реальном масштабе времени, характеризующихся различными топологическими особенностями логико-запоминающей среды, а также способами и формами представления информации. Недостатком подобных устройств является то, что ассоциативные ячейки, составляющие запоминающую среду, образуют точечную -мерную решетку, узлы которой расположены в вершинах многогранника Вороного. Поэтому при добавлении новой (либо удалении устаревшей) информации необходимо изменить (рассчитать заново) топологию запоминающей среды, влияющую на скорость и направление ассоциативного опроса ячеек памяти. Наиболее близким по технической сущности к предлагаемому техническому решению(прототипом) является устройство поиска информации по совпадению 3, предназначенное для быстрой фильтрации информации по совпадению и содержащее блок памяти,блок сравнения, регистр признака, регистр маски, счетчик адреса, блок управления. Однако предложенный прототип обладает рядом недостатков. Так, в частности, разрядность устройства, включающая разрядность входного слова и ячейки памяти, а также регистров маски и признака, строго фиксирована и должна совпадать, что ограничивает функциональность устройства и не позволяет производить поиск информации в случае,если длина искомого пакета превышает разрядность устройства. В случаях когда поисковый запрос содержит ошибки, устройство не сможет их исправить самостоятельно. Задачей предлагаемой полезной модели является повышение универсальности и эффективности работы устройства за счет записи и обработки искомой информации с помощью предельных циклов одно- или многомерных отображений специального вида. 2 90742013.04.30 Задача решается следующим образом. В устройство для фильтрации информации, содержащее блок сравнения, первый информационный вход которого является информационным входом устройства, второй вход блока сравнения соединен с первым выходом блока управления, а выход соединен с первым входом счетчика адреса и является также выходом признака сравнения устройства, второй вход счетчика адреса соединен со вторым выходом блока управления, а первый выход соединен с первым входом блока памяти,второй и третий входы которого соединены с третьим и четвертым выходами блока управления соответственно, выход блока памяти является информационным выходом устройства, второй выход счетчика адреса является выходом признака переполнения, а третий выход является выходом признака пустого накопителя, первый информационный вход блока управления является адресным входом устройства, дополнительно введены блок признака, блок маски, блок дискретного нелинейного элемента, первый и второй элементы задержки, причем первый вход блока признака и вход первого элемента задержки являются информационными входами устройства, выход первого элемента задержки соединен с четвертым входом блока памяти, второй и третий входы блока признака соединены с пятым и шестым выходами блока управления соответственно, а выход соединен с первым входом блока маски, второй и третий входы которого соединены с седьмым и восьмым выходами блока управления соответственно, выход блока маски соединен с первым входом блока дискретного нелинейного элемента, второй и третий входы которого соединены с девятым и десятым выходами блока управления соответственно, выход блока дискретного нелинейного элемента соединен со входом второго элемента задержки,выход которого соединен с третьим входом блока сравнения, второй и третий информационные входы блока управления являются соответственно входами управления данными и управления записью/считыванием устройства. Сущность устройства поясняется фигурами. На фиг. 1 представлена схема предлагаемого устройства. На фиг. 2 представлен пример переходной характеристики блока дискретного нелинейного элемента, кодирующего слово . Устройство для фильтрации информации содержит блок признака 1, блок сравнения 2,первый элемент задержки 3, блок памяти 4, блок управления 5, блок маски 6, блок дискретного нелинейного элемента 7, второй элемент задержки 8, счетчик адреса 9, информационные входы 10 и выход 11, адресные входы 12, вход данных 13, вход записи и считывания 1, десять выходов 15-24 блока управления 5, выход признака сравнения 25,выход признака переполнения 26, выход признака пустого накопителя 27, причем информационный вход устройства 10 является первым входом блока признака 1, первым входом блока сравнения 2 и входом первого элемента задержки 3, выход которого соединен с четвертым входом блока памяти 4, первый вход которого соединен с первым выходом счетчика адреса 9, второй и третий входы блока памяти 4 соединены с третьим 15 и четвертым 16 выходами блока управления 5, выход 11 блока памяти 4 является информационным выходом устройства, второй и третий входы блока признака 1 соединены с пятым 23 и шестым 24 выходами блока управления 5, выход блока признака 1 соединен с первым входом блока маски 6, второй и третий входы которого соединены с седьмым 21 и восьмым 22 выходами блока управления 5, выход блока маски 6 соединен с первым входом блока дискретного нелинейного элемента 7, второй и третий входы которого соединены с девятым 19 и десятым 20 выходами блока управления 5, выход блока дискретного нелинейного элемента 7 соединен со входом второго элемента задержки 8, выход которого соединен с третьим входом блока сравнения 2, второй вход которого соединен с первым выходом 18 блока управления 5, выход блока сравнения 2 является выходом 25 признака сравнения устройства и соединен также с первым входом счетчика адреса 9, второй и третий выходы которого являются выходами признака переполнения 26 и признака пустого накопителя 27 устройства соответственно, второй вход счетчика адреса 9 соединен со вто 3 90742013.04.30 рым выходом 17 блока управления 5, первый информационный вход 12 которого является адресным входом устройства, второй информационный вход 13 является входом управления данными, а третий информационный вход 14 является входом управления записью/считыванием устройства. Устройство работает следующим образом. Устройство может работать в трех режимах. В первом режиме происходит запись характерных признаков искомых сигналов в блок признака 1, блок маски 6 и блок дискретного нелинейного элемента 7. Причем в блок признака 1 записывается максимальное число символов , которые он может хранить, в блок маски 6 - маска адресов дискретного нелинейного элемента 7, а в сам блок дискретного нелинейного элемента 7 - переходная характеристика, соответствующая искомой информации. Дискретный нелинейный элемент 7 в описываемом варианте реализован на основе постоянного запоминающего устройства (ПЗУ), в которое записана переходная характеристика дискретного нелинейного элемента. Адреса, по которым хранится переходная характеристика, содержатся в блоке маски 6. Во втором режиме (рабочем) осуществляется фильтрация сигналов с целью обнаружения искомых неслучайных последовательностей в поступающих на информационный вход устройства данных по заданным признакам. Найденные символы записываются в блок памяти 4 и одновременно дублируются (выдаются) на выходе самого устройства. В третьем режиме из устройства можно считать всю накопленную в блоке памяти 4 информацию. На информационный вход устройства 10 подается последовательность закодированных символов, представляющая собой, например, -код. При включении питания блок управления 5 на первом выходе 18, четвертом выходе 16, шестом выходе 24, восьмом выходе 22 и десятом выходе 20 генерирует тактовые импульсы. Для перевода устройства в один из трех режимов требуется подать номер режима на третий информационный вход 14 управления записью/считыванием блока управления 5, после чего на третьем выходе 15, пятом выходе 23, седьмом выходе 21 и девятом выходе 19 блока управления 5 установятся логические уровни, которые переведут блок памяти 4, блока признака 1, блок маски 6 и блок дискретного нелинейного элемента 7 в выбранный режим работы. В первом режиме, то есть в режиме записи характерных признаков, поочередно в блок признака 1 следует записать число , в блок маски 6 - маску адресов дискретного нелинейного элемента 7 и в блок дискретного нелинейного элемента 7 - его переходную характеристику. Для этого на третий информационный вход 14 блока управления 5 подается номер первого режима работы, переводящий устройство в режим записи. Затем на первый информационный вход 12 блока управления 5 подаются данные, кодирующие адрес того блока, в который осуществляется запись настроек. Блок управления 5 расшифровывает адрес блока, в который необходимо записать данные, и переводит соответствующий блок в режим записи. После чего данные, полученные на втором информационном входе 13 блока управления 5, записываются в блок, адрес которого был получен ранее. Затем устройство может быть переведено во второй режим работы. Числоравно минимальному количеству неповторяющихся символов алфавита, используемого в искомой последовательности сигналов. К примеру, если использовать текстовые сигналы, то в словечислоравно единице, так как каждая из использованных в слове букв встречается в нем только один раз . В другом слове, к примеру , числоравно двум, так как для данного слова можно составить неповторяющуюся последовательность не менее чем из двух символов, так как в приведенном слове присутствуют три буквы . После преобразования в полученной последовательности слогов уже нет одинаковой последовательности символов. На основе полученной последовательности слогов создается отображение, в котором каждый слог отображается в следующий по порядку слог. Причем отображение 4 90742013.04.30 создается таким образом, что последний слог вызывает первый (фиг. 2). Таким образом,получается замкнутая последовательность слогов. Полученное отображение записывается в блок дискретного нелинейного элемента 7 в виде его переходной характеристики. Блок маски 6 позволяет найти адрес ячейки в блоке дискретного нелинейного элемента 7, которая соответствует значению его переходной характеристики для конкретного набора символов. После того как устройство начало работать во втором режиме, на вход устройства 10 подаются кодысоответствующих символов исследуемых сигналов, которые поступают на первый вход блока признака 1 и накапливаются в нем до величины . Когда число накопленных символов достигнет числа , вся полученная последовательность символов 1- по приходу очередного тактового импульса от блока управления 5 поступит с выхода блока признака 1 на первый вход блока маски 6. Блок маски 6 преобразует полученную последовательность 1- символов в число, лежащее в диапазоне адресов блока дискретного нелинейного элемента 7. Другими словами, блок маски 6 сопоставляет входную последовательность символов 1- с записанной в него маской адресов и таким образом определяет, какому адресу в памяти блока дискретного нелинейного элемента 7 соответствует данная последовательность. Блок дискретного нелинейного элемента 7 может быть построен на основе ПЗУ, входные данныекоторого представляют собой адреса, а выходные данные- символы (в рассматриваемом примере - -коды), записанные в ячейке памяти блока дискретного нелинейного элемента 7 по маске адресов, полученной от блока маски 6. Причем символравен первому символу ключевой последовательности -. По окончании преобразования по новому тактовому импульсу полученное числопоступает с выхода блока маски 6 на первый вход блока дискретного нелинейного элемента 7, который выполняет отображение входного адресав соответствии с загруженной в него переходной характеристикой. В результате на выходе блока дискретного нелинейного элемента 7 появляется -код некоторого символа , подающийся на вход второго элемента задержки 8, а с его выхода - на второй вход блока сравнения 2. Время задержки выбирается таким образом, чтобы к моменту появления на втором входе блока сравнения 2 кода символа 7 на его первый вход успел поступить следующий символ 1. Если полученный из блока дискретного нелинейного элемента 7 символсовпадет с очередным символом 1, поступившим через первый вход блока сравнения 2, то блок сравнения 2 сгенерирует сигнал совпадения. Данный сигнал подается на первый (инкрементирующий) вход счетчика адреса 9 и одновременно на выход 25, то есть на выход сигнала идентификации. Данный сигнал означает, что первый символ 1 принадлежит искомой последовательности. Последовательность символов 1- с информационного входа устройства поступает также и на вход первого элемента задержки 3. Время задержки выбирается таким образом, чтобы к моменту появления на входе устройства следующего символа 1 символ 1 появился на четвертом входе блока памяти 4. Так как первый символ 1 принадлежит искомой последовательности, при следующем тактовом импульсе символ 1 будет записан в блок памяти 4 по адресу, присутствующему на первом выходе счетчика адреса 9. В случае если новая последовательность символов 2-1 тоже принадлежит искомой последовательности сигналов, то при следующем тактовом импульсе блок сравнения 2 через свой выход выдаст сигнал на первый (инкрементирующий) вход счетчика адреса 9 и следующий искомый символ 2, запишется в блок памяти 4 уже по следующему адресу. Таким образом, в блоке памяти 4 будут сохранены все распознанные символы 1 искомой последовательности (где- ее длина), поступившие на вход устройства. Данные из блока памяти 4 могут быть извлечены. Для этого устройство переводится в третий режим работы. Блок управления 5 начинает формировать на втором выходе сигналы,поступающие на второй (декрементирующий) вход счетчика адреса 9 и уменьшающие зна 5 90742013.04.30 чение сохраненного в нем числа на единицу при каждом тактовом импульсе. С каждым тактовым сигналом из блока памяти 4 извлекается символ , принадлежащий к распознанной последовательности 1-, и поступает на информационный выход устройства. В случае отсутствия совпадений входныхсимволов и символов , полученных от блока дискретного нелинейного элемента 7, на выходе признака пустого накопителя 27 будет присутствовать сигнал логической единицы. В случае если объем распознанных символов 1-, соответствующих критериям поиска, превысит объем блока памяти 4 устройства, на выходе признака переполнения 26 появится сигнал логической единицы. Национальный центр интеллектуальной собственности. 220034, г. Минск, ул. Козлова, 20. 6