m1
Modul R bo‗yicha keltiriladigan har qanday m darajali R(x)
ko‗pxadning (agar u mavjud bo‗lsa) mavjud;
хP 1
ikkihadli bo‗luvchisi
GF(P) oddiy maydonda quyidagi tenglik bajariladi:
(a+v)r=ar+vr
Modul R uchun [P(x) ]p = P(xp) (mod p) tenglik o‗rinli. Bu yerda R(x) – koeffitsientlari GF(P) maydonga tegishli bo‗lgan ixtiyoriy ko‗pxad;
Agar GF(Pm) 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.
Agar k–n ning bo‗luvchisi bo‗lsa, u holda xk-1 ko‗pxad xn-1
ko‗pxadning bo‗luvchisi bo‗ladi.
Agar modul R bo‗yicha keltirilmaydigan k darajali R1(x) ko‗pxad хPm1 1ikkixadning bo‗luvchisi bo‗lsa, u xolda k daraja m sonining bo‗luvchisi bo‗lishi kerak va aksincha;
Ixtiyoriy oddiy R son va istalgan oddiy m darajali R(x) ko‗pxad uchun, faqat bitta GF( Rm) Galua maydoni mavjud.
GF(Pm) 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(Pm) Galua maydonini qurish kerak bo‗lsin, r=2, m=4 ya‘ni GF(2n). Buning uchun modul 2 bo‗yicha keltirilmaydigan oddiy R(x)=xn+x+1 ko‗pxadni olamiz. α - bu ko‗pxadning ildizi bo‗lsin, unda u GF(2n) 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(24) 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:
α 3 + α 9 = α 12 α 5 + α 11 = α 3
0101 0110
1010 1110
1111 = α12 1000 = α3
Ko‗rsatkichli ko‗rinishdagi elementlarni ko‗paytirish quyidagicha
bajariladi:
3 14
17
17- daraja esa (24-1) dan katta, u xolda ko‗paytirish natijasida
quyidagini hosil qilamiz:
3 14
17 15
2
Rid-Solomon kodining parametrlari quyidagilar:
n- Rid-Solomon kodidagi blok uzunligi:
n q 1 , q 2 m
k – Rid-Solomon kodining axborot qismi:
k n r
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:
Axborotlarni siklik kodlarda kodlashtirish, r/n<0,5 tengsizlik bajarilganda yasovchi ko‗pxad R(x) orqali emas, balki tekshiruvchi ko‗pxad yordamida bajariladi;
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 xr 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 2 ) (x )( x 2 )...( x 2t )
i1
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 2 )( x 3 )( x 4 )( x 5 )( x 6 )
(15.9) Rid-Solomon kodi uchun GF(2m) ko‗rinishdagi Galua maydonini qurish kerak. 2m = 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.
x7 8 x6
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–α2)(x–α3)(x–α4)(x–α5)(x–α6)= x6+α10 x5+α14x4+α4 x3+α6x2 +α9x+α6
g (x) – yasovchi ko‗pxad;
Kodlangan kombinatsiya quyidagi ko‗rinishda bo‗ladi:
αx7+α8x6+α8x5+α9x4 +α8 x3+α9x2 +α14x+α13
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:
O‗zgaruvchilar va belgilashlar kiritiladi;
Galua maydoni parametrlari m, g(x), d kiritiladi; m – ushbu maydonning kengayish qiymati; g(x)- m kengaytma uchun keltirilmaydigan ko‗pxad; α – oddiy element.
m qiymatga bog‗liq ravishda Galua maydonining elementlar soni kiritiladi;
Galua maydonining elementlarini hisoblash uchun boshlang‗ich shart kiritiladi;
«Har bir element oldingi elementni α – oddiy elementga ko‗paytirilganiga teng» degan prinsip bo‗yicha Galua maydoni elementlari hisoblanadi;
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;
Galua maydonining hamma elementlari chop etiladi. Galua maydonining elementlarini hisoblash algoritmi 3.9 – rasmda keltirilgan.
,
3.9 – rasm. Galua maydoning elementlarini hisoblash algoritmi
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;
Kodli kombinatsiya (k (I))ning qiymati kiritiladi;
d – kod masofasi hisoblanadi;
t - to‗g‗irlash qobiliyati hisoblanadi;
d va t ning qiymati chop etiladi;
Kiritilgan axborot qismning elementlari soniga mos ravishda kodli kombinatsiya uzunligi hisoblanadi;
Kodli kombinatsiyaning axborot qismi k(I) ni r razryad chapga suriladi. Surish natijasida hosil bo‗lgan kodli kombinatsiya N2 ga teng;
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;
r ta nolni hosil bo‗lgan R(x) qoldiq bilan almashtiriladi. Bu operatsiya natijasida kodlashtirilgan kombinatsiya n1 hosil qilinadi;
Kod parametrlari n, k va g(x) – keltirilmaydigan ko‗pxad, hamda n1 – kodlashtirilgan kombinatsiya chop etiladi.
Kodlashtirish algoritmi 3.10- rasmda keltirilgan.
| 