Теорія кодування. Види кодування Коли та чому виникла теорія кодування

«Мета цього курсу – підготувати вас до вашого технічного майбутнього.»

Привіт Хабр. Пам'ятаєте офігенну статтю «Ви та ваша робота» (+219, 2442 в закладки, 394k прочитань)?

Так ось у Хеммінга (так, так, коди Хеммінга, що самоконтролюються і самокоректуються) є ціла книга, написана за мотивами його лекцій. Ми її перекладаємо, адже мужик каже.

Це книга не просто про ІТ, це книга про стиль мислення неймовірно крутих людей. Це не просто заряд позитивного мислення; в ній описані умови, які збільшують шанси зробити велику роботу.

Ми вже переклали 28 (із 30) розділів. І ведемо роботу над виданням «у папері».

Теорія кодування - I

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

Для спрощення проблеми подання інформації розглянемо проблему передачі від точки до точки. Це питання пов'язане з питанням збереження інформації. Проблеми передачі у часі та у просторі ідентичні. На малюнку 10.1 представлено стандартну модель передачі.

Малюнок 10.1

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

Коли наприкінці 1940 років Шеннон створив теорію інформації, вважалося, що вона мала називатися теорією зв'язку, але він наполяг на терміні інформація. Цей термін став постійною причиною як підвищеного інтересу, і постійних розчарувань теорії. Слідчі хотіли будувати цілі «теорії інформації», вони вироджувались у теорії набору символів. Повертаючись до моделі передачі, ми маємо джерело даних, які необхідно закодувати для передачі.

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

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

Відповідно до моделі, малюнку 10.1 канал передачі даних піддається впливу «додаткового випадкового шуму». Весь шум у системі об'єднаний у цій точці. Передбачається, що кодер приймає всі символи без спотворень, а декодер виконує свою функцію без помилок. Це деяка ідеалізація, але для багатьох практичних цілей вона близька до реальності.

Фаза декодування також складається з двох етапів: канал - стандарт, стандарт-приймач даних. Наприкінці передачі передаються споживачеві. І знову ми не розглядаємо питання, як споживач трактує ці дані.

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

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

Почнемо розгляд систем із закодованими символами змінної довжини, як у класичному коді Морзе з точок і тире, в якому символи, що часто зустрічаються, - короткі, а рідкісні - довгі. Такий підхід дозволяє досягти високої ефективності коду, але варто відзначити, що код Морзе - тернарний, а не бінарний, тому що в ньому є символ пробілу між точками та тире. Якщо всі символи в коді однакової довжини, такий код називається блоковим.

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

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

Розглянемо алфавіт з небагатьох символів, зазвичай алфавіти набагато більше. Алфавіти мов починається від 16 до 36 символів, включаючи символи у верхньому та нижньому регістрі, числа знаки, пунктуації. Наприклад, у таблиці ASCII 128 = 2^7 символів.
Розглянемо спеціальний код, що складається із 4 символів s1, s2, s3, s4

s1 = 0; s2 = 00; s3 = 01; s4 = 11.

Як приймач повинен трактувати такий отриманий вираз

Як s1s1s4або як s2s4?

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

s1 = 0; s2 = 10; s3 = 110; s4 = 111

Декодує повідомлення унікальним способом. Візьмемо довільний рядок і розглянемо, як його декодуватиме приймач. Вам необхідно побудувати дерево декодування. Відповідно до форми на малюнку 10.II. Рядок

1101000010011011100010100110 …

Може бути розбита на блоки символів

110, 10, 0, 10, 0, 110, 111, 0, 0, 0, 10, 10, 0, 110, …

Відповідно до такого правила побудови дерева декодування:

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

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

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

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

Малюнок 10.II

Наступне питання – це коди для потокового (миттєвого) декодування. Розглянемо код, який виходить із попереднього відображенням символів

s1 = 0; s2 = 01; s3 = 011; s4 = 111.

Припустимо, ми отримали послідовність 011111...111 . Єдиний спосіб, яким можна декодувати текст повідомлення: групувати біти з кінця по 3 групи і виділяти групи з провідним нулем перед одиничками, після цього можна декодувати. Такий код декодується єдиним способом, але не миттєвим! Для декодування потрібно дочекатися закінчення передачі! У практиці такий підхід нівелює швидкість декодування (теорема Макміллана), отже необхідно пошукати способи миттєвого декодування.

Розглянемо два способи кодування одного і того ж символу, Si:

s1 = 0; s2 = 10; s3 = 110; s4 = 1110, s5 = 1111,

Дерево декодування цього способу представлене малюнку 10.III.

Малюнок 10.III

Другий спосіб

s1 = 00; s2 = 01; s3 = 100; s4 = 110, s5 = 111,

Дерево декодування цього догляду представлено малюнку 10.IV.

Найбільш очевидним способом вимірювання якість коду – це середня довжина для деякого набору повідомлень. Для цього необхідно обчислити довжину коду кожного символу, помножену на ймовірність появи pi. Таким чином, вийде довжина всього коду. Формула середньої довжини коду L для алфавіту з q символів виглядає наступним чином

Де pi – ймовірність появи символу si, li – відповідна довжина закодованого символу. Для ефективного коду значення L має бути якнайменше. Якщо P1 = 1/2, p2 = 1/4, p3 = 1/8, p4 = 1/16 та p5 = 1/16, тоді для коду #1 отримуємо значення довжини коду

А для коду #2

Отримані значення свідчать про перевагу першого коду.
Якщо у всіх слів в алфавіті буде однакова ймовірність виникнення, тоді кращим буде другий код. Наприклад, за pi = 1/5 довжина коду #1

А довжина коду #2

Цей результат показує перевагу 2 коди. Отже, під час створення «хорошого» коду необхідно враховувати можливість виникнення символів.

Малюнок 10.IV

Малюнок 10.V

Розглянемо нерівність Крафта, що визначає граничне значення довжини коду символу li. По базису 2 нерівність подається у вигляді

Ця нерівність говорить про те, що в алфавіті не може бути надто багато коротких символів, інакше сума буде досить великою.

Для доказу нерівності Крафта для будь-якого швидкого унікального коду, що декодується, побудуємо дерево декодування і застосуємо метод математичної індукції. Якщо дерево має один або два листи, як показано на малюнку 10.V, тоді без сумніву нерівність вірна. Далі, якщо дерево має більш ніж два листи, то розбиваємо дерево довгий m на два піддерева. Відповідно до принципу індукції припускаємо, що нерівність правильна кожної гілки висотою m -1 чи менше. Відповідно до принципу індукції, застосовуючи нерівність до кожної гілки. Позначимо довжини кодів гілок K" і K"". При об'єднанні двох гілок дерева довжина кожного зростає на 1, отже, довжина коду складається з сум K'/2 і K'/2,

Теорему доведено.

Розглянемо підтвердження теорема Макміллана. Застосуємо нерівність Крафта до неточно декодуємо коди. Доказ побудовано тому факті, що з будь-якого числа K > 1 n-а ступінь числа свідомо більше лінійної функції від n, де n - досить велике число. Зведемо нерівність Крафта в n-ий ступінь і подаємо вираз у вигляді суми

Де Nk число символів довжини k, підсумовування починаємо з мінімальної довжини n-го уявлення символу і закінчуємо максимальну довжину nl, де l - максимальна довжина закодованого символу. З вимоги унікального декодування випливає, що. Сума подається у вигляді

Якщо K > 1, тоді необхідно встановити досить великим для того, щоб нерівність стала хибною. Отже, k<= 1; теорема Макмиллана доказана.

Розглянемо кілька прикладів застосування нерівності Крафта. Чи може існувати унікальний код, що декодується, з довжинами 1, 3, 3, 3? Так, оскільки

А що щодо довжин 1, 2, 2, 3? Розрахуємо згідно з формулою

Нерівність порушена! У цьому коді дуже багато коротких символів.

Точкові коди (comma codes) - це коди, які складаються із символів 1, що закінчуються символом 0, за винятком останнього символу, що складається з усіх одиниць. Одним із окремих випадків служить код

s1 = 0; s2 = 10; s3 = 110; s4 = 1110; s5 = 11111.

Для цього коду отримуємо вираз для нерівності Крафта

І тут досягаємо рівність. Легко бачити, що для точкових кодів нерівність Крафта вироджується на рівність.

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

Необхідно відзначити, що нерівність Крафта говорить не про те, що цей код унікально декодується, а про те, що існує код із символами такої довжини, які унікально декодується. Для побудови унікального коду, що декодується, можна привласнити двійковим числом відповідну довжину в бітах li. Наприклад, для довжин 2, 2, 3, 3, 4, 4, 4, 4 отримуємо нерівність Крафта

Отже, може існувати такий унікальний декодований потоковий код.

s1 = 00; s2 = 01; s3 = 100; s4 = 101;

S5 = 1100; s6 = 1101; s7 = 1110; s8 = 1111;

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

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

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

Далі буде...

Хто хоче допомогти з перекладом, версткою та виданням книги – пишіть у личку чи на пошту [email protected]

До речі, ми ще запустили переклад ще однієї крутої книги.

Взагалі кажучи, кодування- будь-яке перетворення повідомлення на сигнал шляхом встановлення взаємної відповідності між ними. У вузькому значенні кодування– перетворення дискретного повідомлення на послідовність кодових символів за заданим правилом. Безліч всіх кодових послідовностей ( кодових комбінацій чи слів), можливих за даного правила кодування, утворює код. Правило кодування можна виразити кодовою таблицею з алфавітом повідомлень, що кодуються, і відповідними ним кодовими комбінаціями. Сукупність символів, у тому числі становлять кодові послідовності, називають кодовим алфавітом, А їх число (обсяг кодового алфавіту) - основою коду.

Правила кодування елементів повідомлення - правила запису різних чисел в
-Ічної системи числення. Розрізняють двійкові (
) та багатопозиційні (
-Ічні,
)коди. Довжина кодового слова - Число розрядів у ньому . Для передачі повідомлень у двійковому коді достатньо мати лише два різні сигнали. Так, символи і можна передати коливаннями різних частот чи імпульсами струму різної полярності. Відстань Хеммінга між двома кодовими словами і знаходять у два етапи. Складають розрядно шукані слова в
-їчної системи числення без перенесення до старшого розряду ( додавання за модулем основи коду
, що позначається символом ). Отримані значення складають у
-Ічної системи числення:

, (1.1)

де і - однойменні (
і) розряди кодових слів і відповідно. Так,
,
,
і
при
. Для двійкового коду відстань дорівнює числу розрядів, у яких слова і різні. Кодова відстань - найменше для цього коду значення . У еквідистантномукоді відстані між двома будь-якими його словами однакові. Число ненульових елементів кодового слова дорівнює його вагою .

1.2. Класифікація методів кодування

На рис. 1.1 дана класифікація методів кодування . Одне з його завдань – узгодження алфавіту повідомлення з алфавітом каналу. Кожен ансамбль повідомлень можна кодувати різними способами. Найкращий код відповідає вимогам:

1) приймач може відновити повідомлення джерела, надіслане лінією зв'язку;

2) для представлення одного повідомлення в середньому потрібна мінімальна кількість символів.

Першу вимогу задовольняють оборотнікоди. Вони всі кодові слова різні і однозначно пов'язані з відповідними повідомленнями. Економнікоди задовольняють другу вимогу.

Рис. 1.1. Класифікація методів кодування

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

Коди бувають первинні(прості чи примітивні) та завадостійкі. Прості коди складаються зі всіх кодових слів, можливих при даному способі кодування. Перетворення одного символу кодового слова на інше через дії перешкод дає нове кодове слово. Виникає помилка, яку не можна виявити. У завадостійких кодах застосовують лише частину із загальної кількості можливих кодових слів. Застосовувані слова називають дозволеними, решта – забороненими. Перешкодостійке кодування дозволяє підвищити вірність передачі повідомлень.

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

Декодуванняполягає у відновленні повідомлення за кодовими символами. Декодуючий пристрій ( декодер) разом із кодером утворює кодек. Зазвичай кодек – логічний устрій.

Примітивне (надмірне) кодування застосовують для узгодження алфавіту джерела з алфавітом каналу. Тоді надмірність джерел(див. п. 2.1), утворених виходом та входом кодера, однакова. Це кодування застосовують також для шифрування інформації, що передається, і підвищення стійкості роботи системи синхронізації. В останньому випадку правило кодування вибирають так, щоб ймовірність появи на виході кодера довгої послідовності, що складається тільки з або тільки з , була мінімальною. Подібний кодер називають скремблер(Від англійського слова scramble - перемішувати).

Відновлення переданого повідомлення в приймачі завжди наближене. Частина інформації, необхідна для забезпечення необхідної точності відновлення, називається суттєвою. Стиснення (компресування) повідомлення(даних) - повне або часткове видалення з нього (їх) надлишковоїінформації. Вирішення цього завдання досягається економнимкодуванням. Стиснення даних дає економію пам'яті пристроїв і пропускну здатністьканалів. При економному кодуванні надмірність джерела, утвореного виходом кодера, менша, ніж на вході кодера. Економне кодування застосовується в ЕОМ. Операційні системи містять у своєму складі програми стиснення даних ( динамічні компресориі архіватори). Так, стандарт
на модемидля зв'язку між ЕОМ по телефонних мережах загального користування включає стиск до процедур обробки даних (див. Додаток).

Перешкодостійке (надмірне) кодування застосовують для виявлення та виправлення помилок, що виникають при передачі повідомлення по каналу. Тоді надмірність джерела, утвореного виходом кодера, більша надмірності джерела на вході кодера. Це кодування поширене в різних системах зв'язку, при зберіганні та передачі даних у мережах ЕОМ, у цифровій аудіо- та відеотехніці.

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

приклад 1.2.1.Примітивним рівномірним кодом, який використовується в телеграфії, є код Бодо з двійковими елементами у кожному слові (

). Повна кількість слів
. Цього достатньо для кодування
букв російського алфавіту, але недостатньо передачі повідомлення, що містить літери, цифри й різні умовні знаки (точка, кома, додавання, множення тощо.). Тоді можна застосувати Міжнародний код №2 (МТК-2) із реєстровим принципом. У ньому те саме
елементне кодове слово можна використовувати до трьох разів залежно від положення регістру: російська, латинська та цифрова. Загальна кількість різних знаків дорівнює
що достатньо для кодування телеграми. Для передачі даних рекомендовано
елементний код МТК-5 .

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

Будова коду зручно подати у вигляді графа(кодового дерева), в якому з кожного вузлавиходить число гілок, що дорівнює основі коду (для двійкового коду, наприклад, крок вгору означає , крок вниз - ).

приклад 1.2.2.Код Морзе – типовий приклад нерівномірного двійкового коду . У ньому символи і застосовуються лише у двох поєднаннях – як поодинокі ( і ) або як потрійні (
і
). Сигнал, відповідний , називається точкою, а
- тире. Символ використовується як знак, що відокремлює точку від тире, точку від точки та тире від тире. Сукупність
застосовується як знак розподілу кодових слів.

Простий алгоритм отримання нерівномірних префіксних кодів запропонували Шеннон та Фано. Алгоритм Шеннона-Фанодля двійкового коду – наступний. Символи джерела алфавіту записують у порядку без збільшення ймовірностей їх появи. Потім символи поділяють на частини так, щоб суми ймовірностей символів у кожній із цих частин були приблизно однакові. Всім символам
ой (
ой) частини приписують () в якості
ого символу слова коду. Кожну з
х частин (якщо в ній більше
го символу) ділять ще на дві, по можливості, рівноймовірні частини. До них застосовують те саме правило кодування. Процес повторюють, поки в кожній з отриманих частин не залишиться по
му символу. Поділ на частини з приблизно рівними ймовірностями - не завжди однозначна процедура. Похибки кодування можна зменшити, а код зробити ефективнішим, перейшовши від кодування символів до кодування послідовностей символів повідомлення. методом укрупнення алфавіту(Див. п. 4.2).

приклад 1.2.3.Нехай алфавіт
джерело складається із символів ,
. Імовірність появи символів на виході джерела, відповідно, дорівнює
,
,
,
,
і
. Процедура Шеннона-Фано побудови нерівномірного коду без укрупнення джерела алфавіту задається табл. 1.1 .

Таблиця 1.1. Кодування джерела за методом Шеннона-Фано

		Вибір символів нерівномірного коду

на
ом етапі безліч символів ділимо на частини: і
; на
ом - і
; на
їм -
і
; на
ом - і ,і . Більш вірогідним символам джерела надамо кодові слова меншої довжини . Збудували префіксний код. Середня довжина кодового слова (середня кількість символів коду однією символ джерела)
.

Перешкодостійкі коди бувають блоковіі безперервні. При блоковому кодуванні послідовність джерел символів розбивають на відрізки. Кожному відрізку відповідає певна послідовність (блок) кодових символів – кодове слово. Багато кодових слів, можливих при даному способі кодування, утворює блоковий код. У рівномірному (нерівномірному) Код довжина блоку - постійна (змінна). Перешкодостійкі коди – зазвичай рівномірні.

Блокові коди бувають розділеніі нероздільні. У розділеному коді
довжини символи можна розділити за призначенням інформаційних(що несуть інформацію про повідомлення) та
перевірочних. Швидкість коду
. Повна кількість слів у коді дорівнює
, а
- Число дозволених слів. У кодах, що не розділяються, не можна виділити інформаційні та перевірочні символи. Наприклад, - це коди з постійною вагоюі коди на основі матриць Адамара(Див. п. 6.3). У двійковому коді з постійною вагою кодові слова містять однакове число . У стандартному телеграфному коді № 3 кожен із них містить три і чотири .

Роздільні коди бувають лінійніі нелінійні. У лінійних кодах сума за
(Див. (1.1))
x будь-яких кодових слів утворює кодове слово того ж коду. Лінійний код називається систематичним, якщо перші символів будь-якого його кодового слова є інформаційними, а інші
- перевірочними. Підклас лінійних кодів - циклічні коди(Див. п. 6.5). Вони всі набори, утворені циклічною перестановкою символів у кожному кодовому слові, є кодовими словами тієї самої коду. Ця властивість спрощує побудову кодека, особливо при виявленні та виправленні одиночних помилок. Приклади циклічних кодів - коди Хеммінга, коди Боуза-Чоудхурі-Хоквінгема (БЧХ-коди) та інші. Приклад нелінійного двійкового коду - код Бергера(Див. п. 1.4) . У ньому перевірочні символи утворені двійковим записом числа у послідовності інформаційних символів.

Безперервне кодування та декодування роблять над безперервною послідовністю символів без розбиття її на блоки. Серед безперервних найчастіше застосовують згорткові коди(Див. п. 6.8).

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

У Додатку проілюстровано принципи побудови кодів та стиснення даних на прикладі комп'ютерних мереж.

Матеріал з Вікіпедії – вільної енциклопедії

Теорія кодування- наука про властивості кодів та їх придатність для досягнення поставленої мети.

Загальні відомості

Кодування - це процес перетворення даних з форми, зручної для безпосереднього використання, у форму, зручну для передачі, зберігання, автоматичної переробки та збереження від несанкціонованого доступу. До основних проблем теорії кодування відносять питання взаємної однозначності кодування та складності реалізації каналу зв'язку за заданих умов:86. У зв'язку з цим теорія кодування переважно розглядає наступні напрямки :18:

Стиснення даних

Пряма корекція помилок

Криптографія

Криптографія (від др.-грец. κρυπτός - прихований і γράφω - пишу), це область знань про методи забезпечення конфіденційності (неможливість прочитання інформації стороннім), цілісності даних (неможливості непомітної зміни інформації), аутентифікації (перевірки справжності авторства або інших властивостей об'єкта), а також неможливості відмови від авторства

Кодування. Основні поняття.

Різні методи кодування широко використовуються в практичній діяльності людини з незапам'ятних часів. Наприклад, десяткова позиційна система числення – це спосіб кодування натуральних чисел. Інший спосіб кодування натуральних чисел - римські цифри, причому цей метод більш наочний і природний, дійсно, палець - I, п'ятірня - V, дві п'ятірні - X. Однак при цьому способі кодування важче виконувати арифметичні операції над великими числами, тому він був витіснений способом кодування заснованому на позиційній десятковій системі числення. З цього прикладу можна зробити висновок, що різні способи кодування мають властиві тільки їм специфічні особливості, які в залежності від цілей кодування можуть бути як гідністю конкретного способу кодування, так і його недоліком.

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

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

- Подання даних довільної природи (чисел, тексту, графіки) в пам'яті комп'ютера;

- Оптимальна передача даних по каналах зв'язку;

– захист інформації (повідомлень) від несанкціонованого доступу;

- Забезпечення перешкодостійкості при передачі даних по каналах зв'язку;

- Стиснення інформації.

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

Кодування може бути числовим (цифровим) і нечисловим, залежно від виду, в якому представлені кодові символи: числа в системі обчислення або інші якісь об'єкти або знаки відповідно.

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

Число елементів символу коду, яке використовується для представлення одного символу алфавіту вихідного джерела повідомлень, називають значністю коду. Якщо значення коду однакова всім символів алфавіту вихідного повідомлення, то код називають рівномірним, інакше - нерівномірним. Число елементів, що входять до кодового символу, іноді називають довжиною кодового символу.

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

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

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

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

При автоматичній обробці інформації з використанням ЕОМ зазвичай використовують числове (цифрове) кодування, причому, природно, виникає питання обгрунтування використовуваної системи числення. Справді, при зменшенні основи обчислення спрощується алфавіт елементів символів коду, але відбувається подовження символів коду. З іншого боку, чим більша основа системи числення, тим менша кількість розрядів потрібна для представлення одного символу коду, а, отже, і менший час для його передачі, але зі зростанням основи системи числення істотно підвищуються вимоги до каналів зв'язку та технічних засобів розпізнавання елементарних сигналів , які відповідають різним елементам символів коду. Зокрема, код числа, записаного в двійковій системі числення в середньому приблизно в 3,5 рази довше десятичного коду. Так як у всіх системах обробки інформації доводиться зберігати великі інформаційні масиви у вигляді числової інформації, то одним із суттєвих критеріїв вибору алфавіту елементів символів числового коду (тобто основи системи числення) є мінімізація кількості електронних елементів у пристроях зберігання, а також їх простота та надійність.

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

M = a · n. (2.1)

Найбільша кількість різних чисел, яка може бути записана в цьому пристрої N:

N = a n.

Прологарифмувавши цей вираз і висловивши з нього nотримаємо:

n= ln N/ln a.

Перетворивши вираз (2.1) на вигляд

M= a ∙ ln N/ln a(2.2)

можна визначити, за якої підстави логарифмів aкількість елементів Mбуде мінімальним при заданому N. Продиференціювавши по aфункцію M = f(a)і прирівнявши її похідну до нуля, отримаємо:

Очевидно, що для будь-якого кінцевого a

ln N/ ln 2 a ≠ 0

і, отже,

ln a - 1 = 0,

звідки a = e ≈ 2,7.

Так як основа системи числення може бути цілим числом, то авибирають рівним 2 або 3. Для прикладу поставимо максимальну ємність пристрою зберігання N=10 6 чисел. Тоді за різних підстав систем обчислення ( а)кількість елементів ( M)в такому пристрої зберігання буде, відповідно до виразу (2.2), наступні (Таблиця 2.1):

Таблиця 2.1.

а
М	39,2	38,2	39,2	42,9		91,2

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

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

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

Кожне елементарне повідомлення містить певну інформацію як сукупність відомостей (у прикладі) про стан аналізованого джерела інформації. Для кількісного визначення міри цієї інформації не має значення її смисловий зміст, а також ступінь важливості цієї інформації для її одержувача. Зауважимо, що до отримання повідомлення її одержувача завжди є невизначеність щодо того, яке повідомлення я. з-поміж усіх можливих буде йому передано. Цю невизначеність оцінюють за допомогою апріорної ймовірності Р(я) передачі повідомлення я,. Робимо висновок, що об'єктивний кількісний захід інформації, що міститься в елементарному повідомленні дискретного джерела, встановлюється ймовірністю вибору даного повідомлення та визначає сс як функцію цієї всроятності. Ця функція характеризує ступінь невизначеності, наявну в одержувача інформації щодо стану дискретного джерела. Можна зробити висновок, що ступінь невизначеності очікуваної інформації визначає вимоги до каналів передачі.

Загалом ймовірність Р(а,)вибору джерелом деякого елементарного повідомлення я, (далі називатимемо його символом) залежить від обраних раніше символів, тобто. є умовною ймовірністю і не співпадатиме з апріорною ймовірністю такого вибору.

тим, що ^ Р(а:) = 1, так як всі я, утворюють повну групу поді-

ний), і вибір цих символів здійснюється за допомогою деякої функціональної залежності J(a,)= Р(а,) = 1, якщо вибір джерелом символу апріорно визначено, J(a,)= а„ a P(a t ,a)- Імовірність такого вибору, то кількість інформації, що міститься в парі символів, дорівнює сумі кількості інформації, що міститься в кожному із символів я, і я. Його властивість кількісної міри інформації називають адитивністю.

Вважаємо, що Р(а,)- умовна ймовірність вибору символу я, після всіх попередніх символів, а Р(а,,Я,) - умовна ймовірність вибору символу я; після я, і всіх попередніх, а враховуючи, що Р(а 1 ,а 1) = Р(а)Р(я,|я у), умову адитивності можна записати

Введемо позначення Р(а) = Р п Р(ар) = Qі перепишемо умову (5.1):

Вважаємо, що Р, О* 0. Використовуючи вираз (5.2), визначимо вид функції (р (Р).Здійснивши диференціювання, множення на Р* 0 та позначивши РВ = R,запишемо

Зазначимо, що співвідношення (5.3) виконується за будь-яких R ф О і^^О. Однак ця вимога призводить до сталості правої та лівої частин (5.3): Pq>"(P)=Ар"(/?) - до - const. Тоді приходимо до рівняння Рц>"(Р) = Доі після інтегрування отримуємо

Врахуємо, що й перепишемо

Отже, при виконанні двох умов про властивості J(a,) виявилося, що вид функціональної залежності J(a,)від ймовірності вибору символу a tз точністю до постійного коефіцієнта Дооднозначно визначається

Коефіцієнт Довпливає лише на масштаб та визначає систему одиниць вимірювання кількості інформації. Оскільки 1п[Р] Ф 0, то має сенс вибрати До того, щоб міра кількості інформації J(a)була позитивною.

Прийнявши К=-1, запишемо

Звідси випливає, що одиниця кількості інформації дорівнює інформації про те, що настала подія, ймовірність якої дорівнює Me.Така одиниця кількості інформації називається натуральною одиницею. Найчастіше вважають, що До= -, тоді

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

де логарифм може бути з довільною основою.

Властивість адитивності кількісної міри інформації дозволяє на основі виразу (5.9) визначати кількість інформації у повідомленні, що складається з послідовності символів. Імовірність вибору джерелом такої послідовності береться з урахуванням усіх повідомлень, що були раніше.

Кількісний захід інформації, що міститься в елементарному повідомленні а (, не дає уявлення про середню кількість інформації J(A), що видається джерелом при виборі одного елементарного повідомлення а г

Середня кількість інформації характеризує джерело інформації загалом і є однією з найважливіших характеристик систем зв'язку.

Визначимо цю характеристику для дискретного джерела незалежних повідомлень із алфавітом До.Позначимо через Н(А)середня кількість інформації, що припадає на один символ і є математичним очікуванням випадкової величини Л - кількості інформації, що міститься у випадково вибраному символі а

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

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

Ентропія буде максимальною у разі рівності апріорних ймовірностей усіх можливих символів До, тобто. Р(а () = 1 /До,тоді

Якщо джерело незалежно вибирає двійкові символи з ймовірностями Р = Р(а х)і Р 2 = 1 - Р, то ентропія на один символ буде

На рис. 16.1 показана залежність ентропії двійкового джерела від апріорної ймовірності вибору двох двійкових символів, з цього малюнка також видно, що ентропія максимальна при Я, = Р 2 = 0,5

1 про 1 двед - і у двійкових одиницях log 2 2 = 1-

Рис. 5.1. Залежність ентропії при К = 2 від ймовірності вибору одного з них

Ентропія джерел із рівноймовірним вибором символів, але з різними обсягами алфавітів До,логарифмічно збільшується зі зростанням До.

Якщо можливість вибору символів різна, то падає ентропія джерела І(А)щодо можливого максимуму Н(А) пш = log До.

Чим більше кореляції між символами, тим менше свободи вибору наступних символів і менше інформації має символ. Це з тим, що невизначеність умовного розподілу неспроможна перевищувати ентропії їх безумовного розподілу. Позначимо ентропію джерела з пам'яттю та алфавітом Дочерез Н(АА"),а ентропію джерела без пам'яті, але гем алфавітом - через Н(А)і доведемо нерівність

Ввівши позначення Р(аа")для умовної ймовірності вибору символу а,(/ = 1, 2, К)за умови, що раніше вибрано символ ajij =1,2,К)і опускаючи перетворення, без доказу запишемо

що доводить нерівність (5.13).

Рівність у (5.13) або (5.14) досягається у разі, коли

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

Цікаво, що ентропія тексту російською становить 1,5 двійкових одиниць на символ. У той же час при тому ж алфавіті К= 32 з умовою незалежних та рівноймовірних символів Н(А) тп = 5 бінарних одиниць на символ. Отже, наявність внутрішніх зв'язків зменшило ентропію приблизно 3,3 разу.

Важливою характеристикою дискретного джерела є його надмірність р:

Надмірність джерела інформації є безрозмірною величиною, яка знаходиться в межах . Природно, що за відсутності надмірності р = 0.

Для передачі деякого обсягу інформації від джерела, що не має кореляційних зв'язків між символами, при рівній ймовірності всіх символів потрібна мінімально можлива кількість символів, що передаються /7 min: /г 0 (/7 0 Я(Л тах)). Для передачі того ж обсягу інформації від джерела з ентропією (символи взаємопов'язані і нерівноймовірні) знадобиться середня кількість символів п = n„H(A) та JH(A).

Дискретне джерело характеризується також продуктивністю, що визначається числом символів за одиницю часу v H:

Якщо продуктивність І(А)визначати у двійкових одиницях, а час у секундах, то Н"(А) -це число двійкових одиниць за секунду. Для дискретних джерел, що видають стаціонарні послідовності символів досить великої довжини /?, вводять поняття: типові та нетипові послідовності символів джерела, на які можна розбити всі довжини послідовності п.Усі типові послідовності N lMl (A)джерела при п-»оо мають приблизно однакову ймовірність появи

Сумарна ймовірність появи всіх нетипових послідовностей у своїй прагне нулю. Відповідно до рівності (5.11), вважаючи, що ймовірність типових послідовностей /N rm (A),ентропія джерела дорівнює logN TIin (,4) і тоді

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

Тепер припустимо, що інформація джерела кодується та представляє послідовність кодових символів (Ь, (/ = 1,2,..т -підстава коду), узгоджується з дискретним каналом передачі інформації, на виході якого з'являється послідовність сім-

Припускаємо, що операція кодування взаємно однозначна - за послідовністю символів (Ь,)можна однозначно поновити послідовність (я,), тобто. за кодовими символами можна повністю відновити інформацію джерела.

Однак, якщо розглянути символи виходу |?. j та символи входу (/>,), то внаслідок наявності в каналі передачі інформації перешкод, відновлення неможливо. Ентропія вихідної послідовності //(/?)

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

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

Оцінимо втрати інформації в каналі з шумами та кількість інформації, переданої каналом з шумами. Вважаємо, що символ передано правильно, якщо при переданому символі 6 прийнято

символ bjз тим самим номером (/ = j).Тоді для ідеального каналу без шумів запишемо:

За символом bj-на виході каналу внаслідок нерівностей (5.21)

невизначеність неминуча. Можна вважати, що інформація у символі b iне передана повністю і частина її втрачена в каналі через вплив перешкод. Грунтуючись на понятті кількісної міри інформації, вважатимемо, що чисельний вираз невизначеності, що виникає на виході каналу після прийому символу ft; :

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

Зафіксувавши ft. і усереднивши (5.22) за всіма можливими символами, отримуємо суму

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

За усереднення суми (5.23) по всіх ft отримуємо величину Z?), яку позначаємо через н(в/В-Вона визначає кількість інформації, що втрачається під час передачі одного символу по каналу без пам'яті:

де P^bjbjj -спільна ймовірність події, що при передачі

символу Ь.він прийме символ b t.

Н [в/залежить від характеристик джерела інформації на

вході каналу Ута від імовірнісних характеристик каналу зв'язку. За Шенноном у статистичній теорії зв'язку н(в/вназивають ненадійністю каналу.

Умовна ентропія НВ/В, ентропія дискретного джерела

на вході каналу Н(В)та ентропія І ^В) на його виході не можуть бути

негативними. У каналі безперешкодно ненадійність каналу

н(в/в = 0. Відповідно до (5.20) зазначимо, що Н^в/В^

а рівність має місце лише за статистичної незалежності входу і виходу каналу:

Символи на виході не залежать від символів на вході – випадок обриву каналу або дуже сильних перешкод.

Як і раніше, для типових послідовностей можна записати

сати, що за відсутності перешкод його ненадійність

Під переданою в середньому каналом інформацією J[ b/на один символ розуміємо різницю між кількістю інформації на вході каналу J(B)та інформацією, втраченою в каналі /?).

Якщо джерело інформації та канал без пам'яті, то

Вираз (5.27) визначає ентропію вихідних символів каналу. Частина інформації на виході каналу корисна, а решта помилкова, оскільки вона породжена перешкодами в каналі. Звернімо увагу, що н[в/ 2?) виражає інформацію про перешкоди у каналі, а різниця я(й)-Я(й/й) - корисну інформацію, що пройшла через канал.

Зауважимо, що переважна кількість послідовностей, що утворюються на виході каналу, є нетиповими і мають невелику сумарну ймовірність.

Як правило, враховується найпоширеніший вид перешкод - адитивні шуми N(t);сигнал на виході каналу має вигляд:

Для дискретних сигналів еквівалентний шум, виходячи з (5.28), має дискретну структуру. Шум є дискретною випадковою послідовністю, схожою на послідовності вхідного і вихідного сигналів. Позначимо символи аддитивного алфавіту шуму в дискретному каналі через Ц1 = 0, 1,2, т- 1). Умовні можливості переходу в такому каналі

Так як І (^В/?) І (В) то, отже, інформація вихідної послідовності дискретного каналу #(/) щодо вхідний B(t)чи навпаки І (В)-Н^в/в) (5).

Іншими словами, інформація, що передається каналом, не може перевищувати інформації на його вході.

Якщо на вхід каналу надходить у середньому х досимволів за одну секунду можна визначити середню швидкість передачі інформації по каналу з шумами:

де Н(В) = V k J(B,B^ -продуктивність джерела на вході каналу; н(в/в) = У до н(в,в) ~ненадійність каналу за одиницю часу; Н (B) = V k H^B^- продуктивність джерела, утвореного виходом каналу (що видає частину корисної та частину хибної інформації); Н^в/В^ = У до 1/(в/в)- кількість неправдивої інформації,

створюваної на заваді каналі в одиницю часу.

Поняття кількості та швидкості передачі інформації по каналу можна застосовувати до різних ділянок каналу зв'язку. Це може бути ділянка "вхід кодера - вихід декодера".

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

Розглянемо пропускну здатність дискретного каналу та теореми оптимального кодування. Шеннон ввів характеристику, що визначає граничні можливі швидкості передачі по каналу з відомими властивостями (шумами) при ряді обмежень на ансамбль вхідних сигналів. Це пропускна здатність каналу С. Для дискретного каналу

де максимум берегвся за можливими джерелами входу Упри заданому V kта об'єм алфавіту символів входу т.

Виходячи з визначення пропускної спроможності дискретного каналу запишемо

Зауважимо, що С = 0 при незалежному вході та виході (високий рівень перешкод у каналі) і відповідно

при повній відсутностідії перешкод на сигнал.

Для двійкового симетричного каналу без пам'яті

Рис. 5.2.

Графік залежності пропускної спроможності двійкового каналу від параметра рпредставлений на рис. 5.2. При р= 1/2 пропускна спроможність каналу З = 0, умовна ентропія

//(/?//?) = 1. Практичний інтерес

графік представляє при 0

Основна теорема Шеннона щодо оптимального кодування пов'язана з поняттям пропускної спроможності. Її формулювання для дискретного каналу таке: якщо продуктивність джерела повідомлень Н[А)менше пропускної спроможності каналу С:

го існує спосіб оптимального кодування та декодування, при кагорі ймовірність помилки або ненадійність каналу н[а!A j може бути як завгодно мала. Якщо

го таких способів немає.

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

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

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