Алгоритм определения периодичности в ЦП.

Для нахождения объема пакета в кадре определяют величину периодичности L в ЦП X = (x ₁, x ₂, …, x_N), где x – значение бита, N – объем ЦП. Для этого вычисляют АКФ [5]

, (1)

где x_h – значение h -го бита преобразованного ЦП; h – номер бита в ЦП; i = 0, 1, …, N – 1 – величина сдвига ЦП; b = h + i – номер бита с учетом сдвига ЦП. Преобразование исходного ЦП заключается в замене каждого бита со значением «0» на бит со значением «– 1». Это
позволяет получать значения АКФ [1]

(2)

Равенство в правой части (2) соответствует случаю, когда ЦП содержит одинаковые битовые последовательности на текущем шаге i сдвига, а равенство в левой части (2) – противоположные по значению последовательности.

В [5] предложено определять величину L как расстояние между соседними максимумами АКФ (1). При этом математическое обоснование не приведено. Поэтому предлагается следующий алгоритм определения величины L:

1. Вычисление глобального максимума АКФ.

2. Вычисление погрешности нахождения локальных максимумов АКФ.

3. Нахождение значений локальных максимумов АКФ.

4. Вычисление величины L.

5. Определение истинной величины L из полученных нескольких ее значений на основе уточненного математического описания метода суммирования.

Рассмотрим содержание данного алгоритма.

На этапе 1 задается значение первого локального максимума как Z _{XX m} (i) при i = 7 и m = 1. После этого глобальный максимум АКФ вычисляется по следующей формуле:

(3)

где i = 8, 9, …, N – 1; m = 2, 3, …, M – 1 – текущие номера локальных максимумов АКФ; M – номер, соответствующий глобальному максимуму Z _{XX max}(i). Каждое новое значение локального максимума Z _{XX m} (i), его номер m и значение сдвига i ЦП запоминаются.

Если найденное значение Z _{XX max}(i) получено для i _max = N – 1, то за истинное значение глобального максимума АКФ принимается значение последнего локального максимума Z _{XX M – 1}. Это связано с тем, что АКФ всегда имеет глобальный максимум при i = 0 и ее значения симметричны относительно N /2 [2].

На этапе 2 вычисляется погрешность Δ _Z определения локальных максимумов АКФ:

, (4)

если Z _{XX max}(i) получено для i = N – 1;

, (5)

если Z _{XX max}(i) получено для i < N – 1.

На этапе 3 из значений { Z _{XX m} (i)} выбираются те, которые соответствуют условию

, (6)

и далее составляется набор локальных максимумов АКФ.

На этапе 4 вычисляют значение периодичности

, (7)

т. е. как разность между значениями величины сдвига ЦП i_{m + 1} и i_m, которые соответствуют соседним локальным максимумам АКФ, имеющим номера m + 1 и m.

Однако для различных пар значений m периодичность L может иметь разные величины. Поэтому необходимо ввести погрешность Δ _i величины сдвига ЦП в формуле (1).

Исходя из известного требования к погрешности измерений (не более 30 %, если она не задана [5]), а также на основе проведенных экспериментальных исследований цифровых потоков передачи данных (ПД) была выбрана погрешность величиной 10 %:

(8)

В формуле (8) обозначение – математическая операция округления до наименьшего целого числа.

Полученные по (7) значения { L_j } (j = 1, 2, …, J) проверяют на соответствие условию

(9)

Значения L_j, для которых не выполняется условие (9), исключаются из набора { L_j }. Если условие (9) не выполняется для всех значений из набора { L_j }, то принимается решение, что ЦП не имеет периодичности.

При небольших выборках ЦП или наличии в нем битовых ошибок возникает неоднозначность в принятии решения об истинной величине L [5].

На этапе 5 уточняется значение L ЦП на основе метода суммирования [5]. Согласно приведенному в [5] вербальному описанию этого метода необходимо осуществить поиск комбинации бит постоянного вида в структуре ЦП на предполагаемом периоде. Поэтому предлагается вариант математического описания метода суммирования со следующими исходными данными:

значения { L_j } _J, вычисленные на основе формул (1) – (7);

диапазон значений сдвига ЦП от до с шагом 1 (номер j равен меньшему из двух номеров m, характеризующих локальные максимумы АКФ, по которым вычислено минимальное значение L_j).

На этапе 5.1 для каждого текущего значения L_j ЦП разбивается на фрагменты объемом L_j с последующим их построчным размещением друг под другом в виде матрицы

, (10)

где x_ng – биты ЦП; n = 1, 2, …, L_j; g = 1, 2, …, K_j;

– (11)

количество фрагментов объемом L_j в ЦП.

На этапе 5.2 для каждого столбца x _n матрицы вычисляется и запоминается среднее арифметическое значение [3]

, (12)

где n = 1, 2, …, L_j.

В формуле (12) суммирование бит осуществляется по правилу

. (13)

На этапе 5.3 после вычисления по формуле (12) значений { F (x _n)} подсчитывается в матрице (10) количество столбцов x _n, для которых F (x _n) = 1:

, (14)

а также количество столбцов x _n, для которых F (x _n) = 0:

. (15)

На этапе 5.4 вычисляется суммарное количество столбцов

(16)

и отношение

. (17)

Вычисленное значение H (L_j) для каждого L_j запоминается.

На этапе 5.5 выбирают значение L_j, соответствующее максимальной величине H (L_j), которое принимают за истинную периодичность ЦП.

Для поиска максимального значения H _max(L_j) из набора { H (L_j)} _J обозначим первую вычисленную по формуле (17) величину как H_e (L_j) при e = 1. Тогда

(18)

где j = 2, 3, …, J; e = 2, 3, …, E – 1 – текущие номера локальных максимумов отношения H (L_j); E – номер, соответствующий глобальному максимуму H _max(L_j).