Cтраница 2
Рассмотрение кодов Хаффмена начнем с кодирования в двоичном алфавите. Случай r - ичного алфавита рассмотрен в разд. Термин символ источника применяется здесь для обозначения входов S, а кодовый алфавит - для обозначения алфавита, в который происходит кодирование. [16]
В этом параграфе будет дана предложенная Д. А. Хаффманом ( 1952) конструктивная процедура отыскания оптимального множества кодовых слов для кодирования данного множества сообщений. Под оптимальностью будет подразумеваться то, что никакое другое однозначно декодируемое множество кодовых слов не имеет меньшую среднюю длину кодового слова, чем заданное множество. Множество длин, задаваемое (3.3.8), обычно не минимизирует п, даже если на нем достигается граница в теореме 3.3.1. Вначале будут рассмотрены двоичные коды и затем будет дано обобщение на произвольный кодовый алфавит. [17]
KL различных последовательностей длины L, которые могут появляться на выходе источника. Предположим, что нужно закодировать эти последовательности в слова кода с фиксированной длиной. Если кодовый алфавит состоит из D символов и если длина каждого кодового слова равна N, то существуют DN различных последовательностей кодовых букв, которые могут быть рассмотрены как кодовые слова. [18]