Правила построения кода Рида-Маллера

Коды Рида-Маллера являются линейными двоичными блочными кодами. При определенном построении они могут быть систематическими. В общем случае коды Рида-Маллера не являются циклическими.

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

- длина кодового слова ;

- длина информационной части

- длина проверочной части

- минимальное кодовое расстояние .

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

Код Рида-Маллера определяется при помощи порождающей матрицы, состоящей из базисных векторов. Правило построения следующее:

- пусть - вектор, все компоненты которого равны 1;

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

Покомпонентное произведение любых двух векторов и задается следующим образом:

.

(1.18)

Пример. Для m = 4 и соответственно n = 2⁴ = 16 запишем базисные векторы кода Рида-Маллера:

 

Сформированная из базисных векторов порождающая матрица может быть использована для кодирования. Чтобы получить из данной матрицы проверочную, необходимо провести ее преобразование к систематическому виду. Это обеспечивается путем сложения по модулю 2 первой строки со всеми остальными строками матрицы. Такая операция не изменяет характеристик кода. Получив проверочную и порождающую матрицы, можно проводить с кодом все операции, описанные в п. 1.3.1. Следует отметить, что при декодировании методом порогового декодирования строить проверочную матрицу нет необходимости.

 

Основные понятия о свойствах многочленов и полях Галуа

 

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

Полем Галуа называется конечное коммутативное поле. Конечное поле - это конечное множество из q элементов, в котором определены правила для выполнения арифметических операций. Поле Галуа из элементов обозначается .

Поля Галуа обладают следующими свойствами:

- в поле определены две операции: сложение и умножение;

- результатом сложения или умножения двух элементов поля является элемент этого же поля;

- поле всегда содержит мультипликативную единицу 1 и аддитивную единицу 0, т.е. и для любого элемента , принадлежащего полю;

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

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

Для каждого допустимого значения существует ровно одно поле.

Если - простое число, то элементами поля являются числа 0, 1,..., ( -1), а сложение и умножение являются обычными сложением и умножением по модулю .

Если является степенью простого числа, т.е. если , то элементами поля являются все многочлены степени или менее, коэффициенты которого лежат в простом поле .

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

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

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

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

.

(1.19)

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

Запись поля Галуа осуществляется в виде набора из многочленов степени, не превышающей . Первый элемент записи всегда равен нулю (нулевой элемент поля) и обычно в записи не приводится. Остальные многочленов представляют собой степени от 0 до примитивного элемента поля. Здесь и далее принимается, что старшие степени многочленов записываются слева, младшие справа.

Построение поля проводится в следующем порядке:

- записываются степени примитивного элемента от 0 до (m -1); запись производится в виде

- записывается элемент , который определяется по правилу

;

- записываются многочлены, соответствующие остальным степеням , от до . Указанные степени определяются посредством: а) умножения предыдущего многочлена, т.е. многочлена, соответствующего , на ; б) замены на многочлен ; в) приведения подобных членов.

Таким образом, поле Галуа GF(2^m) запишется в виде

(1.20)

Умножение элементов поля Галуа сводится к сложению степеней умножаемых элементов и приведению результата в диапазон … . Операция сложения элементов поля Галуа выполняется над двоичными числами по модулю 2. Степень определяется по соответствию результата сложения в поле вида (1.20).

Пример. Многочлен является неприводимым примитивным многочленом третей степени. Следовательно, при помощи этого многочлена может быть построено поле . Согласно формулам (1.20), поле будет иметь вид

 

.

(1.21)

В соответствии с (1.21) выражение можно вычислить следующим образом: a² + a⁵ = a³ = (011); a³a = a⁴ = (110); 1 + a³ = a = (010); aa = a² = (100); a⁴ + a² = a = (010). Таким образом, искомое выражение будет равно ¦(a) = a = (010).

Также для построения поля Галуа важны следующие свойства:

- неприводимый, т.е. неразложимый на множители над некоторым конечным полем многочлен всегда может быть разложен на множители над некоторым расширением этого поля, т.е. многочлен всегда имеет корни в некотором расширении;

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

- если - корень многочлена , то называется минимальной функцией , если - примитивный элемент, то ¦(x) называется примитивным многочленом;

- корни многочлена совпадают с ненулевыми элементами .

Пример. Многочлен неприводим над полем , но он может быть разложен на множители над полем . Если поле GF (2³) задано в соответствии с (1.21), то подстановкой можно найти, что a является корнем . Действительно, ¦(a) = a³ + a + 1 = (011) + (010) + (001) = (000) = 0. Также корнями являются a² и a⁴, что можно проверить подстановкой. У неприводимого многочлена над полем может быть не более m корней. Дальнейшее повышение степени a дает повторение тех же самых корней (, a² и a⁴), действительно, a⁸ = a, a¹⁶ = a² и т.д. Многочлен может быть также получен, если известно, что a, a² и a⁴ являются корнями одного и того же многочлена. Например, .

Элемент a является примитивным элементом поля GF (2³), поэтому является примитивным многочленом. Многочлен (x⁷-1) разлагается на множители следующим образом: (x⁷-1) = (x³+x²+1)(x³+x+1)(x+1). Корнем примитивного многочлена (x+1) является a⁰ = 1, корнями (x³+x+1) - a, a², a⁴; корнями (x³+x²+1) - a³, a⁶, a¹²=a⁵. Все эти семь корней являются ненулевыми элементами поля GF (2³), состоящего как раз из семи ненулевых элементов.