il8 гл. 8. ЦИкЛИЧЕСКИЁ кбдУ

если некоторый многочлен с (лг) принадлежит коду, fo, СоГЛйййб алгоритму деления,

где deg s (х) < &&gg (х), и многочлен

S (X) = с {X) -Q{x)g (х)

является кодовым, так как оба многочлена в правой Части прина* длежат коду, а код линеен. Но степень многочлена s (х) меньше п-наименьшей степени ненулевого многочлена в коде. Следовательно, S (х) = О я с (х) = Q (х) g (х). □

Теорема 5S2.3. Циклический код длины п с порождаюиим многочленом g (х) существует тогда и только тогда, когда g (х) делит х"-1.

Доказательство. Согласно алгоритму деления,

X" - 1 = Q (х) g (х) + S (х),

где степень многочлена s (х) меньше степени многочлена g (х). Тогда

О = R,n , [X" - 1] = Rn [Q ix)gix)] + [s (X)],

и, следовательно,

0 = i?,« , [Q(x)g(x)] + s(x).

Из теоремы 5.2.1 вытекает, что первый многочлен в правой части является кодовым многочленом. Тогда s (х) также является кодовым многочленом степени ниже, чем степень g(x). Единственный такой кодовый многочлен равен s (х) = 0. Таким образом, q (х) делит X" - 1. Далее, каждый многочлен, делящий х"-1, может быть выбран в качестве порождающего многочлена циклического кода. Это завершает доказательство. □

Согласно теореме 5.2.3, для порождающего многочлена g (х) любого циклического кода выполняется равенство

x"-l=g{x)h (х)

при некотором многочлене h (х). Многочлен h (х) называется проверочным многочленом. Каждое кодовое слово с (х) удовлетворяет равенству

Кп 1 [к{х)с{х)] = О,

так как

h (X) с (X) = /г (X) g (х) а (х) = (х" - \) а (х) для некоторого многочлена а (х).

5.2. полиномиальное описание 119

Пусть с (х) обозначает переданное кодовое слово. Это значит, что символами переданного слова были коэффициенты многочлена с (х). Пусть многочлен v (х) обозначает принятое слово, и пусть е (х) = V (х) - с (х). Многочлен е (х) называется многочленом ошибок. Ненулевые коэффициенты этого многочлена стоят в тех позициях, где в канале произошли ошибки.

Представим информационную последовательность в виде многочлена i (х) степени k I Множество информационных многочленов можно отобразить в кодовые многочлены многими удобными способами. Одним простым правилом кодирования является

с (х) = i (х) g (х).

Такой кодер является несистематическим, так как по многочлену с (х) нельзя сразу установить i (х). Систематическое правило кодирования имеет несколько более сложный вид. Идея состоит в записи информации в виде старших коэффициентов кодового многочлена и 1юдборе младших коэффициентов так, чтобы получить допустимое кодовое слово. Иначе говоря, кодовое слово записывается в виде

с (х) = x"-*i (х) -\- t (х),

где t (х) выбирается так, чтобы выполнялось условие

RgM [с{х)] = 0.

Это требование означает, что

RgM lx--i{x)] + RgM li{x)] = G

и степень многочлена t (х) меньше п-k, степени многочлена g (х). Следовательно,

t{x) = -Rg ix)lx"-H{x)],

и правило кодирования является взаимно-однозначным, так как k старших коэффициентов многочлена определены однозначно. И систематическое, и несистематическое правила кодирования дают одно и то же множество кодовых слов, но соответствия между i (х) и с (х) различны.

Определим синдромный многочлен s (х), который будет использован для декодирования, как остаток от деления многочлена V (х) на g (х):

S (X) = Rg[V (х)] = Rg (.) [с {х) + е\х)\ = = Rg(x) [е(х)].

) На самом деле надо было бы говорить, что степень i {х) не выше k - \, но в случаях, подобных данному, когда i (х) является одним из многочленов множества, удобнее указывать максимальную степень э множестве, хотя это и менее точно.

Сг (X) - (х) = [Qi (х) - (х) ] g (х).

По предположению вес каждого из многочленов (х) и е (х) меньше, чем d*/2, так что вес их разности меньше d*. В правой части последнего равенства стоит кодовое слово. Если это слово отлично от нулевого, то вес его не меньше d*, минимального веса в коде. Следовательно, в правой части стоит нуль, и многочлены Ci (х) и (х) равны. Это доказывает теорему. П

Таким образом, задача исправления ошибок сводится к однозначному вычислению многочлена е (х) с наименьшим числом ненулевых коэффициентов, удовлетворяющего условию

S (х) = Rgxy le (х)].

При не очень большом числе входов эта задача может быть решена путем построения таблиц. Для каждого корректируемого многочлена е (х) вычисляется и табулируется многочлен s (х) так, как это показано в таблице, приведенной на рис. 5.1. Эта таблица называется таблицей значений синдромов. Вычисляя s (х) по принятому V (х), декодер находит s (х) в таблице значений синдромов, а затем соответствующий многочлен е (х). Если таблица значений синдромов не очень велика, то практически ее можно реализовать либо с помощью памяти, либо с помощью цепей комбинаторной логикой.

Синдромный многочлен зависит только от е (х) и не зависит ни от с {х), ни от i (х).

Итак, мы ввели следующие многочлены:

порождающий многочлен g (х), deg g (х) = п -

проверочный многочлен h (х), deg h (х) =

информационный многочлен i (х), deg г" (х) = k -• 1,

кодовый многочлен с (х), deg с {х) = п - 1,

многочлен ошибок е (х), deg е (х) = п - 1,

принятый многочлен v (х), deg у (х) = п - 1,

синдромный многочлен s (х), deg s (х) = п - k- 1.

Теорема 5.12.4. Пусть d* - минимальное расстояние циклического кода ё. Каждому многочлену ошибок веса меньше, чем d*/2, соответствует единственный синдромный многочлен.

Доказательство. Предположим, что веса (х) и е (х) меньше, чем d*/2, и что им соответствует один и тот же синдромный многочлен. Тогда»

ei (х) = Qi (х) g{x) +S (х), 62 (х) = (х) g (х) g (х) + s (х)