Ақпараттар және кодтау теориясы

жүктеу 1,27 Mb.

бет	3/28
Дата	04.03.2023
өлшемі	1,27 Mb.
	#41586

1 2 3 4 5 6 7 8 9 ... 28

А параттар ж не кодтау теориясы

Дәріс №3 Энтропия түсінігі. Энтропия белгісіздік өлшемі ретінде. Энтропияның қасиеттері

Қорытынды:
1. Ақпараттың сандық бағасы бар.
2. Ақпарат саны мен осы алфавиттен тұратын комбинациялар саны арасындағы байланыс логарифмдік болып табылады.
3. Ақпарат санының жалпы қабылданған бірлігі екілік.
Бұл екі мүмкін таңбаның біреуін таңдағанда және битке тең болады.
4. Ақпараттың мөлшері жағдайлардың санына байланысты емес (әрине, оған байланысты), бірақ берілген факт туралы белгісіздікті жою арқылы анықталады.
5. Ақпараттың мөлшері бастапқы алфавитке қатысты анықталады және оны беру әдісіне және екінші алфавиттегі хабарлама ұзындығына байланысты емес.
6. Ақпарат көлемі екінші алфавитке қатысты анықталады және екінші алфавиттегі хабарламаның орташа ұзындығының хабарлама санына көбейтіндісіне тең.
7. Ақпараттың мөлшері сол ақпараттың Өлшем бірліктеріндегі көлемінен аспауы керек.
8. Ақпарат - бұл бір хабарлама немесе олардың жиынтығы, олар келгенге дейін бар белгісіздікті жояды.
9. Бір әріптің пайда болуының энтропиясын анықтау мүмкін емес, өйткені энтропия тұтастай сипаттайды және математикалық күту - log pi.
Сондықтан хабарлама көзінің шығуындағы кодтық сөздердің пайда болуына қатысты "энтропия" ұғымымен жұмыс істеу хабарлама көзінің кодтық шығуының белгісіздігі көздің энтропиясына тең деген мағынада мүмкін.

Дәріс №3 Энтропия түсінігі. Энтропия белгісіздік өлшемі ретінде. Энтропияның қасиеттері

Кездейсоқ оқиғалардың сипаттамасына екінші жағынан сәл жақындайық. Оқиғаның кездейсоқ болуы оның басталуына толық сенімділіктің жоқтығын білдіреді, бұл өз кезегінде осы оқиғаға байланысты тәжірибелердің нәтижелерінде белгісіздік тудырады. Әрине, белгісіздік деңгейі әртүрлі жағдайлар үшін әр түрлі. Мысалы, егер тәжірибе университеттің күндізгі бөлімінің кездейсоқ таңдалған 1-курс студентінің жасын анықтаудан тұрса, онда үлкен сеніммен ол 30 жылдан аз болады деп айтуға болады. Күндізгі бөлімде 35 жасқа дейінгі адамдар оқи алады, бірақ көбінесе жақын арадағы бірнеше мектеп түлектері күндізгі бөлімде оқиды. Егер ерікті түрде таңдалған оқушының Жасы 20 жастан аз болатындығы тексерілсе, сенімділік әлдеқайда аз болады. Тәжірибе үшін әр түрлі тәжірибелердің белгісіздігін сандық бағалау мүмкіндігі болуы керек. Осындай сандық белгісіздік өлшемін енгізуге тырысайық.

Тәжірибе n ықтимал нәтижелерге тең болатын қарапайым жағдайдан бастайық. Әлбетте, олардың әрқайсысының белгісіздігі n-ге байланысты, яғни белгісіздік f (n) - ге тең.
Бұл функцияның кейбір қасиеттерін көрсетуге болады:

1. f (1) = 0, өйткені n = 1-де тәжірибенің нәтижесі кездейсоқ емес, сондықтан белгісіздік жоқ;

2. f (n) n өсуімен артады, өйткені Мүмкін болатын нәтижелердің көптігіне байланысты тәжірибе нәтижесін болжау өте қиын болады.
f (n) функциясының айқын түрін анықтау үшін X және Y екі тәуелсіз тәжірибені қарастырыңыз, олардың нәтижелері бірдей, сәйкесінше n_X және n_Y. X және Y эксперименттерін бір уақытта орындаудан тұратын күрделі z тәжірибесін қарастырыңыз, Z тәжірибесінің мүмкін нәтижелерінің Саны n_yn_X -ге тең, және олардың барлығы бірдей. Мұндай тәжірибенің нәтижесінің белгісіздігі X тәжірибесінің белгісіздігінен үлкен болатыны анық, өйткені оған y белгісіздігі қосылады. z белгісіздігінің өлшемі X және Y тәжірибелерінің белгісіздіктерінің қосындысына тең, яғни белгісіздік аддитивті болады:
. (3.1)
Енді f(n) функциясының айқын көрінісі (1) және (2) қасиеттерін және (1) қатынасын қанағаттандыру үшін қандай болуы мүмкін екендігі туралы ойлана аласыз. Мұндай қасиеттер жиынтығы log(n) функциясымен қанағаттандырылатындығын көруге болады, сонымен қатар бұл функциялардың барлық мүмкін кластарының бірі екенін көрсетуге болады. Осылайша: N тең нәтижелермен тәжірибенің белгісіздігін өлшеу үшін log(n) санын қабылдауға болады.
Бұл жағдайда Логарифмнің негізін таңдау маңызды емес, өйткені Логарифмнің бір негізінен екіншісіне ауысудың белгілі формуласына байланысты

или log_bn = log_balog_an , (3.2)
басқа негізге көшу (2) өрнектің екі бөлігі үшін бірдей тұрақты факторды енгізуден тұрады , бұл белгісіздік өлшемінің масштабының өзгеруіне (яғни бірлік мөлшеріне) тең. Бұл болғандықтан, біз үшін ыңғайлы Логарифм негізін таңдауға мүмкіндігіміз бар (кейбір қосымша себептермен). Мұндай ыңғайлы негіз 2 болып табылады, өйткені бұл жағдайда тәжірибедегі белгісіздік өлшем бірлігі ретінде қабылданады, мысалы, ақиқат (шын) және жалған (жалған) деп атауға болатын және осындай оқиғаларды талдау үшін Математикалық логика аппаратын қолдануға болатын екі мүмкін нәтиже бар.
Тәжірибенің екі мүмкін нәтижесіндегі белгісіздікті өлшеу бірлігі бит деп аталады. (Бит атауы ағылшын тіліндегі binary digit сөзінен шыққан, ол сөзбе-сөз "екілік бит" немесе "екілік бірлік"дегенді білдіреді.)
Осылайша, біз n тең нәтиже беретін тәжірибенің белгісіздігін сипаттайтын функцияның нақты түрін орнаттық:

. (3.3)

Формулалар және негізінде әр жеке нәтиженің жалпы нәтижеге әкелетін белгісіздігін табу оңай. n нәтиже бар және олардың ықтималдылықтары бірдей, сондықтан эквивалентті және жалпы белгісіздік log₂n болғандықтан, белгісіздік аддитивтілігінің қасиетінен бір нәтижемен енгізілген белгісіздік пайда болады

. (3.4)
мұндағы – жеке нәтижелердің кез-келгенінің ықтималдығы.
Осылайша, тең мүмкін нәтижелердің әрқайсысы енгізген белгісіздік (оны Н арқылы белгілеңіз) тең:
. (3.5)

Енді (5) формуланы эксперименттердің нәтижелері бірдей болмайтын жағдайға жалпылауға тырысайық, мысалы, p(x₁) және p(x₂). Сонда:

и

.

Бұл өрнекті n тең емес нәтижелермен қорытындылай келе, біз аламыз:

. (3.6)

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

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

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

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

H = 0 тек болғанда ғана. Алайда, сонымен бірге - ден барлық басқа яғни нәтижелердің бірі сенімді болған кезде жағдай жүзеге асырылады (содан кейін оқиға кездейсоқ болмайды). Барлық басқа жағдайларда Н > 0 екені анық.
Белгісіздік аддитивтілігінен энтропия белгісіздік өлшемі ретінде аддитивтілікке ие болуы керек, яғни X және Y тәуелсіз екі тәжірибе үшін

, (3.7)
яғни бірнеше тәуелсіз тәжірибелерден тұратын күрделі тәжірибенің энтропиясы жеке тәжірибелердің энтропияларының қосындысына тең.

Дәлелдеме

Ақпарат алу процесін байланыс арнасы арқылы сигнал қабылдау нәтижесінде хабарлама қай көзден жіберілгені туралы сұрақтағы белгісіздіктің өзгеруі ретінде түсіндіруге болады. Ресми түрде бұл модельді келесідей ұсынуға болады. Өзара байланысты екі жиын болсын:

1. N көздерінің {xi}жиынтығы, олардың априорлық ықтималдығы p(xi).
2. М көздерінің {y_j} жиынтығы Априорлы ықтималдығы p(y_j) және шартты ықтималдығы p (xi | yj).
Атрибутты бақылаудың априорлық ықтималдығы – бұл бастапқы жиынтықтан ақпарат көздерін (объектілерді) ұсынған кезде оны бақылаудың орташа ықтималдығы, ал шартты ықтималдық-олардың белгілі бір түрін ұсынған кезде оны байқау ықтималдығы.
Ақпарат алғанға дейін жағдай оның қай көзден бағытталатыны, яғни априорлық энтропияның белгісіздігімен сипатталады:
. (3.8)

Көптеген көздер мен олар туралы хабарламалар ешқандай байланысты емес (олар тәуелсіз оқиғалар), яғни олар кездейсоқ түрде байланысты. Бұл екі жиынның оқиғалары бір-бірінен тәуелсіз екенін білдіреді. Мысалы, оқиғаның пайда болу мүмкіндігі бар (xi, yj), яғни егер хабарламада y_j белгісі болса, онда бұл x_i көзінен алынған хабарлама:

. (3.9)

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

(3.10)

(3.10) формуласына ықтималдылыққа арналған (3.8) өрнегін қойсақ:

(3.11)
Мұнда энтропияның классикалық анықтамасы (6) қолданылады және ықтималдылықты қалыпқа келтіру шарты ескеріледі:
.

N нәтижелерінің бірдей саны бар екі тәжірибе болсын, бірақ бір жағдайда олар бірдей, ал екінші жағдайда олар мүмкін емес. Тәжірибе энтропиясының қатынасы қандай?

Белгілердің саны екінің дәрежесін білдірсін, , барлық таңбалар бірдей ықтималдылықта, , яғни барлық екілік сөздер ұзындығы N және . N таңбалары және еркін мәндері бар хабарламалар көзі үшін р (xi)

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

. (3.13)

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

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

. (3.14)
Тең жағдайда, ең үлкен энтропия тең мүмкін нәтижелермен тәжірибеге ие.
Басқаша айтқанда, барлық нәтижелер бірдей болатын тәжірибелерде энтропия максималды болады. Мұнда ұқсастық бар физикада қолданылатын энтропия ұғымымен. Энтропия ұғымын алғаш рет 1865 жылы неміс физигі Рудольф Клаусиус жүйеде стихиялық процестердің бағытын анықтайтын термодинамикалық жүйенің күйінің функциясы ретінде енгізді. Клаузиус термодинамиканың II-ші басталуын тұжырымдады. Атап айтқанда, ол тепе-теңдік күйіне сәйкес келетін жүйеде толық тәртіпсіздікпен энтропияның максимумына жететінін көрсетті. Басқаша айтқанда, физикада энтропия жүйеде бұзылыстың өлшемі болып табылады. Кейінірек (1872 жылы) Людвиг Больцман статистикалық теорияны дамыта отырып, жүйенің энтропиясын оның жағдайының ықтималдығымен байланыстырды, термодинамиканың II-ші басына статистикалық (ықтималдық) түсінік берді және, атап айтқанда, ықтималдық толығымен бұзылған (тепе-теңдік) жүйеде максималды болатындығын көрсетті, сонымен қатар энтропия мен термодинамикалық ықтималдық логарифмдік тәуелділікпен байланысты болды. Ақпарат теориясы мен статистикалық термодинамикадағы ұғымдар мен олардың арасындағы қатынастардың ұқсастығы, кейінірек белгілі болғандай, терең мағынаға ие.
Энтропия ұғымы практикалық есептерді шешуге не береді? Олардың біреуін қарастырайық.

Есеп. Екі қорап болсын, олардың әрқайсысында 12 шар бар. Біріншісінде-3 ақ, 3 қара және 6 қызыл; екіншісінде - әр түсті 4. Тәжірибелер әр қораптан бір допты шығарудан тұрады. Осы тәжірибелердің белгісіздігі туралы не айтуға болады?

Шешімі. (3.6) сәйкес біз екі тәжірибенің энтропиясын табамыз:

.
.

, екінші тәжірибеде нәтиженің белгісіздігі жоғары, бұл (3.12) формуланың әділдігін көрсетеді.

жүктеу 1,27 Mb.

Достарыңызбен бөлісу:

1 2 3 4 5 6 7 8 9 ... 28