13. Назначение и виды кодирования.

Код – система знаков, применяемых для передачи, хранения, обработки информации (сообщений).

Кодирование – процесс представления информации в виде кода.

Назначение:

1. представление сведений об объекте в некотором формализованном виде (задача ПП).

Задачи:

1. простое (функ) 35₁₀->100011₂

2. экономное кодирование. 35₁₀->…₁₀₀

3. помехоустойчивое. 35-> тридцать пять

4. криптографическое.

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

Экономное кодирование – для повышения скорости доставки сообщения либо для уменьшения количества символов.

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

Криптографическое – для повышения секретности.

14. Назначение, принципы и свойства экономного кодирования

14. Экономное кодирование

Свойства эргодических последовательностей знаков

Пусть источник вырабатывает 3 символа

x₀->p(x₀)

x₁->p(x₁)

x₂->p(x₂)

Типичная последовательность – если сигнал совпадает со значениями вероятностей, иначе не типичная.

Теорема о равномерности длинных последовательностей.

- все последовательности достаточно большой длины n можно разбить на 2 группы: 1 группа содержит большинство последовательностей, каждая из которых имеет настолько малую вероятность, что даже суммарная вероятность всех таких последовательностей очень мала, и при достаточно большом n будет меньше сколь угодно малого числа. Такие последовательности будут нетипичными для источника.

2 группа включает типичные для источника последовательности, которые отличаются тем, что вероятность их появления практически одинаковые, причем для вероятностей этих последовательностей справедливо утверждение:

p(q_i Q_T)=Const=p_T

бесконечно малая величина

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

Доказательство:

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

(энтропия Н(х))

X={x_i}, m_x

n*p(x_i)=n_i – число повторений i-го символа.

n*p(x1); n*p(x2)… n*p(xn)

p_T=p(x1)^(n*p(x1))*…..

доказали)

Отношение кол-ва типичных последовательностей ко всему числу N_T/N?

N=m_xⁿ = 2ⁿ *log2 m_x

N_T=1/p_T

Выразим N_T через энтропию H(x)

=>N_T<<N

log m_x – это H_max

- избыточность

Если D(x)=0, то все последовательности типичные.

M_x=16, H(x)=3.5bit => H_max 4 при n=50

N_T/N~1/30*10⁶

Возможность (теоретическая основа)экономного кодирования сообщений.

Теорема Шеннона о кодировании канала без помех.

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

Если производительность источника не превышает пропускной способности канала без помех, то существует способ кодирования, позволяющий приблизить ср длину кодового слова к энтропии источника :П(х)≤С_кс

ИС КС xi H(X) Cкс

Скс=максVn=maxVт_кс*Hmax(Y)

П(x)=Vтн*H(x) б/сек

N=H(x)/Hmax(Y)=Log_mymx при равномерном.

nср H(x) -использование хорошее

T/r=n_u – длина сообщения.

V_T*T=n_k

N_k=m_y^nk – число разнообразных кодовых слов.

=2^{nk*log my}=2^{T*Vt*log my}

C_КС=max V_T[H(Y)-H(Y\Z)] H(Y/Z) = 0 т.к. нет помех

=V_T*log m_y=2^T*Cкс

П(х)<=С_кс

N_T=2^T*П(х) <= N_K=2^T*Ckc

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

Принципы и свойства экономного кодирования.

V_TH – скорость выработки сигналов источником.

Если не будет помех( КС без ошибок)

Скорость передачи можно повысить приблизив H(x)->H_max и

Причины избыточности:

1. 

2. 

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

Согласование производительности источника сообщений с пропускной способности КС.

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

	Кодир.первич	вероятность
х1	000..00	P1
x2	000..01	P2
x3	000..10	P3
…
xn	111..11	Pn

– пусть символы не взаимосвязаны, нет корелляции.

При посимвольном кодировании ->неравномерная длина слов разная.

Выигрыш в случае

Требования к экономному кодированию:

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

2. Экономное кодирование должно обеспечивать однозначное декодирование сообщений.

Однозначно декодируемые коды. Неравенство Крафта.

Все возможные коды
Инъективные	Для которых кодовые слова не повторяются
Однозначно-декодируемые	Можно разделить на кодовые слова любую последовательность
Префиксные коды	Ни одно кодовое слово не начинается с другого более короткого

Для получения префиксного кодового слова необходимо построить кодовое дерево:

0 ярус: корень дерева, из которого выходит столько ветвей, сколько символов находится в алфавите.

1 ярус: образуются слова единичной длины

Кодовым словом будут считаться соответствующие конечные узлы графа. Двигаемся от корня к конечному узлу.

Предположим, что выбрано распределение длин кодовых слов по символам источника.

Можно ли для заданного распределения длин построить префиксный код (или однозначно-декодируемый)?

Да, с помощью неравенства Крафта.

Необходимым и достаточным условием существования префиксного кода с объемом m_x и длинами кодовых слов n_i является выполнение условия:

Для любого однозначно-декодируемого кода с длинами слов n_i неравенство Крафта будет также выполняться.

n-const=2 4*2^-2=4*1/4=1=<1 (01 10 00 11)