7.7. ДЕКОДИРОВАНИЕ С ПОМОЩЬЮ АЛГОРИТМА ЕВКЛИДА

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

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

Для двух произвольных многочленов и повторим алгоритм Евклида в более удобной для нас матричной форме, используя для алгоритма деления запись

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

будет многочлен

причем найдется такой скаляр у, что

где таково, что

Доказательство. Поскольку то в конце концов при некотором и процесс обязательно закончится. Таким образом,

откуда следует, что любой делитель многочленов делит также и Легко проверить, что

и поэтому

так что многочлен должен делить а следовательно, и Отсюда получаем, что делит и сам делится на таким образом,

Далее

и, следовательно,

Это доказывает последнее утверждение теоремы. О

В теореме 7.7.1 найден смысл матричных элементов Можно интерпретировать и два остальных элемента,) для чего нам потребуется обратить матрицу Напомним, что

Из этого равенства видно, что определитель матрицы равен Обратная матрица запишется в следующем виде:

Следствие 7.7.2. Многочлены полученные с помощью алгоритма Евклида, удовлетворяют равенствам

Доказательство. Используя выписанное выше выражение для обратной к матрицы, получаем

откуда и вытекает утверждение следствия.

Опишем два совершенно различных способа использования алгоритма Евклида при декодировании; один из них будет приведен ниже, а другой — в § 9.1.

Напомним, что синдромный многочлен, многочлен Локаторов ошибок многочлен значений ошибок связаны соотношением

и условиями Постараемся теперь использовать доказательство алгоритма Евклида для решения этого уравнения относительно и Из этого доказательства легко установить, что

и поэтому

Если положить и то последнее равенство можно рассматривать как уравнение, которое нам необходимо решить. Это уравнение выполняется для каждого Чтобы решить поставленную задачу, необходимо найти такое значение (если оно существует), при котором Удовлетворить последним условиям можно, выбрав равным такому значению при котором

Поскольку и степень строго убывает с возрастанием эти неравенства определяют единственное значение

По определению получаем

Степень возрастает с возрастанием Остается лишь показать, что

Это неравенство доказывается с помощью обращения матрицы Сначала напомним, что

откуда следует что Напомним также, что Из этих неравенств и матричного равенства

вытекает, что поскольку получаем

где неравенство следует из определения

Теперь мы почти полностью доказали следующую теорему. Теорема 7.7.3. Пусть заданы где синдромный многочлен кода БЧХ, исправляющего t ошибок, и пусть Будем решать следующие рекуррентные уравнения до тех пир, пока не будет выполнено неравенство :

Тогда многочлены

где , являются единственным решениен уравнения

удовлетворяющим условиям

Доказательство. Деление на А обеспечивает равенство С другой стороны, из предыдущих рассуждений следует, что последнее уравнение и все условия удовлетворяются. Единственность полученного решения вытекает из того факта, что для синдрома кода БЧХ, исправляющего ошибок, существует только одно такое решение.

После того как и найдены, декодирование можно завершить любым из методов, предложенных для алгоритма Берлекэмпа-Месси. Блок-схема соответствующего декодера представлена на рис. 7.8, где декодер завершается алгоритмом Форни (хотя его можно завершить и иначе).

Рис. 7.8. (см. скан) Декодирование кодов БЧХ при помощи алгоритма Евклида.