logo
ТИКЛекции

5.1. Основные понятия и определения

Оптимальным статистическим (экономным) кодированием называется кодирование, при котором обеспечивается распределение времени на передачу отдельных символов алфавита в зависимости от априорных вероятностей их появления:

;

где Cп - пропускная способность канала; pi - априорная вероятность i –й кодовой комбинации; ti -длительность i-й кодовой комбинации.

Оптимальными неравномерными кодами (ОНК) - называются коды, в которых символы алфавита кодируются кодовыми словами минимальной средней длины. Эти коды являются безизбыточными в информационном плане. Основная теорема кодирования для каналов без шумов доказывает принципиальную возможность построения оптимальных кодов. Из нее вытекают принципы построения оптимальных кодов:

1. Каждая кодовая комбинация должна содержать максимальное количество информации, что обеспечивает максимальную скорость передачи данных.

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

При таком кодировании избыточность кода, которая вызвана неравной вероятностью символов алфавита, сводится к минимуму (практически к нулю). Оптимальные коды являются неравномерными блочными кодами, при их построении необходимо обеспечить однозначность декодирования.

Построение оптимальных кодов сводится к построению префиксных деревьев. Префиксным (неприводимым) - называется код, в котором ни одна кодовая комбинация не является началом другой. Для обеспечения этого свойства кодовые комбинации должны записываться от корня кодового дерева. Построение ведется от вершины.

Возможность однозначного декодирования неравномерного кода обеспечивается выполнением требования разделимости (префиксности) кодовых комбинаций.

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

Существует много методов оптимального, статистического кодирования. Наиболее часто используют оптимальное кодирование по методу Шеннона - Фано и Хаффмена.