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
|
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.:< 3. MENDELSON E. INTRODUCTION TO MATHEMATICAL LOGIC. FIFTH EDITION. - NY.: < AXBOROT RESURSLAR: 4.INTERNET ( www.wikipedia.com ) 5.”RADIOTEXNIK TIZIMLAR NAZARIYASI ASOSLARI” kitobi,(A.A.Xoliqov) Document Outline
Download 0.65 Mb. Do'stlaringiz bilan baham: 
|