Коды БЧХ. Выбор образующих многочленов.

Коды БЧХ задаются корнями образующего многочлена. Выбор кода заключается в формировании цепочки корней требуемой длины (свойство 9), что производится методом проб. Последним этапом задания кода является нахождение самого образующего многочлена. Один из методов его вычисления только что был указан.

Таблицы неприводимых многочленов над полем GF(2) имеются, частности, в приложении В монографии У.Питерсон, Э Уэлдон. Коды, Исправляющие ошибки. Пер. с англ. Изд-во «Мир», М. 1976 г, 594с.

Многочлены даны в восьмеричном представлении. Каждый символ в таблице обозначает три двоичных знака: 0 ® 000; 1® 001; 2®010; … 6 ® 110; 7 ® 111.

 

Для каждой степени первый многочлен является примитивным и содержит минимальное число ненулевых коэффициентов. Если a - один из его корней, то запись начинающаяся числом i в таблице, соответствует минимальному многочлену для корня aⁱ.

Проиллюстрируем выбор образующего многочлена на примере кода длины 15. Используя таблицу В2. В таблице указано минимально необходимое число многочленов, по которым можно найти разложение двучлена на множители. В нашем примере степень m=4. Первый неприводимый многочлен содержит корень a, он же используется для построения поля GF(2⁴):

1 – 23 – 010 011 ® x⁴+x+1

3 – 37 – 011 111 ® x⁴+ x³+ x²+x+1

5 – 07 – 000 111 ® x²+x+1

Если очередной многочлен в порядке возрастания степени у a отсутствует в таблице, то он будет равен двойственному к одному из уже приведенных в таблице. Чтобы его найти, используют следующую процедуру: заменяют степень на отрицательную и приводят результат по модулю, равному длине кода.

a⁷®a^-7Þ a^15-7=a⁸, a, a², a⁴®двойственные к многочлену a¹. Записывают этот многочлен с отрицательными степенями и умножают на x^m:

m₇(x)= x⁴ m₁(x^-1) x⁴(x^-4+ x^-1+1)= x⁴+ x³+1.

Пусть нужно найти код с кодовым расстоянием d=5. По свойству 7 формируем цепочку корней длины 4.

1) Берем корень a¹ и его цепочку aa²a⁴a⁸; это код (15,11) с d=3.

2) Объединяем первую цепочку с цепочкой, порожденной корнем a³ ® a³ a⁶ a¹² a⁹. Получаем a a² a³ a⁴ a⁶ a⁸ a⁹ a¹². Это код (15,7) с d=5 g(x)= (x⁴+x+1)(x⁴+ x³+ x²+x+1)= x⁸+ x⁷+ x⁶+x⁴+1.

 

 

Другой возможный вариант:

1) Берем корень a⁷ и его цепочку a⁷ a¹⁴ a¹³ a¹⁴, это код (15,11) d =3.

2) Объединяем эту цепочку с цепочкой, порождаемой a³ ®a³ a⁶ a¹² a⁹. Получаем a³ a⁶ a⁷ a⁹ a¹¹ a¹² a¹³ a¹⁴; это код (15,7) d = 5 g(x)= (x⁴+x³+1)(x⁴+ x³+ x²+x+1)= x⁸+ x⁴+ x²+x+1.

Третий вариант кода.

Объединяем три цепочки корней, соответствующие a¹; a³ и a⁷. Получаем a a² a³ a⁴a⁶ a⁷a⁸ a⁹a¹¹ a¹²a¹³ a¹⁴; это код (15,3) с d=5, но он проигрывает двум предыдущим кодам по скорости: R₁=R₂=7/15; R₃=3/15. Объединим цепочки, соответствующие корням a¹; a⁷ и a⁰=1, при этом учтем, что a⁰=a¹⁵=1. Получим a⁰a¹a² a⁴ a⁷a⁸a¹¹ a¹³a¹⁴. Образовалась цепочка корней a¹⁴a¹³a⁰a¹a² длиной 5. Получаем код (15,6) с d=6. g(x)=(x⁴+x+1)(x⁴+x³+1)(x+1).

Методом проб можно убедится, что имеются циклические коды длины 15 с информационной частью любой от 1 до 14 бит.

Пример 2. Разложить на множители x³¹+1 и убедится, что избыточная часть кодов может быть только кратна 5 и 6.

Записываем цепочки корней:

a a² a⁴ a⁸a¹⁶ Þ 45 Þ m₁(x)= x⁵+x+1

a³ a⁶ a¹² a²⁴ a¹⁷Þ75Þ m₃(x)= x⁵+ x⁴+x³+ x²+1

a⁵ a¹⁰ a²⁰ a⁹ a¹⁸Þ 67Þ m₅(x)= x⁵+ x⁴+x²+ x+1

a⁷ a¹⁴ a²⁸ a²⁵ a¹⁵ – в таблице отсутствует, находим, к какому из вышеперечисленных будет двойственным:

a^max=a²⁸Þa^-28 Þa³Þ m₇(x)= x⁵(x^-5+ x^-4+x^-3+ x^-2+1)= x⁵+ x³+x²+ x+1.

a¹¹ a²² a¹³ a²⁶a²¹ – двойственен к m₅(x) Þ m₁₁(x)= x⁵+ x⁴+x³+ x+1

a¹⁵ a³⁰ a²⁹ a²⁷a²³ – двойственен к m₁(x) Þ m₁₅(x)= x⁵+x³+1.

Записываем разложение двучлена:

x³¹+1=(x+1)(x⁵+x+1)(x⁵+ x⁴+x³+ x²+1)(x⁵+ x⁴+x²+ x+1)(x⁵+ x³+x²+ x+1)(x⁵+ x⁴+x³+ x+1)(x⁵+x³+1).

Замечаем, что многочлены, задающие код, могут быть степени кратными 5 или 6 за счет множителя (x+1), т.е. имеются коды (31,26); (31,21); (31,16); (31,11); (31,6); (31,1) или с информационной частью на единицу меньше и нет других.

Обратите внимание, что имеются коды, эквивалентные по длине информационной части и кодовому расстоянию, но различающиеся по числу ненулевых коэффициентов образующего многочлена. Например, коды (31,26) d=3 g(x)= x⁵+x²+1 и (31,26) d=3 g(x)= x⁵+ x⁴+x²+ x+1