|
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)
Do'stlaringiz bilan baham: |
