Пример.

Русский алфавит, включая пропуски между словами, содержит 32 элемента, следовательно, при одинаковых вероятностях появления всех 32 элементов алфавита, неопределенность, приходящаяся на один элемент, составляет Н_max = log 32 = 5 бит. Анализ показывает, что с учетом неравномерного появления различных букв алфавита H = 4,42 бит, а с учетом зависимости двухбуквенных сочетаний H₁ = 3,52 бит.

Таким образом, D = 1 - 3,52 / 5 = 0,30.

Важно понимать, что избыточность – не всегда нежелательное явление. Для повышения помехоустойчивости кодов избыточность необходима и ее вводят искусственно.

Для увеличения скорости передачи сообщений избыточность, получаемую при кодировании, необходимо уменьшить. Способом уменьшения избыточности сообщений является построение эффективных кодов.

Кодирование информации

Пусть кодирующее устройство преобразует сообщения, состоящие из знаков алфавита Z мощности n, в сигналы, состоящие из символов другого алфавита X мощности m. Y – алфавит символов сигнала на выходе линии связи.

При кодировании каждая буква исходного алфавита представляется различными последовательностями, состоящими из кодовых символов.

Равномерное кодирование

Если исходный алфавит Z содержит n букв, то для построения равномерного кода в алфавите X с использованием m кодовых букв необходимо удовлетворить соотношение

,

где l - количество элементов в кодовой последовательности. Поэтому

.

Для построения равномерного кода достаточно пронумеровать буквы исходного алфавита и записать их коды как l-разрядные числа в m-ичной системе счисления.

Пример. При двоичном кодировании 32 букв русского алфавита используется l = log₂32 = 5 разрядов, на чем и основывается телетайпный код.

Очевидно, что максимальное количество информации, которое может содержаться в кодовой комбинации алфавита X для знака алфавита Z, равно . Мы выбирали l исходя из неравенства . Таким образом, равномерный код обладает избыточностью, т.е. для кодирования используется больше символов, чем это минимально необходимо.

Эффективное кодирование

Устранение избыточности кода достигается применением неравномерных кодов, в которых буквы, имеющие наибольшую вероятность, кодируются наиболее короткими кодовыми последовательностями, а более длинные комбинации присваиваются «редким» буквам.

Кодирование называется эффективным, если средняя длина кода равна (в случае двоичного кодирования, средняя длина кода равна энтропии алфавита источника).

Первая теорема Шеннона позволяет утверждать, что эффективное кодирование существует, но не дает нам способа такого кодирования:

Теорема Шеннона (первая). Сообщения всегда можно закодировать так, чтобы средняя длина кода была сколь угодно близкой к величине (но не меньше!).

Замечание 2. Учитывая, что в худшем случае (для равномерного кода) выбирается равным , получаем .

Эффективное кодирование устраняет избыточность, приводит к сокращению длины кода, а значит и длины сообщений. Следовательно, позволяет уменьшить время передачи сообщений или объем памяти, необходимой для их хранения. Итак, наша задача обеспечить такое кодирование, при котором будет минимально возможным.

Все расчеты, включая сформулированную теорему, справедливы при отсутствии помех