Axborot va kodlash nazariyasi asoslari

Axborotlarni Rid-Solomon kodida kodlashtirish usullari


Rid –Solomon kodi bir karralik xatolarni, shuningdek xatolar paketini to‘g‘rilashi mumkin. Rid-Solomon kodining apparatli qismini yaratish oddiy bo‘lgani sababli, ushbu kod aloqa texnikalarida keng qo‘lamda qo‘llanilmoqda. Ko‘p xollarda Rid-Solomon kodidan kaskadli kodlarni qurishda foydalaniladi. Unda Rid-Solomon kodi tashqi kod sifatida ishlatiladi.

Rid-Solomon kodi ham siklik kodlar turkumiga kiradi, shuning uchun ham siklik kodlarning hamma xossalari ushbu kod uchun xam o‘rinli.

1. 
   Axborotlarni siklik kodlarda kodlashtirish, r / n < 0, 5 tengsizlik bajarilganda yasovchi ko‘pxad R(x) orqali emas, balki tekshiruvchi ko‘pxad yordamida bajariladi;
   
2. 
   Axborotlarni siklik kodlarda kodlashtirish, r / n > 0, 5 tengsizlik bajarilganda esa yasovchi ko‘pxad R(x) orqali amalga oshiriladi.
   

Ko‘p xolatlarda 2-usulda kodlashtirish amalga oshiriladi. Shu sababli ushbu usulga ko‘proq to‘xtalib o‘tamiz. Bu usul orqali kodlashtirishda, informatsion ketma-ketlik x^r razryad chapga suriladi va yasovchi ko‘pxad (R(x))ga bo‘lish natijasida qoldiq olinadi. Keyin xosil bo‘lgan qoldiq informatsion ketma-ketlikka qo‘shiladi. Rid-Solomon kodini yasovchi ko‘pxad quyidagi formula orqali aniqlanadi:

g (x) = (x – α ²) = (x – α) (x – α ²) ….(x – α ^{2 t} )

Ko‘pxadning darajasi 2 t quyidagi munosabatdan kelib chiqadi:

n – k = 2 t

9. 
   parametlari Rid-Solomon kodini yasovchi ko‘pxadni xisoblashni misolda qarab chiqamiz.
   

n = 15, k = 9
Demak kodlashtirish 2-usulda bajariladi.

n – k = 15 – 9 = 6 = 2 t

Yasovchi ko‘pxad 6-darajali bo‘lar ekan:

g (x) = (x – α)(x – α ²)(x – α ³) (x – α ⁴)(x – α ⁵)(x – α ⁶)

(15.9) Rid-Solomon kodi uchun GF(2^m )ko‘rinishdagi Galua maydonini qurish kerak. 2^m = q = n + 1 = 15+ 1 = 16, m = 4.

(15.9) Rid-Solomon kodining minimal kod masofasi 11.3- formula asosida topiladi:

d = n – k + 1 = 15 – 9 + 1 = 7

Ushbu kod 11.4- formula asosan quyidagicha xatoni to‘g‘rilashi mumkin:



11.5- formulaga asosan esa 2 ta xatoni va 2 ta o‘chirilganni 1 ta xato va 4 ta o‘chirilganni, 6 ta o‘chirilganni to‘g‘rilashi mumkin.

Kod parametrlarini bilgan xolda Galua maydonini qurish hamda kodlashtirish mumkin.

αx⁷ + α⁸ x⁶ kombinatsiyani uzatish kerak bo‘lsin. Ushbu kombinatsiyani yasovchi ko‘pxadga bo‘lamiz va xosil bo‘lgan qoldiqni, shu kombinatsiyaga qo‘shamiz. Natijada kodlangan kombinatsiyani xosil qilamiz:

g (x) = (x – α)(x – α ²)(x – α ³) (x – α ⁴)(x – α ⁵)(x – α ⁶) =

= x ⁶ + α ¹⁰ x ⁵ + α ¹⁴ x ⁴ + α ⁴ x ³ +α ⁶ x ² + α ⁹ x + α ⁶

g (x) – yasovchi ko‘pxad;

 x⁷ +⁸x⁶ x⁶+¹⁰x⁵+¹⁴x⁴+⁴x³+⁶x²+⁹x +⁶

x⁷ +¹¹x⁶ + ¹⁵x⁵ +⁵x⁴ +⁷x³ +¹⁰x²+ ⁷x x +⁷

⁷x⁶ +¹³x⁵+⁵x⁴ +⁷x³+¹⁰x² +⁷x

⁷x⁶ +²x⁵+⁶x⁴ +¹¹x³+¹³x² +x+¹³

⁸x⁵ +⁹x⁴+⁸x³ +⁹x²+¹⁴x +¹³
Kodlangan kombinatsiya quyidagi ko‘rinishda bo‘ladi:
α x⁷ + α⁸ x⁶ + α⁸ x⁵ +α⁹ x⁴ + α⁸ x³ + α⁹ x² + α¹⁴ x + α¹³
Axborotlarni Rid-Solomon kodida kodlashtirish algoritmini ko‘rib chiqamiz. Algoritm asosida eng avvalo Galua maydoni xisoblanadi. So‘ngra Rid-Solomon kodining parametrlari kiritiladi va Galua maydoni elementlari yordamida kodlashtirish amalga oshiriladi. Kodlashtirish informatsion ketma-ketlikni r razryad chapga surgandan so‘ng, yasovchi polinomga bo‘lingandan xosil bo‘lgan qoldiqni o‘sha informatsion ketma-ketlikka qo‘shish orqali amalga oshiriladi.

Kodlashtirish algoritmi quyidagi etaplardan (bloklardan) iborat.

1. 
   O‘zgaruvchilar va belgilashlar kiritiladi;
   
2. 
   Galua maydoni parametrlari m, g(x), d kiritiladi; m – ushbu maydonning kengayish qiymati; g(x)- m kengaytma uchun keltirilmaydigan ko‘pxad; α – oddiy elementi.
   
3. 
   m qiymatga bog‘lik ravishda Galua maydonining elementlar soni kiritiladi;
   
4. 
   Galua maydonining elementlarini xisoblash uchun boshlang‘ich shart kiritiladi;
   
5. 
   «Xar bir element oldingi elementni α – oddiy elementga ko‘paytirilganiga teng» degan prinsip bo‘yicha Galua maydoni elementlari xisoblanadi;
   
6. 
   Galua maydonining eng katta elementining darajasi, keltirilmaydigan ko‘pxad darajasidan kichik bo‘lishi kerak. Ya’ni
   

dseg α (I) < deg g(x)

Shart tekshiriladi. Agar shart bajarilmasa 7 –blokka o‘tiladi. Unda navbatdagi element Galua maydonining keltirilmaydigan ko‘pxadi bilan mavjud elementni mod 2 bo‘yicha operatsiyasi orqali xisoblanadi;

8. Galua maydonining hamma elementlari chop etiladi. Galua maydonining elementlarini xisoblash algoritmi 11.1 – rasmda keltirilgan.

9. Rid-Solomon kodining parametrlari kiritiladi:

• 
  n – blok uzunligi;
  
• 
  r – blokning tekshiruv qismi;
  
• 
  k – blokning informatsion qismi;
  
• 
  g(x) – yuqoridagi parametrlarga bog‘liq bo‘lgan keltirilmaydigan ko‘pxad;
  

10. Kodli kombinatsiya (k (I))ning qiymati kiritiladi;

11. d – kod masofasi xisoblanadi;

12. t - to‘g‘irlash qobiliyati xisoblanadi;

13. d va t ning qiymati chop etiladi;

14. Kiritilgan informatsion qismning elementlari soniga mos ravishda kodli kombinatsiya uzunligi xisoblanadi;

15. Kodli kombinatsiyaning informatsion qismi k (I) ni r razryad chapga suriladi. Surish natijasida xosil bo‘lgan kodli kombinatsiya N2 ga teng;

16. Xosil bo‘lgan kodli kombinatsiya N2 ni g(x) keltirilmaydigan ko‘pxadga bo‘linadi va R(x) qoldiq xosil qilinadi. Bo‘lish prinsipi ikkilik kodlarni bo‘lish kabi bo‘ladi, lekin 0 va 1 lar o‘rnida Galua maydonining elementlari bo‘ladi. Qo‘shish va ko‘paytirish amallari ham mod m asosida bo‘ladi;

17. r ta nolni xosil bo‘lgan R(x) qoldiq bilan almashtiriladi. Bu operatsiya natijasida kodlashtirilgan kombinatsiya n1 xosil qilinadi;

18. Kod parametrlari n, k va g(x) – keltirilmaydigan ko‘pxad, hamda n1 – kodlashtirilgan kombinatsiya chop etiladi.

Kodlashtirish algoritmi 11.2.- rasmda keltirilgan.

Rida – Solomon kodida kodlangan axborotlarni dekoderlash usullari
Aloqa kanaliga ta’sir etuvchi shovqin xisobiga, istalgan kodli kombinatsiya xatolarga uchrashi mumkin. Kodli kombinatsiyadagi xatolar to‘g‘risidagi ma’lumotni sindromlar orqali olish mumkin.

f (x) – kodli kombinatsiya uzatilgan bo‘lsin. Aloqa kanali bo‘yicha uzatish jarayonida xatolar xosil bo‘ldi va F(x) = f(x) + e(x) kombinatsiya qabul kilindi, ye(x) – xatolar vektori. Xatolar vektori noldan farqli bo‘lgan kombinatsiyalardan iborat. Xatolar vektori ye(x) ning har qaysi noldan farqli komponenti U_i va X _i elementlar ko‘rinishida yoziladi; U_i – xatolarning qiymati, X _i - xatolar pozitsiyalarining nomerlari. U_i – GF(P) maydonning elementi, X _i – GF(P ^m) maydonning elementidir.

11.1 – rasm. Galua maydoning elementlarini xisoblash algoritmi

n,k,g(x)n₁

11.2 – rasm. Rida – Solomon kodida kodlashtirish algoritmi

Agar t ta xato yuz bergan bo‘lsa, unda ye(x) t ta noldan farqli bo‘lgan komponentdan tashkil topadi va t juft (U_i X _i ) ni yozish talab etiladi. U xolda

ye (αⁱ ) = U_i X_i = S_i

S _i = e(α ⁱ ) ning qiymatlari 0  i  2 t – 1 tengsizlikni tekshirish orqali beriladi.

Shunday qilib, xatolar sindromi xatolar bilan quyidagi tenglama orqali bog‘langan:

S _j = U_i X _i ^j , 0  j  2 t – 1

Ushbu tenglama nochizikli tenglama bo‘lib uni yechishning ixtiyoriy usuli xatolarni to‘g‘irlash protsedurasining asosini tashkil etadi. Bu tenglamani yechishda Berlekemp tomonidan taqdim etilgan usuldan foydalaniladi. Bu usulda murakkab xisoblangan etap – xatolar lokatorining ko‘pxadini topishdan iborat.

T(x) = T₀ + T₁ + ….+ T _n-1 q (1 – x _i x)

Ko‘rinishidagi ko‘pxad – xatolar lokatorining ko‘pxadi deyiladi. Bu yerda X _i (i = 1, …t) – xatolar lokatorlari deyiladi. Ular X_i =α ⁱⁱ ,... X_t=α ^it ga teng bo‘lgan GF (P) maydon elementlaridan iborat.