Лекция 1 Ақпарат теориясы ақпараттық жүйелерді сипаттаудың сапалы және сандық әдістері негізі ретінде. Ақпаратты өлшеу


Лекция 6 Котельников теоремасы бойынша есептеу дәлдігін таңдау



бет9/20
Дата24.01.2023
өлшемі1.34 Mb.
#181866
түріЛекция
1   ...   5   6   7   8   9   10   11   12   ...   20
Байланысты:
6-Лекция

Лекция 6
Котельников теоремасы бойынша есептеу дәлдігін таңдау.
Шеннонна-Фэно әдісі келесідей құрылады, дискретті кездейсоқ шаманың мәні ықтималдылықтың кему ретімен орналасады, ал содан кейін бірдей ықтималдылықпен 2 бөлікке бөлінеді, бірінші бөліктің кодына 0, ал екіншінің кодына 1 қосылады.
Бұл мысалда алатынымыз

Тағыда бір мысал. Код іріктелгеннен кейін құрылады, яғни В және С мәнін орналастырғаннан кейін.

Хаффмен(Huffman) әдісі 1952 жылы жасалынды. Ол тиімді және сығу деңгейі бойынша ешқашанда Шеннонна-Фэно әдісіне жол бермейді, сонымен қатар ол максималды тығыз сығады. Код екілік ағаштың (бинарлық) көмегімен құрылады. Дискретті кездейсоқ шама мәнінің ықтималдылығы оның жапырағына жазылады, барлық ағаш жапыраққа сүйене отырып құрылады. Ағаш түйініне жазылған шама түйін салмағы деп аталады. Ең аз салмақтағы екі жапырақтың салмақтарының қосындысына тең салмаққа ие басшы түйінді құрайды. Тамырды құраған соң, басшы түйінінен шығатын әрбір бұтаққа 0 немесе 1 мәнін жазу қажет. Дискретті кездейсоқ шаманың әрбір мәнінің коды- бұл берілген мәнге сәйкес бұтақтың тамырдан жапыраққа тіркесі кезінде алынатын сан.
Хаффмен және Шеннонна-Фэно әдісінің тәсілдері үшін әрқашан мәліметпен бірге код кестесін жіберу керек. Мысалы, 2 мысал үшін, 10 кодқа С символы, 0-ге А және т.б.сәйкес келетінін хабарлау керек.
Алдынғы екі мысалдығы дискретті кездейсоқ шаманың мәні үшін Хаффмен кодын құрамыз.




Арифметикалық кодтау
Хаффменнің кодтау алгоритмі, мәліметтердің әрбір символына 1 биттен артық емес ақпарат жібере алмайды. Нөл мен бірден тұратын мәліметте бірліктер нөлге қарағанда 10 есе жиі кездеседі деп қарастырайық. Хаффменнің әдісі арқылы кодтағанда 0 үшін де, 1 үшін де бірдей артық бит жұмсалады. Бірақ дискретті кездейсоқ шаманың энтропиясы мынадай мәліметті 0,469 бит/сим реттейді. Хаффменнің әдісі мәліметтің бір символындағы биттің орташа санының минималды мәніне 1 битті береді. Кейбір символдарды бірден аз битпен кодтауға мүмкіндік беретін кодтау схемасының болғанын қалаймыз. Осындай схемалардың арасындағы ең үздігі ХХ ғ. 70-жылдарында шыққан арифметикалық кодтау болып табылады.
Ықтималдылықтың үлестірімі бойынша кодтау үшін таңдалған дискретті кездейсоқ шама үшін , дискретті кездейсоқ шаманың әр мәні үшін шекаралық нүктелерде қиылысатын кесіндіден тұратын кесте құрылады. Осы кесінділердің қосындысы [0,1] кесіндіні құрауы қажет, ал олардың ұзындығы дискретті кездейсоқ шаманың мәніне сәйкес ықтималдылықтарға пропорционалды болуы керек. Кодтау алгоритмі дискретті кездейсоқ шама мәнінің кезектестілігін анықтайтын кесіндіні құрудан тұрады. Одан кейін кесінді құру үшін, оның ішкі бөлігінде жататын және минималды мүмкін болатынекінің оң, бүтін дәрежесіне бөлінген, бүтін санға тең санды табамыз. Бұл сан қарастырылып отырған кезектестіктің коды болып табылады. Барлық нақты болатын мүмкін кодтар – бұл нөлден үлкен және бірден кіші сандар, сондықтан алда келе жатқан нөл мен ондық нүктені алып тастауға болады, бірақ мәліметтің соңын белгілейтін тағы да бір арнайы код-маркер керек. Кесінділер былай құрылады.егер n-1 ұзындықтағы мәлімет үшін кесінді болса, онда n ұзындықтағы мәлімет үшін кесіндіні кесіндіні құрастыру үшін, оны қарастырып отырған дискретті кездейсоқ шаманың мәні қанша болса, сонша бөлікке бөлеміз. Бұл бөлу біріншідегідей (реттілікті сақтау) жүзеге асырылады. Одан кейін алынған кесінділерден берілген нақты n ұзындықтағы кезектестікке сәйкес келетінін таңдаймыз.
Алдында қарастырылған әдістерден бұл кодтаудың негізгі ерекшелігі оның үздіксіздігінде, яғни блоктауды қажет етпейтіндігінде.Арифметикалық кодтаудың тиімділігі сығылатын мәліметтің ұзындығы өскен сайын арта түседі (Хаффмен және Шеннонна-Фэно кодтауында болмайды). Арифметикалық кодтау Хаффмен кодтауына қарағанда жақсы сығады, бірақ ол тәжірибеде сирек қолданылады, өйткені ол жай пайда болды және көптеген есептеу ресурстарын талап етеді.
Берілген деректерді сығуда, мысалы, файлдан барлық қарастырылған әдістер екі тәсілді талап етеді. Біріншісі символ ықтималдылығының жақын мәндері ретінде қолданылатын символдардың жиілігін жинақтау және екіншісі сығу үшін.
Арифметикалық кодтаудың мысалы. Х дискретті кездейсоқ шамасы тек 0 және 1 мәнін 2/3 және 1/3 ықтималдылықпен қабылдасын.0 мәнін [0;2/3]; ал 1- [2/3;1] кесіндісіне орналастырамыз. Онда дискретті кездейсоқ шамасы үшін,

кодты құрудың кестесі-
Аралықтар мен кодтар Ықтималдылығы Хаффмен коды


Арифметикалық кодтау үшін мәлімет бірлігіндегі биттің орташа саны, энтропияға қарағанда аз болды. Бұл қарастырылып отырған жай ғана кодтау схемасында мәлімет соңындағы код-маркер сипатталмағандықтан, егер оны енгізсек, онда биттің орташа санын энтропиядан көп етеді.
Шығарылатын мәліметті оның арифметикалық кодынан алу келесі алгоритм бойынша жүзеге асады.
Қадам 1.Дискретті кездейсоқ шама мәнін кодтау кестесінде ағымдағы коды бар аралық анықталады,- бұл аралық бойынша шыққан мәліметтің бір символы анықталады. Егер бұл символ - мәлімет соңының маркері болса, онда бұл соңы болады.
Қадам 2.Ағымдағы кодтан оның аралығы бар төменгі шекара алынады, оны осы аралықтың ұзындығына бөлеміз.Алынған сан кодтың жаңа ағымдағы мәні болып саналады. 1 қадамға ауысамыз.




Достарыңызбен бөлісу:
1   ...   5   6   7   8   9   10   11   12   ...   20




©kzref.org 2023
әкімшілігінің қараңыз

    Басты бет