№ 4 практикалық тапсырмалар

Тақырып: Тиімді кодтау әдістері және принциптері

Мақсаты: Тиімді кодтау әдістері және принциптерімен таныстыру және олардың практикада қолданылуы.

ТЕОРИЯЛЫҚ МӘЛІМЕТТЕР

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

Егер i-я әріп, ықтималдылығы Рi болатын кодтық қиыстыру ұзындығы qi –і алса, онда ортаңғы қиыстыру ұзындығы

Кодтық әріптерді біркелкі деп есептей отырып, Н бастапқы әліпбиі энтропиядан азырақ емес болатын qср log m сияқты кодталған әліпбидің ең үлкен энтропиясын анықтаңдар, о.д.

qср log m ³ Н.

Осы арадан мынаны аламыз

Екілік кодтау кезінде (m=2) qср ³ Н ара қатынасына келеміз, немесе Qср мағынасы Н энтропиясына жақынырақ болса, сонша әсіресе кодтау нәтижелі. Идеалды жағдайда, qср » Н болғанда, кодты тиімді не болмаса нәтижелі деп атайды.

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

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

Әркелкі кодтарда әліпби әріптерінің арасына бөлетін символ қолдануға болады. (мысалы, хабарламаларды Морзе әліппесі көмегі арқылы жіберген кезінде).

Егер бөлетін символдардан бас тартса, онда бастапқы бөлімдерде дербес қиыстырулар сапасы ретінде қолданған кодтық қиыстыруларға тиым салу. Мысалы, егер 101 қандай да бір әріптің кодын білдірсе, онда 1,10 немесе 10101 қиыстыруларын қолдануға болмайды.

Ең алдымен, негізгі әліпбидің әріптерін (немесе кодтауға жататын кез келген хабарламаларды) кеміген ықтималдық ретінде жазады. Бұл ішкі жиындардың ықтималдылық жиынтығы шамамен тең болатындай етіп әріптер жиынын ретімен бөлу керек. Жоғарғы жартысындағы бірінші символ ретінде барлық белгілерге (әріптерге) 1 кодтық элементін, ал барлық төменгісіне 0-ді иемденеді. Содан соң, осы ықтималдықтардың теңдік шарттарын сақтай отырып және кодтық элементтің екінші символы ретінде осы шартпен меншіктелетін әрбір ішкі жиын қайтадан екі ішкі жиындарға бөлінеді. Тек қана ішкі жиында кодталатын әліпбиде бір ғана әріп қалғанша бұндай бөлшектеулер жалғаса береді. Жоғарғы ішкі жиынның әрбір әріптерін бөлшектеген кезінде 1 кодтық элементі меншіктеледі, ал төменгі ішкі жиын әріптеріне – 0.

1 мысал: Сегіз белгіден тұратын ансамбльдік тиімді кодтау өткізу:

1 кесте

Әріп (белгі) xi | Рi ықтималдылығы | Кодтық жүйелілік | qi ұзындығы | рi qi | -рilog рi
Бөлшектеу нөмірі
1 | 2 | 3 | 4
x1 | 0,25 | 1 | 1 |  |  | 2 | 0,5 | 0,50
x2 | 0,25 | 1 | 0 |  |  | 2 | 0,5 | 0,50
x3 | 0,15 | 0 | 1 | 1 |  | 3 | 0,45 | 0,41
x4 | 0,15 | 0 | 1 | 0 |  | 3 | 0,45 | 0,41
x5 | 0,05 | 0 | 0 | 1 | 1 | 4 | 0,2 | 0,22
x6 | 0,05 | 0 | 0 | 1 | 0 | 4 | 0,2 | 0,22
x7 | 0,05 | 0 | 0 | 0 | 1 | 4 | 0,2 | 0,22
x8 | 0,05 | 0 | 0 | 0 | 0 | 4 | 0,2 | 0,22

= 2,7

Көріп тұрғанымыздай, qср = H, демек, алынған код үйлесімді (оптимальды) болып келеді. Қарастырылған әдіс Шеннона - Фано әдісі сияқты белгілі.

2 мысал: Егер ықтималдылығы белгілі болса, Шеннона – Фанон кодын салу:

Р(x1) = 0,5; P(x2)= 0,25; P(x3) = 0,125; P(x4) = 0,125

3 мысал: Шеннона – Фано әдісін қолдана отырып, сегіз белгіден тұратын (m=8) ансамбльдік тиімді кодтау өткізу.

Шешімі: Әдетте (статистикалық мінездемелерді есепке алмағанда) екілік кодтауда k=2 белгісін пайдалана отырып элементтер санын біркелкі кодтау құрған кезінде кодтық жүйелілігі q ³ logk m = log2 8 = 3 болады, о.д. пайдаланылған әліпбидегі көрсетілген әрбір белгі үшін үш екілік символ қажет болады.

Шеннона – Фано әдісі ең үлкен ықтималдылығы бар негізгі ансамбльдің белгілері ең қысқа кодтық жүйеліктермен кодталатын кодтық қиыстырулар салуға рұқсат етеді. Олай болса, толық емес ақпараттық мүмкіншілігі қолданылатын кәдімгі екілік кодтаудың артықтығы жойылады.

2 кесте

Белгілері (әріптер) xi | Pi ықтималдылығы | Кодтық қиыстыру
Бөлшектеу нөмірі
1 | 2 | 3 | 4 | 5 | 6 | 7
x1 | 1/2 | 1 |  |  |  |  |  |  |
x2 | 1/4 | 0 | 1 |  |  |  |  |  |
x3 | 1/8 | 0 | 0 | 1 |  |  |  |  |
x4 | 1/16 | 0 | 0 | 0 | 1 |  |  |  |
x5 | 1/32 | 0 | 0 | 0 | 0 | 1 |  |  |
x6 | 1/64 | 0 | 0 | 0 | 0 | 0 | 1 |  |
x7 | 1/128 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
x8 | 1/128 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

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

Бұл жағдайда, белгідегі символдардың ортаңғы саны энтропияға дәл тең. Жалпы жағдайда, сегіз белгіден тұратын әліпби үшін белгідегі символдардың ортаңғы саны үштен азырақ болады, бірақ әліпби энтропиясы көбірек. Әліпби энтропиясын есептейміз:

Белгідегі символдардың ортаңғы санын есептейміз:

мұндағы q(xi) - xi белгісіне сәйкес келетін, кодты қиыстырулардағы символдардың саны.

4 мысал: Сегіз белгіден тұратын ансамбльдік тиімді кодтау кезіндегі кодтық қиыстырудың ортаңғы ұзындығын және әліпби энтропиясын анықтау.

3 кесте

Белгілері (әріптер) xi | Pi ықтималдылығы | Кодтық қиыстыру
бөлшектеу нөмірі
1 | 2 | 3 | 4 | 5
x1 | 0,22 | 1 | 1 |  |  |
x2 | 0,20 | 1 | 0 | 1 |  |
x3 | 0,16 | 1 | 0 | 0 |  |
x4 | 0,16 | 0 | 1 |  |  |
x5 | 0,10 | 0 | 0 | 1 |  |
x6 | 0,10 | 0 | 0 | 0 | 1 |
x7 | 0,04 | 0 | 0 | 0 | 0 | 1
x8 | 0,02 | 0 | 0 | 0 | 0 | 0

Шешімі: 1. Кодтық қиыстырудың ортаңғы ұзындығы

2. Әліпби энтропиясы

Шеннона - Фано әдістемесі бойынша кодтау кезінде кейбір символдардың жүйелілігі артық, ереже сияқты (qср > H) қалады.

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

5 мысал: Барлығы ықтималдықтар сәйкестігінде көрсетілген x1 және x2 екі белгісі негізінде әліпбидің арқасында құрастырылған хабарламалардың тиімді кодтау процедурасын қарастырамыз

Р(х1) = 0,9; P(x2) = 0,1.

Ықтималдықтары бірдей емес, онда бұндай әріптерде жүйелілік артықпен ие болады. Бірақ, әріптерді әрбір әріпке кодтау кезінде біз ешқандай күшті әсерді алмаймыз. Шынымен де, әрбір әріпті тапсырғанда немесе 1, немесе 0 символдарды қажет етеді, сол уақытта энтропиясы бірдей болады.

,

н.б. былай да болады

Құрамында екі әріптен тұратын блоктарды кодтаған кезінде, мынадай кодтарды аламыз

4 кесте

Блоктар | Ықтималдықтар | Кодтық қиыстыру
бөлшектеу нөмірі
1 | 2 | 3
x1x1 | 0,81 | 1 |  |
x1x2 | 0,09 | 0 | 1 |
x2x1 | 0,09 | 0 | 0 | 1
x2x2 | 0,01 | 0 | 0 | 0

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

Блоктағы символдардың орта саны

ал әріпі, 1,29/2 = 0,645, о.д. Н = 0,47 жақындады және дәл осылай кодтау тиімділігін жоғарлатудың сәті түсті.

Үш белгіден тұратын блоктардың кодталуы тағы да үлкен күшті әсер береді:

5 кесте

Блоктар | Pi ықтималдылығы | Кодтық қиыстыру
бөлшектеу нөмірі
1 | 2 | 3 | 4 | 5
x1x1x1 | 0,729 | 1 |  |  |  |
x2x1x1 | 0,081 | 0 | 1 | 1 |  |
x1x2x1 | 0,081 | 0 | 1 | 0 |  |
x1x1x2 | 0,081 | 0 | 0 | 1 |  |
x2x2x1 | 0,009 | 0 | 0 | 1 | 1 |
x2x1x2 | 0,009 | 0 | 0 | 0 | 1 | 0
x1x2x2 | 0,009 | 0 | 0 | 0 | 0 | 1
x2x2x2 | 0,001 | 0 | 0 | 0 | 0 | 0

Блоктағы символдардың орта саны 1,59-ға тең, ал белгісі – 0,53, энтропиядан барлығы 12%-ға жоғары деген сөз.

Тиімділіктің жоғарылауы блоктардың ірілендіруі кезінде көбіне жақын ықтималдықтарды шағын топ жиынтығымен бөлініп алынған ықтималдықтардың терімі арқылы анықталады.

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

6 кесте

Белгілері (әріптер) xi | Pi ықтималдылығы | 1-ші кодтық қиыстыру | 2- ші кодтық қиыстыру
бөлшектеу нөмірі | бөлшектеу нөмірі
1 | 2 | 3 | 4 | 5 | 1 | 2 | 3 | 4 | 5
x1 | 0,22 | 1 | 1 |  |  |  | 1 | 1 |  |  |
x2 | 0,20 | 1 | 0 | 1 |  |  | 1 | 0 |  |  |
x3 | 0,16 | 1 | 0 | 0 |  |  | 0 | 1 | 1 |  |
x4 | 0,16 | 0 | 1 |  |  |  | 0 | 1 | 0 |  |
x5 | 0,10 | 0 | 0 | 1 |  |  | 0 | 0 | 1 |  |
x6 | 0,10 | 0 | 0 | 0 | 1 |  | 0 | 0 | 0 | 1 |
x7 | 0,04 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1
x8 | 0,02 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0

Көрсетілген жетіспеушілікте Хаффмена әдістемесі бос.

Мынау әдістеме әріпке символдардың орта санымен ықтималдықтардың тап осы таратуларының ең азы үшін кодтың бір мағыналы құрылуына кепіл болады.

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

Ықтималдылығы бірлікке тең жалғыз қосалқы әріпті алмайынша процесс жалғаса береді.

Хаффмен әдістемесін қолдана отырып, сегіз белгіден тұратын ансамбльдік тиімді кодтауды жүзеге асырамыз:

7 кесте

Белгілері | Ықтималдылығы | Қосалқы бағаналар | Жаңа қиыстыру
1 | 2 | 3 | 4 | 5 | 6 | 7
x1 | 0,22 | 0,22 | 0,22 | 0,26 | 0,32 | 0,42 | 0,58 | 1 | 01
x2 | 0,20 | 0,20 | 0,20 | 0,22 | 0,26 | 0,32 | 0,42 |  | 00
x3 | 0,16 | 0,16 | 0,16 | 0,20 | 0,22 | 0,26 |  |  | 111
x4 | 0,16 | 0,16 | 0,16 | 0,16 | 0,20 |  |  |  | 110
x5 | 0,10 | 0,10 | 0,10 | 0,16 |  |  |  |  | 100
x6 | 0,10 | 0,10 |  |  |  |  |  |  | 1011
x7 | 0,04 | 0,06 |  |  |  |  |  |  | 10101
x8 | 0,02 |  |  |  |  |  |  |  | 10100

Көрнектілікке арналған кодты ағашты саламыз. 1 лайықты ықтималдықтар нүктесінен екі бұтақты бағыттаймыз және де бұтақтағы үлкен ықтималдылыққа 1 символын, ал азына 0-ді иемденеміз.

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

1 сурет.

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

6 мысал: Шеннона - Фано және Хаффмона әдістемелерін қолдана отырып, 4 мысалда көрсетілген ансамбль арқылы сипатталатын орыс тілі бойынша әліпбиінің тиімді кодталуын жүзеге асыру.