Ta‟lim vazirligi muhammad al-xorazmiy nomidagi

GF(P^m) maydonning har doim tartibli α elementi mavjud bo‗ladi, ya‘ni P^m-1 tartibli elementi. Maydonning nolga teng bo‗lmagan elementlarini bitta yoki bir nechta α ning darajali ko‗rinishida tasvirlash mumkin. Xulosa qilib aytganda Galua maydonining multiplikativ guruhi siklikdir.

Siklik kodlar nazariyasida quyidagi xossalar muhim o‗rin tutadi.

1. 
   
   m1
   Modul R bo‗yicha keltiriladigan har qanday m darajali R(x)
   

ko‗pxadning (agar u mavjud bo‗lsa) mavjud;
хP 1
ikkihadli bo‗luvchisi

2. 
   GF(P) oddiy maydonda quyidagi tenglik bajariladi:
   

(a+v)^r=a^r+v^r

3. 
   Modul R uchun [P(x) ]^p = P(x^p) (mod p) tenglik o‗rinli. Bu yerda R(x) – koeffitsientlari GF(P) maydonga tegishli bo‗lgan ixtiyoriy ko‗pxad;
   
4. 
   Agar GF(P^m) maydonning α elementi modul R bo‗yicha keltirilmaydigan m darajali R(x) ko‗pxadning ildizi bo‗lsa, unda R(x) ning
   

qolgan ildizlari
^Ð, ^ð2 ,..., ^Ðm 1
elementlar bo‗ladi.

5. 
   Agar k–n ning bo‗luvchisi bo‗lsa, u holda x^k-1 ko‗pxad xⁿ-1
   

ko‗pxadning bo‗luvchisi bo‗ladi.

6. 
   Agar modul R bo‗yicha keltirilmaydigan k darajali R₁(x) ko‗pxad ^хPm1 ^1ikkixadning bo‗luvchisi bo‗lsa, u xolda k daraja m sonining bo‗luvchisi bo‗lishi kerak va aksincha;
   

7. 
   Ixtiyoriy oddiy R son va istalgan oddiy m darajali R(x) ko‗pxad uchun, faqat bitta GF( R^m) Galua maydoni mavjud.
   

GF(P^m) ko‗rinishdagi Galua maydonida faqat ikkita-ko‗shish va ko‗paytirish amalini bajarish mumkin. Ko‗shish mod 2 bo‗yicha, ko‗paytirish esa mod m bo‗yicha bajariladi.
Maydonning ikkita elementini 0 va 1 orqali belgilaymiz va qo‗shish hamda ko‗paytirish amallarini bajaramiz:

0 + 0 = 0	0  0 = 0
0 + 1 = 1	0  1 = 0
1 + 0 = 1	1  0 = 0
1 + 1 = 1	1  1 = 1

GF(P^m) Galua maydonini qurish kerak bo‗lsin, r=2, m=4 ya‘ni GF(2ⁿ). Buning uchun modul 2 bo‗yicha keltirilmaydigan oddiy R(x)=xⁿ+x+1 ko‗pxadni olamiz. α - bu ko‗pxadning ildizi bo‗lsin, unda u GF(2ⁿ) maydonning 1-tartibli elementi hisoblanadi. 2-xossaga asosan hamma 15 ta noldan farqli elementlar quyidagicha bo‗ladi:

α ^0 = 1	(0001)
α ^1 = α	(0010)
α ^2 = α ^2	(0100)
α ^3 = α ^3	(1000)
α ^4 = 1 + α	(0011)
α ^5 = α + α ^2	(0110)
α ^6 = α ^2 + α ^3	(1100)
α ^7 = 1 +α +α^3	(1011)
α ^8 = 1 + α ^2	(0101)
α ^9 = α + α ^3	(1010)
α ^10 = 1+α + α ^2	(0111)
α ^11 = α + α^2 +α ^3	(1110)
α ^12 = 1+α + α ^2 +α ^3	(1111)
α ^13 = 1+α ^2 + α ^3	(1101)
α ^14 = 1 +α ^3	(1001)
α ^15 = 1	(0001)

GF(2⁴) Galua maydonining oddiy elementi 0001 ga, nol elementi 000 ga teng.
Galua maydonining elementlarini qo‗shish, razryadlarini mod 2 bo‗yicha qo‗shish kabi bajariladi:

α ³ + α ⁹ = α ¹² α ⁵ + α ¹¹ = α ³

0101 0110
1010 1110
1111 = α¹² 1000 = α³


Ko‗rsatkichli ko‗rinishdagi elementlarni ko‗paytirish quyidagicha

bajariladi:
_ 3 _ 14
_{ } 17

17- daraja esa (2⁴-1) dan katta, u xolda ko‗paytirish natijasida

quyidagini hosil qilamiz:
_ 3 _14
_{ }17 _{ }15
  ²

Rid-Solomon kodining parametrlari quyidagilar:

1. 
   n- Rid-Solomon kodidagi blok uzunligi:
   

n  q  1 _, q  2^m

2. 
   k – Rid-Solomon kodining axborot qismi:
   

k  n  r

3. 
   r - Rid-Solomon kodining tekshiruv qismi:
   

d  r 1  n  k 1
Rid-Solomon kodi t ta xatolarni to‗g‗irlashi:
t  (d 1) / 2
yoki t ta xatolarni va v ta o‗chirilganlarni to‗g‗irlashi:
^{d  2t  v 1}.
Axborotlarni Rid-Solomon kodida kodlashtirish usullari. Rid – Solomon kodi bir karralik xatolarni, shuningdek xatolar paketini to‗g‗irlashi mumkin. Rid-Solomon kodining apparatli qismini yaratish oddiy bo‗lgani sababli, ushbu kod aloqa texnikalarida keng ko‗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 ham 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 holatlarda 2-usulda kodlashtirish amalga oshiriladi. Shu sababli ushbu usulga ko‗proq to‗xtalib o‗tamiz. Bu usul orqali kodlashtirishda, axborot ketma-ketlik x^r razryad chapga suriladi va yasovchi ko‗pxad (R(x))ga bo‗lish natijasida qoldiq olinadi. Keyin hosil bo‗lgan qoldiq axborot ketma-ketlikka qo‗shiladi. Rid-Solomon kodini yasovchi ko‗pxadi quyidagi formula orqali aniqlanadi:




2t
g(x)  (x   ² )  (x   )( x   ² )...( x   ^2t )
i1

Ko‗pxadning darajasi 2t quyidagi munosabatdan kelib chiqadi:

n  k  2t


(15.9) parametlari Rid - Solomon kodini yasovchi ko‗pxadni hisoblashni misolda qarab chiqamiz:

n = 15, k = 9
k _ 9
n 15
 0,6  0,5

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 quyidagi formula asosida topiladi:
d = n – k + 1 = 15 – 9 + 1 = 7


Ushbu kod quyidagi formulaga asosan xatoni to‗g‗irlashi mumkin:

_{t } (d 1) _,
2
t  ^{7 1}  3 2

Bu 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‗irlashi mumkin.
Kod parametrlarini bilgan holda Galua maydonini qurish hamda kodlashtirish mumkin.

Misol.

x⁷   ⁸ x⁶
kombinatsiyani uzatish kerak bo‗lsin. Ushbu

kombinatsiyani yasovchi ko‗pxadga bo‗lamiz va hosil bo‗lgan qoldiqni shu kombinatsiyaga qo‗shamiz. Natijada kodlangan kombinatsiyani hosil qilamiz:
g(x)=(x–α)(x–α²)(x–α³)(x–α⁴)(x–α⁵)(x–α⁶)= x⁶+α¹⁰ x⁵+α¹⁴x⁴+α⁴ x³+α⁶x² +α⁹x+α⁶


g (x) – yasovchi ko‗pxad;




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 hisoblanadi. So‗ngra Rid-Solomon kodining parametrlari kiritiladi va Galua maydoni elementlari yordamida kodlashtirish amalga oshiriladi. Kodlashtirish axborot ketma-ketlikni r razryad chapga surgandan so‗ng, yasovchi polinomga bo‗lingandan hosil bo‗lgan qoldiqni o‗sha axborot ketma-ketlikka qo‗shish orqali amalga oshiriladi.
Kodlashtirish algoritmi quyidagi bosqichlardan (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 element.
   
3. 
   m qiymatga bog‗liq ravishda Galua maydonining elementlar soni kiritiladi;
   

4. 
   Galua maydonining elementlarini hisoblash uchun boshlang‗ich shart kiritiladi;
   
5. 
   «Har bir element oldingi elementni α – oddiy elementga ko‗paytirilganiga teng» degan prinsip bo‗yicha Galua maydoni elementlari hisoblanadi;
   
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 operatsiyasi orqali hisoblanadi;

8. 
   Galua maydonining hamma elementlari chop etiladi. Galua maydonining elementlarini hisoblash algoritmi 3.9 – rasmda keltirilgan.
   

,

3.9 – rasm. Galua maydoning elementlarini hisoblash algoritmi

9. 
   Rid-Solomon kodining parametrlari kiritiladi:
   
   • 
     n – blok uzunligi;
     
   • 
     r – blokning tekshiruv qismi;
     
   • 
     k – blokning axborot qismi;
     
   • 
     g(x) – yuqoridagi parametrlarga bog‗liq bo‗lgan keltirilmaydigan ko‗pxad;
     
10. 
    Kodli kombinatsiya (k (I))ning qiymati kiritiladi;
    
11. 
    d – kod masofasi hisoblanadi;
    
12. 
    t - to‗g‗irlash qobiliyati hisoblanadi;
    
13. 
    d va t ning qiymati chop etiladi;
    
14. 
    Kiritilgan axborot qismning elementlari soniga mos ravishda kodli kombinatsiya uzunligi hisoblanadi;
    
15. 
    Kodli kombinatsiyaning axborot qismi k(I) ni r razryad chapga suriladi. Surish natijasida hosil bo‗lgan kodli kombinatsiya N2 ga teng;
    
16. 
    Hosil bo‗lgan kodli kombinatsiya N2 ni g(x) keltirilmaydigan ko‗pxadga bo‗linadi va R(x) qoldiq hosil 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 hosil bo‗lgan R(x) qoldiq bilan almashtiriladi. Bu operatsiya natijasida kodlashtirilgan kombinatsiya n1 hosil qilinadi;
    
18. 
    Kod parametrlari n, k va g(x) – keltirilmaydigan ko‗pxad, hamda n1 – kodlashtirilgan kombinatsiya chop etiladi.
    

Kodlashtirish algoritmi 3.10- rasmda keltirilgan.