Кіріспе
Стохастикалық дерек көзінің шығысын анықтау үшін қажетті күтілетін ақпарат мөлшері. Ақпарат теориясында, кездейсоқ айнымалының энтропиясы – айнымалының мүмкін нәтижелеріне тән "ақпарат", "көңіл қоздыру" немесе "белгісіздіктің" орташа деңгейі. Дискретті кездейсоқ айнымалы , алфавиттегі мәндерді қабылдайды және бөлінімі бойынша берілгенде, энтропиясы – айнымалының мүмкін мәндері бойынша қосындыны білдіретін келесідей анықталады:
In information theory, the entropy of a random variable is the average level of "information", "surprise", or "uncertainty" inherent to the variable's possible outcomes. Given a discrete random variable , which takes values in the alphabet and is distributed according to , the entropy is
where denotes the sum over the variable's possible values. The choice of base for , the logarithm, varies for different applications. Base 2 gives the unit of bits (or "shannons"), while base e gives "natural units" nat, and base 10 gives units of "dits", "bans", or "hartleys". An equivalent definition of entropy is the expected value of the self information of a variable. The concept of information entropy was introduced by Claude Shannon in his 1948 paper "A Mathematical Theory of Communication", and is also referred to as Shannon entropy. Shannon's theory defines a data communication system composed of three elements: a source of data, a communication channel, and a receiver. The "fundamental problem of communication" – as expressed by Shannon – is for the receiver to be able to identify what data was generated by the source, based on the signal it receives through the channel. In fact, log is the only function that satisfies а specific set of conditions defined in section
Hence, we can define the information, or surprisal, of an event by
or equivalently,
Entropy measures the expected (i. e., average) amount of information conveyed by identifying the outcome of a random trial. This implies that rolling a die has higher entropy than tossing a coin because each outcome of a die toss has smaller probability than each outcome of a coin toss
Consider a coin with probability p of landing on heads and probability 1 − p of landing on tails. The maximum surprise is when , for which one outcome is not expected over the other. In this case a coin flip has an entropy of one bit. (Similarly, one trit with equiprobable values contains (about 1.58496) bits of information because it can have one of three values.) The minimum surprise is when or , when the event outcome is known ahead of time, and the entropy is zero bits. When the entropy is zero bits, this is sometimes referred to as unity, where there is no uncertainty at all – no freedom of choice – no information. Other values of p give entropies between zero and one bits.
мұнда айнымалының мүмкін мәндері бойынша қосындыны білдіреді. Логарифмнің негізін таңдау әртүрлі қолданыстар үшін өзгеше болуы мүмкін. 2-ге негізделген логарифм биттерді (немесе "шаннон") береді, ал e-ге негізделген логарифм "табиғи бірліктер" – натты, ал 10-ға негізделген логарифм "дит", "бан" немесе "хартли" бірліктерін береді. Энтропияның балама анықтамасы – айнымалының өзіндік ақпаратының күтілетін мәні. Ақпарат энтропиясы тұжырымын Клод Шеннон 1948 жылғы "Коммуникацияның математикалық теориясы" атты жұмысында енгізді, және ол Шеннон энтропиясы деп те аталады. Шеннонның теориясы деректерді жеткізу жүйесін үш элементтен тұратын ретінде анықтайды: дерек көзі, коммуникация арнасы және қабылдағыш. Шеннонның айтуынша, "коммуникацияның негізгі мәселесі" – қабылдағышқа арна арқылы алынған сигналға сүйене отырып, дерек көзінен қандай деректер туындағанын анықтау. Шындығында, логарифм – бөлімде көрсетілген нақты шарттар жиынтығын қанағаттандыратын жалғыз функция. Сондықтан, оқиғаның ақпаратын немесе көңіл қоздыруын, немесе эквивалентті түрде, кездейсоқ тәжірибенің нәтижесін анықтау арқылы берілген ақпараттың күтілетін (яғни орташа) мөлшері ретінде өлшеуге болады. Бұл, мысалы, алты жақты ойыншық текше лақтырудың энтропиясы монета лақтырудан жоғары екенін білдіреді, өйткені ойыншық текшенің әрбір нәтижесі монета лақтырудың әрбір нәтижесіне қарағанда аз ықтималдыққа ие. p ықтималдығымен сыртын көрсетуге және 1 − p ықтималдығымен сыртын көрсетпеуге болатын монетаны қарастырайық. Ең жоғары көңіл қоздыру жағдайы – , яғни бір нәтиже екіншісінен күтілмейтін жағдай. Бұл жағдайда монета лақтырудың энтропиясы бір битке тең. (Сонымен қатар, тең ықтималды мәндері бар бір трит үш мәннің біреуін қабылдай алатындықтан, (шамамен 1,58496) бит ақпаратты қамтиды.) Ең төменгі көңіл қоздыру жағдайы – немесе , яғни оқиғаның нәтижесі алдын ала белгілі болғанда, және энтропия нөл битке тең. Энтропия нөл бит болған кезде, бұл кейде бірлік деп аталады, онда мүлдем белгісіздік жоқ – таңдау еркіндігі жоқ – ақпарат жоқ. p-нің басқа мәндері нөл мен бір бит арасындағы энтропияны береді.
In information theory, the entropy of a random variable is the average level of "information", "surprise", or "uncertainty" inherent to the variable's possible outcomes. Given a discrete random variable , which takes values in the alphabet and is distributed according to , the entropy is
where denotes the sum over the variable's possible values. The choice of base for , the logarithm, varies for different applications. Base 2 gives the unit of bits (or "shannons"), while base e gives "natural units" nat, and base 10 gives units of "dits", "bans", or "hartleys". An equivalent definition of entropy is the expected value of the self information of a variable. The concept of information entropy was introduced by Claude Shannon in his 1948 paper "A Mathematical Theory of Communication", and is also referred to as Shannon entropy. Shannon's theory defines a data communication system composed of three elements: a source of data, a communication channel, and a receiver. The "fundamental problem of communication" – as expressed by Shannon – is for the receiver to be able to identify what data was generated by the source, based on the signal it receives through the channel. In fact, log is the only function that satisfies а specific set of conditions defined in section
Hence, we can define the information, or surprisal, of an event by
or equivalently,
Entropy measures the expected (i. e., average) amount of information conveyed by identifying the outcome of a random trial. This implies that rolling a die has higher entropy than tossing a coin because each outcome of a die toss has smaller probability than each outcome of a coin toss
Consider a coin with probability p of landing on heads and probability 1 − p of landing on tails. The maximum surprise is when , for which one outcome is not expected over the other. In this case a coin flip has an entropy of one bit. (Similarly, one trit with equiprobable values contains (about 1.58496) bits of information because it can have one of three values.) The minimum surprise is when or , when the event outcome is known ahead of time, and the entropy is zero bits. When the entropy is zero bits, this is sometimes referred to as unity, where there is no uncertainty at all – no freedom of choice – no information. Other values of p give entropies between zero and one bits.
Мысал
Ақпарат теориясы хабарды жеткізу үшін қажетті ақпараттың ең аз мөлшерін есептеуге пайдалы, мысалы, деректерді сығымдауда. Мысалы, 'A', 'B', 'C' және 'D' 4 таңбадан тұратын тізбектерді екілік арна арқылы беруді қарастырайық. Егер барлық 4 әріп бірдей ықтимал болса (25%), әр әріпті кодтау үшін екі биттен артық пайдалануға болмайды. 'A' '00', 'B' '01', 'C' '10', ал 'D' '11' деп кодталуы мүмкін. Дегенмен, егер әр әріптің ықтималдығы тең болмаса, мысалы, 'A' 70% ықтималдықпен, 'B' 26% ықтималдықпен, ал 'C' және 'D' әрқайсысы 2% ықтималдықпен пайда болса, өзгермелі ұзындықтағы кодтарды тағайындауға болады. Бұл жағдайда 'A' '0', 'B' '10', 'C' '110', 'D' '111' деп кодталады. Осы бейнелеуде 70% жағдайда тек бір бит жіберу қажет, 26% жағдайда екі бит, ал 4% жағдайда 3 бит қажет болады. Энтропия төмен болғандықтан, орташа есеппен 2 биттен аз талап етіледі (мүмкіндіктердің 96% -ын 'A' және 'B' әріптері құрайтындықтан). Ықтималдықтардың салмақталған логарифмдерінің қосындысын есептеу осы әсерді өлшейді және түсіндіреді. Ағылшын мәтіні, таңбалар тізбегі ретінде қарастырылғанда, өте төмен энтропияға ие, яғни ол өте болжамды. Мысалы, 'e' әрпі 'z' әрпінен әлдеқайда жиі кездесетініне, 'qu' комбинациясы 'q' әрпімен басталатын кез келген басқа комбинациядан әлдеқайда жиі кездесетініне және 'th' комбинациясы 'z', 'q' немесе 'qu' комбинацияларынан жиі кездесетініне сенімді болуға болады. Бірінші бірнеше әріптен кейін сөздің қалған бөлігін көбінесе болжауға болады. Ағылшын мәтінінде хабардың әр таңбасына 0,6 мен 1,3 бит аралығында энтропия тән.
Басқа сипаттама
Энтропияны сипаттаудың тағы бір жолы келесі қасиеттерді пайдаланады. Біз үздіксіздік және деп белгілейміз: H үздіксіз болуы керек, сондықтан ықтималдықтардың мәнін өте аз өзгерту энтропияны да аз ғана өзгертуі тиіс. Симметрия: Егер нәтижелер xi ретімен ауыстырылса, H өзгермеуі керек. Яғни, кез келген перестановка үшін . Максималдық: Барлық нәтижелер бірдей ықтимал болғанда максималды болуы керек, яғни . Нәтижелер санының артуы: Тең ықтималды оқиғалар үшін энтропия нәтижелер санының артуымен бірге өсуі керек, яғни . Қосымшалық: Егер n біртектес таратылған элементтер бар болса және олар b1, …, bk элементтері бар k бөлікке (ішкі жүйелерге) бөлінген болса, онда бүкіл жиынның энтропиясы бөліктер жүйесінің энтропиясы мен әр бөліктің жеке энтропиясының қосындысына тең болуы керек, әрқайсысы сол бөлікте болу ықтималдығымен салмақталған.
Continuity: H should be continuous, so that changing the values of the probabilities by a very small amount should only change the entropy by a small amount. Symmetry: H should be unchanged if the outcomes xi are re ordered. That is, for any permutation of Maximum: should be maximal if all the outcomes are equally likely i. e. Increasing number of outcomes: for equiprobable events, the entropy should increase with the number of outcomes i. e.
Additivity: given an ensemble of n uniformly distributed elements that are partitioned into k boxes (sub systems) with b1, , bk elements each, the entropy of the whole ensemble should be equal to the sum of the entropy of the system of boxes and the individual entropies of the boxes, each weighted with the probability of being in that particular box.
Криптографиядағы энтропияның шектеулері
Криптоанализде энтропия көбінесе криптографиялық кілттің болжау мүмкін еместігін өлшеу үшін қолданылады, бірақ оның нақты белгісіздігі өлшенбейді. Мысалы, біркелкі және кездейсоқ түрде жасалған 128 биттік кілт 128 бит энтропияға ие. Бұндай кілтті күш қолдану арқылы бұзу үшін (орташа есеп бойынша) сол 128 рет ұсыныс қажет болады. Энтропия, егер мүмкін болатын кілттер біркелкі таңдалмаса, қажетті ұсыныстар санын анықтай алмайды. Оның орнына, күш қолдану шабуылы үшін қажетті күшті өлшеу үшін "болжау" деп аталатын өлшемді пайдалануға болады. Криптографияда біркелкі емес таралымдар да проблема тудыруы мүмкін. Мысалы, 1,000,000 цифрлы екілік бір реттік жазбада (exclusive OR) егер жазбада 1,000,000 бит энтропия болса, ол өте жақсы. Егер жазбада 999,999 бит энтропия болса және ол біркелкі таратылса (жазбаның әрбір жеке биті 0.999999 бит энтропияға ие болса), жақсы қауіпсіздік қамтамасыз етілуі мүмкін. Бірақ егер жазбада 999,999 бит энтропия болса, онда бірінші бит бекітілген болса, ал қалған 999,999 биті толығымен кездейсоқ болса, шифрланған мәтіннің бірінші биті мүлде шифрланбайды.