r - shakllanuvchi polinom darajasi.
Kodlashtirishning mazkur usuli quyidagilarga asoslangan:
Kodli kombinatsiya a=(a0, a1, ..., ak-1) xr razryadlar bilan chapga siljiydi (siljish xr ga ko‗paytirishga o‗xshash bo‗ladi );
Siljish natijasida olingan kombinatsiyani a=(ak-1, ..., an-1),
shakllangan polinomga bo‗lamiz g(x);
R(x) ni bo‗lishdan olingan qoldiq (a0,, ..., an-1) kodli
kombinatsiya o‗rniga joylashtiriladi.
Misol. Ko‗phadga mos kombinatsiyani kodlashtirish uchun (110101101101),
φ(x)=x11+x10+x8+x6+x5+x3+x2+1, dastlab x11 ga ko‗paytiramiz, keyinchalik, xrφ(x) ni shakllangan polinom g(x)ga bo‗lamiz va R(x) qoldiqni topamiz. Bo‗lish natijasida quyidagini topamiz:
R(x)= x10+x9+x8+x6+x5+x4+ x3+x2. Kodli ko‗phad xrφ(x) va R(x) ni qo‗shish yo‗li bilan shakllanadi.
X
X
X
xrφ (x)+R(X)=x22+ 21+ 19+x17+x16+x14+x13+ 11+x10+x9+x8+x6+x5+x4+x3+x2
Bu ko‗phad siklik kod kombinatsiyasiga mos keladi:
|
110101101101
|
11101111100
| |
Axborot qismi
|
tekshiriladigan qism
|
usul: Shakllanadigan g(x) polinomga ko‗paytirish
F (x) h(x)g(x)
Mazkur usul kodli kombinatsiyani φ(x) shakllanadigan hosil qiluvchi polinomga ko‗paytirishga g(x) asoslangan. Natijada notizimli kodli kombinatsiya olinadi, bunda axborot va tekshiriladigan razryadlarni aniqlash mumkin emas.
Misol. φ(x)=x11+x10+x8+x6+x5+x3+ x2+1 ko‗phadni g(x)=x11+x9+x7+x6+x5+x+1 ga ko‗paytirish kerak. Ko‗paytirish modul 2ga ko‗ra qo‗shishdan foydalanib amalga oshiriladi. Natijada quyidagini olamiz:
φ(x)g(x)=x22+x2l+x20+x18+x16+x15+x14+x13+x10+x8+x7+x6+x4+x2+x+l.
Bu ko‗phad siklik kod kombinatsiyasiga mos keladi:
11101011110010111010111.
usul: tuzilgan va tekshirilgan matritsadan foydalanish. Bu usul tuziladigan va g(x) tekshiriladigan H(x) matritsalardan foydalanishga asoslangan.
Chiziqli kodlar kabi siklik kod juft matritsalarga beriladi: hosilaviy va tekshirilgan. Hosilaviy matritsa ikkiga bo‗linadi: axborot va tekshiriladigan.
Axborot matritsasi k ustun, tekshiriladigan esa - n ustunga ega bo‗ladi. Axborot matritsasi sifatida birlik matritsani olish qulay. Goley kodining k axborot razryadlari soni 12ga teng, axborot matritsasining o‗lchamliligi mos ravishda E(x)=2 12 bo‗ladi. U quyidagi ko‗rinishda bo‗ladi:
E12, 12
000000000001
000000000010
000000000100
000000001000
000000010000
000000100000
000001000000
000010000000
000100000000
001000000000
010000000000
100000000000
Cr,k, kabi belgilangan tekshiriladigan matritsani tuzish uchun quyidagi usuldan foydalanamiz: faqat yagona birlikdan iborat bo‗lgan Q(x) kombinatsiyani tanlaymiz va uni, g(x) polinomga bo‗lib, R(x) qoldiqni olamiz, natijada tekshiriladigan matritsa qatori yuzaga keladi.
Birlik vektor 00000000000100000000000 ga teng bo‗lib, bunda matritsaning birinchi qatori C1(x) quyidagi tarzda bo‗ladi:
C 1(x)=R(x)= 01011100011
Shunga o‗xshash tarzda birlikni har safar siljitib tekshiriladigan C(x) matritsaning keyingi qatorlarini olamiz. Mazkur operatsiyani i=1 k marta o‗tkazamiz.
Shunday qilib, tekshiriladigan matritsa quyidagi ko‗rinishda bo‗ladi:
C11, 12
01011100011
10111000110
00101101111
01011011110
10110111100
00110011011
01100110110
11001101100
11000111011
11010010101
11111001001
10101110001
Olingan matritsa C11,12 birlik matritsaga o‗ng tomonda yoziladi E12,12
buning natijasida hosilaviy matritsa G23, 12 olinadi:
Endi istalgan kombinatsiyani kodlashtirish uchun
( x)
birga teng
bo‗lgan ularning razryadlaridan tanlash yetarli va G23,12 matritsa qatorlarining tanlangan razryadlariga mos raqamlar bilan modul 2ga ko‗ra qo‗shish kerak.
Siklik kodlarda, aynan Goley kodlarida kodlashtirish jarayoni r
tekshiriladigan razryadlarni aniqlashga qaratilgan. Har bir tekshiriladigan
razryad tekshiriladigan nisbat yordamida aniqlanadi, r tekshiriladigan razryadlarni aniqlash r tekshiriladigan Hn,r matritsa nisbatni talab qiladi.
Tekshiriladigan matritsa H tekshirilgan polinom yordamida tuzilishi mumkin:
(xn 1)
bunda g-1 (x) - polinom.
h( x)
g 1 ( x) ,
h(x) = (x 23+1)/(x 11+x 9+x 7+x 6+x 5+x+1) -1 = x 12+x 11+x 10+x 9+x 8+x 5+x 2+1
ikkilamchi shaklda : 1111100100101.
H tekshiriladigan matritsaning keyingi qatorlari olingan kombinatsiyani siklik siljitish, tekshiriladigan polinom yordamida olinadi.
Natijada tekshiriladigan matritsa quyidagi ko‗rinishda bo‗ladi:
h23,11
11111001001010000000000
01111100100101000000000
00111110010010100000000
00011111001001010000000
00001111100100101000000
00000111110010010100000
00000011111001001010000
00000001111100100101000
00000000111110010010100
00000000011111001001010
00000000001111100100101
Shuningdek, kanonik shakldagi tekshiriladigan matritsa hosilaviy matritsadan olinishi mumkin. Bunday matritsaning shakllanishi hosilaviy matritsa qatorlarini ustunlarga o‗zgartirish yo‗li bilan amalga oshadi. Tuzish jarayoni 3.5- rasmda strelka bilan ko‗rsatilgan.
G23,12 – hosilaviy matritsa; E12,12 – axborot matritsasi; H23,11 – tekshiriladigan matritsa.
3.5-rasm. H tekshiriladigan matritsa shakllanish sxemasi Natijada tekshiriladigan matritsa quyidagi ko‗rinishda bo‗ladi:
01001001111110000000000
10010011111001000000000
01101110001100100000000
11011100011000010000000
11110001001100001000000
H 23,11 10101011100100000100000
00011110110100000010000
00111101101000000001000
01111011010000000000100
11110110100000000000010
10100100111100000000001
Tekshiriladigan matritsa odatda kodlashtirish va qayta kodlashtirish qurilmalarida foydalaniladi, u axborot belgisi bo‗yicha tekshiriladigan razryadlar algoritmini topishni belgilaydi.
Misol. H tekshiriladigan matritsa yordamida kombinatsiyadagi tekshiriladilan simvollarni aniqlaymiz: (110101101101). Birinchi
tekshiriladigan matritsani hisoblash uchun tekshiriladigan matritsa dastlabki qatorini olamiz:
|
B1=a2 a5 a8 a9 a10 a11 a12= 1001101=0
| |
B2=a11 a4 a7 a8 a9 a10 a11=1110110=1
| |
B3=a2 a3 a5 a6 a7 a11 a12=1001101=0
| |
B4=a1 a2 a4 a5 a6 a10 a11=1110110=1
| |
B5=a] a2 a3 a4 a8 a11 a12=1101001=0
| |
B =a a a a a a a =1001011=0
6 1 3 5 7 8 9 12
| |
B7=a4 a5 a6 a7 a9 a10 a12=1011111=0
| |
B8=a3 a4 a5 a6 a8 a9 a11=0101010=1
| |
B9=a2 a3 a4 a5 a7 a8 a10 = 1010101=0
| |
B10=a11 a2 a3 a4 a6 a7 a9 = 1101111=0
| |
B11=a1a3 a6 a9 a10 a11 a12=1011101=1
|
Shunday qilib, chiziqli kod kombinatsiyasi quyidagi ko‗rinishda bo‗ladi: (11010110110101010001001).
Dekoder vazifasi siklik kodning qabul qilingan elementli kombinatsiyasi bo‗ylab tashqi k-elementli kombinatsiyaga o‗zgartirishdir. Bunda siklik kodning samaradorligi uning xatolik kanali bo‗ylab uzatishda paydo bo‗ladigan to‗g‗rilash qobiliyati bilan baholanadi.
Goley kodini qayta kodlashtirish ikkita usul bilan amalga oshishi mumkin:
Meggit dekoderi bilan bir xil ma‘noni aniqlash va uch martalik xatoliklarni tuzatish mumkin, Berlekemp-Messi algoritmi esa faqat ikki martalik xatoliklarni to‗g‗rilaydi. Shuningdek oddiyligi va nisbatan arzonligi hisobiga BChX dekoder bilan taqqoslaganda Meggit dekoderi afzal sanaladi. Shuning uchun hozirgi kunda Goley kodining dekoderi sifatida Meggit dekoderdan foydalaniladi.
Meggit dekoderning ishlash tamoyillari oldingi razryadlarda joylashgan xatolarga asoslangan. Bunda quyidagi shartlar bajarilishi kerak: axborot qismining uzunligi xatolar sindromi uzunligidan katta bo‗lmasligi kerak.
Meggit dekoderi faqat eski razryadlarda joylashgan xatoliklar konfiguratsiyasi uchun sindromlarni tekshiradi. Qolgan pozitsiyalardagi xatoliklarni dekoderlash kodning siklik tuzilmasiga asoslangan va keyinroq amalga oshiriladi. Mos ravishda sindromlar jadvali nol
bo‗lmagan koeffitsientli xatolik ko‗phadiga mos sindromlardan iborat en_i. Har hisoblangan sindrom bu jadvalda joylashgan bo‗lsa u en_i tuzatiladi. Keyinchalik qabul qilingan so‗z siklik siljitiladi va ehtimoliy xatolikni topish jarayoni takrorlanadi (en-i *0). Bu jarayon har bir komponentlar uchun ketma-ket takrorlanadi, har bir komponent mavjud xatoliklarda tekshiriladi va agar xatolik topilsa u tuzatiladi.
Goley (23,12)-kodi uchun Meggit dekoderni tavsiflaymiz.
Xatolik vektori uzunligi 23 ga teng, vazni esa 3 dan oshmaydi. Sindrom registr uzunligi 11 ga teng. Agar xatolikning bunday konfiguratsiyasi tebranmasa, u barcha uch xatolik 11 kichik razryadlarda paydo bo‗lishi uchun siklik siljimaydi. Bunday holatda uch xatolik o‗rnidan biri bir tomonda turadi. Har bir tuzatiladigan xatolik konfiguratsiyasi siklik siljish yordamida quyidagi uch shakldan biriga keltirilishi mumkin:
Barcha xatoliklar 11 eski razryadda joylashgan;
Bir xatolik besh o‗rinni egallaydi, qolganlari 11 eski razryadda joylashadi;
Bir xatolik olti o‗rinni egallaydi, boshqalari 11 eski razryadda joylashadi. Shunday qilib dekoderda miqdorni oldindan hisoblash kerak:
S 5 (x) R
xnV va
S 6 (x) R
xnV
g ( x)
6( x)
Bunda xatolik agar vazn 3 dan oshmasa tebranadi. Dekoderda agar bu shartlar bajarilsa barcha uch xatolikni tuzatish mumkin, yoki kichik 11 bitda ikkita xatolik tuzatiladi.
x16 va x17 ni yasovchi g(x)=x11+x10+x6+x5+x4+x2+1 polinomlarga bo‗lib (ikkihad shaklida 01100110110), S5(x)=x9+x8+x6+x4+x2+x olamiz, S6(x)=x10+x9+x7+x6+x3+x2 (ikki had shaklida 00110011011). Agar xatolik besh yoki olti o‗rindan iborat bo‗lsa, sindrom mos ravishda (01100110110) yoki (00110011011) ga teng bo‗ladi. 11 katta razryadda ikkita qo‗shimcha xatoliklarning mavjudligi bu bitlardan ikkitasining mos o‗rinlarini qarama qarshisiga o‗zgartiradi.
Dekoder uchta pozitsiyadan ortiq bo‗lmagan nolli sindromdan farqlanuvchi sindromni ko‗rsatadi.
Misol. Kodli so‗z quyidagiga teng bo‗lsin:
C(x)=10101010101001100001011.
Belgilarning bir qismini uzatishda buzildi: V ( x) C( x) e( x) . Xatolik
ko‗phadi quyidagiga teng: e(x)=00100000001000000010. Bunda qabul qilinadigan so‗z: V(x)==lo8oi010100001100001o5l, bunda yo‗qolgan belgilar (*) bilan aks ettiriladi. Sindromni aniqlaymiz S(x)=10011000111.
Dekodlashtirishning ikkinchi bosqichini ko‗rib chiqamiz (bunda r6(x)=x'6mod g(x)=00110011011, r(x)=x mod g(x)=01100110110). Har bir bosqichda a,b,v,g - hisoblanadi. 17-bosqichda vazn W=2 va xatoliklarni tuzatish modul 2 bo‗ylab bufer qurilmasi yordamida amalga oshiriladi. Bu vaqtda yo‗qolgan ikkita belgi n razryadli bufer qurilmasida, uchinchi 6 razryadli buferda topiladi.
Navbatdagi sindromni hisoblash operatsiyasi quyidagi tarzda amalga oshiriladi: sindromning katta razryadlari tahlil qilinadi, agar u birga teng bo‗lsa g(x) yasovchi polinom asosida modul 2 bo‗yicha sindrom 1 razryad chapga suriladi va aksincha holatda sindromni faqat chapga surish amalga oshiriladi.
| 