Axborot va kodlash nazariyasi asoslari

9-ma’ruza uchun nazorat savollari
1. Rekurrent kodlar yordamida kodlashga tushuncha bering?

2. Rekurrent kodlar yordamida xatoliklarni tuzatishga tushuncha bering?

3. Zanjir rekurrent kodni qurish prinsipi nimalardan iborat?

4. Koder sxemasiga tushuncha bering?

5. Dekoder sxemasiga tushuncha bering?
10-ma’ruza. Ikkilik Bouza-Choudxuri-Xekvingem kodlari
Reja:

1.BChX kodlari.

2. BChX kodlariga misol.

Qulay kodlash va dekodlash algoritmlari taklif etilgan notasodifiy kodlarning orasidagi eng mashxurlaridan biri BChX (Bouza-Choudxuri-Xekvingem) kodlaridir. BChX kodlari kodlash va dekodlash jarayonlarini sezilarli darajada osonlashtirgan, aniq algebraik strukturaga ega bo‘lgan siklik kodlar oilasiga mansubdir. Hosil qilinadigan BChX kodning polinomi kod uzunligi va berilgan kod masofasi d₀ ≥ 5 bilan aniqlanadi. BChX kodi uzunligi n=2^m-1 ifodasi orqali aniqlanadi,

bu yerda m – istalgan butun son, m=log₂(n + 1).

Tekshiriladigan razryadlar soni quyidagicha aniqlanadi:

BChX kodning hosil qilinadigan polinomi minimal polinomlarning eng kichik umumiy karralisi hisoblanib qaysiki tartibi d_{0 –2} ga teng.

P(x) = EKUK {m₁(x) * m₃(x) * m₅(x) *… * m_d0-2(x) }

 BChX kodlari t karrali va undan kamroq erkin xatolarni to‘g‘irlaydigan siklik kodlarning katta sinfini tashkil etadi. BChX kodlari uchun ham siklik kodlarning barcha asosiy xususiyatlari xos. BChX kodlari n, k, g(x) kattaliklari orqali aniqlanadi,

bu yerda: n - kodli kombinatsiyadagi elementlar miqdori;

k – BChX kodining axborot elementlari miqdori;

g(x) –BChX kodini keltirib chiqaradigan ko‘pxadi.

1. BChX kodlarining parametrlari quyidagi shaklda tanlanadi:

n = 2^m-1 formulasidan kelib chiqib , n soni tanlanadi, bu yerda m –istalgan butun son.

2. To‘g‘rilash shart bo‘lgan xatolar miqdori aniqlanadi. Bu yerdan BChX kod d_o > 2t + 1 ga ega bo‘lishi lozim.

3. d_o ga bog‘liq holda g(x)=EKUK (m₁(X)….m_2t (x )), hisoblanadi bu yerda m₁ (x) ... m_2t (x) – keltirilmagan minimal ko‘pxadlar.

4. Tekshiriladigan belgilar soni quyidagi formula orqali hisoblanadi:

  r = m * t

5. k axborot belgilar soni quyidagi formula orqali hisoblanadi:

k = n - r = (2^m-1) - r

BChX kodni kodlash quyidagidan iborat:

Zarur (x)=_0…_k-1 kod kombinatsiyasini x^n-k razryadga chapga siljitib quyidagi ko‘rinishni olamiz

 

X ^n-k  (x)=X ^n-k (₀ +…+ _k-1X ^k-1)= ₀ X ^n-1 +… _k-1X ^n-1

 

X^n-k  (x) ko‘pxadini g(x)ga bo‘lamiz va bo‘linmani quyidagi ko‘rinishda yozamiz:

  X^n-k  (x)=g(x)q(x)+r(x) ,

 

bu yerda q(x)- bo‘linma;

r(x)- g(x) ga bo‘lingandagi qoldiq.

g(x) ko‘pxadining darajasi n-k ga teng ekan , r(x) ning darajasi n-k-1 ga teng bo‘ladi. Bunda X^n-k(x) + r (x) = g(x) q(x), bu yerdan bo‘linadigan BChX kodning izlangan kodli kombinatsiyasini olamiz.

BChX kodi t=3, n=15 uzunligidagi kombinatsiyalarni 3 karra xatolarni to‘g‘rilashga qodir,

m=log₂(n+1)=log₂₍15+1)=4

jadvaldan polinomlarni tanlaymiz

R(x)=EKUK{m₁(x)m₃(x)…m_d-2(x)} P(x)=10011x11111x111=10100110111

(tahminan)

R(x)=x¹⁰+x⁸+x⁵*x⁴+x²+x+1 r=10

t_osh=3

=7

k=n-r=15-10=5

Misol. 3 xatoni to‘g‘irlovchi BChX kod yasaymiz, kodli kombinatsiya uzunligi n=15. M=log₂(n+1)=log₂(15+1)=4 rMinimal ko‘pxadlar jadvalidan minimal ko‘pxadlarni tanlaymiz: M₁(X)=10011; M₃(x)=11111; M₅(x)=111. Bunda g(x)= 10100110111, va r=10, k=n-r=5, (15,5) kodga egamiz.

10101 kombinatsiyasini kodlaymiz

101010000000000|10100110111

10100110111 |

000011101110000

10100110111

01001000111

BChX kodi bilan kodlangan kombinatsiya quyidagi ko‘rinishga ega bo‘ladi: 10101 1001000111

2 va 10 pozitsiyalariga xatolarni kiritamiz: 111011001100111.

Hosil qilinadigan polinomga qabul qilingan kombinatsiyani bo‘lamiz:

  111011001100111 10100110111

10100110111

010010100010

10100110111

0011001010111

10100110111

01111110110 W=8

 Olgan W=8 qoldig‘imizning og‘irligi to‘g‘irlangan xatolar sonidan katta ekan, kombinatsiyani siklik siljitishni va hosil bo‘ladigan polinomga qoldiq ikkiga teng og‘irlikda bo‘lgunicha bo‘lishni amalga oshiramiz. 

110110011001111|10100110111

10100110111 |

11111110111

10100110111

10110000001

10100110111

1011011011 W=7

 

Olgan W=7 qoldig‘imizning og‘irligi to‘g‘irlangan xatolar sonidan katta ekan, kombinatsiyani siklik siljitishni va hosil bo‘ladigan polinomga qoldiq ikkiga teng og‘irlikda bo‘lgunicha bo‘lishni amalga oshiramiz.

101100110011111|10100110111

10100110111

10101110111

10100110111

10000001 W=2

 Modul bo‘yicha oxirgi ikkita bo‘linuvchilarni qoldiqlari bilan qo‘shamiz 10110011001111110000001=101100100011110.

Olgan ketma-ketligimizni ikkita razryadga o‘ngga siklik siljitamiz:

010110010001111, 101011001000111- bu ketma-ketlik yuborilgan hisoblanadi.

 BChX ni dekodlash algoritmi bir nechta bosqichdan iborat:

1.Sindromni hisoblash.

2. Hatolar lokatori ko‘pxadini hisoblash.

3. Hatolar lokatori ko‘pxadi ildizlarini topish.

4. Xatolarni to‘g‘rilash.