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

и Ni (х) удовлетворяют равенствам Ni {х) Mi [х) + (х) /Л; (х) = = 1. Тогда единственным решением системы сравнена й

Ci (х) = с (х) (mod т,- (х)), i = 1, .... k,

является

с (X) = S Ci (X) W Mi (X) (mod М (х)).

Доказательство. Так как мы уже знаем, что рассматриваемая система сравнений имеет не более одного решения, то нам надо только доказать, что выписанное выше с (х) действительно является решением. Но

с (х) = Cl {x)Ni (X) Mi (х) (mod (x)),

ибо mj (x) делит Mr (x), если r Ф i. Наконец, так как

Ni(x)Mi{x)-ni{x)mi{x)=U

то Ni (x) Mi (x) = 1 (mod (x)) и с (x) = с* (x) (mod m (x)), что и завершает доказательство. □

Китайская теорема об остатках позволяет установить условия, при которых произведение циклических кодов является циклическим KOT.OM.

Теорема 10.2.5. Если длины и щ циклических кодов ё и ё взаимно просты, то при соответствующем расположении компонент в кодовом слове код-произведение также являгтся циклическим.

Доказательство. Если О < t < % - 1 и О < Г < «2 - 1, то, согласно китайской теореме об остатках, имеется единственное целое число / (t, i), лежащее в интервале О <: / (t, i) <: пп - 1 и удовлетворяющее сравнениям

/ (t, V) = i (mod

/ (t, i) = i (mod П2).

Перепишем кодовое слово с (х, у) в следующем порядке:

C{Z) = и С(/ mod /г,) (/ mod /=0

Чтобы увидеть, что такое множество слов с {z) образует циклический код, достаточно заметить, что в указанной записи zc (2) (mod 2"» "2 - 1) соответствует многочлену

хус (х, у) (mod X" - 1) (mod y - 1).

Так как этот многочлен является кодовым словом, то и zc (2) (mod2"i"2 - 1) является кодовым словом. □

Взаимосвязь между с (z) и с {х, у) можно лучше пояснить с помощью следующей двумерной таблицы:

Cflo Cot • Co(>j, I)

Сю Ci2 • • • Cum-i)

Си- =

Коэффициенты многочлена с (z) получаются при считывании элементов этой таблицы вдоль диагонали, начиная с со и возвращаясь после каждого достижения края таблицы, так, как если бы таблица была продолжена периодически в обоих направлениях. Так как Пу и «2 взаимно просты, такая расширенная диагональ не пройдет дважды через один и тот же элемент до тех пор, пока все «12 элементов не будут пройдены.

10.3. ДЕКОДИРОВАНИЕ КОДА-ПРОИЗВЕДЕНИЯ

Если V < {d\d2 - 1)/2, то код-произведение способен исправлять V ошибок. Такая теоретическая корректирующая способность кода, однако, мало что дает без практических алгоритмов декодирования. В данном параграфе описывается такой алгоритм декодирования, основанный на исправляющем только ошибки под-алгоритме для одного кода-сомножителя и на исправляющем ошибки и стирания подалгоритме для другого кода-сомножителя. Такие декодеры были описаны только для кодов БЧХ, и, следовательно, мы будем говорить только о произведениях кодов БЧХ.

Рассмотрим случай, когда d\d2 нечетно, и без ограничения общности предположим, что dld]. Задача декодера, исправляющего в произведении кодов БЧХ только случайные ошибки, состоит в вычислении некоторого кодового слова, находящегося от принятого слова не далее радиуса упаковки t = (did - 1)/2, так как такое слово единственно. Декодер состоит из внутреннего декодера для кода БЧХ и внешней цепи обработки, содержащей произвольный подходящий декодер для кода БЧХ, исправляющий ошибки и стирания. Сначала опишем упрощенный вариант декодера, потом улучшим его, а затем докажем, что он выполняет нужные исправления.

Сначала декодер должен «исправлять» каждый столбец. Для алгоритма декодирования безразлично, передается ли кодовое слово по строкам или по столбцам, но при обсуждении этого алгоритма удобнее предполагать, что кодовое слово передается по столбцам, и воспринимать столбец как отдельно декодируемый

подблок. Позже, при декодировании строк, неправильные подблоки будут выявлены и исправлены.

Пусть в /-М столбце принятого слова произошло v- ошибок; тогда

Первый шаг состоит в использовании БЧХ-декодера для исправления каждого столбца. Для каждого /-го исправленного столбца указывается число со сделанных исправлений. Это число представляет собой вес оценки (/) вектора-столбца ошибки и равно v-, если декодирование произведено правильно. Если обнаружена неисправляемая ошибка, то столбец стирается. Нестертые столбцы с наибольшими значениями чисел рассматриваются строчным декодером как наименее надежные.

Затем исправляющий ошибки и стирания БЧХ-декодер применяется для исправления каждой строки. Теперь, однако, имеется сторонняя информация, которую можно использовать для правомерного стирания дополнительных столбцов. Сначала, игнорируя эту стороннюю информацию, декодируем, как удастся, все строки, начиная с первой. Строчный декодер может потерпеть неудачу и может внести ненулевую конфигурацию ошибок. Любой из этих случаев означает, что некоторые столбцы были декодированы неправильно. Требуется какое-то правило, указывающее, что нужно делать: принять декодированную строку или стереть наименее надежный столбец и попытаться декодировать строку сначала.

Основную теорему мы докажем сначала в предположении, что столбцовый декодер не производит никаких стираний. Впоследствии эта теорема будет использована и при наличии стираний с помощью простого уменьшения числа d* на число стертых столбцов. Рассматриваемые методы доказательства будут использованы в гл. 15, когда мы будем изучать декодирование с мягким решением.

Что можно сказать о строчном декодере, если дано, что код-произведение может исправлять t = {dldl - 1)/2 ошибок и что столбцовый декодер уже исправил to ошибок в /-м столбце? Предположим, что i-я строка декодирована и для нее вычислена оценка \ej (/)} вектора-строки ошибки. Обозначим через Ui множество индексов /, для которых ej (i) отлично от нуля. Если / принадлежит множеству f/j, то /-й столбец продекодирован неправильно; в /-М столбце имеется по меньшей мере dl ошибок, среди которых

могли быть внесены столбцовым декодером, причем со меньше dl. Следовательно, если строчному декодеру удастся правильно найти конфигурацию ошибок, то в исходном принятом слове в /-м