5.5. Стационарлы марковтық дереккөздерді кодтау

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

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

Теорема 5.5.1. r жадты және энтропиялы стационарлы марковтық дереккөздер үшін кодтау теоремасы.

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

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

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

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

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

r жадты және энтропиялы стационарлы марковтық X дереккөзді кодтау.

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

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

3. Егер символ үшін кодты сөздің орташа ұзындығы энтропиясы-

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

5.6. Қорытындылар

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

5.3 Кесте. Марковтық тізбектер.

● Марковтық процесс деп қазіргі мағлұм, ал болашақ өткенге тәуелді емес стохастикалық процессті айтамыз.

● Ахуалдарда және уақытта дискретті марковтық процесс марковтық тізбек деп аталады. Ахуалдар реттілігі оның жүзеге асуы болып табылады

● Егер ахуалдар арасындағы өтпелі ықтималдықтар уақыттың санақ нүктесінің таңдауына тәуелді емес болса, Марковтың тізбегі гомогенді болып табылады, демек

● Гомогенді Марковтық тізбек толықтай өтпелі ықтималдықтар П матрицасымен анықталады және бастапқы бөлінумен

● Өтпелі ықтималдықтар матрицасының эквиваленті болып түйінді, жолды және ахуалдарға, ахуалдар арасындағы өткелдерге және өтпелі ықтималдықтарға сәйкес жолының салмағы бар ахуалдар кестесі болып табылады. 5.11 Сурет.

● Гомогенді марковтық тізбектің n–ші қадамдағы ахуалдарының бөлінуі келесі түрде анықталады