Ключевое уравнение

Рассмотрим процедуру быстрого декодирования применительно к кодам Рида-Соломона (PC). Для этих кодов справедлива граница Синглтона:

n-k= d-1=2t,

где n-k — избыточность кодовой комбинации,

d - минимальное кодовое расстояние,

t - кратность гарантированно исправляемых ошибок.

Будем полагать, что код используется в режиме исправления ошибок. Пусть в приемник АПД поступила кодовая комбинация PC-кода

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

где f(x) - переданная передатчиком АПД кодовая комбинация, в которой в процессе передачи по каналу связи произошло υ ошибок, отображаемых многочленом е(х). Здесь 0≤ v≤t.

Многочлен ошибок можно представить в виде

e (x)=e_i1хⁱ¹ +e_i2xⁱ²+…+e_ivx^iv=∑e_ilx^il,

где e_il - значение ошибки, i_l - номер позиции кодовой комбинации, в которой произошла ошибка. Для исправления ошибок необходимо определить e_il и i_l. Это возможно выполнить на основе синдрома. В 7.1.4 введено понятие синдромного многочлена:

S(x)=S₁x⁰+S₂x¹+…+S_n-к x^n-k-1.

Коэффициенты Si определяются подстановкой в С(х) корней α^l порождающего многочлена кода PC.

S₁=C(x= α^l)=f(x= α^l)+е(х= α^l)=e(α^l),

где l≤ l ≤ 2t.

Теперь получим, S₁₌e₁αⁱ¹ +e₂αⁱ²+…+e_ivα^iv и т.д.

Для упрощения записи компонентов синдромного многочлена определим для всех l =1,...,v значения ошибки У_l= e_il, и локаторы ошибок Х_l= a^il=l,где i_l=l - истинное положение l-й ошибки.

В этих новых обозначениях S₁ запишется в виде:

S₁=Y₁X₁+ Y₂X₂+…+ Y_vX_v,.

Здесь Y_l и Х_l - элементы поля GF(q) над которым построен PC-код, а α - примитивный элемент этого поля. В результате получим следующую систему из 2t уравнений относительно υ неизвестных локаторов X ₁,..., X_v и v неизвестных значений ошибок Y₁,..., Y_υ:

S₁=Y₁X₁+ Y₂X₂+…+ Y_vX_v,

S₂₌Y₁X₁²+ Y₂X₂²+…+ Y_vX_v²,

...

S_2t=Y₁X₁^2t+ Y₂X₂^2t+…+ Y_vX_v^2t.

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

Для его формирования вводятся еще два многочлена:

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

Λ(х)=1+ Λ₁х+Λ₂ х²+ Λ_vx^v, имеющий корни, обратные локаторам ошибок X_l^-1, l=1…,v. Это позволяет представить Λ (x) в следующем виде:

.

---

Дата добавления: 2015-08-02