Diskret tuzulmalari fanidan tayyorlagan

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)