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

Пусть источник вырабатывает 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 ИС     КС Cкс H(X)

Скс=макс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)