Теорія інформації

Тео́рія інформ́ації (англ. Information theory) — це математичне дослідження кількісного вираження, зберігання та передавання інформації. Заснував цю галузь і забезпечив їй надійну основу Клод Шеннон у 1940-х роках, хоча ранній внесок до цьому напряму зробили в 1920-х роках праці Гаррі Найквіста та Ральфа Гартлі. Вона перебуває на перетині електронної інженерії, математики, статистики, інформатики, нейробіології, фізики та електротехніки.

Ключовою мірою в теорії інформації є ентропія. Ентропія вимірює рівень невизначеності щодо значення випадкової величини або результату випадкового процесу. Наприклад, визначення результату підкидання симетричної монети (що має два рівноймовірні результати) дає менше інформації (меншу ентропію, меншу невизначеність), аніж визначення результату кидання гральної кісточки (що має шість рівноймовірних результатів). До інших важливих мір у теорії інформації належать взаємна інформація, пропускна спроможність каналу, показники помилок та відносна ентропія. До важливих підрозділів теорії інформації належать кодування джерела, алгоритмічна теорія складності, алгоритмічна теорія інформації та інформаційно-теоретична безпека.

До застосувань основних предметів теорії інформації належать кодування джерела/стиснення даних (наприклад, для файлів zip) та канальне кодування/виявляння та виправляння помилок (наприклад, для DSL). Її вплив був вирішальним для успіху місій «Вояджер» до глибокого космосу, винайдення компакт-диска, можливості мобільних телефонів і розвитку Інтернету й штучного інтелекту. Ця теорія також знайшла застосування й в інших сферах, як-от індуктивній статистиці, криптографії, нейробіології, сприйнятті, обробці сигналів, мовознавстві, еволюції та функціюванні молекулярних кодів (біоінформатиці), теплофізиці, молекулярній динаміці, чорних дірах, квантових обчисленнях, інформаційному пошуку, збиранні інформації, виявлянні плагіату, розпізнаванні образів, виявлянні аномалій, музичній аналітиці, створенні живопису, проєктуванні систем зображування, вивченні космічного простору, вимірності простору, і навіть епістемології.

Огляд

Теорія інформації вивчає передавання, обробку, виділяння та використання інформації. Абстрактно інформацію можливо розглядати як розв'язання невизначеності. У випадку передавання інформації зашумленим каналом це абстрактне поняття формалізував 1948 року Клод Шеннон у статті під назвою «Математична теорія зв'язку», в якій інформацію розглянуто як набір можливих повідомлень, а метою є передавання цих повідомлень зашумленим каналом, щоби приймач міг відтворити повідомлення з низькою ймовірністю помилки, незважаючи на шум каналу. Головний результат Шеннона, теорема про кодування для зашумленого каналу, показав, що за великої кількості використань каналу швидкість передачі інформації, яка асимптотично досяжна, дорівнює пропускній спроможності каналу, величині, яка залежить лише від статистичних характеристик каналу, яким передають повідомлення.

Теорія кодування займається пошуком конкретних методів, званих кодами (англ. codes), для підвищення ефективності та зниження рівня помилок при передаванні даних зашумленими каналами, з наближенням до пропускної спроможності каналу. Ці коди можливо умовно поділити на методи стискання даних (кодування джерела) та виправляння помилок (кодування каналу). У випадку останнього знадобилося багато років, щоби знайти методи, можливість яких довів Шеннон.^{[джерело?]}

Третій клас кодів у теорії інформації — алгоритми шифрування (як коди, так і шифри). Поняття, методи й результати з теорії кодування та теорії інформації широко використовують у криптографії та криптоаналізі, наприклад, одиничний бан.^{[джерело?]}

Історичне підґрунтя

Знаковою подією, що заклала основу дисципліни теорії інформації та привернула до неї негайну світову увагу, стала публікація класичної статті Клода Е. Шеннона «Математична теорія зв'язку» в Bell System Technical Journal у липні та жовтні 1948 року. Історик Джеймс Ґлік оцінив цю статтю як найважливіше досягнення 1948 року, вище за транзистор, зазначивши, що ця праця була «навіть глибшою й фундаментальнішою» за транзистор. Шеннон став відомим як «батько теорії інформації». Він викладав деякі зі своїх початкових ідей щодо теорії інформації ще 1939 року в листі до Веннівера Буша.

До цієї статті обмежені інформаційно-теоретичні ідеї розробили в Bell Labs, при цьому всі вони неявно виходили з однакової ймовірності подій. У своїй статті 1924 року «Деякі чинники, які впливають на швидкість телеграфу» (англ. Certain Factors Affecting Telegraph Speed) Гаррі Найквіст помістив теоретичний розділ, де кількісно визначив «відомості» (англ. "intelligence") та «швидкість лінії» (англ. "line speed"), з якою їх можливо передавати комунікаційною системою, встановивши співвідношення W = K log m (що нагадує сталу Больцмана), де W — швидкість передачі відомостей, m — кількість різних рівнів напруги, з яких можна обирати на кожному часовому кроці, а K — стала. Стаття Ральфа Гартлі 1928 року «Передавання інформації» (англ. Transmission of Information) використовує термін інформація (англ. information) як вимірювану величину, що відображає здатність приймача розрізняти одну послідовність символів з будь-якими іншими, тим самим кількісно визначаючи інформацію як H = log Sⁿ = n log S, де S — кількість можливих символів, а n — кількість символів у передаванні. Отже, одиницею інформації була десяткова цифра, яку згодом іноді називали гартлі на його честь як одиницю, шкалу або міру інформації. 1940 року Алан Тюрінг використав подібні ідеї як частину статистичного аналізу для розшифровки німецьких шифрів «Енігми» під час Другої світової війни.^{[джерело?]}

Більшість математичного апарату теорії інформації для різноймовірнісних подій розробили для галузі термодинаміки Людвіг Больцман та Джозая Віллард Ґіббз. Зв'язки між інформаційною ентропією та термодинамічною ентропією, включно з важливими внесками Рольфа Ландауера 1960-х років, розглянуто в статті «Ентропія в термодинаміці та теорії інформації».^{[джерело?]}

У революційній і новаторській статті Шеннона, роботу над якою було значною мірою завершено в Bell Labs до кінця 1944 року, Шеннон уперше представив якісну та кількісну модель зв'язку як статистичний процес, що лежить в основі теорії інформації, розпочавши з твердження:

Основна задача зв'язку полягає в тому, щоби відтворити в одній точці, точно або приблизно, повідомлення, вибране в іншій точці. Оригінальний текст (англ.) The fundamental problem of communication is that of reproducing at one point, either exactly or approximately, a message selected at another point.

З нею прийшли ідеї:

• інформаційної ентропії та надмірності джерела, та їхньої значущості через теорему про кодування джерела;
• взаємної інформації та пропускної спроможності зашумленого каналу, включно з обіцянкою бездоганної передачі без втрат, яку дає теорема про кодування для зашумленого каналу;
• практичного результату закону Шеннона — Гартлі для пропускної спроможності гауссового каналу; а також
• біта — нового способу бачення найфундаментальнішої одиниці інформації.^{[джерело?]}

Кількості інформації

Теорія інформації ґрунтується на теорії ймовірностей та статистиці, де кількісно виражену інформацію зазвичай описують у бітах. Теорія інформації часто займається вимірюванням інформації в розподілах, пов'язаних із випадковими величинами. Однією з найважливіших мір є ентропія, що є основою для багатьох інших мір. Ентропія дозволяє кількісно виразити міру інформації в окремій випадковій величині. Іншим корисним поняттям є взаємна інформація, визначена для двох випадкових величин, яка описує міру інформації, спільної між цими величинами, що можливо використовувати для опису їхньої кореляції. Перша величина є властивістю розподілу ймовірності випадкової величини й визначає границю швидкості, з якою дані, породжені незалежними зразками із заданим розподілом, можливо надійно стиснути. Друга є властивістю спільного розподілу двох випадкових величин і є максимальною швидкістю надійного передавання зашумленим каналом в границі довжин блоків, коли статистика каналу визначається цим спільним розподілом.

Вибір основи логарифму в наступних формулах визначає вживану одиницю інформаційної ентропії. Загальновживаною одиницею інформації є біт або шеннон, що ґрунтується на двійковому логарифмі. До інших одиниць належать нат, що ґрунтується на натуральному логарифмі, та десяткова цифра, що ґрунтується на десятковому логарифмі.

Далі вираз вигляду p log p, коли p = 0, вважають за згодою нульовим. Це виправдано тим, що $\lim _{p\rightarrow 0+}p\log p=0$ для будь-якої основи логарифму.

Ентропія інформаційного джерела

Виходячи з функції маси ймовірності кожного символу джерела, що передається, ентропію Шеннона H у бітах (на символ) задають як

$H=-\sum _{i}p_{i}\log _{2}(p_{i})$

де p_i — ймовірність трапляння i-того можливого значення символу джерела. Це рівняння дає ентропію в одиницях «біт» (на символ), оскільки воно використовує логарифм з основою 2, і таку міру ентропії на основі логарифму за основою 2 іноді називають шенноном на його честь. Ентропію також часто обчислюють, використовуючи натуральний логарифм (з основою e, де e — число Ейлера), що дає вимірювання ентропії в натах на символ й іноді спрощує аналіз, усуваючи потребу в додаткових сталих у формулах. Можливі й інші основи, хоча їх використовують рідше. Наприклад, логарифм з основою 2⁸ = 256 дає вимірювання в байтах на символ, а логарифм з основою 10 — у десяткових цифрах (або гартлі) на символ.

Інтуїтивно, ентропія H_X дискретної випадкової величини X є мірою невизначеності (англ. uncertainty), пов'язаної зі значенням X, коли відомий лише її розподіл.

Ентропія джерела, яке видає послідовність з N символів, які незалежні й однаково розподілені (н. о. р.), дорівнює N ⋅ H біт (на повідомлення з N символів). Якщо символи даних джерела однаково розподілені, але не незалежні, ентропія повідомлення довжиною N буде меншою за N ⋅ H.

Ентропія проби Бернуллі як функція ймовірності успіху, часто звана функцією бінарної ентропії, H_b(p). Ця ентропія досягає максимуму в 1 біт на пробу, коли два можливі результати рівноймовірні, як у випадку підкидання симетричної монети.

Якщо передати 1000 бітів (нулів та одиниць), але значення кожного з цих бітів відоме приймачу (має певне значення з упевненістю) ще до передачі, то очевидно, що жодної інформації не передано. Якщо ж кожен біт незалежно й однаково правдоподібно може бути 0 або 1, то передано 1000 шеннонів інформації (частіше званих бітами). Між цими двома крайнощами інформацію можливо кількісно виразити наступним чином. Якщо $\mathbb {X}$ — множина всіх повідомлень {x₁, ..., x_n}, якими може бути X, а p(x) — імовірність деякого $x\in \mathbb {X}$, то ентропію H величини X визначають як

$H(X)=\mathbb {E} _{X}[I(x)]=-\sum _{x\in \mathbb {X} }p(x)\log p(x).$

(Тут I(x) — власна інформація, що є внеском ентропії окремого повідомлення, а $\mathbb {E} _{X}$ — математичне сподівання.) Однією з властивостей ентропії є те, що вона максимізується, коли всі повідомлення у просторі повідомлень рівноймовірні, тобто p(x) = 1/n, тобто найнепередбачуваніші, й у такому випадку H(X) = log n.

Особливий випадок інформаційної ентропії для випадкової величини з двома можливими результатами — функція бінарної ентропії, зазвичай з логарифмом за основою 2, що відтак має одиницею шеннон (Sh):

$H_{\mathrm {b} }(p)=-p\log _{2}p-(1-p)\log _{2}(1-p).$

Спільна ентропія

Спільна ентропія (англ. joint entropy) двох дискретних випадкових величин X та Y — це просто ентропія їхньої двійки: (X, Y). Це означає, що якщо X та Y незалежні, то їхня спільна ентропія дорівнює сумі їхніх окремих ентропій.

Наприклад, якщо (X, Y) подає положення шахової фігури — X це рядок, а Y це стовпець, то спільна ентропія рядка та стовпця фігури буде ентропією її положення.

$H(X,Y)=\mathbb {E} _{X,Y}[-\log p(x,y)]=-\sum _{x,y}p(x,y)\log p(x,y)\,$

Попри схожість позначень, спільну ентропію не слід плутати з перехресною ентропією (англ. cross-entropy).

Умовна ентропія (неоднозначність)

Умовна ентропія (англ. conditional entropy) або умовна невизначеність (англ. conditional uncertainty) величини X за заданої випадкової величини Y (також звана неоднозначністю X щодо Y, англ. equivocation) — це усереднена умовна ентропія за Y:

$H(X|Y)=\mathbb {E} _{Y}[H(X|y)]=-\sum _{y\in Y}p(y)\sum _{x\in X}p(x|y)\log p(x|y)=-\sum _{x,y}p(x,y)\log p(x|y).$

Оскільки ентропія може бути обумовлена випадковою величиною (загальна умовна ентропія) або конкретним значенням цієї випадкової величини (часткова умовна ентропія), слід бути уважними, щоби не плутати ці два визначення умовної ентропії, перше з яких є поширенішим. Основною властивістю цієї форми умовної ентропії є те, що

$H(X|Y)=H(X,Y)-H(Y).\,$

Взаємна інформація (трансінформація)

Взаємна інформація (англ. mutual information) вимірює кількість інформації про одну випадкову величину, яку можливо отримати, спостерігаючи іншу. Вона важлива в комунікаціях, де її можливо використовувати для максимізування кількості спільної інформації між передаваним та отримуваним сигналами. Взаємну інформацію X відносно Y визначають як

$I(X;Y)=\mathbb {E} _{X,Y}[SI(x,y)]=\sum _{x,y}p(x,y)\log {\frac {p(x,y)}{p(x)\,p(y)}}$

де SI (англ. Specific mutual Information, конкретна взаємна інформація) — це поточкова взаємна інформація.

Основна властивість взаємної інформації полягає в тому, що

$I(X;Y)=H(X)-H(X|Y).\,$

Тобто, знаючи Y, можливо заощадити в середньому I(X; Y) бітів при кодуванні X порівняно з ситуацією, коли Y невідома.

Взаємна інформація симетрична:

$I(X;Y)=I(Y;X)=H(X)+H(Y)-H(X,Y).\,$

Взаємну інформацію можливо виразити як усереднення розходження Кульбака — Лейблера (приросту інформації) апостеріорного розподілу ймовірності X за заданого значення Y з апріорним розподілом X:

$I(X;Y)=\mathbb {E} _{p(y)}[D_{\mathrm {KL} }(p(X|Y=y)\|p(X))].$

Іншими словами, це міра того, наскільки в середньому зміниться розподіл імовірності X, якщо задано значення Y. Її часто переобчислюють як розходження добутку відособлених розподілів зі справжнім спільним розподілом:

$I(X;Y)=D_{\mathrm {KL} }(p(X,Y)\|p(X)p(Y)).$

Взаємна інформація тісно пов'язана з критерієм логарифмічного відношення правдоподібностей у контексті таблиць спряженості та поліноміального розподілу, а також із критерієм χ² Пірсона: взаємну інформацію можливо вважати статистикою для оцінювання незалежності пари змінних, і вона має добре визначений асимптотичний розподіл.

Розходження Кульбака — Лейблера (приріст інформації)

Розходження Кульбака — Лейблера (англ. Kullback–Leibler divergence, або розходження інформації, англ. information divergence, приріст інформації, англ. information gain, чи відносна ентропія, англ. relative entropy) — це спосіб порівняння двох розподілів: «істинного» розподілу ймовірності $p(X)$ та довільного розподілу $q(X)$. Якщо ми стискаємо дані, вважаючи, що їхній розподіл це $q(X)$, тоді як насправді правильний розподіл це $p(X)$, розходження Кульбака–Лейблера визначає середню кількість додаткових бітів на дані, необхідних для стискання. Його відтак визначають як

$D_{\mathrm {KL} }(p(X)\|q(X))=\sum _{x\in X}-p(x)\log {q(x)}\,-\,\sum _{x\in X}-p(x)\log {p(x)}=\sum _{x\in X}p(x)\log {\frac {p(x)}{q(x)}}.$

Хоча іноді його й використовують як «метрику відстані», КЛ-розходження не є справжньою метрикою, оскільки воно не симетричне й не задовольняє нерівність трикутника (що робить його напів-квазиметрикою).

Іншим тлумаченням КЛ-розходження є «зайва несподіваність» (англ. "unnecessary surprise"), створювана апріорним розподілом у порівнянні з істинним: припустімо, що число X буде випадковим чином обрано з дискретної множини з розподілом ймовірності $p(x)$. Якщо Аліса знає істинний розподіл $p(x)$, а Боб вважає (має апріорне переконання), що цим розподілом є $q(x)$, то для Боба побачене значення X у середньому буде більш несподіваним, аніж для Аліси. КЛ-розходження є (об'єктивним) очікуваним значенням (суб'єктивної) несподіваності для Боба, мінус несподіваність для Аліси, виміряним у бітах, якщо логарифм взято за основою 2. Таким чином, міру того, наскільки «помилковим» є апріорне переконання Боба, можливо кількісно виразити у вигляді очікуваної «зайвої несподіваності» для нього.

Спрямована інформація

Спрямована інформація (англ. directed Information) $I(X^{n}\to Y^{n})$ — це міра в теорії інформації, що кількісно визначає інформаційний потік від випадкового процесу $X^{n}=\{X_{1},X_{2},\dots ,X_{n}\}$ до випадкового процесу $Y^{n}=\{Y_{1},Y_{2},\dots ,Y_{n}\}$. Термін спрямована інформація запровадив Джеймс Мессі, її визначено як

$I(X^{n}\to Y^{n})\triangleq \sum _{i=1}^{n}I(X^{i};Y_{i}|Y^{i-1})$,

де $I(X^{i};Y_{i}|Y^{i-1})$ — умовна взаємна інформація $I(X_{1},X_{2},...,X_{i};Y_{i}|Y_{1},Y_{2},...,Y_{i-1})$.

На відміну від взаємної інформації, спрямована інформація не симетрична. $I(X^{n}\to Y^{n})$ вимірює кількість інформації, що передається причинно^{[прояснити: ком.]} від $X^{n}$ до $Y^{n}$. Спрямована інформація знаходить широке застосування в задачах, де важливу роль відіграє причинність, як-от пропускна спроможність каналу зі зворотним зв'язком, пропускна спроможність дискретних мереж без пам'яті зі зворотним зв'язком, ставки з причинною додатковою інформацією, стиснення з причинною додатковою інформацією, постановки комунікації керування в реальному часі, та у статистичній фізиці.

Інші кількості

До інших важливих інформаційно-теоретичних кількостей належать ентропія Реньї та ентропія Цалліса (узагальнення поняття ентропії), диференціальна ентропія (узагальнення кількостей інформації для неперервних розподілів) та умовна взаємна інформація. Також було запропоновано прагматичну інформацію як міру кількості інформації, використаної для ухвалення рішення.

Теорія кодування

Зображення подряпин на зчитуваній поверхні CD-R. Музичні й інформаційні CD кодують з використанням кодів з виправлянням помилок, тому їх можливо прочитати навіть за наявності незначних подряпин, використовуючи виявляння й виправляння помилок.

Теорія кодування — одне з найважливіших і найбезпосередніших застосувань теорії інформації. Її можливо поділити на теорію кодування джерела та теорію кодування каналу. Використовуючи статистичний опис даних, теорія інформації визначає кількість бітів, необхідних для опису даних, що є інформаційною ентропією джерела.

• Стиснення даних (кодування джерела): для задачі стиснення існують дві постановки:
  • стиснення без втрат: дані мусять відновлюватися точно;
  • стиснення з утратами: виділяє стільки бітів, скільки необхідно для відновлення даних із заданим рівнем точності, що вимірюється функцією спотворення. Цей підрозділ теорії інформації називають теорією швидкості — спотворення (англ. rate–distortion theory).
• Коди з виправлянням помилок (кодування каналу): тоді як стиснення даних усуває якомога більше надмірності, код з виправлянням помилок додає саме ту надмірність (тобто виправляння помилок), яка необхідна для ефективного й надійного передавання даних зашумленим каналом.

Цей поділ теорії кодування на стиснення й передавання обґрунтовано теоремами про передавання інформації, або теоремами про розділення джерела й каналу, які підтверджують використання бітів як універсальної валюти для інформації в багатьох контекстах. Проте ці теореми справедливі лише в ситуаціях, коли один передавач прагне спілкуватися з одним приймачем. У випадках, коли є понад одного передавача (канал із множинним доступом), понад одного приймача (канал мовлення) або проміжні «помічники» (ретрансляційний канал, англ. relay channel), чи для загальніших мереж, стиснення з подальшим передавання може вже не бути оптимальним.

Теорія джерела

Будь-який процес, що породжує послідовні повідомлення, можливо розглядати як джерело (англ. source) інформації. Джерело без пам'яті (англ. memoryless) — це таке джерело, в якому кожне повідомлення — незалежна й однаково розподілена випадкова величина, тоді як властивості ергодичності та стаціонарності накладають менш жорсткі обмеження. Усі такі джерела стохастичні. Ці терміни добре вивчені й поза межами теорії інформації.

Швидкість

Інформаційна швидкість (англ. rate) — це усереднена ентропія на символ. Для джерел без пам'яті це просто ентропія кожного символу, тоді як у випадку стаціонарного стохастичного процесу це

$r=\lim _{n\to \infty }H(X_{n}|X_{n-1},X_{n-2},X_{n-3},\ldots );$

тобто умовна ентропія символу за заданих всіх попередньо породжених символів. Для загальнішого випадку не обов'язково стаціонарного процесу середня швидкість (англ. average rate) це

$r=\lim _{n\to \infty }{\frac {1}{n}}H(X_{1},X_{2},\dots X_{n});$

тобто границя спільної ентропії на символ. Для стаціонарних джерел ці два вирази дають однаковий результат.

Інформаційну швидкість (англ. information rate) визначають як

$r=\lim _{n\to \infty }{\frac {1}{n}}I(X_{1},X_{2},\dots X_{n};Y_{1},Y_{2},\dots Y_{n});$

У теорії інформації часто говорять про «швидкість» або «ентропію» мови. Це доречно, наприклад, коли джерело інформації — англомовна проза. Швидкість джерела інформації пов'язана з його надмірністю та можливістю стиснення, що є предметом кодування джерела.

Пропускна спроможність каналу

Передавання інформації каналом — основний мотив теорії інформації. Проте канали часто не забезпечують точного відтворення сигналу; його якість часто можуть знижувати шум, періоди тиші та інші форми спотворення сигналу.

Розгляньмо процес передавання дискретним каналом. Просту модель процесу подано нижче:

${\xrightarrow[{\text{Повідомлення}}]{W}}{\begin{array}{|c| }\hline {\text{Кодувальник}}\\f_{n}\\\hline \end{array}}{\xrightarrow[{\mathrm {{\text{Закодована}} \atop {\text{послідовність}}} }]{X^{n}}}{\begin{array}{|c| }\hline {\text{Канал}}\\p(y|x)\\\hline \end{array}}{\xrightarrow[{\mathrm {{\text{Отримана}} \atop {\text{послідовність}}} }]{Y^{n}}}{\begin{array}{|c| }\hline {\text{Декодувальник}}\\g_{n}\\\hline \end{array}}{\xrightarrow[{\mathrm {{\text{Гадане}} \atop {\text{повідомлення}}} }]{\hat {W}}}$

Тут X подає простір передаваних повідомлень, а Y — простір отримуваних повідомлень за одиницю часу нашим каналом. Нехай p(y|x) — умовна ймовірність Y за заданого X. Розгляньмо p(y|x) як притаманну незмінну властивість нашого каналу (що відображає природу його шуму). Тоді спільний розподіл X та Y повністю визначається нашим каналом і вибором f(x), відособленого розподілу повідомлень, які ми обираємо для передавання каналом. За цих обмежень ми би хотіли максимізувати швидкість інформації, або сигнал, який можливо передавати цим каналом. Відповідною мірою для цього є взаємна інформація, і цю максимальну взаємну інформацію називають пропускною спроможністю каналу (англ. channel capacity), та задають як

$C=\max _{f}I(X;Y).\!$

Ця пропускна спроможність має наступну властивість, пов'язану з передаванням на інформаційній швидкості R (де R зазвичай вимірюють у бітах на символ). Для будь-якої інформаційної швидкості R < C та похибки кодування ε > 0, за достатньо великого N, існує кодування довжини N, швидкість ≥ R та алгоритм декодування, такі, що максимальна ймовірність помилки в блоці ≤ ε; тобто завжди можливо передавати з довільно малою блоковою похибкою. Крім того, для будь-якої швидкості R > C передавати з довільно малою блоковою похибкою неможливо.

Канальне кодування (англ. channel coding) займається пошуком таких майже оптимальних кодувань, які можливо використовувати для передавання даних зашумленим каналом з невеликою кодувальною похибкою на швидкості, наближеній до пропускної спроможності каналу.

Пропускна спроможність окремих моделей каналів

• Канал аналогового передавання безперервного часу, підданий гауссовому шуму, — див. теорему Шеннона — Гартлі.
• Двійковий симетричний канал (ДСК) з імовірністю спотворення p — це канал із бінарним входом і бінарним виходом, який змінює вхідний біт на протилежний з імовірністю p. ДСК має пропускну спроможність 1 - H_b(p) бітів на одне використання каналу, де H_b — функція бінарної ентропії для логарифму за основою 2:

• Двійковий канал зі стиранням (ДКС) з імовірністю стирання p — це канал із бінарним входом та тернарним виходом. Можливі виходи каналу — 0, 1 та третій символ 'e', званий стиранням (англ. erasure). Стирання подає повну втрату інформації про вхідний біт. Пропускна спроможність ДКС становить 1 - p бітів на одне використання каналу.

Канали з пам'яттю та спрямована інформація

На практиці багато каналів мають пам'ять. Тобто, у момент часу $i$ канал визначається умовною ймовірністю $P(y_{i}|x_{i},x_{i-1},x_{i-2},...,x_{1},y_{i-1},y_{i-2},...,y_{1})$. Часто зручніше використовувати запис $x^{i}=(x_{i},x_{i-1},x_{i-2},...,x_{1})$, тоді канал стає $P(y_{i}|x^{i},y^{i-1})$. У такому випадку пропускна спроможність визначається швидкістю взаємної інформації, коли зворотний зв'язок недоступний, та швидкістю спрямованої інформації, якщо зворотний зв'язок наявний чи відсутній (якщо зворотний зв'язок відсутній, спрямована інформація дорівнює взаємній інформації).

Замінна інформація

Замінна інформація (англ. fungible information) — це інформація, для якої засоби кодування не мають значення. Класичні теоретики інформації та спеціалісти з комп'ютерних наук здебільшого цікавляться інформацією саме цього типу. Іноді її називають вимовною (англ. speakable) інформацією.

Застосування в інших галузях

Використання в розвідці та прикладна секретність

Поняття теорії інформації застосовні до криптографії та криптоаналізу. Одиницю інформації, введену Тюрінгом — бан, використовували у проекті «Ультра» для зламування коду німецької машини «Енігма», що прискорило завершення Другої світової війни в Європі. Сам Шеннон визначив важливе поняття, відоме тепер як відстань єдиності. Виходячи з надмірності відкритого тексту, це поняття намагається оцінити мінімальну кількість шифротексту, необхідну для забезпечення унікальної розшифровуваності.

Теорія інформації підказує нам, що зберігати секрети набагато складніше, ніж може здатися на перший погляд. Атака повним перебором може зламувати системи на основі асиметричних ключів, або більшості широко використовуваних методів шифрування з симетричними ключами (іноді званих алгоритмами з секретним ключем), як-от блокового шифру. Безпека всіх таких методів ґрунтується на припущенні, що не існує відомих атак, здатних зламати їх за практично прийнятний час.

Інформаційно-теоретична безпека охоплює такі методи як одноразовий блокнот, що не вразливі до подібних атак повним перебором. У таких випадках додатна умовна взаємна інформація між відкритим і шифрованим текстом (обумовлена ключем) може забезпечувати належну передачу, тоді як безумовна взаємна інформація між відкритим і шифрованим текстом залишається нульовою, що забезпечує абсолютно захищений зв'язок. Іншими словами, перехоплювач не зможе покращити свої припущення щодо відкритого тексту, здобувши інформацію про шифротекст без ключа. Проте, як і в будь-якій іншій криптографічній системі, для правильного застосування навіть інформаційно-теоретично захищених методів потрібно бути уважними; проєкт «Венона» виявився здатним зламати одноразові блокноти Радянського Союзу через їхнє неналежне повторне використання ключового матеріалу.

Генерування псевдовипадкових чисел

Генератори псевдовипадкових чисел широко доступні в бібліотеках мов програмування та прикладних програмах. Проте майже повсюдно вони непридатні для криптографічного застосування, оскільки не обходять детерміновану природу сучасного комп'ютерного обладнання та програмного забезпечення. Один з класів удосконалених генераторів випадкових чисел називають криптографічно стійкими генераторами псевдовипадкових чисел, але навіть вони потребують для належної роботи випадкових початкових значень ззовні програмного забезпечення. Їх можливо отримувати за допомогою екстракторів, якщо робити це належним чином. Мірою достатньої випадковості в екстракторах є мін-ентропія, величина, пов'язана з ентропією Шеннона через ентропію Реньї; ентропію Реньї також використовують для оцінювання випадковості в криптографічних системах. Хоч ці міри й пов'язані, відмінності між ними означають, що випадкова величина з високою ентропією Шеннона не обов'язково задовільна для використання в екстракторі та, відповідно, в криптографії.

Сейсмічна розвідка

Одним із ранніх комерційних застосувань теорії інформації була галузь сейсмічного розвідування нафти. Робота в цій галузі уможливила відокремлювання небажаного шуму від потрібного сейсмічного сигналу. Теорія інформації та цифрова обробка сигналів пропонують значне підвищення роздільності та чіткості зображень порівняно з попередніми аналоговими методами.

Семіотика

Семіотики Дуде Наута та Вінфрід Ньот у своїх працях із семіотики розглядали Чарлза Сандерса Пірса як творця теорії інформації.^:171:137 Наута визначав семіотичну теорію інформації як дослідження «внутрішніх процесів кодування, фільтрування та обробки інформації.»^:91

Поняття з теорії інформації, як-от керування надмірністю та кодом, використовували такі семіотики як Умберто Еко та Ферруччо Россі-Ланді для пояснення ідеології як форми передавання повідомлення, за якої домінантний соціальний клас передає своє повідомлення, використовуючи знаки з високим рівнем надмірності, так що з множини конкурентних повідомлень декодується лише одне.

Організація інтегрованої обробки нейронної інформації

Кількісні методи теорії інформації застосували у когнітивістиці для аналізу організації інтегрованої обробки нейронної інформації в контексті проблеми зв'язування в когнітивній нейронауці. У цьому контексті визначають або інформаційно-теоретичну міру, таку як функційні кластери (англ. functional clusters, модель функційного кластерування та гіпотеза динамічного ядра (ГДЯ, англ. dynamic core hypothesis, DCH) Джеральда Едельмана та Джуліо Тононі) або ефективна інформація (англ. effective information, теорія інтегрованої інформації (ТІІ, англ. integrated information theory, IIT) свідомості Тононі), що ґрунтується на повторновикористовній організації обробки, тобто синхронізації нейрофізіологічної активності між групами нейронних сукупностей, або міру мінімізації вільної енергії на основі статистичних методів (принцип вільної енергії Карла Фрістана, інформаційно-теоретична міра, яка стверджує, що кожна адаптивна зміна в самоорганізовній системі веде до мінімізації вільної енергії, та гіпотеза баєсового мозку).

Інші застосування

Теорія інформації також знаходить застосування у пошуку позаземного розуму, дослідженні чорних дір, біоінформатиці^{[джерело?]}, та ста́вках.

Див. також

• Алгоритмічна ймовірність
• Баєсове висновування
• Індуктивна ймовірність
• Інфо-метрика
• Мінімальна довжина опису
• Мінімальна довжина повідомлення
• Теорія конструкторів — узагальнення теорії інформації, яке охоплює квантову інформацію
• Теорія масового спілкування
• Філософія інформації
• Формальні науки

Застосування

• Азартні ігри
• Активні мережі
• Ентропія в термодинаміці та теорії інформації
• Кібернетика
• Криптоаналіз
• Криптографія
• Розвідка (збирання інформації)
• Сейсмічна розвідка

Історія

• Гартлі, Р. В. Л.
• Історія теорії інформації
• Йокі, Г. П.
• Хронологія розвитку теорії інформації
• Шеннон, К. Е.
• Андрій Колмогоров

Теорія

• Алгебра інформації
• Асиметрична інформація
• Інформаційна геометрія
• Інформаційна теорія поля
• Інформація за Фішером
• Квантова інформатика
• Кодування джерела
• Колмогоровська складність
• Логіка інформації
• Мережне кодування
• Перелік нерозв'язаних проблем теорії інформації
• Теорія виявляння
• Теорія інформації та теорія міри
• Теорія кодування
• Теорія оцінювання
• Філософія інформації

Поняття

• Бан (одиниця виміру)
• Взаємна інформація
• Відстань Геммінга
• Відстань єдиності
• Власна інформація
• Декодувальник
• Джерело інформації
• Диференціальна ентропія
• Ентропія Реньї
• Замінна інформація
• Інформаційна ентропія
• Інформаційно-флуктуаційна складність
• Канал зв'язку
• Надмірність
• Перплексивність
• Поточкова взаємна інформація (ПВІ)
• Приймач (теорія інформації)
• Прихований канал
• Пропускна спроможність каналу
• Різноманітність
• Розходження Кульбака — Лейблера
• Спільна ентропія
• Стиснення даних
• Умовна ентропія

Література

Класичні праці

• Shannon, C.E. (1948), "A Mathematical Theory of Communication", Bell System Technical Journal (англ.), 27, pp. 379–423 & 623–656, July & October, 1948. PDF.
  Примітки та інші формати.
• R.V.L. Hartley, "Transmission of Information", Bell System Technical Journal (англ.), July 1928
• Andrey Kolmogorov (1968), "Three approaches to the quantitative definition of information" in International Journal of Computer Mathematics (англ.), 2, pp. 157–168. (Колмогоров, А. Н. (1965). Три подхода к определению понятия «количество информации». Пробл. передачи информ. (рос.). 1 (1): 3—11. Архів оригіналу за 26 червня 2017.)

Інші журнальні статті

• J. L. Kelly Jr., Princeton, "A New Interpretation of Information Rate" Bell System Technical Journal (англ.), Vol. 35, July 1956, pp. 917–26.
• R. Landauer, IEEE.org, "Information is Physical" Proc. Workshop on Physics and Computation PhysComp'92 (англ.) (IEEE Comp. Sci.Press, Los Alamitos, 1993) pp. 1–4.
• Landauer, R. (1961). Irreversibility and Heat Generation in the Computing Process (PDF). IBM J. Res. Dev. (англ.). 5 (3): 183—191. doi:10.1147/rd.53.0183.
• Timme, Nicholas; Alford, Wesley; Flecker, Benjamin; Beggs, John M. (2012). Multivariate information measures: an experimentalist's perspective (англ.). arXiv:1111.6857 [cs.IT].

Підручники з теорії інформації

• Alajaji, F. and Chen, P.N. An Introduction to Single-User Information Theory. (англ.) Singapore: Springer, 2018. ISBN 978-981-10-8000-5
• Arndt, C. Information Measures, Information and its Description in Science and Engineering (англ.) (Springer Series: Signals and Communication Technology), 2004, ISBN 978-3-540-40855-0
• Ash, Robert B. (1990) [1965]. Information Theory (англ.). New York: Dover Publications, Inc. ISBN 0-486-66521-6.
• Gallager, R. Information Theory and Reliable Communication. (англ.) New York: John Wiley and Sons, 1968. ISBN 0-471-29048-3
• Goldman, S. Information Theory. (англ.) New York: Prentice Hall, 1953. New York: Dover 1968 ISBN 0-486-62209-6, 2005 ISBN 0-486-44271-3
• Cover, Thomas; Thomas, Joy A. (2006). Elements of information theory (англ.) (вид. 2nd). New York: Wiley-Interscience. ISBN 0-471-24195-4.
• Csiszar, I, Korner, J. Information Theory: Coding Theorems for Discrete Memoryless Systems (англ.) Akademiai Kiado: 2nd edition, 1997. ISBN 963-05-7440-3
• MacKay, David J. C. Information Theory, Inference, and Learning Algorithms (англ.) Cambridge: Cambridge University Press, 2003. ISBN 0-521-64298-1
• Mansuripur, M. Introduction to Information Theory. (англ.) New York: Prentice Hall, 1987. ISBN 0-13-484668-0
• McEliece, R. The Theory of Information and Coding. (англ.) Cambridge, 2002. ISBN 978-0521831857
• Pierce, JR. "An introduction to information theory: symbols, signals and noise". (англ.) Dover (2nd Edition). 1961 (перевидано Dover 1980).
• Reza, Fazlollah M. (1994) [1961]. An Introduction to Information Theory (англ.). New York: Dover Publications, Inc. ISBN 0-486-68210-2.
• Shannon, Claude; Weaver, Warren (1949). The Mathematical Theory of Communication (PDF) (англ.). Urbana, Illinois: University of Illinois Press. ISBN 0-252-72548-4. LCCN 49-11922.
• Stone, JV. Chapter 1 of book "Information Theory: A Tutorial Introduction" (англ.), University of Sheffield, England, 2014. ISBN 978-0956372857.
• Yeung, RW. A First Course in Information Theory (англ.) Kluwer Academic/Plenum Publishers, 2002. ISBN 0-306-46791-7.
• Yeung, RW. Information Theory and Network Coding (англ.) Springer 2008, 2002. ISBN 978-0-387-79233-0

Українською

• Жураковський, Ю.П.; Полторак, В.П. (2001). Теорія інформації та кодування (PDF) (укр.). Київ: Вища школа.
• Жураковський, Ю. П.; Гніліцький, В. В. (2002). Теорія інформації та кодування в задачах: Навчальний посібник (укр.). Житомир: ЖІТІ. Архів оригіналу за 23 липня 2024.
• Кожевников, В.Л.; Кожевников, А.В. (2012). Теорія інформації та кодування (PDF) (укр.). Дніпро: НГУ. Архів оригіналу (PDF) за 25 березня 2022.
• Коваленко, А.Є. (2020). Теорія інформації і кодування: курс лекцій (PDF) (укр.). Київ: КПІ. Архів (PDF) оригіналу за 26 липня 2023.
• Гусєв, О.Ю.; Конахович, Г.Ф.; Корнієнко, В.І.; Кузнецов, Г.В.; Пузиренко, О.Ю. (2010). Теорія електричного зв'язку. Навчальний посібник (PDF) (укр.). Львів: Магнолія 2006. ISBN 978-966-2025-97-2. Архів (PDF) оригіналу за 18 травня 2024.
• Білинський, Й.Й.; Огородник, К.В.; Юкиш, М.Й. (2011). Електронні системи. Навчальний посібник (PDF) (укр.). Вінниця: ВНТУ. Архів (PDF) оригіналу за 29 червня 2024.
• Партико, З.В. (2001). Образна концепція теорії інформації (укр.) (англ.). Львів: ЛНУ. ISBN 966-613-046-7.

Інші книги

• Leon Brillouin, Science and Information Theory (англ.), Mineola, N.Y.: Dover, [1956, 1962] 2004. ISBN 0-486-43918-6
• Gleick, James (2011). [[Інформація: історія, теорія, потік|The Information: A History, a Theory, a Flood]][[Категорія:Вікіпедія:Запити на переклад]] (англ.) (вид. 1st). New York: Vintage Books. ISBN 978-1-4000-9623-7. {{cite book}}: Назва URL містить вбудоване вікіпосилання (довідка)
• A. I. Khinchin, Mathematical Foundations of Information Theory (англ.), New York: Dover, 1957. ISBN 0-486-60434-9
• H. S. Leff and A. F. Rex, Editors, Maxwell's Demon: Entropy, Information, Computing (англ.), Princeton University Press, Princeton, New Jersey (1990). ISBN 0-691-08727-X
• Robert K. Logan. What is Information? - Propagating Organization in the Biosphere, the Symbolosphere, the Technosphere and the Econosphere (англ.), Toronto: DEMO Publishing.
• Tom Siegfried, The Bit and the Pendulum (англ.), Wiley, 2000. ISBN 0-471-32174-5
• Charles Seife, Decoding the Universe (англ.), Viking, 2006. ISBN 0-670-03441-X
• Jeremy Campbell, Grammatical Man (англ.), Touchstone/Simon & Schuster, 1982, ISBN 0-671-44062-4
• Henri Theil, Economics and Information Theory (англ.), Rand McNally & Company - Chicago, 1967.
• Escolano, Suau, Bonev, Information Theory in Computer Vision and Pattern Recognition (англ.), Springer, 2009. ISBN 978-1-84882-296-2
• Vlatko Vedral, Decoding Reality: The Universe as Quantum Information (англ.), Oxford University Press 2010. ISBN 0-19-923769-7

Посилання

• Hazewinkel, Michiel, ред. (2001), Information, Математична енциклопедія, Springer, ISBN 978-1-55608-010-4
• Lambert F. L. (1999), "Shuffled Cards, Messy Desks, and Disorderly Dorm Rooms - Examples of Entropy Increase? Nonsense!", Journal of Chemical Education (англ.)
• IEEE Information Theory Society та Монографії, огляди та рецензії ITSOC [Архівовано 2018-06-12 у Wayback Machine.] (англ.)