Муҳаммад ал-хоразмий номидаги тошкент ахборот технологиялари университети “маълумотлар узатиш тармоқлари ва тизимлари” кафедраси

мисол: Қуйидаги кўринишда ахборот берилган:

• мисол: Қуйидаги кўринишда ахборот берилган:
• BBCBBBCDDEDAAADDFFGGHHEE.
• Ушбу ахборотда умумий белгилар сони 24 та. Дастлаб ушбу ахборот учун энтропия кўрсаткичининг қийматини ҳисоблаймиз.
• Н(х) = ∑ Р(х) * Log 2 Р(х) = 2,89 бит га тенг бўлади.
• Ушбу алгоритм бўйича ҳисоблаш натижалари жадвалда келтирилган.
• Шеннон- Фано алгоритми бўйича ҳисоблаш натижалари.

Белгилар	Пайдо бўлиш частотаси	Ёрдамчи жадвал				Коди
B	5	5 (1) 5 (1) 3 (1)	5 (1)			11
D	5		5 (0) 3 (0)	5 (1)		101
A	3			3 (0)		100
E	3	3 (0) 2 (0) 2 (0) 2 (0) 2 (0)	3 (1)	3 (1)		011
C	2		2 (1)	2 (0)		010
F	2		2 (0) 2 (0) 2 (0)	2 (1)		001
				2 (0) 2 (0)	2 (1)	0001
G	2				2 (0)	0000
H	2

Кодлаштирилган ахборотдаги хар бир белгига мос келган кодли комбинациянинг ўртача узунлиги қуйидагича ҳисобланади:

• Кодлаштирилган ахборотдаги хар бир белгига мос келган кодли комбинациянинг ўртача узунлиги қуйидагича ҳисобланади:
• n ўрт = ∑ n i * Р(х) = 2,96 битга тенг.
• Ҳозирги кунда энг кенг тарқалган, амалиётда кўп ишлатиладиган энтропияли кодлаш усулига асосланган алгоритмлардан бири бу – Хаффман алгоритми ҳисобланади.
• Хаффман алгоритми асосида матнли ахборотлар кодлаштирилади.

• Дэвид Хаффман 1925 йил 9 августда АҚШнинг Огайо штатида туғилган. 1999 йил 7 октябрда АҚШнинг Калифорния штатида вафот этган.
• Дэвид Хаффман - ахборот назарияси муҳити бўйича иш олиб борган. У 1952 йил кам ортиқчалик билан префиксларни кодлаш алгоритмини яратган. 1999 йил ахборот назариясига қўшган ҳиссаси учун Ричард Хэмминг медалини олган.

• Дэвид Хаффман
• 1925 - 1999

Ушбу алгоритм ёрдамида ахборотни кодлаштириш қуйидагича амалга оширилади:

• Ушбу алгоритм ёрдамида ахборотни кодлаштириш қуйидагича амалга оширилади:
• ахборотдаги барча белгилар сони, яъни N ҳисобланади;
• жами N та белгидан иборат бўлган ахборотдаги ҳар бир белгининг пайдо бўлиш частотаси ҳисобланади;
• ҳар бир белгининг пайдо бўлиш частотаси камайиб бориш тартибида жадвалга жойлаштирилади;
• жадвалдаги охирги иккита частота йиғиндиси ҳисобланиб, битта умумий бўлган йиғинди частотага бирлаштирилади;
• ҳисобланган янги йиғинди частотадан ва ҳисоблашда қатнашмаган бошқа частоталардан жадвалнинг янги устуни ҳосил қилинади (бунда ҳам частоталар камайиб бориш тартибида жойлаштирилади);
• шу тарзда то битта умумий N га тенг бўлган йиғинди ҳосил бўлгунча жараён давом этаверади;
• жадвал тўлдирилгандан сўнг, ундаги ҳисоблашларга мувофиқ дарахт қурилади;
• дарахтнинг тепа қисмида N жойлашган бўлади ва уни тенг иккига бўлиш керак, ҳосил бўлган натижаларни яна тенг иккига бўлиш лозим;
• шу тарзда ахборотдаги ҳар бир белгининг пайдо бўлиш частотаси топилгунча, бўлиш давом эттирилади.

Белги-лар	Пайдо бўлиш частотаси	Ёрдамчи жадвал
B	5	5	5	6	8	10	14	24
D	5	5	5	5	6	8	10
A	3	4	4	5	5	6
E	3	3	4	4	5
C	2	3	3	4
F	2	2	3
G	2	2
H	2

• мисол: Қуйидаги кўринишда ахборот берилган: BBCBBBCDDEDAAADDFFGGHHEE.
• Хаффман алгоритми бўйича ҳисоблаш натижалари жадвалда келтирилган.

Белгилар	B	D	A	E	C	F	G	H
коди	01	00	100	101	1101	1100	1111	1110

Кодлаштирилган ахборотдаги хар бир белгига мос келган кодли комбинациянинг ўртача узунлигини ҳисоблаймиз:

• Кодлаштирилган ахборотдаги хар бир белгига мос келган кодли комбинациянинг ўртача узунлигини ҳисоблаймиз:
• n ўрт = ∑ n i * Р(х) = 2,92 битга тенг.
• Юқоридаги кўриб чиқилган 1 ва 2-мисолларда кодлаштирилаётган ахборот қўйидагича, яъни BBCBBBCDDEDAAADDFFGGHHEE.
• Бироқ, ҳисоблаш натижаларига кўра, кодлаштирилган ахборотдаги хар бир белгига мос келган кодли комбинациянинг ўртача узунлиги Шеннон - Фано усули учун n ўрт =2,96 битга,
• Хаффмен усули учун эса n ўрт =2,92 битга тенг чиқди.
• Бундан хулоса қилинадики, юқоридаги ахборотни Хаффен усули билан кодлаштирилса мақсадга мувофиқ бўлади, чунки ушбу алгоритм билан ахборотни кодлаштирилганда ахборотдаги хар бир белгига мос келувчи кодли комбинациянинг ўртача узунлиги кичкина, яъни ахборотни узатиш учун кам бит сарфланади.
• Бу эса ўз навбатида ахборотни узатиш тезлигини оширишга олиб келади.

• Хаффман коди асосан факсимил тизимларда ишлатилади. Хаффман кодларининг шартлари қуйидагилардан иборат:
• энг кўп учрайдиган символларни биринчи узатиш;
• символлар эхтимоллигини аниқлаш;
• эхтимоллигига қараб жойлаштириш (катта кичиклигига қараб);
• энтропия хисобланади;
• энтропия хисоблангандан кейин дарахт холига келтирилади ва кодлаштирилади.

• Мисол: Қуйидаги кўринишда ахборот берилган бўлсин

Символ	А	Б	В	Г	Д
Частота	15	7	6	6	5

• Бу мисолни ечиш учун дарахтсимон усулни қуришдан фойдаланамиз:

• Бу берилган усул учун Хаффман коди жадвали қуйидаги кўринишда бўлади

Символ	А	Б	В	Г	Д
Код	0	100	101	110	111

Символлари пайдо бўлишининг эҳтимоли бир хил бўлган маълумотларни самарали кодлаш

• Символлари пайдо бўлишининг эҳтимоли бир хил бўлган маълумотларни самарали кодлаш
• Самарали кодлаш шовқинсиз алоқа каналларида қўлланилади. Бунда каналларда асосий масала – максимал ахборот узатиш тезлигини таъминлаш, яъни ахборот узатиш тезлигини алоқа каналининг маълумот узатиш имконига етказиш ҳисобланади.
• Агар Н(х) – бирламчи маълумотнинг энтропияси бўлса, ҳамда (xi) маълумот символларини пайдо бўлиш эҳтимоллиги бир хил ва маълумот манбаи алфавитининг ҳажми m бўлса, (xi) маълумотини ҳоҳлаган i символининг пайдо бўлиш эҳтимоллиги P(xi) бир хил қийматга эга бўлади, яъни:

• i=1,.., m,

Маълумотнинг энтропияси (Н(х)):

• Маълумотнинг энтропияси (Н(х)):

• га тенг бўлади.
• Агар кодлаш учун k асосли рақамли коддан фойдаланилган бўлса (код символлари элементлари алфавитининг ҳажми k га тенг) ва бунда код символлари элементларининг энтропияси (Н1), символ элементларининг пайдо бўлиш эҳтимоллиги бир хил ва улар ўзаро мустақил бўлиш шарти бажарилганида қуйидаги формула орқали ҳисобланади:
• H1 = log2k .
• Бунда самарали код символи элементларининг узунлиги (lэфф.) қуйидаги формула ёрдамида ҳисобланиши мумкин:

• Бунда m = k n.

Шовқинсиз алоқа каналлари орқали узатиладиган маълумотларни самарали кодлаштириш Шеннон теоремасига асосланади:

• Шовқинсиз алоқа каналлари орқали узатиладиган маълумотларни самарали кодлаштириш Шеннон теоремасига асосланади:
• Агар маълумот манбаининг энтропияси Н [бит/символ] га ва алоқа каналининг узатиш қобилияти С [бит/сек] га (алоқа каналининг узатиш қобилияти деганда, унинг энг максимал маълумот узатиш тезлигини таъминлаши тушунилади) тенг бўлса, ҳар доим шундай кодлаш усулини топиш мумкинки, каналда маълумот узатиш тезлигининг ўртача қиймати ушбу формула негизида ҳисобланган тезликга тенг бўлади:

• [символ/сек],

• С- алоқа каналининг узатиш қобилияти.

• Н- маълумот манбанинг энтропияси;

Самарали кодлаш алгоритмларининг камчиликлари

• Самарали кодлаш алгоритмларининг камчиликлари
• ташқи шовқинларга таъсирчанлиги – шовқин таъсирида битта элементда содир бўлган хато бир код комбинациясини вақт бирлиги бўйича бошқа қийматга эга иккинчисига ўтиб кетишига сабаб бўлиши мумкин;
• бир код символи бошқа вақт бирлигидаги символга айланиши мумкин, бунинг оқибатида жорий ва кейинги символлар нотўғри декодланади ва бирламчи маълумот бошқа маълумотга ўзгариб кетади;
• кейинги камчилик бу техникавий жиҳатдан уларни яратиш мураккаблиги ҳисобланади: қурилма буфер ва символларни йиғиш ускуналарига эга бўлиши керак. Чунки алоқа каналлари бир хил узунликдаги код комбинацияларини узатишда самарали ишлайди, юқоридаги алгоритмлардаги код комбинацияларининг узунлиги ҳар хил, уларни йиғиб бир тугалланган маълумот шаклига келтириш учун олдин қабул қилинган символларни сақлаш керак бўлади.