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

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

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

Аксіоми теорії інформації

1. Інформація є лише там, де функціонують пристрої керування.
2. Інформація зберігається і передається тільки на матеріальному носії.
3. Інформація має ідеальний характер.
4. Інформація має різні форми.

Базові закони теорії інформації

Закон 1: на отримання інформації будь-яка кібернетична система витрачає не менше деякої мінімальної кількості енергії.

Закон 2: кількість інформації, яку отримує кібернетична система в процесі розпізнавання після прийняття певного сигналу, дорівнює логарифму при основі m від кількості варіантів вибору, що передували розпізнаванню.

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

Закон 4: будь-які сигнали, отримані кібернетичною системою, впливають на цю систему.

Історія

Виникнення теорії інформації зазвичай пов'язують із появою у 1948 році фундаментальної праці американського науковця Клода Шеннона «Математична теорія зв'язку».

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

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

Властивості інформації

1. Достовірність — відповідність відображуваному об'єктові або реальному стану об'єктивної дійсності при відсутності прихованих помилок у такій інформації.
2. Повнота — властивість інформації, що дозволяє характеризувати об'єкт вичерпним для споживача засобом, що й надає можливість ухвалювати на основі такої інформації управлінські рішення.
3. Релевантність — відповідність потребам споживача, що характеризує, наскільки інформація сприяє досягненню поставлених перед споживачем цілей і завдань.
4. Доступність — можливість одержання будь-яким споживачем.
5. Актуальність — відповідність інформації теперішньому моменту часу.
6. Коректність — властивість, що полягає в такому її зображенні, щоб інформація однозначно сприймалася всіма її споживачами.
7. Захищеність — неможливість несанкціонованого доступу й цілеспрямованого спотворення інформації.
8. Ергономічність — достатність обсягу і форми інформації для даного споживача.

Кодування інформації

Кодування є переходом від повідомлення на вході каналу зв'язку до коду повідомлення на виході, а декодування — зворотний процес переходу від коду повідомлення на виході каналу зв'язку до повідомлення на вході, при цьому повідомлення на вході й виході з каналу зв'язку повинні збігатися.

Більш суворо задачу кодування можна сформулювати в такий спосіб. Нехай є два алфавіти: алфавіт ${\displaystyle A}$, що складається з ${\displaystyle n}$ символів і алфавіт ${\displaystyle B}$, що складається з ${\displaystyle m}$ символів. Під алфавітним кодуванням розуміють таке відображення ${\displaystyle F}$, яке кожному слову з непустої підмножини слів з алфавіту ${\displaystyle A}$ ставить у відповідність деяке слово з алфавіту ${\displaystyle B}$. Слова з алфавіту B називаються кодовими послідовностями або кодами. Традиційно, відображення ${\displaystyle F}$ задається у вигляді деякого алгоритму й повинне задовольняти наступним вимогам:

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

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

Кодування являє собою процес переходу повідомлення на вході каналу зв'язку до коду повідомлення на виході, при цьому інформаційна цінність повідомлення повинна залишатися незмінною. У теорії інформації можна виділити наступні методи кодування:

1. Кодування дискретних джерел. Це гіпотетична модель кодування інформації «без втрат», яка проходить через канал зв'язку без шуму, стисненням інформації.

2. Кодування інформації при її передачі по каналу з шумом. Цей метод враховує і захищає інформацію від перешкод в каналі зв'язку.

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

Також потрібно розглянути код Шеннона-Фано — алгоритм префіксного неоднорідного кодування. Цей метод кодування використовує надмірність повідомлення, укладену в неоднорідному розподілі частот символів його алфавіту, тобто замінює коди більш частих символів короткими двійковими послідовностями, а коди більш рідкісних символів — довшими двійковими послідовностями. Розглянемо джерело, що вибирає букви з множествас можливостями. Вважаємо, що букви впорядковані за спаданням ймовірностей. Кодовим словом коду Шеннона для повідомлення з номером M є двійкова послідовність, що є першим розрядом після коми в двійковому запису числа.

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

4. Кодування інформації для систем з багатьма користувачами описує оптимальну взаємодію абонентів, що використовують загальний ресурс, наприклад, канал зв'язку.

5. Секретний зв'язок, системи захисту інформації від несанкціонованого доступу. Цей тип активно використовуються і є актуальним. Зачіпає теорію інформації, теорії обчислювальної потужності алгоритмів, дослідження операцій, теорії чисел.

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

Ентропійний підхід

Докладніше: Кількості інформації

В основі теорії інформації лежить запропонований Шенноном спосіб обчислення кількості інформації як випадкової величини відносно іншої випадкової величини. Для випадкових величин X і Y, заданих законами розподілу ${\displaystyle P(X=X_{i})=p_{i},P(Y=Y_{j})=q_{j}}$ і спільним законом розподілу ${\displaystyle P(X=X_{i},Y=Y_{j})=p_{i,j}}$, кількість інформації в X відносно Y, дорівнює

${\displaystyle I(X,Y)=\sum _{i,j}p_{i,j}\log _{2}{\frac {p_{i,j}}{p_{i}q_{j}}}}$

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

Об'ємний підхід

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

Алгоритмічний підхід

Докладніше: Алгоритмічна теорія інформації

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

${\displaystyle I=L[G(A,B)]}$

${\displaystyle A}$ — вхідний об'єкт; ${\displaystyle B}$ — вихідний об'єкт; ${\displaystyle G}$ — програма перетворення; ${\displaystyle L}$ — функція отримання довжини програми (в бітах чи байтах).

Вадами цієї теорії є те, що вона:

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

Бібліографія

• Claude E. Shannon, Warren Weaver. The Mathematical Theory of Communication. Univ of Illinois Press, 1963.
• Thomas M. Cover, Joy A. Thomas. Elements of information theory New York: Wiley, 1991.
• R. Landauer, Information is Physical Proc. Workshop on Physics and Computation PhysComp'92 (IEEE Comp. Sci.Press, Los Alamitos, 1993) pp. 1-4.
• Maxwell's Demon: Entropy, Information, Computing, H. S. Leff and A. F. Rex, Editors, Princeton University Press, Princeton, NJ (1990).
• Колмогоров А. Н. Три подхода к определению понятия «Количество информации»
• Гусєв О. Ю., Конахович Г. Ф., Пузиренко О. Ю. та ін. Теорія електричного зв'язку. Навчальний посібник. — Львів: «Магнолія 2006», 2010. — 364 с.^{[недоступне посилання з липня 2019]} (PDF, 4,13 МБ, укр.)
• Білинський Й. Й., Огороднік К. В., Юкиш М. Й. Електронні системи. — Вінниця: ВНТУ, 2011. — 208 с. [ 13 червня 2016 у Wayback Machine.]
• Образна концепція теорії інформації = Image conception of the information theory / З. В. Партико; Львів. нац. ун-т ім. І. Франка. — Л., 2001. — 132 c.

Посилання

• «Енциклопедія кібернетики», відповідальний ред. В. Глушков, 2 тт., 1973, рос. вид. 1974;
• Shannon C.E. A Mathematical Theory of Communication [ 15 липня 1998 у Wayback Machine.] (PDF, 358 КБ, англ.)
• (PDF, 200 КБ, рос.)

Див. також

• Інформологія