Модель зв'язку Шеннона (переклад Great Principles of Computing)

Переклад Great Principles of Computing




У 1948 році Шеннон у своїй «теорії зв'язку» запропонував математичну модель зв'язку. Її сенс полягає в наступному.



Є джерело і є приймач. Джерело відправляє повідомлення, а приймач приймає. Обидва учасники користуються однаковим словником для кодування та декодування повідомлень.
Модель Шеннона застосовна до будь-якій системі, яка кодує, розкодує, передає, зберігає і отримує повідомлення. Так можна розглядати природу як джерело фізичних законів (повідомлень), а процес відкриття цих законів — як канал зв'язку (Dretske 1981).

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

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

У своїй моделі Шеннон в якості «словника для кодування» вибрав біти. Він стверджував, що будь-яке повідомлення може бути представлено у вигляді набору біт, т. e. у прямому сенсі оцифровано, будь-яка інформація перетворює в цифри, набір нулів і одиниць.

Цікаво подивитися на те, як оцифровувати повідомлення і що таке шум, на спрощеному прикладі.
Нехай джерело може передавати тільки повідомлення складаються з 4 літер: A, B, C і D. Використовуємо двобітові коди для позначення цих букв:

A: 11
B: 10
C: 01
D: 00

Наприклад, джерело хоче сказати: «CAB». Цьому повідомленню відповідає код «011110». Джерело надсилає цей набір біт на канал, а приймач їх отримує і запускає зворотний процес: розбиває код на пари біт і звіряє зі словником.

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

Наприклад, якщо перший біт в букві A з якихось причин загубиться, ми отримаємо 010110 — що відповідає CCB, а це повністю змінює зміст повідомлення. Як бути?

Додамо додатковий біт для кожної букви (біт парності):

A: 110
B: 101
C: 011
D: 000

Тепер, якщо перший біт в A втрачається ми отримуємо 010 — такий трійки в словнику немає, тому приймач легко може зрозуміти, що це помилка. Однак, він не зможе відновити вихідне повідомлення.

Якщо додати ще кілька зайвих бітів, то це допоможе приймача не тільки з'ясувати де помилка, але і відновити вихідний код:

A: 11111
B: 10010
C: 01001
D: 00100

Кожен код відрізняє від іншого як мінімум на 3 біти. Тепер зіпсований біт показує набір, який раніше відрізняється від вірного на один біт, але тепер він відрізняється на два або більше бітів від всіх інших у словнику! Відповідно, приймач може легко «поправити» зіпсоване повідомлення.

Инжерен зв'язку Річард Хеммінг (Richard Hamming) вперше сформулював правило, за яким можна визначити достатню «відстань» між наборами біт. За Хеммингу, відстань — це кількість біт, які відрізняються набори біт один від одного. Тепер ця величина називається відстанню Хеммінга.

Хеммінг зрозумів, що для того, щоб поправити k помилок, достатньо щоб відстань Хеммінга було одно 2^k — 1. Хеммінг так само розробив сімейство кодів (коди Хеммінга), які виходять додаванням біт парності до вихідного коду і створив схеми, які дозволяють легко отримувати вихідні повідомлення (з урахуванням виправлення помилок). Коди Хеммінга широко використовуються при передачі повідомлень від процесора до пам'яті комп'ютера.

Коди Хеммінга добре працюють, коли шум розподілений випадковим чином. Однак, в деяких сигналах шум виникає періодично або на відносно тривалий час. З цим завданням добре справляються інший тип кодів — коди Ріда-Соломона (Reed-Solomon). З точки зору математики, вони хитріші, однак і ті й інші легко можуть бути виконані на інтегральних схемах комп'ютера.
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.