Комунікаційні канали

Класична теорія інформації базується на понятті каналу передачі.

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

У цій задачі ми розглянемо один із найпростіших можливих зашумлених каналів, а саме — бінарний симетричний канал (BSC). BSC передає послідовність бітів, але кожен переданий біт має ймовірність $p$ бути інвертованим. Це називається ймовірністю перехресної помилки (crossover probability), як показано на малюнку. Вважаємо, що різні біти поводяться незалежно, тож передача $l$ бітів буде здійснена без помилок із ймовірністю (1 - p)^l. Завжди можна вважати, що p < \frac{1}{2}, оскільки канал із p = \frac{1}{2} є марним, а канал із p > \frac{1}{2} можна перетворити на новий канал із ймовірністю перехресної помилки 1 - p, інвертувавши всі вихідні біти.

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

Вам потрібно дослідити поведінку бінарного симетричного каналу.