Нелинейные последовательности

 

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

В качестве оценки непредсказуемости нелинейных ПСП принимают длину эквивалентного РСЛОС или эквивалентную степень∙k характеристического полинома (2.35) и называют её эквивалентной линейной степенью (ЭЛС) ПСП. Для М-последовательности ЭЛС равна ∙k, а для нелинейных ПСП ЭЛС может достигать значения , т.е. периода ПСП, что обеспечивает непредсказуемость нелинейных ПСП.

Алгоритм синтеза эквивалентного РСЛОС по известному принятому сегменту ПСП называют алгоритмом Берлекэлепа-Месси [7], ускоренный алгоритм реализации которого требует операций.

Однако, в отличие от М – последовательностей сумма двух сдвинутых нелинейных последовательностей не является циклически сдвинутой относительно исходной нелинейной последовательности. Это свойство нелинейных последовательностей приводит к росту боковых пиков КФ по сравнению с М – последовательностями.

В настоящее время известны следующие нелинейные ПСП [5]:

1. Последовательности де Брейна, генерируемые РС с нелинейной обратной связью (рис.2.11 а).

 

 

Рис.2.11. Схемы формирования нелинейных ПСП.

 

2. Последовательности, формируемые применением нелинейной внешней логики для комбинирования символов РСЛОС и имеющие период (длину) N = (2^k-1) (риc.2.11 б).

3. Составные нелинейные ПСП, формируемые чередованием символов с выходов двух и более РСЛОС по определенному правилу (рис.2.11 в).

а). Последовательности де Брейна имеют максимально возможный период N = 2^k и большой ансамбль сигналов

(2.58)

и высокую непредсказуемость, определяемую ЭЛС:

, (2.59)

 

которая зависит от способа формирования ПСП.

При этом эти ПСП приближаются по статистическим свойствам к СП (нормальное распределение блоков в последовательности, сбалансированность «1» и «0» в периоде).

Наиболее простым является способ генерации последовательности де Брейна на основе РСЛОС формирования М-последовательности (рис.2.6). При этом в цепи обратной связи используется дополнительная нелинейная цепь в виде схемы совпадения «И», на входы которой поступают сигналы с инверсных выходов l -ых триггеров РС, а выход подключен к входу триггера Т₁ (рис.2.12) через дополнительный сумматор.

T₁ T₂ T₃ T _{k -1} T _k

x_0,j x_1,j x_2,j x_3,j x_k-1,j x _{k ,j}

 

	X		X		X		X		X		X

 

C₁ C₂ C₃ C_k-2 C_k-1 С_k

 

 

 

Рис.2.12. Схема формирования нелинейной ПСП де Брейна.

 

Нелинейная ПСП содержит все возможные комбинации (полный код)

длительностью , включая нулевую.

Прямой символ на входе l -го триггера на j +1 такте равен и символ на входе первого триггера на j-м такте равен:

, (2.60)

где .

Используя очевидного равенство для выходов триггера можно из (2.60) получить аналогично (2.33) нелинейное рекуррентное уравнение формирования ПСП (для символа на входе Т₁ в j -м такте) в виде:

. (2.61)

Хотя последовательность де Брейна, построенная данным способом, обладает ЭЛС=(2 ^k -1), многие авторы оспаривают эту цифру. Считают, что вся ПСП определяется также по 2k известным символам (не содержащим состояния из k нулей), т.к. она повторяет структуру М-последовательности. Общее число последовательностей ПСП для данного способа (сравни с (2.37)) равно:

(2.62)

Другие способы построения ПСП де Брейнаможно найти в [5].

Отметим, что нелинейные ПСП де Брейна целесообразно использовать в качестве синхронизирующих, например, в ШСС. Эти ПСП имеют хорошие периодические АКФ (ровное плато около главного пика R(0) и минимальное значение боковых пиков ).

 

б). Последовательности, формируемые нелинейной внешней логикой. ЭЛС характеристического полинома ПСП является мерой сложности эквивалентного РС и определяется числом корней характеристического полинома. Увеличить их число можно внешним нелинейным комбинированием символов с выходов триггеров РСЛОС генератора М-последовательности.

К росту ЭЛС генерируемой нелинейной ПСП в наибольшей степени приводит операция умножения символов, выполняемая схемой «И», но

ухудшаются условие сбалансированности кода и КФ, а ЭЛС равно:

, (2.63)

где - число операций умножения символов РСЛОС, производимых нелинейной внешней логикой; а k - число каскадов РСЛОС.

При n → k, ЭЛС→ к значению 2 ^k-1.

В [6] для формирования нелинейных ПСП с асимптотически оптимальными корреляционными свойствами предложена нелинейная функция комбинирования бент-функция (максимально нелинейная), имеющая равномерный спектр коэффициентов при разложении в дискретный ряд Уолша - Адамара. При этом функция комбинирования символов реализуется в след-ортогональном базисе, используя идентичное бент-функции след-ортогональное преобразование степенного базиса поля GF (2 ^k), формируемого РСЛОС. В результате выходные бент-последовательности могут быть синтезированы для четных и имеют период N =2 ^k -1, причем сбалансированы по числу «1» и «0» и имеют 3-х уровневые АКФ и ВКФ со значениями, не превышающими (2^k/2+1), что в раз меньше, чем у кодов Голда. Число нелинейных операций комбинирования определяет ЭЛС ПСП:

. (2.64)

 

в). Составные нелинейные последовательности

Составными (комбинированными) называют последова тельности, формируемые чередованием символов с выходов нескольких РСЛОС.

Простейший алгоритм формирования составной нелинейной ПСП – это перемножение символов с выходов двух РСЛОС, что соответствует перемножению элементов поля GF(2 ^k) первого РСЛОС на элементы поля GF(2 ^т) второго РСЛОС и получению элементов поля GF(2 ^kт).

При этом порядок ЭЛС = kт, а период составной нелинейной ПСП равен НОК (N₁ =2^k -1, N₂ =2^m -1).

Однако, при этом нарушается условие сбалансированности кода (умножение ведет к росту числа «0») и, соответственно, ухудшаются корреляционные характеристики.

Для обеспечения сбалансированности кода составной ПСП известны разные способы «перемешивания» символов с выходов РСЛОС [6,8]. Например, Дженнингс предложил [5] алгоритм чередования символов с выходов РСЛОС, который формирует ансамбль составных ПСП, удовлетворяющих большинству вышеприведенных требований и реализуется схемой рис.2.13 на основе мультиплексора, управляемого регистром RG2.

RG1 и RG2: –два РСЛОС с n и m каскадами соответственно. Обозначим их через А и В соответственно.

Рис.2.13. Схема формирования составной ПСП.

 

Алгоритм формирования нелинейной ПСП можно записать в следующем виде:

1.Выбирается целое k, 1≤ k ≤ m, такое что 2 ^k -1≤ п, причем если

2 ^m -1 ≤ п, то k = т.

2. Выбирается произвольно k каскадов задержки RG1 и, на каждый момент t_i, двоичное k состояние преобразуется в десятичное число:

,

причем если .

3. Выбирается отображение

Порядок поступления символов RG1 на выход генератора ПСП

т.е. в качестве элемента чередования символов RG1 используется мультиплексор, управляемый RG2.

Период составной ПСП при этом число единиц и нулей в периоде, а ЭЛС при k = m равна

. (2.65)

При этом среднеквадратическое значение уровня боковых пиков АКФ

 

. (2.66)

 

Если n >> m, то большинство боковых пиков АКФ

(2.67)

Однако, отдельные боковые пики, расположенные на позициях,

кратных могут превышать это значение.

Таким образом составные нелинейные ПСП обладают большой ЭЛС, хорошими характеристиками КФ и имеют более широкие возможности по генерации.

С другими алгоритмами генерации нелинейных ПСП, например, Касами – подобными нелинейными ПСП, студент может ознакомиться самостоятельно, используя литературу [6,7] и др. источники.

 

Псевдослучайные числовые последовательности

 

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

Наиболее известными вычислительными алгоритмами являются [12] целочисленный конгруэнтный алгоритм Лемера и семейство алгоритмов Фибоначчи.

Алгоритм Лемера:

(2.75)

 

где х₀ , а, с – заданные целые числа, (причем х₀ , а, с < M, а в качестве М взято некоторое большое число).

Алгоритмы Фибоначчи (алгоритмы с запаздыванием):

(2.76)

где а_i, b_j равны нулю или 1; N_z - параметр запаздывания, - некоторый оператор, учитывающий фазовые соотношения между запаздывающими членами.

Случай соответствует обобщенному генератору Фибоначчи:

, (2.77)

где параметр N_z - определяет число заданных (или вычисленных ранее) членов последовательности, которые надо хранить в памяти устройства, чтобы найти новый член ПСП на каждом следующим шаге алгоритма;

а_п-i - коэффициенты, которые обычно считают равными нулю или 1. Классический алгоритм Фибоначчи учитывает только два члена ряда: вычисленный на предыдущем шаге (п -1) и вычисленный на шаге (п - N_z).

Размерность фазового пространства (ФП) динамической системы определяется числом величин, которые надо задать, чтобы однозначно описать её состояние и иметь возможность найти состояние системы на следующем шаге вычисления. Очевидно, что размерность ФП динами-ческой системы, описываемой алгоритмом с запаздыванием, определяется параметром запаздывания N_z.

В силу ограниченности ФП алгоритма, заданного на конечном интер-вале [1, М ] целых чисел, общее число всех состояний счетно и конечно. Поэтому, начиная с некоторого шага, результаты вычисления обязательно повторят ранее полученные значения, т.е. система выйдет на цикл, период которого зависит от начальных условий.

Для разработчика представляют интерес задачи исследования

зависимости этих циклов (периодов) и максимальных периодов ПСП,

определяющих помехозащищенность системы, от изменения интервала

[1, М ] чисел, на котором задан алгоритм, и параметра запаздывания N_z, т.е. размерности ФП. Авторы [12] исследовали указанные выше задачи для алгоритма типа Фибоначчи формирования ПСП целых чисел { x_n } на заданном интервале [1, М ] с параметром запаздывания N_z:

 

x_n = x_n-1 + x_n-Nz, (2.78)

 

где величина суммы x_n при вычислениях может быть меньше или равна 2 М и выходит за верхнюю границу М области определения алгоритма. Поэтому этот алгоритм может быть дополнен оператором возвращения в указанный интервал [1, М ], который реализует механизм перемешивания вычисленных чисел ПСП с определенным распределением вероятностей.

Авторами использован оператора возвращения - «сшивание» концов интервала, т.е. превышение разности (x_n – М) над величиной М прибавляется к величине нижней границы интервала, т.е. x_n = x_n – М.

Для вычисления значений ПСП, формируемой этим алгоритмом, необходимо задать параметры М, N_z и массив памяти (вектор запаз-дывания) , т.е. ряд начальных значений, состоящий из N_z целых чисел на интервале [1, М ]. ФП такой системы имеет размерность и состоит из совокупности точек с координатами из интервала чисел [1, М ], однозначно определяющих состояние системы.

Результаты исследования состояний динамической системы в ФП для данного алгоритма и более простого двумерного случая: N_z = 2 и М = 8 представлены на рис.2.16.

Рис.2.16. Последовательность состояний динамической системы в двумерном ФП для параметров алгоритма: М =8, N_z =2. Фазовые траектории циклов: с периодом Т (1)_8,2=3 (треугольники), Т (2)_8,2 = 6 (кружочки), Т (4)_8,2 = 12 (квадратики).

 

Эти результаты позволяют выявить следующие общие закономерности формируемых ПСП этим алгоритмом для случая больших размерностей N_z и значений М:

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

2. Как правило, при заданных М и N_z, в ФП существует несколько различных циклов одинакового периода. Они отличаются совокупностью точек ФП. Число циклов с одинаковым периодом обозначим через ν: Т(ν)_{М, Nz}. Например, на рис.2.16 Т (2)_8,2 = 6 означает, что при М =8, N_z =2 в ФП существует два цикла с периодом равным 6.

3. При любых М и N_z точка, все координаты которой равны М, является изолированной, что следует из формулы (2.78) и операции возврата.

4. Точка с координатами (1,1,…1) при любых М и N_z всегда лежит на цикле с максимальным периодом. Точки (1,1,…1) и (М, М,…М) являются особенными во всем ФП.

5. Сумма точек состояний в ФП динамической системы по всем циклам всегда равна полному объему ФП: . На рис.2.16 показаны три из 8 существующих фазовых траекторий (ФТ): Т (1)_8,2=3; Т (2)_8,2=6; Т (4)_8,2=12, а объем ФП равен 64, что совпадает с суммой точек по всем ФТ с учетом особой точки: (1+2+2×6+4×12=64).

Отметим, что ФТ при размерности ФП > 3 можно изучать только по их проекциям на соответствующие двумерные плоскости ФП рис.2.16.

Исследования также показали, что когда число М является не простым, а имеет сомножители, то ФТ ПСП воспроизводит ФТ сомножителей в большем масштабе и с тем же периодом. Кроме того, максимальный период ПСП растет при увеличении М, но не монотонно, т.к. не все простые числа М обеспечивают достижение максимального периода, т.е. простое число М не является для этого достаточным условием.

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