Ця стаття має кілька недоліків. Будь ласка, допоможіть удосконалити її або обговоріть ці проблеми на .
|
Інформаці́йна ентропі́я (англ. information entropy) — це усереднена швидкість, із якою продукує інформацію стохастичне джерело даних.
Мірою інформаційної ентропії, пов'язаною з кожним можливим значенням даних, є від'ємний логарифм функції маси ймовірності для цього значення: . Таким чином, коли джерело даних має менш імовірне значення (наприклад, коли стається низькоймовірна подія), то ця подія несе більше «інформації» («неочікуваності»), ніж коли джерело даних має більш імовірне значення. Визначена таким чином кількість інформації, що передається кожною подією, стає випадковою змінною, чиє математичне сподівання є інформаційною ентропією. Взагалі, ентропію позначають безлад або невизначеність, і визначення ентропії, що застосовують в теорії інформації, є прямим аналогом визначення, що застосовують у статистичній термодинаміці. Поняття інформаційної ентропії було введено Клодом Шенноном у його праці 1948 року «Математична теорія зв'язку».
Базова модель системи передавання даних складається з трьох елементів: джерела даних, каналу зв'язку та приймача, і, за виразом Шеннона, «фундаментальною задачею зв'язку» є те, щоби отримувач був здатен встановлювати, які дані було породжено джерелом, на основі сигналу, що він отримує каналом. Ентропія забезпечує абсолютну межу найкоротшої можливої усередненої довжини безвтратного стиснювального кодування даних, продукованих джерелом, і якщо ентропія джерела є меншою за пропускну спроможність каналу зв'язку, то дані, породжувані цим джерелом, можливо надійно передавати приймачеві (принаймні теоретично, можливо, нехтуючи деякими практичними міркуваннями, такими як складність системи, потрібної для передавання даних, або кількості часу, що це передавання цих даних може забирати).
Інформаційну ентропію зазвичай вимірюють в бітах (що також називають «шеннонами», англ. bit, shannon), або іноді в «натуральних одиницях» (натах, англ. nat), або в десяткових цифрах (що називають «дитами», «банами» або «гартлі»). Одиниця вимірювання залежить від основи логарифма, що використовують для визначення ентропії.
Логарифм розподілу ймовірності є корисним як міра ентропії тому, що для незалежних джерел він є адитивним. Наприклад, ентропія підкидання справедливої монети складає 1 біт, а ентропією m підкидань є m біт. У простому поданні, для представлення величини, що може набувати одного з n значень, потрібно log2(n) бітів, якщо n є степенем числа 2. Якщо ці значення є однаково ймовірними, то ентропія (в бітах) дорівнює цьому числу. Якщо ж трапляння одного з цих значень є ймовірнішим за інші, то спостереження трапляння цього значення є менш інформативним, ніж якби трапився не такий звичайний результат. І навпаки, рідкісніші події при їхньому спостереженні надають більше інформації. Оскільки спостереження менш імовірних подій трапляється рідше, в підсумку виходить, що ентропія (при розгляданні її як усередненої інформації), отримувана від нерівномірно розподілених даних, є завжди меншою або рівною до log2(n). Якщо вихід є незмінним, то ентропія дорівнює нулеві. Коли розподіл імовірності джерела даних є відомим, ентропія виражає ці міркування кількісно. Зміст спостережуваних подій (зміст повідомлень) у визначенні ентропії значення не має. Ентропія враховує лише ймовірність спостереження певної події, тому інформація, яку вона включає, є інформацією про розподіл ймовірності, що лежить в основі, а не про зміст самих подій.
Введення
Основною ідеєю теорії інформації є те, що чим більше хтось знає про предмет, то менше нової інформації про нього вони здатні отримати. Якщо подія є дуже ймовірною, то коли вона трапляється, в цьому немає нічого неочікуваного, і відтак вона привносить мало нової інформації. І навпаки, якщо подія була малоймовірною, то її трапляння є набагато інформативнішим. Таким чином, інформаційний вміст є висхідною функцією оберненої ймовірності події (1/p, де p є ймовірністю події). Тепер, якщо може трапитися більше подій, ентропія вимірює усереднений інформаційний вміст, який ви можете очікувати отримати, якщо дійсно трапляється одна з цих подій. З цього випливає, що викидання грального кубика має більше ентропії, ніж підкидання монети, оскільки кожен з результатів грального кубика має меншу ймовірність, ніж кожен з результатів монети.
Отже, ентропія — це міра непередбачуваності (англ. unpredictability) стану, або, рівнозначно, його усередненого інформаційного вмісту (англ. average information content). Щоби отримати інтуїтивне розуміння цих термінів, розгляньмо приклад політичного опитування. Як правило, такі опитування відбуваються тому, що їхні результати не є заздалегідь відомими. Іншими словами, результати опитування є відносно непередбачуваними, і фактичне здійснення опитування та з'ясовування результатів дає деяку нову інформацію; це просто різні способи сказати, що апріорна ентропія результатів опитування є високою. Тепер розгляньмо випадок, коли таке ж опитування проводиться вдруге незабаром після першого опитування. Оскільки результати першого опитування вже є відомими, підсумки другого опитування можна передбачити добре, і ці результати не повинні містити багато нової інформації; в цьому випадку апріорна ентропія результатів другого опитування є низькою по відношенню до апріорної ентропії першого.
Тепер розгляньмо приклад з підкиданням монети. Якщо ймовірність випадання аверсу така ж, як і ймовірність випадання реверсу, то ентропія підкидання монети є настільки високою, наскільки це можливо. Причиною цього є те, що немає жодного способу передбачити результат підкидання монети заздалегідь — якщо нам треба було би обирати, то найкраще, що ми могли би зробити, це передбачити, що монета випаде аверсом догори, і цей прогноз був би правильним з імовірністю 1/2. Таке підкидання монети має один біт ентропії, оскільки є два можливі результати, які трапляються з однаковою ймовірністю, і з'ясування фактичного результату містить один біт інформації. На противагу до цього, підкидання монети, яка має два аверси й жодного реверсу, має нульову ентропію, оскільки монета завжди випадатиме аверсом, і результат може бути передбачено цілком. Аналогічно, бінарна подія з рівноймовірними результатами має ентропію Шеннона біт. Подібно до цього, один трит із рівноймовірними значеннями містить (близько 1.58496) бітів інформації, оскільки він може мати одне з трьох значень.
Англомовний текст, якщо розглядати його як стрічку символів, має досить низький рівень ентропії, тобто, він є доволі передбачуваним. Навіть якщо ми не знаємо точно, що буде далі, ми можемо бути доволі впевненими, що, наприклад, «e» там буде набагато поширенішою за «z», що поєднання «qu» зустрічатиметься набагато частіше за будь-які інші поєднання, які містять «q», і що поєднання «th» буде набагато поширенішим за «z», «q» або «qu». Після перших кількох літер часто можна вгадати решту слова. Англійський текст має між 0.6 та 1.3 біта ентропії на символ повідомлення.
Якщо схема стиснення є вільною від втрат, — тобто, завжди можна відтворити повне первинне повідомлення шляхом розтискання, — то стиснене повідомлення має такий самий обсяг інформації, як і первинне, але переданий меншою кількістю символів. Тобто, воно має більше інформації, або вищу ентропію, на один символ. Це означає, що стиснене повідомлення має меншу надмірність. Грубо кажучи, [en] стверджує, що схема стиснення без втрат в середньому не може стиснути повідомлення так, щоби воно мало більше одного біту інформації на біт повідомлення, але що будь-яке значення менше одного біту інформації на біт повідомлення може бути досягнуто шляхом застосування відповідної схеми кодування. Ентропія повідомлення на біт, помножена на довжину цього повідомлення, є мірою того, наскільки багато інформації в цілому містить повідомлення.
Для наочності уявіть, що ми хочемо передати послідовність, до складу якої входять 4 символи, «А», «Б», «В» і «Г». Таким чином, повідомленням для передавання може бути «АБАГГВАБ». Теорія інформації пропонує спосіб обчислення найменшої можливої кількості інформації, яка передасть це. Якщо всі 4 літери є рівноймовірними (25 %), ми не можемо зробити нічого кращого (над двійковим каналом), аніж кодувати кожну літеру 2 бітами (у двійковому вигляді): «А» може бути кодовано як «00», «Б» — як «01», «В» — як «10», а «Г» — як «11». Тепер припустімо, що «А» трапляється з імовірністю 70 %, «Б» — 26 %, а «В» та «Г» — по 2 % кожна. Ми могли би призначити коди змінної довжини, так, що отримання «1» казало би нам дивитися ще один біт, якщо тільки ми не отримали вже перед цим 2 послідовні біти одиниць. В цьому випадку «А» було би кодовано як «0» (один біт), «Б» — як «10», а «В» і «Г» як «110» і «111». Легко побачити, що протягом 70 % часу потрібно надсилати лише один біт, 26 % часу — два біти, і лише протягом 4 % від часу — 3 біти. Тоді в середньому необхідно менше за 2 біти, оскільки ентропія є нижчою (через високу поширеність «А» з наступною за нею «Б» — разом 96 % символів). Обчислення суми зважених за ймовірностями логарифмічних імовірностей вимірює та схоплює цей ефект.
Теорема Шеннона також означає, що жодна схема стиснення без втрат не може скорочувати всі повідомлення. Якщо якісь повідомлення виходять коротшими, хоча б одне повинне вийти довшим в силу принципу Діріхле. В практичному застосуванні це зазвичай не є проблемою, оскільки нас, як правило, цікавить стиснення лише певних типів повідомлень, наприклад, документів англійською мовою на противагу до тексту тарабарщиною, або цифрових фотографій, а не шуму, і не важливо, якщо алгоритм стиснення робить довшими малоймовірні або нецікаві послідовності.
Означення
Назвавши її на честь [en], Шеннон означив ентропію Η (грецька літера ета) дискретної випадкової величини з можливими значеннями та функцією маси ймовірності як
Тут є оператором математичного сподівання (англ. expectation), а I є кількістю інформації X. I(X) і сама є випадковою величиною.
Ентропію може бути записано в явному вигляді як
де b є [en]логарифма, який застосовується. Звичними значеннями b є 2, число Ейлера е, та 10, а відповідними одиницями ентропії є біти для b = 2, нати для b = e, та бани для b = 10.
У випадку P(xi) = 0 для деякого i значення відповідного доданку 0 logb(0) приймають рівним 0, що відповідає границі
Можна також визначити умовну ентропію двох подій X та Y, які набувають значень xi та yj відповідно, як
де p(xi, yj) є ймовірністю того, що X = xi та Y = yj. Цю величину слід розуміти як ступінь довільності випадкової величини X при заданій події Y.
Приклад
Детальніші відомості з цієї теми ви можете знайти в статті [en] та [en].
Розгляньмо підкидання монети з відомими, але не обов'язково справедливими ймовірностями випадання аверсу чи реверсу; це можна змоделювати як [en].
Ентропія невідомого результату наступного підкидання монети є найбільшою, якщо монета є справедливою (тобто, якщо як аверси, так і реверси мають однакову ймовірність 1/2). Це є ситуацією максимальної невизначеності, оскільки в ній найскладніше передбачити результат наступного підкидання; результат кожного підкидання монети подає один повний біт інформації. Це є тому, що
Проте, якщо ми знаємо, що монета не є справедливою, а випадає аверсом чи реверсом з імовірностями p та q, де p ≠ q, то тоді невизначеності є менше. Кожного разу, як її підкидають, випадання однієї зі сторін є ймовірнішим, ніж випадання іншої. Зниження невизначеності отримує кількісну оцінку в вигляді меншої ентропії: в середньому кожне підкидання монети подає менше ніж один повний біт інформації. Наприклад, якщо p=0.7, то
Крайнім випадком є двоаверсова монета, яка ніколи не випадає реверсом, або двореверсова монета, яка ніколи не дає в результаті аверс. Тут немає ніякої невизначеності. Ентропія дорівнює нулеві: кожне підкидання монети не подає жодної нової інформації, оскільки результати кожного підкидання монети завжди визначені.
Ентропію може бути нормалізовано шляхом ділення її на довжину інформації. Це співвідношення називається [en], воно є мірою хаотичності інформації.
Обґрунтування
Щоби зрозуміти сенс ∑ pi log(1/pi), спершу спробуймо визначити функцію інформації I з точки зору події i з імовірністю pi. Кількість інформації, отримувана через спостереження події i, випливає з шеннонового розв'язку фундаментальних властивостей інформації:
- I(p) є монотонно спадною в p — збільшення ймовірності події зменшує інформацію зі спостереження події, і навпаки.
- I(p) ≥ 0 — інформація є невід'ємною величиною.
- I(1) = 0 — події, які відбуваються завжди, не несуть інформації.
- I(p1p2) = I(p1) + I(p2) — інформація від незалежних подій є адитивною.
Остання властивість є ключовою. Вона стверджує, що спільна ймовірність незалежних джерел інформації несе стільки ж інформації, скільки й ці дві окремі події по одній. Зокрема, якщо перша подія може видавати один з n [en] результатів, а інша має один із m рівноймовірних результатів, то існує mn можливих результатів спільної події. Це означає, що якщо для кодування першого значення потрібно log2(n) біт, а для кодування другого — log2(m), то для кодування обох потрібно log2(mn) = log2(m) + log2(n). Шеннон виявив, що правильним вибором функції для кількісної оцінки інформації, яка зберігала би цю адитивність, є логарифмічна, тобто
нехай є інформаційною функцією, що є двічі неперервно диференційовною, тоді
Це диференціальне рівняння веде до розв'язку для будь-якого . Умова 2 веде до , а надто, може обиратися з вигляду , де , що рівнозначне обиранню конкретної . Різні одиниці інформації (біти для двійкового логарифма log2, нати для натурального логарифма ln, бани для десяткового логарифма log10 і так далі) є лише сталим домноженням одна одної. Наприклад, у випадку підкидання справедливої монети аверс дає log2(2) = 1 біт інформації, що становить приблизно 0.693 нат, або 0.301 десяткових цифр. В силу адитивності, n підкидань дають n біт інформації, що становить приблизно 0.693n нат, або 0.301n десяткових цифр.
Якщо існує розподіл, в якому подія i може траплятися з імовірністю pi, з нього було взято N проб, і результат i трапився ni = N pi разів, то загальною кількістю інформації, яку ми отримали, є
- .
Отже, усередненою кількістю інформації, яку ми отримуємо на подію, є
Аспекти
Відношення до термодинамічної ентропії
Детальніші відомості з цієї теми ви можете знайти в статті [en].
Натхнення прийняти слово ентропія в теорії інформації виникло від близької подібності між формулою Шеннона, і дуже схожими відомими формулами зі статистичної механіки.
У статистичній термодинаміці найзагальнішою формулою для термодинамічної ентропії S термодинамічної системи є ентропія Гіббса,
де kB є сталою Больцмана, а pi є ймовірністю [en]. Ентропію Гіббса було визначено Віллардом Гіббсом 1878 року після ранішої праці Больцмана (1872 року).
Ентропія Гіббса переноситься майже беззмінною до світу квантової фізики, даючи ентропію фон Неймана, введену Джоном фон Нейманом 1927 року,
де ρ є матрицею густини квантової механічної системи, а Tr є слідом.
На побутовому практичному рівні зв'язок між інформаційною та термодинамічною ентропією очевидним не є. Фізики та хіміки схильні більше цікавитися змінами ентропії при спонтанному розвитку системи від її первісних умов, у відповідності з другим законом термодинаміки, ніж незмінним розподілом імовірності. І, як вказує малість сталої Больцмана kB, зміни в S / kB навіть для невеликих кількостей речовин у хімічних та фізичних процесах являють собою обсяги ентропії, які є надзвичайно великими порівняно з чим завгодно в стисненні даних та обробці сигналів. Крім того, в класичній термодинаміці ентропія визначається в термінах макроскопічних вимірювань, і не робить жодних посилань на будь-який розподіл імовірності, що є головним у визначенні ентропії інформаційної.
Зв'язок між термодинамікою і тим, що зараз відомо як теорія інформації, було вперше зроблено Людвігом Больцманом, і виражено його [en]:
де S є термодинамічною ентропією окремого макростану (визначену термодинамічними параметрами, такими як температура, об'єм, енергія тощо), W є числом мікростанів (різних комбінацій частинок у різних енергетичних станах), які можуть дати даний макростан, а kB є сталою Больцмана. Передбачається, що кожен мікростан є однаково правдоподібним, так що ймовірністю заданого мікростану є pi = 1/W. При підставленні цих імовірностей до наведеного вище виразу для ентропії Гіббса (або, рівнозначно, ентропії Шеннона, помноженої на kB) в результаті виходить рівняння Больцмана. В термінах теорії інформації інформаційна ентропія системи є кількістю інформації, якої «бракує» для визначення мікростану при відомому макростані.
На думку [en] (1957 року), термодинамічну ентропію, як пояснюється статистичною механікою, слід розглядати як застосування теорії інформації Шеннона: термодинамічна ентропія інтерпретується як така, що є пропорційною до кількості додаткової інформації Шеннона, необхідної для визначення детального мікроскопічного стану системи, яка залишається не повідомленою описом виключно в термінах макроскопічних величин класичної термодинаміки, з коефіцієнтом пропорційності, який є просто сталою Больцмана. Наприклад, додавання теплоти до системи підвищує її термодинамічну ентропію, оскільки це збільшує число можливих мікроскопічних станів системи, які узгоджуються з вимірюваними значеннями його макроскопічних величин, роблячи таким чином будь-який повний опис стану довшим. (Див. статтю [en]). Демон Максвелла може (гіпотетично) знижувати термодинамічну ентропію системи з використанням інформації про стан окремих молекул, але, як показали [en] (з 1961 року) з колегами, щоби діяти, цей демон мусить сам підвищувати термодинамічну ентропію в цьому процесі, принаймні на кількість інформації Шеннона, яку він пропонує спочатку отримати й зберегти; і, таким чином, загальна термодинамічна ентропія не знижується (що розв'язує парадокс). Принцип Ландауера встановлює нижню межу кількості тепла, яке комп'ютер повинен генерувати для обробки заданого обсягу інформації, хоча сучасні комп'ютери є набагато менш ефективними.
Ентропія як кількість інфромації
Детальніші відомості з цієї теми ви можете знайти в статті [en].
Ентропія визначається в контексті ймовірнісної моделі. Незалежні підкидання справедливої монети мають ентропію по 1 біту на підкидання. Джерело, яке завжди породжує довгий рядок «Б», має ентропію 0, оскільки наступним символом завжди буде «Б».
Ентропійна швидкість джерела даних означає усереднене число бітів на символ, потрібне для його кодування. Експерименти Шеннона з передбаченням людьми показують швидкість інформації на символ англійською мовою між 0.6 і 1.3 біта;Алгоритм стиснення PPM може досягати рівня стиснення в 1.5 біти на символ англомовного тексту.
Зверніть увагу на наступні моменти з попереднього прикладу:
- Кількість ентропії не завжди є цілим числом бітів.
- Багато бітів даних можуть не нести інформації. Наприклад, структури даних часто зберігають інформацію надмірно, або мають ідентичні розділи, незалежно від інформації в структурі даних.
Шеннонівське визначення ентропії, при застосуванні до джерела інформації, може визначати мінімальну пропускну здатність каналу, необхідну для надійного передавання джерела у вигляді закодованих двійкових цифр (див. застереження нижче курсивом). Цю формулу може бути виведено шляхом обчислення математичного сподівання кількості інформації, яка міститься в одній цифрі з джерела інформації. Див. також теорему Шеннона — Гартлі.
Ентропія Шеннона вимірює інформацію, яка міститься в повідомленні, на противагу до тієї частини повідомлення, яка є визначеною (або передбачуваною). Приклади останнього включають надмірність у структурі мови та статистичні властивості, які стосуються частот трапляння пар, трійок тощо літер або слів. Див. ланцюги Маркова.
Ентропія як міра різноманітності
Ентропія є одним з декількох способів вимірювання різноманітності. Зокрема, ентропія Шеннона є логарифмом 1D, індексу істинної різноманітності з параметром, який дорівнює 1.
Стиснення даних
Ентропія ефективно обмежує продуктивність найсильнішого можливого стиснення без втрат, яке може бути реалізовано теоретично з допомогою [en], або практично із застосуванням кодування Хаффмана, Лемпеля — Зіва, або арифметичного кодування. Див. також колмогоровську складність. На практиці для захисту від помилок алгоритми стиснення навмисно включають деяку розумну надмірність у вигляді контрольних сум.
Світовий технологічний потенціал для зберігання та передавання інформації
Дослідження 2011 року в журналі «Science» оцінює світовий технологічний потенціал для зберігання та передавання оптимально стисненої інформації, нормалізований за найефективнішими алгоритмами стиснення, доступними в 2007 році, оцінюючи таким чином ентропію технологічно доступних джерел.
Тип інформації | 1986 | 2007 |
---|---|---|
Зберігання | 2.6 | 295 |
Широкомовлення | 432 | 1900 |
Телекомунікації | 0.281 | 65 |
Автори оцінюють технологічний потенціал людства у зберіганні інформації (повністю ентропійно стисненої) 1986 року, і знову 2007 року. Вони ділять інформацію на три категорії — зберігання інформації на носії, отримування інформації через мережі однобічного широкомовлення, та обмін інформацією через двобічні телекомунікаційні мережі.
Обмеження ентропії як кількості інформації
Існує ряд пов'язаних з ентропією понять, які певним чином здійснюють математичну кількісну оцінку обсягу інформації:
- власна інформація окремого повідомлення або символу, взятого із заданого розподілу ймовірності,
- ентропія заданого розподілу ймовірності повідомлень або символів, та
- ентропійна швидкість стохастичного процесу.
(Для конкретної послідовності повідомлень або символів, породженої заданим стохастичним процесом, також може бути визначено «швидкість власної інформації»: у випадку стаціонарного процесу вона завжди дорівнюватиме швидкості ентропії.) Для порівняння різних джерел інформації, або встановлення зв'язку між ними, використовуються й інші Кількості інформації.
Важливо не плутати наведені вище поняття. Яке з них мається на увазі, часто може бути зрозумілим лише з контексту. Наприклад, коли хтось говорить, що «ентропія» англійської мови становить близько 1 біта на символ, вони насправді моделюють англійську мову як стохастичний процес, і говорять про швидкість її ентропії. Шеннон і сам використовував цей термін таким чином.
Проте, якщо ми використовуємо дуже великі блоки, то оцінка посимвольної ентропійної швидкості може стати штучно заниженою. Це відбувається тому, що насправді розподіл ймовірності послідовності не є пізнаваним точно; це лише оцінка. Наприклад, припустімо, що розглядаються тексти всіх будь-коли опублікованих книг як послідовність, у якій кожен символ є текстом цілої книги. Якщо існує N опублікованих книг, і кожну книгу опубліковано лише одного разу, то оцінкою ймовірності кожної книги є 1/N, а ентропією (в бітах) є −log2(1/N) = log2(N). Як практичний код, це відповідає призначенню кожній книзі унікального ідентифікатора і використання його замість тексту книги будь-коли, коли потрібно послатися на цю книгу. Це надзвичайно корисно для розмов про книги, але не дуже корисно для характеризування кількості інформації окремих книг або мови в цілому: неможливо відтворити книгу з її ідентифікатора, не знаючи розподілу ймовірності, тобто повного тексту всіх книг. Ключова ідея полягає в тому, що повинна братися до уваги складність імовірнісної моделі. Колмогоровська складність являє собою теоретичне узагальнення цієї ідеї, яке дозволяє розглядати кількість інформації послідовності незалежно від конкретної ймовірнісної моделі; воно розглядає найкоротшу програму для універсального комп'ютера, яка виводить цю послідовність. Такою програмою є код, який досягає ентропійної швидкості послідовності для заданої моделі, плюс кодовий словник (тобто, ймовірнісна модель), але вона не може бути найкоротшою.
Наприклад, послідовністю Фібоначчі є 1, 1, 2, 3, 5, 8, 13, …. При розгляді цієї послідовності як повідомлення, а кожного числа як символу, існує майже стільки ж символів, скільки є символів у повідомленні, даючи ентропію близько log2(n). Таким чином, перші 128 символів послідовності Фібоначчі мають ентропію приблизно 7 біт/символ. Проте цю послідовність може бути виражено за допомогою формули [F(n) = F(n−1) + F(n−2) для n = 3, 4, 5, …, F(1) =1, F(2) = 1], і ця формула має значно нижчу ентропію, і застосовується до послідовності Фібоначчі будь-якої довжини.
Обмеження ентропії в криптографії
В криптоаналізі ентропію часто грубо використовують як міру непередбачуваності криптографічного ключа, хоча її справжня невизначеність є незмірною. Наприклад, 128-бітовий ключ, який породжено рівномірно випадково, має 128 біт ентропії. Він також вимагає (усереднено) спроб для зламу грубою силою. Проте, ентропія не відображає число потрібних спроб, якщо можливі ключі вибирають не рівномірно. Натомість, для вимірювання зусиль, необхідних для атаки грубою силою, можна використовувати міру, що називають здогадом (англ. guesswork).
Через нерівномірність розподілів, що застосовують в криптографії, можуть виникати й інші проблеми. Наприклад, розгляньмо 1 000 000-цифровий двійковий шифр Вернама із застосуванням виключного «або». Якщо цей шифр має 1 000 000 біт ентропії, це чудово. Якщо цей шифр має 999 999 біт ентропії, які розподілено рівномірно (коли кожен окремий біт шифру має 0.999999 біт ентропії), то він може пропонувати добру безпеку. Але якщо цей шифр має 999 999 біт ентропії, так, що перший біт є незмінним, а решта 999 999 бітів вибирають випадково, то перший біт шифрованого тексту не буде шифровано взагалі.
Дані як марковський процес
Звичний спосіб визначення ентропії для тексту ґрунтується на марковській моделі тексту. Для джерела нульового порядку (кожен символ обирається незалежно від останніх символів) двійковою ентропією є
де pi є ймовірністю i. Для [en] першого порядку (такого, в якому ймовірність вибору символу залежить лише від безпосередньо попереднього символу) ентропійною швидкістю є
- []
де i є станом (деякими попередніми символами), а є ймовірністю j за заданого попереднього символу i.
Для марковського джерела другого порядку ентропійною швидкістю є
b-арна ентропія
В загальному випадку b-арна ентропія джерела = (S, P) з первинною абеткою S = {a1, …, an} і дискретним розподілом ймовірності P = {p1, …, pn}, де pi є імовірністю ai (скажімо, pi = p(ai)), визначається як
Зауваження: b у «b-арній ентропії» є числом різних символів ідеальної абетки, яка використовується як стандартне мірило для вимірювання первинних абеток. В теорії інформації для абетки для кодування інформації є необхідними і достатніми два символи. Тому стандартним є брати b = 2 («двійкова ентропія»). Таким чином, ентропія первинної абетки, з її заданим емпіричним розподілом імовірності, — це число, яке дорівнює числу (можливо дробовому) символів «ідеальної абетки», з оптимальним розподілом імовірності, необхідних для кодування кожного символу первинної абетки. Також зверніть увагу, що «оптимальний розподіл імовірності» тут означає рівномірний розподіл: первинна абетка з n символів має найвищу можливу ентропію (для абетки з n символів), коли розподіл імовірності абетки є рівномірним. Цією оптимальною ентропією виявляється logb(n).
Ефективність
Первинна абетка з нерівномірним розподілом матиме меншу ентропію, ніж якби ці символи мали рівномірний розподіл (тобто, були «оптимальною абеткою»). Цю дефективність ентропії може бути виражено відношенням, яке називається ефективністю:[]
- []
Ефективність є корисною для кількісної оцінки ефективності використання каналу зв'язку. Це формулювання також називають нормалізованою ентропією, оскільки ентропія ділиться на максимальну ентропію . Крім того, ефективності байдужий вибір (додатної) бази b, про що свідчить нечутливість до неї в кінцевому логарифмі.
Характеризування
Ентропія Шеннона [en] невеликим числом критеріїв, перерахованих нижче. Будь-яке визначення ентропії, яке задовольняє ці припущення, має вигляд
де K є сталою, яка відповідає виборові одиниць вимірювання.
Далі pi = Pr(X = xi), а Ηn(p1, …, pn) = Η(X).
Неперервність
Ця міра повинна бути неперервною, так що зміна значень ймовірностей на дуже незначну величину повинна змінювати ентропію лише на незначну величину.
Симетричність
При перевпорядкуванні виходів xi ця міра повинна залишатися незмінною.
- тощо
Максимум
Ця міра повинна бути максимальною тоді, коли всі виходи є однаково правдоподібними (невизначеність є найвищою, коли всі можливі події є рівноймовірними).
Для рівноймовірних подій ентропія повинна зростати зі збільшенням числа виходів.
Для безперервних випадкових змінних розподілом із максимальною диференціальною ентропією є багатовимірний нормальний розподіл.
Адитивність
Величина ентропії повинна не залежати від того, який поділ процесу на частини розглядається.
Ця остання функційна залежність характеризує ентропію системи з підсистемами. Вона вимагає, щоби ентропію системи можливо було обчислити з ентропій її підсистем, якщо взаємодії між цими підсистемами є відомими.
При заданому ансамблі n рівномірно розподілених елементів, які поділяються на k блоків (підсистем) з b1, ..., bk елементами в кожному, ентропія всього ансамблю повинна дорівнювати сумі ентропії системи блоків і окремих ентропій блоків, кожна з яких є зваженою на ймовірність знаходження в цьому відповідному блоці.
Для додатних цілих чисел bi, де b1 + … + bk = n,
При обранні k = n, b1 = … = bn = 1 це означає, що ентропія незмінного виходу дорівнює нулеві: Η1(1) = 0. Це означає, що ефективність первинної абетки з n символами може бути визначено просто як таку, що дорівнює її n-арній ентропії. Див. також надмірність інформації.
Додаткові властивості
Ентропія Шеннона задовольняє наступні властивості, для деяких з яких корисно інтерпретувати ентропію як кількість пізнаної інформації (або усуненої невизначеності) при розкритті значення випадкової величини X:
- Додавання або усування подій з нульовою ймовірністю не впливає на ентропію:
- .
- Ентропія дискретної випадкової змінної є невід'ємним числом:
- .
- За допомогою нерівності Єнсена може бути підтверджено, що
- .
- Ця максимальна ентропія logb(n) ефективно досягається первинною абеткою, яка має рівномірний розподіл ймовірності: невизначеність є максимальною, коли всі можливі події є однаково ймовірними.
- Ентропія, або обсяг інформації, розкритої шляхом визначення (X,Y) (тобто визначення X та Y одночасно) дорівнює інформації, розкритої шляхом проведення двох послідовних експериментів: спершу виявлення значення Y, а потім виявлення значення X, за умови, що ви знаєте значення Y. Це може бути записано як
- Якщо , де є функцією, то . Застосування попередньої формули до дає
- отже, , таким чином, ентропія величини може тільки зменшуватися, коли остання проходить через функцію.
- Якщо X та Y в є двома незалежними випадковими змінними, то знання значення Y не впливає на наше знання про значення X (оскільки ці двоє не впливають одне на одне в силу незалежності):
- Ентропія двох одночасних подій є не більшою за суму ентропій кожної з окремих подій, і дорівнює їй, якщо ці дві події є незалежними. Точніше, якщо X та Y є двома випадковими величинами на одному й тому ж імовірнісному просторі, а (X, Y) позначає їхній декартів добуток, то
- Ентропія є угнутою за функцією маси ймовірності , тобто,
- для всіх функцій маси ймовірності та .
Розширення дискретної ентропії до неперервного випадку
Диференціальна ентропія
Ентропію Шеннона обмежено випадковими величинами, які набувають дискретних значень. Відповідна формула для неперервної випадкової величини з функцією густини ймовірності f(x) зі скінченною або нескінченною областю визначення на дійсній осі визначається аналогічно, з допомогою наведеного вище вираження ентропії як математичного сподівання:
Цю формулу зазвичай називають непере́рвною ентропі́єю (англ. continuous entropy), або диференціальною ентропією. Попередником неперервної ентропії h[f] є вираз функціоналу Η в [en].
Хоча аналогія між обома функціями й наводить на роздуми, мусить бути поставлено наступне питання: чи є диференціальна ентропія обґрунтованим розширенням дискретної ентропії Шеннона? Диференціальній ентропії бракує ряду властивостей, якими володіє дискретна ентропія Шеннона, — вона навіть може бути від'ємною, — і відтак було запропоновано поправки, зокрема, [en].
Щоби відповісти на це питання, ми мусимо встановити зв'язок між цими двома функціями:
Ми хочемо отримати загальну скінченну міру при прямуванні розміру засіків до нуля. В дискретному випадку розмір засіків є (неявною) шириною кожного з n (скінченних або нескінченних) засіків, чиї ймовірності позначаються через pn. Оскільки ми робимо узагальнення до неперервної області визначення, ми мусимо зробити цю ширину явною.
Щоби зробити це, почнімо з неперервної функції f, дискретизованої засіками розміру . Згідно теореми про середнє значення, в кожному засіку існує таке значення xi, що
і відтак інтеграл функції f може бути наближено (в рімановому сенсі) за допомогою
де ця границя і «розмір засіку прямує до нуля» є рівноцінними.
Позначмо
і, розкриваючи цього логарифма, ми маємо
При Δ → 0 ми маємо
Але зауважте, що log(Δ) → −∞ при Δ → 0, отже, нам потрібне особливе визначення диференціалу або неперервної ентропії:
що, як було сказано раніше, називають диференціа́льною ентропі́єю (англ. differential entropy). Це означає, що диференціальна ентропія не є границею ентропії Шеннона при n → ∞. Вона радше відрізняється від границі ентропії Шеннона нескінченним зсувом (див. також статтю про [en]).
Взяття границі щільності дискретних точок
Детальніші відомості з цієї теми ви можете знайти в статті [en].
В результаті виходить, що, на відміну від ентропії Шеннона, диференціальна ентропія не є в цілому доброю мірою невизначеності або інформації. Наприклад, диференціальна ентропія може бути від'ємною; крім того, вона не є інваріантною відносно неперервних перетворень координат. Цю проблему може бути проілюстровано зміною одиниць вимірювання, коли x є розмірною величиною. f(x) тоді матиме одиниці 1/x. Аргумент логарифма мусить бути безрозмірним, інакше він є неправильним, бо така диференціальна ентропія, як наведено вище, буде неправильною. Якщо є деяким «стандартним» значенням x (тобто, «розміром засіку»), і відтак має такі ж одиниці вимірювання, то видозмінену диференціальну ентропію може бути записано в належному вигляді як
і результат буде однаковим при будь-якому виборі одиниць вимірювання для x. Насправді границя дискретної ентропії при N → 0 включала би також і член log(N), який в загальному випадку був би нескінченним. Це є очікуваним, неперервні величини при дискретизації зазвичай матимуть нескінченну ентропію. [en] в дійсності є мірою того, наскільки розподіл є простішим для опису за розподіл, який є рівномірним над своєю схемою квантування.
Відносна ентропія
Детальніші відомості з цієї теми ви можете знайти в статті [en].
Іншою корисною мірою ентропії, яка однаково добре працює в дискретному та неперервному випадках, є відно́сна ентропі́я (англ. relative entropy) розподілу. Вона визначається як відстань Кульбака — Лейблера від розподілу до еталонної міри m наступним чином. Припустімо, що розподіл імовірності p є абсолютно неперервним відносно міри m, тобто має вигляд p(dx) = f(x)m(dx) для деякої невід'ємної m-інтегрованої функції f з m-інтегралом 1, тоді відносну ентропію може бути визначено як
В такому вигляді відносна ентропія узагальнює (з точністю до зміни знака) як дискретну ентропію, коли міра m є лічильною мірою, так і диференціальну ентропію, коли міра m є мірою Лебега. Якщо міра m і сама є розподілом ймовірності, то відносна ентропія є невід'ємною, і нульовою, якщо p = m як міри. Вона визначається для будь-якого простору мір, отже, не залежить від координат, і є інваріантною відносно перепараметризації координат, якщо перетворення міри m береться до уваги правильно. Відносна ентропія, і неявно ентропія та диференціальна ентропія, залежать від «базової» міри m.
Застосування в комбінаториці
Ентропія стала корисною величиною в комбінаториці.
Нерівність Люміса — Уїтні
Простим прикладом цього є альтернативне доведення [en]: для будь-якої підмножини A ⊆ Zd ми маємо
де Pi є ортогональною проєкцією в i-й координаті:
Це доведеня випливає як простий наслідок [en]: якщо X1, …, Xd є випадковими величинами, а S1, …, Sn є підмножинами {1, …, d}, такими, що кожне ціле число між 1 і d лежить точно в r з цих підмножин, то
де є декартовим добутком випадкових величин Xj з індексами j в Si (тому розмірність цього вектора дорівнює розмірові Si).
Ми зробимо нарис, як з цього випливає Люміс — Уїтні: справді, нехай X є рівномірно розподіленою випадковою величиною зі значеннями в A, і такою, що кожна точка з A трапляється з однаковою ймовірністю. Тоді (згідно додаткових властивостей ентропії, згадуваних вище) Η(X) = log|A|, де |A| позначає потужність A. Нехай Si = {1, 2, …, i−1, i+1, …, d}. Діапазон міститься в Pi(A) і, отже, . Тепер застосуймо це, щоби обмежити праву частину нерівності Ширера, і піднести до степеня протилежні частини нерівності, яку ви отримали в результаті.
Наближення до біноміального коефіцієнту
Для цілих чисел 0 < k < n покладімо q = k/n. Тоді
де
Нижче наведено схематичне доведення. Зауважте, що є одним із членів суми
Відповідно, з нерівності після логарифмування отримується верхня межа.
Для отримання нижньої межі спочатку шляхом певних перетворень показується, що доданок є найбільшим членом у наведеній сумі. Але тоді
оскільки біном містить n + 1 членів. Звідси випливає нижня межа.
Наведені результати інтерпретуються, наприклад, таким чином: число двійкових стрічок довжини n, які містять рівно k одиниць, можна оцінити як .
Див. також
- Взаємна інформація
- Випадковість
- Відстань Геммінга
- Відстань Левенштейна
- [en]
- Ентропійна швидкість
- Ентропійне кодування — схема кодування, яка призначає коди символам таким чином, щоби довжини кодів відповідали ймовірностям символів
- [en]
- [en]
- [en] в динамічних системах
- Ентропія Реньї — узагальнення ентропії Шеннона; вона є однією з сімейства функціоналів для кількісної оцінки різноманіття, невизначеності або випадковості системи.
- Ентропія Цалліса
- Індекс різноманітності — альтернативні підходи до кількісної оцінки різноманітності в розподілі ймовірності
- Індекс Тейла
- Індекс Шеннона
- Інформація за Фішером
- [en]
- [en]
- [en] — міра розрізнюваності між двома квантовими станами
- Множник Лагранжа
- Негентропія
- [en]
- Типоглікемія
- [en]
- Перехресна ентропія — є мірою усередненого числа бітів, необхідних для ідентифікації події з набору можливостей між двома розподілами ймовірності
- Перплексивність
- Спільна ентропія — це міра того, як багато ентропії міститься в спільній системі з двох випадкових величин.
- Умовна ентропія
- [en] — інші міри статистичної дисперсії для номінальних розподілів
Примітки
- Pathria, R. K.; Beale, Paul (2011). . Academic Press. с. 51. ISBN . Архів оригіналу за 17 червня 2020. Процитовано 13 грудня 2018. (англ.)
- Shannon, Claude E. (July–October 1948). A Mathematical Theory of Communication. [en]. 27 (3): 379—423. doi:10.1002/j.1538-7305.1948.tb01338.x. (, заархівовано звідси [ 20 червня 2014 у Wayback Machine.]) (англ.)
- Shannon, Claude E. (1948). (PDF). [en]. 27. Архів оригіналу (PDF) за 15 лютого 2019. Процитовано 13 грудня 2018., July and October (англ.)
- Schneier, B: Applied Cryptography, Second edition, John Wiley and Sons. (англ.)
- Borda, Monica (2011). . Springer. ISBN . Архів оригіналу за 15 лютого 2017. Процитовано 6 червня 2017. (англ.)
- Han, Te Sun & Kobayashi, Kingo (2002). . American Mathematical Society. ISBN . Архів оригіналу за 15 лютого 2017. Процитовано 6 червня 2017. (англ.)
- Schneider, T.D, Information theory primer with an appendix on logarithms[недоступне посилання], National Cancer Institute, 14 April 2007. (англ.)
- Carter, Tom (March 2014). (PDF). Santa Fe. Архів оригіналу (PDF) за 4 червня 2016. Процитовано 4 серпня 2017. (англ.)
- Compare: Boltzmann, Ludwig (1896, 1898). Vorlesungen über Gastheorie : 2 Volumes – Leipzig 1895/98 UB: O 5262-6. English version: Lectures on gas theory. Translated by Stephen G. Brush (1964) Berkeley: University of California Press; (1995) New York: Dover (англ.)
- Mark Nelson (24 August 2006). . Архів оригіналу за 1 березня 2018. Процитовано 27 листопада 2008. (англ.)
- "The World's Technological Capacity to Store, Communicate, and Compute Information" [ 27 липня 2013 у Wayback Machine.], Martin Hilbert and Priscila López (2011), Science, 332(6025); free access to the article through here: martinhilbert.net/WorldInfoCapacity.html (англ.)
- Massey, James (1994). (PDF). Proc. IEEE International Symposium on Information Theory. Архів оригіналу (PDF) за 1 січня 2014. Процитовано 31 грудня 2013. (англ.)
- Malone, David; Sullivan, Wayne (2005). (PDF). Proceedings of the Information Technology & Telecommunications Conference. Архів оригіналу (PDF) за 15 квітня 2016. Процитовано 31 грудня 2013. (англ.)
- Pliam, John (1999). Guesswork and variation distance as measures of cipher security. International Workshop on Selected Areas in Cryptography. doi:10.1007/3-540-46513-8_5. (англ.)
- Thomas M. Cover; Joy A. Thomas (18 липня 2006). Elements of Information Theory. Hoboken, New Jersey: Wiley. ISBN . (англ.)
- Aoki, New Approaches to Macroeconomic Modeling. (англ.)
- Probability and Computing, M. Mitzenmacher and E. Upfal, Cambridge University Press (англ.)
Література
Підручники з теорії інформації
- Теорія інформації і кодування: навч. посіб. / А. Я. Кулик, С. Г. Кривогубченко; Вінниц. нац. техн. ун-т. — Вінниця, 2008. — 145 c.
- Теорія інформації: навч. посіб. / Н. О. Тулякова; Сум. держ. ун-т. — Суми, 2008. — 212 c.
- Теорія інформації: навч. посіб. / В. В. Дядичев, Б. М. Локотош, А. В. Колєсніков; Східноукр. нац. ун-т ім. В. Даля. — Луганськ, 2009. — 249 c.
- Теорія інформації та кодування / В. С. Василенко, О. Я. Матов; НАН України, Ін-т пробл. реєстрації інформації. — Київ : ІПРІ НАН України, 2014. — 439 c.
- Теорія інформації та кодування: підручник / В. І. Барсов, В. А. Краснобаєв, З. В. Барсова, О. І. Тиртишніков, І. В. Авдєєв; ред.: В. І. Барсов; МОНМС України, Укр. інж.-пед. акад., Полтав. нац. техн. ун-т ім. Ю. Кондратюка. — Полтава, 2011. — 321 c.
- Теорія інформації та кодування: Підруч. для студ. вищ. техн. навч. закл. / Ю. П. Жураковський, В. П. Полторак. — К. : «Вища шк.», 2001. — 255 c.
- Arndt, C. (2004), Information Measures: Information and its Description in Science and Engineering, Springer, (англ.)
- Cover, T. M., Thomas, J. A. (2006), Elements of information theory, 2nd Edition. Wiley-Interscience. . (англ.)
- Gray, R. M. (2011), Entropy and Information Theory, Springer. (англ.)
- [en]. Information Theory, Inference, and Learning Algorithms [ 17 лютого 2016 у Wayback Machine.] Cambridge: Cambridge University Press, 2003. (англ.)
- Martin, Nathaniel F.G. & England, James W. (2011). . Cambridge University Press. ISBN . Архів оригіналу за 19 березня 2015. Процитовано 6 червня 2017. (англ.)
- Мартин Н., Ингленд Дж. Математическая теория энтропии. — М. : Мир, 1988. — 350 с. (рос.)
- Shannon, C.E., Weaver, W. (1949) The Mathematical Theory of Communication, Univ of Illinois Press. (англ.)
- Stone, J. V. (2014), Chapter 1 of Information Theory: A Tutorial Introduction [ 3 червня 2016 у Wayback Machine.], University of Sheffield, England. . (англ.)
- Хэмминг Р. В. (1983). Теория информации и теория кодирования. Москва: Радио и Связь. (рос.)
Посилання
- Hazewinkel, Michiel, ред. (2001), Entropy, Математична енциклопедія, , ISBN (англ.)
- Введення в ентропію та інформацію [ 17 травня 2016 у Wayback Machine.] на [en](англ.)
- Entropy [ 31 травня 2016 у Wayback Machine.], міждисциплінарний журнал про всі аспекти поняття ентропії. Відкритий доступ. (англ.)
- (англ.)
- Аплет Java, який представляє експеримент Шеннона з обчислення ентропії англійської мови [ 13 травня 2016 у Wayback Machine.]
- (англ.)
- An Intuitive Guide to the Concept of Entropy Arising in Various Sectors of Science — вікікнига про інтерпретацію поняття ентропії. (англ.)
- Network Event Detection With Entropy Measures [ 13 квітня 2016 у Wayback Machine.], Dr. Raimund Eimann, University of Auckland, PDF; 5993 kB — докторська праця, яка демонструє, як вимірювання ентропії можуть застосовуватися для виявлення мережевих аномалій. (англ.)
- Entropy [ 4 червня 2016 у Wayback Machine.] — репозитарій [en] реалізацій ентропії Шеннона різними мовами програмування.
- "Information Theory for Intelligent People" [ 13 червня 2020 у Wayback Machine.]. Коротке введення до аксіом теорії інформації, ентропії, взаємної інформації, відстані Кульбака — Лейблера та відстані Єнсена — Шеннона. (англ.)
- Інтерактивний інструмент для обчислення ентропії (простого тексту ASCII) [ 15 квітня 2022 у Wayback Machine.]
- Інтерактивний інструмент для обчислення ентропії (двійкового входу)
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
U Vikipediyi ye statti pro inshi znachennya cogo termina Entropiya znachennya Cya stattya maye kilka nedolikiv Bud laska dopomozhit udoskonaliti yiyi abo obgovorit ci problemi na storinci obgovorennya Cyu stattyu napisano zanadto profesijnim stilem zi specifichnoyu terminologiyeyu sho mozhe buti nezrozumilim dlya bilshosti chitachiv Vi mozhete dopomogti vdoskonaliti cyu stattyu zrobivshi yiyi zrozumiloyu dlya nespecialistiv bez vtrat zmistu Mozhlivo storinka obgovorennya mistit zauvazhennya shodo potribnih zmin gruden 2018 Cya stattya potrebuye dodatkovih posilan na dzherela dlya polipshennya yiyi perevirnosti Bud laska dopomozhit udoskonaliti cyu stattyu dodavshi posilannya na nadijni avtoritetni dzherela Zvernitsya na storinku obgovorennya za poyasnennyami ta dopomozhit vipraviti nedoliki Material bez dzherel mozhe buti piddano sumnivu ta vilucheno traven 2016 Dva biti entropiyi u vipadku dvoh spravedlivih pidkidan moneti entropiya informaciyi v bitah ye logarifmom za osnovoyu 2 z chisla mozhlivih rezultativ za dvoh monet isnuye chotiri mozhlivi rezultati ta dva biti entropiyi Vzagali informacijna entropiya ye userednenoyu kilkistyu informaciyi sho nese podiya za rozglyadu vsih mozhlivih rezultativ Informaci jna entropi ya angl information entropy ce userednena shvidkist iz yakoyu produkuye informaciyu stohastichne dzherelo danih Miroyu informacijnoyi entropiyi pov yazanoyu z kozhnim mozhlivim znachennyam danih ye vid yemnij logarifm funkciyi masi jmovirnosti dlya cogo znachennya S iPiln Pi textstyle S sum i P i ln P i Takim chinom koli dzherelo danih maye mensh imovirne znachennya napriklad koli stayetsya nizkojmovirna podiya to cya podiya nese bilshe informaciyi neochikuvanosti nizh koli dzherelo danih maye bilsh imovirne znachennya Viznachena takim chinom kilkist informaciyi sho peredayetsya kozhnoyu podiyeyu staye vipadkovoyu zminnoyu chiye matematichne spodivannya ye informacijnoyu entropiyeyu Vzagali entropiyu poznachayut bezlad abo neviznachenist i viznachennya entropiyi sho zastosovuyut v teoriyi informaciyi ye pryamim analogom viznachennya sho zastosovuyut u statistichnij termodinamici Ponyattya informacijnoyi entropiyi bulo vvedeno Klodom Shennonom u jogo praci 1948 roku Matematichna teoriya zv yazku Bazova model sistemi peredavannya danih skladayetsya z troh elementiv dzherela danih kanalu zv yazku ta prijmacha i za virazom Shennona fundamentalnoyu zadacheyu zv yazku ye te shobi otrimuvach buv zdaten vstanovlyuvati yaki dani bulo porodzheno dzherelom na osnovi signalu sho vin otrimuye kanalom 379 423 ta 623 656 Entropiya zabezpechuye absolyutnu mezhu najkorotshoyi mozhlivoyi userednenoyi dovzhini bezvtratnogo stisnyuvalnogo koduvannya danih produkovanih dzherelom i yaksho entropiya dzherela ye menshoyu za propusknu spromozhnist kanalu zv yazku to dani porodzhuvani cim dzherelom mozhlivo nadijno peredavati prijmachevi prinajmni teoretichno mozhlivo nehtuyuchi deyakimi praktichnimi mirkuvannyami takimi yak skladnist sistemi potribnoyi dlya peredavannya danih abo kilkosti chasu sho ce peredavannya cih danih mozhe zabirati Informacijnu entropiyu zazvichaj vimiryuyut v bitah sho takozh nazivayut shennonami angl bit shannon abo inodi v naturalnih odinicyah natah angl nat abo v desyatkovih cifrah sho nazivayut ditami banami abo gartli Odinicya vimiryuvannya zalezhit vid osnovi logarifma sho vikoristovuyut dlya viznachennya entropiyi Logarifm rozpodilu jmovirnosti ye korisnim yak mira entropiyi tomu sho dlya nezalezhnih dzherel vin ye aditivnim Napriklad entropiya pidkidannya spravedlivoyi moneti skladaye 1 bit a entropiyeyu m pidkidan ye m bit U prostomu podanni dlya predstavlennya velichini sho mozhe nabuvati odnogo z n znachen potribno log2 n bitiv yaksho n ye stepenem chisla 2 Yaksho ci znachennya ye odnakovo jmovirnimi to entropiya v bitah dorivnyuye comu chislu Yaksho zh traplyannya odnogo z cih znachen ye jmovirnishim za inshi to sposterezhennya traplyannya cogo znachennya ye mensh informativnim nizh yakbi trapivsya ne takij zvichajnij rezultat I navpaki ridkisnishi podiyi pri yihnomu sposterezhenni nadayut bilshe informaciyi Oskilki sposterezhennya mensh imovirnih podij traplyayetsya ridshe v pidsumku vihodit sho entropiya pri rozglyadanni yiyi yak userednenoyi informaciyi otrimuvana vid nerivnomirno rozpodilenih danih ye zavzhdi menshoyu abo rivnoyu do log2 n Yaksho vihid ye nezminnim to entropiya dorivnyuye nulevi Koli rozpodil imovirnosti dzherela danih ye vidomim entropiya virazhaye ci mirkuvannya kilkisno Zmist sposterezhuvanih podij zmist povidomlen u viznachenni entropiyi znachennya ne maye Entropiya vrahovuye lishe jmovirnist sposterezhennya pevnoyi podiyi tomu informaciya yaku vona vklyuchaye ye informaciyeyu pro rozpodil jmovirnosti sho lezhit v osnovi a ne pro zmist samih podij VvedennyaOsnovnoyu ideyeyu teoriyi informaciyi ye te sho chim bilshe htos znaye pro predmet to menshe novoyi informaciyi pro nogo voni zdatni otrimati Yaksho podiya ye duzhe jmovirnoyu to koli vona traplyayetsya v comu nemaye nichogo neochikuvanogo i vidtak vona privnosit malo novoyi informaciyi I navpaki yaksho podiya bula malojmovirnoyu to yiyi traplyannya ye nabagato informativnishim Takim chinom informacijnij vmist ye vishidnoyu funkciyeyu obernenoyi jmovirnosti podiyi 1 p de p ye jmovirnistyu podiyi Teper yaksho mozhe trapitisya bilshe podij entropiya vimiryuye userednenij informacijnij vmist yakij vi mozhete ochikuvati otrimati yaksho dijsno traplyayetsya odna z cih podij Z cogo viplivaye sho vikidannya gralnogo kubika maye bilshe entropiyi nizh pidkidannya moneti oskilki kozhen z rezultativ gralnogo kubika maye menshu jmovirnist nizh kozhen z rezultativ moneti Otzhe entropiya ce mira neperedbachuvanosti angl unpredictability stanu abo rivnoznachno jogo userednenogo informacijnogo vmistu angl average information content Shobi otrimati intuyitivne rozuminnya cih terminiv rozglyanmo priklad politichnogo opituvannya Yak pravilo taki opituvannya vidbuvayutsya tomu sho yihni rezultati ne ye zazdalegid vidomimi Inshimi slovami rezultati opituvannya ye vidnosno neperedbachuvanimi i faktichne zdijsnennya opituvannya ta z yasovuvannya rezultativ daye deyaku novu informaciyu ce prosto rizni sposobi skazati sho apriorna entropiya rezultativ opituvannya ye visokoyu Teper rozglyanmo vipadok koli take zh opituvannya provoditsya vdruge nezabarom pislya pershogo opituvannya Oskilki rezultati pershogo opituvannya vzhe ye vidomimi pidsumki drugogo opituvannya mozhna peredbachiti dobre i ci rezultati ne povinni mistiti bagato novoyi informaciyi v comu vipadku apriorna entropiya rezultativ drugogo opituvannya ye nizkoyu po vidnoshennyu do apriornoyi entropiyi pershogo Teper rozglyanmo priklad z pidkidannyam moneti Yaksho jmovirnist vipadannya aversu taka zh yak i jmovirnist vipadannya reversu to entropiya pidkidannya moneti ye nastilki visokoyu naskilki ce mozhlivo Prichinoyu cogo ye te sho nemaye zhodnogo sposobu peredbachiti rezultat pidkidannya moneti zazdalegid yaksho nam treba bulo bi obirati to najkrashe sho mi mogli bi zrobiti ce peredbachiti sho moneta vipade aversom dogori i cej prognoz buv bi pravilnim z imovirnistyu 1 2 Take pidkidannya moneti maye odin bit entropiyi oskilki ye dva mozhlivi rezultati yaki traplyayutsya z odnakovoyu jmovirnistyu i z yasuvannya faktichnogo rezultatu mistit odin bit informaciyi Na protivagu do cogo pidkidannya moneti yaka maye dva aversi j zhodnogo reversu maye nulovu entropiyu oskilki moneta zavzhdi vipadatime aversom i rezultat mozhe buti peredbacheno cilkom Analogichno binarna podiya z rivnojmovirnimi rezultatami maye entropiyu Shennona log2 2 1 displaystyle log 2 2 1 bit Podibno do cogo odin trit iz rivnojmovirnimi znachennyami mistit log2 3 displaystyle log 2 3 blizko 1 58496 bitiv informaciyi oskilki vin mozhe mati odne z troh znachen Anglomovnij tekst yaksho rozglyadati jogo yak strichku simvoliv maye dosit nizkij riven entropiyi tobto vin ye dovoli peredbachuvanim Navit yaksho mi ne znayemo tochno sho bude dali mi mozhemo buti dovoli vpevnenimi sho napriklad e tam bude nabagato poshirenishoyu za z sho poyednannya qu zustrichatimetsya nabagato chastishe za bud yaki inshi poyednannya yaki mistyat q i sho poyednannya th bude nabagato poshirenishim za z q abo qu Pislya pershih kilkoh liter chasto mozhna vgadati reshtu slova Anglijskij tekst maye mizh 0 6 ta 1 3 bita entropiyi na simvol povidomlennya 234 Yaksho shema stisnennya ye vilnoyu vid vtrat tobto zavzhdi mozhna vidtvoriti povne pervinne povidomlennya shlyahom roztiskannya to stisnene povidomlennya maye takij samij obsyag informaciyi yak i pervinne ale peredanij menshoyu kilkistyu simvoliv Tobto vono maye bilshe informaciyi abo vishu entropiyu na odin simvol Ce oznachaye sho stisnene povidomlennya maye menshu nadmirnist Grubo kazhuchi en stverdzhuye sho shema stisnennya bez vtrat v serednomu ne mozhe stisnuti povidomlennya tak shobi vono malo bilshe odnogo bitu informaciyi na bit povidomlennya ale sho bud yake znachennya menshe odnogo bitu informaciyi na bit povidomlennya mozhe buti dosyagnuto shlyahom zastosuvannya vidpovidnoyi shemi koduvannya Entropiya povidomlennya na bit pomnozhena na dovzhinu cogo povidomlennya ye miroyu togo naskilki bagato informaciyi v cilomu mistit povidomlennya Dlya naochnosti uyavit sho mi hochemo peredati poslidovnist do skladu yakoyi vhodyat 4 simvoli A B V i G Takim chinom povidomlennyam dlya peredavannya mozhe buti ABAGGVAB Teoriya informaciyi proponuye sposib obchislennya najmenshoyi mozhlivoyi kilkosti informaciyi yaka peredast ce Yaksho vsi 4 literi ye rivnojmovirnimi 25 mi ne mozhemo zrobiti nichogo krashogo nad dvijkovim kanalom anizh koduvati kozhnu literu 2 bitami u dvijkovomu viglyadi A mozhe buti kodovano yak 00 B yak 01 V yak 10 a G yak 11 Teper pripustimo sho A traplyayetsya z imovirnistyu 70 B 26 a V ta G po 2 kozhna Mi mogli bi priznachiti kodi zminnoyi dovzhini tak sho otrimannya 1 kazalo bi nam divitisya she odin bit yaksho tilki mi ne otrimali vzhe pered cim 2 poslidovni biti odinic V comu vipadku A bulo bi kodovano yak 0 odin bit B yak 10 a V i G yak 110 i 111 Legko pobachiti sho protyagom 70 chasu potribno nadsilati lishe odin bit 26 chasu dva biti i lishe protyagom 4 vid chasu 3 biti Todi v serednomu neobhidno menshe za 2 biti oskilki entropiya ye nizhchoyu cherez visoku poshirenist A z nastupnoyu za neyu B razom 96 simvoliv Obchislennya sumi zvazhenih za jmovirnostyami logarifmichnih imovirnostej vimiryuye ta shoplyuye cej efekt Teorema Shennona takozh oznachaye sho zhodna shema stisnennya bez vtrat ne mozhe skorochuvati vsi povidomlennya Yaksho yakis povidomlennya vihodyat korotshimi hocha b odne povinne vijti dovshim v silu principu Dirihle V praktichnomu zastosuvanni ce zazvichaj ne ye problemoyu oskilki nas yak pravilo cikavit stisnennya lishe pevnih tipiv povidomlen napriklad dokumentiv anglijskoyu movoyu na protivagu do tekstu tarabarshinoyu abo cifrovih fotografij a ne shumu i ne vazhlivo yaksho algoritm stisnennya robit dovshimi malojmovirni abo necikavi poslidovnosti OznachennyaNazvavshi yiyi na chest en Shennon oznachiv entropiyu H grecka litera eta diskretnoyi vipadkovoyi velichini X textstyle X z mozhlivimi znachennyami x1 xn textstyle left x 1 ldots x n right ta funkciyeyu masi jmovirnosti P X textstyle mathrm P X yak H X E I X E log P X displaystyle mathrm H X mathbb E operatorname I X mathbb E log mathrm P X Tut E displaystyle mathbb E ye operatorom matematichnogo spodivannya angl expectation a I ye kilkistyu informaciyi X 11 19 20 I X i sama ye vipadkovoyu velichinoyu Entropiyu mozhe buti zapisano v yavnomu viglyadi yak H X i 1nP xi I xi i 1nP xi logb P xi displaystyle mathrm H X sum i 1 n mathrm P x i mathrm I x i sum i 1 n mathrm P x i log b mathrm P x i de b ye en logarifma yakij zastosovuyetsya Zvichnimi znachennyami b ye 2 chislo Ejlera e ta 10 a vidpovidnimi odinicyami entropiyi ye biti dlya b 2 nati dlya b e ta bani dlya b 10 U vipadku P xi 0 dlya deyakogo i znachennya vidpovidnogo dodanku 0 logb 0 prijmayut rivnim 0 sho vidpovidaye granici limp 0 plog p 0 displaystyle lim p to 0 p log p 0 Mozhna takozh viznachiti umovnu entropiyu dvoh podij X ta Y yaki nabuvayut znachen xi ta yj vidpovidno yak H X Y i jp xi yj log p xi yj p yj displaystyle mathrm H X Y sum i j p x i y j log frac p x i y j p y j de p xi yj ye jmovirnistyu togo sho X xi ta Y yj Cyu velichinu slid rozumiti yak stupin dovilnosti vipadkovoyi velichini X pri zadanij podiyi Y PrikladEntropiya H X tobto ochikuvana neochikuvanist pidkidannya moneti vimiryuvana v bitah predstavlena grafichno vidnosno uperedzhennya moneti Pr X 1 de X 1 ye vipadinnyam aversa Tut entropiya skladaye shonajbilshe 1 bit i dlya povidomlennya rezultativ pidkidannya moneti 2 mozhlivi znachennya potribno v serednomu ne bilshe 1 bitu v tochnosti 1 bit dlya spravedlivoyi moneti Rezultat spravedlivogo gralnogo kubika 6 mozhlivih znachen potrebuvatime v serednomu log26 bitiv Detalnishi vidomosti z ciyeyi temi vi mozhete znajti v statti en ta en Rozglyanmo pidkidannya moneti z vidomimi ale ne obov yazkovo spravedlivimi jmovirnostyami vipadannya aversu chi reversu ce mozhna zmodelyuvati yak en Entropiya nevidomogo rezultatu nastupnogo pidkidannya moneti ye najbilshoyu yaksho moneta ye spravedlivoyu tobto yaksho yak aversi tak i reversi mayut odnakovu jmovirnist 1 2 Ce ye situaciyeyu maksimalnoyi neviznachenosti oskilki v nij najskladnishe peredbachiti rezultat nastupnogo pidkidannya rezultat kozhnogo pidkidannya moneti podaye odin povnij bit informaciyi Ce ye tomu sho H X i 1nP xi logb P xi i 1212log2 12 i 1212 1 1 displaystyle begin aligned mathrm H X amp sum i 1 n mathrm P x i log b mathrm P x i amp sum i 1 2 frac 1 2 log 2 frac 1 2 amp sum i 1 2 frac 1 2 cdot 1 1 end aligned Prote yaksho mi znayemo sho moneta ne ye spravedlivoyu a vipadaye aversom chi reversom z imovirnostyami p ta q de p q to todi neviznachenosti ye menshe Kozhnogo razu yak yiyi pidkidayut vipadannya odniyeyi zi storin ye jmovirnishim nizh vipadannya inshoyi Znizhennya neviznachenosti otrimuye kilkisnu ocinku v viglyadi menshoyi entropiyi v serednomu kozhne pidkidannya moneti podaye menshe nizh odin povnij bit informaciyi Napriklad yaksho p 0 7 to H X plog2 p qlog2 q 0 7log2 0 7 0 3log2 0 3 0 7 0 515 0 3 1 737 0 8816 lt 1 displaystyle begin aligned mathrm H X amp p log 2 p q log 2 q amp 0 7 log 2 0 7 0 3 log 2 0 3 amp approx 0 7 cdot 0 515 0 3 cdot 1 737 amp 0 8816 lt 1 end aligned Krajnim vipadkom ye dvoaversova moneta yaka nikoli ne vipadaye reversom abo dvoreversova moneta yaka nikoli ne daye v rezultati avers Tut nemaye niyakoyi neviznachenosti Entropiya dorivnyuye nulevi kozhne pidkidannya moneti ne podaye zhodnoyi novoyi informaciyi oskilki rezultati kozhnogo pidkidannya moneti zavzhdi viznacheni Entropiyu mozhe buti normalizovano shlyahom dilennya yiyi na dovzhinu informaciyi Ce spivvidnoshennya nazivayetsya en vono ye miroyu haotichnosti informaciyi ObgruntuvannyaShobi zrozumiti sens pi log 1 pi spershu sprobujmo viznachiti funkciyu informaciyi I z tochki zoru podiyi i z imovirnistyu pi Kilkist informaciyi otrimuvana cherez sposterezhennya podiyi i viplivaye z shennonovogo rozv yazku fundamentalnih vlastivostej informaciyi I p ye monotonno spadnoyu v p zbilshennya jmovirnosti podiyi zmenshuye informaciyu zi sposterezhennya podiyi i navpaki I p 0 informaciya ye nevid yemnoyu velichinoyu I 1 0 podiyi yaki vidbuvayutsya zavzhdi ne nesut informaciyi I p1p2 I p1 I p2 informaciya vid nezalezhnih podij ye aditivnoyu Ostannya vlastivist ye klyuchovoyu Vona stverdzhuye sho spilna jmovirnist nezalezhnih dzherel informaciyi nese stilki zh informaciyi skilki j ci dvi okremi podiyi po odnij Zokrema yaksho persha podiya mozhe vidavati odin z n en rezultativ a insha maye odin iz m rivnojmovirnih rezultativ to isnuye mn mozhlivih rezultativ spilnoyi podiyi Ce oznachaye sho yaksho dlya koduvannya pershogo znachennya potribno log2 n bit a dlya koduvannya drugogo log2 m to dlya koduvannya oboh potribno log2 mn log2 m log2 n Shennon viyaviv sho pravilnim viborom funkciyi dlya kilkisnoyi ocinki informaciyi yaka zberigala bi cyu aditivnist ye logarifmichna tobto I p log 1p log p displaystyle mathrm I p log left tfrac 1 p right log p nehaj I textstyle I ye informacijnoyu funkciyeyu sho ye dvichi neperervno diferencijovnoyu todi I p1p2 I p1 I p2 p2I p1p2 I p1 I p1p2 p1p2I p1p2 0I u uI u 0 u uI u 0 displaystyle begin array lcl I p 1 p 2 amp amp I p 1 I p 2 p 2 I p 1 p 2 amp amp I p 1 I p 1 p 2 p 1 p 2 I p 1 p 2 amp amp 0 I u uI u amp amp 0 u mapsto uI u amp amp 0 end array Ce diferencialne rivnyannya vede do rozv yazku I u klog u displaystyle I u k log u dlya bud yakogo k R displaystyle k in mathbb R Umova 2 vede do k lt 0 displaystyle k lt 0 a nadto k displaystyle k mozhe obiratisya z viglyadu k 1 log x displaystyle k 1 log x de x gt 1 displaystyle x gt 1 sho rivnoznachne obirannyu konkretnoyi Rizni odinici informaciyi biti dlya dvijkovogo logarifma log2 nati dlya naturalnogo logarifma ln bani dlya desyatkovogo logarifma log10 i tak dali ye lishe stalim domnozhennyam odna odnoyi Napriklad u vipadku pidkidannya spravedlivoyi moneti avers daye log2 2 1 bit informaciyi sho stanovit priblizno 0 693 nat abo 0 301 desyatkovih cifr V silu aditivnosti n pidkidan dayut n bit informaciyi sho stanovit priblizno 0 693n nat abo 0 301n desyatkovih cifr Yaksho isnuye rozpodil v yakomu podiya i mozhe traplyatisya z imovirnistyu pi z nogo bulo vzyato N prob i rezultat i trapivsya ni N pi raziv to zagalnoyu kilkistyu informaciyi yaku mi otrimali ye iniI pi iNpilog pi displaystyle sum i n i mathrm I p i sum i Np i log p i Otzhe userednenoyu kilkistyu informaciyi yaku mi otrimuyemo na podiyu ye ipilog pi displaystyle sum i p i log p i AspektiVidnoshennya do termodinamichnoyi entropiyi Detalnishi vidomosti z ciyeyi temi vi mozhete znajti v statti en Nathnennya prijnyati slovo entropiya v teoriyi informaciyi viniklo vid blizkoyi podibnosti mizh formuloyu Shennona i duzhe shozhimi vidomimi formulami zi statistichnoyi mehaniki U statistichnij termodinamici najzagalnishoyu formuloyu dlya termodinamichnoyi entropiyi S termodinamichnoyi sistemi ye entropiya Gibbsa S kB piln pi displaystyle S k text B sum p i ln p i de kB ye staloyu Bolcmana a pi ye jmovirnistyu en Entropiyu Gibbsa bulo viznacheno Villardom Gibbsom 1878 roku pislya ranishoyi praci Bolcmana 1872 roku Entropiya Gibbsa perenositsya majzhe bezzminnoyu do svitu kvantovoyi fiziki dayuchi entropiyu fon Nejmana vvedenu Dzhonom fon Nejmanom 1927 roku S kBTr rln r displaystyle S k text B rm Tr rho ln rho de r ye matriceyu gustini kvantovoyi mehanichnoyi sistemi a Tr ye slidom Na pobutovomu praktichnomu rivni zv yazok mizh informacijnoyu ta termodinamichnoyu entropiyeyu ochevidnim ne ye Fiziki ta himiki shilni bilshe cikavitisya zminami entropiyi pri spontannomu rozvitku sistemi vid yiyi pervisnih umov u vidpovidnosti z drugim zakonom termodinamiki nizh nezminnim rozpodilom imovirnosti I yak vkazuye malist staloyi Bolcmana kB zmini v S kB navit dlya nevelikih kilkostej rechovin u himichnih ta fizichnih procesah yavlyayut soboyu obsyagi entropiyi yaki ye nadzvichajno velikimi porivnyano z chim zavgodno v stisnenni danih ta obrobci signaliv Krim togo v klasichnij termodinamici entropiya viznachayetsya v terminah makroskopichnih vimiryuvan i ne robit zhodnih posilan na bud yakij rozpodil imovirnosti sho ye golovnim u viznachenni entropiyi informacijnoyi Zv yazok mizh termodinamikoyu i tim sho zaraz vidomo yak teoriya informaciyi bulo vpershe zrobleno Lyudvigom Bolcmanom i virazheno jogo en S kBln W displaystyle S k text B ln W de S ye termodinamichnoyu entropiyeyu okremogo makrostanu viznachenu termodinamichnimi parametrami takimi yak temperatura ob yem energiya tosho W ye chislom mikrostaniv riznih kombinacij chastinok u riznih energetichnih stanah yaki mozhut dati danij makrostan a kB ye staloyu Bolcmana Peredbachayetsya sho kozhen mikrostan ye odnakovo pravdopodibnim tak sho jmovirnistyu zadanogo mikrostanu ye pi 1 W Pri pidstavlenni cih imovirnostej do navedenogo vishe virazu dlya entropiyi Gibbsa abo rivnoznachno entropiyi Shennona pomnozhenoyi na kB v rezultati vihodit rivnyannya Bolcmana V terminah teoriyi informaciyi informacijna entropiya sistemi ye kilkistyu informaciyi yakoyi brakuye dlya viznachennya mikrostanu pri vidomomu makrostani Na dumku en 1957 roku termodinamichnu entropiyu yak poyasnyuyetsya statistichnoyu mehanikoyu slid rozglyadati yak zastosuvannya teoriyi informaciyi Shennona termodinamichna entropiya interpretuyetsya yak taka sho ye proporcijnoyu do kilkosti dodatkovoyi informaciyi Shennona neobhidnoyi dlya viznachennya detalnogo mikroskopichnogo stanu sistemi yaka zalishayetsya ne povidomlenoyu opisom viklyuchno v terminah makroskopichnih velichin klasichnoyi termodinamiki z koeficiyentom proporcijnosti yakij ye prosto staloyu Bolcmana Napriklad dodavannya teploti do sistemi pidvishuye yiyi termodinamichnu entropiyu oskilki ce zbilshuye chislo mozhlivih mikroskopichnih staniv sistemi yaki uzgodzhuyutsya z vimiryuvanimi znachennyami jogo makroskopichnih velichin roblyachi takim chinom bud yakij povnij opis stanu dovshim Div stattyu en Demon Maksvella mozhe gipotetichno znizhuvati termodinamichnu entropiyu sistemi z vikoristannyam informaciyi pro stan okremih molekul ale yak pokazali en z 1961 roku z kolegami shobi diyati cej demon musit sam pidvishuvati termodinamichnu entropiyu v comu procesi prinajmni na kilkist informaciyi Shennona yaku vin proponuye spochatku otrimati j zberegti i takim chinom zagalna termodinamichna entropiya ne znizhuyetsya sho rozv yazuye paradoks Princip Landauera vstanovlyuye nizhnyu mezhu kilkosti tepla yake komp yuter povinen generuvati dlya obrobki zadanogo obsyagu informaciyi hocha suchasni komp yuteri ye nabagato mensh efektivnimi Entropiya yak kilkist infromaciyi Detalnishi vidomosti z ciyeyi temi vi mozhete znajti v statti en Entropiya viznachayetsya v konteksti jmovirnisnoyi modeli Nezalezhni pidkidannya spravedlivoyi moneti mayut entropiyu po 1 bitu na pidkidannya Dzherelo yake zavzhdi porodzhuye dovgij ryadok B maye entropiyu 0 oskilki nastupnim simvolom zavzhdi bude B Entropijna shvidkist dzherela danih oznachaye userednene chislo bitiv na simvol potribne dlya jogo koduvannya Eksperimenti Shennona z peredbachennyam lyudmi pokazuyut shvidkist informaciyi na simvol anglijskoyu movoyu mizh 0 6 i 1 3 bita Algoritm stisnennya PPM mozhe dosyagati rivnya stisnennya v 1 5 biti na simvol anglomovnogo tekstu Zvernit uvagu na nastupni momenti z poperednogo prikladu Kilkist entropiyi ne zavzhdi ye cilim chislom bitiv Bagato bitiv danih mozhut ne nesti informaciyi Napriklad strukturi danih chasto zberigayut informaciyu nadmirno abo mayut identichni rozdili nezalezhno vid informaciyi v strukturi danih Shennonivske viznachennya entropiyi pri zastosuvanni do dzherela informaciyi mozhe viznachati minimalnu propusknu zdatnist kanalu neobhidnu dlya nadijnogo peredavannya dzherela u viglyadi zakodovanih dvijkovih cifr div zasterezhennya nizhche kursivom Cyu formulu mozhe buti vivedeno shlyahom obchislennya matematichnogo spodivannya kilkosti informaciyi yaka mistitsya v odnij cifri z dzherela informaciyi Div takozh teoremu Shennona Gartli Entropiya Shennona vimiryuye informaciyu yaka mistitsya v povidomlenni na protivagu do tiyeyi chastini povidomlennya yaka ye viznachenoyu abo peredbachuvanoyu Prikladi ostannogo vklyuchayut nadmirnist u strukturi movi ta statistichni vlastivosti yaki stosuyutsya chastot traplyannya par trijok tosho liter abo sliv Div lancyugi Markova Entropiya yak mira riznomanitnosti Dokladnishe Mira riznomanitnosti Entropiya ye odnim z dekilkoh sposobiv vimiryuvannya riznomanitnosti Zokrema entropiya Shennona ye logarifmom 1D indeksu istinnoyi riznomanitnosti z parametrom yakij dorivnyuye 1 Stisnennya danih Dokladnishe Stisnennya danih Entropiya efektivno obmezhuye produktivnist najsilnishogo mozhlivogo stisnennya bez vtrat yake mozhe buti realizovano teoretichno z dopomogoyu en abo praktichno iz zastosuvannyam koduvannya Haffmana Lempelya Ziva abo arifmetichnogo koduvannya Div takozh kolmogorovsku skladnist Na praktici dlya zahistu vid pomilok algoritmi stisnennya navmisno vklyuchayut deyaku rozumnu nadmirnist u viglyadi kontrolnih sum Svitovij tehnologichnij potencial dlya zberigannya ta peredavannya informaciyi Doslidzhennya 2011 roku v zhurnali Science ocinyuye svitovij tehnologichnij potencial dlya zberigannya ta peredavannya optimalno stisnenoyi informaciyi normalizovanij za najefektivnishimi algoritmami stisnennya dostupnimi v 2007 roci ocinyuyuchi takim chinom entropiyu tehnologichno dostupnih dzherel 60 65 Vsi chisla v entropijno stisnenih eksabajtah Tip informaciyi 1986 2007Zberigannya 2 6 295Shirokomovlennya 432 1900Telekomunikaciyi 0 281 65 Avtori ocinyuyut tehnologichnij potencial lyudstva u zberiganni informaciyi povnistyu entropijno stisnenoyi 1986 roku i znovu 2007 roku Voni dilyat informaciyu na tri kategoriyi zberigannya informaciyi na nosiyi otrimuvannya informaciyi cherez merezhi odnobichnogo shirokomovlennya ta obmin informaciyeyu cherez dvobichni telekomunikacijni merezhi Obmezhennya entropiyi yak kilkosti informaciyi Isnuye ryad pov yazanih z entropiyeyu ponyat yaki pevnim chinom zdijsnyuyut matematichnu kilkisnu ocinku obsyagu informaciyi vlasna informaciya okremogo povidomlennya abo simvolu vzyatogo iz zadanogo rozpodilu jmovirnosti entropiya zadanogo rozpodilu jmovirnosti povidomlen abo simvoliv ta entropijna shvidkist stohastichnogo procesu Dlya konkretnoyi poslidovnosti povidomlen abo simvoliv porodzhenoyi zadanim stohastichnim procesom takozh mozhe buti viznacheno shvidkist vlasnoyi informaciyi u vipadku stacionarnogo procesu vona zavzhdi dorivnyuvatime shvidkosti entropiyi Dlya porivnyannya riznih dzherel informaciyi abo vstanovlennya zv yazku mizh nimi vikoristovuyutsya j inshi Kilkosti informaciyi Vazhlivo ne plutati navedeni vishe ponyattya Yake z nih mayetsya na uvazi chasto mozhe buti zrozumilim lishe z kontekstu Napriklad koli htos govorit sho entropiya anglijskoyi movi stanovit blizko 1 bita na simvol voni naspravdi modelyuyut anglijsku movu yak stohastichnij proces i govoryat pro shvidkist yiyi entropiyi Shennon i sam vikoristovuvav cej termin takim chinom Prote yaksho mi vikoristovuyemo duzhe veliki bloki to ocinka posimvolnoyi entropijnoyi shvidkosti mozhe stati shtuchno zanizhenoyu Ce vidbuvayetsya tomu sho naspravdi rozpodil jmovirnosti poslidovnosti ne ye piznavanim tochno ce lishe ocinka Napriklad pripustimo sho rozglyadayutsya teksti vsih bud koli opublikovanih knig yak poslidovnist u yakij kozhen simvol ye tekstom ciloyi knigi Yaksho isnuye N opublikovanih knig i kozhnu knigu opublikovano lishe odnogo razu to ocinkoyu jmovirnosti kozhnoyi knigi ye 1 N a entropiyeyu v bitah ye log2 1 N log2 N Yak praktichnij kod ce vidpovidaye priznachennyu kozhnij knizi unikalnogo identifikatora i vikoristannya jogo zamist tekstu knigi bud koli koli potribno poslatisya na cyu knigu Ce nadzvichajno korisno dlya rozmov pro knigi ale ne duzhe korisno dlya harakterizuvannya kilkosti informaciyi okremih knig abo movi v cilomu nemozhlivo vidtvoriti knigu z yiyi identifikatora ne znayuchi rozpodilu jmovirnosti tobto povnogo tekstu vsih knig Klyuchova ideya polyagaye v tomu sho povinna bratisya do uvagi skladnist imovirnisnoyi modeli Kolmogorovska skladnist yavlyaye soboyu teoretichne uzagalnennya ciyeyi ideyi yake dozvolyaye rozglyadati kilkist informaciyi poslidovnosti nezalezhno vid konkretnoyi jmovirnisnoyi modeli vono rozglyadaye najkorotshu programu dlya universalnogo komp yutera yaka vivodit cyu poslidovnist Takoyu programoyu ye kod yakij dosyagaye entropijnoyi shvidkosti poslidovnosti dlya zadanoyi modeli plyus kodovij slovnik tobto jmovirnisna model ale vona ne mozhe buti najkorotshoyu Napriklad poslidovnistyu Fibonachchi ye 1 1 2 3 5 8 13 Pri rozglyadi ciyeyi poslidovnosti yak povidomlennya a kozhnogo chisla yak simvolu isnuye majzhe stilki zh simvoliv skilki ye simvoliv u povidomlenni dayuchi entropiyu blizko log2 n Takim chinom pershi 128 simvoliv poslidovnosti Fibonachchi mayut entropiyu priblizno 7 bit simvol Prote cyu poslidovnist mozhe buti virazheno za dopomogoyu formuli F n F n 1 F n 2 dlya n 3 4 5 F 1 1 F 2 1 i cya formula maye znachno nizhchu entropiyu i zastosovuyetsya do poslidovnosti Fibonachchi bud yakoyi dovzhini Obmezhennya entropiyi v kriptografiyi V kriptoanalizi entropiyu chasto grubo vikoristovuyut yak miru neperedbachuvanosti kriptografichnogo klyucha hocha yiyi spravzhnya neviznachenist ye nezmirnoyu Napriklad 128 bitovij klyuch yakij porodzheno rivnomirno vipadkovo maye 128 bit entropiyi Vin takozh vimagaye useredneno 2128 1 displaystyle 2 128 1 sprob dlya zlamu gruboyu siloyu Prote entropiya ne vidobrazhaye chislo potribnih sprob yaksho mozhlivi klyuchi vibirayut ne rivnomirno Natomist dlya vimiryuvannya zusil neobhidnih dlya ataki gruboyu siloyu mozhna vikoristovuvati miru sho nazivayut zdogadom angl guesswork Cherez nerivnomirnist rozpodiliv sho zastosovuyut v kriptografiyi mozhut vinikati j inshi problemi Napriklad rozglyanmo 1 000 000 cifrovij dvijkovij shifr Vernama iz zastosuvannyam viklyuchnogo abo Yaksho cej shifr maye 1 000 000 bit entropiyi ce chudovo Yaksho cej shifr maye 999 999 bit entropiyi yaki rozpodileno rivnomirno koli kozhen okremij bit shifru maye 0 999999 bit entropiyi to vin mozhe proponuvati dobru bezpeku Ale yaksho cej shifr maye 999 999 bit entropiyi tak sho pershij bit ye nezminnim a reshta 999 999 bitiv vibirayut vipadkovo to pershij bit shifrovanogo tekstu ne bude shifrovano vzagali Dani yak markovskij proces Zvichnij sposib viznachennya entropiyi dlya tekstu gruntuyetsya na markovskij modeli tekstu Dlya dzherela nulovogo poryadku kozhen simvol obirayetsya nezalezhno vid ostannih simvoliv dvijkovoyu entropiyeyu ye H S pilog2 pi displaystyle mathrm H mathcal S sum p i log 2 p i de pi ye jmovirnistyu i Dlya en pershogo poryadku takogo v yakomu jmovirnist viboru simvolu zalezhit lishe vid bezposeredno poperednogo simvolu entropijnoyu shvidkistyu ye H S ipi j pi j log2 pi j displaystyle mathrm H mathcal S sum i p i sum j p i j log 2 p i j dzherelo de i ye stanom deyakimi poperednimi simvolami a pi j displaystyle p i j ye jmovirnistyu j za zadanogo poperednogo simvolu i Dlya markovskogo dzherela drugogo poryadku entropijnoyu shvidkistyu ye H S ipi jpi j kpi j k log2 pi j k displaystyle mathrm H mathcal S sum i p i sum j p i j sum k p i j k log 2 p i j k b arna entropiya V zagalnomu vipadku b arna entropiya dzherela S displaystyle mathcal S S P z pervinnoyu abetkoyu S a1 an i diskretnim rozpodilom jmovirnosti P p1 pn de pi ye imovirnistyu ai skazhimo pi p ai viznachayetsya yak Hb S i 1npilogb pi displaystyle mathrm H b mathcal S sum i 1 n p i log b p i Zauvazhennya b u b arnij entropiyi ye chislom riznih simvoliv idealnoyi abetki yaka vikoristovuyetsya yak standartne mirilo dlya vimiryuvannya pervinnih abetok V teoriyi informaciyi dlya abetki dlya koduvannya informaciyi ye neobhidnimi i dostatnimi dva simvoli Tomu standartnim ye brati b 2 dvijkova entropiya Takim chinom entropiya pervinnoyi abetki z yiyi zadanim empirichnim rozpodilom imovirnosti ce chislo yake dorivnyuye chislu mozhlivo drobovomu simvoliv idealnoyi abetki z optimalnim rozpodilom imovirnosti neobhidnih dlya koduvannya kozhnogo simvolu pervinnoyi abetki Takozh zvernit uvagu sho optimalnij rozpodil imovirnosti tut oznachaye rivnomirnij rozpodil pervinna abetka z n simvoliv maye najvishu mozhlivu entropiyu dlya abetki z n simvoliv koli rozpodil imovirnosti abetki ye rivnomirnim Ciyeyu optimalnoyu entropiyeyu viyavlyayetsya logb n EfektivnistPervinna abetka z nerivnomirnim rozpodilom matime menshu entropiyu nizh yakbi ci simvoli mali rivnomirnij rozpodil tobto buli optimalnoyu abetkoyu Cyu defektivnist entropiyi mozhe buti virazheno vidnoshennyam yake nazivayetsya efektivnistyu cya citata potrebuye posilannya h X i 1np xi logb p xi logb n logn i 1np xi p xi displaystyle eta X sum i 1 n frac p x i log b p x i log b n log n prod i 1 n p x i p x i proyasniti Efektivnist ye korisnoyu dlya kilkisnoyi ocinki efektivnosti vikoristannya kanalu zv yazku Ce formulyuvannya takozh nazivayut normalizovanoyu entropiyeyu oskilki entropiya dilitsya na maksimalnu entropiyu logb n displaystyle log b n Krim togo efektivnosti bajduzhij vibir dodatnoyi bazi b pro sho svidchit nechutlivist do neyi v kincevomu logarifmi HarakterizuvannyaEntropiya Shennona en nevelikim chislom kriteriyiv pererahovanih nizhche Bud yake viznachennya entropiyi yake zadovolnyaye ci pripushennya maye viglyad K i 1npilog pi displaystyle K sum i 1 n p i log p i de K ye staloyu yaka vidpovidaye viborovi odinic vimiryuvannya Dali pi Pr X xi a Hn p1 pn H X Neperervnist Cya mira povinna buti neperervnoyu tak sho zmina znachen jmovirnostej na duzhe neznachnu velichinu povinna zminyuvati entropiyu lishe na neznachnu velichinu Simetrichnist Pri perevporyadkuvanni vihodiv xi cya mira povinna zalishatisya nezminnoyu Hn p1 p2 Hn p2 p1 displaystyle mathrm H n left p 1 p 2 ldots right mathrm H n left p 2 p 1 ldots right toshoMaksimum Cya mira povinna buti maksimalnoyu todi koli vsi vihodi ye odnakovo pravdopodibnimi neviznachenist ye najvishoyu koli vsi mozhlivi podiyi ye rivnojmovirnimi Hn p1 pn Hn 1n 1n logb n displaystyle mathrm H n p 1 ldots p n leq mathrm H n left frac 1 n ldots frac 1 n right log b n Dlya rivnojmovirnih podij entropiya povinna zrostati zi zbilshennyam chisla vihodiv Hn 1n 1n n logb n lt logb n 1 Hn 1 1n 1 1n 1 n 1 displaystyle mathrm H n bigg underbrace frac 1 n ldots frac 1 n n bigg log b n lt log b n 1 mathrm H n 1 bigg underbrace frac 1 n 1 ldots frac 1 n 1 n 1 bigg Dlya bezperervnih vipadkovih zminnih rozpodilom iz maksimalnoyu diferencialnoyu entropiyeyu ye bagatovimirnij normalnij rozpodil Aditivnist Velichina entropiyi povinna ne zalezhati vid togo yakij podil procesu na chastini rozglyadayetsya Cya ostannya funkcijna zalezhnist harakterizuye entropiyu sistemi z pidsistemami Vona vimagaye shobi entropiyu sistemi mozhlivo bulo obchisliti z entropij yiyi pidsistem yaksho vzayemodiyi mizh cimi pidsistemami ye vidomimi Pri zadanomu ansambli n rivnomirno rozpodilenih elementiv yaki podilyayutsya na k blokiv pidsistem z b1 bk elementami v kozhnomu entropiya vsogo ansamblyu povinna dorivnyuvati sumi entropiyi sistemi blokiv i okremih entropij blokiv kozhna z yakih ye zvazhenoyu na jmovirnist znahodzhennya v comu vidpovidnomu bloci Dlya dodatnih cilih chisel bi de b1 bk n Hn 1n 1n Hk b1n bkn i 1kbinHbi 1bi 1bi displaystyle mathrm H n left frac 1 n ldots frac 1 n right mathrm H k left frac b 1 n ldots frac b k n right sum i 1 k frac b i n mathrm H b i left frac 1 b i ldots frac 1 b i right Pri obranni k n b1 bn 1 ce oznachaye sho entropiya nezminnogo vihodu dorivnyuye nulevi H1 1 0 Ce oznachaye sho efektivnist pervinnoyi abetki z n simvolami mozhe buti viznacheno prosto yak taku sho dorivnyuye yiyi n arnij entropiyi Div takozh nadmirnist informaciyi Dodatkovi vlastivostiEntropiya Shennona zadovolnyaye nastupni vlastivosti dlya deyakih z yakih korisno interpretuvati entropiyu yak kilkist piznanoyi informaciyi abo usunenoyi neviznachenosti pri rozkritti znachennya vipadkovoyi velichini X Dodavannya abo usuvannya podij z nulovoyu jmovirnistyu ne vplivaye na entropiyu Hn 1 p1 pn 0 Hn p1 pn displaystyle mathrm H n 1 p 1 ldots p n 0 mathrm H n p 1 ldots p n dd Entropiya diskretnoyi vipadkovoyi zminnoyi ye nevid yemnim chislom H X 0 displaystyle mathrm H X geq 0 15 dd Za dopomogoyu nerivnosti Yensena mozhe buti pidtverdzheno shoH X E logb 1p X logb E 1p X logb n displaystyle mathrm H X operatorname E left log b left frac 1 p X right right leq log b left operatorname E left frac 1 p X right right log b n 29 dd Cya maksimalna entropiya logb n efektivno dosyagayetsya pervinnoyu abetkoyu yaka maye rivnomirnij rozpodil jmovirnosti neviznachenist ye maksimalnoyu koli vsi mozhlivi podiyi ye odnakovo jmovirnimi Entropiya abo obsyag informaciyi rozkritoyi shlyahom viznachennya X Y tobto viznachennya X ta Y odnochasno dorivnyuye informaciyi rozkritoyi shlyahom provedennya dvoh poslidovnih eksperimentiv spershu viyavlennya znachennya Y a potim viyavlennya znachennya X za umovi sho vi znayete znachennya Y Ce mozhe buti zapisano yakH X Y H X Y H Y H Y X H X displaystyle mathrm H X Y mathrm H X Y mathrm H Y mathrm H Y X mathrm H X dd Yaksho Y f X displaystyle Y f X de f displaystyle f ye funkciyeyu to H f X X 0 displaystyle H f X X 0 Zastosuvannya poperednoyi formuli do H X f X displaystyle H X f X dayeH X H f X X H f X H X f X displaystyle mathrm H X mathrm H f X X mathrm H f X mathrm H X f X dd otzhe H f X X H X displaystyle H f X X leq H X takim chinom entropiya velichini mozhe tilki zmenshuvatisya koli ostannya prohodit cherez funkciyu Yaksho X ta Y v ye dvoma nezalezhnimi vipadkovimi zminnimi to znannya znachennya Y ne vplivaye na nashe znannya pro znachennya X oskilki ci dvoye ne vplivayut odne na odne v silu nezalezhnosti H X Y H X displaystyle mathrm H X Y mathrm H X dd Entropiya dvoh odnochasnih podij ye ne bilshoyu za sumu entropij kozhnoyi z okremih podij i dorivnyuye yij yaksho ci dvi podiyi ye nezalezhnimi Tochnishe yaksho X ta Y ye dvoma vipadkovimi velichinami na odnomu j tomu zh imovirnisnomu prostori a X Y poznachaye yihnij dekartiv dobutok toH X Y H X H Y displaystyle mathrm H X Y leq mathrm H X mathrm H Y dd Entropiya H p displaystyle mathrm H p ye ugnutoyu za funkciyeyu masi jmovirnosti p displaystyle p tobto H lp1 1 l p2 lH p1 1 l H p2 displaystyle mathrm H lambda p 1 1 lambda p 2 geq lambda mathrm H p 1 1 lambda mathrm H p 2 dd dlya vsih funkcij masi jmovirnosti p1 p2 displaystyle p 1 p 2 ta 0 l 1 displaystyle 0 leq lambda leq 1 32Rozshirennya diskretnoyi entropiyi do neperervnogo vipadkuDiferencialna entropiya Dokladnishe Diferencialna entropiya Entropiyu Shennona obmezheno vipadkovimi velichinami yaki nabuvayut diskretnih znachen Vidpovidna formula dlya neperervnoyi vipadkovoyi velichini z funkciyeyu gustini jmovirnosti f x zi skinchennoyu abo neskinchennoyu oblastyu viznachennya X displaystyle mathbb X na dijsnij osi viznachayetsya analogichno z dopomogoyu navedenogo vishe virazhennya entropiyi yak matematichnogo spodivannya h f E ln f x Xf x ln f x dx displaystyle h f operatorname E ln f x int mathbb X f x ln f x dx Cyu formulu zazvichaj nazivayut nepere rvnoyu entropi yeyu angl continuous entropy abo diferencialnoyu entropiyeyu Poperednikom neperervnoyi entropiyi h f ye viraz funkcionalu H v en Hocha analogiya mizh oboma funkciyami j navodit na rozdumi musit buti postavleno nastupne pitannya chi ye diferencialna entropiya obgruntovanim rozshirennyam diskretnoyi entropiyi Shennona Diferencialnij entropiyi brakuye ryadu vlastivostej yakimi volodiye diskretna entropiya Shennona vona navit mozhe buti vid yemnoyu i vidtak bulo zaproponovano popravki zokrema en Shobi vidpovisti na ce pitannya mi musimo vstanoviti zv yazok mizh cimi dvoma funkciyami Mi hochemo otrimati zagalnu skinchennu miru pri pryamuvanni rozmiru zasikiv do nulya V diskretnomu vipadku rozmir zasikiv ye neyavnoyu shirinoyu kozhnogo z n skinchennih abo neskinchennih zasikiv chiyi jmovirnosti poznachayutsya cherez pn Oskilki mi robimo uzagalnennya do neperervnoyi oblasti viznachennya mi musimo zrobiti cyu shirinu yavnoyu Shobi zrobiti ce pochnimo z neperervnoyi funkciyi f diskretizovanoyi zasikami rozmiru D displaystyle Delta Zgidno teoremi pro serednye znachennya v kozhnomu zasiku isnuye take znachennya xi sho f xi D iD i 1 Df x dx displaystyle f x i Delta int i Delta i 1 Delta f x dx i vidtak integral funkciyi f mozhe buti nablizheno v rimanovomu sensi za dopomogoyu f x dx limD 0 i f xi D displaystyle int infty infty f x dx lim Delta to 0 sum i infty infty f x i Delta de cya granicya i rozmir zasiku pryamuye do nulya ye rivnocinnimi Poznachmo HD i f xi Dlog f xi D displaystyle mathrm H Delta sum i infty infty f x i Delta log left f x i Delta right i rozkrivayuchi cogo logarifma mi mayemo HD i f xi Dlog f xi i f xi Dlog D displaystyle mathrm H Delta sum i infty infty f x i Delta log f x i sum i infty infty f x i Delta log Delta Pri D 0 mi mayemo i f xi D f x dx 1 i f xi Dlog f xi f x log f x dx displaystyle begin aligned sum i infty infty f x i Delta amp to int infty infty f x dx 1 sum i infty infty f x i Delta log f x i amp to int infty infty f x log f x dx end aligned Ale zauvazhte sho log D pri D 0 otzhe nam potribne osoblive viznachennya diferencialu abo neperervnoyi entropiyi h f limD 0 HD log D f x log f x dx displaystyle h f lim Delta to 0 left mathrm H Delta log Delta right int infty infty f x log f x dx sho yak bulo skazano ranishe nazivayut diferencia lnoyu entropi yeyu angl differential entropy Ce oznachaye sho diferencialna entropiya ne ye graniceyu entropiyi Shennona pri n Vona radshe vidriznyayetsya vid granici entropiyi Shennona neskinchennim zsuvom div takozh stattyu pro en Vzyattya granici shilnosti diskretnih tochok Detalnishi vidomosti z ciyeyi temi vi mozhete znajti v statti en V rezultati vihodit sho na vidminu vid entropiyi Shennona diferencialna entropiya ne ye v cilomu dobroyu miroyu neviznachenosti abo informaciyi Napriklad diferencialna entropiya mozhe buti vid yemnoyu krim togo vona ne ye invariantnoyu vidnosno neperervnih peretvoren koordinat Cyu problemu mozhe buti proilyustrovano zminoyu odinic vimiryuvannya koli x ye rozmirnoyu velichinoyu f x todi matime odinici 1 x Argument logarifma musit buti bezrozmirnim inakshe vin ye nepravilnim bo taka diferencialna entropiya yak navedeno vishe bude nepravilnoyu Yaksho D displaystyle Delta ye deyakim standartnim znachennyam x tobto rozmirom zasiku i vidtak maye taki zh odinici vimiryuvannya to vidozminenu diferencialnu entropiyu mozhe buti zapisano v nalezhnomu viglyadi yak H f x log f x D dx displaystyle H int infty infty f x log f x Delta dx i rezultat bude odnakovim pri bud yakomu vibori odinic vimiryuvannya dlya x Naspravdi granicya diskretnoyi entropiyi pri N 0 vklyuchala bi takozh i chlen log N yakij v zagalnomu vipadku buv bi neskinchennim Ce ye ochikuvanim neperervni velichini pri diskretizaciyi zazvichaj matimut neskinchennu entropiyu en v dijsnosti ye miroyu togo naskilki rozpodil ye prostishim dlya opisu za rozpodil yakij ye rivnomirnim nad svoyeyu shemoyu kvantuvannya Vidnosna entropiya Detalnishi vidomosti z ciyeyi temi vi mozhete znajti v statti en Inshoyu korisnoyu miroyu entropiyi yaka odnakovo dobre pracyuye v diskretnomu ta neperervnomu vipadkah ye vidno sna entropi ya angl relative entropy rozpodilu Vona viznachayetsya yak vidstan Kulbaka Lejblera vid rozpodilu do etalonnoyi miri m nastupnim chinom Pripustimo sho rozpodil imovirnosti p ye absolyutno neperervnim vidnosno miri m tobto maye viglyad p dx f x m dx dlya deyakoyi nevid yemnoyi m integrovanoyi funkciyi f z m integralom 1 todi vidnosnu entropiyu mozhe buti viznacheno yak DKL p m log f x p dx f x log f x m dx displaystyle D mathrm KL p m int log f x p dx int f x log f x m dx V takomu viglyadi vidnosna entropiya uzagalnyuye z tochnistyu do zmini znaka yak diskretnu entropiyu koli mira m ye lichilnoyu miroyu tak i diferencialnu entropiyu koli mira m ye miroyu Lebega Yaksho mira m i sama ye rozpodilom jmovirnosti to vidnosna entropiya ye nevid yemnoyu i nulovoyu yaksho p m yak miri Vona viznachayetsya dlya bud yakogo prostoru mir otzhe ne zalezhit vid koordinat i ye invariantnoyu vidnosno pereparametrizaciyi koordinat yaksho peretvorennya miri m beretsya do uvagi pravilno Vidnosna entropiya i neyavno entropiya ta diferencialna entropiya zalezhat vid bazovoyi miri m Zastosuvannya v kombinatoriciEntropiya stala korisnoyu velichinoyu v kombinatorici Nerivnist Lyumisa Uyitni Prostim prikladom cogo ye alternativne dovedennya en dlya bud yakoyi pidmnozhini A Zd mi mayemo A d 1 i 1d Pi A displaystyle A d 1 leq prod i 1 d P i A de Pi ye ortogonalnoyu proyekciyeyu v i j koordinati Pi A x1 xi 1 xi 1 xd x1 xd A displaystyle P i A x 1 ldots x i 1 x i 1 ldots x d x 1 ldots x d in A Ce dovedenya viplivaye yak prostij naslidok en yaksho X1 Xd ye vipadkovimi velichinami a S1 Sn ye pidmnozhinami 1 d takimi sho kozhne cile chislo mizh 1 i d lezhit tochno v r z cih pidmnozhin to H X1 Xd 1r i 1nH Xj j Si displaystyle mathrm H X 1 ldots X d leq frac 1 r sum i 1 n mathrm H X j j in S i de Xj j Si displaystyle X j j in S i ye dekartovim dobutkom vipadkovih velichin Xj z indeksami j v Si tomu rozmirnist cogo vektora dorivnyuye rozmirovi Si Mi zrobimo naris yak z cogo viplivaye Lyumis Uyitni spravdi nehaj X ye rivnomirno rozpodilenoyu vipadkovoyu velichinoyu zi znachennyami v A i takoyu sho kozhna tochka z A traplyayetsya z odnakovoyu jmovirnistyu Todi zgidno dodatkovih vlastivostej entropiyi zgaduvanih vishe H X log A de A poznachaye potuzhnist A Nehaj Si 1 2 i 1 i 1 d Diapazon Xj j Si displaystyle X j j in S i mistitsya v Pi A i otzhe H Xj j Si log Pi A displaystyle mathrm H X j j in S i leq log P i A Teper zastosujmo ce shobi obmezhiti pravu chastinu nerivnosti Shirera i pidnesti do stepenya protilezhni chastini nerivnosti yaku vi otrimali v rezultati Nablizhennya do binomialnogo koeficiyentu Dlya cilih chisel 0 lt k lt n pokladimo q k n Todi 2nH q n 1 nk 2nH q displaystyle frac 2 n mathrm H q n 1 leq tbinom n k leq 2 n mathrm H q de H q qlog2 q 1 q log2 1 q displaystyle mathrm H q q log 2 q 1 q log 2 1 q 43 Nizhche navedeno shematichne dovedennya Zauvazhte sho nk qqn 1 q n nq displaystyle tbinom n k q qn 1 q n nq ye odnim iz chleniv sumi i 0n ni qi 1 q n i q 1 q n 1 displaystyle sum i 0 n tbinom n i q i 1 q n i q 1 q n 1 Vidpovidno z nerivnosti nk qk 1 q n k 1 displaystyle tbinom n k q k 1 q n k leq 1 pislya logarifmuvannya otrimuyetsya verhnya mezha Dlya otrimannya nizhnoyi mezhi spochatku shlyahom pevnih peretvoren pokazuyetsya sho dodanok nk qqn 1 q n nq displaystyle tbinom n k q qn 1 q n nq ye najbilshim chlenom u navedenij sumi Ale todi nk qqn 1 q n nq 1n 1 displaystyle binom n k q qn 1 q n nq geq frac 1 n 1 oskilki binom mistit n 1 chleniv Zvidsi viplivaye nizhnya mezha Navedeni rezultati interpretuyutsya napriklad takim chinom chislo dvijkovih strichok dovzhini n yaki mistyat rivno k odinic mozhna ociniti yak 2nH k n displaystyle 2 n mathrm H k n Div takozhPortal Matematika Vzayemna informaciya Vipadkovist Vidstan Gemminga Vidstan Levenshtejna en Entropijna shvidkist Entropijne koduvannya shema koduvannya yaka priznachaye kodi simvolam takim chinom shobi dovzhini kodiv vidpovidali jmovirnostyam simvoliv en en en v dinamichnih sistemah Entropiya Renyi uzagalnennya entropiyi Shennona vona ye odniyeyu z simejstva funkcionaliv dlya kilkisnoyi ocinki riznomanittya neviznachenosti abo vipadkovosti sistemi Entropiya Callisa Indeks riznomanitnosti alternativni pidhodi do kilkisnoyi ocinki riznomanitnosti v rozpodili jmovirnosti Indeks Tejla Indeks Shennona Informaciya za Fisherom en en en mira rozriznyuvanosti mizh dvoma kvantovimi stanami Mnozhnik Lagranzha Negentropiya en Tipoglikemiya en Perehresna entropiya ye miroyu userednenogo chisla bitiv neobhidnih dlya identifikaciyi podiyi z naboru mozhlivostej mizh dvoma rozpodilami jmovirnosti Perpleksivnist Spilna entropiya ce mira togo yak bagato entropiyi mistitsya v spilnij sistemi z dvoh vipadkovih velichin Umovna entropiya en inshi miri statistichnoyi dispersiyi dlya nominalnih rozpodilivPrimitkiPathria R K Beale Paul 2011 Academic Press s 51 ISBN 978 0123821881 Arhiv originalu za 17 chervnya 2020 Procitovano 13 grudnya 2018 angl Shannon Claude E July October 1948 A Mathematical Theory of Communication en 27 3 379 423 doi 10 1002 j 1538 7305 1948 tb01338 x zaarhivovano zvidsi 20 chervnya 2014 u Wayback Machine angl Shannon Claude E 1948 PDF en 27 Arhiv originalu PDF za 15 lyutogo 2019 Procitovano 13 grudnya 2018 July and October angl Schneier B Applied Cryptography Second edition John Wiley and Sons angl Borda Monica 2011 Springer ISBN 978 3 642 20346 6 Arhiv originalu za 15 lyutogo 2017 Procitovano 6 chervnya 2017 angl Han Te Sun amp Kobayashi Kingo 2002 American Mathematical Society ISBN 978 0 8218 4256 0 Arhiv originalu za 15 lyutogo 2017 Procitovano 6 chervnya 2017 angl Schneider T D Information theory primer with an appendix on logarithms nedostupne posilannya National Cancer Institute 14 April 2007 angl Carter Tom March 2014 PDF Santa Fe Arhiv originalu PDF za 4 chervnya 2016 Procitovano 4 serpnya 2017 angl Compare Boltzmann Ludwig 1896 1898 Vorlesungen uber Gastheorie 2 Volumes Leipzig 1895 98 UB O 5262 6 English version Lectures on gas theory Translated by Stephen G Brush 1964 Berkeley University of California Press 1995 New York Dover ISBN 0 486 68455 5 angl Mark Nelson 24 August 2006 Arhiv originalu za 1 bereznya 2018 Procitovano 27 listopada 2008 angl The World s Technological Capacity to Store Communicate and Compute Information 27 lipnya 2013 u Wayback Machine Martin Hilbert and Priscila Lopez 2011 Science 332 6025 free access to the article through here martinhilbert net WorldInfoCapacity html angl Massey James 1994 PDF Proc IEEE International Symposium on Information Theory Arhiv originalu PDF za 1 sichnya 2014 Procitovano 31 grudnya 2013 angl Malone David Sullivan Wayne 2005 PDF Proceedings of the Information Technology amp Telecommunications Conference Arhiv originalu PDF za 15 kvitnya 2016 Procitovano 31 grudnya 2013 angl Pliam John 1999 Guesswork and variation distance as measures of cipher security International Workshop on Selected Areas in Cryptography doi 10 1007 3 540 46513 8 5 angl Thomas M Cover Joy A Thomas 18 lipnya 2006 Elements of Information Theory Hoboken New Jersey Wiley ISBN 978 0 471 24195 9 angl Aoki New Approaches to Macroeconomic Modeling angl Probability and Computing M Mitzenmacher and E Upfal Cambridge University Press angl LiteraturaPidruchniki z teoriyi informaciyi Teoriya informaciyi i koduvannya navch posib A Ya Kulik S G Krivogubchenko Vinnic nac tehn un t Vinnicya 2008 145 c Teoriya informaciyi navch posib N O Tulyakova Sum derzh un t Sumi 2008 212 c Teoriya informaciyi navch posib V V Dyadichev B M Lokotosh A V Kolyesnikov Shidnoukr nac un t im V Dalya Lugansk 2009 249 c Teoriya informaciyi ta koduvannya V S Vasilenko O Ya Matov NAN Ukrayini In t probl reyestraciyi informaciyi Kiyiv IPRI NAN Ukrayini 2014 439 c Teoriya informaciyi ta koduvannya pidruchnik V I Barsov V A Krasnobayev Z V Barsova O I Tirtishnikov I V Avdyeyev red V I Barsov MONMS Ukrayini Ukr inzh ped akad Poltav nac tehn un t im Yu Kondratyuka Poltava 2011 321 c Teoriya informaciyi ta koduvannya Pidruch dlya stud vish tehn navch zakl Yu P Zhurakovskij V P Poltorak K Visha shk 2001 255 c Arndt C 2004 Information Measures Information and its Description in Science and Engineering Springer ISBN 978 3 540 40855 0 angl Cover T M Thomas J A 2006 Elements of information theory 2nd Edition Wiley Interscience ISBN 0 471 24195 4 angl Gray R M 2011 Entropy and Information Theory Springer angl en Information Theory Inference and Learning Algorithms 17 lyutogo 2016 u Wayback Machine Cambridge Cambridge University Press 2003 ISBN 0 521 64298 1 angl Martin Nathaniel F G amp England James W 2011 Cambridge University Press ISBN 978 0 521 17738 2 Arhiv originalu za 19 bereznya 2015 Procitovano 6 chervnya 2017 angl Martin N Inglend Dzh Matematicheskaya teoriya entropii M Mir 1988 350 s ros Shannon C E Weaver W 1949 The Mathematical Theory of Communication Univ of Illinois Press ISBN 0 252 72548 4 angl Stone J V 2014 Chapter 1 of Information Theory A Tutorial Introduction 3 chervnya 2016 u Wayback Machine University of Sheffield England ISBN 978 0956372857 angl Hemming R V 1983 Teoriya informacii i teoriya kodirovaniya Moskva Radio i Svyaz ros PosilannyaHazewinkel Michiel red 2001 Entropy Matematichna enciklopediya Springer ISBN 978 1 55608 010 4 angl Vvedennya v entropiyu ta informaciyu 17 travnya 2016 u Wayback Machine na en angl Entropy 31 travnya 2016 u Wayback Machine mizhdisciplinarnij zhurnal pro vsi aspekti ponyattya entropiyi Vidkritij dostup angl angl Aplet Java yakij predstavlyaye eksperiment Shennona z obchislennya entropiyi anglijskoyi movi 13 travnya 2016 u Wayback Machine angl An Intuitive Guide to the Concept of Entropy Arising in Various Sectors of Science vikikniga pro interpretaciyu ponyattya entropiyi angl Network Event Detection With Entropy Measures 13 kvitnya 2016 u Wayback Machine Dr Raimund Eimann University of Auckland PDF 5993 kB doktorska pracya yaka demonstruye yak vimiryuvannya entropiyi mozhut zastosovuvatisya dlya viyavlennya merezhevih anomalij angl Entropy 4 chervnya 2016 u Wayback Machine repozitarij en realizacij entropiyi Shennona riznimi movami programuvannya Information Theory for Intelligent People 13 chervnya 2020 u Wayback Machine Korotke vvedennya do aksiom teoriyi informaciyi entropiyi vzayemnoyi informaciyi vidstani Kulbaka Lejblera ta vidstani Yensena Shennona angl Interaktivnij instrument dlya obchislennya entropiyi prostogo tekstu ASCII 15 kvitnya 2022 u Wayback Machine Interaktivnij instrument dlya obchislennya entropiyi dvijkovogo vhodu