лекции / DekoderivRida
.pdfДекодирование кодов Рида-Соломона во временной области
(n,k)-код;
Элементы кодовой комбинации принадлежат полю GF(2m). t – кратность исправляемых ошибок;
dmin – минимальное кодовое расстояние, dmin |
= 2t +1; |
|
|
|
|
|
|
|||
Корни образующего многочлена кода: 1,ε,ε2 ,ε3 ,...,ε2t −1. |
|
|
|
|
|
|
||||
Многочлен ошибок : |
e(x) = e εi1 +e εi2 +... +e εit |
=Y X |
1 |
+Y X |
2 |
+... +Y X |
. |
|||
|
i1 |
i2 |
it |
1 |
|
2 |
t t |
|
||
|
|
t |
|
|
|
|
|
|
|
|
|
|
Λ(z) = ∏(1− zεik ) =(1− zεi1 )(1− zεi2 )...(1− zεit ). |
||||||||
|
|
k =1 |
|
|
|
|
|
|
|
|
Многочлен локаторов ошибок – |
Λ(ε-ik ) = 0 |
|
|
|
|
|
|
|
|
|
|
|
t |
|
|
|
|
|
|
|
|
|
|
Λ'(z) = ∑(−εik )∏(1− zεim ); |
deg Λ'(z) = (t −1). |
|||||||
|
|
k =1 |
m¹k |
|
|
|
|
|
|
|
Синдромы:
|
t |
|
|
|
|
S j |
= ∑eik ε jik ; |
j = 0,1,..., (2t −1). |
|
|
|
|
k =1 |
|
|
|
|
|
|
t |
|
|
|
S0 |
=Y1 +Y2 +... +Yt = ∑eik |
, |
|
|
|
|
|
k =1 |
|
|
|
|
|
|
t |
εik |
|
S1 |
=Y1 X1 +Y2 X 2 |
+... +Yt X 2 |
= ∑ei |
||
|
|
|
k |
|
|
|
|
|
k =1 |
|
|
|
|
|
t |
|
|
S2 |
=Y1 X12 +Y2 X 22 +... +Yt X t2 = ∑ei |
ε |
|||
|
|
|
k =1 |
k |
|
|
|
|
|
|
,
2ik ,
.............................................................
t
S2t -1 =Y1 X12t -1 +Y2 X 22t -1 +... +Yt X t2t -1 = ∑eik ε(2t -1)ik . k =1
Введем производящую функцию
∞ |
|
∞ |
t |
|
t |
∞ |
|
t |
S (z) = ∑z j S j =∑z j ∑ei |
ε jik =∑ei |
∑(zεik ) j = ∑ei |
||||||
j =0 |
|
j =0 |
k =1 |
k |
k |
j =0 |
|
k |
|
|
k =1 |
|
k =1 |
||||
Ключевое уравнение: |
|
|
|
|
|
|
||
t |
|
1 |
|
t |
|
t |
|
|
S (z)Λ(z) = ∑ei |
|
∏(1− zεim ) = ∑ei |
∏(1− zεim ) |
|||||
|
i |
|||||||
k =1 |
k |
(1− zε k ) |
m=1 |
k =1 |
k |
m¹k |
||
|
|
|
|
|||||
|
|
S ( z ) |
|
|
L( z ) |
|
|
|
deg Ω(z) = (t −1); |
deg Ω(z) < deg Λ(z). |
|
|
1
(1− zεik ).
= Ω(z).
Λ(z) - многочлен локаторов ошибок; Ω(z) - многочлен ошибок.
Нахождение ошибочных позиций кода – |
процедура Ченя над Λ(z) . |
|
|
|
|
||||||
Нахождение значений ошибок: |
|
|
|
|
|
|
|
|
|||
Примем z = ε −im |
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
' |
-i |
||
Λ'(ε-im ) = −εim ∏(1−ε-im εik ); |
|
|
отсюда ∏(1−ε-im εik ) = |
Λ |
(ε m ) |
. |
|||||
|
|
|
i |
||||||||
|
|
k ¹m |
|
|
|
k ¹m |
|
(−ε m ) |
|||
|
|
|
|
|
' |
-i |
|
|
|
|
|
Ω(ε-im ) =ei ∏(1−ε-im εik ) =ei |
Λ (ε m ) |
. |
|
|
|
|
|||||
i |
|
|
|
|
|||||||
|
|
m k ¹m |
m |
(−ε m ) |
|
|
|
|
|||
Из последнего уравнения находим: |
|
|
|
|
|||||||
e |
= −εim |
Ω(ε-im ) |
−формулаФорни( решение ключевого уравнения). |
||||||||
|
|||||||||||
im |
|
Λ'(ε-im ) |
|
|
|
|
|
|
|
|
|
Главная задача реализации декодирования состоит в нахождении Λ(z) |
- |
|
|
||||||||
многочлена локаторов ошибок и Ω(z) - многочлена ошибок. Эта задача |
|
|
решается с помощью алгоритма Евклида.