Axborot va kodlash nazariyasi asoslari

Axborotlarni Fayra kodida kodlashtirish usullari. Uzatish kanaliga impuls xarakteridagi shovqin ta’sir etishi natijasida xatolar paketi xosil bo‘ladi. Bu impuls davomiyligi bitta razryad davomiyligidan katta bo‘ladi. Natijada xosil bo‘lgan xatolar paketining davomiyligi shovqin davomiyligiga mos bo‘lib, bunday shovqin tasodifiy bo‘lmagan shovqin xisoblanadi.

Bir karralik bunday xatolar paketini aniqlash va to‘g‘irlash uchun Fayra kodi qo‘llaniladi. Fayra kodini yasovchi polinom quyidagi ko‘rinishda bo‘ladi:

R (x) = g (x) (x⁰ +1)

g(x) – m - darajaga tegishli bo‘lgan;

t – darajali keltirilmaydigan ko‘pxad;

s – m ga karralik bo‘lmagan butun son;

g (x) – polinom m – darajaga tegishli deyiladi, agar m – x^m +1 ikkixad g (x) koldiqsiz bo‘linadigan eng kichik musbat son bo‘lsa.

Ixtiyoriy t uchun m = 2 ^t –1 darajaga tegishli bo‘lgan faqat bitta t darajali R(x) polinom mavjud. Masalan: t = 3, m = 2³ –1 = 7

R (x) = x³ + x² +1

Ya’ni R(x) = x³ +x² +1 ko‘pxad m=7 darajaga tegishli bo‘lgan polinom. Bu xolatda s soni m ga karralik bo‘lmagan, ya’ni qoldiqsiz bo‘linmaydigan quyidagi sonlar bo‘lishi mumkin: 15, 16, 17, 18, 19, 20 va xok.

t darajali keltirilmaydigan polinom deb – darajasi t dan kichik bo‘lgan xech qaysi polinomga qoldiqsiz bo‘linmaydigan ko‘pxadga aytiladi.

Chekli maydonning  elementining m – tartibi deb ^m = 1 bo‘ladigan m ning eng kichik qiymatiga aytiladi,  esa x^m –1 ko‘pxadning ildizi xisoblanadi.

Fayra kodining uzunligi s va m sonlarinning eng kichik umumiy karralisiga (EUK) teng bo‘ladi:

n = EUK (s, m)

Tekshiruv razryadlarining soni quyidagi ifoda orqali aniqlanadi:

r = c + t

Informatsion bitlarining soni esa quyidagiga teng:

k = n – c – t

To‘g‘irlanadigan xatolar paketining uzunligi v quyidagi tengsizlikni qanoatlantiradi:

t  v, c  2 v – 1

Fayra kodi bir vaqtning o‘zida v uzunlikdagi xamda undan kichik bo‘lgan xatolar paketini to‘g‘irlashi va d  v uzunlikdagi xatolar paketini aniqlashi mumkin:

s  v +  - 1, t  v

R(x) yasovchi ko‘pxaddagi x^s +1 ko‘paytuvchi s uzunlikdagi xatolar paketini aniqlashi va uzunligi v dan oshmaydigan xatolar paketining to‘liq qiymatini aniqlashi mumkin.

Xatolar paketini joylashishi va xolati to‘g‘risidagi ma’lumot esa g(x) ko‘paytuvchi yordamida aniqlanadi. Demak R(x) yasovchi ko‘pxaddagi xadlar mos ravishda bir karralik xatolar paketini tegishli qiymatini, xolatini, joyini aniqlash imkonini beradi.

Masalan: k=63, v=3, =9 ya’ni uzunligi v=3 ga teng va undan kichik bo‘lgan xatolar paketini to‘g‘irlovchi xamda bir vaqtning o‘zida uzunligii =9 ga teng va undan kichik bo‘lgan xatolar paketini aniqlovchi kodni qurish kerak bo‘lsin. U xolda:

t  v = 3 , c  v + - 1 = 3 + 9 -1 = 11

tengsizlik o‘rinli bo‘ladi. Bu xolatda 3-darajali keltirilmaydigan polinomni tanlab olamiz:

g (x) = x ³ +x ² +1

m=2^t – 1=7, c va m sonlarining kichik karralisi quyidagiga teng bo‘ladi:

n = EKUK (c, m) = EKUK (7, 77) = 77

Kodni yasovchi polinom quyidagi ko‘rinishga ega bo‘ladi:

R(x) = ( x³ +x² +1) (x¹¹ +1)

Shunday qilib, uzunligi v=3 va undan kichik bo‘lgan xatolar paketini to‘g‘irlovchi xamda bir vaqtning o‘zida uzunligi =9 va undan kichik bo‘lgan xatolar paketini aniqlovchi Fayra kodi n=77, k=63, c+t=r=14 kattaliklardan iborat.

Fayra kodi siklik kodlar sinfiga kiradi. Shuning uchun u siklik koddagi xususiyatlarga ega. Shu jumladan Fayra kodida kodlashtirish jarayoni ham siklik kodlarini kodlashtirish jarayoni kabi amalga oshadi.

Axborotlarni Fayra kodida kodlashtirish ikki xil usulda amalga oshiriladi:

1. Oddiy kodning k- elementli kombinatsiyasini R(x) yasovchi polinomga ko‘paytirish orqali kodlashtirish:

F (x) = Q (x) P (x)

2. Oddiy kodli kombinatsiyani x^r xadga ko‘paytirib, ko‘paytmaga uni R(x) yasovchi polinomga bo‘lish natijasida xosil bo‘lgan qoldiqni qo‘shish orqali:

F (x) = G (x)  x ^r + R (x)

Ya’ni

G (x)  x ^r = Q (x)  P (x) + R (x)
F (x) = G (x)  x ^r +R (x) = Q (x)  P (x)

F (x) – Fayra kodining polinomli ko‘rinishi.

Fayra kodi asos qilib olingan kodli kombinatsiyalarni muayyan tarzda tanlab olish orqali xosil qilinadi. Bu kodli kombinatsiyalar esa matritsa ko‘rinishida yozilib, shu matritsa orqali Fayra kodining tegishli kodli kombinatsiyalari xosil qilinadi. n ta ustun va k ta qatordan iborat bo‘lgan bunday matritsa xosil qiluvchi matritsa deyiladi.

Ikkinchi usul bo‘yicha kodlashtirish uchun, xosil qiluvchi matritsani tuzishni qarab chiqamiz. Bunday matritsaning qatorlarini tuzishda faqat bitta razryadida bir ishtirok etgan G(x) oddiy kodli kombinatsiyalar olinadi. Aynan shu kodli kombinatsiyalar x^r ga ko‘paytirilib, yasovchi polinomga bo‘linadi:

va natijada R_i(x) qoldiqlar topiladi. Matritsaning tegishli qatorlari

G_i (x)  x ^r + R _i (x)

ko‘rinishda yoziladi. Bunday matritsa ikkita qism matritsaga bo‘linadi:

- transponirlangan birlik matritsa;

C_{r, k} - R_i (x) qoldiqlardan iborat bo‘lgan r ustun va k qatorli qism matritsa.

Xosil qiluvchi matritsa G_{n, k} k ta kodli kombinatsiyani bevosita xosil qilish imkonini beradi. Qolgan 2^k - k – 1 ta kodli kombinatsiya xosil qiluvchi matritsa qatorlarini mod 2 bo‘yicha qo‘shish orqali aniqlanadi.

Misol sifatida n = 9, k = 4 parametrli Fayra kodini qurishni ko‘rib chiqamiz. Bu kodni qurish uchun

R (x) = (x ² + x + 1) (x ³ + 1) = x ⁵ + x ⁴ + x ³+ x²+ x + 1

yasovchi polinomni tanlaymiz. U xolda t = 2, m = 2 ^t –1 = 3, c = 3,

r = c + t = 5 bo‘ladi. Xosil qiluvchi matritsa quyidagi ko‘rinishga ega:

G _{9, 4} =  , C_{5, 4} 

transponirlangan matritsa quyidagiga teng:
0 0 0 1

= 0 0 1 0

0 1 0 0

1 0 0 0
S_5,4 matritsani tuzish uchun o‘ng tomoni nollar bilan to‘ldirilgan 1 ni yasovchi polinomga bo‘lish natijasida xosil bo‘lgan qoldiqlardan foydalaniladi.

100000000 111111

111111 1100

1-qoldiq 111110

111111

2-qoldiq  000010

000000

3-qoldiq  000100

000000

4-qoldiq  00100

S_{5, 4} quyidagi ko‘rinishda bo‘ladi:

1 1 1 1 1

S _5,4 = 0 0 0 0 1

0 0 0 1 0

0 0 1 0 0

Umumiy xolatda (9, 4) Fayra kodini xosil qiluvchi matritsa quyidagicha yoziladi:

0 0 0 1 1 1 1 1 1

G _9,4 = 0 0 1 0 0 0 0 01

0 1 0 0 0 0 1 0

1 0 0 0 0 0 1 0 0

G _9,4 matritsa orqali istalgan 4-razryadli axborotlarni kodlashtirish mumkin. Masalan G(x) = x³ + x² + 1  1011 ni kodlashtirish kerak bo‘lsin. Buning uchun G _9,4 matritsaning 1, 2, 4 chi katorlari o‘zaro mod 2 bo‘yicha qo‘shiladi:

000111111 001000001 100000100 = 101111010 yoki

F (x) = x ⁸ + x ⁶ + x ⁵ + x ⁴ + x ³ + x

Fayra kodida kodlashtirish algoritmi 12.1-rasmda keltirilgan. U quyidagi bosqichlardan (bloklardan) iborat:

1. 
   Fayra kodi parametrlari n, k, r lar kiritiladi.
   
2. 
   g(x) keltirilmaydigan ko‘pxad va k ning darajasi t kiritiladi;
   
3. 
   kiritilgan g(x) va uning darajasi t chop etiladi;
   
4. 
   qo‘shimcha ko‘pxad (x^s +1) va uning darajasi s ni kiritish;
   
5. 
   M ning qiymati M=2^t –1 formula bo‘yicha xisoblanadi;
   
6. 
   S sonini xisoblab chiqarilgan M soniga karraliligi tekshiriladi. Agar karralik bo‘lsa, 4-blokka o‘tiladi. Unda (x^s +1) ko‘pxad va uning darajasi s qaytadan kiritiladi. Agar shart bajarilmasa, keyingi 7-blokka o‘tiladi;
   
7. 
   Kiritilgan (x^s +1) va uning darajasi s chop etiladi;
   
8. 
   R(x) yasovchi polinom kiritiladi;
   

9) Kiritilgan R(x) polinom chop etiladi;

10) Kodning informatsion qismi k₁ (x) kiritiladi;

11) k₁ (x) kombinatsiyaga muvofiq n1 parametr n1 = k₁ + r formulaga asosan aniqlanadi;

12) k₁ (x) ni r razryad chapga siljitish ishi bajariladi;

13) Xosil bo‘lgan kombinatsiya R(x) yasovchi polinomga bo‘linadi va R(x) qoldiq xosil qilinadi;

14) Xosil bo‘lgan R(x) qoldiq k₁ (x) informatsion qismga biriktiriladi;

15) Kodlangan axborot chop etiladi.

12.1-rasm. Fayra kodida kodlashtirish algoritm

12.1-rasm. Fayra kodida kodlashtirish algoritmi (davomi)