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

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

Известный аналог предлагаемого устройства описан в авторском свидетельстве СССР 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 входа и 2³= 8 выходов показана в [Гольденберг Л.М. Импульсные и цифровые устройства. Учебник для ВУЗов. М.: Связь. 1973. 496 с.] на рис. 10.12. Аналогичным образом строится дешифратор на N+2 входов и 2^N+2 выходов. В случае построения дешифратора 4.3 используются только первые N выходов согласно таблице.

Элементы задержки: 19, 24. Являются линиями задержки (ЛЗ). Сигнал на выходе линии задержки воспроизводится с некоторой задержкой на определенный период времени t_p. ЛЗ может быть построена путем последовательного соединения одновходовых схем ИЛИ, каждая из которых для определенного базиса (серии микросхем) имеет время задержки 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 ≤ A_Tнг+Δ_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) не меняется от наблюдения к наблюдению, то выборочное распределение числа серий в последовательность является случайной величиной со средним значением и дисперсией


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

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

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

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

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

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-разрядным выходом селектора серий.