Принципы эффективного кодирования

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

Различают избыточность естественную и искусственную. Естественная избыточность характерна для первичных алфавитов, а искусственная - для вторичных.

Естественная избыточность может быть подразделена на семантическую и статистическую избыточности.

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

Статистическая избыточность обусловливается не равновероятностным распределением качественных признаков первичного алфавита и их взаимозависимостью. Например, для английского языка избыточность составляет 50 %.

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

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

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

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

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

Эффективными называются коды, представляющие кодируемые понятия кодовыми словами минимальной средней длины. В литературе вместо термина “эффективное кодирование” часто используют так же термины оптимальное или статистическое кодирование.

Впервые идея эффективного кодирования была реализована Морзе. Например, в русском варианте Морзе буква “е” передается одной точкой, а редко встречающаяся буква “ц” - наоборот четырьмя символами.

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

Принципы эффективного кодирования - student2.ru

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

минимальная средняя длина кодового слова оптимального кода обеспечивается в том случае, когда избыточность каждого кодового слова сведена к минимуму (в идеальном случае - к нулю);

кодовые слова оптимального кода должны строиться из равновероятных и взаимно независимых символов.

Из свойств оптимальных кодов вытекают принципы их построения.

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

Принципы эффективного кодирования определяют методику построения эффективных кодов.

Наши рекомендации