5.7. КОДЫ, ИСПРАВЛЯЮЩИЕ ПАКЕТЫ ОШИБОК 139

информационных многочленов на g (х) с последующим переме-жением этих слов (п, й)-кода. Точнее, пусть

Ci (х) = h (х) g (х),

С2 (х) = h ix)gix), •

Cj (х) = ij {х) g (х)

представляют собой выбранные кодовые слова. Для формирования слова из кода-перемежения каждое из этих выбранных информационных кодовых слов растягивается вставкой между всеми символами слова /- 1 нулей. Кодовое слово из кода-перемежения получается затем задержкой и сложением этих слов:

с (х) = ci (д:/) + хс (х) + • • • + x--cj (х) =

= 1 (0 g ix) + хй (xi) g (хО + • • • + xi-4j (xi) g (X) =

= ik ix) + xi, (x/) + • • + x-Hj (xi)] g (xi).

Стоящий в квадратных скобках член можно разложить так, что получится информационное слово, составленное из исходных информационных слов методом перемежения. Это слово можно заменить любым информационным словом i (х); следовательно,

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

Замена g (х) на g (х) эквивалентна перемежению / копий кода, порождаемого многочленом g (х).

Кроме найденных на ЭВМ кодов и получающихся из них пере-межением кодов известны также коды, построенные аналитическими методами. Одним из классов таких кодов являются коды Файра. Параметры некоторых кодов Файра приведены в табл. 5.2.

Таблица 5.2

Параметры некоторых двоичных кодов Файра

Определение 5.7.3. Кодом Файра называется исправляющий пакеты ошибок циклический код над GF (q) с порождающим многочленом

g{x)(x--l)p(x),

где р (х) - примитивный многочлен над GF (q), степень т которого не меньше длины t исправляемого пакета и который не делит х- - 1. Длина п кода Файра равна наименьшему целому п, такому, что g (х) делит х - 1.

Теорема 5.7.4. Длина кода Файра равна п = е {2t- 1), где

е - наименьшее целое число, такое, что р {х) делит х - 1. Следовательно, если р (х) примитивен, то для этюго кода

(п, к) = ((9- - 1) {2t- 1), (Г - 1) (2- 1) - m - 2 + 1).

Доказательство. При п = е {2t - 1) возможно несколько разложений многочлена х - 1:

X" - 1 = х - 1 = (д: - 1) Е X,

X- 2-") - 1 = (х2- - 1) Ц x(-l) ft.

Так как р {х) делит х ~ \ , то он делит и х" - 1. Так как он

не делит x~- 1, то он должен делить многочлен 2Jft=oЛ~ Таким образом,

1 = (xz-i - \)р{х)а{х)

для некоторого а [х), и так как не существует меньшего п, для которого имеет место это разложение, то такое п равно длине кода.

В частности, если р (х) - примитивный многочлен степени т, то р {х) делит х - 1 при е - q - 1 и не делит ни при каком меньшем значении е. □

Теорема 5.7.5. Код Файра исправляет все пакеты ошибок длины t и менее.

Доказательство. Этот код способен исправлять все пакеты длины и менее, если никакие два таких пакета, хЬ (х) и хЪ (х), не принадлежат одному и тому же смежному классу. В силу цикличности кода без потери общности можно полагать, что I равно нулю. Предположим, что два пакета длины i или меньше, by (х) и х/Ьа (х), принадлежат одному и тому же смежному классу стандартного расположения рассматриваемого кода. Тогда их разность равна кодовому слову и для некоторого а (х) имеем

I. (л) - xibi (х) а (х) (х2- -\)р (X) (mod х* - 1).

S.7. Коды, ИСПРАВЛЯк)ЩИЕ ПАКЕТЫ ОШИБОК 141

Но многочлен х-- 1 делит х (2-- 1 для всех неотрицательных V. Следовательно, можно записать

(xv(2;-u i)b, (х) = - 1) (modx" - 1).

Складывая эти равенства, получаем

XV (2-1) [bi (х) - х-" (х)] =-- а (х) {х*~ - 1) (mod х" - 1),

или, что эквивалентно,

(2;-I)-(;-I, [xt-% (Х) - x/+(-)-v (2-1);, (X)] =

= а" (х) (х2- - 1) (mod - 1)

для некоторых а (х) и а" (х). Но теперь в каждом из последних двух равенств можно выбрать неотрицательное целое v, меньшее е, так что bg (х) будет умножаться на х, О < k <i t. Таким образом, за счет выбора v получаем

х" (2-" [Ь, (х) - х% (х)] = а {X) (х2- - 1) (mod лг" - 1),

Х- (2-1)-(-1) [x-lfei {Х) - Х% (Х)] =

= а"(х) (x2- - 1) (mcdx" - 1),

где deg b- (х) < t, deg b (x) < t и k < t, так что степень мнсгочлена в квадратных скобках не превышает 2t- 2. Но x*- - 1 должен делить стоящий в квадратных скобках многочлен. Следовательно, или

bi (х) - хЬа (х) = О,

x- b-i {х) - хЬа {х) = 0.

По определению пакета ошибок оба коэффициента Ью и Ь отличны от нуля. Следовательно, k = Q или соответственно k = = t~- 1. В любом случае / = v (2-- 1) и b (х) = Ь (х) = b (х). Остается показать, что b (х) = 0. Но исходное соотношение

ki (х) - xib, (х) = а (х) (х5-> - 1) р (х)

теперь приводится к виду

(XV (2/-1) -l)b{x)=Q (Х) (.V-"- - 1) р (Х).

при о многочлен р (х) не может делить л;(~)-1, так как v меньше е и р (х) не делит х(2-) - 1 ни для одного целого положительного v, меньшего е. Поэтому в левой части равенства многочлен р (х) может делить только b (х). Но степень многочлена b (х) меньше степени многочлена р (х); следовательно, при V о многочлен b (х) равен нулю. Так как, далее, / = v (2 - - 1), то v = О означает, что / = О, а это совместно с уже доказан-