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

1) число различных лежащих в GF (д") корней Л (х) отлично от L;

2) значения "ошибок не лежат в поле символов кода.

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

В § 9.6 будут рассмотрены способы декодирования кодов БЧХ с исправлением некоторых конфигураций более чем / ошибок; здесь же мы обсудим противоположный случай, когда число исправляемых ошибок ограничивается конструктивным расстоянием. На практике такое декодирование используется для значительного уменьшения вероятности ошибки декодирования, платой за которое является увеличение вероятности отказа от декодирования.

Для уменьшения вероятности неправильного декодирования число исправляемых декодером ошибок можно ограничить числом t, таким, что 2t + 1 будет строго меньше d* (при четном d* это выполняется всегда). В этом случае декодер всегда будет обнаруживать неисправляемую конфигурацию ошибок при условии, что число V действительно случившихся ошибок удовлетворяет неравенству

t + V <d*.

поскольку для перехода кодового слова в неправильную сферу декодирования должно произойти не менее d* - t ошибок.

В таком декодере хорошо применять алгоритм Берлекэмпа- Месси. Для вычисления Л (х) необходимо сделать 2/ итераций по алгоритму Берлекэмпа-Месси. Остальные т - / итераций, т = = d* - 1 - требуются для проверки равенства нулю невязок Д,. Если хотя бы при одной из этих дополнительных итера-

ций Дг не равняется нулю, то принятое слово объявляется словом, в котором произошло более t ошибок.

Правомерность описанной процедуры доказывается следующей теоремой.

Теорема 7.5.3. Пусть произошло не более т ошибок и заданы Sj при j=l,...,t+xur>t. Пусть, далее, (Lt, Л (х)) - регистр сдвига с линейной обратной связью, генерирующий последовательность Sj, / = 1, ..., 2t, и

причем Дг равняются нулю при г = 2t -\- \, t х и Lt < t. Тогда произошло не более t ошибок и Л<2> (л:) будет являться правильным многочленом локаторов ошибок.

Доказательство. В условии теоремы заданы компоненты синдрома Sj для / = 1, t -f- т. Если бы имелись еще т - t компонент синдрома 5/, j = t -\-\, ...,2х, то можно было бы исправлять т ошибок, т. е. любую конфигурацию предполагаемых ошибок Вообразим на минуту, что эти дополнительные компоненты сообщены нам добрым волшебником или переданы по неведомому добавочному каналу. Тогда, используя алгоритм Берлекэмпа-Месси, можно найти многочлен локаторов ошибок, степень которого равна числу ошибок. Но при 2/-й итерации Lgt <: и по предположению Д равняется нулю при г = 2/ -f--f 1, / -fx. Поэтому значение L не будет меняться до итерации с номером t -{-X -{-\, и, следовательно, по правилу изменения I

Z-2t + Т -f 1) - Lgt (/ + т -I- 1) - / = т -f 1,

а это противоречит предположению о том, что произошло не более т ошибок. □

7.6. ДЕКОДИРОВАНИЕ ДВОИЧНЫХ КОДОВ БЧХ

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

Дальнейшее упрощение декодирования менее очевидно; намек на его возможность содержится в примере, приведенном в табл. 7.4.

Iv{a)

- О/.

i=i L/=i

что следует из теоремы 5.3.3. Получим для нескольких начальных значений г алгебраические выражения для коэффициентов Л*") (х). Следуя алгоритму, приведенному на рис. 7.5, и используя справедливые для всех двоичных кодов равенства S4 = S = S, получаем

Ai = Si,

* Д2 = S2 + S? = 0, A3 = S3 -[- SjSg,

Д4 = Si + S1S3 + 88283 -ь S = 0,

An)(x) = SiX + l,l.

A(2)(x) = SiX+l,

A-> (x) = (SrSs + S2) x f S,x + 1.

Отсюда следует, что для любых двоичных кодов БЧХ Да и Д4 всегда равняются нулю. Бесконечное продолжение этого прямого пути для вычисления других значений синдромов с четными номерами невозможно. Вместо этого сформулируем общий результат, показыварощий, что Д, = О для всех четных г.

Теорема 7.6.1. Пусть в расширении поля GF (2) задана произвольная последовательность 8у, S.,, Sgv-i. удовлетворяющая условию 821 = S/ для 2/ < 2v - 1; пусть также задан регистр сдвига с линейной обратной связью Л (х) и выполняются равенства п-г

8jlAiSj „ у = V, 2v-1.

Если следующий член последозательности задается равенством

Sav - 1 AjSav-i,

Sov - 8%.

Нетрудно заметить, что значение всегда обращается в нуль при четных итерациях. Если это происходит всегда при декодировании двоичных кодов, то итерации с четными номерами можно пропускать.

В этом параграфе будет доказано, что дело обстоит действительно так. Доказательство основывается на следующем факте: в поле GF (2) синдромы с четными номерами определяются синдромами с нечетными номерами по формуле