5.5. Тұрақты марковский көзін кодтау

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

жадысы бар марковский көзі жағдайында, блок ұзындығы үшін сәйкес энтропия шекті жағдай болып табылады және кодтау теоремасы келесі бейнеде жазылуы мүмкін:

Теорема 5.5.1. жадысы бар тұрақты марковский көзінің кодтау теоремасы және энтропиясы.

ұзындықты блок үшін -шы префиксті код бар, онда орташа ұзындықты кодтық сөзі теңсіздікті қанағаттандырады

Марковский көзінің жіктелуі жадысыз қосалқы көзінен тікелей оңтайлы кодтау стратегиясы туындайды.

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

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

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

жадысы бар тұрақты марковский көзін кодтау және энтропиясы, тең.

1. Блоктарға символ көздерін біріктіреді.

2. Блоктар үшін Хаффман кодтауын өткізу.

3. Егер символға кодтық сөздердің орташа ұзындығы елеулі түрде энтропиядан ерекшелінсе, онда блок ұзындығын кейінгі символдар есебінен арттыру қажет. Үлкен ұзындықты блок үшін Хаффман кодтауын өткізу. Бұл процесті орташа ұзындықты кодтық сөздің энтропияға жуықтауын қанағаттандырғанша жалғастыру.

Мысалы: жадысы бар Марковский көзін кодтау (жалғасы).

Алдыңғы бөлімнен ұсынылған сандық мысал негізіндегі алгоритмнің тиімділігін тексереміз.

Сәкесінше жадысы бар , әрбір үш символын блоктарға біріктіреміз және Хаффман кодтауын өткіземіз.

Б локтар үшін қажетті ықтималдылық күйі тұрақты бөлу ықтималдылығымен(5.58) және өтпелі ықтималдылық матрицасымен (5.58) немесе күй графымен (5.7-сурет) анықталады. 001 блогының ықтималдылығы ,мысалы, тең

000 блогы ешқашан пайда болмайтынын байқауға болады, демек кодталмауы тиіс.

5 .7. таблицасынан кодтық сөздің орташа ұзындығы 0,911 символына тең екенін анықтаймыз.Сондықтан, кодтаудың тиімділігі салыстырмалы түрде аз

Ү лкен ұзындықты блоктарды құру арқылы кодтаудың тиімділігі айтарлықтай арттырылатын болады. Ұзындығы 4-ке тең (5.2-таблица) Хаффман кодтауын блок үшін қайталаймыз. 5.1. таблицадан символға кодтық сөздердің орташа ұзындығы 0,744-ке тең. Кодтаудың тиімділігі қазірдің өзінде тең

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

Мысалы: бірінші реттегі марковский көзі.

Бірінші реттегі марковский көзінің күй графы 5.9-суретте берілген.

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

Т аблица 5.1. Блок ұзындығы 3-ке тең және жадысы бар марковский көзі үшін Хаффман кодтауы.

2. Энтропия көзін табыңыз.

3. Үш екілік символдан тұратын блок үшін Хаффман кодтауын өткізіңіз.

4. Қандай кодтау тиімділікке ие ?

Шешімі.

1. 5 .9-суретте өтпелі ықтималдылық тең

мына теңдіктен өтпей, Фр тұрақты ықтималдылық күйінің мәні анықталады

с ондықтан,

О сыдан аңғарылады, бұл

Таблица 5.2. Блок ұзындығы 4-ке тең және жадысы бар марковский көзі үшін

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

2. Э нтропия көзі анықталады

3. Ү ш екілік символдан тұратын блок ықтималдылығы тең

5 .10-суретте Хаффман кодтауы көрсетілген.

4. К одтық сөздің орташа ұзындығы анықталады

д егенмен, кодтау тиімділігі тең