Циклический код может быть задан порождающей и проверочной матрицами. Для их построения достаточно знать порождающий g(x) и проверочный h(x) многочлены.
Для несистематического циклического кода матрицы строятся циклическим сдвигом порождающего и проверочного многочленов, что эквивалентно умножению этих многочленов на x.
и
При построении матрицы H(n,k) старший коэффициент многочлена h(x) располагается справа.
Пример:
Для циклического (7,4) -кода с порождающим многочленом g(x)=x3+x+1 матрицы G(n,k) и H(n,k) имеют вид:
Для систематического циклического кода матрица G(n,k) определяется выражением:
,
где Ik – единичная матрица , Rk,r – прямоугольная матрица .
Строки матрицы Rk,r определяются из выражения:
где ai(x) – полином соответствующий i-той строке матрицы Ik.
Пример:
Матрица G(n,k) для систематического (7,4) -кода на основе порождающего многочлена g(x)=x3+x+1 строится в следующей последовательности:
или
или
Аналогично определяется:
или
Строки матрицы G(n,k) можно определить непосредственно из выражения:
|
|
Проверочная матрица в систематическом виде строится на основе матрицы G(n,k) (также как и для линейных кодов):
Пример:
Для (7,4) -кода матрица H(n,k) будет иметь вид:
Одна из основных задач, стоящих перед разработчиками устройств защиты от ошибок при передаче дискретных сообщений по каналам связи является выбор порождающего многочлена g(x), который позволит построить циклический код с заданной исправляющей способностью.
У разных классов циклических кодов имеются свои особенности формирования порождающих многочленов g(x).
Важный класс циклических кодов способный исправлять многократные ошибки – БЧХ.
Коды БЧХ
Код БЧХ может быть двоичным и недвоичным. Двоичные БЧХ коды можно построить с параметрами:
где m>3 – некоторое положительное число, tи – исправляющая способность кода.
Примитивным кодом БЧХ, исправляющим tu ошибок, называется код длиной n=qm-1 над полем GF(q), для которого элементы являются корнями порождающего многочлена.
Здесь a - примитивный элемент поля GF(qm), являющегося расширением поля GF(q).
Порождающий многочлен кода БЧХ определяется из выражения:
где НОК – наименьшее общее кратное, - минимальные многочлены корней g(x).
Справка: конечные поля.
Код над полем GF(q) имеет основание q. Число q обозначает порядок поля, который равен числу разных элементов содержащихся в этом поле. Порядок конечного поля может быть простым числом q или целой степенью m числа q. Поле GF(qm) – расширение поля GF(q).
Примитивным элементом a поля GF(q) или его расширения является такой элемент, посредством возведения которого в различные степени можно описать все остальные элементы поля.
|
|
Для построения порождающего многочлена кода БЧХ, необходимо выполнить арифметические операции в поле GF(qm).
Таблицу представления элементов поля рассмотрим на примере поля GF(8)=GF(23), которое является расширением поля GF(2) по модулю неприводимого многочлена .
Таблица - Таблица элементов поля
Степени примитивного элемента | Многочленные представления | Двоичные представления | Десятичные представления |
0 | 0 | 000 | 0 |
α7=α0=1 | 1 | 001 | 1 |
α1 | z | 010 | 2 |
α2 | z2 | 100 | 4 |
α3 | z+1 | 011 | 3 |
α4 | z2+z | 110 | 6 |
α5 | z2+z+1 | 111 | 7 |
α6 | z2+1 | 101 | 5 |
С помощью степенного представления выполняются операции умножения элементов поля. Для выполнения операции сложения необходимо использовать многочленные представления поля.
Конец справки.
Минимальный многочлен элемента b поля GF(qm) определяется из выражения:
где - наименьшее целое число, при котором .
Пример:
Определить значение порождающего многочлена g(x) для построения примитивного кода БЧХ над полем GF(2) длины 31, исправляющего двух кратные ошибки (tu=2).
Исходя из определения кода БЧХ корнями многочлена g(x) являются: , где a - примитивный элемент поля GF(25).
Порождающий многочлен определяется из выражения:
где - минимальные многочлены корней соответственно .
Определим . Нужно определить - числа сомножителей для выражения .
В расширении поля GF(2m) содержится 25=32 разных элементов. 31 из них представляют собой разные степени примитивного элемента a (от нулевой степени до тридцатой). Следовательно, значения a в степени s, при s>30 начнут повторяться:
Минимальное число , для которого , .
Значения минимальных многочленов будут следующими:
Так как , то:
На практике при определении порождающего многочлена используется таблица минимальных многочленов и выражением для порождающего многочлена:
Определение порождающего многочлена осуществляется в следующей последовательности.
По заданной длине кода n и кратности исправляемых ошибок tu определяют:
1. из выражения n=2m-1 значение параметра m, который является максимальной степенью сомножителей g(x);
2. из выражения j=2tu-1 максимальный порядок j минимального многочлена, входящего в число сомножителей g(x);
3. пользуясь таблицей минимальных многочленов, определяется выражение для g(x) в зависимости от m и j. Для этого из колонки, соответствующей параметру m, выбираются многочлены с порядками от 1 до j, которые в результате перемножения дают значение g(x).
Примечание: в выражении для g(x) содержаться минимальные многочлены только для нечетных степеней a, так как обычно соответствующие им минимальные многочлены четных степеней a имеют аналогичные выражения.
Например, минимальные многочлены элементов соответствуют минимальному многочлену элемента a1, минимальные многочлены элементов соответствуют минимальному многочлену a3 и т.п.
Пример:
Определить значение порождающего многочлена для построения примитивного кода БЧХ над полем GF(2), n=31, tu=3.
Определяем значения m и j:
Из таблицы минимальных многочленов в соответствии с m=5 и j=5 получаем:
Заданные исходные данные n и tu или k и tu для построения циклического кода часто приводят к выбору завышенного значения m и как следствие этого к увеличению длины кода. Такое положение снижает эффективность полученного кода, так как часть информационных разрядов не используется.
Пример:
Построить циклический код, исправляющий двух кратные ошибки, если длина информационной части кода k=40.
n=2m-1, ближайшая длина кода равна 63, для которой m=6, а r=mtu=12. Следовательно, код будет иметь n=63 и k=51. Неиспользованных информационных разрядов будет 51-40=11.
Подобное несоответствие в ряде случаев можно устранить, применяя непримитивный код БЧХ.
|
|
Непримитивным кодом БЧХ, исправляющим tu ошибок, называется код длины n над GF(q), для которого элементы являются корнями порождающего многочлена.
Здесь bi -непримитивный элемент поля GF(qm), а длина кода n равна порядку элемента bi.
Порядком элемента bi является наименьшее n, для которого .
Пример:
Порядок элемента b3 поля GF(26) равен 21, так как .
Порождающий многочлен непримитивного кода БЧХ, по аналогии с примитивным кодом, определяется из выражения:
где - минимальные многочлены элементов поля GF(qm), которые являются корнями g(x).
Пример:
Определить g(x) для построения непримитивного кода БЧХ над GF(2), n=20, tu=2.
Из таблицы непримитивных элементов GF(2m) выбираем поле, элемент b которого имеет порядок больший, но близкий к заданному n. Такими являются GF (26) и b3, порядок которого n=21. Так как j=2tu-1=3, то выражение для g(x) будет:
где и - минимальные многочлены элементов b3 и b9 поля GF(26).
Значения этих многочленов следующие:
Выражения для и можно определить из таблицы минимальных многочленов, используя для этого параметр m поля GF(2m) и порядковые номера сомножителей g(x).
Для рассмотренного примера m=6, а порядковые номера равны 3 и 9. Поэтому: