Математична теорія зв'язку (стаття)

Математична теорія зв’язку
A Mathematical Theory of Communication
Жанр	Наукова стаття
Тема	теорія інформації і інформаційна ентропія
Автор	Клод Шеннон
Мова	англійська
Опубліковано	1948 рік
Країна	США

«Математична теорія зв’язку» (англ. A Mathematical Theory of Communication) — стаття, опублікована Клодом Шенноном у 1948 році в журналі американської телефонної компанії «Bell System»^[1] і що зробила його всесвітньо відомим. Включаючи велику кількість інноваційних і плідних ідей, ця робота ініціювала багато наукових досліджень по всьому світу, які тривають і по нині, поклавши початок розвитку методів обробки передачі та зберігання інформації.

Докладніше : Шеннон Клод

Клод Елвуд Шеннон (англ. Claude Elwood Shannon) – американський математик та інженер, засновник теорії інформації, автор багатьох книг і статей з кібернетики.

Докладніше: Хронологія розвитку теорії інформації^[ru]

Поняття теорії інформації з’явилося задовго до публікації цієї статті. Безліч авторів закладували фундамент нової теорії своїми роботами. Наприклад, у тому журналі компанії «Bell System» у 1924 році була публікація Найквіста, що містила в собі деякі положення, що лежать в основі даної статті.^[2]

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

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

У книзі вводиться логарифмічна функція як міра інформації, і показується її зручність:

	Вона зручна практично. Параметри, важливі в інженерному застосуванні – такі, як час, пропускна здатність, число перемикачів і так далі – зазвичай змінюються лінійно при логарифмічній зміні числа можливих варіантів. Наприклад, додавання одного перемикача подвоює число можливих станів їх групи, збільшуючи на одиницю його логарифм за основою 2. Збільшення в два рази часу призводить до квадратичного зростання числа повідомлень, або подвоєнню їх логарифма, і так далі. Вона близька до нашого інтуїтивного уявлення про таку міру. Це тісно пов’язано з попереднім пунктом, оскільки ми інтуїтивно вимірюємо величини, лінійно порівнюючи їх зі стандартами. Так, нам здається, що на двох перфокартах можна розмістити в два рази більше інформації, а по двох однакових каналах – передати її в два рази більше. Вона зручна математично. Багато граничних переходів прості в логарифмах, у той час як в термінах числа варіантів вони досить нетривіальні.
— К.Шеннон

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

Багато часу після своєї появи, всупереч поширеній думці, ця робота Шеннона була майже невідомою. Ось що пише, наприклад, з цього прикладу академік А.Н. Колмогоров:

	— Мені згадується, що на міжнародному з’їзді математиків в Амстердамі (1954 р.) мої американські колеги, спеціалісти по теорії ймовірностей, вважали мій інтерес до робіт Шеннона дещо перебільшеними, так як це більше техніка, ніж математика.
— А.Колмогоров

Але поступово вчені з різних областей науки стали проявляти до статті все більший інтерес. Зараз важко назвати область людських знань, в якій чудову формулу не намагалися так чи інакше застосувати. Кількість публікацій росла, що не могло не викликати відповідної реакції зі сторони самого Шеннона, так як спочатку цей захід призначався тільки для суто прикладних завдань техніки зв’язку. У 1956 році він опублікував коротеньку статтю «Бандвагон», у якій гаряче закликав писати про теорію інформації скромніше, не вважати цю теорію всемогутньою і універсальною, не перебільшувати її значення:

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

В результаті з’явилося два поняття - «теорія інформації» і «теорія передачі інформації». Перша визначає такі фундаментальні поняття, як «кількість інформації», і використовується для вирішення найрізноманітніших проблем різних розділів науки. Друга – вже своєю назвою відображає адекватну сферу застосування її ідей.

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

В п’ятидесяті роки багато зусилля було витрачено на спроби побудови в явному вигляді класів кодів, що дозволяють отримати обіцяну як завгодно малу ймовірність помилки, але результати були мізерними. У наступному десятилітті вирішенню цієї захоплюючої задачі приділялося менше уваги; замість цього дослідники кодів зробили тривали атаку по двом основним напрямам:

• Перший напрям носив чисто алгебраїчний характер і переважно розглядав блокові (лінійні) коди.
• Другий напрям досліджень з кодування носив скоріше імовірнісний характер. З цими дослідженнями були пов’язані спроби зрозуміти кодування і декодування з ймовірнісної точки зору, і ці спроби привели до появи послідовного декодування.

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

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

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

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

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

• Оригінал: Shannon C. E.. A Mathematical Theory of Communication. — Bell System Technical Journal^[en], 1948. — Т. 27. — С. 379—423.