Лекции по Широкополосным сигналам и системам   

8. Бинарные последовательности с оптимальными периодическими автокорреляционными свойствами

8.2. Начальные сведения о конечных полях и линейных последовательностях

   

Для объяснения вышеупомянутых конструкций минимаксных бинарных последовательностей необходимо некоторое начальное представления о конечных полях. Назовем конечным полем (полем Галуа) конечное множество элементов, на котором определены две операции, именуемые (по аналогии с обычной арифметикой) сложением и умножением и обозначаемые привычными символами «+» и «∙». В любом поле обязательно присутствуют нулевой «0» и единичный «1» элементы, которые оставляют любой элемент поля неизменным в операциях сложения и умножения соответственно. Таблицы сложения и умножения в поле строятся таким образом, чтобы указанные операции были коммутативны, ассоциативны, дистрибутивны и обратимы. Последнее означает, что определены также операции вычитания и деления на ненулевой элемент. В частности, у каждого элемента имеется противоположный по сложению, а для любого ненулевого существует обратный по умножению элемент. Очевидно, что поле представляет собой множество, в пределах которого операции с элементами подобны операциям с действительными числами в обычной арифметике.

            Простейшим конечным полем является поле порядка 2 (число элементов поля), обозначаемое как GF(2), элементы которого «0» и «1» подчиняются правилам арифметики по модулю 2 (см. таблицу слева).

            Введем в рассмотрение последовательность  с элементами (символами) 0 и 1 из конечного поля , подчиняющуюся линейной рекурсии:

где коэффициенты  – фиксированные константы, принадлежащие . Элементы линейной последовательности вычисляются один за другим по правилам сложения и умножения в поле , причем каждый последующий определяется  предшествующими, так что, задав  начальных элементов , можно сгенерировать всю последовательность. Такая последовательность называется линейной (рекуррентной) последовательностью над полем  памяти .

     

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

            Предположим, что начальные состояния (т.е. начальные символы последовательности)  записаны в разряды регистра слева направо. Тогда состояние выхода петли обратной связи определится равенством

и после подачи тактового импульса содержимое ячеек регистра сдвига примет вид , генерируя состояние обратной связи

,

так что после подачи тактового импульса состояние обратной связи будет  и т.д. Обобщая, можно видеть, что в каждом такте текущее содержимое регистра  формирует состояние обратной связи , которое является следующим символов ЛРП и входным сигналов для первой ячейки регистра сдвига. Таким образом, полностью линейная рекуррентная последовательность может быть непосредственно считана с крайнего правого разряда, начиная с самого первого символа , или с любого другого разряда, но с определенным опережением во времени.

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

            Линейные рекуррентные последовательности, имеющие максимально возможный период

,

играют особую роль в современных информационных технологиях и называются последовательностями максимальной длины или просто m-последовательностями. Будучи полностью детерминированными, они обладают многими свойствами, присущими случайным последовательностям типа последовательности исходов подбрасывания правильной монеты, поэтому m–последовательности служат примером псевдошумовой последовательности. Два следующих замечательных свойства являются ключевыми для понимания ценности –последовательностей в плане построения кодов с хорошей автокорреляцией.

            1. Свойство уравновешенности. На одном периоде –последовательности число единиц  всегда превышает число нулей  ровно на единицу

.

            2. Свойство сдвига и сложения. Поэлементное сложение (разумеется, по модулю ) некоторой -последовательности и ее копии, циклически сдвинутой на  позиций, дает нулевую последовательность, если взаимный сдвиг m кратен периоду N:

 – целое,

либо некоторую новую сдвинутую (на l позиций) копию исходной -последовательности в противном случае:

.



*****
© Банк лекций Siblec.ru
Формальные, технические, естественные, общественные, гуманитарные, и другие науки.