Ta‟lim vazirligi muhammad al-xorazmiy nomidagi

t
^S j ^{ T}i ^S j 1 i1

bu yerda j = t + 1; …. ; 2 t · S _{j- t} ; S _{j- t+1} ; ….S _{j- 1} komponentlar bo‗yicha navbatdagi S_j, T_t , T _t-1 ,….,T ₁ qiymatlar yordamida hisoblanadi. Dekoderga S₁, S₂, S_2t sindromlar komponentlari ma‘lum, T_t , T_t-1 ,….,T ₁ qiymatlar esa noma‘lum. Shuning uchun xatolar lokatorlarining ko‗phadi (T(x))ni aniqlash quyidagicha amalga oshadi:


2t
^S j  ^Ti ^S j 1 i1

tenglama yordamida dekoder o‗ziga ma‘lum bo‗lgan S₁, S₂,... S_2t ketma- ketliklarni hosil qilish uchun, minimal uzunlik L aniqlanadi. L – ketma- ketlikning minimal uzunligi hisoblanadi. U xatolar soniga teng. Lekin aloqa kanalidagi xatolar tasodifiy va teng ehtimolli deb qaraladi.

Endi yuqorida keltirilganlar asosida Berlekemp - Messi algoritmini –
T(x) xatolar lokatorlari ko‗phadini hisoblashni formula ko‗rinishga

keltiramiz: S₁; S₂;…;S_2t sindrom komponentlari aniqlangan bo‗lsin va
T₀(x) = 1, V₀(x) = 1 , L₀ = 0 boshlang‗ich shartda
L

^n ^{ T}j ^Sn j j0
tenglik o‗rinli bo‗lsin.

Bu yerda Δ_n - GF(2^m), n = 1:2, …., 2t maydon elementlari orqali hisoblanuvchi hisoblash xatoligi;
V(x) – qo‗shimcha element.

Agar
^{ n  0} va
2L_n1  n 1
shart bajarilsa, u holda
L_n  n  L_n1

va ^B
(x)  ^1  T
(x)
bo‗ladi.

n n n1

Agar
^2L_n1 ^{ n 1} shart bajarilmasa, u holda
^Ln ^{ L}n1 ^va

B_n (x)  x  B_n1 (x)
bo‗ladi.
bo‗ladi. U holda T_{2 t}(x) ko‗pxad kichik darajali ko‗pxad

Berlekemp – Messi algoritmining blok-sxemasi 3.11 – rasmda keltirilgan.
Xatolar lokatorlarining ko‗phadi hisoblangandan so‗ng, xatolar lokatorlarining ko‗phadini ildizlari izlanadi. Bu esa Chen protsedurasi orqali amalga oshiriladi. U GF(2^m) maydonning hamma elementlarini T(x) – xatolar lokatorlarining ko‗phadiga ketma-ket qo‗yib chiqishdan iborat. T(x) ko‗phadga qo‗yganda uni nolga aylantiradigan GF(2^m) maydonning elementlari, bu ko‗phadning ildizlari deyiladi. Xatolar lokatorlarining ko‗phadini ildizlariga teskari bo‗lgan qiymat – xato sodir bo‗lgan pozitsiyalarni bildiradi.
Rid – Solomon kodini dekoderlashning keyingi bosqichi Y₁; Y₂; Y_t xatolar qiymatini topishdan iborat. Xatolar qiymatini topishda Forni algoritmidan foydalaniladi. Bu algoritmni keltirishdan avval xatolar lokatorlarining ko‗phadini quyidagi ko‗rinishda yozamiz:

t
T (x)  T_t x
^{ T}t 1
x^t1  ...  T
x  1

i

1
ildizlari
x ^1, i  1;2;...; t
dan iborat.

n = n +1



Yo‗ ^Hа

2L_n-T ≤ n-1
Hа
Yo‗

Yo‗
degT(x)=L_n
n = 2t


^Hа Dekoderning keyingi bosqichiga

Qabul qilingan kombinatsiyada

t dan ortiq xato bor

3.11-rasm. Berlekemp – Messi algoritmi

Sindromlar ko‗phadini quyidagicha yozamiz:



i
2t 2t t

X

j
S (x)  _ S _j X
_{ Y} i _X j j

j 1
j 1 i1

Endi S(x) – sindromlar ko‗pxadi bo‗yicha  (x) – xatolar qiymatining ko‗phadini yozish mumkin:

(x)  S (x) T (x)(mod
_x 2t ₎

mod x^2t ning ko‗rsatkichi x ga kiruvchi xadlarning darajasi 2t dan oshmasligini bildiradi.
Bu ko‗pxadni yana quyidagicha yozish mumkin:



t



(x)  _Y_i X_i П (1 - X_i X )
i1

va ushbu ifodadan Y_i ni topish mumkin:

Y_i 
(x) T ^' (x)

T‘(x) – t (x) dan olingan hosila.
Rid-Solomon kodida kodlangan axborotlarni dekodlash algoritmini tushuntirib o„tamiz. Dekodlash algoritmi (3.12-rasm) quyidagi ketma-ketlik (blok)lardan iborat:

1. 
   (19) – t1 xatolar soni kiritiladi;
   
2. 
   (20) – n1 kodli kombinatsiyadagi xato o‗rni kiritiladi;
   
3. 
   (21) – xatolar qiymati v (d) kiritiladi;
   
4. 
   (22) – xato o‗rni va uning qiymati chop etiladi;
   
5. 
   (23) – joylashgan o‗rniga bog‗liq holda xatolarni n1 kodli kombinatsiyaga kiritiladi va n2 kodli kombinatsiya hosil bo‗ladi;
   
6. 
   (24) – xato kodli kombinatsiya n2 chop etiladi. Keyingi bosqich – xatolar sindromlari S(x) ni hisoblash.
   
7. 
   (25) – sindromlar soni beriladi;
   
8. 
   (26) – sindromni tashkil etgan elementlar soni beriladi;
   

3.12-rasm. Rid-Solomon kodini dekodlash algoritmi

3.12-rasm. Rid-Solomon kodini dekodlash algoritmi (davomi)

3.12-rasm. Rid-Solomon kodini dekodlash algoritmi (davomi)

9. 
   (27) – quyidagi formula bo‗yicha sindromlar qiymatlari S
   

hisoblanadi:



j
n 2

X
S _j  Y_{i i} i 1

o‗rni.
Y – Galua maydoni elementi  ning qiymati;
X – Galua maydoni elementining kodli kombinatsiyada joylashish

10. 
    (28) – sindrom qiymatlari tekshiriladi. Agar hamma sindromlar
    

nolga teng bo‗lsa, unda kombinatsiyada xato yo‗q va 11-blokka o‗tiladi. 11-blokda n2 kodli kombinatsiyani chop etish bajariladi va dastur ishi yakunlanadi. Agar sindromlarning ixtiyoriy bittasi ham nolga teng bo‗lmasa, unda xato mavjud deb topiladi va uni aniqlash hamda to‗g‗irlash talab etiladi;
12 (30) – sindromlarning ko‗pxadi S(x) hisoblanadi.
Endi Berlekemp-Messi algoritmi bo‗yicha xatolar lokatorlarining ko‗phadini hisoblashga o‗tiladi.
13 (31) – algoritm ishini ta‘minlash maqsadida boshlang‗ich shartlar kiritiladi;
14 (32) – Berlekemp-Messi algoritmi bo‗yicha izlash qadamining nomeri beriladi;
15 (33) – xatolik _n hisoblanadi;
16 (34) – bu xatolik qiymati tekshiriladi. Agar _n  0, u holda T_n(x) ko‗pxad 17-blokdagi formula bo‗yicha hisoblanadi. Agar _n = 0 bo‗lsa, u holda T_n(x) oldingi ko‗phad T_n-1(x) ga teng (18-blok);
19 (37) 2L_n-1  n-1 shart tekshiriladi.
L – xatolar soni;
n - izlash qadami.
Agar ushbu shart bajarilmasa, xatolar soni L oldingi qiymati (L_n-1) ga teng bo‗lib qoladi (21-blok). Agar shart bajarilsa xatolar soni L ortadi (20- blok);

22. 
    (40) n = 2t – xatolar lokatorlarining ko‗phadini izlash qadami 2t qiymatdan oshib ketmasligi kerak degan shart tekshiriladi. Agar ushbu shart bajarilsa, u holda 23-blokka o‗tiladi, aks holda 14-blokka;
    
23. 
    (41) T(x) ko‗phad darajasi tekshiriladi. U topilgan xatolar sonidan oshmasligi kerak. Agar shart bajarilmasa, unda: «Qabul qilingan kombinatsiyada t dan ortiq xato mavjud» - degan xabar chop etiladi va dastur tugallanadi. Agar shart bajarilsa, unda 24-blokka o‗tiladi;
    
24. 
    (42) – xatolar qiymatlarining ko‗pxadi  (x) hisoblanadi;
    

22. 
    (43) – T(x) ning hosilasi topiladi;
    
23. 
    (44) – natija chop etiladi;
    
24. 
    (45) – Chen protsedurasiga mos ravishda xatolar o‗rnini aniqlash uchun siklning boshi beriladi;
    
25. 
    (46) – xatolar lokatorlarining ko‗phadi T(x) ni ildizlarini topish uchun tekshirishlar soni aniqlanadi;
    
26. 
    (47) – xatolar lokatorlarining ko‗phadi ildizlarini hisoblash uchun Galua maydonining boshlang‗ich elementi beriladi;
    
27. 
    (48) – Xatolar mavjud bo‗lgan pozitsiyalarning nomerlari hisoblanadi. Buning uchun Galua maydonining hamma elementlari navbatma – navbat T(x) ko‗pxadga qo‗yib tekshiriladi;
    
28. 
    (49) – T(x) ko‗phad tekshiriladi. Agar T(x) = 0 bo‗lsa, unda ushbu qiymat ildiz deb topiladi va T(x) ko‗phad ildizining teskari qiymati hisoblanadi (34-blok). Bu qiymat esa xato yuz bergan pozitsiya nomerini bildiradi;
    
29. 
    (50) – Galua maydonining navbatdagi elementiga o‗tiladi;
    
30. 
    (51) – T(x) ning ildizlarini topishda Galua maydonining hamma elementlari ishtirok etganligi tekshiriladi;
    

35. 
    (53) – xatolar lokatorlarining ko‗phadini navbatdagi ildizini aniqlashga o‗tiladi;
    
36. 
    (54) – ko‗pxadning hamma ildizlari topilganligi tekshiriladi;
    
37. 
    (55) – xatolar soni beriladi;
    
38. 
    (56) – xatolarning qiymatlarini hisoblash uchun boshlang‗ich element beriladi;
    
39. 
    (57) – xatolarning qiymatlari hisoblanadi;
    
40. 
    (58) – n2 kombinatsiyadagi xatolarni to‗g‗irlash amalga oshadi.
    

Buning uchun esa hisoblab topilgan xatolarning qiymatlarini kombinatsiyadagi xatolarning qiymatlari bilan o‗zaro mod m bo‗yicha qo‗shiladi;

35. 
    (59) – to‗g‗irlangan kodli kombinatsiya chop etiladi;
    
36. 
    (60) – dastur ishi yakunlanadi.
    

Rid-Solomon kodida kodlangan axborotlar dekoderi 3.13-rasmda blok sxema ko‗rinishida berilgan.

	O‗zgarishlarni hisoblash
Tenglamani yeching

3.13-rasm. Rid-Solomon kodini dekodlash blok-sxemasi

Dekoder kirishiga kodlangan axborot va xatolar vektori yig‗indisidan iborat bo‗lgan kodli kombinatsiya F(x) kelib tushadi. F(x) kodli kombinatsiya buferda saqlanadi. Shuningdek ushbu F(x) kodli kombinatsiya o‗zgarishlarni hisoblash qurilmasiga ham tushadi. Unda sindromlar hisoblanadi. Sindromlardan xatolar lokatorlarining ko‗pxadi T(x) ni aniqlovchi tenglamani yechishda foydalaniladi.

Dekoder tenglamani yechish bilan bir vaqtning o‗zida hosil qilinuvchi xatolar qiymatlarining ko‗pxadi  (x) ni hisoblashni amalga oshiradi.
«Chen prodedurasi»ni bajaruvchi qurilma xatolar o‗rnini aniqlaydi.
«Xatolarni hisoblash» blokida esa xatolarning qiymatlari aniqlanadi va bu qiymatlar ventil hamda summator yordamida, xatolar mavjud bo‗lgan pozitsiyadagi simvollar bilan qo‗shiladi. Shu tariqa to‗g‗irlangan kodli kombinatsiya f (x) summator chiqishida hosil qilinadi.