Ипатов В. Широкополосные системы и кодовое разделение сигналов (2007) (1151883), страница 43

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 43)

На рис. 6.12, а представлена схема на основе РСЛОС, генерирующая бинарную последовательность примера 6.4. Отметим, что в случае бинарной поснедовательности умножение иа единицу означает попросту соединение разряда с сумматором. Рнс. 6.12, б иллюстрирует последовательную смену состояний ячеек регистра, а также состояния выхода обратной связи (точка ОС на схеме) при подаче тактовых импульсов. Генерируемая линейная последовательность считывается в виде последовательных состояний крайнего правого разряда. Результатом считывания состояний второго нли первого разряда является копия той же последовательности с опережением в один или два такта соответственно. б) а) Рмс. 6.12. Генератор бинарной последовательности (а) и таблица состояний (б) Поскольку число различных состояний регистра конечно (не более р"), неизбежна ситуация, когда после некоторого числа тактов уже наблюдавшееся состояние повторится вновь.

Однако, стартуя с некоторой начальной загрузки, т.е. фиксированного состояния РСЛОС, схема рис. 6.11 генерирует лишь единственную последовательность, определяемую (6.13). ~218 Г д.Ыд д д Следовательно, повторение какого-либо состояния регистра ведет к повторению всех последующих генерируемых символов, что означает периодичность (по крайней мере, после некоторого переходного процесса) любой линейной рекуррентной последовательности. Далее, как непосредственно видно из (6.13), если регистр окажется в нулевом состоянии (нули во всех разрядах)., все последующие символы будут также нулевыми, т. е. генерируемая линейная последовательность окажется вырожденной, состоящей только из нулей.

Понятно, что подобная последовательность практически бессмысленна, так что нулевое состояние регистра в процессе генерирования последовательности должно быть исключено. В итоге остается самое большее р" — 1 разрешенных состояний регистра, означая, что максимальный период (длина) линейной последовательности не может быть больше р" — 1. 6.6.3.т-последовательности Линейные рекуррентные последовательности, имеющие максимально возможный период Ь = р" — 1, играют особую роль в современных информационных технологиях и называются последовательностями максимальной длины или просто т-последовательностями. Будучи полностью детерминированными, они обладают многими свойствами, присущими случайным последовательностям типа последовательности исходов подбрасывания правильной монеты.

Следующие замечательные свойства являются ключевыми для понимания ценности т-последовательностей в плане построения кодов с хорошей автокорреляцией. 1. Свайспдво уравновепденноспди. На одном периоде р-ичной пп~оследовательности любой ненулевой элемент сдР(р) встречается р" 1 раз, тогда как нулевой — р" 1 — 1 раз. Для того чтобы убедиться в этом, достаточно заметить, что все возможные рв — 1 ненулевые состояния регистра должны быть пройдены в том или ином порядке в ходе генерирования одного периода т-последовательности, так как иначе период не будет максимальным.

Все эти состояния есть не что иное, как различные и-разрядные р-ичные числа из диапазона 1, 2,..., р" — 1, а т-последовательность, считываемая с крайней правой ячейки регистра, может трактоваться как последовательность цифр старшего разряда этих чисел. При пробегании диапазона 0,1,2,...,р" — 1 любая р-ичная цифра в любом конкретном разряде (например, старшем) повторяется точно рв рзз. Исключение из пробегаемого диапазона и-разрядного числа из одних нулей уменьшит на единицу только число повторений нуля в старшем (или любом другом разряде).

В частности, период бинарной (двоичной) т-последовательности памяти п составляет Ь = 2" — 1 и содержит ьв = 2" 1 — 1 нулей и Ьд = 2" 1 единиц. Легко видеть, например, что последовательность при- б.б. Н . д б д 2 б 9)) мера 6.4 является бинарной 9п-последовательностью длины Ь = 22 — 1 = 7, содержащей на периоде Ье = 22 — 1 = 3 нуля и Ь1 = 22 = 4 единицы.

Аналогично последовательность примера 6.5 есть троичная т-последовательность длины Ь = Зз — 1 = 26, имеющая на периоде 7 = 32 — 1 = 8 нулей и по Ь1 = Х2 = 3 = 9 элементов 1 и 2. 2. Любые две т-последовательности, генерируемые одной и той же рекурсией (6.13), отличаются друг от друга не более чем циклическим сдвигом. Действительно, поскольку при фиксированных и начальных элементах соотношение (6.13) полностью определяет последовательность, то две несовпадающие т-последовательности, формируемые заданной рекурсией, не могут иметь и абсолютно идентичных начальных элементов.

С другой стороны, на одном периоде т-последовательности содержатся все состояния РСЛОС, кроме нулевого, и после появления состояния, повторяющего начальную установку генератора одной последовательности в генераторе другой, вторая последовательность полностью повторит первую, оказавшись попросту некоторой ее задержанной репликой. 3. Свойство сдвига и еычитпаддил. Возьмем некоторую т-последовательность, заданную уравнением (6.13), и вычтем из нее поэлементно (разумеется„по модулю р) ее же копию, циклически сдвинутую на пд позиций пб+т = — Уа — 1д1+та — 1 — Уп — 2229-1-ж — 2 — ' — уел~-922 — и, где т — произвольное целое.

Результатом будет «2 — дб+пь = .дббб — 1(212-1 219+922-1) дбб2-2(219-2 Пбб-Ебдд-2) ' ' ' дбз(919 — 92 Пбб Ебдд-бд). Введя обозначение 21'; = 91; — дбььб„, придем к линейной рекуррентной последовательности, элементы о; 'которой определяются первоначальной рекурсией (6.14) Возможны лишь две взаимоисключающие ситуации. Предположим вначале, что сдвиг т равен целому числу периодов 7. Тогда 211 = сЦ и д'; = 0 для всех 1, т. е. последовательность, описываемая (6.14), состоит из одних нулей.

Пусть теперь тп не кратно Ь. Тогда 211 и д1+ не могут совпадать для всех 2 = О, 1,..., Т вЂ” 1, поскольку сдвинутая копия может полностью повторить исходную последовательность только при сдвиге, кратном периоду, что противоречит предположению. Тогда очевидно, что рекурсия (6.14), полностью повторяющая (6.13), генерирует некоторую ненулевую последовательность. Однако, согласно предыдущему свойству, если рекурсия (6.13) или, что эквивалентно, соответствующая схема рис. 6.11 генерирует ти-последовательность, стартуя с некоторого определенного начального состояния, то никакой другой ненулевой последовательности, кроме сдвинутой копии той же самой т-последовательности, она при другом начальном состоянии сгенерировать не может. Мы таким образом приходим к заключению: поэлементное вычитание двух сдвинутых копий одной и той же т-последовательности дает либо нулевую последовательность, если взаимный сдвиг кратен периоду, либо некоторую новую сдвинутую копию исходной тп-последовательности в противном случае.

Для двоичных последовательностей вычитание равносильно сложению, благодаря чему рассмотренное свойство нередко упоминается как свойство сдввга и сложения. Возвратившись к примеру 6.4, можно видеть, что сложение полученной в нем последовательности с ее сдвинутой на две позиции влево копией 0,1,0,1,1,1,0,0,1,0,1,1,1,0,... даетпоследовательность 1,1,0,0,1,0,1,1,1,0,0,1,0, 1,..., которая является копией исходной, циклически сдвинутой вправо на одну позицию.

Читателю рекомендуется самостоятельно проверить справедливость свойства сдвига и вычитания для троичной т-последовательности примера 6.5. Очевидно, для генерирования р-ичной т-последовательности, т. е. последовательности с максимальным периодом, возможным для фиксированной памяти п (а не некоторой последовательности меньшей длины), требуется специальный подбор коэффициентов 1; в рекурсии (6.13) (или в РСЛОС). Для того чтобы линейная последовательность была т-последовательностью,необходимо и достаточно использовать в рекурсии (6.13) множители Д, являющиеся коэффициентами ~;, ю' = 0,1,...,п — 1 примишиеного полинома,)(х) = х" + ~„1х" + )~ зх" + + 1е степени п над полем Сг'(р).

Примитивные полиномы составляют подкласс неприеодимых полиномов. Полипом 1(х) степени и над полем СГ(р) (т.е. с коэффициентами из СГ(р)) называется неприводимым над СР(р), если его нельзя представить как произведение двух полиномов степени, меньшей п. Подобным полиномам в множестве всех полиномов принадлежит та же роль, что простым числам в множестве целых. Не каждый неприводимый полипом примитивен, хотя, к примеру, в частном случае р = 2 и простого 2" — 1 все неприводимые полиномы примитивны.

Характеристики

Список файлов книги