Генераторы М-последовательности.

⇐ ПредыдущаяСтр 3 из 9Следующая ⇒

При соответствующем выборе коэффициентов α _i на основании характеристического полинома (1.2). который должен быть неприводимым и примитивным, последовательность имеет максимальную длину, равную . Такая последовательность называется M-последовательностью. Неприводимым называется такой многочлен φ (x) степени m, который не делится ни на какой другой многочлен от пониженной степени. Характеристический полином φ (x) будет примитивным в том случае, если полином делится на полином φ (x) только при . При этом необходимо, чтобы начальное состояние регистра сдвига не было нулевым, так как в противном случае генерируемая последовательность будет состоять из одних нулей, что соответствует тривиальному нулевому циклу генератора.

Основная задача синтеза генератора ПС—последовательности максимальной длины это нахождение многочлена φ (x), удовлетворяющего условию примитивности и неприводимости. Известно, что для данного m существует Ф(L)/m примитивных различных и неприводимых полиномов, где Ф(L)—функция Эйлера. Поскольку с ростом m число Ф(L) быстро увеличивается, то соответственно возрастает и количество многочленов φ (x) степени m, порождающих М—последовательности. Среди этого множества можно отыскать полиномы, имеющие наименьшее число нулевых членов. Данный случай характерен для минимальной конфигурации ГПСЧ, где в состав цепи ОС входит наименьшее число сумматоров по модулю два.

Необходимо отметить, что для формирования М–последовательности наряду с примитивным неприводимым полиномом φ (x) может использоваться и обратный ему . Получаемая в этом случае последовательность максимальной длины будет инверсна по отношению к последовательности, порождаемой φ (х).

Так как нулевое состояние регистра ГПК является запрещенным, максимально возможное число состояний устройства, а значит, и максимально возможная длина формируемой двоичной последовательности, снимаемой с выхода любого из триггеров, равны 2^m-1. В этом случае диаграмма состояний генератора состоит из одного тривиального цикла и цикла максимальной длины 2^m – 1.

В качестве примера построим генератор M-последовательностей для порождающего полинома j (x)=x⁴Å x³Å 1. В соответствии с (1.3а) и (1.3б) для рассматриваемого примера имеем

. (1.5)

Для построения одноканального генератора М-последовательности получим систему логических уравнений:

(1.6)

На рис.1.3 изображена схема генератора М-последовательности для полинома в соответствии с системой логических уравнений (1.6), а в табл.1.1 представлена последовательность смены состояний регистров сдвига при начальном состоянии A(0)=1000. Регистр сдвига реализован на D-триггерах, состояния которых изменяются по приходу на С-входы тактовых импульсов.

Рис.1.3

Таблица 1.1

№ такта	а₁	а₂	а₃	а₄	Выход

Из табл.1 следует, что длина формируемой последовательности равна 15, т.е. через 15 тактов регистр устанавливается в начальное состояние.

Перейдём к рассмотрению свойств последовательностей максимальной длины.

1. Период М–последовательности, формируемый в соответствии с выражением

, k = 0, 1, 2, 3, ...,

где а_k? {0, 1}–символы последовательности; α _i? {0, 1}–коэффициенты, определяемые примитивным неприводимым порождающим полиномом φ (х), для которого m=deg φ (х), равен 2^m -1

2. Для заданного φ (х) существует L различных М—последовательностей, сдвинутых относительно друг друга.

3. Число единичных символов на периоде М—последовательности равно 2^m^-1, а нулевых—2^m^-1-1. Вероятности появления 1 и 0 определяются выражениями

;

и при увеличении m достигают значений сколь угодно близких к 0, 5.

4. В псевдослучайной последовательности максимальной длины серии из одного символа (1 или 0) встречаются 2^m^-2 раз, из двух единиц или нулей 2^m^-3 и т.д. Серии из m-1 нулей и m единиц встречаются лишь по одному разу. Сравнивая выражения для оценки вероятности появлении серий из l одинаковых символов, можно убедиться в их практической эквивалентности.

5. Для каждого целого s(l≤ s< L) существует такое целое r≠ s (l≤ r< L), что {a_i}Å {a_i-s}={a_i-r}. Данное свойство обычно называют свойством сдвига и сложения.

6. Автокорреляционная функция М–последовательности определяется выражением

7. Децимацией последовательности {a_i} по индексу q(q=1, 2, 3, …) называется формирование новой последовательности {bi} из q—х элементов {a_i}, т.е. b_k=a_kq. Если {b_i} является нулевой последовательностью, то она порождается полиномом ψ (х), и имеет период L/(L, q), где (L, q)наибольший общий делитель L и q. При (L, q)=1период {b_i} равен L=2^m-1, где m=deg φ (х), и децимация называется собственной или нормальной.

Результатом всякой нормальной децимации является М–последовательность периода L, порождаемая примитивным неприводимым полиномом ψ (х). При этом если децимация выполняется над последовательностью, сдвинутой на j тактов относительно исходной {a_i}, то получаемая последовательность будет также сдвинутой на некоторое число j тактов по сравнению с {bi}. Иначе говоря, независимо от того, какой именно сдвиг последовательности, порождаемой полиномом φ (х), выбран, результатом ее всегда оказывается М–последовательность, порождаемая полиномом ψ (х). В частности, при децимации характеристической М—последовательности {a_i}*, порождаемой многочленом φ (х), получается также характеристическая последовательность {b_i}*, соответствующая полиному ψ (х).

Рассмотрим несколько разновидностей М—последовательностей, формируемых в результате нормальных децимаций. Поскольку децимация по индексу q будет давать тот же результат, что и децимация по q(mod L), ограничимся q≤ L. Прежде всего, очевидно, что децимация по единичному индексу будет равна исходной последовательности b_k=a_k*l=a_k. Результатом децимации характеристической последовательности по индексу 2 будет исходная характеристическая последовательность b_k*=a_2k*=a_k*. Следовательно, для произвольной последовательности {a_i} существует такое n, при котором ее децимация {a_i} по индексу 2 равна сдвигу на n тактов a_k₂=a_k_-n. Отсюда следует, что характеристическая последовательность {a_i}* есть результат сдвига исходной {a_i} на 2*n тактов, a*_k=a*_k_-2n. Тогда, поскольку для любого s a*₂_k^s=a_k, справедливо равенство a_2k^s=a_k_-r, где величина сдвига r зависит от s. В общем случае М—последовательность периода L может быть сформирована из исходной посредством ее децимации по нечетному индексу q.

Среди децимации по четному индексу выделяют случай q=L-1, при котором b_k=a_k_(l_-1)=a_-k. Иными словами, последовательность {b_i} является инверсной к {a_i} и порождается полиномом ψ (х), обратным к φ (х), ψ (х)=φ (х).

Данное свойство это тест, который позволяет различать М—последовательности и последовательности случайных двоичных цифр. Пусть а₀, а₁, …, а_n_-1—сегмент М–последовательности периода L=2^m-1, где n< L. Составим матрицу:

где m< b< n/2. ранг данной матрицы меньше величины b, что следует из наличия линейной зависимости между символами М—последовательности. С другой стороны, если а₀а₁…а_n_-1—последовательность равновероятных двоичных случайных цифр, то вероятность того, что rang(M)< b, не превышает 2²^b^-n^-1 и при соответствующем выборе b и n оказывается весьма незначительной величиной.

Таким образом, вопрос rang(M)< b? является тестом, с помощью которого по ограниченному числу элементов М—последовательности можно показать, ее отклонение от абсолютной случайности. Например, при m=11, L=2^m-1=2047 и b=15 для М—последовательности rang(M)< b, начиная с n=50, тогда, как вероятность получить такой же результат для случайной последовательности не превышает 2^-21.

Многоканальные генераторы М-последовательностей.

Если последовательность состояний регистра сдвига представить как последовательность m—мерных векторов А=(a1, a2, …am), где an? {0, 1}, n=1, m то преобразование, осуществляемое схемой в некотором к–ом такте работы, можно записать в матричной форме:

(1.7)

или в более компактном виде

, (1.8)

где

(1.9)

Таким образом, при последовательном применении выражения (2.6), можно определить состояние регистра сдвига генератора в произвольный последующий такт работы:

, (1.10)

где s – это величина сдвига.

⇐ Предыдущая 1 234 5 6 7 8 9 Следующая ⇒