Axborot va kodlash nazariyasi asoslari

Xatolar lokatorining ko‘pxadini

T _t , T _t-1, ….T₁ kattaliklar ma’lum bo‘lsa quyidagini yozish mumkin:

S _j = - T _i S _j-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 xisoblanadi. Dekoderga S₁, S₂, S_{2 t} sindromlar komponentlari ma’lum, T _t ;T _t-1 ….T ₁ qiymatlar esa noma’lum. Shuning uchun xatolar lokatorlarining ko‘pxadini (T(x)) aniqlash quyidagicha amalga oshadi:

S _j = T_i S_{j- 1}

Tenglama yordamida dekoder o‘ziga ma’lum bo‘lgan S₁, S₂,... S_2t ketma- ketliklarni xosil qilish uchun, minimal uzunlik L aniqlanadi. L – ketma- ketlikning minimal uzunligi xisoblanadi. U xatolar soniga teng. Lekin aloqa kanalidagi xatolar tasodifiy va teng extimolli deb qaraladi.

Endi yuqorida keltirilganlar asosida Berlekemp - Messi algoritmini – T(x) xatolar lokatorlari ko‘pxadini xisoblashni 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

Δ _n = T _j S _n-j

tenglik o‘rinli bo‘lsin. Bu yerda Δ _n - GF(2 ^m), n q 1:2, …. 2t maydon elementlari orqali xisoblanuvchi xisoblash xatoligi;

V (x) – qo‘shimcha element.

Agar Δ _n  0 va 2 L _n-1  n – 1 shart bajarilsa, u xolda L_n = n–L_n-1 va V_n (x) =Δ^-1 _n · T_n-1 (x) bo‘ladi. Agar 2L _n-1 n –1 shart bajarilmasa, u xolda

L_n = L_n-1 va V_n (x) = x · V_n-1 (x)

bo‘ladi. U xolda T_{2 t} (x) ko‘pxad kichik darajali ko‘pxad bo‘ladi.

Berlekemp – Messi algoritmining blok-sxemasi 11.3 – rasmda keltirilgan.

Xatolar lokatorlarining ko‘pxadi xisoblangandan so‘ng, xatolar lokatorlarining ko‘pxadini ildizlari izlanadi. Bu esa Chen protsedurasi orqali amalga oshiriladi. U GF(2^m) maydonning hamma elementlarini T(x) – xatolar lokatorlarining ko‘pxadiga ketma-ket qo‘yib chiqishdan iborat. T(x) ko‘pxadga qo‘yganda uni nolga aylantiradigan GF(2^m) maydonning elementlari, bu ko‘pxadning ildizlari deyiladi. Xatolar lokatorlarning ko‘pxadini ildizlariga teskari bo‘lgan qiymat – xato sodir bo‘lgan pozitsiyalarni bildiradi.

Rid–Solomon kodini dekoderlashning keyingi etapi U₁; U₂; U_t xatolar qiymatini topishdan iborat. Xatolar qiymatini topishda Forni algoritmidan foydalaniladi. Bu algoritmni keltirishdan avval xatolar lokatorlarining ko‘pxadini quyidagi ko‘rinishda yozamiz:

T(x) =T_t x^t +T_t-1 x^t-1 + … + T₁ x + 1

ildizlari X_i ^–1 , i = 1; 2; ….; t dan iborat.

yo‘q ha
yo‘q

ha

yo‘q ha

dekoderlashning keyingi etapiga

qabul qilingan kombinatsiyada t dan

ortiq xato bor
11.3-rasm. Berlekemp – Messi algoritmi

Bu ko‘pxadni yana quyidagicha yozish mumkin:

Ω (x) = U_i X_i P (1 – X_i X)

va ushbu ifodadan U_i ni topish mumkin:

T’(x) – t (x) dan olingan xosila.

Rid-Solomon kodida kodlangan axborotlarni dekoderlash algoritmini tushuntirib o‘tamiz. Dekoderlash algoritmi (11.4-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 xolda xatolarni n1 kodli kombinatsiyaga kiritiladi va n2 kodli kombinatsiya xosil bo‘ladi;

6. (24) – xato kodli kombinatsiya n2 chop etiladi;

Keyingi etap – xatolar sindromlari S (x) ni xisoblash.

7. (25) – Sindromlar soni beriladi;

8. (26) – sindromni tashkil etgan elementlar soni beriladi;

9. (27) – quyidagi formula bo‘yicha sindromlar qiymatlari S xisoblanadi:

Xatolar o‘rni va B(α)ni

chop etish

n₂

11.4-rasm. Rida-Solomon kodini dekoderlash algoritmi

n₂

11.4-rasm. Rid-Solomon kodini dekoderlash algoritmi (davomi)

Kombinatsiyada t da

ortiq xato

T(x)

11.4-rasm. Rid-Solomon kodini dekoderlash algoritmi (davomi)

To‘g‘irlangan kombinatsiyani chop etish

U – Galua maydoni elementi  ning qiymati;

X – Galua maydoni elementining kodli kombinatsiyada joylashish o‘rni.

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 xatto ixtiyoriy bittasi ham nolga teng bo‘lmasa, unda xato mavjud deb topiladi va uni aniqlash xamda to‘g‘irlash talab etiladi;

12. (30) – Sindromlarning ko‘pxadi S (x) xisoblanadi;

Endi Berlekemp-Messi algoritmi bo‘yicha xatolar lokatorlarining ko‘pxadini xisoblashga 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 xisoblanadi;

16. (34) – bu xatolik qiymati tekshiriladi. Agar  _n  0, u xolda T_n(x) ko‘pxad 17-blokdagi formula bo‘yicha xisoblanadi. Agar  _n = 0, u xolda T_n(x) oldingi ko‘pxad 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 = 2 t – xatolar lokatorlarining ko‘pxadini izlash qadami 2t qiymatdan oshib ketmasligi kerak degan shart tekshiriladi. Agar ushbu shart bajarilsa, u xolda 23-blokka o‘tiladi, aks xolda 14-blokka;

23. (41) – T(x) ko‘pxad 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) xisoblanadi;

Rid-Solomon kodida kodlangan axborotlarni dekoderlash algoritmini tushuntirib o‘tamiz. Dekoderlash algoritmi (11.5-rasm) quyidagi ketma-ketlik (blok)lardan iborat:

11.5-rasm. Rid-Solomon kodini dekoderlash blok-sxemasi

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 xolda xatolarni n1 kodli kombinatsiyaga kiritiladi va n2 kodli kombinatsiya xosil bo‘ladi;

6. (24) – xato kodli kombinatsiya n2 chop etiladi;

Keyingi etap – xatolar sindromlari S (x) ni xisoblash.

7. (25) – Sindromlar soni beriladi;

8. (26) – sindromni tashkil etgan elementlar soni beriladi;

9. (27) – quyidagi formula bo‘yicha sindromlar qiymatlari S xisoblanadi:

S_j = U_i

U –Galua maydoni elementi  ning qiymati;

X – Galua maydoni elementining kodli kombinatsiyada joylashish o‘rni.

10. (28) – Sindrom qiymatlari tekshiriladi. Agar xamma 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 xatto ixtiyoriy bittasi xam 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) xisoblanadi;

Endi Berlekemp-Messi algoritmi bo‘yicha xatolar lokatorlarining ko‘pxadini xisoblashga 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 xisoblanadi;

16. (34) – bu xatolik qiymati tekshiriladi. Agar  _n  0, u xolda T_n (x) ko‘pxad 17-blokdagi formula bo‘yicha xisoblanadi. Agar  _n = 0, u xolda

T_n (x) oldingi ko‘pxad 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 = 2 t – xatolar lokatorlarining ko‘pxadini izlash qadami 2t qiymatdan oshib ketmasligi kerak degan shart tekshiriladi. Agar ushbu shart bajarilsa, u xolda 23-blokka o‘tiladi, aks xolda 14-blokka;

23. (41) – T(x) ko‘pxad 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) xisoblanadi;

25. (43) – T(x) ning xosilasi topiladi;

26. (44) – natija chop etiladi;

27. (45) – Chen protsedurasiga mos ravishda xatolar o‘rnini aniqlash uchun siklning boshi beriladi;

28. (46) – xatolar lokatorlarining ko‘pxadi T(x) ni ildizlarini topish uchun tekshirishlar soni aniqlanadi;

29. (47) – xatolar lokatorlarining ko‘pxadini ildizlarini xisoblash uchun Galua maydonining boshlang‘ich elementi beriladi;

30. (48) – Xatolar mavjud bo‘lgan pozitsiyalarning nomerlari xisoblanadi. Buning uchun Galua maydonining xamma elementlari navbatma – navbat T(x) ko‘pxadga qo‘yib tekshiriladi;

31. (49) – T(x) ko‘pxad tekshiriladi. Agar T(x) = 0 bo‘lsa, unda ushbu qiymat ildiz deb topiladi va T(x) ko‘pxad ildizining teskari qiymati xisoblanadi (34-blok). Bu qiymat esa xato yuz bergan pozitsiya nomerini bildiradi;

32. (50) – Galua maydonining navbatdagi elementiga o‘tiladi;

33. (51) – T(x) ning ildizlarini topishda Galua maydonining xamma elementlarining ishtirok etganligi tekshiriladi;

35. (53) – Xatolar lokatorlarining ko‘pxadini navbatdagi ildizini aniqlashga o‘tiladi;

36. (54) – ko‘pxadning xamma ildizlari topilganligi tekshiriladi;

37. (55) – xatolar soni beriladi;

38. (56) – xatolarning qiymatlarini xisoblash uchun boshlang‘ich element beriladi;

39. (57) – xatolarning qiymatlari xisoblanadi;

40. (58) – n2 kombinatsiyadagi xatolarni to‘g‘irlash amalga oshadi.

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

41. (59) – to‘g‘irlangan kodli kombinatsiya chop etiladi;

42. (60) – dastur ishi yakunlanadi.

Rid-Solomon kodida kodlangan axborotlar dekoderi 11.5-rasmda blok sxema ko‘rinishida berilgan.

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 xisoblash qurilmasiga ham tushadi. Unda sindromlar xisoblanadi. Sindromlardan xatolar lokatorlarining ko‘pxadi T(x) ni aniqlovchi tenglamani yechishda foydalaniladi.

T(x) ko‘pxadni aniqlash algoritmi 11.3.-rasmda keltirilgan edi.

Dekoder tenglamani yechish bilan bir vaqtning o‘zida xosil qilinuvchi xatolar qiymatlarining ko‘pxadi  (x) ni xisoblashni amalga oshiradi.

«Chen prodedurasi»ni bajaruvchi qurilma xatolar o‘rnini aniqlaydi.

«Xatolarni xisoblash» blokida esa xatolarning qiymatlari aniqlanadi va bu qiymatlar ventil xamda summator yordamida, xatolar mavjud bo‘lgan pozitsiyadagi simvollar bilan qo‘shiladi. Shu tariqa to‘g‘rilangan kodli kombinatsiya f (x) summator chiqishda xosil qilinadi.