УСТРОЙСТВО ПОИСКА ИНФОРМАЦИИ Российский патент 1999 года по МПК G06F17/30 

Описание патента на изобретение RU2130644C1

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

Известный аналог предлагаемого устройства описан в авторском свидетельстве СССР N 1621049 класса (G 06 F 15/40), заявленном 09.01.89, и содержит регистры границ, суммирующие и вычитающие счетчики, схемы сравнения, блоки памяти, блоки вычисления и ряд других элементов, позволяющих осуществлять поиск информации. Однако указанная операция реализуется в нем относительно детерминированных информационных единиц с низкой оперативностью.

Ближайшее устройство поиска информации (прототип) к предлагаемому описано в авторском свидетельстве СССР N 1711185 класса (G 06 F 15/40), заявленном 05.04.89. В указанном изобретении описано устройство поиска информации, содержащее регистры верхней и нижней границы, сумматор-вычитатель, регистр стратегии поиска, вычитающий и суммирующие счетчики, схемы сравнения, блок памяти, регистр ключа, выходной регистр, группы элементов И и ИЛИ, триггер, распределитель импульсов, вход запуска, входы адресов верхней и нижней границы, вход кода критерия смены стратегии поиска, вход ключа, выход адреса, выход признака отсутствия информации. Описанное устройство обладает более высокой оперативностью по сравнению с вышеотмеченным.

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

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

Поставленная цель достигается тем, что в известном устройстве поиска информации, включающем регистры верхней границы и адреса, распределитель импульсов, первый компаратор, четырехвходовый, двухвходовый и (N-1)-входовый элементы И, первый RS-триггер, суммирующий счетчик, элемент ИЛИ, вход "Запуск", выход адреса, вход "Адрес верхней границы", вход "Адрес нижней границы", блок памяти, адресный вход которого соединен с выходом суммирующего счетчика, дополнительно введены второй компаратор, регистр окна, второй и третий RS-триггеры, вычитатель адресов, генератор, селектор серий, первый и второй элементы задержки, суммирующий счетчик нижней границы, блок из N счетчиков, где N>1, блок из N-1 делителей на два, блок из N-1 вычитателей, блок из N-1 двухпороговых компараторов, первый, второй и третий ключи.

K-разрядные информационные входы первого, второго и третьего ключей являются соответственно k-разрядными входами "Адрес верхней границы", "Адрес нижней границы", "Интервал поиска" устройства, где k равно разрядности адресных данных. K-разрядные выходы первого, второго и третьего ключей соединены соответственно с k-разрядными информационными входами регистра верхней границы, суммирующего счетчика нижней границы и регистра окна. K-разрядный выход регистра верхней границы соединен с первым k-разрядным входом первого компаратора. K-разрядный выход суммирующего счетчика нижней границы соединен одновременно с k-разрядными информационными входами суммирующего счетчика и регистра адреса, а также с k-разрядным входом "Уменьшаемое" вычитателя адресов. K-разрядный выход регистра окна соединен с вторым k-разрядным входом второго компаратора. Первый k-разрядный вход второго компаратора соединен с k-разрядным выходом вычитателя адресов. Адресный вход блока памяти соединен с выходом суммирующего счетчика.

Второй и третий выходы распределителя импульсов соединены соответственно с входами "Установка 1" первого RS-триггера и "Установка 0" второго RS-триггера. Входы "Установка 1" второго RS- триггера, "Установка 0" первого и третьего RS-триггеров, входы "Разрешение параллельной загрузки" регистров верхней границы, окна, адреса, суммирующего счетчика нижней границы, вход распределителя импульсов, вход инициализации селектора серий соединены в параллель и подключены к входу устройства "Запуск". Первый вход элемента ИЛИ, управляющие входы первого, второго и третьего ключей соединены одновременно с первым выходом распределителя импульсов. K- разрядный выход суммирующего счетчика соединен одновременно с вторым k-разрядным входом первого компаратора и k-разрядным входом "Вычитаемое" вычитателя адресов. Информационный и управляющий входы блока памяти соединены соответственно с информационным входом устройства и выходом первого RS-триггера. Выход блока памяти соединен с информационным входом селектора серий. Вход синхронизации селектора серий соединен с выходом первого элемента задержки. Выходы первого компаратора и второго RS-триггера, генератора и инверсный третьего RS-триггера соединены соответственно с первым, вторым, третьим и четвертым входами четырехвходового элемента И. Выход четырехвходового элемента И соединен одновременно со счетным входом суммирующего счетчика и входом первого элемента задержки. Выход второго компаратора соединен одновременно со счетным входом суммирующего счетчика нижней границы и с вторым входом элемента ИЛИ. Выход элемента ИЛИ соединен одновременно с входами установки в ноль блока из N счетчиков и входом второго элемента задержки. Выход второго элемента задержки соединен с входом "Разрешение параллельной загрузки" суммирующего счетчика. N-разрядный выход селектора серий соединен с N-разрядным информационным входом блока из N счетчиков.

N-разрядный выход блока из N счетчиков соединен одновременно с (N-1)-разрядным входом блока из N-1 делительный на два и (N-1)-разрядным входом "Вычитаемое" блока из N-1 вычитателей. Причем 1, 2, 3, ...., N-1 разряды выхода блока из N счетчиков соединены соответственно с 1, 2, 3, ..., N-1 разрядами входа блока из N-1 делителей на два и, кроме того, разряды 2, 3, . ..., N-1, N блока из N счетчиков соединены соответственно с 1, 2,..., (N-2), (N-1) разрядами входа "Вычитаемое" блока из N-1 вычитателей. В других случаях соединений выходов и входов блоков, входящих в устройство, поразрядное их соединение не оговаривается, т.к. соединяются соответствующие по номеру разряды выходов и входов.

(N-1)-разрядный вход "Уменьшаемое" и (N-1)-разрядный выход блока из N-1 вычитателей соединены соответственно с (N-1)-разрядным выходом блока из N-1 делителей на два и вторым (N-1)-разрядным входом блока из N-1 двухпороговых компараторов. Первый (N-1)-разрядный вход блока из N-1 двухпороговых компараторов является (N-1)-разрядным входом "Порог" устройства. (N-1)-разрядный выход блока из N-1 двухпороговых компараторов соединен с (N-1)-разрядным входом (N-1)-входового элемента И. Выход (N-1)-входового элемента И соединен с входом "Установка 1" третьего RS-триггера. Прямой выход третьего RS-триггера соединен с управляющим входом регистра адреса. K-разрядный выход регистра адреса является выходом устройства - Выход адреса.

Селектор серий состоит из (N+2)-разрядного регистра сдвига, блока из N+2 ключей и дешифратора, (N+2)-разрядный вход дешифратора соединен с (N+2)-разрядным выходом блока из N+2 ключей. (N+2)-разрядный информационный вход блока из N+2 ключей соединен с (N+2)-разрядным выходом регистра сдвига, информационный вход и вход инициализации которого являются соответственно информационным входом и входом инициализации селектора серий. Тактовый вход блока из N+2 ключей является входом синхронизации селектора серий. N-разрадный выход дешифратора является N-разрядным выходом селектора серий.

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

Заявленное устройство поясняется чертежами, где на фиг.1 - общая схема устройства поиска информации; на фиг.2 - селектор серий; на фиг.3 - блок из N-1 двухпороговых компараторов;
в таблице - соответствие значений разрядов на входе и выходе дешифратора.

Устройство, показанное на фиг. 1, содержит первый 1, второй 2 и третий 3 ключи, селектор серий 4, регистр верхней границы 5, суммирующий счетчик нижней границы 6, регистр окна 7, регистр адреса 27, суммирующий счетчик 8, первый 9 и второй 15 компараторы, распределитель импульсов 10, первый 19 и второй 24 элементы задержки, вычитатель адресов 12, блок памяти 13, генератор 14, первый 11, второй 16 и третий 26 RS-триггеры, четырехвходовый 17 и (N-1)-входовый 25 элементы И, элемент ИЛИ 18, блок из N счетчиков 20, блок из N-1 делителей на два 21, блок из N-1 вычитателей 22, блок из N-1 двухпороговых компараторов 23. Причем N-целое и N>1.

K-разрядные информационные входы первого 1, второго 2 и третьего 3 ключей являются соответственно k-разрядными входами "Адрес верхней границы", "Адрес нижней границы", "Интервал поиска" устройства, где k равно разрядности адресных данных. K-разрядные выходы первого 1, второго 2 и третьего 3 ключей соединены соответственно с k-разрядными информационными входами регистра верхней границы 5, суммирующего счетчика нижней границы 6 и регистра окна 7. K-разрядный выход регистра верхней границы 5 соединен с первым k-разрядным входом первого компаратора 9. K-разрядный выход суммирующего счетчика нижней границы 6 соединен одновременно с k-разрядными информационными входами суммирующего счетчика 8 и регистра адреса 27, а также с k-разрядным входом "Уменьшаемое" вычитателя адресов 12. K-разрядный выход регистра окна 7 соединен с вторым k-разрядным входом второго компаратора 15. Первый k-разрядный вход второго компаратора 15 соединен с k-разрядным выходом вычитателя адресов 12. Адресный вход блока намята 13 соединен с выходом суммирующего счетчика 8.

Второй и третий выходы распределителя импульсов 10 соединены соответственно с входами "Установка 1" первого RS-триггера 11 и "Установка 0" второго RS-триггера 16. Входы "Установка 1" второго 16 RS-триггера, "Установка 0" первого 11 и третьего 26 RS-григгеров, входы "Разрешение параллельной загрузки" регистров верхней границы 5, окна 7, адреса 27, суммирующего счетчика нижней границы 6, вход распределителя импульсов 10, вход инициализации селектора серий 4 соединены в параллель и подключены к входу устройства "Запуск". Первый вход элемента ИЛИ 18, управляющие входы первого 1, второго 2 и третьего 3 ключей соединены одновременно с первым выходом распределителя импульсов 10. K-разрядный выход суммирующего счетчика 8 соединен одновременно с вторым k-разрядным входом первого компаратора 9 и k-разрядным входом "Вычитаемое" вычитателя адресов 12. Информационный и управляющий входы блока памяти 13 соединены соответственно с информационным входом устройства и выходом первого RS-триггера 11. Выход блока памяти 13 соединен с информационным входом селектора серий 4. Вход синхронизации селектора серий 4 соединен с выходом первого элемента задержки 19. Выходы первого компаратора 9 и второго RS-триггера 16, генератора 14 и инверсный третьего RS-триггера 26 соединены соответственно с первым, вторым, третьим и четвертым входами четырехвходового элемента И 25. Выход четырехвходового элемента И 25 соединен одновременно со счетным входом суммирующего счетчика 8 и входом первого элемента задержки 19. Выход второго компаратора 15 соединен одновременно со счетным входом суммирующего счетчика нижней границы 6 и с вторым входом элемента ИЛИ 18. Выход элемента ИЛИ 18 соединен одновременно с входами установки в ноль блока из N счетчиков 20 и входом второго элемента задержки 24. Выход второго элемента задержки 24 соединен с входом "Разрешение параллельной загрузки" суммирующего счетчика 8. N-разрядный выход селектора серий 4 соединен с N-разрядным информационным входом блока из N счетчиков 20.

N-разрядный выход блока из N счетчиков 20 соединен одновременно с (N-1)-разрядным входом блока из N-1 делителей на два 21 и (N-1)-разрядным входом "Вычитаемое" блока из N-1 вычитателей 22. Причем 1,2,3,..., N-1 разряды выхода блока из N счетчиков соединены соответственно с 1, 2, 3,..., N-1 разрядами входа блока из N-1 делителей на два и, кроме того, разряды 2, 3, . . . , N-1, N блока из N счетчиков соединены соответственно с 1, 2,..., (N-2), (N-1) разрядами входа "Вычитаемое" блока из N-1 вычитателей. В других случаях соединений выходов и входов блоков, входящих в устройство, поразрядное их соединение не оговаривается, т.к. соединяются соответствующие по номеру разряды выходов и входов.

(N-1)-разрядный вход "Уменьшаемое" и (N-1)-разрядный выход блока из N-1 вычитателей 22 соединены соответственно с (N-1)-разрядным выходом блока из N-1 делителей на два 21 и вторым (N-1)-разрядным входом блока из N-1 двухпороговых компараторов 23. Первый (N-1)-разрядный вход блока из N-1 двухпороговых компараторов 23 является (N-1)-разрядным входом "Порог" устройства. (N-1)-разрядный выход блока из N-1 двухпороговых компараторов 23 соединен с (N-1)-разрядным входом (N-1)-входового элемента И 25. Выход (N-1)-входового элемента И 25 соединен с входом "Установка 1" третьего RS-триггера 26. Прямой выход третьего RS-триггера 16 соединен с управляющим входом регистра адреса 27. K-разрядный выход регистра адреса 27 является выходом устройства - Выход адреса.

На фиг. 2 показан селектор серий 4, который вырабатывает сигнал на том одном из N разряде его выхода, который соответствует длине серии, поступающей на его информационный вход. Селектор серий 4 состоит из (N+2)-разрядного регистра сдвига 4.1, блока из N+2 ключей 4.2 и дешифратора 4.3. (N+2)-разрядный вход дешифратора 4.3 соединен с (N+2)-разрядным выходом блока из N+2 ключей 4.2. (N+2)-разрядный информационный вход блока из N+2 ключей 4.2 соединен с (N+2)-разрядным выходом регистра сдвига 4.1, информационный вход и вход инициализации которого являются соответственно информационным входом и входом инициализации селектора серий 4. Тактовый вход блока из N+2 ключей 4.2 является входом синхронизации селектора серий 4. N-разрядный выход дешифратора 4.3 является N-разрядным выходом селектора серий 4. Соответствие значений разрядов на входе и выходе дешифратора 4,3 приведено в таблице.

На фиг.3 показан блок из N-1 двухпороговых компараторов 23, который вырабатывает сигнал на каждом i-разряде (i= 1,2,...N-1) его (N-1)-разрядного выхода, который соответствует случаю попадания значения, поступающего на i-разряд второго (N-1)-разрядного входа 23, в интервал между верхним и нижним значением порога, поступающего на i-разряд первого (N-1)-разрядного входа 23. Блок из N-1 двухпороговых компараторов 23 состоит из 1-го, 2-го,.. . , N-1-го двухпороговых компараторов 23.1, 23.2,..., 23.N-1, каждый из которых содержит соответственно первый 23.1.1, 23.2.1,..., 23.N-1.1 и второй 23.1.2, 23.2.2,..., 23.N-1.2 компараторы, а также элемент И 23.1.3, 23.2.3,. .., 23.N-1.3. Каждый i-разряд второго (N-1)-разрядного входа 23 соединен одновременно с вторым входом первого компаратора и с первым входом второго компаратора i-го двухпорогового компаратора. Каждый i-разряд первого (N-1)-разрядного входа 23 состоит из двух подразрядов, причем на первый подразряд подается верхнее значение порога, а на второй - нижнее значение порога с аналогичных подразрядов i-разряда (N-1)-разрядного входа устройства "Порог". Верхнее значение порога i-разряда первого N-1-разрядного входа блока 23 подается на первый вход первого компаратора i-го двухпорогового компаратора. Нижнее значение порога i-разряда первого N-1-разрядного входа блока 23 подается на второй вход второго компаратора i-го двухпорогового компаратора. Выходы первого и второго компараторов i-го двухпорогового компаратора соединены соответственно с первым и вторым входом элемента И i-го двухпорогового компаратора, выход которого является i-м разрядом (N1)-разрядного выхода блока из N-1 двухпороговых компараторов 23.

Блоки и устройства, не раскрытые в данном описании, могут быть реализованы известными из литературы способами (схемами), возможные варианты построения которых приводятся ниже.

Суммирующие счетчики: 6, 8 строятся на основе однонаправленного суммирующего счетчика с увеличением счета и с предварительной записью. Предварительная запись осуществляется через k-разрядный информационный вход суммирующего счетчика после поступления импульса на вход "Разрешение параллельной загрузки" счетчика. Добавление к записанной в счетчик комбинации единицы - при поступлении сигнала на счетный вход. Возможность построения однонаправленного суммирующего счетчика с увеличением счета и с предварительной записью показана в [Цифровые интегральные микросхемы: справочник/ Богданович, Грель, Прохоренко, Шалимо. - Минск: Беларусь, 1991. - 493 с.] на стр. 138, рис. 2.69.

Блок из N счетчиков: 20 строится на основе объединения N однонаправленных суммирующих счетчиков с увеличением счета и без предварительной записи. Обнуление каждого из входящих в блок счетчиков происходит при поступлении сигнала на вход установки в ноль блока из N счетчиков, а прибавление к записанной в каждый из N счетчиков комбинации единицы - при поступлении сигнала на счетный вход соответствующего счетчика; i-й разряд N-разрядного информационного входа блока из N счетчиков соответствует счетному входу i-го счетчика блока из N счетчиков (i=1,2,3...N).

Дешифратор: 4.3. Дешифратор в общем случае имеет n входов и N выходов и выполняет следующую функцию: каждому входному слову (n-разрядному входу), т. е. комбинации единиц и нулей на входе, соответствует сигнал "1" на одном определенном выходе; обычно сигнал "1" появляется на той выходной шине, номер которой в двоичной форме совпадает с входным n разрядным кодом. Структура дешифратора на 3 входа и 23= 8 выходов показана в [Гольденберг Л.М. Импульсные и цифровые устройства. Учебник для ВУЗов. М.: Связь. 1973. 496 с.] на рис. 10.12. Аналогичным образом строится дешифратор на N+2 входов и 2N+2 выходов. В случае построения дешифратора 4.3 используются только первые N выходов согласно таблице.

Элементы задержки: 19, 24. Являются линиями задержки (ЛЗ). Сигнал на выходе линии задержки воспроизводится с некоторой задержкой на определенный период времени tp. ЛЗ может быть построена путем последовательного соединения одновходовых схем ИЛИ, каждая из которых для определенного базиса (серии микросхем) имеет время задержки tзi. Тогда требуемое значение tз= Σtзi.
Другая возможная реализация показана в [Гольденберг Л.М. Импульсные и цифровые устройства. Учебник для ВУЗов. М.: Связь. 1973. 496 с.] на рис. 1.27.

Распределитель импульсов: 10. Он строится путем последовательного соединения трех элементов задержки. Выходы первого, второго и третьего элементов задержки являются соответственно первым, вторым и третьим выходами распределителя импульсов.

Компараторы: 9, 15, 23.1.1, 23.2.1,..., 23.N-1.1, 23.1.2, 23.2.2,..., 23.N-1.2. Компаратор выполняет операцию сравнения двух n разрядных чисел A и B и формирует на одном из трех выходов (A<B, A>B, A=B) сигнал "1"; число входов компаратора равно 2n. При сравнении двухрязрадных чисел компаратор строится на основе таблицы 2.10 на стр.51 (Лебедев О.Н., Сидоров А.М. Импульсные и цифровые устройства. Цифровые узлы и их проектирование на микросхемах. Л.: ВАС. 1980. 128 с.] и реализован на рис. 2.33 (стр. 52). Т.к. схемы сравнения обладают свойством наращиваемости, то компаратор для сравнения двух n-разрядных чисел строится по аналогии с таблицей 2.11, рис. 2.35, стр. 53-54, до требуемой величины n. У каждого из используемых в устройстве компараторов задействован только один из выходов: у 15 - "равно"; у 9, 23.1.1, 23.2.1, ..., 23.N-1.1 - "меньше"; у 23.1.2, 23.2.2,..., 23.N- 1.2-"больше".

Регистры верхней границы 5, окна 7, адреса 27 являются регистрами параллельного действия. Построение таких регистров из n входов и n выходов показано в [Шляпоберский В.И. Основы техники передачи дискретных сообщений. М. : Связь. 1973. 480 с.] на рис. 3.1, стр. 106. Указанные регистры используются также в качестве блоков памяти, ранящих один элемент (операнд) в течение одного интервала анализа.

Блок памяти : 13. Возможное построение блока памяти показано в [С.Т. Хвощ, Н.Н. Варлинский, Е.А. Попов. Микропроцессоры и микроЭВМ в системах автоматического управления. - Справочник. Л.: Машиностроение, 1987.] на рис. 14.1, стр. 434.

Вычитатель адресов: 12 и блок из N-1 вычитателей : 22, который строится на основе объединения N-1 вычитателей. Вычитатель строится на основе сумматора, на один вход которого подается уменьшаемое, на другой дополнение до единицы вычитаемого (отрицание вычитаемого - через схему НЕ - поразрядно складывается по модулю два с единицей).

Ключи: 1, 2, 3. Ключ, в общем случае, строится в виде мультиплексора, принцип построения которого описан в [Лебедев О.Н., Сидоров А.М. Импульсные и цифровые устройства. Цифровые узлы и их проектирование на микросхемах. Л.: ВАС. 1980. 128 с.] стр. 54. Реализация мультиплексора на 8 каналов, управляемых 3-элементным кодом показана на рис. 2.36 стр. 55 (построена на основе таблицы 2.12 стр. 54). При одноразрядном управляющем входе мультиплексор вырождается в простейший ключ, который чаще всего реализуется n-входовыми схемами И.

Блок из N-1 делителей на два: 21, который строится на основе объединения N-1 устройств деления. Устройство деления двух n разрядных двоичных чисел строится на основе алгоритма деления без восстановления остатка, описанного в [Бочаров К. П. , Немшилов Н.Н., Петров Е.И., Сулин Л.И. Вычислительные комплексы автоматизированных систем управления. Л.: ВАС. 1984. 368 с.], стр. 88-90, рис. 3.24 (а). Схема устройства деления представлена на стр. 89, рис. 3.24 (б). Результат деления - n-разрядное двоичное число. В случае, когда разрядность поступающих на вход устройства деления чисел разная, за n принимаем большую разрядность. Число с меньшей разрядностью представляем n разрядным, добавлением в старшие разряды нулей.

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

Устройство поиска информации работает следующим образом. Сигналом с входа "Запуск" осуществляется инициализация (начальная установка) регистров 5, 7 и счетчика 6, после чего в них записываются значения адресов верхней, нижней границы и интервала поиска через ключи 1, 2 и 3 соответственно. Необходимое разнесение во времени указанных операций обеспечивается распределителем 10, на первом выходе которого сигнал появляется с задержкой на 1τ. Значение данной задержки должно быть не меньше продолжительности переходных процессов инициализации. Этот же задержанный сигнал устанавливает в начальное состояние блок из N счетчиков 20 и, пройдя через элемент задержки 24, перезаписывает значение нижней границы с выхода счетчика 6 в суммирующий счетчик 8. Этот счетчик (8) формирует текущее значение адреса анализа в информационном массиве, хранящемся в блоке памяти 13, начиная с некоторого его нижнего значения. Таким образом, началу каждого цикла анализа соответствует равенство
AТнг + Aнг,
где AТнг - текущее значение адреса нижней границы, Aнг - абсолютное значение адреса нижней границы поиска.

Сигналом "Запуск" также осуществляется инициализация триггеров 11, 16 и 26, регистра 27 и селектора серий 4. При этом триггер 11 своим выходным сигналом разрешает запись информации в блок памяти 13 (запись анализируемого информационного массива в блок памяти может осуществляться параллельным или последовательным способом). Тактовые импульсы генератора 14 через элемент 17 не проходят, поскольку последний закрыт запрещающим сигналом триггера 16. Регистр адреса 27 обнуляется, запись в него значения адреса поиска запрещена соответствующим сигналом с прямого выхода триггера 26. Регистры сдвига селектора серий 4 этим сигналом также обнуляются.

Затем сигнал "Запуск", задержанный на 2τ распределителем 10, устанавливает триггер 11 в противоположное состояние, и блок памяти 13 переходит в режим "чтения". Через время 3τ сигнал "Запуск" с третьего выхода распределителя 10 переключает триггер 16, разрешающий сигнал с выхода которого открывает элемент И 17 для прохождения тактовых импульсов генератора 14 на суммирующий счетчик 8 и, через элемент задержки 19, на селектор серий 4. Данная задержка устраняет влияние переходных процессов установки адреса информационного элемента в блоке памяти 13.

Под воздействием тактовых импульсов состояние счетчика 8 последовательно изменяется в сторону увеличения, а соответственно увеличивается и значение адреса блока памяти 13, в пределах значений интервала поиска -Δun, начиная со значения нижней границы
AТнг≤ A ≤ ATнгun,
где A - абсолютное значение адреса поиска в анализируемом информационном массиве.

При этом на селектор серий последовательно поступают символы входного информационного массива.

Серии символов различной длины l(1 ≤ l ≤ N), выделенные селектором, подсчитываются соответствующими счетчиками, число которых в блоке 20 равно числу различаемых серий N. Для выделения состояния статистической неоднородности, при котором функция распределения исследуемого потока изменяется, в блоках 21, 22 и 23 анализируется характер распределения серий. При степени неопределенности потока, превышающей заданный порог (на входе "Порог"), сигнал на выходе элемента И 25 переключает триггер 26 в противоположное состояние, при этом прекращается поступление тактовых импульсов в счетчик 8 и в регистр адреса 27 разрешается запись текущего значения адреса нижней границы, указывающей на интервал, в котором статистические характеристики потока меняются. Если в текущем интервале поиска изменений характеристик потока не обнаружено, то по достижении значения адреса A = Aнгun, выделяемое компаратором 15, текущее значение адреса нижней границы поиска увеличивается в суммирующем счетчике 6 на единицу
AТнг = AТнг + 1,
которое с задержкой, определяемой элементом 24, переписывается в счетчик 8. После чего начинается новый цикл поиска. Данный итеративный процесс продолжается до тех пор, пока компаратор 9 не выдаст сигнал останова, соответствующий достижению верхней границы поиска (Aвг)
A = AТнгun= Aвг.
При этом работа схемы останавливается, поскольку элемент 17 закрывается запрещающим сигналом с выхода компаратора 9.

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

Обоснование используемого принципа поиска в предлагаемом устройстве проведено следующим образом.

Анализ информационных массивов осуществляется в предположении априорной неопределенности относительно их функций распределения и поэтому нуждается в исследованиях, свободных от распределений, что обеспечивается непараметрическими методами. Одной из процедур, позволяющих установить статистическую независимость и выявить наличие тренда в таких условиях, является критерий серий [Бендат Дж. , Пирсол А. Прикладной анализ случайных данных. М.: Мир, 1989. ] . Этот критерий позволяет также проводить анализ и нестационарных случайных данных.

В соответствии с данным критерием, если вероятность отдельных исходов (например, 0 или 1) не меняется от наблюдения к наблюдению, то выборочное распределение числа серий в последовательность является случайной величиной со средним значением и дисперсией


Здесь N1 - число исходов 0, а N2 - число исходов 1, N=N1 + N2.

С другой стороны, известно [Винокуров В.И., Гантмахер В.Е. Дискретно-кодированные последовательности. Ростов-на-Дону: Ростовский университет. 1990. ] , что при q независимых исходах одной и той же случайной величины серии различной длины l распределяются в соответствии с выражением

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

В данном устройстве количество серий различной длины l подсчитывается соответствующими счетчиками на интервале поиска Δun, после чего оценивается характер распределения их числа. Оценка осуществляется с учетом порога, которым вводится допустимый диапазон отклонений получаемого распределения от теоретического.

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

название год авторы номер документа
УСТРОЙСТВО ПОИСКА ИНФОРМАЦИИ 1997
  • Алексеев А.А.
  • Липатников В.А.
  • Самойлов Ю.Б.
  • Тараскин М.М.
  • Пьянков В.В.
  • Устимов Е.А.
RU2116670C1
УСТРОЙСТВО УПРАВЛЕНИЯ ПЕРЕДАЧЕЙ ДАННЫХ ПО РАДИОКАНАЛУ 1997
  • Белобров Е.Г.
  • Бобровский В.И.
  • Паращук И.Б.
  • Путилин А.Н.
  • Шарко Г.В.
RU2116004C1
СЕЛЕКТОР ИМПУЛЬСНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ 1994
  • Смирнов П.Л.
  • Терентьев А.В.
  • Викторов А.В.
  • Соловьев Н.В.
RU2085028C1
УСТРОЙСТВО АВТОМАТИЧЕСКОГО ПОИСКА РАДИОСТАНЦИЙ 1994
  • Липатников В.А.
  • Архипенко А.А.
  • Сапаев Е.Г.
RU2099868C1
СПОСОБ ШИФРОВАНИЯ/ДЕШИФРОВАНИЯ СООБЩЕНИЙ ХЭШИРУЮЩЕЙ ФУНКЦИЕЙ И УСТРОЙСТВО, ЕГО РЕАЛИЗУЮЩЕЕ 1998
  • Бурнашев Р.У.
  • Оков И.Н.
  • Туринцев И.В.
  • Царик О.В.
RU2138126C1
СПОСОБ И УСТРОЙСТВО РАСПОЗНАВАНИЯ КЛАССОВ СИГНАЛОВ 1998
  • Асеев А.Ю.
  • Балаболин О.В.
  • Григорьев С.В.
  • Сауков А.М.
RU2133501C1
УСТРОЙСТВО АВТОМАТИЧЕСКОГО ПОИСКА СИГНАЛОВ РАДИОСТАНЦИЙ 1998
  • Архипенко А.А.
  • Горин Д.Г.
  • Липатников В.А.
  • Сапаев Е.Г.
  • Толочков С.В.
RU2132111C1
УСТРОЙСТВО УПРАВЛЕНИЯ ПЕРЕДАЧЕЙ ДАННЫХ ПО РАДИОКАНАЛУ 1998
  • Шарко Г.В.
  • Иванов А.А.
  • Макаров М.И.
RU2144267C1
УСТРОЙСТВО ПОИСКА ИНФОРМАЦИИ 2006
  • Авраменко Владимир Семенович
  • Бухарин Владимир Владимирович
  • Бушуев Сергей Николаевич
  • Гурьев Сергей Николаевич
  • Копчак Ян Миланович
  • Паращук Игорь Борисович
RU2313128C1
УСТРОЙСТВО МОНИТОРИНГА ИНФОРМАЦИОННОГО ТРАФИКА 2005
  • Барышников Николай Владимирович
  • Гончаров Евгений Сергеевич
  • Капитонов Александр Васильевич
  • Киреев Владимир Сергеевич
  • Слабов Роман Игоревич
  • Стародубцев Юрий Иванович
  • Тараскин Михаил Михайлович
RU2290691C1

Иллюстрации к изобретению RU 2 130 644 C1

Реферат патента 1999 года УСТРОЙСТВО ПОИСКА ИНФОРМАЦИИ

Изобретение относится к области вычислительной техники и может быть использовано в качестве устройства для поиска участков информации, имеющих заданный закон распределения. Технический результат изобретения заключается в обеспечении возможности поиска информации о границах статистических неоднородностей. Устройство содержит первый, второй и третий ключи, селектор серий, регистр верхней границы, суммирующий счетчик нижней границы, регистр окна, регистр адреса, суммирующий счетчик, первый и второй компараторы, распределитель импульсов, первый и второй элементы задержки, вычитатель адресов, блок памяти, генератор, первый, второй и третий RS-триггеры, четырехвходовый и (N-1)-входовый элементы И, элемент ИЛИ, блок N счетчиков, блок из N-1 делителей на два, N-1 вычитателей, блок из N-1 двухпороговых компараторов. Устройство позволяет путем анализа информационного массива находить границы его статистических неоднородностей на основе использования непараметрической процедуры критерия серий. Для этого информационный массив анализируется скользящим <окном>, размер которого определяется дисперсией распределения неоднородностей. 1 з.п. ф-лы, 3 ил., 1 табл.

Формула изобретения RU 2 130 644 C1

1. Устройство поиска информации, содержащее регистры верхней границы и адреса, распределитель импульсов, первый компаратор, четырехвходовый и (N - 1)-входовый элементы И, первый RS-триггер, суммирующий счетчик, элемент ИЛИ, вход "Запуск", вход "Адрес верхней границы", вход "Адрес нижней границы", выход адреса, блок памяти, адресный вход которого соединен с выходом суммирующего счетчика, отличающееся тем, что дополнительно введены второй компаратор, регистр окна, второй и третий RS-триггеры, вычитатель адресов, генератор, селектор серий, первый и второй элементы задержки, суммирующий счетчик нижней границы, блок из N счетчиков, где N - целое и N > 1, блок из N - 1 делителей на два, блока из N - 1 вычитателей, блок из N - 1 двухпороговых компараторов, первый, второй и третий ключи, K-разрядные информационные входы которых являются соответственно K-разрядными входами "Адрес верхней границы", "Адрес нижней границы", "Интервал поиска" устройства, где K равно разрядности адресных данных, K-разрядные выходы первого, второго и третьего ключей соединены соответственно с K-разрядными информационными входами регистра верхней границы, суммирующего счетчика нижней границы и регистра окна, K-разрядный выход регистра верхней границы соединен с первым K-разрядным входом первого компаратора, K-разрядный выход суммирующего счетчика нижней границы соединен одновременно с K-разрядными информационными входами суммирующего счетчика и регистра адреса, а также с входом "Уменьшаемое" вычитателя адресов, K-разрядный выход регистра окна соединен с вторым K-разрядным входом второго компаратора, первый K-разрядный вход которого соединен с K-разрядным выходом вычитателя адресов, второй и третий выходы распределителя импульсов соединены соответственно с входами "Установка 1" первого RS-триггера и "Установка 0" второго RS-триггера, входы "Установка 1" второго RS-триггера, "Установка 0" первого и третьего RS-триггеров, входы "Разрешение параллельной загрузки" регистров верхней границы, адреса, окна, суммирующего счетчика нижней границы, вход распределителя импульсов, вход инициализации селектора серий соединены в параллель и подключены к входу устройства "Запуск", первый вход элемента ИЛИ, управляющие входы первого, второго и третьего ключей соединены одновременно с первым выходом распределителя импульсов, K-разрядный выход суммирующего счетчика соединен одновременно с вторым K-разрядным входом первого компаратора и K-разрядным входом "Вычитаемое" вычитателя адресов, информационный и управляющий входы блока памяти соединены соответственно с информационным входом устройства и выходом первого RS-триггера, выход блока памяти соединен с информационным входом селектора серий, вход синхронизации которого соединен с выходом первого элемента задержки, выходы первого компаратора и второго RS-триггера, генератора и инверсный третьего RS-триггера соединены соответственно с первым, вторым, третьим и четвертым входами четырехвходового элемента И, выход которого соединен одновременно со счетным входом суммирующего счетчика и входом первого элемента задержки, выход второго компаратора соединен одновременно со счетным входом суммирующего счетчика нижней границы и с вторым входом элемента ИЛИ, выход которого соединен одновременно с входом "Установка 0" блока из N счетчиков и входом второго элемента задержки, выход которого соединен с входом "Разрешение параллельной загрузки" суммирующего счетчика, N-разрядный выход селектора серий соединен с N-разрядным информационным входом блока из N счетчиков, N-разрядный выход которого соединен одновременно с (N - 1)-разрядным входом блока из N - 1 делителей на два и (N - 1)-разрядным входом "Вычитаемое" блока из N - 1 вычитателей, (N - 1)-разрядный вход "Уменьшаемое" и (N - 1)-разрядный выход которого соединены соответственно с (N - 1)-разрядным выходом блока из N - 1 делителей на два и вторым (N - 1)-разрядным входом блока из N - 1 двухпороговых компараторов, первый (N - 1)-разрядный вход которого является (N - 1)-разрядным входом "Порог" устройства, (N - 1)-разрядный вход блока из N - 1 двухпороговых компараторов соединен с (N - 1)-разрядным входом (N - 1)-входового элемента И, выход которого соединен с входом "Установка 1" третьего RS-триггера, прямой выход которого соединен с управляющим входом регистра адреса, K-разрядный выход которого является выходом устройства - Выход адреса. 2. Устройство по п.1, отличающееся тем, что селектор серий состоит из (N + 2)-разрядного регистра сдвига, блока из N + 2 ключей и дешифратора, (N + 2)-разрядный вход которого соединен с (N + 2)-разрядным входом блока из N + 2 ключей, (N + 2)-разрядный информационный вход которого соединен с (N + 2)-разрядным выходом регистра сдвига, информационный вход и вход инициализации которого являются соответственно информационным входом и входом инициализации селектора серий, тактовый вход блока из N + 2 ключей является входом синхронизации селектора серий, N-разрядный выход дешифратора является N-разрядным выходом селектора серий.

Документы, цитированные в отчете о поиске Патент 1999 года RU2130644C1

Устройство для поиска информации 1989
  • Пришибской Александр Владимирович
  • Глушань Валентин Михайлович
  • Курейчик Виктор Михайлович
SU1711185A1
Устройство для поиска информации 1989
  • Глушань Валентин Михайлович
  • Курейчик Виктор Михайлович
  • Пришибской Александр Владимирович
SU1621049A1
УСТРОЙСТВО ПОИСКА ИНФОРМАЦИИ 1995
  • Липатников В.А.
  • Плотников А.М.
  • Якимовец В.В.
RU2094845C1
СПОСОБ РЕГЕНЕРАЦИИ ВУЛКАНИЗОВАННЫХ ЭЛАСТОМЕРНЫХ ОТХОДОВ 1991
  • Гринцевич В.Ф.
  • Шаховец С.Е.
  • Петров Г.Н.
  • Раппопорт Леонид Яковлевич[Us]
RU2014339C1
US 4611298 A, 09.09.86.

RU 2 130 644 C1

Авторы

Мартынов М.В.

Пьянков В.В.

Савельев С.К.

Стародубцев Ю.И.

Тараскин М.М.

Устимов Е.А.

Даты

1999-05-20Публикация

1998-05-19Подача