Способ автоматического обнаружения периодичности в цифровом потоке

Способ автоматического обнаружения периодичности в цифровом потоке

Иллюстрации

Показать все

Реферат

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

В совокупности признаков заявляемого способа используются следующие термины:

Цифровой поток (ЦП) - последовательность двоичных символов, получаемых с выхода демодулятора из канала связи.

Цифровой групповой сигнал (ЦГС) - цифровой поток, представляющий собой объединенные методом временного мультиплексирования (уплотнения) сигналы нескольких источников.

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

Сетевой сканер - аппаратное, программное или программно-аппаратное средство анализа цифрового потока в сети (системе) передачи данных.

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

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

В настоящее время известен ряд способов обнаружения периодичности в цифровом потоке.

Наиболее распространенный в настоящее время способ обнаружения периодичности на основе сравнения с эталоном описан в [Мультиплексоры передачи данных / Корчинский А.И., Булычев А.Ф., Голубцов А.Р. и др./ Под общ.ред. В.С.Лапина и А.И.Корчинского. - М.: Энергия, 1980] и предназначен для установления факта того, что в анализируемом канале связи для передачи используется стандартизованная аппаратура мультиплексирования, одной из характеристик которой является значение синхрокомбинации. То есть существует фиксированный набор описаний параметров цифрового сигнала для n различных типов оборудования. Описание, как правило, включает в себя конкретный вид синхрокомбинации S и значение Т периодичности, на которой она повторяется. В наблюдаемом цифровом потоке производится поиск синхрокомбинации S_i известного i-го мультиплексора, i=1,2,...,n. Если комбинация найдена, то выбирается Т_ij - минимально возможная длина кадра для этого мультиплексора, j - номер возможной длины кадра для данного мультиплексора, т.е. предполагается, что выбранная длина является реальной длиной кадра для данной реализации. Затем проверяется наличие комбинации S_i через T_ij бит. Если комбинация обнаружится в нескольких подряд следующих кадрах, то принимается решение, что обнаружены истинные значения синхрокомбинации и длины кадра. В противном случае выбирается следующая длина кадра. Затем выбирается следующая синхрокомбинация и перебираются все возможные для нее длины кадра пока не обнаружится несколько совпадений синхрокомбинации. Таким образом принимается решение об обнаружении периодичности и идентификации типа мультиплексора.

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

Известен способ обнаружения периодичности в ЦГС с помощью корреляционного метода [Варакин Л.Е. Системы связи с шумоподобными сигналами. - М.: Радио и связь, 1985], который состоит в следующем. Характеристикой, которая определяет взаимосвязь между отдельными участками двоичными последовательностями сигнала, является автокорреляционная функция (АКФ):

где j=0(1)N-1; x_i∈{0, 1},

N - длина анализируемой двоичной последовательности,

- оператор совпадения (несовпадения) двоичных символов двоичной последовательности.

АКФ характеризует близость (меру сходства) двоичной последовательности и ее сдвинутой во времени копии. Максимум значения АКФ наблюдается в случае, когда сдвиг j становится равным значению T периодичности цифрового группового сигнала, на основании чего принимается решение об обнаружении периодичности и вычисления ее значения. Одним из способов получения такой копии является использование циклического регистра сдвига.

Недостатком данного способа-аналога является недостаточная достоверность обнаружения периодичности, обусловленная особенностями сигналообразования ЦГС, а именно наличием кадрово-пакетных структур (передачи с использованием процедур HDLC, SDLC, BSC, вокодерные передачи). Наличие процедуры вставки флаговых комбинаций между передаваемыми кадрами на канальном уровне сетевого обмена обуславливает низкую чуствительность данного метода для обнаружения периодичности в ЦГС.

Наиболее близким по своей технической сущности к заявляемому способу является эвристический (ручной визуальный) способ, представлющий собой поиск повторений в массиве данных с помощью программы-визуализатора. Визуализатор (visualizer, viewer; синонимы: вьювер, просмотровщик, жарг. вьюер) - программное средство, предназначенное для визуализации данных. Примером программы-визуализатора может служить программный продукт типа Quick View, поставляемых с операционной системой Windows для просмотра дампов данных и описанный в [Основы современных компьютерных технологий. /Под редакцией А.Хомоненко - Учебное пособие. С-Пб: "Корона-Принт", 1998 г. - 448 с.].

Способ-прототип включает разрезание ЦП специальной программой-визуализатором на блоки длины t и формирование из этих блоков матрицы, которая затем выводится на экран в виде светлых и темных точек (пикселей), соответствующих значениям битов цифрового потока 0 и 1. Последовательно изменяя длину блока t, оператор добивается того, что длина блока t становится равной периоду последовательности (длине кадра, суперкадра и др.), что проявляется в появлении на экране вертикальных линий, составленных из точек одного цвета. Это обусловлено тем, что при правильно подобранном значении t в матрице находятся столбцы, составленные только из нулей или только из единиц в соответствии с видом синхрокомбинации.

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

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

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

Рассмотрим более подробно шаги способа обнаружения периодичности в цифровом потоке (ЦП), представленном двумерным изображением.

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

Каждый структурный элемент изображения, если он присутствует при текущем значении t в соответствии со своим сдвигом характеризуется углом наклона θ на изображении, как это представлено на фиг.2.

2. На втором шаге способа решается задача распознавания СЭИ на каждом из сформированных изображений ЦП. Для решения этой задачи используется подход, основанный на преобразованиях систем координат Хоха (Hough). Основная идея преобразований Хоха [Hough and P.V.C. Methods and Means for Recognizing Complex Patterns. U.S. Patent 3,069,654, 1962] (см. фиг.3) состоит в следующем. Прямую линию (фиг.3,а) можно описать в параметрической форме в виде уравнения:

где ρ - расстояние, измеренное от начала координат по нормали к прямой, а θ - угол наклона этой нормали относительно оси х.

Преобразование Хоха, примененное к прямой линии, дает точку на плоскости с полярными координатами ρ, θ (фиг.3,б). Множество прямых, проходящих через общую точку в декартовой системе координат (X, Y) (фиг.4,а), отображается в совокупность точек в полярной системе координат (ρ, θ) (фиг.4,б). И наоборот, в свою очередь, каждой точке пространства (ρ, θ) соответствует набор точек (х, у) на изображении, образующий прямую. Каждой точке (ρ₀, θ₀) пространства (ρ, θ) поставим в соответствие счетчик, соответствующий количеству точек плоскости (X, Y), лежащих на прямой xcosθ₀+ysinθ₀=ρ₀.

В случае, если есть несколько точек (х_i, y_i) на плоскости (X, Y), лежащих на прямой xcosθ₀+ysinθ₀=ρ₀, то соответствующие им кривые на плоскости (ρ, θ) должны проходить через точку (ρ₀, θ₀).

Проиллюстрируем это примером. Пусть дана прямая в декартовой системе координат. Возьмем три точки А(0; 1), В(0,5; 0,5), С(1; 0), лежащие на этой прямой (фиг.5а). Преобразование Хоха, примененное к семействам прямых, проходящих через эти точки, дает в результате совокупность трех кривых в полярной системе координат (ρ, θ). Из фиг.5.б видно, что эти кривые пересекаются в единственной точке с координатами (ρ₀, θ₀), которая соответствует прямой, проходящей через точки А, В, С.

Таким образом, обнаружение СЭИ будет выполняться следующим образом. Создается двумерный массив-накопитель на плоскости (ρ, θ) (квантование угла наклона θ осуществляется через 5 градусов) - С(ρ, θ). Будем считать, что начало координат находится в левом нижнем углу сформированного изображения. Для каждой точки изображения в декартовой системе координат соответствующая (квантованная) кривая заносится в массив С(ρ, θ) (с использованием процедуры преобразования Хоха, показанной выше) посредством увеличения содержимого соответственного элемента массива-накопителя в каждой клетке вдоль прямой на единицу. Точки, лежащие на одной прямой, создадут в результате большие числа в некоторых элементах массива-накопителя (моды в двухмерной гистограмме, отображаемой массивом). Пример сформированного массива-накопителя С(ρ, θ) приведен на фиг.6.

Значение счетчика в каждой из ячеек квантованной плоскости С(ρ, θ) интерпретируется как количество пикселей изображения искомого цвета, лежащих на прямой линии с данными параметрами ρ и θ.

Ввиду различной длины СЭИ - линий на изображении ЦП необходимо провести нормализацию полученного массива-накопителя:

где - количество пикселей изображения, находящихся на прямой линии под наклоном θ_i.

Далее производится поиск максимального элемента в нормализованном массиве-накопителе С_норм(ρ_i, θ_i). Для осуществления поиска используется процедура, основанная на алгоритме пузырьковой сортировки.

Правило принятия решения при распознавании СЭИ определено экспериментально и показано на фиг.7. Для гарантированного обнаружения СЭИ необходимо, чтобы обнаруженный максимум в двухмерной гистограмме, отображаемой массивом С_норм(ρ_i, θ_i), превышал значение 80, как это представлено на фиг.8 для обнаружения СЭИ под углом θ=45 градусов.

3. На третьем шаге производится проверка корректности функционирования процедуры обнаружения СЭИ на изображении ЦП посредством обнаружения СЭИ во втором (произвольно выбранном) фрагменте изображения ЦП, и если углы наклона θ₁, θ₂ обнаруженных СЭИ совпадут, то принимается решение, что СЭИ обнаружен.

Процедура проверки корректности обнаружения СЭИ на изображении ЦП иллюстрируется фиг.9. На фиг.9 видно, что если СЭИ обнаружен в 1 фрагменте изображения, то и во втором фрагменте изображения он будет присутствовать под тем же углом. То есть, θ₁=θ₂.

4. На четвертом шаге производится классификация обнаруженного СЭИ изображения табличным способом (табл.1). По обнаруженному углу наклона θ СЭИ - линии и значению свертки t, на котором осуществлялось формирование изображения ЦП, принимается решение об обнаруженном значении периодичности. Табл.1

Табл.1
θ	0	45	65	75	77	80	82	83	84	85	95	96	97	98	100	100	115	135
T	t	t+1	t+2	t+3	t+4	t+4	t+5	t+6	t+8	t+9	t-1	t-2	t-3	t-4	t-5	t-6	t-7	t-8

Иллюстрация четвертого шага представлена на фиг.10.

5. На пятом шаге в случае, если на данном значении свертки не удалось обнаружить СЭИ производится увеличение значения свертки t для формирования изображения ЦП и последующее распознавание СЭИ на полученном изображении, используя вышеперечисленную последовательность действий.

Правило выбора шага перебора в зависимости от предполагаемой горизонтальной ширины распознаваемого СЭИ приведено на фиг.11. Исходя из приведенной установленной зависимости и наиболее часто встречаемых значения ширины СЭИ, равной 8, рекомендуется шаг перебора установить равным 18.

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

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

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

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

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

1. Способ автоматического обнаружения периодичности в цифровом сигнале, согласно которому цифровой поток двоичных символов разрезают на блоки длины t, осуществляют преобразование Хоха (Hough) для указанного массива символов, определяют значение периода последовательности Т, отличающийся тем, что указанный массив символов представляют в виде двумерного бинарного изображения указанного цифрового потока, при проявлении на указанном изображении прямой линии, составленной только из 0 или только из 1, вычисляют угол наклона θ прямой линии, для определения значения периода последовательности Т используют соответствие

θ	45	65	75	77	80	82	83	84	85	95	96	97	98	100	100	115	135
Т	t+1	t+2	t+3	t+4	t+4	t+5	t+6	t+8	t+9	t-1	t-2	t-3	t-4	t-5	t-6	t-7	t-8

2. Способ по п.1, отличающийся тем, что преобразование Хоха включает создание двумерного массива счетчиков для каждой точки плоскости (ρ, θ), где ρ и θ интерпретируют как параметры прямой линии двумерного бинарного изображения, ρ - расстояние, измеренное от начала координат по нормали к прямой линии, θ - угол наклона этой нормали относительно оси х, при этом преобразования Хоха применяют к каждой точке указанного изображения, полученные в результате преобразования значения заносятся в двумерный массив счетчиков, при превышении значения в одном из счетчиков порогового значения принимают решение об обнаружении на указанном изображении прямой линии с углом наклона θ.