Mavzu: daraxtlarni prufer usulida kodlash

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)