Коды, исправляющие ошибки
Содержание | Назад | Вперед | Лабораторные | О курсе

  Содержание



 

9.2. Построение циклических кодов с большим кодовым расстоянием

Пусть a - примитивный элемент поля GF(2m), n = 2m-1 и g(x) - порождающий многочлен циклического кода длины n. Согласно теореме 8.1, если мы хотим построить код с расстоянием не меньше, чем некоторое число d, то в качестве g(x) мы должны выбрать многочлен, корнями которого являются элементы  a, ..., ad-1. Коды с такими порождающими многочленами часто называют БЧХ-кодами.

Многочлен с описанными выше свойствами можно построить на основе минимальных функций элементов a, ..., ad-1 в поле GF(2m). Минимальной функцией элемента bÎGF(2m) называется многочлен наименьшей степени с коэффициентами 0 и 1, корнем которого (в поле GF(2m)) является b. Известно, что любая минимальная функция является неприводимым многочленом, т. е. не делится ни на один многочлен, степень которого не равно 0 и меньше степени данной минимальной функции. Более того, известно, что степень минимальной функции для элементов поля GF(2m) не превосходит m.

Пример: Рассмотрим поле Галуа GF(23), построенное по модулю неприводимого многочлена x3 + x + 1. В данном случае  с примитивным элементом является элемент a = 2 (010). Непосредственной проверкой можно убедиться, что минимальной функцией этого элемента будет многочлен x3 + x + 1, так  как 2 не является корнем ни одного из неприводимых многочленов x, x+1, x2+x+1 степени меньше 3.

Таблицы минимальных функций известны. Поэтому искомый порождающий многочлен кода можно строить как НОК (наименьшее общее кратное) минимальных функций для элементов a, ..., ad-1. Однако прежде чем привести пример такого кода, мы покажем, что в случае двоичных кодов из списка элементов можно исключить все четные степени элемента a.

Утверждение 9.2. Если bÎ GF(2m) есть корень многочлена s(x) с коэффициентами 0 и 1, то b2 также является корнем этого многочлена.

Доказательство. Напомним, что в поле GF(2m) для любых элементов a и b справедливо (a + b)2 = a2 + b2, и c2 = c для cÎ{0,1}. Пусть s(x) = sn-1xn-1 + s n-2xn-2 + ...+ s0. Так как b - корень многочлена s(x), то sn-1b n-1 + sn-2b n-2 + ...+ s0 = 0. С другой стороны, sn-1(b2) n-1 + sn-2(b2) n-2 + ...+ s0 = (sn-1)2(b2) n-1 + (sn-2) 2(b2)n-2 + ...+ (s0)2  = (sn-1b n-1 + s n-2b n-2 + ...+ s0)2 = 0, т. е. b2 - корень многочлена s(x).

Теорема 9.3. 1. Пусть GF(q) - конечное поле Галуа. Для любого n = q - 1 и любого t < n/2 существует циклический код, исправляющий все комбинации из t или менее ошибок, число проверочных символов которого не превосходит величины 2mt. 2. Для любого n = 2m - 1 и любого t < n/2 существует двоичный циклический код, исправляющий все комбинации из t или менее ошибок, число проверочных символов которого не превосходит величины mt.

Доказательство части 1 теоремы следует из того факта, что порождающий многочлен g(x) циклического кода можно выбрать как НОК минимальных функций для элементов a, ..., a2t, степень каждой из которых не превосходит числа m. Как известно, многочлен степени k порождает циклический (n,n-k)-код, т. е. код с k проверочными символами. При построении двоичного циклического кода многочлен g(x) можно выбрать как НОК минимальных функций только для нечетных степеней элемента a, т. е. для t элементов a, ..., a2t-1.

Пример: Построим порождающий многочлен двоичного кода длины 15, который исправляет 2 ошибки. С этой целью построим  поле GF(24) по модулю неприводимого многочлена x4 + x + 1. Элемент 2 (0010) является примитивным элементом поля. Согласно теореме 8.3, построим минимальные функции для элементов 2 (0010) и 8 (1000). Такими функциями являются многочлен x4 + x + 1 (для элемента 2) и многочлен x4 + x3 + x2 + x + 1 (для элемента 8). НОК этих многочленов равно их произведению, т. е. циклический (15,7)-код порождается многочленом x8 + x7 + x6 + x4 + 1, имеет 27 кодовых слов, 8 проверочных символов и исправляет любую комбинацию из двух или менее ошибок.