Теорема. Дереккөздерді кодтау теоремасы I.

Кез-келген негізгі алфавитті және Н(х) энтропиялы жадсыз дискретті Х дереккөзi үшін n кодты сөзінің орташа ұзындығы теңсіздікті қанағаттандыратын D-типті префиксті код бар

Префиксті код термині кодты сөздің ешқандай бастамасы басқа кодты сөз бола алмайды дегенді білдіреді. Бұл дегеніміз оқиғалар ағыны бұл жағдайлардың арнайы бөлінуінсіз де кодталуы мүмкін екенін айқындайды. D = 2 болған жағдайда екілік код қолданылады. Егер энтропия биттерде берілген болса n-ның орташа ұзындығы да екілік кодты қолдану арқылы биттерде өрнектелген болады.

Дереккөздерді кодтау теоремасы кодты сөздің орташа ұзындығы энтропиядан кіші болуы мүмкін емес екенін көрсетеді. Бірақ, 5.2 және 5.5 тарауларда көрсетілгендей, дереккөздерді блокты кодтау уақтысында кодты сөздің орташа ұзындығы энтропияға жақындауы мүмкін. Бұл жайт энтропия түсінігінің маңыздылығын тағы да ескере кетеді. Энтропия – бұл минималды орташа шығындардың өлшемі. Теңсіздіктің (3.1) практикалық түрде жүзеге асу мысалы ретінде келесі тарауларды қаралатын Хаффман кодын алуға болады.

 

 

Ескерту. 3.1.1 теоремасының дәлелі Крафт теңсіздігінің қолданылуына алып келеді және шығын тұрғысынан алғанда оптималды кодтар құруға өзімен ешқандай да негізді түсінік ұсынбайды. Дәлелдер дерліктей ауқымды, бірақ ақпараттар теориясының әдістері жайлы жақсы мәлімет береді. Сонымен қатар, келесі бөлімдерді түсіну үшін ол еш зақымсыз өткізілуі мүмкін.

Дәлел.

Қадам 1. Крафт теңсіздігі.

n₁, n₂, …, n_k ұзындықты К кодты сөзі бар бір мәнді декодталатын D-типті кодтың бар болуы үшін, Крафт теңсіздігінің орындалуы зәру және жеткілікті

Бұл анықтаманы дәлелдеу үшін 3.2 суретте көрсетілген кодты құрылымды қолданамыз

3.2. Сурет. D = 2 және n = 4 үшін кодты дарақ.

Біз бұл құрылымның 3 өзіндік қасиетін байқаймыз:

1. i тәртіптің (і дәрежелі) Dⁱ түйіні бар;

2. i тәртіптің әр түйіні n дәреженің D^n-1 туғызады;

3. Кодтық құрылым префикстік кодқа сәйкес, яғни ешбір кодты сөз басқа кодты сөздің бастамасы бола алмайды, себебі кодты сөздер біріңғай біткен түйіндермен анықталады.

 

 

Жеңілдету үшін кодты сөздердің ұзындығын тізіп шығамыз

Енді есеп беруді бастаймыз. n₁ ұзындығының с₁ кодты сөзі соңғы n деңгейде нақты D^n-n₁ мүмкін біткен түйінді болдырмайды. Себебі префиксті кодтың кодты сөздері бірікпейді, сонда n деңгейде

жүзеге аспаған түйін аламыз. N деңгейдегі мүмкін түйіндердің жалпы саны Dⁿ -ге тең, сондықтан

Теңсіздіктің екі бөлігін де Dⁿ- ға бөлсек, Крафт теңсіздігін аламыз.

Қадам 2. Мак-Миллан тұжырымы.

Әр біріңғай декодталатын код Крафт теңсіздігін қанағаттандырады.

Крафт теңсіздігін қорытындылау нәтижесінде префикстік кодтың ерекшеліктері қолданылған болатын. Бірақ бұл шарт міндетті болып есептелмейді. Келесі көрсетілетіндей, кодтың біріңғай декодталуы қажетті шарт болып табылады. Крафт теңсіздігіндегі қосындыны L дәрежеге шығарамыз

Жалпы i ұзындықты L кодты сөзі бар комбинациялар санын А_і арқылы көрсетіп, (3.6)-ны жинақы түрде жазамыз

мұндағы L _{n, max} L кодты сөзді хабарламаның максималды ұзындығы.

Егер код біріңғай декодталатын болса, онда жалпы і ұзындықты L кодты сөзден шығатын реттіліктер өзгеше. Себебі Dⁱ ғана мүмкін реттіліктер бар болғандықтан

 

және осылайша

L-типті негізді шығара отырып, Крафт теңсіздігіндегі дәреже өзгерісін

барлық натурал L-дер үшін аламыз.

L санының мәнін талқылауға көшейік. Бұл {1, 2, …, K}-дан алынатын және L_{n, max} -тан аспайтын ұзындықтың барлық мүмкін реттіліктерін құру үшін қолданылатын тәуелсіз кодты сөздердің саны. Сондықтан, L → ∞ болған жағдайда біз Крафт теңсіздігіне келеміз

Жоғарыда келтірілген тұжырымдар әрбір біріңғай декодталатын код үшін әділ болып табылады. Сол себепті, әрбір біріңғай декодталатын код Крафт теңсіздігін қанағаттандырады.

Адам 3.

Теңсіздіктің (3.1) сол жақ бөлігін келесі түрде жазамыз

P_k оқиғасының ықтималдығын және n_k кодты сөздерінің сәйкес ұзындықтарын пайдаланамыз

 

 

Тоқтамды(2.1) дәлелдегендегідей, (2.19) көмегімен логарифмдік функцияны төбесінен бағалайық

Бұл жерде Крафт теңсіздігі және шарты қолданылған болатын.

Осылайша дереккөздерді кодтау теоремасының сол жақ бөлігі дәлелденді.

Адам 4.

Теңсіздіктің (3.1) сол жақ бөлігі

Дәлелдеу барысында Крафт теңсіздігінің n_k кодты сөздерінің және шартының сәйкес ұзындықтарымен болу шартын қолданамыз.

Крафт теңсіздігін келесі түрде жазсақ болады

Крафт теңсіздігі күшін жоймай тұрғанда, біз n_k ∈ N кодты сөздерінің ұзындығын таңдау еркіндеміз. Әр өрнекке келесі нәтиже шығатындай ең аз n_k таңдаймыз

Мұндай таңдауда Крафт теңсіздігі орындалатын болады, демек, 3.2 суреттегі құрылымды қолданып біз мұндай префиксті код құра аламыз. n_k (3.17) орынды болатын ең аз бүтін болғандықтан, n_k – 1 үшін келесі теңсіздік әділетті

Дәлелдің қалған бөлігі негізсіз.

 

Логарифмдік функцияның қасиеттерін пайдаланып, алатынымыз

Барлық K-ларға қосқанда

Теңсіздіктің екі жағын да log D- ға бөліп және мүшелерді -1 көбейтіп (нәтижесінде теңсіздік белгісін өзгертеді) қайта орындарына қойсақ, ізделіп отырған дәлелді аламыз.

Хаффман кодтары

Хаффман¹ кодтары айнымалы ұзындықты кодты сөзді кодтар тобына жатады. Ең әйгілі айнымалы ұзындықты код – Морзе² әліпбесі (3.2 кесте). Морзе әліпбесінің негізгі мақсаты – жиі кезесетін әріптерді қысқа ұзындықты кодты сөздермен тасымалдау және, керісінше, сирек кездесетін әріптерді ұзын кодты сөздермен орташа шығынды азайту үшін тасымалдау. Кодтаудың мұндай тәсілін сондай-ақ минималды шығынмен кодтау немесе энтропиялық кодтау деп атайды.

Мысалы, Морзе әліпбесінде жиі кездесетін “Е” әріпі бір «∙» белгісімен, ал сирек “Х” төрт «- ∙ ∙ -» белгісімен кодталады.

1952 жылы Хаффман ұсынған айнымалы ұзындықты кодты сөздермен кодтау әдісі жадсыз дискретті дереккөздер үшін ең қолайлы префиксті код болып табылатынын көрсетті. Яғни Хаффман коды сөзінің орташа ұзындығы минималды және де ол үтірсіз код болып табылады. «Үтірсіз код» термині синхрондау орнатылғанда кодты сөздердің арнайы бөлінуінсіз мәндес декодты үзіліссіз хабарламалар тасымалы мүмкін екендігін білдіреді.

Префикстік кодта ешқандай кодты сөз басқа сөздің префиксі бола алмайды.

 

 

________________________________

¹ Дэвид Хаффман (1925 - 1999) – америкалық ғалым.

² Самуэль Морзэ (1791 - 1872) – америкалық суретші және шебер.

 

3.1 Кесте. Морзе әліпбесінің әріптері, символдары және олардың

неміс әдебиетіндегі салыстырмалы жиіліктері

Ескерту. Хаффман кодтары кескіндерді кодтау барысында маңызды рөл атқарады. Олар JPEG, MPEG және H.261 стандарттарының негізгі бөлігі болып табылады. Сонымен қатар олар аудио сигналдарды цифрлеуде қолданылады. Әдебиеттерде энтропиялық кодтау мысалы ретінде Шеннон және Фано кодтарын атап өтеді, бірақ олар барлық жағдайларда да қолайлы болып табылмайды, сондықтан біз оның сипаттамасын өткізіп жібереміз.

Хаффман кодтауы үш қадам арқылы жүзеге асады. Біз бұл процессті шағын мысалда айқындаймыз.

Хаффман кодтауы.

1. Тәртіптеу. Белгілерді олардың ықтималдықтарының азаю тәртібі-мен орналастыру.

2. Редукция. Екі ықтималдықтары ең аз белгілерді бір құрама таңбаға біріктіру. Таңбалар тізімін 1-ші қадамға сәйкес қайта тәртіпке келтіру. Бұл процессті барлық таңбалар бірікпегенше жалғастыру.

3.2 Кесте. Екі таңбаның ықтималдықтары және энтропиясы.

3. Кодтау. Соңғы бірікпеден бастау. Құрама таңбаның біріші компоненті-не «0» символын, ал екіншісіне «1» символын енгізу. Бұл процессті барлық жәй таңбалар кодталмағанша жалғастыру.

Бірнеше таңбалар біркелкі ықтималдыққа ие болған жағдайда бұл уақытқа дейін ең аз біріккен екі таңба қосылады. Бұл әрекетпен ақпарат тасымалдауды жеңілдететін кодты сөздердің ұзындықтарын туралау жүзеге асады.

3.3 Сурет. Хаффман кодтауы n=4.

Мысал:

Хаффман кодтауы 3.2 кестеде берілген дереккөз мысалында айқын көрсетілген. Сондай-ақ, біз екінші қадамдағы айқын қайта тәртіптеуден бас тартып кодтауды азғана жеңілдетеміз, себебі мұндай шағын мысалда мұны «ойша» істеуге болады. Бірінші қадамға сәйкес, барлық таңбаларды олардың ықтималдықтарының азаю тәртібі бойынша орналастырамыз (3.3 сурет).

 

3.3 Кесте. 3.3 суретке Хаффман кодтау тәсілімен кодтау.

Екінші қадамда ең аз ықтималдықтарға ие «а» және «с» символдарын «ас» құрама символына біріктіреміз. Онан соң «е» және «ас» символдарын 0.25 ықтималдықпен «еас» құрама символына біріктіреміз. Енді ең аз ықтималдықтарға ие символдар «f» және «b». Келесі редукция 0,6 ықтималдықпен «fbeac» құрама сиволын береді. Және, соңында, барлық символдарды біріктіріп ықтималдығы 1-ге тең «dfbeac» құрама символын аламыз.

Үшінші қадамда оңнан солға қарай жүретін боламыз, бірлеспелердің жоғарғы компоненттеріне «0», ал төменгі компоненттеріне «1» символдарын енгіземіз. Барлық жәй таңбалардың кодты сөздері ұзындықтарымен 3.3 кестеде көрсетілген.

Бұл код кодты сөздің минималды орташа ұзындығына ие.

Кодты сөздің орташа ұзындығы сәйкес p_i ықтималдықтарымен«өлшенген», барлық n_i сөздердің ұзындығымен анықталады

Жоғарыда қаралған мысалда кодты сөзінің орташа ұзындығы энтропиясына жақын. Код нәтижелілігі немесе қысу факторы деп аталатын маңызды өлшем орташа ұзындықтың энтропияға қатынасы болып табылады. Біздің мысалда код нәтижелілігі -ға тең.

Код нәтижелілігі немесе қысу факторы

Символдардың ықтималдықтарының айырмашылығы қаншалықты көп болса, қарапайым блокты кодтаумен салыстырғандағы Хаффман кодының ұтысы соншалықты көп болатыны мысалдан айқын көрініп тұр.

Шеннонның дереккөздерді кодтау турасындағы теоремасы мұндай кодтау қаншалықты нәтижелі болатынын көрсетеді. Бірақ сонымен қатар ақпараттар теориясы кодтау уақтысында ұзындығы өте үлкен кодты сөздер пайда болатын жағдайға да меңзейді. Бұл жағдай дереккөздерді кодтау теоремасын практикалық түрде қолдануға кедергі келтіруі мүмкін.

Хаффман кодының декодерін жүзеге асыру тікелей 3.3 суретке апарады. 3.4 суретте декодердың кодты дарағы бейнеленген.

Әрбір жаңа сөзді декодтау кодты дарақтың әуелгі түйінінен (тамыры-нан) басталады. Егер біз «0»-ді қабылдасақ, онда нөлге сәйкес қабырғамен жүреміз(жоғарғы қабырғамен). Біздің мысалда біз сонымен қатар d біткен түйініне де жетеміз. Демек, d символы тасымалданған және біз жаңа символды декодтауды негізінен бастаймыз.

3.4 Сурет. D = 2 және n = 4 үшін кодты құрылым.

Егер біз «1»-ді қабылдасақ, онда төменгі қабырғамен жүреміз және екі қабырға шығатын түйінге кезігеміз. Келесі қабылданған бит бұл екі қабырғаның қайсысын таңдау керек екенін көрсетеді. Біз бұр рәсімді біткен түйінге жетпегенше жалғастырамыз. Бұл жағдайда біз тасымалданған символ турасында шешім қабылдаймыз және кодты дарақтың негізіне қайта ораламыз.

 

Декодтаудың және құрудың тым қарапайымдылығына қарамастан, Хаффман кодтарының үш кемістігі бар:

● Кодты сөздердің түрлі ұзындықтары декодтауды әркелкі тоқтауларға алып келеді.

● Мағлұматтарды қысу шығынды төмендетеді және сондықтан қателердің таралу мүмкіндігін жоғарылатады. Хаффман кодтауы жағдайында, бір қате орналасқан бит, келесі символдардың баршасының дұрыс декодталмауына әкелуі мүмкін.

● Хаффман кодтауы оқиғалар (таңбалар) ықтималдығын болжайды немесе бұл ықтималдықтардың дұрыс бағалауды жүзеге асырады. Практикада көп жағдайларда оқиғалар ықтималдығы беймағлұм, ал олардың бағалаулары өте қиындатылған.

Сол себепті деректердің үлкен ауқымын қысу үшін Лемпель-Зива алгоритмі деп танылған кодтаудың универсалды алгоритмін жиі қолданады. Бұл алгоритмнің сипаттамасы 6.3 бөлімде көрсетілген. Кодтаудың универсалды алгоритмі деректердің статистикасын негізсіз білуді талап етпейді.

 

 

БӨЛІМ

БАЙЛАНЫСТЫ

ДЕРЕККӨЗДЕР

ЭНТРОПИЯСЫ

Осы уақытқа дейін біз өз пікірлерімізде реттілікті оқиғаларың тәуелсіз болжамдарынан шығып отырдық. Бірақ, неміс орфографилық сөздігін ашқан күйде, біз бірден жақын орналасқан әріптер арасындағы тәуелділікті байқаймыз, мысалы: «qu», «ch», «ck», «tz» және «sch». Неміс мәтінін оқи отыра «q»-дан соң, сирек жағдайларды есепке алмағанда, «u» кездеседі. Бұл жағдайда «u» шарасыз оқиға секілді өзімен ешқандай ақпарат тасымалдамайды. Сондықтан, бұл тәріздес дереккөздер ақпаратын анықтау уақтысында оқиғалар арасындағы өзара байланысты ескеруіміз керек.