Эффективность кодирования
Эффективность кодирования показывает, насколько экономно набор сообщений представлен кодовыми словами: сколько символов в среднем требуется для передачи одного сообщения и есть ли лишняя длина относительно теоретически возможной.
Средняя длина кода
Если сообщения \(m_1, m_2, \ldots, m_n\) встречаются с вероятностями \(p_1, p_2, \ldots, p_n\), а длины соответствующих кодовых слов равны \(l_1, l_2, \ldots, l_n\), то средняя длина кода вычисляется как взвешенное среднее. Редкие сообщения могут иметь длинные коды, а часто встречающиеся — короткие. Это типичный принцип кода переменной длины.
Если все сообщения равновероятны, средняя длина равна обычному среднему арифметическому длин кодовых слов. Для сравнения с нижней границей используют количество информации или энтропию источника \(H\). Приближённо эффективность можно оценить отношением \(H\) к средней длине: чем ближе это отношение к 1, тем меньше потери и избыточность.
Пусть два сообщения имеют вероятности \(0{,}75\) и \(0{,}25\), а их кодовые слова имеют длины 1 и 3 символа. Тогда \(\bar{L}=0{,}75\cdot1+0{,}25\cdot3=1{,}5\) символа на сообщение. Код эффективнее равномерного кода длины 3, потому что часто передаваемое сообщение получает короткое слово.
Средняя длина кода — это не длина самого длинного кодового слова и не длина кода для одного выбранного сообщения. Избыточность также не равна избыточному кодированию: здесь речь идёт о количественной оценке лишних символов, а не обязательно о добавлении проверочных данных.
Как изменится средняя длина, если более частому сообщению назначить более короткое кодовое слово?
Главное
- Эффективность кодирования оценивают прежде всего по средней длине кодовых слов.
- Средняя длина вычисляется как \(\bar{L}=\sum p_i l_i\).
- Чем ближе код к оптимальному кодированию и чем меньше его избыточность, тем выше его эффективность.