по определению параметра такое слово единственно, разыскивается любое подходящее слово. Нам нужно только найти какое-либо решение, так как мы знаем, что оно лишь одно.

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

Как мы видели, частный класс кодов БЧХ допускает многие сильные алгоритмы декодирования. Все они могут быть обобщены на случай декодирования ошибок и стираний. Для простоты будем полагать /о = 1.

Пусть Vi, i == О, п - 1, обозначают символы принятого вектора. Предположим, что стирания произошли в позициях ij, ip. Во всех этих позициях принятое слово содержит пробелы, которые мы сначала заполним нулями. Определим п-мерный вектор стираний, положив символы в стертых позициях равными fi., 1=1, р, а в остальных позициях равными нулю. Тогда

Vi = Ci-\-et-i-fi, i = 0, ... , n~ \.

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

\piVi = [Ci + -{- fi) = xiCi -f iCi.

Определим модифицированное принятое слово равенством Vi = ~ "ffiVi, модифицированный вектор ошибок равенством Ci = = "iCi и модифицированное кодовое слово равенством q = Ci. (Модифицированный вектор ошибок содержит ошибки в тех же позициях, что и исходный вектор ошибок е.) Тогда последнее равенство приводится к виду

Щ = Q -f в].

Теперь задача состоит в декодировании вектора v и сводится к задаче вычисления вектора е, которую мы умеем решать при достаточном числе компонент синдрома.

Следующий шаг построения алгоритма состоит в выборе вектора W, основанном на некоторых проводимых в частотной области рассуждениях. Пусть Ui = а для / = 1, р обозначают локаторы стираний. Определим многочлен локаторов стираний равенством

к=0 t=l

Этот многочлен специально определен так, чтобы компоненты ipj обратного преобразования вектора W были равны нулю, как только fi =7%0. Следовательно, \pifi = 0. В частотной области это дает

V =(Т * С) + Е.

Но вектор Ч*" отличен от нуля только на блоке длины р + 1, а по построению кода БЧХ вектор С имеет нулевые компоненты в блоке длины 2t. Следовательно, свертка Ч*" * С равна нулю в блоке длины 2t - р. Полагая = Vj, определим на этом блоке модифицированный синдром. Тогда

S] = {W*\l)j = E],

что задает достаточное число компонент синдрома для исправления модифицированного вектора ошибок.

Итак, точно так же, как в случае наличия только ошибок (при условии, что их не более (2 - р)/2), по этим 2t - р известным компонентам вектора Е можно найти многочлен локаторов ошибок Л {х). Коль скоро многочлен локаторов ошибок известен, можно скомбинировать его с многочленом локаторов стираний и дальнейшее декодирование проводить так же, как и в случае наличия только ошибок. Чтобы проделать это, определим сначала многочлен локаторов ошибок и стираний:

Л {X) = (х) Л {X).

Обратное преобразование Фурье вектора Л содержит нуль в позиции каждой ошибки и каждого стирания. Таким образом, = О, если ei Ф О или ft ф 0. Следовательно, (е -f Д) = О,

Л * (Е f F) = О,

и многочлен Л отличен от нуля в блоке длины, не превышающей V + Р + 1- Следовательно, используя известные компоненты вектора Л и 2 известных компонент вектора Е -f F, можно воспользоваться этим содержащим свертку уравнением для того.

Многочлен локаторов ошибок вычисляется с помощью п итераций при начальных условиях Л°(х) = Б°(х) = 1.

Но что произойдет, если заменить начальные условия на Л°Чх) = Б"**(х) = ¥(х)? Заметим, что в этом случае

Л (х) ¥ (х) = Л- (х) ¥ {х) - А.хБ- {х) Ч (х),

В (х) ¥ (X) = (1 - б,) хБ""" (X) (х) -Ь

-\-ЬА7А~\х)Ч{х).

Если мы временно определим Л*" (х) = Л*" (х) ¥ (х) и будем вычислять невязку Дг по формуле

/-.=0 /=0

лГ> =

/е=0

1=0 \fe=0 / "

чтобы рекуррентно продолжить вектор Е --F до всех п компонент. Затем вычисляются

С, = 1/,-(£, -\-Fi).

Обратное преобразование Фурье завершает декодирование.

Вычисление многочлена локаторов ошибок по модифицированному значению синдрома можно выполнить с помощью алгоритма Берлекэмпа-Месси. Можно, однако, сделать это гораздо лучше, если скомбинировать несколько шагов. Идея алгоритма Берлекэмпа-Месси состоит в рекуррентной процедуре вычисления многочлена Л (х) за 2t итераций, начиная с оценок Л** (х) = 1 и Б<°> (X) = 1.

В случае наличия стираний в уравнении для невязки компоненты синдрома заменяются компонентами модифицированного синдрома: