k n r (2m 1) r
BChX kodini kodlash quyidagidan iborat: Zarur
( x) 0 ... k1
kod
kombinatsiyasini
xn k
razryadga chapga siljitib shu sonni olamiz:
0 k 1 0 k 1
xnk (x) xnk ( ... xk1 ) xn1 ... xn1
xnk (x) ko‗pxadini g(x)ga bo‗lamiz va bo‗linmani quyidagi ko‗rinishda yozamiz:
xnk (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 xnk (x) r(x) g(x)q(x) , bu yerdan bo‗linadigan BChX kodning
izlangan kodli kombinatsiyasini olamiz.
BChX kodlarning boshqa siklik kodlardan farqi shundaki, keltirib bo‗lmaydigan polinomlar GF(q) kengligini kengaytirishda ildizga ega
bo‗lishi mumkin. Agar q, (q=qm) sonining darajasi bo‗lsa, bunda m-1 darajali polinom kengligi elementlaridir, ularning koeffitsienti GF(p) oddiy kengligida yotadi.
GF(q) oddiy kengligida kengaytirilgan kengliklar Galua maydoni deyiladi. GF(qm) maydoni elementlari m razryadli vektorlarning q elementi bilan ifodalanadi.
Misol. 3 xatoni to‗g‗rilovchi BChX kod yasaymiz, kodli kombinatsiya uzunligi n=15. M=log2(n+1)=log2(15+1)=4 rMinimal ko‗pxadlar jadvalidan 1 va 3 minimal ko‗pxadlarni tanlaymiz: M1(X)=10011; M3(x)=11111; M5(x)=111.
Bunda g(x)= 10100110111, va r=10, k=n-r=5, (15,5) kodga egamiz. 10101 kombinatsiyasini kodlaymiz:
Yuqorida keltirilgan kombinatsiyani polinom ko‘rinishga keltiramiz:
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:
Yuqorida keltirilgan kombinatsiyani polinom ko‘rinishga keltiramiz:
Olingan W=8 qoldiqimizning vazni to‗g‗irlangan xatolar sonidan katta ekan, kombinatsiyani siklik siljitishni va hosil bo‗ladigan polinomga qoldiq ikkiga teng vaznda bo‗lgunicha bo‗lishni amalga oshiramiz:
Yuqorida keltirilgan kombinatsiyani polinom ko‘rinishga keltiramiz:
Olingan W=7 qoldig‗imizning vazni to‗g‗irlangan xatolar sonidan katta ekan, kombinatsiyani siklik siljitishni va hosil bo‗ladigan polinomga qoldiq ikkiga teng vaznda bo‗lgunicha bo‗lishni amalga oshiramiz:
Yuqorida keltirilgan kombinatsiyani polinom ko‘rinishga keltiramiz:
Modul bo‗yicha oxirgi ikkita bo‗linuvchilarni qoldiqlari bilan qo‗shamiz 101100110011111 10000001 = 101100100011110.
Olingan ketma-ketligimizni ikkita razryad o‗ngga siklik siljitamiz: 010110010001111, 101011001000111- bu ketma-ketlik yuborilgan hisoblanadi.
BChX kodini dekodlash algoritmi bir nechta bosqichdan iborat: 1.Sindromni hisoblash.
Xatolar lokatori ko‗pxadini hisoblash.
Hatolar lokatori ko‗pxadi ildizlarini topish.
Xatolarni to‗g‗irlash.
Misol. n=15 uzunlikdagi kodli so‗zlar va kodli so‗zlar orasidagi d=5 minimal masofali BChX kodini qurish kerak. Oddiy ko‗phadning darajasi q=log2(n+1)=4 ga teng va uning o‗zi x4+x3+1 ga teng. α bu ko‗phadning ildizi bo‗lsin, u holda α2 va α4 ham uning ildizlari bo‗ladi. α3 uchun minmal ko‗phad x4+x3+x2+x+1 bo‗ladi.
Demak, g(x)=EKUK (x4+x3+1, x4 +x3+x2+x+1)=
= (x4+x3+1)(x4+x3+x2+x+1)=x8+x4+x2+x+1.
Olingan ko‗phadning darajasi 8 ga teng, demak, qurilgan BChX kod (7,15) kodli bo‗ladi. 1000100 so‗z yoki a(x)=x4+1 a(x)g(x)=x12+x6+x5+x2+x+1 yoki 111001100000100 kodli so‗z bilan kodlanadi.
n =2q-1 uzunlikdagi va kodli so‗zlarli va nazorat simvollari soni q(d-1)/2 dan ortiq bo‗lmagan d toq minimal masofali ikkilik BChX kodni qurish mumkin.
Amalda qo‗llanilgan birinchi BChX kod 5 gacha karrali xatoliklarni to‗g‗rilaydigan (92,127) kod bo‗lgan, ammo eng keng qo‗llanishni 6 gacha karrali xatoliklarni aniqlaydigan (231, 255) kod oldi. O‗rtacha uzunlikdagi BChX kod takomillashgan va kvazi takomillashgan kodlardan juda uzoqda emas. Xemming kodlari, masalan, BChX kodlar hisoblanadi, kodli so‗zi minimal 5 vaznli BChX-kodlar kvazi takomillashgan kodlar hisoblanadi. Lekin kodli so‗zlar uzunliklarining ortishi bilan BChX kodlarning sifati pasayadi.
|