Кодування, операція ототожнення символів або груп символів одного коди з символами або групами символів іншої коди. Необхідність До. виникає перш за все з потреби пристосувати форму повідомлення до даного каналу зв'язку або якому-небудь іншому пристрою, призначеному для перетворення або зберіганню інформації. Так, повідомлення представлені у вигляді послідовності букв, наприклад російської мови, і цифр, за допомогою телеграфних код перетворяться в певні комбінації посилок струму. При введенні в обчислювальні пристрої зазвичай користуються перетворенням числових даних з десяткової системи числення в двійкову і т.д. (див. Кодуючий пристрій ) .
До. у інформації теорії застосовують для досягнення наступних цілей: по-перше, для зменшення так званою надмірності повідомлень і, по-друге, для зменшення впливу перешкод, що спотворюють повідомлення при передачі по каналах зв'язку (див. Шенона теорема ) . Тому вибір нової коди прагнуть найбільш вдалим чином погоджувати із статистичною структурою даного джерела повідомлень. Якоюсь мірою це узгодження є вже в коді телеграфному, в якому частіше букви, що зустрічаються, позначаються коротшими комбінаціями крапок і тире.
Прийоми, вживані в теорії інформації для досягнення вказаного узгодження, можна пояснити на прикладі побудови «економних» двійкових код. Хай канал може передавати лише символи 0 і 1, витрачаючи на кожен один і той же час t. Для зменшення часу передачі (або, що те ж саме, збільшення її швидкості) доцільно до передачі кодувати повідомлення так, щоб середня довжина L кодового позначення була найменшою. Хай х 1 , х 2 ..., x n позначають можливі повідомлення деякого джерела, а p 1 , р 2 , ..., р 2 — відповідна ним вірогідність. Тоді, як встановлюється в теорії інформації, при будь-якому способі До.,
де L ³ Н, (1)
—
ентропія джерела. Кордон для L у формулі (1) може не досягатися. Проте при будь-яких p i існує метод До. (метод Шенона — Фено), для якого
L £ Н + 1. (2)
Метод полягає в тому, що повідомлення розташовуються в порядку убування вірогідності і отриманий ряд ділиться на 2 частини з вірогідністю, по можливості близькою один до одного. Як 1-й двійковий знак приймають 0 в 1-ій частині і 1 — в 2-ій. Подібним же чином ділять навпіл кожну з частин і вибирають 2-й двійковий знак і т.д., поки не прийдуть до частин, що містять лише по одному повідомленню.
Приклад 1. Хай n = 4 і p 1 =9/16, р 2 = р 3 = 3/16, p 4 = 1/16. Вживання методу ілюструється таблиці.:
х,
Pi
Кодове позначення
х 1
9/16
0
х 2
3/16
1
0
х 3
3/16
1
1
0
х 3
1/16
1
1
1
B даному випадку L = = 1,688 і можна показати, що жоден ін. код не дає меншого значення. В той же час Н = 1,623. Все сказане застосовно і до випадку, коли алфавіт нової коди містить не 2, як передбачалося вище, а m > 2 букв.(буквально) При цьому лише величина Н у формулах (1) і (2) має бути замінена велічиной H/log 2 m.
Завдання про «стискування» запису повідомлень в даному алфавіті (тобто завдання про зменшення надмірності) може бути вирішена на основі методу Шенона — Фено. Дійсно, з одного боку, якщо повідомлення представлені послідовностями букв довжини N з м-кодів -буквенного алфавіту, то їх середня довжина L N після До. завжди задовольняє нерівності L N ³ Nh/log 2 т, де Н — ентропія джерела на букву. З іншого боку, при скільки завгодно малому e>0 можна добитися виконання при всіх чималих N нерівності
. (3)
З цією метою користуються До. «блоками»: по даному e вибирають натуральне число s і ділять кожне повідомлення на рівні частини — «блоки», що містять по s букв.(буквально) Потім ці блоки кодують методом Шенона — Фено в той же алфавіт. Тоді при чималих N буде виконане нерівність (3). Справедливість цього твердження найлегше зрозуміти, розглядаючи випадок, коли джерелом є послідовність незалежних символів 0 і 1, що з'являються з вірогідністю відповідно р і q, p ¹ q. Ентропія на блок дорівнює s-кратній ентропії на одну букву, тобто рівна sh = s ( plog 2 1/p+qlog 2 1/q ) . Кодове позначення блоку вимагає в середньому не більш sh + 1 двійкових знаків. Тому для повідомлення довжини N букв L N £(1+ N/s ) ( sh +1) = N ( H +1 /s ) (1+ s/n ) , що при чималих s і N/s приводить до нерівності (3). При такому До. ентропія на букву наближається до свого максимального значення — одиниці, а надмірність — до нуля.
Приклад 2. Хай джерелом повідомлень є послідовність незалежних знаків 0 і 1, в якій вірогідність появи нуля рівна р = 3 / 4 , а одиниці q = 1 / 4 . Тут ентропія Н на букву рівна 0,811, а надмірність — 0,189. Найменші блоки ( s = 2), тобто 00, 01, 10, 11, мають відповідно вірогідності р 2 = 9 / 16 , pq = 3 / 16 , qp = 3 / 16 , q 2 = 1 / 16 . Вживання методу Шенона — Фено (див. приклад 1) приводить до правила К.: 00®0 01®10, 10®110, 11®111. При цьому, наприклад, повідомлення 00111000... набере вигляду 01111100... На кожну букву повідомлення в колишній формі доводиться в середньому 27 / 32 = 0,844 букв в новій формі (при нижньому кордоні коефіцієнта стискування, рівному Н = 0,811). Ентропія на букву в новій послідовності рівна 0,811/0,844 = 0,961, а надмірність рівна 0,039.
До., що зменшує перешкоди, перетворилося на великий розділ теорії інформації, зі своїм власним математичним апаратом, значною мірою чисто алгеброю (див. Канал, Шенона теорема і літературу при цих статтях).
