Кодування алфавітний - це

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

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

А = 1.. а п> - алфавіт каналу зв'язку, т. е. перелік сигналів, к-які можуть передаватися по каналу, t (а i)-тривалість сигналу а i. В = 1,. b т> - алфавіт мови повідомлень. У найпростішому випадку джерело повідомлень є імовірнісна схема. на виході до-рій в кожен момент дискретного часу з'являється одна з букв У, причому ймовірності Pi = p (bi) появи букв не залежать від часу. Схема кодування f відображає літери Вв слова А * (А * - моноїд, породжений A), f (bi) = vi і слова В * кодуються побуквенно: f (bi1. Bik) = f (bi1). f (bik). Таким чином, відображення f повністю задається кодом V = v1. . vm>. Якщо f взаємно однозначно, то завдання схеми декодування - відновити передане повідомлення, реалізуючи відображення f -1.

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

(Е f зв. Також вартістю кодування f). У загальному випадку Е f залежить від структури коду, к-раю описується структурним многочленом

- виробляє функцією, що перераховує слова коду по їх складу. В окремому випадку, коли t (а 1) =. = T (а n) = t, маємо т. Е. Е f визначається тільки спектром довжин слів коду 1. l2,. 1 т), де li - довжина слова vi. Для цього випадку проблема вибору оптимального коду (т. Е. Мінімізує вартість) вирішується повністю; доведено [2] необхідна і достатня спектральний умова для існування однозначно декодіруемой коду

Показано [4], що разом з нерівністю (1) умова

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

Для складності декодування, з абстрактної точки зору, найбільш цікава якісна міра: наявність властивості кінцівки затримки декодування, що означає можливість реалізації декодування кінцевим автоматом (кількісні оцінки складності схемної реалізації автоматів виходять за рамки теорії кодування). Так зв. префіксние коди (властивість префіксних полягає в тому, що ніяке слово Vне є початковим відрізком іншого слова з V) всі мають це властивість. Було показано [2], що будь-який код, для к-якого f взаємно однозначно, спектрально еквівалентний недо-рому префіксних коду. Клас префіксних кодів відносно добре Оглянувши, чим і пояснюється результативність дослідження випадку t (а 1) =. = T (а n).

У загальному випадку відомі алгорітміч. вирішення питань розпізнавання властивостей взаємної однозначності кодування і кінцівки затримки декодування. Властивість взаємної однозначності f можна розглядати як мінімальний рівень завадостійкості коду V. Є алгорітміч. рішення задачі обчислення фактичної коректує здатності довільного коду в загальному випадку і з додатковою вимогою кінцевої затримки декодування. Клас всіх вільних кодів (т. Е. Однозначно декодуємих) влаштований досить складно, але екстремальні вимоги до кодів часто призводять до суттєвих обмежень. Напр. показано, що для максимальних по включенню кодів (для яких брало нерівність (1) звертається в рівність і к-які зв. повними, так як для них і лише для них алфавіт каналу використовується повністю в тому сенсі, що будь-яке слово з А * є частиною деякого закодованого повідомлення) властивість кінцевої затримки має місце в тому і тільки в тому, випадку, якщо код префіксний.

Літ. : [1] Шеннон К. Роботи по теорії інформації і кібернетики, пров. з англ. М. 1963; [2] Мак-Міллан Б. "Кібернетіч. Зб.", 1961, ст. 3, с. 88-92; [3] Xаффмен Д. там же, с. 79-87; [4] Schutzenberger M. P. "Information and Control", 1967, v. 11, p. 396-401; [5] Марков А л. А. "Пробл. Кібернетики", 1962, ст. 8, с. 169-86; 1964 в. 12, с. 137 - 53; 1967 в. 19, с. 307-09; 1976, в. 31, с. 77 - 108.

Математична енциклопедія. - М. Радянська енциклопедія. І. М. Виноградов. 1977-1985.