Трохи теорії інформації

[ichthuss]

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

За перші десятиліття існування радіозв’язку народ емпіричним шляхом опанував частотне розділення каналів і амплітудну модуляцію. В 40-х же роках за діло всерйоз взялися математики, і саме тоді були написані фундаментальні роботи з теорії інформації та зв’язку, значною мірою — силами Клода Шеннона. Одним з фундаментальних результатів була теорема Шеннона для канала з шумами. В цій теоремі розглядається абстрактний канал зв’язку, який представляє собою, з точки зору математики, два випадкових процеси: один — сигнал на вході, другий — сигнал на виході. Для такої моделі ця теорема доводить, що існує скінченна величина, яка називається пропускною спроможністю каналу, і що існує спосіб закодувати будь-який потік інформації (якщо його об’єм, виміряний в бітах за секунду, не перевищує пропускної спроможності каналу) таким чином, що його можна на другому кінці каналу розкодувати майже без помилок. Для педантів розшифрую слово «майже»: у випадку прямування тривалості передачі до нескінченності ймовірність помилкового прийому прямує до нуля.

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

Один з важливих частинних випадків згаданої вище теореми, а саме теорема Шеннона-Хартлі для канала з аддитивним гаусовим шумом, стверджує, що пропускна спроможність аналогового каналу в бітах за секунду дорівнює

C = B log(1+S/N),
де
B — смуга пропускання каналу, Гц,
S — потужність сигналу в межах смуги пропускання, Вт,
N — потужність шуму в межах смуги пропускання, Вт.

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

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

Спочатку розкажу про модуляцію. Модуляція, за означенням — це зміна якогось параметру одного сигналу у відповідності до другого сигналу. Перший сигнал при цьому називається сигналом-носієм, а другий — інформаційним. На практиці це дозволяє «перемістити» частотну смугу інформаційного сигналу в область, близьку до частоти носія. Наприклад, коли кажуть, що передача ведеться на частоті 100 МГц, йдеться саме про частоту носія. Насправді радіопередача займає цілу смугу частот навколо цієї центральної частоти.

У синусоїди є два параметри: амплітуда і початкова фаза. Відповідно, є два основних види модуляції: амплітудна та фазова. Частотну модуляцію можна розглядати як різновид фазової. Найпростіший варіант амплітудної модуляції при передаванні цифрового сигналу може виглядати так: якщо треба передати «1», передаємо несну частоту, якщо треба передати «0», припиняємо передачу. Таким чином, за один «крок» нашої передачі ми передаємо один біт. При фазовій модуляції в залежності від інформаційного сигналу кожен раз змінюється фаза сигналу. Ці два підходи можна суміщувати і отримувати більшу кількість варіантів. Наприклад, поширена зараз модуляція QAM-64 має 64 позиції, тобто дозволяє за один «крок» передавати 6 біт інформації. Однак потрібно враховувати, що чим більше позицій передає дана модуляція, тим більше вона чутлива до шумів та завад.

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

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

e1 e2 d3 e4 d5 d6 d7 e8 d9 d10 d11 d12 d13 d14 d15

,

де d_i — біти корисної інформації, а e_i — біти корекції помилок, підібрані у відповідності до таких умов:

e1 ^ d3 ^ d5  ^ d7  ^ d9  ^ d11 ^ d13 ^ d15 = 0
e2 ^ d3 ^ d6  ^ d7  ^ d10 ^ d11 ^ d14 ^ d15 = 0
e4 ^ d5 ^ d6  ^ d7  ^ d12 ^ d13 ^ d14 ^ d15 = 0
e8 ^ d9 ^ d10 ^ d11 ^ d12 ^ d13 ^ d14 ^ d15 = 0

(тут через ^ позначено операцію додавання по модулю 2, також відому як XOR).

Логіка вибору індексів така: в першому рядку стоять числа, в яких в двійковому записі молодший біт дорівнює одиниці (тобто непарні), в другому — числа, в яких в двійковому записі другий біт дорівнює одиниці (2₁₀ = 10₂, 3₁₀ = 11₂, 6₁₀ = 110₂, 7₁₀ = 111₂ і т.д.), в третьому і четвертому — ті, що містять одиницю в третьому та четвертому біті відповідно.

При безпомилковому прийнятті інформації всі чотири вирази дадуть нулі. Якщо ж трапиться помилка в одному з бітів, то по розходженню цих виразів можна точно встановити, який саме з бітів пошкодився. Наприклад, нехай помилково був прийнятий біт номер 13. Число d13 входить у вирази 1, 3, 4, тому в них ми отримаємо одиниці. Таким чином, замість чотирьох нулів ми маємо результатом чотири цифри: 1, 0, 1, 1. Ці цифри в зворотньому записі (1101) якраз і дають нам номер помилкового біту в двійковому записі (1101₂ = 13₁₀).

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

Так от. Сумістивши один з методів модуляції з якимось з кодів корекції помилок, отримаємо приблизно таке:

На графіку показано, який максимальний бітрейт можна пропустити через 1 Гц смуги пропускання при різних типах модуляції і при ідеальному коді корекції помилок. Наприклад, при співвідношенні сигнал/шум 10 дБ (тобто сигнал потужніший за шум в 10 разів) двопозиційна диференційна фазова модуляція (BPSK) дозволить передати близько 1 біт/с на 1 Гц смуги пропускання, а 16-позиційна комбінована амплітудно-фазова модуляція (16-QAM) — трохи більше 3 біт/с на Гц. Верхній графік показує теоретичну межу відповідно до теореми Шеннона-Хартлі.

Тепер давайте прикинемо, що нам дасть перехід на цифру, скажімо, в області FM-радіостанцій. Смуга частот такої станції — 100 кГц. (Якщо бути більш точним, то на одну станцію виділяється 50 кГц, плюс додатково робиться 50 кГц «порожнього» проміжку, щоб сусідні станції не заважали одна одній, але, раз ми переходимо на цифру, ці проміжки можна задіяти). Це дасть, відповідно до нашого графіку, бітрейт до 600 кБіт/с у випадку, якщо співвідношення сигнал/шум > 25 дБ (при використанні модуляції 64-QAM — втім, більш наворочені модуляції, здається, зараз не поширені). Це — один аудіопотік у FLAC-якості, або 5 mp3-потоків середньої паршивості. Мінусом такого переходу буде те, що якщо рівень сигналу впаде так, що співвідношення сигнал/шум вийде за вказані межі, сигнал прийняти не вдасться взагалі, і замість шумного звуку (як зараз) людина отримає шиш. Плюсом — звісно, покращення якості трансляції або ж збільшення кількості доступних радіостанцій.

Причому вказане співвідношення (1 FLAC чи 5 mp3-потоків на одну аналогову станцію) залишиться в силі незалежно від того, чи будемо ми транслювати, як раніше, кожну станцію в своїй смузі частот, чи об’єднаємо їх на одній частоті-носії, як в телефонному зв’язку.

Хотів ще розказати про технології такого об’єднання, але запис і так вже виріс. Якщо комусь буде цікаво, напишу окремо.