7.2. Быстрое декодирование кодов бчх

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

Рассмотрим процедуру быстрого декодирования применительно к кодам Рида-Соломона (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) в следующем виде:

.

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

Он определяется через S(x) и Λ(х) в соответствии с видом введенного выше многочлена ошибок Ω(x)=S(x)* Λ (x) (mod x^2t)=

=[(S₁x⁰+ S₂x¹+…+ S_2t x^2t-1) ] (mod x^2t)=

=[(Y₁X₁+ Y₂X₂+…+ Y_vX_v,)x⁰+(Y₁X₁²+ Y₂X₂²+…+ Y_vX_v²)x¹+…

+(Y₁X₁^2t+ Y₂X₂^2t+…+ Y_vX_v^2t)x^2t-1](mod x^2t)=

=[ Y₁X₁( 1+ X₁x +Xx²+…+Xx^2t-1) +

+ Y₂X₂( 1+ X₂x +Xx²+…+Xx^2t-1) + . . .

.+ Y_vX_v ( 1+ X_v x +Xx²+…+Xx^2t-1) ](mod x^2t)=

=[ Y₁X₁( 1+ X₁x +Xx²+…+Xx^2t-1)(1+X₁x) +…

+ Y_vX_v ( 1+ X_v x +Xx²+…+Xx^2t-1)(1+ X_v x ) ](mod x^2t)=

=[ Y₁X₁ (1+X₁x)^2t+…+ Y_vX_v(1+ X_v x )^2t](mod x^2t)=

=[ Y₁X₁+…+ Y_vX_v] =.

=[ Y₁X₁ (1+(X₁x)^2t)+…+ Y_vX_v(1+( X_v x) )^2t](mod x^2t)=

Итак, многочлен значений ошибок выражается через значения ошибок и локаторы ошибок следующим образом:

Ω(х) =.

Выражение для Ω(х) определяет множества из 2t-v уравнений и называется ключевым уравнением, так как оно является ключом решения задачи декодирования.

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

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

I этап — вычисление многочлена локатора ошибок Λ(х). Для двоичных кодов БЧХ этим этапом декодирование завершается.

II этап - для недвоичных кодов, какими являются РС-коды, вычисление многочлена значений ошибок Ω(х), позволяющего вычислять значение каждой из υ ошибок в принятой комбинации.

Для нахождения многочлена локаторов ошибок из литературы известны три алгоритма:

1. Алгоритм Питерсона.

2 .Алгоритм Берлекемпа-Месси.

3- Алгоритм Евклида - алгоритм СКХН.

Авторы первого и второго алгоритмов указаны в их названии. Алгоритм Евклида для целей решения ключевого уравнения был впервые предложен четырьмя авторами: Сугияма, Касахара, Хирасава и Намекава. В дальнейшем для краткости будем называть алгоритмом Евклида.

Алгоритм Питерсона может быть использован как самостоятельная процедура декодирования недвоичных циклических кодов и на II этапе.

Алгоритм Берлекемпа-Месси и алгоритм Евклида на II этапе декодирования для недвоичных циклических кодов дополняют алгоритмом Форни, позволяющим по корням Λ (х) и многочлену Ω(x) найти значения ошибок. Сочетание алгоритма Берлекемпа-Месси и алгоритма Форни получило название быстрого декодирования кодов БЧХ.

Рассмотрим сущность изложенных алгоритмов декодирования