Достигнутая степень близости среднего числа k двоичных знаков, приходящихся на одну букву сообщения к H может быть ещё сколь угодно увеличена при помощи перехода к кодированию всё более и более длинных блоков. Это вытекает из следующего общего утверждения, которое называется основной теоремой о кодировании.
Теорема:При кодировании сообщения,разбитого наN-буквенные блоки можно,вы-брав N достаточно большим добиться того, чтобы среднее число k элементарных дво-ичных сигналов, приходящихся на одну букву исходного сообщения было сколь угодно близко к H. Замечание: Очень длинное сообщение из M букв может быть закодировано
при помощи сколь угодно близкого к числу MH (но большего) числа элементарных сиг-налов, если только предварительно разбить это сообщение на достаточно длинные блоки из N букв и сопоставлять отдельные кодовые обозначения сразу целым блокам. Методы кодирования блоков могут быть самыми различными (например, можно использовать методы Шеннона - Фано, Хаффмана)
m-ичные коды
Содержание предыдущих параграфов легко переносится и на случай m-ичных кодов, ис-пользующих m элементарных сигналов. Так, например для построения m-ичных кодов Шеннона - Фано надо лишь разбивать группы символов не на 2, а на m частей, по воз-можности близкой суммарной вероятности, а для построения m-ичного кода Хаффмана надо использовать операцию сжатия алфавита, при которой каждый раз сливаются не две, а m букв исходного алфавита, имеющих наименьшие вероятности.
Ввиду важности кодов Хаффмана остановимся на этом вопросе подробнее. Сжатие ал-фавита, при котором m букв заменяются на одну приводит к уменьшению числа букв на m − 1.Так,как для построения m-ичного кода,очевидно,требуются,чтобы последова-тельность сжатий привела нас к алфавиту из m букв (сопоставляемых m сигналам кода), то необходимо, чтобы число n букв первоначального алфавита было представимо в виде n = m + s(m − 1),где s -целое число сжатий.
Этого всегда можно добиться, добавив, если нужно, к первоначальному алфавиту ещё несколько "фиктивных букв", вероятности появления которых считаются равными 0. По-сле этого, построение m-ичного кода Хаффмана производится точно так-же, как и в случае двоичного кода.
Пример:В случае алфавита из6букв,имеющих вероятности0:4; 0:2; 0:2; 0:1; 0:05; 0:05.Для построения троичного кода Хаффмана надо присоединить к нашему алфавиту ещё одну фиктивную букву с нулевой вероятностью и поступать, как указано в таблице:
Любые из kn чисел являются длинами сообщений некоторого m-ичного
mkn
кода, сопоставляющего n буквам алфавита n последовательностей элементарных сигна-лов, принимающих m возможных значений.
Это утверждение (∗) впервые было доказано в 1949 году американским учёным Л.Крафтом и позднее было обобщено Б. Макмилланом, поэтому неравенство (∗) часто называют неравенством Крафта - Макмиллана. Используя неравенство (∗) можно полу-чить следующий результат:
Теорема:основная теорема о кодировании дляm-ичных кодов.При любом методе коди-рования, использующем m-мчнный код среднее число k элементарных сигналов, прихо-дящихся на одну букву сообщения никогда не может быть меньше отношения logHm , где H - энтропия одной букв сообщения. Однако, оно всегда может быть сделано сколь угодно близким к этой величине, если кодировать сразу достаточно длинные блоки из N букв.
Следствие:Если по линии связи за единицу времени можно передатьLэлементарныхсигналов, принимающих m различных значений, то скорость передачи сообщений по
такой линии не может быть большей, чем v =
L log m
[
букв
]. Однако, передача со
·H
ед.времени
скоростью, сколь угодно близкой к v (но меньшей v) является возможной. Величина C = L · log m зависит лишь от характеристик самой линии связи,в то время,как знаме-натель H характеризует передаваемое сообщение. Величина C указывает наибольшее количество единиц информации, которое можно передать по линии связи за единицу времени. Она называется пропускной способностью линии связи.
