столбце содержалось по меньшей мере - ошибок для каждого / из мчожества Ui и, как уже известно, оплибок для каждого /, не принадлежаш,его множеству и. Таким образом, разумное условие принятия результата декодирования i-u строки дается следующим неравенством:

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

2 I- (l-cuy/d) + 2 S (coy/dSXdl.

Тогда

S 1-f Б S (l-ffly/d)-2 I (0;/d)>R,-d!.

->"t i"t iVi

Пусть %j равно -1, если /принадлежит Ui, и 1 в противном случае. Тогда

Если, наконец, 1 -2ffly/d5, то неравенство приводится к виду

Теперь все готово для доказательства теоремы.

Теорема 10.3.1. Пусть со. - число позиций, в которых j-u столбец исправленной столбцовым декодером таблицы отличается от принятого слова. Для каждого i существует в точности одно слово строчного кода, удовлетворяющее неравенству

I {dl ~ иу) + S иу <: t.

Здесь Ui - множество номеров j позиций, в которых компоненты i-u строки ксдоеогэ слова отличаются от компонент этой строки в исправленной столбцовым декодером гтблице.

Доказательство. На первом шаге мы докажем, что правиль ное слово строчного кода в i-u строке удовлетворяет выписанному неравенству. На втором шаге мы докажем единственность такого слова.

Шаг 1. Пусть ф - число неправильно декодированных столбцов, и пусть t/ф - множество индексов этих столбцов. Тогда щ - ф столбцов декодированы правильно. Но

S "Vy + £ Vj < t, /€%

и число произошедших в /-м столбце принятого слова ошибок удовлетворяет равенству v. = fo, если /-й столбец декодирован правильно, и неравенству V,- dg - > соу, если /-й столбец декодирован неправильно. Множество U; декодированных столбцов, содержащих в f-й строке ошибку, удовлетворяет включению Ui cz U<s,; следовательно,

а это и доказывает, что для каждой строки кодовое слово удовлетворяет данному неравенству.

Шаг 2. Рассмотрим f-ю строку. Предположим, что Сг и Сг- являются словами строчного кода, и обозначим i-ю строку после «исправления» столбцов через Пусть Zj равно 1, если с совпадает с Li в /-Й компоненте, и = -1 в противном случае. Пусть 5/ обозначает аналогичную величину для кодового слова с. Определим множества

V = {ЦСг1фСг-1 И С,;=(Х;}, = I/ I Сг,- Ф Cr-j И Crj Ф\У.!\.

Каждый индекс / принадлежит одному из этих трех множеств; тогда

п,-1

где величины At, Ay и Aw определены очевидным образом. Число элементов в 7 не превосходит т - di. Если Сг удовлетворяет условиям теоремы, то

/2,-1

£ IjUj = Ат Av~ Aw>n\~d\,

и, следовательно, Ау - Л vv > 0.

Теперь рассмотрим кодовое слово с. Мы имеем

£?;•«/ = £ %щ + £ л- £ Ш«/ = Рт-Ау + в,у,

/=0 ifT jV ifW

где величина Bw определена очевидным образом и па множестве V выполняется равенство с-у =/= yi,-. Но Вw Aw, и, как мы видели, Aw л1/ •< 0. Следовательно, «.-1

1 Iflj < Лт- - + Л К< Лт- < m - d\,

так что Сг не удовлетворяет неравенству. □

Опишем теперь практический способ вычисления такого кодового слова. Мы уже знаем, как строить декодеры для исправления ошибок и стираний с жестким решением. К любому из таких декодеров присоединим внешнюю цепь обработки. По имеющейся таблице декодированных столбцов для i-u строки построим пробную цепочку векторов, полученных при жестком декодировании ошибок и стираний. Индексы упорядочим следующим образом: w, % -- :::з или а, < aj < ... < а/. Для каждого / из интервала от О до dt - 1 будем стирать / компонент с наибольшими значениями м. Такое построение приведет к вектору Li<" со стираниями. Декодируем этот вектор декодером для исправления ошибок и стираний и проверим результат декодирования Сг на соответствие условию, даваемому теоремой 10.3.1. Если он удовлетворяет этому условию, то с будет кодовым словом для данной строки; в противном случае увеличим /и повторим процедуру. Следующая теорема доказывает, что описанная процедура всегда приводит к кодовому слову.

Теорема 10.3.2. Если кодовое слово с удовлетворяет неравенству

п,-1

то хотя бы для одного I выполняется условие

lbbP>m-~d\,

М:> = ьФ = ... = ь};) = о, ь = 111 = ...= ==1,

и, следовагпельно, с представляет собой единственное кодовое слово, вычисляемое исправляюищм ошибки и стирания декодером.

Доказательство. Доказательство достаточно провести для всех / от О до п\, так как при I d] утверждение теоремы, очевидно, не может выполнятьс?},