Основы построения телекоммуникационных сетей и систем
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
которого k.
При кодировании сообщений данного источника двоичным, равномерным кодом, потребуется двоичных элементов на кодирование каждого сообщения.
Если вероятности P(ai) появления всех сообщений источника равны, то энтропия источника (или среднее количество информации в одном сообщении) максимальна и равна.
В данном случае каждое сообщение источника имеет информационную емкость бит, и очевидно, что для его кодирования (перевозки) требуется двоичная комбинация не менее элементов. Каждый двоичный элемент, в этом случае, будет переносить 1 бит информации.
Если при том же объеме алфавита сообщения не равновероятны, то, как известно, энтропия источника будет
.
Если и в этом случае использовать для перевозки сообщения lр.к.-разрядные кодовые комбинации, то на каждый двоичный элемент кодовой комбинации будет приходиться меньше чем 1 бит.
Появляется избыточность, которая может быть определена по следующей формуле:
, где D - избыточность.
Если средняя загрузка единичного элемента так мала, встает вопрос, нельзя ли уменьшить среднее количество элементов необходимых для переноса одного сообщения и как наиболее эффективно это сделать?
Для решения этой задачи используются неравномерные коды.
При этом, для передачи сообщения, содержащего большее количество информации, выбирают более длинную кодовую комбинацию, а для передачи сообщения с малым объемом информации используют короткие кодовые комбинации.
Учитывая, что объем информации, содержащейся в сообщении, определяется вероятностью появления
,
можно перефразировать данное высказывание.
Для сообщения, имеющего высокую вероятность появления, выбирается более короткая комбинация и наоборот, редко встречающееся сообщение кодируется длинной комбинацией.
Таким образом, на одно сообщение будет затрачено в среднем меньшее единичных элементов
,
чем при равномерном.
Если скорость телеграфирования постоянна, то на передачу одного сообщения будет затрачено в среднем меньше времени:
А значит, при той же скорости телеграфирования будет передаваться большее число сообщений в единицу времени, чем при равномерном кодировании, т.е. обеспечивается большая скорость передачи информации.
Каково же в среднем минимальное количество единичных элементов требуется для передачи сообщений данного источника?
Ответ на этот вопрос дал Шеннон.
Шеннон показал, что
. Нельзя закодировать сообщение двоичным кодом так, что бы средняя длина кодового слова была численно меньше величины энтропии источника сообщений.
. Существует способ кодирования, при котором средняя длина кодового слова немногим отличается от энтропии источника
.
Остается выбрать подходящий способ кодирования.
Эффективность применения оптимальных неравномерных кодов может быть оценена:
1.Коэффициентом статистического сжатия, который характеризует уменьшение числа двоичных элементов на сообщение, при применении методов эффективного кодирования в сравнении с равномерны
Коэффициент относительной эффективности
- позволяет сравнить эффективность применения различных методов эффективного кодирования.
В неравномерных кодах возникает проблема разделения кодовых комбинаций.
Решение данной проблемы обеспечивается применением префиксных кодов.
Префиксным называют код, для которого никакое более короткое слово не является началом другого более длинного слова кода. Префиксные коды всегда однозначно декодируемы.
Введем понятие кодового дерева для множества кодовых слов.
Наглядное графическое изображение множества кодовых слов можно получить, установив соответствие между сообщениями и концевыми узлами двоичного дерева. Пример двоичного кодового дерева изображен на рисунке. 3.2.1.
Две ветви, идущие от корня дерева к узлам первого порядка, соответствуют выбору между 0 и 1 в качестве первого символа кодового слова: левая ветвь соответствует 0, а правая - 1. Две ветви, идущие из узлов первого порядка, соответствуют второму символу кодовых слов, левая означает 0, а правая - 1 и т. д. Ясно, что последовательность символов каждого кодового слова определяет необходимые правила продвижения от корня дерева до концевого узла, соответствующего рассматриваемому сообщению.
Рис. 3.2.1 Кодовое дерево
Формально кодовые слова могут быть приписаны также промежуточным узлам. Например, промежуточному узлу второго порядка на рис.3.2.1 можно приписать кодовое слово 11, которое соответствует первым двум символам кодовых слов, соответствующих концевым узлам, порождаемых этим узлом. Однако кодовые слова, соответствующие промежуточным узлам, не могут быть использованы для представления сообщений, так как в этом случае нарушается требование префиксности кода.
Требование, чтобы только концевые узлы сопоставлялись сообщениям, эквивалентно условию, чтобы ни одно из кодовых слов не совпало с началом (префиксом) более длинного кодового слова.
Любой код, кодовые слова которого соответствуют различным концевым вершинам некоторого двоичного кодового дерева, является префиксным, т. е. однозначно декодируемым.
Код Хаффмана
Одним из часто используемых методов эффективного кодирования является так называемый код Хаффмана.
Пусть сообщения входного алфавита A{a1,a2,a3…ak} ?/p>