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

Теорія інформації
Ентропія Диференціальна ентропія Умовна ентропія Спільна ентропія Взаємна інформація Спрямована інформація(інші мови) Умовна взаємна інформація(інші мови) Відносна ентропія Ентропійна швидкість Границя густини дискретних точок(інші мови)
Властивість асимптотичної рівнорозподіленості(інші мови) Швидкість–спотворення(інші мови)
Теорема Шеннона про кодування джерела(інші мови) Пропускна здатність каналу Теорема про кодування для зашумленого каналу(інші мови) Теорема Шеннона — Гартлі Алгоритмічна теорія інформації
п о р

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

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

До застосувань основних предметів теорії інформації належать кодування джерела/стиснення даних (наприклад, для файлів zip) та канальне кодування/виявляння та виправляння помилок (наприклад, для DSL). Її вплив був вирішальним для успіху місій «Вояджер» до глибокого космосу,^[4] винайдення компакт-диска, можливості мобільних телефонів і розвитку Інтернету й штучного інтелекту.^[5][3] Ця теорія також знайшла застосування й в інших сферах, як-от індуктивній статистиці,^[6] криптографії, нейробіології,^[7] сприйнятті,^[8] обробці сигналів,^[2] мовознавстві, еволюції^[9] та функціюванні^[10] молекулярних кодів (біоінформатиці), теплофізиці,^[11] молекулярній динаміці,^[12] чорних дірах, квантових обчисленнях, інформаційному пошуку, збиранні інформації, виявлянні плагіату,^[13] розпізнаванні образів, виявлянні аномалій,^[14] музичній аналітиці,^[15][16] створенні живопису,^[17] проєктуванні систем зображування(інші мови),^[18] вивченні космічного простору,^[19] вимірності простору,^[20] і навіть епістемології.^[21]

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

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

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

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

До цієї статті обмежені інформаційно-теоретичні ідеї розробили в 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.

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

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

Цей розділ не містить посилань на джерела. Ви можете допомогти поліпшити цей розділ, додавши посилання на надійні (авторитетні) джерела. Матеріал без джерел може бути піддано сумніву та вилучено. (листопад 2024)

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

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

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

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

${\displaystyle 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.

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

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

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

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

${\displaystyle 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 це стовпець, то спільна ентропія рядка та стовпця фігури буде ентропією її положення.

${\displaystyle 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 (також звана неоднозначністю^[28] X щодо Y, англ. equivocation) — це усереднена умовна ентропія за Y:^[29]

${\displaystyle 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).}$

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

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

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

${\displaystyle 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, конкретна взаємна інформація) — це поточкова взаємна інформація.

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle 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 буде випадковим чином обрано з дискретної множини з розподілом ймовірності ${\displaystyle p(x)}$. Якщо Аліса знає істинний розподіл ${\displaystyle p(x)}$, а Боб вважає (має апріорне переконання), що цим розподілом є ${\displaystyle q(x)}$, то для Боба побачене значення X у середньому буде більш несподіваним, аніж для Аліси. КЛ-розходження є (об'єктивним) очікуваним значенням (суб'єктивної) несподіваності для Боба, мінус несподіваність для Аліси, виміряним у бітах, якщо логарифм взято за основою 2. Таким чином, міру того, наскільки «помилковим» є апріорне переконання Боба, можливо кількісно виразити у вигляді очікуваної «зайвої несподіваності» для нього.

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

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

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

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

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

Цей розділ не містить посилань на джерела. Ви можете допомогти поліпшити цей розділ, додавши посилання на надійні (авторитетні) джерела. Матеріал без джерел може бути піддано сумніву та вилучено. (листопад 2024)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle {\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), та задають як

${\displaystyle 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 бітів на одне використання каналу.

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

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

Цей розділ не містить посилань на джерела. Ви можете допомогти поліпшити цей розділ, додавши посилання на надійні (авторитетні) джерела. Матеріал без джерел може бути піддано сумніву та вилучено. (листопад 2024)

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

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

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

Цей розділ не містить посилань на джерела. Ви можете допомогти поліпшити цей розділ, додавши посилання на надійні (авторитетні) джерела. Матеріал без джерел може бути піддано сумніву та вилучено. (листопад 2024)

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

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

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

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

Кількісні методи теорії інформації застосували у когнітивістиці для аналізу організації інтегрованої обробки нейронної інформації в контексті проблеми зв'язування(інші мови) в когнітивній нейронауці.^[48] У цьому контексті визначають або інформаційно-теоретичну міру, таку як функційні кластери (англ. functional clusters, модель функційного кластерування та гіпотеза динамічного ядра (ГДЯ, англ. dynamic core hypothesis, DCH) Джеральда Едельмана та Джуліо Тононі^[49]) або ефективна інформація (англ. effective information, теорія інтегрованої інформації(інші мови) (ТІІ, англ. integrated information theory, IIT) свідомості Тононі^[50][51][52]), що ґрунтується на повторновикористовній організації обробки, тобто синхронізації нейрофізіологічної активності між групами нейронних сукупностей, або міру мінімізації вільної енергії на основі статистичних методів (принцип вільної енергії Карла Фрістана, інформаційно-теоретична міра, яка стверджує, що кожна адаптивна зміна в самоорганізовній системі веде до мінімізації вільної енергії, та гіпотеза баєсового мозку(інші мови)^{[53][54][55][56][57]}).

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

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

Вікіцитати містять висловлювання від або про: Теорія інформації

• 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.] (англ.)