Теория информации |
Конспект лекций |
3. ПОБУКВЕННОЕ КОДИРОВАНИЕ
3.1 Определения и примеры
В этом параграфе приведены некоторые теоремы о свойствах побуквенного кодирования. Одной из основных задач теории информации является построение кодов для сообщений, порождаемых некоторым источником информации, для дальнейшей передачи уже закодированных сообщений по каналу связи. Очевидным требованием к кодированию сообщений источника является условие однозначного декодирования, т.е. после получения закодированного сообщения получатель должен иметь возможность прочитать исходное сообщение. В данной главе рассматривается задача построения однозначно декодируемых кодов без учета статистики источника информации, т.е. можно считать, что сообщения источника независимы и равновероятны.
Определение. Пусть известны алфавит источника информации и кодовый алфавит
. Кодирование сообщения, которое порождает источник информации, будем понимать как сопоставление кодовой последовательности всему сообщению в целом или как построение кода сообщения из кодов его частей (побуквенное кодирование).
Пример 3.1 Пусть ,
. Побуквенное кодирование символов источника
позволяет следующим образом закодировать сообщение
Пример 3.2 Азбука Морзе. Входной алфавит – английский. Наиболее часто встречающиеся буквы кодируются более короткими словами:
Определение. Побуквенное кодирование задается таблицей кодовых слов: – конечные последовательности в алфавите B.
Определение. Множество кодовых слов называется множеством элементарных кодов. Используя побуквенное кодирование, можно закодировать любое сообщение
следующим образом
,
т.е. общий код сообщения складывается из элементарных кодов символов входного алфавита.
Определение. Количество букв в слове (последовательности символов) называется длиной слова. (Обозначение
) Пустое слово, т.е. слово, не содержащее ни одного символа обозначается
. Если
, то
– начало (префикс) слова
, – окончание (постфикс) слова
.