9.33. Последовательности, генерируемые регистрами сдвига с обратными связями

Наиболее известным (и самым простым) генератором ПСП является регистр сдвига с обратной связью (рис. 9.82). Регистр сдвига длины работает от тактовых импульсов с частотой .

Рис. 9.82. Генератор псевдослучайной двоичной последовательности.

Рис. 9.83.

Входная последовательность формируется с помощью вентиля ИСКЛЮЧАЮЩЕЕ ИЛИ, на вход которого поступают сигналы от и последнего разрядов регистра сдвига. Такая схема проходит через некоторое множество состояний (совокупность состояний регистра сдвига после каждого тактового импульса), которые после К тактов начинают повторяться, т. е. последовательность состояний является циклической с периодом К.

Максимальное число возможных состояний -разрядного регистра равно , т. е. числу -битовых двоичных комбинаций. Однако состояние «все нули» является «тупиком» для этой схемы, поскольку на выходе вентиля ИСКЛЮЧАЮЩЕЕ ИЛИ появляется 0, который вновь поступает на вход схемы. Таким образом, последовательность максимальной длины, которую может сформировать данная схема, содержит бит. Оказывается, что такую последовательность максимальной длины можно получить только при правильном выборе и , причем полученная последовательность будет псевдослучайной. (Критерием максимальной длины является неприводимость и примитивность многочлена над полем Галуа). В качестве примера рассмотрим -разрядный регистр сдвига с обратной связью, показанный на рис. 9.83. Начиная с состояния 1111 (можно было бы начать с любого другого состояния, за исключением 0000), можно записать состояния в порядке их следования:

Мы записали эти состояния как -разряд-ные числа QAQBQCQD. Здесь различных состояний, затем они повторяются вновь. Значит, это регистр максимальной длины.

Упражнение 9.6. Покажите, что -разрядный регистр с обратной связью от второго и четвертого разрядов не является регистром максимальной длины. Сколько существует различных последовательностей? Сколько состояний в каждой последовательности?

Отводы обратной связи.

Сдвиговые регистры максимальной длины можно выполнить с числом отводов в цепи обратной связи больше 2 (в этом случае используются несколько вентилей ИСКЛЮЧАЮЩЕЕ ИЛИ, соединенных в виде стандартного дерева четности, т. е. в виде суммы по модулю 2 нескольких разрядов). На самом деле, для некоторых значений регистр максимальной длины можно сделать только в том случае, когда число отводов будет больше 2. Ниже перечислены все значения до 40, для которых регистр максимальной длины реализуется с использованием ровно двух отводов, т.е. с обратной связью от (последнего) разрядов по типу регистра, приведенного ранее. Представлены также значения и длина цикла К по числу тактов. В некоторых случаях подойдут и другие значения и во всех случаях можно заменить на — ; таким образом, для предыдущего примера можно использовать отводы и .

Длина регистров сдвига обычно кратна 8 и, возможно, как раз такую длину вы захотите использовать. В этих случаях может потребоваться более двух отводов. Вот эти магические числа:

В ИМС (генератор шума) используется -разрядный регистр с отводом от разряда. Внутренний тактовый генератор обеспечивает работу на частоте около схема генерирует белый шум в диапазоне до (затухание ) с временем цикла около 1 мин. На рис. 7.61 эта ИМС была использована в схеме генератора «розового шума». При использовании -разрядного регистра, работающего на частоте 1 МГц, время цикла будет около . Время цикла -разрядного регистра, работающего на частоте 10 МГц, будет в миллион раз больше, чем возраст Вселенной!

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

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

1. В полном цикле (К тактов) число «1» на единицу больше, чем число «0». Добавочная «1» появляется за счет исключения состояния «все нули». Это свидетельствует о том, что «орлы» и «решки» равновероятны (дополнительная «1» большой роли не играет; -разрядный регистр будет вырабатывать 65 536 «1» и 65 535 «0» за один цикл).

2. В одном цикле (К тактов) половина серий из последовательных «1» имеет длину 1, одна четвертая серий - длину 2, одна восьмая - длину 3 и т.д. Такими же свойствами обладают и серии из «0» с учетом пропущенного «0». Это говорит о том, что вероятности «орлов» и «решек» не зависят от исходов предыдущих «подбрасываний» и поэтому вероятность того, что серия из последовательных «1» или «0» закончится при следующем подбрасывании равна 1/2 (вопреки обывательскому пониманию «закона о среднем).

3. Если последовательность полного цикла (К тактов) сравнить с этой же последовательностью, но циклически сдвинутой на любое число символов не является нулем или кратным К), то число несовпадений будет на единицу больше, чем число совпадений. Научно выражаясь, автокорреляционная функция этой последовательности представляет собой дельта-функцию Кронекера при нулевой задержке и равна - при любой другой задержке. Отсутствие «боковых лепестков» автокорреляционной функции - это как раз то свойство, которое делает ПСП очень полезными в радиолокационных системах.

Упражнение 9.7. Покажите, что последовательность, полученная с помощью -разрядного регистра сдвига (с отводами , удовлетворяет этим свойствам. В качестве «выхода» возьмите QA: 100010011010111.