dV)-Koda, не содержит одновременно слова веса не больше t при t = (ddl - 1)/2 и слова, представляЮи{его собой пакет ошибок длины не больше max (n,ti, nt при t, < (d1 - l)/2 ы (dl - l)/2.

Доказательство. Для определенности предположим, что «21 > n-ytzH что код считывается по столбцам. Если пакет ошибок длины не более «21 и отличная от него конфигурация ошибок веса не более Улежат в одном смежном классе, то их разность представляет собой кодовое слово. Вес каждой ненулевой строки такого кода равен не меньше d]. Так как длина пакета не превосходит nty, то каждая ненулевая строка может содержать не более ошибок из этого пакета и, следовательно, должна содержать по меньшей мере d*i - ti других случайных ошибок. Таким образом, t случайных ошибок разбросаны самое большое по [t/{d\ - /i)J строкам. Следовательно, кодовое слово содержит не более этого количества ненулевых строк, в каждой из которых имеется не более ty ошибок, принадлежащих пакету. Полное число ошибок не превосходит L/(rf1 - i)J ti + t, но, поскольку dt- ti больше ty, это число 1у;еньше 2t. Это противоречиг тому, что минимальный вес кода равен по меньшей мере 2 -Н 1 и поэтому такое кодовое слово не может существовать, и, следовательно, рассматриваемые пакет ошибок и конфигурация случайных ошибок не могут принадлежать одному и тому же смежному классу. □

Код-произведение можно использовать в соответствии с доказанной теоремой. Декодер для такого кода можно строить в виде составного декодера, содержащего декодер для исправления пакетов ошибок и декодер для исправления случайных ошибок, каждый из которых исправляет требуемое число ошибок и обнаруживает неисправляемые конфигурации ошибок. При этом либо оба декодера укажут одну и ту же конфигурацию ошибок, либо успешно декодирует только один из них; в последнем случае второй декодер укажет неисправляемую конфигурацию ошибок. Иногда декодер для исправления случайных ошибок может указать все пакеты ошибок. В § 10.3 будет описан декодер для произведения двух кодов БЧХ, исправляющий все случайные ошибки в пределах конструктивного расстояния.

10.2. КИТАЙСКИЕ ТЕОРЕМЫ ОБ ОСТАТКАХ

Когда можно однозначно определить целое число, если заданы только его вычеты по модулям нескольких целых чисел? Ответ на этот вопрос был известен еще в древнем Китае. Мы сейчас рассмотрим эту теорему, а также ее современные аналоги, относящиеся к множеству полиномиальных модулей. Китайская теорема об остатках будет доказана в два этапа. Сначала мы докажем единственность решения, а затем его существование.

Теорема 10.2.1. Для заданного множества целых положительных попарно взаимно простых чисел т-, пц, т и множества неотрицательных целых чисел q, Cg, с при с <С система сравнений

Ci = с (mod mi), i = \, k,

имеет не более одного решения с в интервале О < с<: Yliimi.

Доказательство. Предположим, что с и с являются двумя лежащими в рассматриваемом интервале решениями. Тогда

с - Qimi + Ci и с = Qlmc + с,-,

и, следовательно, с - с кратно для каждого i, а так как /П; попарно взаимно просты, то с - с кратно П,/п,-. Но число с - с лежит между - (Flfimj - l) и Ylimc - 1. Единственным положительным числом, удовлетворяющим этим условиям, является с - с = 0. Следовательно, с = с. □

Для того чтобы практически найти решение выписанной в теореме 10.2.1 системы сравнений, воспользуемся следствием 4.1.4 из алгоритма Евклида, согласно которому в кольце целых чисел НОД (г, s) = аг + bs для некоторых целых а и Ь.

Для заданного множества попарно взаимно простых положительных целых чисел ти Шг, т. положим М = Ylimi и М, - М/т,-. Тогда НОД (М, mt) = I, и, следовательно, существуют такие целые Ni и п, что

NjMi -\-nimi = 1.

Теперь можно доказать следующую теорему.

Теорема 10.2.2. Пусть М = П,-=,,т£ - произведение попарно взаимно простых положительных целых чисел, пусть Mi = М/т-,, и пусть Ni удовлетворяют равенству NjMi -Ь «г/П: = 1. Тогда единственным решением системы сравнений

Ci = с (mod Ш;), i = 1, k,

будет

с = £ CiNiMi (mod М).

Доказательство. Поскольку мы уже знаем, что решение рассматриваемой системы сравнений единственно, надо только доказать, что выписанное выше с действительно является решением. Но ft"

с == S c,.NrM,. (modm,) =CiNiMi [(modm;),

r=i . -

ибо Ш; делит Mj. при г =f= i. Наконец, так как N:Mi + гг = 1> то NiM; = 1 (mod nii) и с = С; (mod m,), что и завершает доказательство. □

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

Теорема 10.2.3. Для заданного множества попарно взаимно простых многочленов т (х), пц (х), т (х) и множества многочленов с {х), Са (х), Ch (х), таких, что deg Ct (х) < deg т, (х), система сравнений

Ct (х) = с (х) (mod Ш; (х)), i = 1, k,

имеет не более одного решения с (х), удовлетворяющего условию

degc(x)< Д] degmi(x). • t=i

Доказательство. По существу доказательство совпадает с доказательством теоремы 10.2.1. Предположим, что имеются два решения, а именно

c(x) = Qi(x)m;(x) + c,(x)

с {x) = Qi{x)mi{x)ci{x),

так что разность с (х) - с (х) кратна многочлену т (х) для каждого I. Тогда многочлен с (х) - с (х) кратен и многочлену nf=,,m,- (х), причем

k

deg [с (х) - с (х)] < deg П т-, (х)

Lt=i

Следовательно, с (х) - с (х) = О, и доказательство закончено. □

Так же как и в кольце целых чисел, в кольце многочленов над произвольным полем выполняется равенство

НОД \г (х), S (х) ] = а (х) г (х) + {х) s (х)

для некоторых а (х) и (х). Для заданного множества попарно взаимно простых т (х) положим М (х) = П*;=,т;. (х) и Mi (х) == = M{x)/mi (х) и допустим, что Ni (х) и (х) удовлетворяют равенствам Ni (х) Ml (х)Т-]- Hi (х) Ш; (х) = 1; Г согласно следствию 4.3.7, такие многочлены Л; (х) иП; (х) всегдасуществуют.

Теорема 10.2.4. Пусть М (х) = Пг=,т( (х) - произведение попарно взаимно простых многочленов, и пусть Mi (х) == М (x)/mi (х)