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

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

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

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

Огляд

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

Теорія кодування займається пошуком конкретних методів, званих кодами (Шаблон:Lang-en), для підвищення ефективності та зниження рівня помилок при передаванні даних зашумленими каналами, з наближенням до пропускної спроможності каналу. Ці коди можливо умовно поділити на методи стискання даних (кодування джерела) та виправляння помилок (кодування каналу). У випадку останнього знадобилося багато років, щоби знайти методи, можливість яких довів Шеннон.Шаблон:Cn

Третій клас кодів у теорії інформації — алгоритми шифрування (як Шаблон:Li, так і шифри). Поняття, методи й результати з теорії кодування та теорії інформації широко використовують у криптографії та криптоаналізі, наприклад, одиничний бан.Шаблон:Cn

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

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

До цієї статті обмежені інформаційно-теоретичні ідеї розробили в Bell Labs, при цьому всі вони неявно виходили з однакової ймовірності подій. У своїй статті 1924 року «Деякі чинники, які впливають на швидкість телеграфу» (Шаблон:Lang-en) Гаррі Найквіст помістив теоретичний розділ, де кількісно визначив «відомості» (Шаблон:Lang-en) та «швидкість лінії» (Шаблон:Lang-en), з якою їх можливо передавати комунікаційною системою, встановивши співвідношення Шаблон:Math (що нагадує сталу Больцмана), де W — швидкість передачі відомостей, m — кількість різних рівнів напруги, з яких можна обирати на кожному часовому кроці, а K — стала. Стаття Ральфа Гартлі 1928 року «Передавання інформації» (Шаблон:Lang-en) використовує термін інформація (Шаблон:Lang-en) як вимірювану величину, що відображає здатність приймача розрізняти одну послідовність символів з будь-якими іншими, тим самим кількісно визначаючи інформацію як Шаблон:Math, де S — кількість можливих символів, а n — кількість символів у передаванні. Отже, одиницею інформації була десяткова цифра, яку згодом іноді називали гартлі на його честь як одиницю, шкалу або міру інформації. 1940 року Алан Тюрінг використав подібні ідеї як частину статистичного аналізу для розшифровки німецьких шифрів «Енігми» під час Другої світової війни.Шаблон:Cn

Більшість математичного апарату теорії інформації для різноймовірнісних подій розробили для галузі термодинаміки Людвіг Больцман та Джозая Віллард Ґіббз. Зв'язки між інформаційною ентропією та термодинамічною ентропією, включно з важливими внесками Шаблон:Li 1960-х років, розглянуто в статті «Шаблон:Li».Шаблон:Cn

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

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

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

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

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

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

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

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

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

$H=-\sum _i{p}_i{\log }_2(p_i)$

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

Інтуїтивно, ентропія Шаблон:Math дискретної випадкової величини Шаблон:Math є мірою невизначеності (Шаблон:Lang-en), пов'язаної зі значенням Шаблон:Math, коли відомий лише її розподіл.

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

Ентропія проби Бернуллі як функція ймовірності успіху, часто звана Шаблон:Em, Шаблон:Math. Ця ентропія досягає максимуму в 1 біт на пробу, коли два можливі результати рівноймовірні, як у випадку підкидання симетричної монети.

Якщо передати 1000 бітів (нулів та одиниць), але значення кожного з цих бітів відоме приймачу (має певне значення з упевненістю) ще до передачі, то очевидно, що жодної інформації не передано. Якщо ж кожен біт незалежно й однаково правдоподібно може бути 0 або 1, то передано 1000 шеннонів інформації (частіше званих бітами). Між цими двома крайнощами інформацію можливо кількісно виразити наступним чином. Якщо $𝕏$ — множина всіх повідомлень Шаблон:Math, якими може бути Шаблон:Math, а Шаблон:Math — імовірність деякого $x\in 𝕏$, то ентропію Шаблон:Math величини Шаблон:Math визначають якШаблон:Sfn

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

(Тут Шаблон:Math — власна інформація, що є внеском ентропії окремого повідомлення, а ${𝔼}_X$ — математичне сподівання.) Однією з властивостей ентропії є те, що вона максимізується, коли всі повідомлення у просторі повідомлень рівноймовірні, тобто Шаблон:Math, тобто найнепередбачуваніші, й у такому випадку Шаблон:Math.

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

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

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

Шаблон:Em (Шаблон:Lang-en) двох дискретних випадкових величин Шаблон:Math та Шаблон:Math — це просто ентропія їхньої двійки: Шаблон:Math. Це означає, що якщо Шаблон:Math та Шаблон:Math незалежні, то їхня спільна ентропія дорівнює сумі їхніх окремих ентропій.

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

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

Попри схожість позначень, спільну ентропію не слід плутати з Шаблон:Em (Шаблон:Lang-en).

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

Шаблон:Em (Шаблон:Lang-en) або умовна невизначеність (Шаблон:Lang-en) величини Шаблон:Math за заданої випадкової величини Шаблон:Math (також звана неоднозначністю Шаблон:Math щодо Шаблон:Math, Шаблон:Lang-en) — це усереднена умовна ентропія за Шаблон:Math:Шаблон:Sfn

$H(X|Y)={𝔼}_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).$

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

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

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

Взаємна інформація (Шаблон:Lang-en) вимірює кількість інформації про одну випадкову величину, яку можливо отримати, спостерігаючи іншу. Вона важлива в комунікаціях, де її можливо використовувати для максимізування кількості спільної інформації між передаваним та отримуваним сигналами. Взаємну інформацію Шаблон:Math відносно Шаблон:Math визначають як

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

де Шаблон:Math (Шаблон:Lang-en, конкретна взаємна інформація) — це поточкова взаємна інформація.

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

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

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

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

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

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

$I(X;Y)={𝔼}_{p(y)}[D_{\mathrm{K}\mathrm{L}}(p(X|Y=y)\Vert p(X))].$

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

$I(X;Y)=D_{\mathrm{K}\mathrm{L}}(p(X,Y)\Vert p(X)p(Y)).$

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

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

Розходження Кульбака — Лейблера (Шаблон:Lang-en, або розходження інформації, Шаблон:Lang-en, приріст інформації, Шаблон:Lang-en, чи відносна ентропія, Шаблон:Lang-en) — це спосіб порівняння двох розподілів: «істинного» розподілу ймовірності Шаблон:Tmath та довільного розподілу Шаблон:Tmath. Якщо ми стискаємо дані, вважаючи, що їхній розподіл це Шаблон:Tmath, тоді як насправді правильний розподіл це Шаблон:Tmath, розходження Кульбака–Лейблера визначає середню кількість додаткових бітів на дані, необхідних для стискання. Його відтак визначають як

$D_{\mathrm{K}\mathrm{L}}(p(X)\Vert 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)}.$

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

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

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

Шаблон:Li (Шаблон:Lang-en) $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})$ — Шаблон:Li $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$. Спрямована інформація знаходить широке застосування в задачах, де важливу роль відіграє причинність, як-от пропускна спроможність каналу зі зворотним зв'язком, пропускна спроможність дискретних мереж Шаблон:Li зі зворотним зв'язком, ставки з причинною додатковою інформацією, стиснення з причинною додатковою інформацією, постановки комунікації керування в реальному часі, та у статистичній фізиці.

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

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

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

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

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

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

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

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

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

Швидкість

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

$r=\underset{n\to \mathrm{\infty }}{\lim }H(X_n|X_{n-1},X_{n-2},X_{n-3},\dots );$

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

$r=\underset{n\to \mathrm{\infty }}{\lim }\frac{1}{n}H(X_1,X_2,\dots X_n);$

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

Шаблон:Li (Шаблон:Lang-en) визначають як

$r=\underset{n\to \mathrm{\infty }}{\lim }\frac{1}{n}I(X_1,X_2,\dots X_n;Y_1,Y_2,\dots Y_n);$

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

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

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

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

$\underset{\text{Повідомлення}}{\overset{W}{\to }}\begin{array}{c}\text{Кодувальник}\\ f_n\end{array}\underset{\genfrac{}{}{0ex}{}{\text{Закодована}}{\text{послідовність}}}{\overset{X^n}{\to }}\begin{array}{c}\text{Канал}\\ p(y|x)\end{array}\underset{\genfrac{}{}{0ex}{}{\text{Отримана}}{\text{послідовність}}}{\overset{Y^n}{\to }}\begin{array}{c}\text{Декодувальник}\\ g_n\end{array}\underset{\genfrac{}{}{0ex}{}{\text{Гадане}}{\text{повідомлення}}}{\overset{\hat{W}}{\to }}$

Тут X подає простір передаваних повідомлень, а Y — простір отримуваних повідомлень за одиницю часу нашим каналом. Нехай Шаблон:Math — умовна ймовірність Y за заданого X. Розгляньмо Шаблон:Math як притаманну незмінну властивість нашого каналу (що відображає природу його шуму). Тоді спільний розподіл X та Y повністю визначається нашим каналом і вибором Шаблон:Math, відособленого розподілу повідомлень, які ми обираємо для передавання каналом. За цих обмежень ми би хотіли максимізувати швидкість інформації, або сигнал, який можливо передавати цим каналом. Відповідною мірою для цього є взаємна інформація, і цю максимальну взаємну інформацію називають Шаблон:Em (Шаблон:Lang-en), та задають як

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

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

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

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

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

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

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

На практиці багато каналів мають пам'ять. Тобто, у момент часу $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})$. У такому випадку пропускна спроможність визначається швидкістю взаємної інформації, коли зворотний зв'язок недоступний, та швидкістю Шаблон:Li, якщо зворотний зв'язок наявний чи відсутній (якщо зворотний зв'язок відсутній, спрямована інформація дорівнює взаємній інформації).

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

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

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

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

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

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

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

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

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

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

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

Семіотика

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

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

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

Кількісні методи теорії інформації застосували у когнітивістиці для аналізу організації інтегрованої обробки нейронної інформації в контексті Шаблон:Li в когнітивній нейронауці. У цьому контексті визначають або інформаційно-теоретичну міру, таку як Шаблон:Em (Шаблон:Lang-en, модель функційного кластерування та гіпотеза динамічного ядра (ГДЯ, Шаблон:Lang-en) Джеральда Едельмана та Джуліо Тононі) або Шаблон:Em (Шаблон:Lang-en, Шаблон:Li (ТІІ, Шаблон:Lang-en) свідомості Тононі), що ґрунтується на повторновикористовній організації обробки, тобто синхронізації нейрофізіологічної активності між групами нейронних сукупностей, або міру мінімізації вільної енергії на основі статистичних методів (принцип вільної енергії Карла Фрістана, інформаційно-теоретична міра, яка стверджує, що кожна адаптивна зміна в самоорганізовній системі веде до мінімізації вільної енергії, та гіпотеза Шаблон:Li).

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

Теорія інформації також знаходить застосування у пошуку позаземного розуму, дослідженні чорних дір, біоінформатиціШаблон:Cn, та Шаблон:Li.

Див. також

• Шаблон:Li
• Баєсове висновування
• Шаблон:Li
• Шаблон:Li
• Мінімальна довжина опису
• Мінімальна довжина повідомлення
• Шаблон:Li — узагальнення теорії інформації, яке охоплює квантову інформацію
• Теорія масового спілкування
• Філософія інформації
• Формальні науки

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

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

Історія

• Гартлі, Р. В. Л.
• Шаблон:Li
• Шаблон:Li
• Шаблон:Li
• Шеннон, К. Е.
• Андрій Колмогоров

Теорія

• Шаблон:Li
• Асиметрична інформація
• Шаблон:Li
• Шаблон:Li
• Інформація за Фішером
• Квантова інформатика
• Кодування джерела
• Колмогоровська складність
• Шаблон:Li
• Шаблон:Li
• Шаблон:Li
• Теорія виявляння
• Шаблон:Li
• Теорія кодування
• Теорія оцінювання
• Філософія інформації

Поняття

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

Література

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

• Shannon, C.E. (1948), "A Mathematical Theory of Communication", Bell System Technical Journal Шаблон:Ref-en, 27, pp. 379–423 & 623–656, July & October, 1948. PDF.
  Примітки та інші формати.
• R.V.L. Hartley, "Transmission of Information", Bell System Technical Journal Шаблон:Ref-en, July 1928
• Andrey Kolmogorov (1968), "Three approaches to the quantitative definition of information" in Шаблон:Li Шаблон:Ref-en, 2, pp. 157–168. (Шаблон:Cite journal)

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

• J. L. Kelly Jr., Princeton, "A New Interpretation of Information Rate" Bell System Technical Journal Шаблон:Ref-en, Vol. 35, July 1956, pp. 917–26.
• R. Landauer, IEEE.org, "Information is Physical" Proc. Workshop on Physics and Computation PhysComp'92 Шаблон:Ref-en (IEEE Comp. Sci.Press, Los Alamitos, 1993) pp. 1–4.
• Шаблон:Cite journal
• Шаблон:Cite arXiv

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

• Alajaji, F. and Chen, P.N. An Introduction to Single-User Information Theory. Шаблон:Ref-en Singapore: Springer, 2018. Шаблон:Isbn
• Arndt, C. Information Measures, Information and its Description in Science and Engineering Шаблон:Ref-en (Springer Series: Signals and Communication Technology), 2004, Шаблон:Isbn
• Шаблон:Cite book
• Gallager, R. Information Theory and Reliable Communication. Шаблон:Ref-en New York: John Wiley and Sons, 1968. Шаблон:Isbn
• Goldman, S. Information Theory. Шаблон:Ref-en New York: Prentice Hall, 1953. New York: Dover 1968 Шаблон:Isbn, 2005 Шаблон:Isbn
• Шаблон:Cite book
• Csiszar, I, Korner, J. Information Theory: Coding Theorems for Discrete Memoryless Systems Шаблон:Ref-en Akademiai Kiado: 2nd edition, 1997. Шаблон:Isbn
• Шаблон:Li Information Theory, Inference, and Learning Algorithms Шаблон:Ref-en Cambridge: Cambridge University Press, 2003. Шаблон:Isbn
• Mansuripur, M. Introduction to Information Theory. Шаблон:Ref-en New York: Prentice Hall, 1987. Шаблон:Isbn
• Шаблон:Li. The Theory of Information and Coding. Шаблон:Ref-en Cambridge, 2002. Шаблон:Isbn
• Pierce, JR. "An introduction to information theory: symbols, signals and noise". Шаблон:Ref-en Dover (2nd Edition). 1961 (перевидано Dover 1980).
• Шаблон:Cite book
• Шаблон:Cite book
• Stone, JV. Chapter 1 of book "Information Theory: A Tutorial Introduction" Шаблон:Ref-en, University of Sheffield, England, 2014. Шаблон:Isbn.
• Yeung, RW. A First Course in Information Theory Шаблон:Ref-en Kluwer Academic/Plenum Publishers, 2002. Шаблон:Isbn.
• Yeung, RW. Information Theory and Network Coding Шаблон:Ref-en Springer 2008, 2002. Шаблон:Isbn

Українською

• Шаблон:Cite book
• Шаблон:Cite book
• Шаблон:Cite book
• Шаблон:Cite book
• Шаблон:Cite book
• Шаблон:Cite book
• Шаблон:Cite book

Інші книги

• Leon Brillouin, Science and Information Theory Шаблон:Ref-en, Mineola, N.Y.: Dover, [1956, 1962] 2004. Шаблон:Isbn
• Шаблон:Cite book
• A. I. Khinchin, Mathematical Foundations of Information Theory Шаблон:Ref-en, New York: Dover, 1957. Шаблон:Isbn
• H. S. Leff and A. F. Rex, Editors, Maxwell's Demon: Entropy, Information, Computing Шаблон:Ref-en, Princeton University Press, Princeton, New Jersey (1990). Шаблон:Isbn
• Шаблон:Li. What is Information? - Propagating Organization in the Biosphere, the Symbolosphere, the Technosphere and the Econosphere Шаблон:Ref-en, Toronto: DEMO Publishing.
• Tom Siegfried, The Bit and the Pendulum Шаблон:Ref-en, Wiley, 2000. Шаблон:Isbn
• Шаблон:Li, Шаблон:Li Шаблон:Ref-en, Viking, 2006. Шаблон:Isbn
• Jeremy Campbell, Шаблон:Li Шаблон:Ref-en, Touchstone/Simon & Schuster, 1982, Шаблон:Isbn
• Henri Theil, Economics and Information Theory Шаблон:Ref-en, Rand McNally & Company - Chicago, 1967.
• Escolano, Suau, Bonev, Information Theory in Computer Vision and Pattern Recognition Шаблон:Ref-en, Springer, 2009. Шаблон:Isbn
• Vlatko Vedral, Decoding Reality: The Universe as Quantum Information Шаблон:Ref-en, Oxford University Press 2010. Шаблон:ISBN

Посилання

• Шаблон:SpringerEOM
• Lambert F. L. (1999), "Shuffled Cards, Messy Desks, and Disorderly Dorm Rooms - Examples of Entropy Increase? Nonsense!", Journal of Chemical Education Шаблон:Ref-en
• IEEE Information Theory Society та Монографії, огляди та рецензії ITSOC Шаблон:Webarchive Шаблон:Ref-en