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

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

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

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

Действительно, математическая суть метода половинного деления (дихотомии), используемого в известном устройстве, заключается в том, что с целью определения некоторого Δf(x) на отрезке [a, b], последний делится пополам и в его средней точке c= (a+b)/2 вычисляется значение f(c). Если f(c) = Δf(x), то для последующего деления пополам выбирается один из следующих двух отрезков [a, c] и [c, b] и т.д. [А.М. Прохоров и др. Математический энциклопедический словарь. М., Советская энциклопедия, 1988].

Указанная процедура реализована в уже описанном устройстве поиска требуемых информационных блоков в некотором массиве при условии:
K_тр/K_общ<1, (1)
где K_тр - количество искомых блоков в массиве;
K_общ - общее количество блоков в массиве.

Пусть длина искомого блока - μ_тр. При этом, μ_тр< μ, где μ - длина элементарной анализируемой реализации (базы анализа) в массиве объема S. В этом случае количество секторов поиска K определяется [В.А.Абчук, Ф.А.Матвейчук, Л.П.Томашевский. Справочник по исследованию операций, М., Воениздат, 1979]:

Следовательно, можно представить:

где T - общее время поиска в массиве;
γ - скорость поиска;
Tμ = T_{перестр.}+T_{анализа} - время, необходимое для анализа одного сектора.

Для дихотомического метода:
(2)
Т.е. указанное устройство - аналог требует значительных временных затрат при заданной вероятности правильного решения.

Ближайшее устройство поиска информации (прототип) к предлагаемому описано в авторском свидетельстве Российской Федерации N 2116670, МПК⁶ G 06 F 17/30, заявленном 07.04.97.

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

Информационные входы формирователя сигналов текущей оценки и дискриминатора зон значений оценки объединены и являются информационным входом устройства. Первый выход распределителя импульсов подключен ко входам синхронизации формирователя сигналов текущей оценки и дискриминатора зон значений оценки, а также к тактовому входу счетчика временных интервалов. Второй и четвертый выходы распределителя импульсов подключены соответственно к тактовым входам коммутатора и классификатора. Третий выход распределителя импульсов подключен к тактовым входам первого и второго блоков памяти. Выход таймера текущих суток подключен ко входам "Время" распределителя импульсов, формирователя сигналов текущей оценки, дискриминатора зон значений оценки и блока изменения пороговых сигналов. Выходы значений порогов поиска "П_в" и "П_н" блока изменения пороговых сигналов подключены к одноименным входам регистра стратегии поиска. Выходы значений верхнего и нижнего порогов классификации "П_клВ" и "П_клН" регистра стратегии поиска подключены к соответствующим входам классификатора, у которого выходы изменения состояния обстановки "П" и отсутствия изменения состояния обстановки "О" подключены к соответствующим входам блоков индикации и формирователя сигналов сброса. Выход формирователя сигналов сброса подключен ко входам "Сброс" первого и второго блоков памяти, счетчика временных интервалов и регистра стратегии поиска. Вход номера текущего временного интервала "N_текщ" регистра стратегии поиска соединен с выходом счетчика временных интервалов. Выход первого формирователя переменной поиска подключен к первому информационному входу первого суммирующего счетчика, второй информационный вход которого подключен к выходу первого блока памяти. Выход первого суммирующего счетчика соединен с информационным входом первого блока памяти и первым информационным входом блока деления. Выход блока деления соединен с информационным входом классификатора. Выход второго суммирующего счетчика подключен одновременно ко второму информационному входу блока деления и информационному входу второго блока памяти. Выход второго блока памяти соединен со вторым информационным входом второго суммирующего счетчика, первый информационный вход которого подключен к выходу второго формирователя переменной поиска. Информационный вход второго формирователя переменной поиска соединен с выходом отсутствия изменения состояния обстановки "О" коммутатора. Выход изменения состояния обстановки "П" коммутатора соединен с информационным входом первого формирователя переменной поиска. Входы количества интервалов разбиения значений изменения состояния обстановки "Зона 1" и количества интервалов разбиения значений отсутствия изменения состояния обстановки "Зона 2" устройства являются входами количества интервалов разбиения значений состояния обстановки "Зона" соответственно первого и второго формирователей переменной поиска. Вход управления коммутатора подключен к выходу формирователя сигналов текущей оценки. Входы коммутатора изменения состояния обстановки "П" и отсутствия изменения состояния обстановки "О" подключены к соответствующим выходам дискриминатора зон значений оценки. Входы "Порог" и "Пуск" устройства соединены с одноименными входами блока изменения пороговых сигналов. Входы значений порогов поиска "П_в" и "П_н" блока формирования порога усечения подключены к одноименным выходам блока изменения пороговых сигналов. Входы максимального номера временного интервала "N_max" первого и второго формирователей переменной поиска, а также регистра стратегии поиска являются одноименным входом устройства.

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

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

Целью предлагаемого изобретения является построение устройства, обладающего более высокой скоростью поиска информации при заданной вероятности правильного решения за счет уточнения значения максимального номера временного интервала - "N_max", адекватно характеристике входного информационного потока на протяжении всего времени работы устройства. Объектом распознавания для предлагаемого устройства является состояние обстановки на основании оценки входного трафика, рассматриваемого как информационный массив, в котором присутствуют некоторые детерминированные кодовые комбинации (в данном случае это комбинации начала сообщения - КНС). Именно по КНС оценивается интенсивность входного трафика и, как следствие, состояние обстановки. В дальнейшем этим состояниям соответствуют обозначения "О" - изменения отсутствуют и "П" - изменения присутствуют. Решение о состоянии "П" принимается в случае, когда интенсивность входного трафика имеет отклонение от среднего значения в большую или меньшую сторону на величину, превышающую пороговое, в противном случае принимается решение о состоянии "О". В свою очередь верхнее и нижнее значения порогов могут быть либо интервальными, либо точечными, что определяется стратегией поиска, принятой в устройстве поиска на данном этапе.

Поставленная цель достигается тем, что в известном устройстве поиска информации, включающем распределитель импульсов, первые и вторые формирователи переменной поиска, суммирующие счетчики и блоки памяти, регистр стратегии поиска, формирователь сигналов текущей оценки, дискриминатор зон значений оценки, счетчик временных интервалов, коммутатор, блок деления, классификатор, блок изменения пороговых сигналов, таймер текущих суток, блок индикации и формирователь сигналов сброса, информационные входы формирователя сигналов текущей оценки и дискриминатора зон значений оценки объединены и являются информационным входом устройства, первый выход распределителя импульсов подключен ко входам синхронизации формирователя сигналов текущей оценки и дискриминатора зон значений оценки, а также к тактовому входу счетчика временных интервалов, второй и четвертый выходы распределителя импульсов подключены соответственно к тактовым входам коммутатора и классификатора, а третий выход распределителя импульсов подключен к тактовым входам первого и второго блоков памяти, выход таймера текущих суток подключен ко входам "Время" распределителя импульсов, формирователя текущей оценки, дискриминатора зон значений оценки и блока изменения пороговых сигналов, выходы значений порогов поиска которого "П_в" и "П_н" подключены к одноименным входам регистра стратегии поиска, выходы значений верхнего и нижнего порогов классификации которого "П_клВ" и "П_клН" подключены к соответствующим входам классификатора, у которого выходы изменения состояния обстановки "П" и отсутствия изменения состояния обстановки "О" подключены к соответствующим входам блоков индикации и формирователя сигналов сброса, выход которого подключен ко входам "Сброс" первого и второго блоков памяти, счетчика временных интервалов и регистра стратегии поиска, вход номера текущего временного интервала "N_текщ" которого соединен с выходом счетчика временных интервалов, выход первого формирователя переменной поиска подключен к первому информационному входу первого суммирующего счетчика, второй информационный вход которого подключен к выходу первого блока памяти, а выход первого суммирующего счетчика соединен с информационным входом первого блока памяти и первым информационным входом блока деления, выход которого соединен с информационным входом классификатора, выход второго суммирующего счетчика подключен одновременно ко второму информационному входу блока деления и информационному входу второго блока памяти, выход которого соединен со вторым информационным входом второго суммирующего счетчика, первый информационный вход которого подключен к выходу второго формирователя переменной поиска, информационный вход которого соединен с выходом отсутствия изменения состояния обстановки "О" коммутатора, выход изменения состояния обстановки "П" которого соединен с информационным входом первого формирователя переменной поиска, входы количества интервалов разбиения значений изменения состояния обстановки "Зона 1" и количества интервалов разбиения значений отсутствия изменения состояния обстановки "Зона 2" устройства являются входами количества интервалов разбиения значений состояния обстановки "Зона" соответственно первого и второго формирователей переменной поиска, вход управления коммутатора подключен к выходу формирователя сигналов текущей оценки, а входы изменения состояния обстановки "П" и отсутствия изменения состояния обстановки "О" коммутатора подключены к соответствующим выходам дискриминатора зон значений оценки, входы "Порог" и "Пуск" устройства соединены с одноименными входами блока изменения пороговых сигналов, дополнительно введен блок формирования порога усечения.

Входы значений порогов поисков "П_в" и "П_н" блока формирования порога усечения подключены к одноименным выходам блока изменения пороговых сигналов. Входы "Пуск", "Порог" блока формирования порога усечения подключены к одноименным входам устройства. Входы максимального номера временного интервала "N_max", числового значения единицы "1" и объема выборки интервала анализа "V_выб" блока формирования порога усечения являются одноименными входами устройства. Входы номера текущего временного интервала "N_текщ", "Сброс" и информационный блока формирования порога усечения соединены с выходами соответственно счетчика временных интервалов, формирователя сигналов сброса и блока деления. Входы максимального номера временного интервала "N_max" первого и второго формирователей переменной поиска, а также регистра стратегии поиска подключены к выходу блока формирования порога усечения.

Блок формирования порога усечения состоит из первого, второго, третьего, четвертого и пятого ключей, первого и второго четырехвходовых ключей, схемы ИЛИ, первого и третьего сумматоров, первого и второго устройств деления, первого и второго компараторов, регистра, первого, второго и третьего вычитателей, RS-триггера, суммирующего счетчика, дешифратора. Вход номера текущего временного интервала "N_текщ" блока соединен одновременно с информационными входами первого ключа и первого компаратора. Вход "Сброс" блока соединен одновременно с управляющим входом первого ключа и входом начальной установки регистра, а также с тактовым входом суммирующего счетчика. Выход первого ключа соединен с входом первого слагаемого первого сумматора, вход второго слагаемого которого соединен с выходом регистра. Выход первого сумматора соединен одновременно с информационными входами регистра и второго ключа, управляющий вход которого соединен с выходом дешифратора. Вход объема выборки интервала анализа "V_выб" блока соединен одновременно с информационными входами суммирующего счетчика и пятого ключа, выход которого соединен со входом делителя первого устройства деления. Вход "Пуск" блока соединен одновременно с входом "Установка О" RS-триггера и входом "Разрешение загрузки" суммирующего счетчика, выход которого соединен со входом дешифратора, выход которого соединен одновременно с управляющим входом пятого ключа и со входом "Установка 1" RS-триггера. Выход второго ключа соединен со входом делимого первого устройства деления, выход которого соединен одновременно с информационными входами третьего и четвертого ключей и с пороговым входом первого компаратора, выходы равно "-" и меньше "<" которого соединены с управляющими входами соответственно третьего и четвертого ключей. Выход третьего ключа соединен со входом первого слагаемого второго сумматора, вход второго слагаемого которого соединен с выходом третьего сумматора. Выходы второго сумматора и четвертого ключа соединены соответственно с первым и вторым входами схемы ИЛИ, выход которой соединен с первым информационным входом второго четырехвходового ключа. Вход максимального номера временного интервала "N_max" блока соединен со вторым информационным входом второго четырехвходового ключа, первый и второй управляющие входы которого соединены соответственно с прямым и инверсным выходами RS-триггера. Вход значения порога поиска "П_в" блока соединен со входом уменьшаемого первого вычитателя, выход которого соединен одновременно с информационным входом второго компаратора и первым информационным входом первого четырехвходового ключа. Информационный вход блока соединен одновременно со входами вычитаемого первого и третьего вычитателей и уменьшаемого второго вычитателя. Вход значения порога поиска "П_н" блока соединен со входом вычитаемого второго вычитателя, выход которого соединен одновременно с пороговым входом второго компаратора и со вторым информационным входом первого четырехвходового ключа, первый и второй управляющие входы которого соединены соответственно с выходами меньше "<" и больше ">" второго компаратора. Вход "Порог" блока соединен со входом уменьшаемого третьего вычитателя, выход которого соединен со входом делителя второго устройства деления. Выход первого четырехвходового ключа соединен со входом делимого второго устройства деления, выход которого соединен со входом первого слагаемого третьего сумматора, вход второго слагаемого которого соединен со входом числового значения единицы "1" блока. Выход второго четырехвходового ключа является выходом блока.

Благодаря такой совокупности блоков и их соединений достигается возможность увеличения скорости поиска информации, которое является следствием сокращения общего времени поиска T при различном процентном соотношении K_тр к K_общ при условии равной вероятности правильного распознавания за счет того, что значение максимального номера временного интервала - "N_max" корректируется на протяжении всего интервала анализа адекватно входному информационному потоку.

Проведенный анализ уровня техники позволил установить, что аналоги, характеризирующие совокупность признаков, тождественных всем признакам заявленного технического решения, отсутствуют, что указывает на соответствие заявленного устройства условию патентоспособности "новизна". Результаты поиска известных решений в данной и смежных областях техники с целью выявления признаков, совпадающих с отличительными от прототипа признаками заявленного объекта, показали, что они не следуют явным образом из уровня техники. Из уровня техники также не выявлена известность влияния предусматриваемых существенными признаками заявленного изобретения преобразований на достижение указанного технического результата. Следовательно, заявленное изобретение соответствует условию патентоспособности "изобретательский уровень".

Заявленное устройство поясняется чертежами:
фиг. 1 - общая схема устройства поиска информации;
фиг. 2 - блок формирования порога усечения.

Устройство поиска информации, показанное на фиг. 1, содержит формирователь сигналов текущей оценки 1, дискриминатор зон значений оценки 2, распределитель импульсов 3, счетчик временных интервалов 4, коммутатор 5, первый 6 и второй 7 формирователи переменной поиска, первый 8 и второй 9 суммирующие счетчики, первый 10 и второй 11 блоки памяти, блок деления 12, классификатор 13, регистр стратегии поиска 14, формирователь сигналов сброса 15, блок индикации 16, блок изменения пороговых сигналов 17, таймер текущих суток 18, блок формирования порога усечения 19.

Информационные входы формирователя сигналов текущей оценки 1 и дискриминатора зон значений оценки 2 объединены и являются информационным входом устройства. Первый выход распределителя импульсов 3 подключен ко входам синхронизации формирователя сигналов текущей оценки 1 и дискриминатора зон значений оценки 2, а также к тактовому входу счетчика временных интервалов 4. Второй и четвертый выходы распределителя импульсов 3 подключены соответственно к тактовым входам коммутатора 5 и классификатора 13. Третий выход распределителя импульсов 3 подключен к тактовым входам первого 10 и второго 11 блоков памяти. Выход таймера текущих суток 18 подключен ко входам "Время" распределителя импульсов 3, формирователя сигналов текущей оценки 1, дискриминатора зон значений оценки 2 и блока изменения пороговых сигналов 17. Выходы значений порогов поиска "П_в" и П_н" блока изменения пороговых сигналов 17 подключены к одноименным входам регистра стратегии поиска 14. Выходы значений верхнего и нижнего порогов классификации "П_клВ" и "П_клН" регистра стратегии поиска 14 подключены к соответствующим входам классификатора 13, у которого выходы изменения состояния обстановки "П" и отсутствия изменения состояния обстановки "О" подключены к соответствующим входам блоков индикации 16 и формирователя сигналов сброса 15. Выход формирователя сигналов сброса 15 подключен ко входам "Сброс" первого 10 и второго 11 блоков памяти, счетчика временных интервалов 4 и регистра стратегии поиска 14. Вход номера текущего временного интервала "N_текщ" регистра стратегии поиска 14 соединен с выходом счетчика временных интервалов 4. Выход первого формирователя переменной поиска 6 подключен к первому информационному входу первого суммирующего счетчика 8, второй информационный вход которого подключен к выходу первого блока памяти 10. Выход первого суммирующего счетчика 8 соединен с информационным входом первого блока памяти 10 и первым информационным входом блока деления 12. Выход блока деления 12 соединен с информационным входом классификатора 13. Выход второго суммирующего счетчика 9 подключен одновременно ко второму информационному входу блока деления 12 и информационному входу второго блока памяти 11. Выход второго блока памяти 11 соединен со вторым информационным входом второго суммирующего счетчика 9, первый информационный вход которого подключен к выходу второго формирователя переменной поиска 7. Информационный вход второго формирователя переменной поиска 7 соединен с выходом отсутствия изменения состояния обстановки "О" коммутатора 5. Выход изменения состояния обстановки "П" коммутатора 5 соединен с информационным входом первого формирователя переменной поиска 6. Входы количества интервалов разбиения значений изменения состояния обстановки "Зона 1" и количества интервалов разбиения значений отсутствия изменения состояния обстановки "Зона 2" устройства являются входами количества интервалов разбиения значений состояния обстановки "Зона" соответственно первого 6 и второго 7 формирователей переменной поиска. Вход управления коммутатора 5 подключен к выходу формирователя сигналов текущей оценки 1. Входы изменения состояния обстановки "П" и отсутствия изменения состояния обстановки "О" коммутатора 5 подключены к соответствующим выходам дискриминатора зон значений оценки 2. Входы "Порог" и "Пуск" устройства соединены с одноименными входами блока изменения пороговых сигналов 17. Входы значений порогов поиска "П_в" и "П_н" блока формирования порога усечения 19 подключены к одноименным выходам блока изменения пороговых сигналов 17. Входы "Пуск", "Порог" блока формирования порога усечения 19 подключены к одноименным входам устройства. Входы максимального номера временного интервала "N_max", числового значения единицы "1" и объема выборки интервала анализа "V_выб" блока формирования порога усечения 19 являются одноименными входами устройства. Входы номера текущего временного интервала "N_текщ", "Сброс" и информационный блока формирования порога усечения 19 соединены с выходами соответственно счетчика временных интервалов 4, формирователя сигналов сброса 15 и блока деления 12. Входы максимального номера временного интервала "N_max" первого 6 и второго 7 формирователей переменной поиска, а также регистра стратегии поиска 14 подключены к выходу блока формирования порога усечения 19.

Блок формирования порога усечения, показанный на фиг. 2, вырабатывает новое значение максимального номера временного интервала "N_max" по окончании текущего интервала анализа, которое является адекватным характеристикам потока, поступающего на информационный вход устройства. Новое значение максимального номера временного интервала "N_max" поступает с выхода блока формирования порога усечения 19 на входы максимального номера временного интервала "N_max" первого 6 и второго 7 формирователей переменной поиска, а также регистра стратегии поиска 14. Блок формирования порога усечения 19 состоит из первого 19.1, второго 19.3, третьего 19.6, четвертого 19.10 и пятого 19.12 ключей, первого 19.19 и второго 19.13 четырехвходовых ключей, схемы ИЛИ 19.8, первого 19.2, второго 19.7 и третьего 19.21 сумматоров, первого 19.4 и второго 19.20 устройств деления, первого 19.5 и второго 19.18 компараторов, регистра 19.9, первого 19.15, второго 19.16 и третьего 19.17 вычитателей, RS-триггера 19.14, суммирующего счетчика 19.11, дешифратора 19.22. Вход номера текущего временного интервала "N_текщ" блока 19 соединен одновременно с информационными входами первого ключа 19.1 и первого компаратора 19.5. Вход "Сброс" блока 19 соединен одновременно с управляющим входом первого ключа 19.1 и входом начальной установки регистра 19.9, а также с тактовым входом суммирующего счетчика 19.11. Выход первого ключа 19.1 соединен с входом первого слагаемого первого сумматора 19,2, вход второго слагаемого которого соединен с выходом регистра 19.9. Выход первого сумматора 19.2 соединен одновременно с информационными входами регистра 19.9 и второго ключа 19.3, управляющий вход которого соединен с выходом дешифратора 19.22. Вход объема выборки интервала анализа "V_выб" блока 19 соединен с информационными входами суммирующего счетчика 19.11 и пятого ключа 19.12, выход которого соединен со входом делителя первого устройства деления 19.4. Вход "Пуск" блока 19 соединен одновременно с входом "Установка О" RS-триггера 19.14 и входом "Разрешение загрузки" суммирующего счетчика 19.11, выход которого соединен со входом дешифратора 19.22, выход которого соединен одновременно с управляющим входом пятого ключа 19.12 и со входом "Установка 1" RS-триггера 19.14. Выход второго ключа 19.3 соединен со входом делимого первого устройства деления 19.4, выход которого соединен одновременно с информационными входами третьего 19.6 и четвертого 19.10 ключей и с пороговым входом первого компаратора 19.5, выходы равно "=" и меньше "<" которого соединены с управляющими входами соответственно третьего 19.6 и четвертого 19.10 ключей. Выход третьего ключа 19.6 соединен со входом первого слагаемого второго сумматора 19.7, вход второго слагаемого которого соединен с выходом третьего сумматора 19.21. Выходы второго сумматора 19.7 и четвертого ключа 19.10 соединены соответственно с первым и вторым входами схемы ИЛИ 19.8, выход которой соединен с первым информационным входом второго четырехвходового ключа 19.13. Вход максимального номера временного интервала "N_max" блока 19 соединен со вторым информационным входом второго четырехвходового ключа 19.13, первый и второй управляющие входы которого соединены соответственно с прямым и инверсным входами RS-триггера 19.14. Вход значения порога поиска "П_в" блока 19 соединен со входом уменьшаемого первого вычитателя 19.15, выход которого соединен одновременно с информационным входом второго компаратора 19.18 и первым информационным входом первого четырехвходового ключа 19.19. Информационный вход блока 19 соединен одновременно со входами вычитаемого первого 19.15 и третьего 19.17 вычитателей и уменьшаемого второго вычитателя 19.16. Вход значения порога поиска "П_н" блока 19 соединен со входом вычитаемого второго вычитателя 19.16, выход которого соединен одновременно с пороговым входом второго компаратора 19.18 и со вторым информационным входом первого четырехвходового ключа 19.19, первый и второй управляющие входы которого соединены соответственно с выходами меньше "<" и больше ">" второго компаратора 19.18. Вход "Порог" блока 19 соединен со входом уменьшаемого третьего вычитателя 19.17, выход которого соединен со входом делителя второго устройства деления 19.20. Выход первого четырехвходового ключа 19.19 соединен со входом делимого второго устройства деления 19.20, выход которого соединен со входом первого слагаемого третьего сумматора 19.21, вход второго слагаемого которого соединен со входом числового значения единицы "1" блока 19. Выход второго четырехвходового ключа 19.13 является выходом блока 19.

Остальные элементы и блоки заявленного устройства известны и, в частности, описаны в патенте РФ N 2116670, МПК⁶ G 06 F 17/30, заявленном 07.04.97. Назначение блоков и элементов заявленного устройства следующее.

Формирователь сигналов текущей оценки 1 по окончании текущего интервала анализа вырабатывает двоичный сигнал, характеризующий состояние обстановки. Сигнал этот принимает значения "П" или "О". Схема формирователя 1 известна и описана на фиг. 2 патента РФ N 2116670.

Дискриминатор зон значений оценки 2 вырабатывает сигнал о номере зоны того состояния, в котором находится входной поток соответствующей интенсивности. Схема дискриминатора 2 известна и описана на фиг. 3 патента РФ N 2116670.

Распределитель импульсов 3 предназначен для синхронизации работы всего устройства посредством формирования четырех импульсов последовательностей, сдвинутых друг относительно друга на некоторую величину Δt. Схема распределителя 3 известна и описана на фиг. 4 патента РФ N 2116670.

Коммутатор 5 осуществляет коммутацию сигнала о номере зоны на вход соответствующего формирователя переменной поиска по сигналу управления, поступающему от формирователя 1 и принимающему значения "П" и "О". Схема коммутатора 5 известна и описана на фиг. 5 патента РФ N 2116670.

Формирователи переменной поиска 6 и 7 предназначены для построения приращений апостериорных интегральных функций распределения вероятностей нормального F_о(N) (формирователь 6) и отклоненного F_п(N) (формирователь 7) состояния трафика на N-м интервале наблюдения. Схемы формирователей 6 и 7 идентичны. Схема формирователя 6 известна и описана на фиг. 6 патента РФ N 2116670.

Классификатор 13 вырабатывает сигнал "П" или "О" на основе сравнения входной информации с пороговыми значениями. Схема классификатора 13 известна и описана на фиг. 7 патента РФ N 2116670.

Регистр стратегии поиска 14 формирует интервальное либо точечное значение порогов классификации в зависимости от того, является ли номер интервала поиска предельным или нет. Схема регистра 14 известна и описана на фиг. 8 патента РФ N 2116670.

Блок изменения пороговых сигналов 17 предназначен для изменения значений пороговых сигналов в зависимости от времени суток. Схема была 17 известна и описана на фиг. 9 патента РФ N 2116670.

СЧЕТЧИКИ: 4, 19, 11. Суммирующий счетчик по модулю k = 2^m образуется путем соединения m триггеров. В качестве примера на рис. 10.4а [Гольденберг Л. М. Импульсные и цифровые устройства. Учебник для ВУЗов. М.: Связь. 1973, 496 с. ] приведена схема, состоящая из 4 каскадно соединенных триггеров. В таблице 10.4 того же учебника показаны состояния триггеров в зависимости от числа входных импульсов. Если на входе m-разрядного счетчика, состоящего из m последовательно соединенных триггеров, появилось в течение некоторого интервала времени n импульсов, причем:
N = n2^m + a_m 2^m-1 + a_m-12^m-2 + ... + a₁2⁰,
где

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

КОМПАРАТОРЫ: 19,5, 19,18. Компаратор выполняет операцию сравнения двух 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.

РЕГИСТР 19.9 и БЛОКИ ПАМЯТИ 10, 11 являются регистрами параллельного действия. Построение таких регистров из n входов и n выходов показано в [Шляпоберский В.И. Основы техники передачи дискретных сообщений. М.: Связь, 1973, 480 с.] на рис. 3.1., стр. 106. Указанные регистры используются также в качестве блоков памяти, хранящих один элемент (операнд) в течение одного интервала анализа.

СУММАТОРЫ 19.2, 19.7, 19.21 и СУММИРУЮЩИЕ СЧЕТЧИКИ 8, 9 являются арифметическими сумматорами. Сумматор (параллельный) строится аналогично рис. 14.17 стр. 377 [Основы импульсной и цифровой техники. Учебное пособие для ВУЗов. М.: Советское радио, 1975, 440 с.], где полусумматор показан на рис. 14.13, а полный сумматор - рис. 14.14.

ВЫЧИТАТЕЛИ: 19.15, 19.16, 19.17. Вычитатель строится на основе сумматора, на один вход которого подается уменьшаемое, на другой дополнение до единицы вычитаемого (отрицание вычитаемого - через схему НЕ - поразрядно складывается по модулю два с единицей).

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

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

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

ФОРМИРОВАТЕЛЬ СИГНАЛОВ СБРОСА представляет собой схему объединения сигналов "П" и "О", а также их усиления и согласования с последующими блоками. Может быть выполнен в виде двухвходовой схемы ИЛИ с повышенной нагрузочной способностью.

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

Для минимизации объема выборки применяется последовательная процедура выбора решения. При этом размер выборки не фиксируется, а ограничивается в процессе работы в зависимости от результата предшествующих наблюдений. Процедура принятия решения становится многошаговой. Вначале наблюдается одно значение случайной величины и по заранее установленному правилу либо прекращается наблюдение и принимается решение, либо наблюдение продолжается. Если правило предписывает отказ от решения, то оценивают следующую выборку. Испытание заканчивается на той же выборке, на основании которой наблюдение в соответствии с правилом остановки прекращается и принимается решение [В.В. Поповский. Математическое моделирование сложных систем. Л., ВАС, 1990].

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

Для устранения этого недостатка в предлагаемом устройстве применяется усечения последовательная процедура, при которой максимальный объем выборки ограничивается максимальным номером временного интервала числом N_max. При такой процедуре для всех N < N_max устанавливаются, как и для неусеченного правила, интервальные значения порогов, с которыми сравнивается отношение правдоподобия. Если размер анализируемой выборки достигает N_max, то устанавливаются точечные значения порогов, при которых в любом случае принимается решение, и цикл наблюдения повторяется. В свою очередь значения порогов изменяются в зависимости от времени суток, поскольку этот фактор определяет количественные показатели входного трафика. Варьирование пороговыми значениями сокращает время принятия решения при обеспечении заданных требований по вероятности ложной тревоги (α) и пропуска сигнала (β).
Состояние обстановки оценивается по интенсивности входного трафика на N+1 интервале наблюдения, которая определяется через интенсивность поступления комбинаций KHC. Степень интенсивности представляет собой информационный массив, разделенный на два класса "П" и "О", соответствующие оценкам "Присутствует" и "Отсутствует". Описанием класса состояний "П" является F_п(N) - эмпирическая интегральная функция распределения выборочных значений коэффициента разброса K_j, предшествующих оценкам "П"_N+1. Описание класса "О" является функция F_o(N), построенная по значениям K_j, предшествующим оценкам "О"_N+1.

Данными для статистических выводов являются случайные значения коэффициента разброса K_j, измеренные на некоторых интервалах времени t_N, где 1 < N < N_max [Э. Мушик, П. Мюллер. Методы принятия технических решений. М., Мир, 1990].

Задача анализа выборки сводится к усеченной последовательной процедуре принятия решения, при которой после каждого наблюдаемого интервала времени t_N вычисляется отношение правдоподобия:
L(N) = F_п(N)/F_o(N)
и величина L(N) сравнивается с нижним и верхним порогами классификации:
и
где α и β - заданные вероятности ложной тревоги и пропуска сигнала соответственно.

Входной информационный поток поступает на информационные входы формирователя сигналов текущей оценки 1 и дискриминатора зон значений оценки 2 (фиг. 1).

В формирователе 1 по окончании текущего интервала анализа вырабатывается двоичный сигнал, характеризующий состояние обстановки. При превышении отклонения числа КНС от среднего значения в верхнюю или нижнюю сторону больше порогового, на выходе формирователя 1 формируется сигнал "П", в других случаях вырабатывается сигнал "О". С выхода формирователя 1 сигнал "П" или "О" поступает затем на управляющий вход коммутатора 5.

В дискриминаторе зон значений оценки 2 вырабатывается сигнал о номере зоны того состояния, в котором находится входной поток соответствующей интенсивности. Этот номер зоны соответствует более точной оценке состояния обстановки по сравнению с оценкой, получаемой в формирователе сигналов текущей оценки 1. С выходов изменения состояния обстановки "П" или отсутствия изменения состояния обстановки "О" дискриминатора 2 сигнал соответственно "П" или "О" поступает на одноименный вход коммутатора 5.

Распределитель импульсов 3 осуществляют синхронизацию работы всего устройства посредством формирования четырех импульсных последовательностей, сдвинутых друг относительно друга на некоторую величину Δt.
Счетчик временных интервалов 4 осуществляет подсчет количества наблюдаемых интервалов времени и выдает комбинацию о номере временного интервала на входы номера текущего временного интервала "N_текщ" регистра стратегии поиска 14 и блока формирования порога усечения 19. Коммутатор 5, в соответствии с поступающим на него сигналом управления от формирователя 1, обеспечивает подключение сигнала о номере зоны состояния "П" или "О" соответственно на вход формирователя переменной поиска 6 или 7, где на основе сигнала о номере зоны K_j (1 < j < m), наибольшего номера зоны K_m и максимального числа наблюдений N_max производится построение приращений F_п(N) или F_o(N) эмпирических интегральных функций распределения вероятностей отклоненного и нормального состояния трафика на N-м интервале наблюдения:


В суммирующих счетчиках 8 и 9 производится сложение значений приращений F_п(N) и F_o(N) с соответствующими значениями эмпирической интегральной функции распределения, вычисленной за N-1 временной интервал F_п(N-1) и F_o(N-1), которые поступают с выходов блоков памяти 10 и 11:
F_п(N) = F_п(N-1) + F_п(N);
F_o(N) = F_o(N-1) + F_o(N).

Значение F_п(N) и F_o(N) поступают на входы блока деления 12 и на запись в первый 10 и второй 11 блоки памяти. Блок деления 12 осуществляет операцию арифметического деления
L(N) = F_п(N)/F_o(N)
и выдачу отношения правдоподобия на информационные входы классификатора 13 и блока формирования порога усечения 19.

Блок формирования порога усечения 19 (фиг. 2) вырабатывает новое значение N_max по окончании текущего интервала анализа, которое является адекватным характеристикам потока. Блок 19 работает следующим образом.

По сигналу "Сброс" ключ 19.1 передает на первый вход сумматора 19.2 значение N_текщ. Сумматор 19.2 суммирует значение N_текщ с предыдущей суммой, которая находится в регистре 19.9, и результат сложения поступает опять в регистр 19.9.

Суммирующий счетчик 19.11 подчитывает количество импульсов сигнала "Сброс" на заданном интервале усреднения, устанавливаемом сигналом "V_выб", и через дешифратор 19.22 формирует сигнал управления.

Устройство деления 19.4 формирует среднее значение N'_текщ делением суммы значений N_текщ на заданном интервале усреднения и значения V_выб, поступающих на его входы через ключи 19.3 и 19.12 по сигналу с дешифратора 19.22.

В компараторе 19.5 сравнивается очередное значение N_текщ с усредненным N'_текщ. Если эти значения равны, то открывается ключ 19.6 и значение N'_текщ поступает на первый вход сумматора 19.7. Если же значение N_текщ меньше, то открывается ключ 19.10 и значение N'_текщ поступает на второй вход схемы ИЛИ 19.8. RS-триггер 19.14 управляет работой четырехвходового ключа 19.13. По сигналу "Пуск" RS-триггер 19.14 открывает второй информационный вход четырехвходового ключа 19.13, на который со входа блока поступает сигнал "N_max". По сигналу с выхода дешифратора 19.22 RS-триггер 19.14 изменяет состояние и открывает первый информационный вход четырехвходового ключа 19.13.

Вычитатели 19.15 и 19.16 вычисляют разности (П_в - П_тек) и (П_тек-П_н) соответственно, которые поступают на информационный и пороговый входы компаратора 19.18 соответственно. Причем значения П_В, П_Н и П_тек поступают соответственно с входов значений порогов поиска "П_в", "П_н" и информационного блока 19. Если значение (П_в - П_тек) меньше (П_тек - П_н), то на входе делимого устройства деления 19.20 через четырехвходовый ключ 19.19 поступает результат с вычитателя 19.15, если же больше - с вычитателя 19.16. На вход делителя устройства деления 19.20 поступает модуль значения разности (П_тек - "Порог"). Результат деления с устройства деления 19.20 поступает на первый вход сумматора 19.21, который к этому значению прибавляет единицу, поступающую с входа числового значения единицы "1" блока 19. Результат сложения сумматора 19.21 поступает на вход второго слагаемого сумматора 19.7, результат сложения которого - N_нов ⁺ поступает на первый вход схемы ИЛИ 19.8. С выхода схемы 19.8 на первый информационный вход четырехвходового ключа 19.13 поступает либо значение N'_тек, либо N_нов ⁺.

С выхода четырехвходового ключа 19.13 новое значение N_max поступает на выход блока 19.

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

Таймер текущих суток 18 устанавливает время суток всего устройства.

Сигнал с выхода классификатора 13 подается на вход блока индикации 16 и формирователя сигналов сброса 15, с выхода которого сигнал "Сброс" подается на сброс счетчика 4, первый 10 и второй 11 блоки памяти, блок формирования порога усечения, а также регистр 14 для перевода их в исходное состояние.

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

Оценка повышения скорости поиска информации в предлагаемом устройстве проведена в Приложении.

Таким образом, полученные результаты позволяют сделать вывод о том, что предлагаемое устройство, в котором для поиска информации в массиве и ее оценки используется последовательная процедура с ограничениями по критерию Вальда, а также введен новый блок для уточнения значения N_max в процессе анализа, обеспечивает максимальный временной выигрыш для последовательного метода, который составит 40% при K_тр ---> K_об.

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

1. Устройство поиска информации, содержащее распределитель импульсов, первые и вторые формирователи переменной поиска, суммирующие счетчики и блоки памяти, регистр стратегии поиска, формирователь сигналов текущей оценки, дискриминатор зон значений оценки, счетчик временных интервалов, коммутатор, блок деления, классификатор, блок изменения пороговых сигналов, таймер текущих суток, блок индикации и формирователь сигналов сброса, информационные входы формирователя сигналов текущей оценки и дискриминатора зон значений оценки объединены и являются информационным входом устройства, первый выход распределителя импульсов подключен ко входам синхронизации формирователя сигналов текущей оценки и дискриминатора зон значений оценки, а также к тактовому входу счетчика временных интервалов, второй и четвертый выходы распределителя импульсов подключены соответственно к тактовым входам коммутатора и классификатора, а третий выход распределителя импульсов подключен к тактовым входам первого и второго блоков памяти, выход таймера текущих суток подключен ко входам Время распределителя импульсов, формирователя сигналов текущей оценки, дискриминатора зон значений оценки и блока изменения пороговых сигналов, выходы значений порогов поиска которого П_в и П_н подключены к одноименным входам регистра стратегии поиска, выходы значений верхнего и нижнего порогов классификации которого П_клВ и П_клН подключены к соответствующим входам классификатора, у которого выходы изменения состояния обстановки П и отсутствия изменения состояния обстановки 0 подключены к соответствующим входам блоков индикации и формирователя сигналов сброса, выход которого подключен ко входам Сброс первого и второго блоков памяти, счетчика временных интервалов и регистра стратегии поиска, вход номера текущего временного интервала N_текщ которого соединен с выходом счетчика временных интервалов, выход первого формирователя переменной поиска подключен к первому информационному входу первого суммирующего счетчика, второй информационный вход которого подключен к выходу первого блока памяти, а выход первого суммирующего счетчика соединен с информационным входом первого блока памяти и первым информационным входом блока деления, выход которого соединен с информационным входом классификатора, выход второго суммирующего счетчика подключен одновременно ко второму информационному входу блока деления и информационному входу второго блока памяти, выход которого соединен со вторым информационным входом второго суммирующего счетчика, первый информационный вход которого подключен к выходу второго формирователя переменной поиска, информационный вход которого соединен с выходом отсутствия изменения состояния обстановки 0 коммутатора, выход изменения состояния обстановки П которого соединен с информационным входом первого формирователя переменной поиска, входы количества интервалов разбиения значений изменения состояния обстановки Зона 1 и количества интервалов разбиения значений отсутствия изменения состояния обстановки Зона 2 устройства являются входами количества интервалов разбиения значений состояния обстановки Зона соответственно первого и второго формирователей переменной поиска, вход управления коммутатора подключен к выходу формирователя сигналов текущей оценки, а входы изменения состояния обстановки П и отсутствия изменения состояния обстановки 0 коммутатора подключены к соответствующим выходам дискриминатора зон значений оценки, входы Порог и Пуск устройства соединены с одноименными входами блока изменения пороговых сигналов, отличающееся тем, что дополнительно введен блок формирования порога усечения, входы значений порогов поиска П_в и П_н которого подключены к одноименным выходам блока изменения пороговых сигналов, входы Пуск, Порог блока формирования порога усечения подключены к одноименным входам устройства, входы максимального номера временного интервала N_max, числового значения единицы 1 и объема выборки интервала анализа V_выб блока формирования порога усечения являются одноименными входами устройства, входы номера текущего временного интервала N_текщ, Сброс и информационный блока формирования порога усечения соединены с выходами соответственно счетчика временных интервалов, формирователя сигналов сброса и блока деления, входы максимального номера временного интервала N_max первого и второго формирователей переменной поиска, а также регистра стратегии поиска подключены к выходу блока формирования порога усечения. 2. Устройство по п. 1, отличающееся тем, что блок формирования порога усечения состоит из первого, второго, третьего, четвертого и пятого ключей, первого и второго четырехвходовых ключей, схемы ИЛИ, первого, второго и третьего сумматоров, первого и второго устройств деления, первого и второго компараторов, регистра, первого, второго и третьего вычитателей, RS-триггера, суммирующего счетчика, дешифратора, вход номера текущего временного интервала N_текщ блока соединен одновременно с информационными входами первого ключа и первого компаратора, вход Сброс блока соединен одновременно с управляющим входом первого ключа и входом начальной установки регистра, а также с тактовым входом суммирующего счетчика, выход первого ключа соединен с входом первого слагаемого первого сумматора, вход второго слагаемого которого соединен с выходом регистра, выход первого сумматора соединен одновременно с информационными входами регистра и второго ключа, управляющий вход которого соединен с выходом дешифратора, вход объема выборки интервала анализа V_выб блока соединен с информационными входами суммирующего счетчика и пятого ключа, выход которого соединен со входом делителя первого устройства деления, вход Пуск блока соединен одновременно с входом Установка 0 RS-триггера и входом Разрешение загрузки суммирующего счетчика, выход которого соединен со входом дешифратора, выход которого соединен одновременно с управляющим входом пятого ключа и со входом Установка 1 RS-триггера, выход второго ключа соединен со входом делимого первого устройства деления, выход которого соединен одновременно с информационными входами третьего и четвертого ключей и с пороговым входом первого компаратора, выходы равно = и меньше < которого соединены с управляющими входами соответственно третьего и четвертого ключей, выход третьего ключа соединен со входом первого слагаемого второго сумматора, вход второго слагаемого которого соединен с выходом третьего сумматора, выходы второго сумматора и четвертого ключа соединены соответственно с первым и вторым входами схемы ИЛИ, выход которой соединен с первым информационным входом второго четырехвходового ключа, вход максимального номера временного интервала N_max блока соединен со вторым информационным входом второго четырехвходового ключа, первый и второй управляющие входы которого соединены соответственно с прямым и инверсным выходами RS-триггера, вход значения порога поиска П_в блока соединен со входом уменьшаемого первого вычитателя, выход которого соединен одновременно с информационным входом второго компаратора и первым информационным входом первого четырехвходового ключа, информационный вход блока соединен одновременно со входами вычитаемого первого и третьего вычитателей и уменьшаемого второго вычитателя, вход значения порога поиска П_н блока соединен со входом вычитаемого второго вычитателя, выход которого соединен одновременно с пороговым входом второго компаратора и со вторым информационным входом первого четырехвходового ключа, первый и второй управляющие входы которого соединены соответственно с выходами меньше < и больше > второго компаратора, вход Порог блока соединен со входом уменьшаемого третьего вычитателя, выход которого соединен со входом делителя второго устройства деления, выход первого четырехвходового ключа соединен со входом делимого второго устройства деления, выход которого соединен со входом первого слагаемого третьего сумматора, вход второго слагаемого которого соединен со входом числового значения единицы 1 блока, выход второго четырехвходового ключа является выходом блока.