Циклические коды. Коды БЧХ (стр. 2 из 3)
Коды БЧХ
Одним из классов циклических кодов, способных исправлять многократные ошибки, являются коды БЧХ.
Примитивным кодом БЧХ, исправляющим tu ошибок, называется код длиной n=qm-1 над GF(q), для которого элементы
являются корнями порождающего многочлена.Здесь a - примитивный элемент GF(qm).
Порождающий многочлен определяется из выражения
где f1(x),f2(x)...- минимальные многочлены корней g(x).Число проверочных элементов кода БЧХ удовлетворяет соотношению
Пример. Определить значение порождающего многочлена для построения примитивного кода БЧХ над GF(2) длины 31, исправляющего двух кратные ошибки (tu=2).
Исходя из определения кода БЧХ корнями многочлена g(x) являются:
, где a - примитивный элемент GF(qm)=GF(25).Порождающий многочлен определяется из выражения
где f1(x), f2(x), f3(x), f4(x) - минимальные многочлены корней соответственно 
.Примечание.
Минимальный многочлен элемента b поля GF(qm) определяется из выражения
, где 
- наименьшее целое число, при котором 
.Значения минимальных многочленов будут следующими:
Так как f1(x)= f2(x)= f4(x), то
На практике при определении значений порождающего многочлена пользуются специальной таблицей минимальных многочленов (см. таблицу 8 приложения), и выражением для порождающего многочлена
При этом работа осуществляется в следующей последовательности.По заданной длине кода n и кратности исправляемых ошибок tu определяют:
- из выражения n=2m-1 значение параметра m, который является максимальной степенью сомножителей g(x); - из выражения j=2tu-1 максимальный порядок минимального многочлена, входящего в число сомножителей g(x).
- пользуясь таблицей минимальных многочленов, определяется выражение для g(x) в зависимости от m и j. Для этого из колонки, соответствующей параметру m, выбираются многочлены с порядками от 1 до j, которые в результате перемножения дают значение g(x).
В выражении для g(x) содержаться минимальные многочлены только для нечетных степеней a, так как обычно соответствующие им минимальные многочлены четных степеней a имеют аналогичные выражения.
Например, минимальные многочлены элементов
соответствуют минимальному многочлену элемента a1, минимальные многочлены элементов 
соответствуют минимальному многочлену a3 и т.п.Пример. Определить значение порождающего многочлена для построения примитивного кода БЧХ над GF(2) длины 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. Неиспользованных информационных разрядов будет 11(51-40).
Подобное несоответствие в ряде случаев можно устранить, применяя непримитивный код БЧХ.
Непримитивным кодом БЧХ, исправляющим tu ошибок, называется код длины n над GF(q), для которого элементы
являются корнями порождающего многочлена.Здесь bi-непримитивный элемент GF(qm), а длина кода n равна порядку элемента bi.
Примечание.
Порядком элемента bi является наименьшее n, для которого
.Пример. Порядок элемента b3 поля GF(26) равен 21, так как
.Порождающий многочлен непримитивного кода БЧХ, по аналогии с примитивным кодом, определяется из выражения
- минимальные многочлены элементов 
поля GF(qm), которые являются корнями g(x); i - степень непримитивного элемента b.Пример. Определить значение g(x) для построения непримитивного кода БЧХ над GF(2) длины n=20, исправляющего двух кратные ошибки.
Из таблицы непримитивных элементов GF(2m) (см. таблицу 7 приложения) выбираем поле, элемент b которого имеет порядок больший, но близкий к заданному n.
Приложение
Таблица 1
Разложение бинома хn+1 на неприводимые сомножители
| Степень бинома | Последовательности степеней корней неприводимых сомножителей | Неприводимые сомножители |
| 7 | 1 2 4 3 6 5 | 13 15 |
| 15 | 01 02 04 08 03 06 12 09 05 10 07 14 13 11 | 023 037 007 031 |
| 31 | 01 02 04 08 16 03 06 12 24 17 05 10 20 09 18 07 14 28 25 19 11 22 13 26 21 15 30 29 27 23 | 045 075 067 057 073 051 |
| 63 | 01 02 04 08 16 32 03 06 12 24 48 33 05 10 20 40 17 34 07 14 28 56 49 35 09 18 36 11 22 44 25 50 37 13 26 52 41 19 38 15 30 60 57 51 39 21 42 23 46 29 58 53 43 27 54 45 31 62 61 59 55 47 | 103 127 147 111 015 155 133 165 007 163 013 141 |
Примечание. В разложение всех биномов входит сомножитель 03 с корнем 00. Все сомножители представлены в восьмеричной форме.
Таблица 2
Элементы поля GF(16) как расширение GF(2) по примитивному многочлену a(z)=z4+z+1
| В двоичном виде | В виде многочлена | В виде степени |
| 0000 | 0 | 0 |
| 0001 | 1 | a0 |
| 0010 | z | a1 |
| 0100 | z2 | a2 |
| 1000 | z3 | a3 |
| 0011 | z+1 | a4 |
| 0110 | z2+z | a5 |
| 1100 | z3+z2 | a6 |
| 1011 | z3+z+1 | a7 |
| 0101 | z2+1 | a8 |
| 1010 | z3+z | a9 |
| 0111 | z2+z+1 | a10 |
| 1110 | z3+z2+z | a11 |
| 1111 | z3+z2+z+1 | a12 |
| 1101 | z3+z2+1 | a13 |
| 1001 | z3+1 | a14 |
Таблица 3
Элементы поля GF(16) как расширение GF(4) по примитивному многочлену f(z)=z2+z+2
| В четвертичном виде | В десятичном виде | В виде многочлена | В виде степени |
| 00 | 0 | 0 | 0 |
| 01 | 1 | 1 | a0 |
| 10 | 4 | z | a1 |
| 12 | 6 | z+2 | a2 |
| 32 | 14 | 3z+2 | a3 |
| 11 | 5 | z+1 | a4 |
| 02 | 2 | 2 | a5 |
| 20 | 8 | 2z | a6 |
| 23 | 11 | 2z+3 | a7 |
| 13 | 7 | z+3 | a8 |
| 22 | 10 | 2z+2 | a9 |
| 03 | 3 | 3 | a10 |
| 30 | 12 | 3z | a11 |
| 31 | 13 | 3z+1 | a12 |
| 21 | 9 | 2z+1 | a13 |
| 33 | 15 | 3z+3 | a14 |
Таблица 4
Элементы поля GF(4) как расширение GF(2) по примитивному многочлену f(z)=z2+z+1
| В двоичном виде | В виде многочлена | В виде степени | В десятичном виде |
| 00 | 0 | 0 | 0 |
| 01 | 1 | a0 | 1 |
| 10 | z | a1 | 2 |
| 11 | z+1 | a2 | 3 |
Таблица 6
Элементы поля GF(8) как расширение GF(2) по примитивному многочлену f(z)=z3+z+1
| В двоичном виде | В виде многочлена | В виде степени |
| 000 | 0 | 0 |
| 001 | 1 | a0 |
| 010 | z | a1 |
| 100 | z2 | a2 |
| 011 | z+1 | a3 |
| 110 | z2+z | a4 |
| 111 | z2+z+1 | a5 |
| 101 | z2+1 | a6 |
Таблица 7