P(x) = (x 2 + x + 1) (x 3 + 1) = x 5 + x 4 + x 3+ x2+ x + 1
yasovchi polinomni tanlaymiz. U holda t = 2, m = 2 t –1 = 3, c = 3, r = c
+ t = 5 bo‗ladi. Hosil qiluvchi matritsa quyidagi ko‗rinishga ega:
4
E
t transponirlangan matritsa quyidagiga teng:
E
|
0
|
0
|
0
|
1
| |
0
|
0
|
1
|
0
| |
0
|
1
|
0
|
0
| |
1
|
0
|
0
|
0
|
t
4
C5,4 matritsani tuzish uchun o‗ng tomoni nollar bilan to‗ldirilgan 1 ni yasovchi polinomga bo‗lish natijasida hosil bo‗lgan qoldiqlardan foydalaniladi.
C 5, 4 quyidagi ko‗rinishda bo‗ladi:
|
1
|
1
|
1
|
1
| |
0
|
0
|
0
|
1
| |
0
|
0
|
1
|
0
| |
0
|
0
|
1
|
0
| |
ayra kodin
|
C5,4
Umumiy holatda (9,4) F i hosil qiluvchi matritsa
|
quyidagicha yoziladi:
|
|
|
0
|
0
|
0
|
1
|
1
|
1
|
1
|
1
|
1
|
|
0
|
0
|
1
|
0
|
0
|
0
|
0
|
0
|
1
|
G9,4
|
0
|
1
|
0
|
0
|
0
|
0
|
0
|
1
|
0
|
|
1
|
0
|
0
|
0
|
0
|
0
|
1
|
0
|
0
|
G9,4 matritsa orqali istalgan 4-razryadli axborotlarni kodlashtirish mumkin.
Masalan G(x) = x3 + x2 + 1 1011 ni kodlashtirish kerak bo‗lsin. Buning uchun G9,4 matritsaning 1, 2, 4 chi qatorlari o‗zaro mod 2 bo‗yicha qo‗shiladi:
000111111 001000001 100000100 = 101111010 yoki
F(x) = x8 + x6 + x5 + x4 + x3 + x
Fayra kodida kodlashtirish algoritmi 3.14 rasmda keltirilgan. U quyidagi bosqichlardan (bloklardan) iborat:
3.14-rasm. Fayra kodida kodlashtirish algoritmi
Fayra kodi parametrlari n, k, r lar kiritiladi.
g(x) keltirilmaydigan ko‗phad va k ning darajasi t kiritiladi;
Kiritilgan g(x) va uning darajasi t chop etiladi;
Qo‗shimcha ko‗pxad (xc +1) va uning darajasi c kiritiladi;
M ning qiymati M=2t –1 formula bo‗yicha hisoblanadi;
C sonini hisoblab chiqarilgan M soniga karraliligi tekshiriladi. Agar karralik bo‗lsa, 4-blokka o‗tiladi. Unda (xc +1) ko‗pxad va uning darajasi s qaytadan kiritiladi. Agar shart bajarilmasa, keyingi 7-blokka o‗tiladi;
Kiritilgan (xc +1) va uning darajasi c chop etiladi;
P(x) yasovchi polinom kiritiladi;
Kiritilgan P(x) polinom chop etiladi;
Kodning axborot qismi k1(x) kiritiladi;
k1(x) kombinatsiyaga muvofiq n1 parametr n1 = k1 + r formulaga asosan aniqlanadi;
k1(x) ni r razryad chapga siljitish ishi bajariladi;
Hosil bo‗lgan kombinatsiya P(x) yasovchi polinomga bo‗linadi va R(x) qoldiq hosil qilinadi;
Hosil bo‗lgan R(x) qoldiq k1(x) axborot qismga biriktiriladi;
Kodlangan axborot chop etiladi.
3.14-rasm. Fayra kodida kodlashtirish algoritmi (davomi)
Fayra kodida kodlashtirilgan axborotlarni dekodlash usullari. Fayra kodi, n – elementli kodli kombinatsiyada hosil bo‗luvchi, uzunligi v va undan kichik bo‗lgan bir karralik xatolar guruhini to‗g‗irlaydi va bir
vaqtning o‗zida uzunligi v bo‗lgan bir karralik xatolar guruhini aniqlaydi.
Fayra kodida kodlashtirilgan axborotlarni dekodlashning ikki xil usuli mavjud. Ularning har birini alohida qarab chiqamiz:
1 usul. f(x) uzatilgan kodli kombinatsiyaga xi B(x) ko‗rinishdagi xatolar paketi ta‘sir qilsin.
B(x) – xatolar paketini ifodalovchi ko‗phad;
xi - xatolar paketi boshlangan razryad.
Agar qabul qilingan kodli kombinatsiya P(x) yasovchi polinomga qoldiqsiz bo‗linsa, demak uzatilgan kombinatsiya to‗g‗ri qabul qilingan yoki xatolar aniqlanmay qolgan. Aks holda esa, uzatilgan kodli kombinatsiya xato qabul qilingan hisoblanadi va uni aniqlash hamda to‗g‗irlash talab etiladi. Demak, qoldiq noldan farqli bo‗lsa, u holda qabul qilingan kombinatsiyada quyidagi ko‗rinshdagi xatolar mavjud bo‗ladi:
xi B(x) g(x) S(x) R(x)
R(x) – darajasi (n – k) dan kichik bo‗lgan qoldiq ko‗phad.
Xatolarni to‗g‗irlash uchun R(x) qoldiq ko‗rinishiga qarab xi B(x) ni topish talab etiladi. Shundan so‗ng qabul qilingan vektor va xi B(x) larni o‗zaro mod 2 bo‗yicha qo‗shish orqali xatolar to‗g‗irlanadi. Agar xi B(x) to‗g‗irlanadigan xatolar paketining k – sinfiga kirsa, u holda
1
xi B(x) x n1 R (x) ko‗rinishda bo‗ladi.
1
Bu yerda R (x) x j R(x) va i n j bilan ifodalanadi.
Xatolar vektori sifatida R1(x) qoldiq olinadi va bu kombinatsiya qabul qilingan kodli so‗zning (n –1) – razryadidan boshlanadi deb qaraladi. Bu usuldagi dekodlash algoritmi quyidagi ketma-ketlik asosida olib boriladi:
qabul qilingan kodli kombinatsiya R(x)ga bo‗linadi. Natija qoldiqsiz chiqsa demak, kombinatsiya xatosiz qabul qilingan yoki xato aniqlanmay qolgan. Agar R(x) qoldiq hosil bo‗lsa navbatdagi bosqichga o‗tiladi;
õi ( i 1, n)
ga ko‗paytiriladi va P(x) ga
R1(x) qoldiqning to‗g‗irlanadigan kombinatsiya bo‗lishi
tekshiriladi.
xi R(x)ni P(x)ga bo‗lish, i ning R1(n) qoldiq to‗g‗irlanadigan kombinatsiya bo‗lgunga qadar davom ettiriladi. Lekin bu operatsiya n martadan oshmasligi kerak. To‗g‗irlanadigan kombinatsiyaning hosil bo‗lmasligi esa, qabul qilingan kombinatsiyaning buzilish darajasi, kodning to‗g‗irlash imkoniyatidan oshib ketganligidan dalolat beradi;
agar i qadamdan so‗ng R1(x) qoldiq to‗g‗irlanadigan holatga kelsa, u holda xatolarni to‗g‗irlash uchun, qabul qilingan kombinatsiyaga hosil bo‗lgan qoldiqni j = (n- i) razryaddan boshlab mod 2 bo‗yicha qo‗shish kerak.
2 usul. Dekodlashning eng muhim bo‗lgan ikkinchi usulini ko‗rib o‗tamiz. Aloqa kanaliga uzunligi v dan oshmaydigan bir karralik xatolar paketi ta‘sir etsin. Aloqa kanali chiqishida quyidagi xato sodir bo‗lgan kombinatsiya olinadi:
F (x) f (x) xi B(x)
f(x) – P(x) ga bo‗linadigan uzatilgan kombinatsiyaning polinomi;
B(x) – xatolar paketiga mos keluvchi darajali ko‗phad;
i – kodli kombinatsiyadagi xatolar paketi boshlangan razryad. Bu usulda dekodlash quyidagi bosqichlarda olib boriladi:
qabul qilingan polinom F(x)ni P(x) yasovchi ko‗pxadning ko‗paytuvchilari g(x) va (xs +1)larga bo‗lib, B1(x) va B2(x) qoldiqlar aniqlanadi;
B1(x) va B2(x) polinomlar x ning ketma-ket darajalariga ko‗paytiriladi va har qadamda g(x) hamda (xc +1) polinomlarga bo‗lish natijasida hosil bo‗luvchi qoldiqlar hisoblanadi. Bu holda har safar yangi hosil bo‗lgan qoldiqlar o‗zaro solishtiriladi;
bosqich yuqorida aytilgan qoldiqlar o‗zaro tenglashgunga qadar davom ettiriladi. O‗zaro mos kelgan qoldiq esa xatolar paketining ko‗rinishini bildiradi. Xatolar paketining joylashgan o‗rni I ni topish uchun esa tengliklar nazariyasi apparatidan foydalaniladi.
Ko‗paytirilgan xi va xj ning i va j daraja ko‗rsatkichlarida, qoldiqlar o‗zaro mos kelsin. Unda xatolar paketi boshlangan razryad I quyidagicha topiladi:
I - ( i D1 + j D2) mod n
bu yerda D1 1 mod m; D1 0 mod s;
D2 0 mod s; D2 1 mod m
xatoni to‗g‗irlash uchun qabul qilingan F(x) kombinatsiyaga aniqlangan xI B(x) mod 2 bo‗yicha qo‗shiladi.
Ikkinchi usulda keltirilgan algoritmni tushuntirish uchun quyidagi misolni keltiramiz:
P(x) = (x4 + x +1) (x7 +1) = x11 +x8 + x7 + x4 +x +1
Yasovchi polinom uzunligi B=4 va undan kichik bo‗lgan xatolar paketini to‗g‗irlovchi Fayra kodini hosil qiladi. Berilgan P(x) yasovchi polinomli Fayra kodining parametrlari quyidagilar:
t = 4, m = 15, c = 7, n = 105, k = 94.
Aloqa kanali orqali quyidagi
f (x) = x31+x28+x27+x24+x21+x20+x14+x10+x8+x3+x+1
kodli kombinatsiya uzatiladi. Kanalda esa B(x) = x19(x3+x+1) xatolar paketi hosil bo‗ldi va kanal chiqishidagi polinom quyidagi ko‗rinishga keldi:
F(x)=f(x)+xIB(x)=x31+x28+x27+x24+x22+x21+x19+x14+x10+x8+
+x3+x+1
F(x)ni g(x) = x4+x+1 va (xc+1) = x7+1 larga bo‗lib qoldiqlarni aniqlaymiz:
Demak bo‗lish natijasida hosil bo‗lgan qoldiqlar
B1(x)=x3+x2+x, B2 (x)=x6+x5+x ga teng.
Hosil bo‗lgan qoldiqlar tenglangunga qadar ko‗paytirilishi zarur bo‗lgan xi va xj larning i va j daraja ko‗rsatkichlari aniqlanadi:
x11 B1 (x) = x11 (x3 +x2+x) = x14 +x13+x12
x2 * B2(x)= x2(x6+x5+x)=x8 + x7 +x3
x ning i = 11 va j = 2 daraja qiymatlarida qoldiq bir xil bo‗ladi:
B (x)=x 3+x+1
Xatolar paketining o‗rni aniqlanadi: I - (11 D1 + 2 D2 ) mod 105
D1 1 mod 15, D2 0 mod 7
D2 1 mod 7, D2 0 mod 15
D1 = 16, 31, 46, 61, 76, 91
D2 = 7, 14, 21, 28, 35, 42, 49, 56, 63, 70, 77, 84, 91
Demak, D1 = 91ga teng
D2 = 8, 15
D2 = 15
Tengliklardan ko‗rinadiki D1 = 91, D2 = 15 bo‗ladi. Endi I ni aniqlasak bo‗ladi:
I - (1.91 + 2.15 ) mod 105
I - 86 mod 105
Bu ifodadan I = 105 – 86 = 19 ekanligi kelib chiqadi.
Xatolar paketining ko‗rinishi B(x)= x3+x+1 bo‗lib, u 19-razryaddan boshlanar ekan.
Xatolar paketini to‗g‗irlash uchun qabul qilingan F(x) kodli kombinatsiyaga x19(x3+x+1) polinom mod 2 bo‗yicha qo‗shiladi.
F(x)=x22+x20+x19=x31+x28+x27+x24+x21+x19+x14+x10+x8+x3+x+1+
+x22+x20+x19= =x31+x28+x27+ x24 + x21+x20+x14+x10+x8+x3+ x +1
Shu tariqa dekoderda quyidagi to‗g‗irlangan kodli kombinatsiya tiklanadi:
F(x)+xI B(x) = x31+x28+x27+x24+x21 +x20+x14+x10+x8+x3+x+1
Ushbu algoritmni blok-sxema ko‗rinishdagi tahlili 3.15-rasmda berilgan. Rasmdagi bloklarning vazifasini izohlab o‗tamiz:
3.15-rasm. Fayra kodini dekoderlash algoritmi
|
(xc+1) ga bo‗luvchi qism dasturga murojaat: QOL J
|
|
|
B1(x)ni I razryadga chapga surish
|
|
|
g(x) ga bo‗luvchi qism dasturga murojaat: QOL I
|
3.15-rasm. Fayra kodini dekoderlash algoritmi (davomi)
Xatolar paketi boshlangan razryad nomeri «I1» kiritiladi;
Xatolar paketining qiymati B(x) kiritiladi;
Kodlangan f(x) kombinatsiyaga «I1» razryaddan boshlab B(x)
xato kiritiladi va F(x) xato kombinatsiya hosil qilinadi;
F(x) xato kombinatsiya chop etiladi;
F(x) ni P(x) yasovchi polinomga bo‗lish bajariladi va R(x) qoldiq olinadi;
R(x) qoldiq tekshiriladi. Agar R(x) = 0 bo‗lsa, u holda 30-blokka o‗tiladi. Unda F(x) kombinatsiyada xato yo‗q degan xabar chop etiladi va dastur ishi yakunlanadi. Agar shart bajarilmasa navbatdagi 7-blokka o‗tiladi;
F(x) kombinatsiyada xato mavjud degan xabar chop etiladi;
F(x) ni g(x) ga bo‗lish bajariladi va B1(x) qoldiq hosil qilinadi;
F(x) ni (xs+1) ga bo‗lish bajariladi va B2(x) qoldiq hosil qilinadi;
Qoldiq B1(x) ga ko‗paytirish kerak bo‗lgan xi ning boshlang‗ich darajasi beriladi;
Qoldiq B2(x) ga ko‗paytirish kerak bo‗lgan xj ning boshlang‗ich darajasi beriladi;
B2(x) ni J razryad chapga surish ishi bajariladi ya‘ni xjga ko‗paytiriladi;
Hosil bo‗lgan kombinatsiya (xc+1)ga bo‗linadi va qoldiq j hosil qilinadi.
B1(x) ni I razryad chapga surish ishi bajariladi (xi ga ko‗paytiriladi).
Hosil bo‗lgan natija g(x) ga bo‗linadi va QOLI olinadi.
QolI va QOLj larning tengligi solishtiriladi. Agar qoldiqlar teng bo‗lmasa 17 blokka o‗tiladi.
x j ning navbatdagi daraja ko‗rsatkichi olinadi, ya‘ni J daraja bir birlikka orttiriladi.
J ning kod uzunligi n1 dan kattaligi tekshiriladi. Agar shart bajarilmasa 12-blokka o‗tiladi, ya‘ni sikl takrorlanadi. Agar shart bajarilsa 19-blokka o‗tiladi;
xi ning navbatdagi daraja ko‗rsatkichiga o‗tiladi, ya‘ni I daraja bir birlikka oshiriladi;
I ning n dan kattaligi tekshiriladi. Agar shart bajarilmasa 11- blokka o‗tiladi. Agar shart bajarilsa 21-blokka o‗tiladi;
«Xatolarni to‗g‗irlash imkoni yo‗q» degan xabar chop etiladi va dastur ishi yakunlanadi. 16-blokdagi shart bajarilganda 22-blokka o‗tiladi;
Bir xil bo‗lgan qoldiq B(x) (QOL I = QOL J ) chop etiladi;
Qoldiqlari teng bo‗lgan daraja ko‗rsatkich I va J lar chop etiladi;
D1 ning qiymati topiladi;
D2 ning qiymati aniqlanadi;
D1 va D2 lar asosida xatolar paketi boshlangan I razryad aniqlanadi;
F(x) xato kombinatsiya to‗g‗irlanadi;
To‗g‗irlangan kombinatsiya chop etiladi; Dastur ishi yakunlanadi.
| 