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

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

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

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

Рассмотрим пример. На рис. 3.24 представлена схема регистра отличающаяся от схемы, приведенной на рис. 3.14, следующим. Во-первых, каждый триггер на рис. 3.24 схематично разделен вертикальной линией на две половины. С выхода одной половины снимается прямой символ х, с выхода другого — его инверсия х. Прямой и инверсный символы удовлетворяют условию

Если инверсный символ то это означает, что прямой символ Во-вторых, на схему совпадения И поступают инверсные символы со всех триггеров ( кроме последнего. На выходе схемы И символ 1 появится только тогда, когда инверсные символы триггеров принимают значение 1. При любых других комбинациях инверсных символов триггеров на выходе схемы И будет символ 0. В-третьих, в схеме включен дополнительный сумматор по на входы которого поступают символы со схемы И и сумма символов цепи обратной связи регистра. Так как цепь обратной связи замкнута, то в схеме возможны колебания. Можно показать, что в триггере будут иметь место все кодовые комбинации длиною символов, в том числе и комбинация

Рис. 3.24. Регистр с нелинейной обратной связью

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

Необходимо отметить, что в нелинейных последовательностях вида (3.59) число символов 1 и 0 за период равно друг другу.

В отличие от М-последовательностей сумма двух сдвинутых нелинейных последовательностей не является циклически сдвинутой относительно исходно нелинейной последовательностью. Действительно, если просуммировать последовательность (3.59) с последовательностью, сдвинутой относительно нее, например, на три такта, то получим

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

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

Рис. 3.25. Автомат формирования нелинейных последовательностей

Она построена на том же принципе, что и схемы на рис. 3.17, 3.24. Схема И является схемой совпадения единиц, т. е. на выходе схемы И символ 1 проявляется тогда, когда на всех ее входах единицы. При этом

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

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

где

— операция символического умножения, выполняемая схемой И.

Используя (3.60), нелинейное рекуррентное уравнение (3.61) можно записать как

Нелинейность уравнений (3.61), (3.62) приводит к тому, что непосредственный анализ состояний регистра сопряжен с большими математическими трудностями. Иногда анализ состояний регистра не требуется, поскольку выбор структуры регистра (рис. 3.25) можно производить на основе теории М-последовательностей.

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

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

Рис. 3.26. АКФ нелинейной (а) и М-последователыюсти (б)

АКФ. На рис. 3.26, а изображена КФ нелинейной последовательности для На этом рисунке для области изображена периодическая АКФ, для области непериодическая.

На рис. 3.26, б изображены АКФ периодической нелинейной последовательности с периодом

Как видно из рисунков, боковые пики периодических АКФ нелинейных последовательностей значительно отличаются от Для сравнения на рис. представлена АКФ .М-последовательности, период которой имеет вид . Несмотря на разницу в периоде в один символ 0, автокорреляционные свойства нелинейных периодических последовательностей, с точки зрения уровня боковых пиков значительно хуже, чем М-последовательностей. Это является следствием того, что сумма двух нелинейных последовательностей не является циклически сдвинутой нелинейной последовательностью.

Вместе с тем, необходимо отметить, что до настоящего

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