Реферат: Циклические коды. Коды БЧХ
Заданные исходные данные: 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
Непримитивные элементы поля GF(2m )
| ¹ | m | GF(2m ) | b | n |
| 1 | 4 | GF(24 ) | b3 | 5 |
| b5 | 3 | |||
| 2 | 6 | GF(26 ) | b3 | 21 |
| b7 | 9 | |||
| b9 | 7 | |||
| 3 | 8 | GF(27 ) | b3 | 85 |
| b5 | 51 | |||
| b15 | 17 | |||
| b17 | 15 | |||
| 4 | 9 | GF(29 ) | b7 | 73 |
| 5 | 10 | GF(210 ) | b3 | 341 |
| b11 | 93 | |||
| b31 | 33 | |||
| b33 | 31 | |||
| 6 | 12 | GF(212 ) | b3 | 1365 |
| b5 | 819 | |||
| b7 | 585 | |||
| b9 | 455 | |||
| b13 | 315 | |||
| b15 | 273 | |||
| b21 | 195 | |||
| b45 | 91 | |||
| b63 | 65 | |||
| b65 | 63 |
Таблица 8
Минимальные неприводимые многочлены в поле GF(2m )
| 2tu -1 | m | ||||||||
| 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
| 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 | 7 | 13 15 | 31 37 07 31 | 45 75 67 57 73 | 103 127 147 111 015 155 | 211 217 235 367 277 325 203 | 435 567 763 551 675 747 453 727 023 545 613 543 433 477 615 435 537 771 | 1021 1131 1461 1231 1423 1055 1167 1541 1333 1605 1027 1751 1743 1617 1401 | 2011 2017 2415 3771 2257 2065 2157 2653 3515 2773 3753 2033 2443 3573 2461 3041 75 3023 |
Такими являются GF(26 ) и b3 , порядок которого n=21.