Daraxtlarni Prufer usulida kodlash. Daraxtlarni ularning kodi bo‘yicha yasash


s1 \u003d 0; s2 \u003d 01; s3 \u003d 011; s4 \u003d 111


Download 0.65 Mb.
Pdf ko'rish
bet4/4
Sana06.11.2023
Hajmi0.65 Mb.
#1752225
1   2   3   4
Bog'liq
diskret1mi

s1 \u003d 0; s2 \u003d 01; s3 \u003d 011; s4 \u003d 111. 
Deylik, biz ketma-ketlikni oldik 011111...111 ... Xabar matnini dekodlashning 
yagona usuli bu bitlarni guruhning oxiridan 3 ga guruhlash va oldin nolga teng gu-
ruhlarni tanlash, so'ngra dekodlashingiz mumkin. Bunday kodni noyob tarzda dek-
odlash mumkin, ammo darhol emas! Kod hal qilish uchun uzatish tugaguncha kut-
ish kerak! Amalda ushbu yondashuv dekodlash tezligini inkor etadi (MakMillan 
teoremasi), shuning uchun darhol dekodlash usullarini izlash kerak. 
Xuddi shu belgini kodlashning ikkita usulini ko'rib chiqing, Si: 
s1 \u003d 0; s2 \u003d 10; s3 \u003d 110; s4 \u003d 1110, s5 \u003d 1111, 
Ushbu usul uchun dekodlash daraxti 10.III-rasmda keltirilgan. 
Ikkinchi yo'l 
s1 \u003d 00; s2 \u003d 01; s3 \u003d 100; s4 \u003d 110, s5 \u003d 111
Ushbu ketishning dekodlash daraxti 10.IV-rasmda ko'rsatilgan. 
Kod sifatini o'lchashning eng aniq usuli - bu xabarlar to'plamining o'rtacha uzun-
ligi. Buning uchun har bir belgining kod uzunligini mos keladigan pi ehtimoli bilan 
ko'paytirilishini hisoblashingiz kerak. Bu butun kodning uzunligini beradi. Q belgi-
lar alifbosi uchun o'rtacha L uzunlik kodining formulasi quyidagicha 
Bu erda pi - si belgisining paydo bo'lish ehtimoli, li - kodlangan belgining mos 
keladigan uzunligi. Samarali kod uchun L qiymati iloji boricha kichikroq bo'lishi 
kerak. Agar P1 \u003d 1/2, p2 \u003d 1/4, p3 \u003d 1/8, p4 \u003d 1/16 va p5 
\u003d 1/16 bo'lsa, unda # 1 kod uchun biz kod uzunligining qiymatini olamiz 
Va kod №2 uchun 


Olingan qiymatlar birinchi kodning afzalligini ko'rsatadi. 
Agar alfavitdagi barcha so'zlarning paydo bo'lish ehtimoli bir xil bo'lsa, unda 
ikkinchi kod afzalroq bo'ladi. Masalan, pi \u003d 1/5 bilan kodning uzunligi # 1 
Va kodning uzunligi
# 2 
Ushbu natija 2 ta kodning afzalligini ko'rsatadi. Shunday qilib, "yaxshi" kodni 
loyihalashda ramzlar ehtimolini hisobga olish kerak. 


Li belgi kodining chegara qiymatini belgilaydigan Kraft tengsizligini ko'rib 
chiqing. 2-asosda tengsizlik quyidagicha ifodalanadi 
Ushbu tengsizlik shuni ko'rsatadiki, alifboda juda ko'p qisqa belgilar bo'lishi 
mumkin emas, aks holda bu miqdor juda katta bo'ladi. 
Kraftning har qanday tezkor noyob dekodlash kodi uchun tengsizligini isbotlash 
uchun biz dekodlash daraxtini quramiz va matematik induksiya usulini qo'llaymiz. 
Agar daraxt 10.V rasmda ko'rsatilgandek bitta yoki ikkita bargga ega bo'lsa, unda 
shubhasiz tengsizlik haqiqatdir. Bundan tashqari, agar daraxtning ikkitadan ko'p 
barglari bo'lsa, unda biz uzun daraxt m ni ikkita kichik daraxtga ajratamiz. Induk-
siya printsipiga ko'ra, biz tengsizlikning balandligi m -1 yoki undan past bo'lgan 
har bir novda uchun to'g'ri deb hisoblaymiz. Induksiya printsipiga ko'ra, tengsiz-
likni har bir filialga qo'llash. K "va K" "novdalari kodlarining uzunligini belgi-
laylik. Daraxtning ikkita novdasi birlashtirilganda, ularning har biri uzunligi 1 ga 
ko'payadi, shuning uchun kodning uzunligi K '/ 2 va K' '/ 2 yig'indilaridan iborat, 
Teorema isbotlangan. 
Makmillan teoremasining isbotini ko'rib chiqing. Biz Kraftning tengsizligini 
soddalashtirilgan dekodlash kodlariga qo'llaymiz. Buning isboti har qanday 
K\u003e 1 son uchun raqamning n-chi kuchi n ning chiziqli funktsiyasidan 
kattaroq ekanligiga asoslanadi, bu erda n juda katta son. Biz Kraft tengsizligini n-
darajaga ko'taramiz va ifodani yig'indisi sifatida ifodalaymiz 


Bu erda Nk - k uzunlikdagi belgilar soni, yig'indisi n-sonli belgining minimal 
uzunligidan boshlanadi va maksimal nl uzunligi bilan tugaydi. 
Daraxtni kodlash. 
#include  
using namespace std; 
// Prints edges of tree represented by give Prufer code 
void printTreeEdges(int prufer[], int m) 

int vertices = m + 2; 
int vertex_set[vertices]; 
// Initialize the array of vertices 
for (int i = 0; i < vertices; i++) 
vertex_set[i] = 0; 
// Number of occurrences of vertex in code 
for (int i = 0; i < vertices - 2; i++) 
vertex_set[prufer[i] - 1] += 1; 
cout << "\nThe edge set E(G) is :\n"; 
// Find the smallest label not present in 
// prufer[]. 


int j = 0; 
for (int i = 0; i < vertices - 2; i++) { 
for (j = 0; j < vertices; j++) { 
// If j+1 is not present in prufer set 
if (vertex_set[j] == 0) { 
// Remove from Prufer set and print 
// pair. 
vertex_set[j] = -1; 
cout << "(" << (j + 1) << ", " 
<< prufer[i] << ") "; 
vertex_set[prufer[i] - 1]--; 
break; 



j = 0; 
// For the last element 
for (int i = 0; i < vertices; i++) { 
if (vertex_set[i] == 0 && j == 0) { 
cout << "(" << (i + 1) << ", "; 
j++; 

else if (vertex_set[i] == 0 && j == 1) 
cout << (i + 1) << ")\n"; 




// Driver code 
int main() 

int prufer[] = { 4, 1, 3, 4 }; 
int n = sizeof(prufer) / sizeof(prufer[0]); 
printTreeEdges(prufer, n); 
return 0; 

#include  
using namespace std; 
// Prints edges of tree represented by give Prufer code 
void printTreeEdges(int prufer[], int m) 

int vertices = m + 2; 
int vertex_set[vertices]; 
// Initialize the array of vertices 
for (int i = 0; i < vertices; i++) 
vertex_set[i] = 0; 
// Number of occurrences of vertex in code 
for (int i = 0; i < vertices - 2; i++) 
vertex_set[prufer[i] - 1] += 1; 


cout << "\nThe edge set E(G) is :\n"; 
// Find the smallest label not present in 
// prufer[]. 
int j = 0; 
for (int i = 0; i < vertices - 2; i++) { 
for (j = 0; j < vertices; j++) { 
// If j+1 is not present in prufer set 
if (vertex_set[j] == 0) { 
// Remove from Prufer set and print 
// pair. 
vertex_set[j] = -1; 
cout << "(" << (j + 1) << ", " 
<< prufer[i] << ") "; 
vertex_set[prufer[i] - 1]--; 
break; 



j = 0; 
// For the last element 
for (int i = 0; i < vertices; i++) { 
if (vertex_set[i] == 0 && j == 0) { 


cout << "(" << (i + 1) << ", "; 
j++; 

else if (vertex_set[i] == 0 && j == 1) 
cout << (i + 1) << ")\n"; 


// Driver code 
int main() 

int prufer[] = { 4, 1, 3, 4 }; 
int n = sizeof(prufer) / sizeof(prufer[0]); 
printTreeEdges(prufer, n); 
return 0; 

FOYDALANILGAN ADABIYOTLARDAN: 
1.MATEMATIK MANTIQ VA DISKRET MATEMATIKA (H.T.TO’RARYEV,I.AZIZOV) 
2.YUNUSOV A.S. MATEMATIK MANTIQ VA ALGARITIMLAR NAZARIYASI 
ELEMENTLARI. -T.:<>, 2006 


3. MENDELSON E. INTRODUCTION TO MATHEMATICAL LOGIC. FIFTH EDITION. -
NY.: <>, 2010 
AXBOROT RESURSLAR: 
4.INTERNET (
www.wikipedia.com

5.”RADIOTEXNIK TIZIMLAR NAZARIYASI ASOSLARI” kitobi,(A.A.Xoliqov) 

Document Outline

  • Daraxtni tiklash
  • Xususiyatlar

Download 0.65 Mb.

Do'stlaringiz bilan baham:
1   2   3   4




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling