3.5.3. Декодер pgz

Впервые этот алгоритм был рассмотрен Питерсоном. Решение ключевого уравнения (3.16) может быть найдено с помощью стандартной техники решения системы линейных уравнений. Это решение дает коэффициенты σ(х). Применению этой техники мешает только то, что неизвестно действительное число ошибок в принятом слове. По этой причине приходится проверять гипотезу о том, что действительное количество ошибок в принятом слове равно v. Предположим, что не все синдромы S_i, 1 ≤ i ≤2t равны нулю. Очевидно, что принятое слово совпадает с одним из кодовых, если все синдромы равны нулю. Тогда процедура декодирования на этом завершается!

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

(3.22)

и сравнивает его с нулем. Если определитель равен нулю, то действительное число ошибок меньше, чем предполагалось. Значение i уменьшается на единицу и снова проверяется определитель. Процедура повторяется, если это необходимо, пока i >1. Как только окажется, что определитель не равен нулю, вычисляется обратная матрица для матрицы синдромов и вычисляются значения σ₁ , σ₂ ,..., σ _v, где v = i. В случае, когда ∆i = 0, для i = 1, 2,..., t_d, декодирование считается безуспешным и регистрируется обнаружение неисправляемой комбинации ошибок.

Пример 35. В этом примере полином локаторов ошибок для (15, 5, 7) БЧХ кода из Примера 34 находится с помощью PGZ алгоритма. Предположим для начала, что имеется i=t_d = 3 ошибки. Определитель ∆₃ вычисляется (с использованием алгебраического дополнения) следующим образом:

Так как ∆₃ ≠ 0, то подтверждается предположение о том, что в принятом слове три ошибки. Подставляя синдромы, найденные в Примере 34, в ключевое уравнение (3.16), получаем:

(3.23)

Напомним, что (∆₃)^-1 = a^-14 = а. Решение уравнения (3.23) имеет вид:

Таким образом, получили что совпадает с результатом, полученным по алгоритму БМ в Примере 34.

3.5.4. Евклидов алгоритм (еа)

В основе этого алгоритма лежит хорошо известная процедура нахождения наибольшего общего делителя (НОД) двух полиномов (или целых чисел). Ниже рассматривается применение ее для декодирования БЧХ кодов.

Определим полином значений ошибок как Λ(х) = σ(x)S(x), где синдромный полином имеет вид

(3.24)

Из уравнения (3.16) следует, что

(3.25)

Задача декодирования может быть переформулирована как задача определения многочлена Λ(х), удовлетворяющего уравнению (3.25). Это решение может быть найдено применением расширенного алгоритма Евклида к многочленам r₀(x) = x^d, d = 2t_d+ 1 и r₁(x) = S(x). Если нa j-ом шаге алгоритма получено решение

такое, что deg[r_j(x)] ≤ t_d, то Λ(х) = r_j(x) и σ_i(x) = b_j(x). Заметим, что для задачи декодирования полином а_i(х) не представляет интереса, так как решение (3.25) ищется по модулю х^d.

Расширенный алгоритм Евклида вычисления НОД состоит в следующем.

Расширенный алгоритм Евклида: Вычисление НОД(r₀(x), r₁(x))

Вход: r₀(x), r₁(x), deg[r₀(x)] > deg[r₁(x)]

Начальные условия: а₀(х) = 1, b₀(х) = 0, а₁(х) = 0, b₁(х) = 1.

На шаге j (j ≥ 2) применить длинное деление к многочленам

•Вычислить

a_j(x) = a_j-2(x)-q_j(x)a_j-1(x), b_j(x) = b_j-2(x)-q_j(x)b_j-1(x)

•Остановить вычисления на итерации last = j_last, когда deg[r_last(x)]=0.

Выход: НОД(r₀(х), r₁(x)) = r_k(x), где к наибольшее ненулевое целое такое, что r_к(х) ≠ 0 и k <j_last.

Пример 36. В этом примере вычисляется полином локаторов ошибок о(х) для (15, 5, 7) кода БЧХ из примера 34 по алгоритму Евклида.

• Начальные условия:

Так как deg[r₄(x)] = 1 ≤ 3, алгоритм останавливается.

Очевидно, что многочлен

имеет те же самые корни, что и многочлены, найденные алгоритмами ВМА и PGZ (см. Пример 37 ниже), и отличается только константным множителем.

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