8
|
10
|
|
A
|
3
|
4
|
4
|
5
|
5
|
6
|
|
|
E
|
3
|
3
|
4
|
4
|
5
|
|
|
|
C
|
2
|
3
|
3
|
4
|
|
|
|
|
F
|
2
|
2
|
3
|
|
|
|
|
|
G
|
2
|
2
|
|
|
|
|
|
|
H
|
2
|
|
|
|
|
|
|
|
1.2-rasm. Xaffman algoritmining daraxtsimon ko‘rinishi
1.3-jadval
Xaffman algoritmida har bir belgini paydo bo‘lish chastotasi
Belgilar
|
B
|
D
|
A
|
E
|
C
|
F
|
G
|
H
|
Kodi
|
01
|
00
|
100
|
101
|
1101
|
1100
|
1111
|
1110
|
№ 2 LABORATORIYA ISHI
XEMMING KODINI KODLASH VA DEKODLASH
QISQACHA NAZARIY MA’LUMOT
Xemming kodlari birinchi o‘z-o‘zini tekshirish va o‘z-o‘zini to‘g‘rilash kodlarining eng mashhurlaridan biridir. 20-asr o‘rtalarida Richard Xemming asarlarida paydo bo‘lgan. Xemming kodi bir marotaba xatolarni to‘g‘irlash uchun yaratilgan bo‘lib, u dmin=3 kod masofasiga ega. Xemming kodlarining tuzilish qoidasi (2.1-jadval) har bir r ≥ 2 butun soni uchun blok uzunligi va foydali axborot uzunligi bo‘lgan kod mavjud.
.
Masalan, (7, 4), (15, 11), (31, 26) va boshqalar
2.1-jadval
Xemming kodining tuzilish parametrlari
Tekshiruvchi razryad soni (r)
|
Umumiy bit uzunligi (n)
|
Foydali bit uzunligi (k)
|
Kod turi
|
3
|
7
|
4
|
Xemming (7,4)
|
4
|
15
|
11
|
Xemming (15,11)
|
5
|
31
|
26
|
Xemming (31,26)
|
Xemming kodlash usulida tekshiruv belgilari ikkining darajasi (1, 2, 4, 8 va boshqalar) bo‘yicha kodli kombinatsiyalardan tashkil topadi.
N = (26)10 = (11010)2 ko‘rinishidagi ma’lumot uzunligi k=5 bitdan iborat va bu xabarni Xemming kodlash usulida kodlashtiramiz.
Ushbu axborotni kodlash uchun tekshirish elementlar soni (r) hisoblanadi. Tekshirish element soni quyidagi formula orqali topiladi. yoki
4 ta tekshiruvchi elementdan tashkil topgan:
Tekshirish elementlarini 2 ni darajasi bo‘yicha axborotga joylashtiramiz (1,2,4,8......).
Tekshiruv elementlarini qiymatini aniqlash uchun 2.2-jadval va 2.3-jadvallarda keltirilgan ketma-ketlikda tanlab olinadi va ikkilik moduli bo‘yicha hisoblanadi. Hisoblash natijasi har doim 0 (yoki birlar soni juft) bo‘lishi shart.
2.2-jadval
Tekshiruv elementlarini aniqlash jadvali
Tekshiruv element №
|
Tekshiruv elementlari
|
1
|
1,3,5,7,9..........................................................
|
2
|
2,3,6,7,10,11,14,15,18,19................................
|
3
|
4,5,6,7,12,13,14,15,20,21,22,23,28,29,30,31....
|
4
|
8,9,10,11,12,13,14,15,24,25,26,27,28,29,30,31,40,41,42,43,44,45,46
|
2.3-jadval
T ekshiruv elementlarini aniqlash jadvali
Birinchi tekshiruv elementini hisoblash quyidagicha aniqlanadi:
bo‘lsa, shart bajariladi.
Ikkinchi tekshiruv elementini hisoblash quyidagicha aniqlanadi:
bo‘lsa, shart bajariladi
Uchinchi tekshiruv elementini hisoblash quyidagicha aniqlanadi:
bo‘lsa, shart bajariladi
To‘rtinchi tekshiruv elementini hisoblash quyidagicha aniqlanadi:
bo‘lsa, shart bajariladi
11010 xabari Xemming kodi asosida kodlashtirilgandan keyin quyidagi ko‘rinishga ega bo‘ladi:
Agar uzatilgan axborotga shovqin ta’sir qilib, undagi bitlar ketma-ketligida o‘zgarish bo‘lsa, u holda axborot xato qabul qilinadi. Xatoni aniqlash uchun quyidagi misolni ko‘rib chiqamiz. Masalan: quyidagi ketma-ketlikda axborot kelib tushgan bo‘lsin:
Xemming kodi asosida xatoni topish jarayoni quyidagicha aniqlanadi:
Qabul qilingan axborotni 1 0 1 1 1 0 1 0 0 6.2-jadvalda keltirilgan ketma-ketlik bo‘yicha tekshiruv amalga oshiriladi.
Birinchi tekshiruv
|
|
Ikkinchi tekshiruv
|
|
Uchinchi tekshiruv
|
|
To‘rtinchi tekshiruv
|
|
Olingan qiymatlarni pastdan tepaga yozib olinadi (0100) va o‘nlik sanoq sistemasiga aylantiriladi (01002 =410). Natija axborotda qaysi bitda xato borligining o‘rnini ko‘rsatadi. Shu asnoda xato to‘g‘irlanadi.
№ 3 LABORATORIYA ISHI
BCHX KODLARINI KODLASH VA DEKODLASH
QISQACHA NAZARIY MA’LUMOT
Qulay kodlash va dekodlash algoritmlari taklif etilgan notasodifiy kodlarning orasidagi eng mashxurlaridan biri BCHX kodlaridir (Bouza-Choudxuri-Xekvingem). BCHX 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 d0 ≥ 5 bilan aniqlanadi. BCHX kodi uzunligi n=2m-1 ifodasi orqali aniqlanadi.
bu yerda: m – istalgan butun son, m=log2(n + 1).
Tekshiriladigan razryadlar soni quyidagicha aniqlanadi:
(3.1)
BCHX kodning hosil qilinadigan polinomi minimal polinomlarning eng kichik umumiy karralisi hisoblanib qaysiki tartibi d0 –2 ga teng.
P(x) = EKUK {m1(x) * m3(x) * m5(x) *… * md0-2(x) } (3.2)
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‘phadi.
BCHX kodni kodlash quyidagidan iborat:
Zarur (x)=0…k-1 kod kombinatsiyasini xn-k razryadga chapga siljitib shu sonni olamiz
X n-k (x)=X n-k (0 +…+ k-1X k-1)= 0 X n-1 +… k-1X n-1 (3.3)
Xn-k (x) ko‘phadini g(x)ga bo‘lamiz va bo‘linmani quyidagi ko‘rinishda yozamiz:
Xn-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‘phadining darajasi n-k ga teng ekan , r(x) ning darajasi n-k-1 ga teng bo‘ladi.
Bunda Xn-k(x) + r (x) = g(x) q(x), bu yerdan bo‘linadigan BCHX kodning izlangan kodli kombinatsiyasini olamiz .
|
