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

Эффективное кодирование решает задачу более компактной записи сообщений, вырабатываемых источником за

Сжатие в большее число раз

Применяется, если же не требуется восстановление

Кодирование – в широком смысле слова – это представление сообщений в форме,

ИИ – источник информации
КИ – кодер источника
КК –кодер канала
М – модулятор
ЛС

Сообщению X на выходе источника информации (ИИ) необходимо поставить в соответствие определенный сигнал.

1. Преобразовать информацию в такую систему символов (код), чтобы он обеспечивал.:
простоту

2. Второй целью кодирования является на основании теорем Шеннона – согласование

в канале эффективное кодирование позволяет преобразовать входную информацию в последовательность символов,

имеет целью обеспечить заданную достоверность при передаче или хранении информации путем

Если избыточность источника сообщений (ИС) и помехи в канале связи практически

кодированный сигнал поступает в устройство кодирования символов сигналами – модулятор М.

Устройство декодирования помехоустойчивого кода декодер канала ДК и
устройство декодирования сообщений

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

достаточно пронумеровать буквы исходного алфавита и записать их коды как q

Кроме двоичных кодов, наибольшее распространение получили восьмеричные коды.
Например, необходимо закодировать

В этом случае среднее количество информации, переносимое одним символом, можно считать:
J(Z; Y)

следовательно, пропускная способность дискретного канала без помех в единицах информации за

Если источник информации создает поток информации
,
Такой что, производительность источника информации равна

Согласно сформулированной теореме существует метод кодирования, позволяющий при:
H(x) ≤ C – передавать всю

если источник информации имеет энтропию H(X),
то сообщения можно закодировать так, чтобы

Это следует из равенства:
.
Таким образом, lср выступает критерием эффективности кодирования. Чем ближе lср к H(x), тем

Это следует из равенства:
(Производительность ист.=попускн.сп .к=макс.ск. Канала без помех=произ макс. скорости

Из этого же критерия следует, что если буквы имеют равномерное распределение

В большинстве случаев буквы сообщений преобразуются в последовательности двоичных символов.
Учитывая статистические

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

Алгоритм использует коды переменной длины: часто встречающийся символ кодируется кодом меньшей

Символы первичного алфавита m1 выписывают по убыванию вероятностей.
Символы полученного алфавита делят на

Наибольший эффект сжатия получается в случае, когда вероятности букв представляют собой

Методика Шеннона-Фэно Пример:

В равномерном коде длина сообщения n=3
Среднее число двоичных символов кода

Методика Шеннона-Фэно

В равномерном коде длина сообщения n=3
22<6<23,
Среднее число двоичных символов кода

Условие эффективного кодирования:
max H(Z): log2 m ≥ lср ≥ H(Z) + ε,
но H(Z) < lср.
Следовательно, некоторая избыточность в

Рассмотрим сообщения, образованные с помощью алфавита, состоящего из 2-х букв Z1 и Z2 
с вероятностями

В этом случае средняя длина кодового слова составляет:
с =1,81 бит.

От указанного недостатка свободна методика Хаффмена.
МХ гарантирует однозначное построение кода

Расположить символы исходного алфавита А в порядке убывания вероятности.
Два

Припишем символам последнего алфавита кодовые обозначения 0 (например - верхнему) и

Методика Хаффмена пример 1

Методика Хаффмена пример2

Методика Хаффмена пример 2