1–дәріс. Жүйелер туралы теорияның мәселелері. Жүйелер теориясының терминологиясы. Жүйенің қасиеттері. Жүйелік талдау
дәріс. Шеннонның кодтау туралы фундаменталды теоремалары. Аналогты - кодты түрлендірушілер. Циклдық кодтар. Циклдық кодтарды техникалық жүзеге асыру
жүктеу/скачать 1,13 Mb.
|
- Бұл бет үшін навигация:
- Шеннон-Фано алгоритмі
| 13 дәріс. Шеннонның кодтау туралы фундаменталды теоремалары. Аналогты - кодты түрлендірушілер. Циклдық кодтар. Циклдық кодтарды техникалық жүзеге асыру.
Кодтау – ақпаратты түрлендірудің жеке жағдайы. тиімді (оңтайлы) кодтау; бөгеуілге орнықты кодтар; криптография (ақпаратты құпиялап кодтау). Хабарламаны беру сұлбасында кодтаудың барлық түрлері және оларға сәйкес кодтау құрылғылары (кодер) және қабылдағыш тарапынан декодтау құрылғылары (декодер) берілген. Қысқартулар: К - криптографиялық; Э - тиімді; П – бөгеуілге орнықты Циклдық кодтау артықтықты жояды, хабарламалардың ұзындығының қысқаруына алып келеді, яғни хабарлама беру уақыты және жады көлемі азаяды. Циклдық кодтау тасығышта-сигналда ақпарат көлемін азайту үшін қолданылады. Циклдық кодтау қамтамасыз етеді: 1) хабарламалар көзінің статистикасы бойынша сигналдарды кодтау кезінде ақпаратты берудің ең үлкен жылдамдығы байқалады; 2) қабылдағыш жағынан сигналдарды декодтау жүзеге асады, жеке хабарламалар сигналдарға бөлінеді. Циклдық кодтау тәсілдері ақпараттық каналдың түрінен және қасиеттерінен тәуелді. Қазіргі кезде тиімді кодтаудың бірнеше тәсілдері жасалды Әліпбидегі символдарды кодтау үшін айнымалы (өзгермелі) ұзындықты екілік код пайдаланылады. Код тиімділігі екілік разрядтың орта санымен есептеледі: мұндағы k – әліпбидегі символдар саны; ns –s символын кодтау үшін екілік разрядтар саны; fs –s символының жиілігі; және Тиімді кодтау кезінде ақпарат жоғалмау үшін сығу шегі бар болады. Бұл параметр екілік разрядтардың шектік мәнімен анықталады: мұндағы n – кодталатын алфавит қуаты, fi –i-ші символ жиілігі. Шеннон-Фано алгоритмі— американдық ғалымдар Шеннон және Р.Фано алғаш рет жасаған сығу алгоритмі. Шеннон-Фано алгоритмі хабарламалардың артықтығын қолданады. Шеннон-Фано алгоритмі әдісі Хаффман алгоритміне өте ұқсас. Алгоритм ұзын айнымалы кодын қолданады: жиі кездесетін символ қысқа кодпен кодталады, сирек кездесетін символ ұзын кодпен кодталады. Шеннон-Фано коды префиксті болып табылады, ешбір кодтық сөз басқа кодтық сөздің префиксі болып табылмайды. Бұл қасиет кез-келген кодтық сөзді декодтауға мүмкіндік береді. Негізгі кезеңдері: m1 алғашқы алфавитінің белгілері ықтималдылықтарының кему реті бойынша жазылады; пайда болған алфавит белгілері екі бөлікке бөлінеді, бір – біріне максималды жақын белгілердің қосынды ықтималдылықтары; префиксті кодта алфавиттің бірінші бөлігі үшін екілік жүйедегі «0» саны меншіктеледі, екінші бөлігіне – «1». пайда болған бөліктер рекурсивті түрде бөлінеді және олардың бөліктері болып сәйкесінше префиксті кодтағы екілік жүйе сандары есептеледі. Шеннон-Фано коды ағаш түрінде тұрғызылады. Ағаштың тұрғызылуы түбірінен басталады. Мысал:a, b, c и d төрт символдан тұратын әліпби берілсін. Әр символды кодтау үшін 2 бит жеткілікті. a – 00, b – 01, c – 10, d – 11. Сонымен ababcaacdb хабарламасы 20 битпен кодталады. ababcaacdb хабарламасы бойынша әр символдың үлесін анықтайық және оларды үлестің кемуі бойынша кестеге орналастыру керек.
жүктеу/скачать 1,13 Mb. Достарыңызбен бөлісу:
|