Лекция No.5.ССКРК

переводится в конечное множество S с помощью сравнения по модулю р. Умножение двух чисел по модулю р записывается как ab = d ≡ r (mod p ) , при

0 ≤ r ≤ p − 1 . Например, если a = 2, b = 4, то d = 8 и для р = 5 8 ≡ 3(mod 5) , т. е.

число 8, которого нет в множестве S, переводится в число 3.

Отметим, что каждая строка и столбец таблицы состоят из всех возможных символов множества S и не содержат, за исключением нулевого столбца и строки, одинаковых символов. Это является следствием того, что в качестве модуля р взято простое число 5. Если р — составное число, то при умножении в одной строке или столбце могут оказаться одинаковые числа, т. е. операция умножения не будет однозначной. Для сохранения однозначности в качестве модуля берут простые числа.

Отметим, что умножение любого числа на нуль означает, что символ на выходе умножителя всегда равен нулю. Это эквивалентно разрыву цепи между выходом триггера и сумматором. Следовательно, умножитель может быть опущен. Например, при р = 2 (символы 0 и 1) множитель cl может принимать значение или 0, или 1, т. е. выходы триггеров или подсоединены к сумматорам, или нет. После умножения суммирование производится также по модулю р. Сумма двух целых чисел переводится с помощью сравнения в конечное множество 5, т. е. a + b = d ≡ r (mod p ) для 0 ≤ r ≤ p − 1 . Следовательно,

в результате операций умножения и сложения получаются только элементы множества S.

Возвращаясь к работе сдвигающего регистра (см. рис, 2.3.3), можно записать, что символ на входе Т1 в j-м такте равен

Выражение (2.11) является линейным рекуррентным уравнением. Оно позволяет по известным k символам на выходах триггеров найти символ x0,j, который в последующем такте перейдет на выход Т1.

Анализ работы цифрового автомата формирования М-последовательности на основе рекуррентного уравнения (2.11) показывает, что работа этого автомата полностью определяется характеристическим многочленом

коэффициенты которого связаны с множителями с1, …, сk следующим соотношением:

Отрицательные значения сп (2.13) можно свести с помощью сравнения пo mod р к положительному числу множества S.

11

Для двоичных М-последовательностей, состоящих из символов 0 и 1 (р = 2), множители сп и коэффициенты ап согласно (2.13) равны, т. е. cn = an

причем a0 = c0 = 1 .

Таким образом, для определения структуры цифрового автомата необходимо знать характеристический многочлен степени k. Из теории М-последовательностей известно, что характеристический многочлен f(x) степени k, во-первых, должен быть неприводимым, т. е. его нельзя представить в виде произведения многочленов меньших степеней, а вовторых, он должен быть первообразным (примитивным) относительно двучлена xN—1, т. е. характеристический многочлен f(x) (2.13) должен делить xN—1 без остатка. Поэтому характеристический многочлен является первообразным корнем уравнения xN—1. Если характеристический многочлен является первообразным, то он является и неприводимым.

Таким образом, чтобы при заданных N, k и р определить структуру регистра для формирования М-последовательности с периодом N = pk — 1, необходимо в качестве характеристического многочлена взять первообразный многочлен степени k. В таблице 3.9 книги «Системы связи с шумоподобными сигналами» Варакин Л.Е. приведены характеристические многочлены, порождающие М-последовательности.

12