№ 1-2 практикалық тапсырмалар

Тақырып: Ақпараттық санын бағалауы бойынша үйрету.

Шумен байланыс каналы бойынша хабарламаларды жіберу кезіндегі ақпараттық хабарлардың жойылуын есептеу

 

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

 

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

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

Алфавит m белгілерден (әріптерден) тұрсын, олардың әрқайсысы хабарлама элементтерінен тұруы мүмкін. Мүмкін болатын хабарлама санының ұзындығы n ауыспалы шектелмеген қайталанулар санына тең:

N = mn

 

Комбинаторика (негізгі ұғымдары).

 

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

Егер n тіркесім ретін қадағалау есептелсе және көңілге элементтер есепсіз ретпен алынса, онда n элементінің іріктемесі  n- орын ауыстыру деп аталады. n- элементінің іріктемесі деп, егер жүру реті есептелсе және n-тіркесім болса, онда элементтің реті есепке алынбайды. Төрт элементтен (белгіден) тұратын жиын (алфавит) берілсін

M = {a,b,c,d,}

(алфавиттің көлемі төрт белгіден тұрады)

Хабарламаларды іріктеу abc, acb, bac, bca, cab, cba әртүрлі болып табылады

Бір және сол элементтерден (белгілерден) жасалған 3-ауыспалы. Осы уақытта іріктемелер (хаттама) бір және сол сияқты 3-тіркесімнен тұратын әртүрлі жазуын көрсетеді.

Хабарламалар қайталану белгілерін жіберуі де, жібермеуі де мүмкін.

Хабарламалардағы қайталануларды екі тәсілмен айыруға болады.

Бірінші жағдайда, қайталанатын элементтер қоры шектелген деп ұйғарылады және өзіндік ерекшелігімен анықталады  {m1, m2, ...,mk}, мұндағы mi -  i-ші түріндегі элементтер саны. Бастапқы жиындардағы элементтердің жалпы саны m = m1+m2+...+mk, ал n – іріктемесінде n £ m. Әрбір түрдегі элементтерді әртүрлі есеппен саналатын және әдетте бірдей нөмірлермен немесе символдармен белгіленетін эквивалентті класс ретінде қарастыруға болады. Әрбір класстардың жиынтығы отбасылық өкілді құрайды.

Бастапқы жиын ерекшеленген эквивалентті үш класспен берілсін {2,5,4}, m = 2+5+4 = 11. Класстар өкілін a, b, c арқылы белгілейміз, ал отбасы өкілі {a, b, c} жиынын құрайды.  Отбасы өкілі {a, b, c} жиынын құрайтындай етіп класстар өкілін a, b, c  арқылы белгілейміз. Сонда aabbbc, ababbc, babbc іріктегенде әртүрлі 6-ауыспалы, aabbbbbcccc және aabbbccbccb іріктегенде әртүрлі 11-ауыспалы болып табылады. aabbbc, bbbbbc, abbccc арқылы іріктегенде мысалы, әртүрлі 6-тіркесім, ал 11 – тіркесім тек қана біреу: aabbbbbcccc.

Екінші жағдайда, элементтер қоры шектелмейді, іріктемеде n элементтер ішінен n-нен асып кетпейтіндей кез келген қайталанатын сан жіберіледі. Бастапқы жиынды әртүрлі элементтен тұратын етіп қарастыруға болады, бірақ іріктемеден кейін кейбір элементтерді осы жиында қайта құрады (қайтару іріктемесі).

Қайталанбайтын әртүрлі m элементтері (алфавит негізі ішінен) ішінен n-ауыспалы бойынша (хабарлама ұзындығы  n)  N санын (мүмкін болатын хабарлама санын) анықтаймыз. Бірінші ауыспалы мүшесін (хабарлама) m элементтер (белгілер) ішінен m әртүрлі тәсілдермен таңдауға болады. Элементтер қайталанбауы керек, онда екінші мүшені таңдауды m -1  амалымен ғана жүзеге асыруға болады және т.б. n-ші мүшесіне дейін таңдауға болады.

m-n+1амалымен. Көбейтінді ережесін жүйелі түрде қолдана отырып (егер а объектісі р тәсілімен таңдап алынған болса және әрбір осындай таңдап алынған кейінгі өз кезегіндегі b объектісі q тәсілімен таңдап алынған болса, онда көрсетілген реттегі “a” және “b” таңдауды pq тәсілімен жүзеге асыруға болады; бұл ереже таңдалған a және b тәуелсіз болған жағдайда ғана қолданылады), аламыз

N(m,n) = m(m-1)...(m-n+1),  m ³ n

Мысалы, 1,2,3,4, нөмірленген төрт әртүрлі объектілердің ішінен 12 келесі 2-ауыспалы құрастыруға болады: 12, 13, 14, 23, 24, 34, 21, 31, 41, 32, 42, 43.

Әдетте n әртүрлі элементтері бойынша m-ауыспалысын жай ауыспалы деп атайды. n = m деп, ауыспалы санды аламыз

N(m,n) = m(m-1)...2*1 = n!

Қатынасты пайдалана отырып, былай жазамыз:

Ауыспалы m элементінің қайталануын қарастырамыз, ерекшілігі {m1, m2,...,mk}, мұндағы m = m1+m2+...+mk. Бұндай ауыспалы кейбір санның элементтерінің бейнеленуіне байланысты m! қарағанда кіші болады, ал бірдей элементтерді ауыстыру ештемені өзгертпейді. J классының элементтерін ауыстыруды mj! тәсілі бойынша жібереді, ал әрбір класста бұндай операциялар тәуелсіз түрінде жүзеге асырылады. Сондықтан, берілген ауыстыруды өзгертпей көбейтінді ережесіне сәйкес ауыстыруды m1! m2! ... mk! бойынша жасау. Демек m элементінен алынатын қайталанатын ауыспалы әртүрлі сандарды мына формуламен өрнектейді:

Мысалы, 10 үйдің көшесінің құрылысын салу жоспары, оның ішінде 3 үй бір типті, 5-і басқа және

2 үшінші, мына амалмен  N10(3,5,2) = 10!*3!*5!*2! = 2520 көрсетуге болады.

Егер m әртүрлі типті объектілер қорында шектелген болса, онда n – ауыстыруының әрбір орнын m әртүрлі амалдарымен толтыруға болады.  Сондықтан, көбейтінді  ережесіне сәйкес шектелмеген қайталанатын n-ауыспалы санына N(m,n) =mn тең. Негізінде, бұл қатынас  позициялық жүйенің негізі m  түрінде жазылған әртүрлі n-разрядтық сандар санын анықтайды.

Хабарламаға барлық N-ді алу теңықтималдық болып табылады, ал нақтылы хабарламаны алу үшін 1/N ықтималдығынан кездейсоқ бір объектілерінің ішінен  N –ді таңдап алу. N –нен үлкен екені айқын, үлкен дәрежелі анықталмаған сипатталса, сонша хаттамаларды  хабарланатын деп есептеуге болады. Сонымен, N саны ақпараттың өлшеміне қызмет ететін еді. Бірақ, ақпараттық теория позициясында аддитивті қасиет өлшемі есептеледі, оны хаттаманың ұзындығына пропорционалды етіп анықтайды (мысалы, телеграмма –арқылы хабарлама жібергенде және төлегенде оның мазмұны маңызды емес, ал жалпы белгі саны маңызды).  Бұл талапқа ақпараттық санның сапасы ретінде қолданылатын логарифмдік функция жауап береді.

I = log N = log mn = n *log m

Бір элементке келетін хабарламалардың (белгі, әріп) ақпараттық санын энтропия деп атайды:

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

loga m =loga b logb m  бір негізінен басқаға ауысуы тек қана бірлікті өлшеу өзгерісіне әкеп соғады. Көбінесе екілік логарифм қолданылады, сонда энтропия былай болады

H0 = log2 m

Хабарламаның бір элементіндегі ақпараттар санының бірлігін екілік бірлік немесе бит деп атайды. log2 m = 1 өрнегінен m  = 2, бұдан 1 биттің – 0 және 1 теңықтималдық жағдайында бір екілік элементті сипаттайтын ақпараттық саны екенін көреміз.

Екілік хабарламаның n ұзындығында n ақпараттық бит бар.

8 битке тең болатын ақпараттық санының бірлігі байт деп аталады.

Егер логарифмнің негізін онға тең деп таңдап алсақ, онда энтропия ондық бірліктегі хабарламаның элементі (дит) арқылы өрнектеледі, мұндағы 1 дит = log102 бит = 3,32 бит. 

 

1 мысал: Бір кадрлық разверткаға сәйкес келетін теледидардық сигналға қатысты ақпараттық санын анықтаймыз. Кадрда 625 жол болсын, ал бір жолға сәйкес келетін сигнал 600 кездейсоқ амплитуда импульсындағы тізбегін көрсетеді, ал амплитуда импульсы кез келген 8 мәнінің 1 В қадамын қабылдай алады. 

Шешімі: Олай болса, біл жолдағы n = 600 сәйкес келетін хабарламаның ұзындығы бойынша жағдайды қарастырамыз. Бір жолдағы хабарламаның (белгілерінің) элементтер саны m = 8.

Бір жолдағы ақпараттық саны: I = n log m = 600 * log 8, ал кадрдағы ақпараттық саны  I¢ = 625 * I = 625*600 log 8 = 1,125 × 106 бит

 

2 мысал: Санның ең аз салмағын анықтаймыз, оның оңжақты салмақта туындауы қажет болатындай етіп ортасында 27 сыртқы айырықсыз мәнеталардың ішінен бір жалғанды не болмаса ең жеңілін табу. (Жауабы: 3)

Жоғарыда қарастырылған ақпараттың бағалауы алфавиттің барлық белгілерінің ықтималдық теңдігі ұйғарымына негізделген.

Жалпы жағдайда әрбір белгіден әртүрлі ықтималдық хабарлама шығады.

Статистикалық талдау негізінде хабарлама xi белгісі бойынша n ұзындығынан ni рет шығатыны белгілі болсын, ол дегеніміз белгінің ықтималдық шығуы

      (i = 1, 2, 3, ... , m)

Алфавиттің барлық белгілері кездейсоқ оқиғалардың толық жүйесін құрайды, сондықтан

Барлық мүмкін болатын хабарлама санының n ұзындығын, ерекшелігі {n1, n2, ..., nm} болатын  xi белгісі ni (i = 1, 2, ... ,m) рет арқылы өтетін n элементінен қайталанатын ауыспалы сан ретінде анықтауға болады.

Сондықтан мүмкіндік хабарлама саны

Мысалы, 10 үйдің көшесінің құрылысын салу жоспары, оның ішінде 3 үй бір типті, 5-і басқа және 2-і үшінші типті, төмендегідей түрде көрсетуге болады

Алдыңдағысы сияқты, аналогиялық түрде ақпараттар санын табамыз

I = log N = log n! - (log n1!+log n2!+...+log nm!).

Үлкен n-ң жеткіліктілігі арқылы бұл өрнекті жуықталған Стирлинг формуласының көмегімен түрлендіруге болады.

log n! » n(ln n - 1)!.

Мына формуланы және қатынасты пайдалана отырып, мынаны , аламыз

Логарифмнің ықтималдық және еркіндік  негізіне ауыса отырып, энтропия және ақпараттық саны үшін Шеннон формуласын аламыз.

Алда теңдеулердегі I және H үшін логарифмнің негізін үнемі 2 деп аламыз.

 

Энтропияның қасиеттері.

Алфавиттің тең ықтималдық белгілерінен Рi = 1/m және жалпы формуладан мынаны аламыз

Бұл жағдайда, энтропия алфавиттің m өңкей сандық белгілерімен анықталады және тек қана алфавиттің сипаттамасы болып табылады.

Егер әріптер бір-бірімен тең болмаса, онда алфавитті статистикалық үлестіруі бойынша  берілген ni жиілігінің дискреттік кездейсоқ шамасы  ретінде қарастыруға болады. (немесе ықтималдылық  Рi =ni / n):

 

1 кесте

хi белгілері

x1

x2

. . .

xm

ni жиілігі

n1

n2

. . .

nm

 

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

Сол себепті, өрнектегі энтропияның формалдығына алфавиттің сипаттамасы ғана кіреді, ол кейбір хабарламаны қосындысының статистикалық қасиеттерінде бейнеленеді. log 1/Pi шамасын  өрнегі негізінде хi белгісін хабарландыратын, ал H – энтропиясын жеке энтропияның орташа мәнін сипаттайтын жеке энтропия ретінде қарастыруға болады.

Pi кіші болғанда жеке энтропия зор, Pi –ді бірлікке жақындатқанда ол нөлге ұмтылады (1 сурет).

 

1 сурет. log 1/Pi   және   -Pi × log Pi функцияларының кестесі

-Pi × log Pi функциясы H энтропиясына  хi белгісін аманатында бейнеленеді.  Көріп тұрғанымыздай, Pi=1 болғанда бұл функция нөлге тең болады, содан кейін өзінің максимумына дейін өседі және Pi кеміген кезінде нөлге ұмтылады.

Шарт бойынша, мынанытабамыз

Pi e = 1,мұндағы е – натуралдық логарифмнің негізі. Олай болса, Pi = 1/e = 0,37 арқылы -Pi log Pi функциясында  максимумы бар.  Н энтропиясының -  шамасы нақты, теріс емес және шектеулі , ол дегеніміз Н ³ 0. (бұл қасиет Pi log 1/Pi –ң барлық қосындысының қасиеттеріне ие). 

Егер бізге хабарлама ертерек белгілі болса, онда энтропия нөлге тең болады (бұл жағдайда,  хабарламадағы әрбір элемент бірлікке тең кейбір белгілердің ықтималдылығын кірістіреді, ал қалған белгілердің ықтималдылығы нөлге тең). 

Сол сияқты энтропияның максималдылығын алфавиттің барлық белгілері бойынша теңықтималды арқылы көрсетуге болады, ол дегенімізі  Нmax = log m.

 

3 мысал: Алфавиттің белгілерінің үлестіру түрі мынадай р(х1) = 0,1 р(x2) = 0,1 р(x3) = 0,1 р(x4) = 0,7. Барлық белгілері теңықтималды, ал энтропиясы берілген алфавиттікі сияқты басқа алфавиттің де белгілер санын анықтау.

Көбінесе, екі белгілі алфавитті (0,1) пайдаланатын бинарлық хабарламасы қызығушылық танытады. Алфавиттің Р1¹Р2 = 1 ықтималдық белгісінде m = 2 болса, онда Р1 = Р және Р2 = 1-Р деп алуға болады. Онда энтропияның қатынасы былай анықталады

,

графигі 2 суретте көрсетілген

2 сурет. Екілік энтропиясының хабарламасы 1 және оның құрастырушысы

2 кестесі:  - (1 - Р) log (1 - P)  және  3: - P log P

 

Көріп тұрғанымыздай, бинарлық хабарламаның энтропиясы Р = 0,5 болғанда 1 битке тең болатын максималды мәндерге жетеді және оның кестесі осы мәнге қатысты симметриялы.

 

4 мысал: Әріптерді пайдаланғанда теңықтималдықтардың көзі болатын және кестеде көрсетілгендей ансамбл арқылы сипатталып әріпке келетін ақпараттың көзі (орыс тілінің алфавиттері) бойынша белгісіздігін салыстыру,

 

 2 кесте

Әріп

Ықтималдық

Әріп

Ықтималдық

Әріп

Ықтималдық

Әріп

Ықтималдық

а

0,064

й

0,010

т

0,056

ы

0,016

б

0,015

к

0,029

у

0,021

э

0,003

в

0,039

л

0,036

ф

0,02

ю

0,007

г

0,014

м

0,026

х

0,09

я

0,019

д

0,026

н

0,056

ц

0,04

пробел

0,143

е

0,074

о

0,096

ч

0,013

 

 

ж

0,008

п

0,024

ш

0,006

 

 

з

0,015

р

0,041

ш

0,003

 

 

и

0,064

с

0,047

ъ

0,015

 

 

 

Шешімі: 1. Бір әріп арқылы өтетін бірдей ықтималдылығында шығатын барлық m = 32 алфавиттегі әріптің белгісіздігі энтропияны сипаттайды

H = log m = log 32 = 5 бит

2.     Берілген ансамблдік кестеде сипатталатын энтропияның негізі

                           -0,064 log 0,064 -0,015log0,015 - ... -

- 0,143log0,143 » 4,43 бит

Олай болса, әріптерді пайдалана отырып ықтималдылықты әркелкілік үлестіруі энтропияның негізін 5-тен 4,42 битке дейін төмендетеді

 

5 мысал: Х және У ансамблінің х және у екі дискреттік шамасы берілген:  

 

3 кесте

хi кездейсоқ шамалары

0,5

0,7

0,9

0,3

Олардың пайда болу ықтималдылығы

0,25

0,25

0,25

0,25

4 кесте

уj кездейсоқ шамалары

5

10

15

8

Олардың пайда болу ықтималдылығы

0,25

0,25

0,25

0,25

 

Олардың энтропиясын салыстыру.

 

Шешімі: Энтропия кездейсоқ шаманың айқын мәніне тәуелді емес.

Екі шаманың да пайда болу ықтималдылығы бірдей, онда

Н(Х) = Н(У) = - 4(0,25log0,25) = -4(1/4log1/4) =

= log 4 = 2 бит

 

Үздіксіз хабарламаның энтропиясы

Хабарламаның үздіксіздігі арқылы элементтерге бөлінбеген, соңғы алфавиттің орнына ықтималдылық тығыздығының Р(х) үздіксіз бөлінуімен анықталатын мүмкін болатын элементтері бойынша шексіз жиындарды қарастыру қажет. 

Шеннон формуласын жалпылау үшін Dх тең қиылыспайтын бөліктерінің (кесінділерінің) мүмкін болатын жағдайлары бойынша интервалдарға бөлеміз және Pi = p(xi)Dx   (i = 1, 2, ... , m) ықтималдылығы бойынша х1, x2, ... , xm дискреттік жиынның жағдайын қарастырамыз. Олай болса

 

Қатынас есебі бойынша шегі Dx ®0 ұмтылады

мынаны аламыз

Көрсетілген энтропия деп аталатын бұл соммадағы бірінші қосындысы оның элементінің сертті статистикалық жағдайының  тұтасымен хабарландыратын хабарламаны анықтайды.

logDx шамасы таңдап алынған Dx интервалының кванттық жағдайының дәлдігін анықталатын Dx =const тұрақты кезінде ғана тәуелді.

Сонымен, энтропия және ақпараттық саны р(х) ықтималдылық тығыздылығын үлестіруіне қатысты болады.

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

Берілген дисперсия арқылы көрсетуге болады

Элементтерінің жағдайы қалыпты заң бойынша бөлінген жағдайда ғана хабарланатын ең үлкен хабарламаға ие болады:

Дисперсия сигналдың орташа күштілігін анықтайды, осыдан маңызды қорытынды шығаруға болады. Берілген сигналдың күштілігінен ең үлкен ақпараттық санын тапсыруы бойынша  (немесе берілген ақпараттық санын қолайлырақ етіп үнемдеп беру) үлестіруді қалыпты етіп жақындату арқылы сигналды өңдеп жетістікке жеткізеді. Осы уақытта, қалыпты үлестіруді бөгеуілге жапсыру арқылы оны ең үлкен «хабарландыратын» мен қамтамасыз етеді, ол дегеніміз сигналдарды ең жаман жағдайда өткізе отырып оның зиянды әсер етуін есепке алады.

Элементтің жағдайың қалыпты заң бойынша энтропияның үлестірілген жағдайындағы мәнін табамыз:

Элементтің жағдайы ішкі интервалда а £ х £ b  бар болуының бірқалыпты заңы бойынша үлестірілген энтропияның мәнін табамыз, 

Р(х) =

 

Бірқалыпты дисперсияның таралуы  , сол себепті   b-a = 2.  Осыны есепке ала отырып, мынаны жазамыз

Нн(х) = Нр(х) шартын пайдалана отырып, хабарламаларды бір бірімен бірқалыпты және қалыпты ықтималдылық таралулары бойынша салыстыра отырып, мынаны аламыз 

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

 

6 мысал: Ықтималдылық тығыздығының экспоненциальды заңы бойынша таратылған үздіксіз кездейсоқ шаманың энтропиясын анықтаймыз:

 

р(х) =

7 мысал: Ықтималдылық тығыздығы заңы бойынша таратылған кездейсоқ шаманың энтропиясын табамыз:

 

р(х) =

 

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

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

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

 ,

мұндағы Dx = 1 Ом, а , ондағы sг2 - резисторда 1Ом қарсылық етуімен белгіленетін күштілігімен сипатталатын дисперсия.

Бірқалыпты тарату үшін:

Нр(х) =

Бірқалыпты таратудың дисперсиясы

Осыдан

 

Сол себепті, тығыздықтың қалыпты таратуы бойынша шу қайнар көзін таңдаған жөн, себебі анықталмаған байланыс каналына енгізілген күштілігін 42%-ға жеңіп алуға болады.