Коды БЧХ. Выбор образующих многочленов.
Коды БЧХ задаются корнями образующего многочлена. Выбор кода заключается в формировании цепочки корней требуемой длины (свойство 9), что производится методом проб. Последним этапом задания кода является нахождение самого образующего многочлена. Один из методов его вычисления только что был указан.
Таблицы неприводимых многочленов над полем GF(2) имеются, частности, в приложении В монографии У.Питерсон, Э Уэлдон. Коды, Исправляющие ошибки. Пер. с англ. Изд-во «Мир», М. 1976 г, 594с.
Многочлены даны в восьмеричном представлении. Каждый символ в таблице обозначает три двоичных знака: 0 ® 000; 1® 001; 2®010; … 6 ® 110; 7 ® 111.
Для каждой степени первый многочлен является примитивным и содержит минимальное число ненулевых коэффициентов. Если a - один из его корней, то запись начинающаяся числом i в таблице, соответствует минимальному многочлену для корня ai.
Проиллюстрируем выбор образующего многочлена на примере кода длины 15. Используя таблицу В2. В таблице указано минимально необходимое число многочленов, по которым можно найти разложение двучлена 
на множители. В нашем примере степень m=4. Первый неприводимый многочлен содержит корень a, он же используется для построения поля GF(24):
1 – 23 – 010 011 ® x4+x+1
3 – 37 – 011 111 ® x4+ x3+ x2+x+1
5 – 07 – 000 111 ® x2+x+1
Если очередной многочлен в порядке возрастания степени у a отсутствует в таблице, то он будет равен двойственному к одному из уже приведенных в таблице. Чтобы его найти, используют следующую процедуру: заменяют степень на отрицательную и приводят результат по модулю, равному длине кода.
a7®a-7Þ a15-7=a8, a, a2, a4®двойственные к многочлену a1. Записывают этот многочлен с отрицательными степенями и умножают на xm:
m7(x)= x4 m1(x-1) x4(x-4+ x-1+1)= x4+ x3+1.
Пусть нужно найти код с кодовым расстоянием d=5. По свойству 7 формируем цепочку корней длины 4.
1) Берем корень a1 и его цепочку aa2a4a8; это код (15,11) с d=3.
2) Объединяем первую цепочку с цепочкой, порожденной корнем a3 ® a3 a6 a12 a9. Получаем a a2 a3 a4 a6 a8 a9 a12. Это код (15,7) с d=5 g(x)= (x4+x+1)(x4+ x3+ x2+x+1)= x8+ x7+ x6+x4+1.
Другой возможный вариант:
1) Берем корень a7 и его цепочку a7 a14 a13 a14, это код (15,11) d =3.
2) Объединяем эту цепочку с цепочкой, порождаемой a3 ®a3 a6 a12 a9. Получаем a3 a6 a7 a9 a11 a12 a13 a14; это код (15,7) d = 5 g(x)= (x4+x3+1)(x4+ x3+ x2+x+1)= x8+ x4+ x2+x+1.
Третий вариант кода.
Объединяем три цепочки корней, соответствующие a1; a3 и a7. Получаем a a2 a3 a4a6 a7a8 a9a11 a12a13 a14; это код (15,3) с d=5, но он проигрывает двум предыдущим кодам по скорости: R1=R2=7/15; R3=3/15. Объединим цепочки, соответствующие корням a1; a7 и a0=1, при этом учтем, что a0=a15=1. Получим a0a1a2 a4 a7a8a11 a13a14. Образовалась цепочка корней a14a13a0a1a2 длиной 5. Получаем код (15,6) с d=6. g(x)=(x4+x+1)(x4+x3+1)(x+1).
Методом проб можно убедится, что имеются циклические коды длины 15 с информационной частью любой от 1 до 14 бит.
Пример 2. Разложить на множители x31+1 и убедится, что избыточная часть кодов может быть только кратна 5 и 6.
Записываем цепочки корней:
a a2 a4 a8a16 Þ 45 Þ m1(x)= x5+x+1
a3 a6 a12 a24 a17Þ75Þ m3(x)= x5+ x4+x3+ x2+1
a5 a10 a20 a9 a18Þ 67Þ m5(x)= x5+ x4+x2+ x+1
a7 a14 a28 a25 a15 – в таблице отсутствует, находим, к какому из вышеперечисленных будет двойственным:
amax=a28Þa-28 Þa3Þ m7(x)= x5(x-5+ x-4+x-3+ x-2+1)= x5+ x3+x2+ x+1.
a11 a22 a13 a26a21 – двойственен к m5(x) Þ m11(x)= x5+ x4+x3+ x+1
a15 a30 a29 a27a23 – двойственен к m1(x) Þ m15(x)= x5+x3+1.
Записываем разложение двучлена:
x31+1=(x+1)( x5+x+1)( x5+ x4+x3+ x2+1)( x5+ x4+x2+ x+1)( x5+ x3+x2+ x+1)( x5+ x4+x3+ x+1)( x5+x3+1).
Замечаем, что многочлены, задающие код, могут быть степени кратными 5 или 6 за счет множителя (x+1), т.е. имеются коды (31,26); (31,21); (31,16); (31,11); (31,6); (31,1) или с информационной частью на единицу меньше и нет других.
Обратите внимание, что имеются коды, эквивалентные по длине информационной части и кодовому расстоянию, но различающиеся по числу ненулевых коэффициентов образующего многочлена. Например, коды (31,26) d=3 g(x)= x5+x2+1 и (31,26) d=3 g(x)= x5+ x4+x2+ x+1