Необходимые теоретические сведения

Для всякого натурального , делящего в поле Галуа найдется элемент b порядка (например, для примитивного элемента и ). Зафиксируем целые числа не делящиеся на и d > 1, натуральное делящее или равное но не делящее для всех целых При этом значение должно быть таким, что выполняется неравенство

Определение 5.1. Линейный код длиной с проверочной матрицей

Н= (5.1)

над полем называется кодом Боуза-Чоудхури-Хоквингема (БЧХ-кодом) с конструктивным расстоянием . При n = БЧХ-код называют примитивным, и не примитивным, если n < .

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

Теорема 5.1. Для всякого целого числа не делящегося на над полем существует БЧХ-код длиной Для всякого нечетного существует двоичный БЧХ-код длиной

Здесь изучим некоторые свойства элементов играющих неотъемлемую роль в определении БЧХ-кодов – в формировании проверочных матриц этих кодов. Они возникают несколько затененно, как степени примитивных элементов. В принципе, это естественно, так как мультипликативная группа циклична. Но такой подход не позволяет сказать что-либо об аддитивных свойствах

Теорема 5.2. Для всякого натурального являющегося делителем но не делящего для всех целых элемент порядка существует. Он является корнем неприводимого и непримитивного полинома показателя и степени над полем

Размерность линейного кода длиной как векторного пространства над полем при задании этого кода с помощью проверочной матрицы определяется формулой .

Ранг проверочной матрицы БЧХ-кода чаще всего совпадает с числом ее строк Но иногда возникают ситуации, когда этот ранг меньше Наиболее типичную из таких ситуаций описывает теорема 5.3.

Теорема 5.3. Пусть для некоторого целого не делящегося на проверочная матрица БЧХ-кода содержит, с точностью до перестановки строк, подматрицу Тогда

Заметим, что теорема остается справедливой, если в подматрице степень заменить на для целых

Выяснением равенства устанавливается принадлежность данному коду. Все декодеры телекоммуникационных цифровых систем реализуют проверку этого соотношения. Вычисления происходят быстро, синхронно с поступлением информации. Поэтому эти вычисления должны требовать минимума временных затрат. В силу сказанного, матрица должна быть минимально сложной, в частности не содержать линейно зависимых строк – такие из матрицы следует удалять. Из указанного обстоятельства и возникло условие: ранг проверочной матрицы кода равен числу ее строк.

Указанная теоремой 5.3 ситуация чаще всего возникает при (тогда код называют БЧХ-кодом в узком смысле). Наиболее типична она для двоичных кодов, когда Поэтому после удаления линейно зависимых строк проверочная матрица БЧХ-кода в узком смысле в данном случае и для и для имеет один и тот же вид:

, . (5.2)

Истинная размерность данного БЧХ-кода есть величина что существенно больше конструктивной размерности Именно такие коды получили наибольшее применение, особенно когда , то есть при .

Примитивный двоичный БЧХ-код исправляющий случайных ошибок, задается над полем Галуа проверочной матрицей

где фиксированный примитивный элемент поля , параметр принимает целые значения в пределах от 0 до для . Предполагается, что каждый элемент матрицы есть двоичный столбец из элементов 0 или 1 – координат соответствующей степени как вектора пространства над полем в базисе Поскольку ядром матрицы является весь код ненулевое мерное подпространство в двоичном n –мерном пространстве, то ранг матрицы по построению равный должен быть существенно меньше Таким образом, при задании кода автоматически должно выполняться строгое неравенство Конструктивное кодовое расстояние такого БЧХ-кода отсюда следует мотивация обозначения данного кода через Как уже отмечалось, реальное кодовое расстояние

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

(5.4)

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

Определение 5.2. Следующие симметрических многочленов от неизвестных называются элементарными симметрическими многочленами:

………………………….

Для степенных сумм ещё Ньютоном установлены следующие рекуррентные формулы:

Эти формулы позволяют последовательно выражать степенные суммы через элементарные симметрические полиномы. Очевидно, Формула (5.5) при имеет вид: Следовательно, Формула (5.5) при имеет более сложный вид: Подстановкой в это уравнение найденных значений для и получаем: Продолжая аналогичным образом, можно получить выражение через элементарные симметрические полиномы любой конкретной степенной суммы

Для обработки БЧХ-кодов все эти вычисления необходимо проводить в поле – поле характеристики 2. Здесь Поэтому формулы несколько меняются. Здесь Выражение для зависит от если то для выражения через элементарные симметрические многочлены применяем формулу , в противном случае – формулу .

Предположим, что мы применяем БЧХ-код , исправляющий тройные ошибки, то есть код с параметром Тогда для исправления тройных ошибок необходимо решать следующий более простой аналог системы :

(5.7)

В данном случае для выражения через элементарные симметрические многочлены следует воспользоваться формулой (5.6). В таком случае И так далее.

Посмотрим, однако, на соотношения – в противоположном направлении – как на соотношения для определения элементарных симметрических полиномов. Фактически, уравнения и определяют значения степенных сумм Тогда уравнения – определяют систему линейных уравнений для нахождения Так для БЧХ-кода эта система линейных уравнений имеет вид:

или

Предположим, мы решили такую систему уравнений и нашли значения элементарных симметрических многочленов: Этой информацией мы можем воспользоваться для нахождения координат ошибочных позиций принятого с помощью БЧХ-кода сообщения Идея эта базируется на следующей классической теореме о связи корней алгебраических уравнений с коэффициентами этих уравнений.

Теорема Виета. Пусть у уравнения

(5.9)

коэффициенты принадлежат полю Элементы поля являются корнями данного уравнения тогда и только тогда, когда

……………………………………………………………………………. (5.10)

Теорему Виета будем применять следующим образом. По найденным в силу соотношений (5.10) составляем уравнение (5.9), называемое уравнением локаторов ошибок. Алгебраические уравнения над полями Галуа проще всего решать методом Чэня, то есть последовательной подстановкой в уравнение элементов данного поля. Найдя корни мы однозначно определяем вектор и, следовательно, исправляем принятое сообщение.

Пример 5.1. В системе связи, построенной на основе примитивного БЧХ-кода длиной 63 с проверочной матрицей примитивный элемент поля Галуа корень неприводимого полинома принято сообщение с синдромом

Выяснить наличие ошибок в этом сообщении и попытаться их исправить.

Решение. Система линейных уравнений (5.8) здесь имеет вид:

или

Несложные вычисления показывают, что здесь Теперь можно составить уравнение (5.9): Кропотливые вычисления метода Чэня позволяют найти следующие корни этого уравнения: Следовательно, в принятом сообщении имеется тройная ошибка на 11-й, 21-й и 31-й позициях.

В заключении заметим, что представленный синдромный метод декодирования не лишён недостатков. В его реализации имеются такие громоздкие этапы как нахождение коэффициентов уравнения (5.9) и его решение переборным методом Чэня. Обойти все эти сложности синдромного метода позволяет теория норм синдромов.

Дата добавления: 2017-02-01