7.3.4. ВАЖНЫЕ ПОДКЛАССЫ ЛИНЕЙНЫХ ДВОИЧНЫХ КОДОВ

1. Коды с общей проверкой на чётность. Это класс кодов с параметрами когда имеется лишь один проверочный символ, который образуется как сумма по всех информационных символов. Очевидно, что минимальное расстояние для данных кодов всегда равно 2 и поэтому они могут гарантированно обнаруживать лишь одну ошибку. Комбинации данного кода имеют лишь чётные веса.

2. Коды Хэмминга. Данный класс кодов имеет параметры целое. Он определяется проверочной матрицей которая должна содержать все ненулевых двоичных векторов. Используя подход, изложенный в доказательстве теоремы 7.7, легко видеть, что данный класс кодов имеет при любых минимальное кодовое расстояние, равное 3. Это пример совершенного кода, исправляющего все однократные ошибки и ничего более. Коды Хэмминга могут гарантированно обнаруживать ошибки кратности 1 и 2.

Число кодовых слов веса (спектр кода Хэмминга длины ) можно найти как коэффициент при следующего многочлена:

Если к кодам Хэмминга добавить ещё один проверочный символ (путём общей проверки на чётность), то получатся коды с параметрами , у которых , а спектр их определяется многочленом

3.М-последовательности. Это класс кодов с параметрами целое, которые определяются как дуальные к кодам Хэмминга той же самой

длины. Данный класс кодов может быть определён также иначе, как совокупность выходных последовательностей при различных начальных заполнениях линейного регистра длины 5 со связями, выбранными так, чтобы период выходной последовательности оказался равным Поэтому они получили название последовательностей максимальной длины или -последовательностей. Все комбинации данного кода, кроме нулевой, имеют одинаковый вес 21 и, следовательно, для такого кода Коды Хэмминга и -последовательности являются крайними случаями кодов с малой и большой величиной минимального кодового расстояния. Они не всегда удобны для практического использования, поскольку исправление только однократных ошибок обычно оказывается недостаточным для обеспечения высокой верности передачи, а высокая исправляющая способность -последовательностей покупается за счёт их весьма низкой кодовой скорости Поэтому необходимо иметь класс кодов с промежуточными значениями Это может быть достигнуто при переходе к определённым подклассам циклических кодов.

Полиномиальные коды. Циклические коды. Коды Боуза-Чоудхури-Хоквингема (БЧХ). Кодовые слова двоичного линейного кода могут быть представлены в виде полиномов степени от некоторой формальной переменной причём двоичные коэффициенты х. задают символы кодового слова. Полиномиальный код определяется как множество полиномов (кодовых слов) степени получаемых умножением информационного полинома степени на порождающий полином кода степени

Уравнение (7.68) задаёт процедуру кодирования полиномиального кода: сообщение дискретного источника кодируется примитивным кодом длины к, символы примитивного кода становятся коэффициентами информационного полинома последний умножается на порождающий полином кода и после приведения подобных членов определяются коэффициентов полинома являющихся символами кодового слова.

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

На практике находят применение циклические коды, являющиеся частным случаем полиномиальных кодов.

Пусть произвольный двоичный блок длины Будем называть циклическим сдвигом вправо данного блока преобразование следующего вида:

Определение 14. Линейный двоичный -код V называется циклическим кодом, если в результате циклического сдвига любой из его комбинаций полученная комбинация снова принадлежит коду, т.е. если

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

где произвольный многочлен с двоичными коэффициентами степени не выше [21].

Многочлен о котором идёт речь в данной теореме, называется порождающим многочленом циклического кода. Многочлен называется проверочным многочленом. Можно доказать, что многочлен является порождающим многочленом для дуального кода.

Циклические коды значительно упрощают описание линейного кода, поскольку для них вместо задания к элементов двоичной матрицы в представлении (7.48) требуется задать двоичных коэффициентов многочлена Кроме того, они упрощают процедуру кодирования и декодирования для обнаружения ошибок. Действительно, для осуществления кодирования достаточно выполнить перемножение полиномов, что реализуется с помощью линейного регистра, содержащего к ячеек памяти и имеющего обратные связи, соответствующие многочлену [21]. Для обнаружения ошибок достаточно разделить многочлен, соответствующий принятому слову на порождающий многочлен и проверить, будет ли остаток от деления равен нулю. Эта процедура также осуществляется на линейных сдвиговых регистрах с обратными связями. Однако более важное преимущество циклических кодов состоит в том, что они могут быть сконструированы как коды с некоторым гарантированным значением минимального кодового расстояния. Для этого необходимо определённым образом выбрать порождающий многочлен кода Циклические коды, которые имеют порождающий многочлен, заданный своими определёнными корнями, называются кодами Боуза-Чоудхури-Хоквингема (кратко БЧХ-кодами). Однако корни этого многочлена ищутся не среди вещественных или комплексных чисел, а как элементы так называемых конечных полей Галуа.

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

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

1. Для любой пары элементов поля определены операции называемые, соответственно, сложением и умножением, отображающие пару в какой-либо элемент поля

2. Поле содержит нулевой элемент 0 и единичный 1, такие что а для любого

3. Для любого существует противоположный (аддитивно обратный) элемент -а такой, что и для любого , существует мультипликативно обратный элемент такой, что

4. Для операций с элементами поля выполняются законы:

а) ассоциативный

б) коммутативный

в) дистрибутивный

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

Из определения поля видно, что фактически для любых пар элементов определена также и операция вычитания: а для пар и операция деления Доказывается, что в поле существует единственный элемент 0 и единственный элемент 1. В алгебре доказывается важная теорема о том, что порядок поля всегда является степенью простого числа т.е. где натуральное число. Еслн то поле называется простым. Для каждого допустимого значения правила сложения и умножения, удовлетворяющие заданным требованиям, можно определить только одним способом. Все элементы простого поля могут бьггь заданы как множество чисел ( а операции над ними — как действия по модулю т.е. как числа, равные остатку от деления на

В качестве примера в табл. 7.3 даны правила умножения и сложения для поля Таблица умножения позволяет находить обратные элементы; так, поскольку Таблица сложения позволит определить обратный элемент -а на пересечении а и 0. При вычитании или делении необходимо, используя таблицы, найти обратный элемент для вычитаемого или делителя, а затем выполнить сложение илиумножение обычным образом.

Например,

Таблица 7.3 (см. скан)

Возведение в степень также возможно с учётом формулы Например,

Определим операции в расширенном поле которые не задаются уже как операции по

Поле при называется расширением поля а поля такого вида — расширенными полями. Все элементы расширенного поля можно представить как всевозможные последовательности длины с элементами из поля Например, поле состоит из элементов: 000, 001, 010, 011, 100, 101, 110, 111.

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

Пример. Многочлен приводим над так как ; многочлен не приводим над так как его цельзя представить как произведение каких-либо из следующих многочленов степени меньше 3, но больше нуля над полем

Разработаны регулярные методы генерирования неприводимых многочленов. В литературе (см., например, [21]) имеются таблицы некоторых неприводимых многочленов различных степеней (В действительности имеется много неприводимых многочленов любой степени.)

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

представить полиномом степени с коэффициентами над полем как Тогда сумму двух элементов поля а можно получить как сумму соответствующих им многочленов, а произведение как произведение соответствующих многочленов по модулю неприводимого полинома степени

Пример:

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

Определение. Элемент называется примитивным, если все его степени различны и дают все элементы конечного поля кроме нулевого. Доказывается [21], что в любом конечном поле всегда существует примитивный элемент. (В действительности в каждом поле имеется несколько примитивных элементов.) Использование понятия примитивного элемента значительно упрощает описание таблицы умножения элементов поля. Действительно, если то Легко определяются и обратные элементы, поскольку если то (Однако таблица сложения не упрощается при использовании примитивного элемента.)

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

Определение. Неприводимый многочлен степени над полем называется примитивным многочленом, если хотя бы один из его корней является примитивным элементом поля

Можно доказать [21], что у примитивного многочлена все корни являются примитивными элементами, причём если один из корней этого многочлена, то образуют совокупность всех корней этого многочлена. (В действительности последнее свойство справедливо для любого неприводимого многочлена.) Существует и другое (эквивалентное) определение примитивного многочлена — это такой неприводимый многочлен степени что он делит многочлен и не делит многочлены вида если . В литературе приводятся таблицы примитивных элементов [21]. Число примитивных многочленов степени определяется по формуле

где функция Эйлера, которая определяется как количество чисел ряда взаимно простых с Если простое число, то

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

Определение. Двоичный циклический код длины где I — неотрицательное целое число, называемое кодом Боуза-Чоуцхури-Хоквингема (или сокращённо БЧХ-кодом) в узком смысле, если слово х принадлежит коду тогда, и только тогда, когда где примитивный элемент поля являются корнями многочлена

Это определение эквивалентно следующему матричному уравнению:

Все действия в (7.68а) выполняются в поле

Рассмотрим определитель составленный из любого набора столбцов матрицы

Вынося из каждого столбца множитель получаем

Поскольку в правой части (7.69) стоит определитель Ван-дер-Монда, то он всегда будет отличен от нуля, и, следовательно, не существует линейно зависимых комбинаций из 21 или меньшего числа столбцов матрицы Поэтому аналогично выводу границы Варшамова-Гильберта получим, что код, определяемый уравнением (7.68а), будет иметь минимальное кодовое расстояние

Можно доказать [21], что степень порождающего многочлены такого циклического кода не превосходит и поэтому такой код содержит не более чем проверочных символов. Этот факт может быть сформулирован в виде следующей теоремы.

Теорема 7.10. Всегда можно построить двоичный БЧХ-код с длиной блока любое натуральное число), который имеет информационных символов натуральное число) и гарантированно исправляет ошибки кратности не меньше, чем

Этот код в отличие от неконструктивного метода, который мы использовали при выводе границы Варшамова-Гильберта, весьма просто определяется своим порождающим многочленом Имеются достаточно подробные таблицы, которые дают для всевозможных наборов виды порождающих многочленов и соответствующие им значения минимальных кодовых расстояний