7.1.4. Способы кодирования и декодирования рс-кодов

Способы кодирования и декодирования РС-кодов достаточно хорошо разработаны в теоретическом и реализационном плане. Их основу составляют процедуры исправления стираний, ошибок и совместного исправления ошибок и стираний. Рассмотрим процедуры, нашедшие применение в отечественной технике передачи данных.

Рассмотрим процедуру декодирования с исправлением ошибок, известную [ 4 ] как алгоритм Форни.

Пусть в приемник аппаратуры передачи данных (АПД) поступила кодовая комбинация РС-кода

C(x)=f(x)+e(x),

где f(x) – переданная передатчиком (АПД) кодовая комбинация, в которой в процессе передачи по каналу связи произошло v ошибок , отображаемых многочленом e(x) степени . Каждый ненулевой компонент e(x) описывается парой элементов: Y_i – величина ошибок и X_i – номер позиции ошибки (локатор ошибки). Y_i, X_i – элементы GF(q), и элемент X_i=αⁱ,αⁱ Є GF(q).

Для описания ошибок используются:

1. Многочлен локаторов ошибок:

имеющий корни X_i^–1, i = 1, …,v взаимные к локаторам ошибок, т. е. X_i^–1∙αⁱ = 1.

2.Синдромный многочлен

–многочлен бесконечной степени, для которого известны только 2t коэффициентов для поступившей комбинации РС-кода.

Здесь – элемент синдрома, α^j – корень порождающего многочлена РС-кода. Значения S_j e(α^j) задаются проверками:

S_j=C(α^j)=f(α^j)+e(α^j)=e(α^j),

где m₀jm₀+2t–1 при m₀=1.

3. Многочлен значений ошибок

Ω(x)S(x)Λ(x) (modx^2t), (*)

Равенство (*) определяет множество из (2t–υ) уравнений и называетсяключевым уравнением, так как оно представляется «ключом» решения задачи декодирования.

Это становится понятным, если учесть, что степень Ω(x) не превышает υ–1 и поэтому справедливо:

, (**),

где .

Из (**) можно получить υ уравнений для υ неизвестных коэффициентов Λ_k. Эти уравнения являются линейными. Они могут быть решены обычными методами либо с помощью итерационных процедур. После нахождения многочлена Λ(x) ключевое уравнение позволяет найти неизвестные компоненты вектора e(x) и по ним выходной вектор декодера: f(x)=C(x)+e(x).

Простейшим путем нахождения корней многочлена Λ(x) является метод проб и ошибок, известный как процедура Ченя. Эта процедура состоит в последовательном вычислении Λ(α^j) для каждого j и проверки полученных значений на ноль. Если величина Λ(α^–k) равна нулю, то α^k является взаимным к корню многочлена локаторов ошибок и k-й элемент кодовой комбинации содержит ошибку. Наиболее простым способом вычисления значения Λ(x) в точке β является схема Горнера:

.

Для вычисления Λ(β) по схеме Горнера требуется только υ умножений и υ сложений, где υ – степень Λ(x).

После определения локаторов ошибок с помощью ключевого уравнения находим значения ошибок. Для этого, используя значения сомножителей, входящих в равенство для Ω(x), перепишем ключевое уравнение следующим образом:

Сворачивая выражение в квадратных скобках, получаем окончательно

Приводя это выражение по модулю x^2t , получаем

.

Вычислим многочлен значений ошибок на позиции l:.

,

Откуда

.

Найдем производную от многочлена локаторов ошибок Λ(x):

.

Для l-й позиции получаем:

.

С учетом последнего выражения Y_lзначение ошибки на позицииlпринимает вид

.

Рассмотренный способ декодирования позволяет найти значение ошибок по известным многочленам локаторов и значений ошибок. Он известен в литературе [ 4 ] как алгоритм Форни. Указанные многочлены вычисляются в результате решения ключевого уравнения. Более подробно декодирование кодов Рида-Соломона рассматривается в разделе 7.2.