Некоторые свойства многочленов и их использование в задачах связи (стр. 2 из 3)

что и требовалось доказать.

5.2. Применение новых свойств многочленов к задачам связи

Применение новых свойств многочленов к задачам помехоустойчивого кодирования

Типовые (стандартные) процедуры помехоустойчивого кодирования базируются на вычислении вычета (остатка или контрольной суммы) в регистре сдвига с обратными связями [7]:

, (4)

где G(x) – неприводимый многочлен, образующий код, а А(х) – вектор информационной части блока.

Полученный остаток дополняет блок и передается по каналу связи на приемную станцию. По принятому блоку

, (5)

где

– вектор ошибки, вычисляется синдром ошибки:

. (6)

Вычисление контрольной суммы в кодере и синдрома ошибки в декодере выполняется одинаковыми регистрами сдвига кодера и декодера. Стандартный кодер систем передачи данных для

оговорен рекомендацией V-41 МККТТ [7].

Логичным является следующий вопрос:

– имеют ли одинаковую обнаруживающую способность полиномы одной и той же степени (включая взаимные)?

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

(7)

где

– элемент кольца вычетов по модулю G(x).

Вычислим вычет инверсного к информационному многочлена:

(8)

Отметим, что для циклического кода Боуза-Чоудхури-Хоквингема (БЧХ кода) длину информационной части блока берут из условия

, где k – степень кодового полинома, а L – длина блока. Это значит, что длина информационной части блока не должна превышать длины периода кольца вычетов.

Всегда можно выбрать L=T, а любой двучлен вида

представить в виде

.

Учтем, что:

– неприводимый многочлен делит без остатка двучлен

, что обозначает ;

– многочлены

и имеют одинаковую степень, поэтому .

Отсюда прямой и взаимный многочлен без остатка делит не только

, но и .

Поэтому, если неприводимый многочлен

несимметричен, т.е. , то имеет место следующее разложение:

. (9)

Учитывая, что

– симметричные многочлены, то F(x) – также симметричный многочлен, степень которого равна d = (T-1)-2k.

Здесь

– взаимные несимметричные многочлены (их произведение есть симметричный многочлен). Симметричные многочлены, если они имеются в разложении, записываются отдельно (например, Е(х), (х+1)) или входят в F(x) (см., например, в разложении ).

Учитывая, что

,

получим, что

(10)

т.е. вычеты прямого и инверсного многочленов равны друг другу.

Для вычетов:

– прямого многочлена по взаимному модулю;

– взаимного многочлена по взаимному модулю;

– взаимного многочлена по прямому модулю запишем:

(11)

(12)

где

– элемент кольца вычетов по модулю G^(x).

(13)

Сравнивая (7) и (13), (11) и (12) заметим, что

и есть соответственно прямой и обратный элемент кольца вычетов по модулю G(x), связанные, соответственно, как . Аналогично и есть соответственно прямой и обратный элемент кольца вычетов по модулю , . Отсюда следует, что:

1. контрольная сумма прямой и инверсной последовательности равны, кодирование прямой или инверсной последовательности равноценны;

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

3. кодирующее устройство не обязательно строить в виде регистра сдвига с обратными связями.

Кодирующее устройство может реализовать любую из процедур (7,11,12 или13).

В этом случае кодер может быть представлен структурой, показанной на рис.1 и содержать:

- генератор элементов кольца;

- накапливающий сумматор, который складывает элементы кольца

или , взвешенные с весом бита данных(0 или 1) .

Рис.1 Структурная схема БЧХ кодера

Данный кодер отличает то полезное свойство, что он не требует битовых операций и обеспечивает легкую смену кодового полинома. В силу этих обстоятельств легко выполняется как аппаратная, так и программная реализация такого кодека для БЧХ кода.

Декодер вычисляет синдром по уравнению (6), при этом, если ε(х) = 0, то S(х) = = 0. Однако, если S(х) = 0, то это не означает, что ε(х) = 0.

Возможна ситуация, когда S(х) = 0 при ε(х) ≠ 0. Эта ситуация есть необнаружение ошибки декодером или остаточная ошибка декодера. Очевидно, ошибка декодирования возникает тогда, когда вектор ошибки кратен порождающему полиному, т.е

. (14)

Если кадр входных данных имеет длину L, то мощность вектора ошибки ε(х) равна 2^L, мощность множества необнаруженных ошибок D(x) равна 2^(L-k), при этом ошибки на оси 0,1,2,3… 2^L (такую ось можно получить, если записать все вектора ошибки в виде (1), положив х^j = 2^j) распределены равномерно через G(х) ошибок.

Поскольку мощность множества ошибок определяется только степенью порождающего многочлена и не зависит от его структуры и веса (веса по Хэммингу), то все коды, порожденные полиномом одной и той же степени (включая взаимные многочлены) имеют одинаковую обнаруживающую способность. Меняется лишь расположение необнаруживаемых ошибок на числовой оси. Это вовсе не означает, что вероятность остаточной ошибки декодера будет одинакова для любого полинома одной и той же степени. Вероятность остаточной ошибки декодера будет определяться тем, как часто "использует" канал связи ту или иную конфигурацию ошибок, т.е. зависит от статистики ошибок в канале. Отметим, что при равномерном распределении ошибок в канале связи вектора ошибки равномерно распределены по числовой оси, поэтому при любой длине блока доля необнаруженных ошибок не меняется. Отметим также, что с учетом теоремы 1 контрольная сумма прямого и взаимного кодового многочлена взаимны, поэтому они взаимно легко пересчитываются одна в другую и поэтому число неприводимых многочленов степени "k", которые можно использовать для помехоустойчивого кодирования равно числу пар "прямой-взаимный" многочлен.

Применение новых свойств многочленов к задачам генерации псевдослучайных последовательностей (ПСП)

ПСП, в частности, в такой разновидности, как последовательности максимального периода

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