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

за счет их перекодировки.

Применяется практически во всех архиваторах типа

Rar, Zip и др.

Позволяют сжать информацию в в 2-3, max в 4 раза, но при этом происходит полное восстановление сжатой информации «бит в бит»

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

восстановление информации «бит в бит»

Например, при передаче речи можно допускать

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

форме, удобной для передачи по данному каналу.

Операция, обратная кодированию, называется декодирование.

Общее

определение кодирования и кода

модулятор
ЛС –линия связи
ДМ - демодулятор
ДК- декодер канала
ДИ – декодер источника
П

- приемник

Схема системы передачи информации

сигнал.

Дискретные сообщения складываются из букв,
а непрерывные сообщения можно

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

При большом объеме алфавита прибегают к представлению букв в другом алфавите с меньшим числом букв, которые будем называть символами. Т. е. выполняется КОДИРОВАНИЕ


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

Число символов в кодовой комбинации называется ее значностью.

обеспечивал.:
простоту аппаратуры различения отдельных символов;
минимальное время передачи;
минимальный объем запоминающего устройства

при хранении;
простоту выполнения в принятой системе арифметических и логических действий.

Статистические свойства источника сообщений и помех в канале связи при этом не принимаются во внимание.

Техническая реализация процесса кодирования в таком простейшем виде при непрерывном входном сигнале осуществляется аналого-кодовыми (цифровыми) преобразователями.

В процессе преобразования букв в символы нужно:

согласование свойств источника сообщений со свойствами канала связи.

При отсутствии помех

это непосредственно дает выигрыш во времени передачи или в объеме запоминающего устройства.
Такое кодирование получило название эффективное кодирование.

В процессе преобразования букв в символы нужно:

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

При наличии

помех

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

с учетом статистических закономерностей помехи в канале связи.

Такое кодирование получило название помехоустойчивого.

КК - кодер канала

практически отсутствуют, то введение как КИ, так и КК нецелесообразно.

Если

избыточность ИС высока, а помехи малы, целесообразно введение только КИ.
Когда избыточность источника мала, а помехи велики, целесообразно введение КК.

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

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

М.

Получаемый на выходе модулятора сигнал Y подготовлен к передаче по конкретной

линии связи ЛС.

В устройство декодирования сигналов в символы (демодулятор ДМ) из линии связи приходит сигнал, искаженный шумом, который обозначен на схеме – Z.

После кодера канала КК

сообщений (декодер источника ДИ)
выдают декодированное сообщение W получателю П (человеку или

машине).

Устройства декодирования

из кодовых букв (цифр).

Если исходный алфавит содержит m букв,

то для построения равномерного кода с
использованием k кодовых букв необходимо удовлетворить соотношение
m ≤ kq ,
где q - количество элементов в кодовой последовательности.

Итак

q - разрядные числа в k-ичной системе счисления

Например,
при

двоичном кодировании 32 букв русского алфавита используется
q = log232 = 5 разрядов,
на чем и основывается телетайпный код.

Для построения равномерного кода

закодировать алфавит, состоящий из 64 букв.
Для этого потребуется q

= log264 = 6 двоичных разрядов или q = log864 = 2 восьмеричных
разрядов.
При этом буква с номером 13 при двоичном кодировании получает код 001101, а при
восьмеричном кодировании 15.

уровень настолько мал, что вероятность искажения практически равна нулю, можно

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

Основная теорема Шеннона о эффективном кодировании

считать:
J(Z; Y) = Hапр(Z) – Hапост(Z) = Hапр(Y),

так как H(Y) = H(Z) и H(Y/Z) = 0, а

max{J(Z; Y)} = Hmax(Y) – max энтропия источника сигнала, получающаяся при равномерном распределении вероятностей символов алфавита Y.
p( y1) = p( y2) = ... = p( ym) = 1/My,
т.е. Hmax(Y) = logaMy

теорема Шеннона

за единицу времени равна:

Cy = Vy · max{J(Z; Y)} = Vy · Hmax(Y) = Vy · logaMy
или Ck = Vk · logaMy,
Vk – скорость

передачи определяется частотными переключательными способностями канала:

Теорема Шеннона

равна пропускной способности канала , т.е. равна энтропии источника, приходящаяся

на единицу времени(бит,сек=бод)

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



Не существует способа кодирования, позволяющего сделать эту скорость большей, чем Vx max.

Теорема Шеннона

всю информацию, вырабатываемую источником при ограниченном объеме буфера;
H(x) > C – такого

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

Теорема Шеннона

чтобы средняя длина кода lср (количество символов сигнала на одну букву сообщения)

была сколь угодно близкой к величине:

Следствия из теоремы Шеннона

вероятность встречи данного элемента алфавита;
li – количество символов в i-ой кодовой комбинации;
ε

– бесконечно малая величина ≥ 0, т.е. lim lср = H(x).

Следствия из теоремы Шеннона

тем лучше мы закодировали. В инженерной практике это различие можно

считать допустимым 3÷5% (до 10%).

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

Чем ближе lср к H(x), тем лучше мы закодировали.

В инженерной практике это различие можно считать допустимым 3÷5% (до 10%).

Следствия из теоремы Шеннона

распределение вероятностей их употребления, то
H(x) = log2 M,
а lср = log2 M.
Пределы эффективного кодирования:
H(x) ≤ lср ≤

log2 M.

Следствия из теоремы Шеннона

статистические свойства источника сообщений, можно минимизировать среднее число двоичных символов,

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

Методики эффективного кодирования

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

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

Методики эффективного кодирования

меньшей длины, редко встречающийся — кодом большей длины.
Коды Шеннона — Фано префиксные,

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

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

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

другу.
В префиксном коде для первой части алфавита присваивается двоичная цифра «0», второй части — «1».
Полученные части рекурсивно делятся и их частям назначаются соответствующие двоичные цифры в префиксном коде.

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

собой целочисленные отрицательные степени двойки. Среднее число символов на букву

в этом случае точно равно энтропии источника.

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

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

кода Шеннона-Фано, приходящихся на один символ алфавита источника, равно:
nср=

∑ Li*P(ai) =1*0,4+ 2*0,2+3*0,2+4*0,1+5(0,05+0,05)=2,3 бит

кода Шеннона-Фано, приходящихся на один символ алфавита источника, равно:
nср=

∑ Li*P(ai) =1*0,4+ 2*0,2+3*0,2+4*0,1+5(0,05+0,05)=2,3 бит
Энтропия источника равна:

в последовательностях символов осталась.

Из теоремы Шеннона следует, что эту избыточность

можно устранить, если перейти к кодированию достаточно большими блоками.

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

вероятностями появления
P(Z1) = 0.7 и P(Z2) = 0.3.
Поскольку P(Z1) не равно P(Z2),

то последовательность из таких букв будет обладать избыточностью. Однако при буквенном кодировании мы никакого эффекта не получим.
Действительно, на передачу каждой буквы требуется либо 1, либо 0, то есть
lср = 1 · 0.9 + 1 · 0.1 = 1,
в то время как
H(Z) = –0.7log2 0.7 – 0.3log2 0.3 = 0.88бит.
Избыточность составляет R(A)=0,12 бит/символ.

Методика Шеннона-Фэно кодирование блоками

бит.
На один символ алфавита источника приходится в среднем

1,81/2=0,905
бит/символ.
Избыточность составляет R(A)=0,905 – 0,88=0,025 бит/символ.

Методика Шеннона-Фэно кодирование блоками

кода с наименьшей для данного распределения вероятностей средним числом символов

на букву.

Метод широко применяется в факсимильных устройствах.

Построение кода Хаффмана основывается на преобразовании, которое называется сжатием алфавита.

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

Два наименее вероятных символа алфавита А будем считать одним символом

нового сжатого алфавита А1.
Располагаем символы алфавита А1 в порядке убывания вероятности. И снова подвергаем его сжатию.
Повторяем процедуру, пока не придем к алфавиту, содержащему всего два символа.

Методика Хаффмена Алгоритм:

и 1 (в нашем примере – нижнему). Это старшие символы

будущих кодовых слов.
В предпоследнем алфавите кодовые обозначения получаются следующим образом:
• Символ, который сохранился в последнем алфавите, имеет то же кодовое обозначение.
• Символам, которые слились в последнем алфавите, приписывают справа 0 (в нашем примере – верхнему символу) и 1 (нижнему символу).
Повторяем процедуру, последовательно возвращаясь к исходному алфавиту.

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

что никакой другой метод кодирования алфавита не позволяет получить среднее

число
двоичных символов на один символ алфавита меньше, чем в случае кода Хаффмана.

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