Лекции, страница 2

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

В дальнейшем мы будем рассматривать стационарный эргодический источник с независимыми знаками.

Энтропия одного знака.

Пусть источник вырабатывает дискретные знаки (алфавит):

L: z₁, z₂, z₃, z₄,.................z_L

p_1, p_2, p_3, p_{4,...........................}p_L

Следовательно выражение для энтропии одного знака запишется так:

Если бы все знаки встречались бы с равной вероятностью, то

- коэффициент избыточности.

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

- количество информации, которое источник может выдать за единицу времени.

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

Возьмём большое количество знаков (последовательность):

Рассмотрим, какое число последовательностей длины N можно составить из L знаков.

M – число последовательностей: M = L^N.

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

Например: Сколько раз встретиться знак z_i ?

Необходимо вспомнить закон больших чисел:

где N – длина последовательности;

m_i – число, показывающее, сколько раз знак z_i встретится в

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

m_i ~ Np_i (очень длинная последовательность)

Знаки независимы , для независимых событий A , B, C :

P(ABC) = P(A) * P(B) * P(C)

P(ABCA) = P(A)² * P(B) * P(C) , поэтому вероятность P₀ – типичной последовательности,

P₀ = p₁^NP1 * p₂^NP2 * ....

Все типичные последовательности равновероятны , а не типичные - крайне мало вероятны, поэтому количество типичных последовательностей m_T = 1/P₀.

Тогда H_m = log₂m_T = NH(z) – энтропия системы из N независимых частей.

H(z) – энтропия одного знака.

1. Отношение числа типичных последовательностей ко всем возможным.

Чем > N, тем < m_T , но если нет избыточности , то практически все последовательности - типичные.

Любую типичную последовательность можно закодировать набором двоичных символов, число их Q должно быть равно энтропии последовательности.

Q = H_m = log₂m_T .

Но в последовательности N, потому в среднем на 1 знак придется Q/N символов. В то же время Q/N = H_m/N=H(z)

Кодирование , при котором среднее число двоичных символов на знак равно энтропии знака , называется эффективным. Его можно реализовать всегда , если кодировать очень длинные последовательности , но это технически сложно. Поэтому на практике среднее число символов на знак больше энтропии знака , чем меньше различие Q/N и H(z) , тем эффективнее код.

Какова производительность источника непрерывных сообщений?

Данная производительность характеризуется - энтропией.

, где - ширина полосы пропускания.

- среднее время итерации одного отсчёта.

Информационные характеристики канала передачи данных.

U_i V_j

канал передачи

данных

U_i– набор знаков на входе канала, - V_j знаки на выходе.

U_i = V_i - условие идеального канала.

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

- среднее время передачи одного знака .

Пример:

Найти С_к при условии, что по каналу передаётся в одну секунду 10⁶ символов (частичный случай знака “0” или ”1”). “0” или ”1” поступает на вход с равной вероятностью.

А) При этом каждый символ искажается ( воспринимается как противоположный) с вероятносью p=0.1..

H(U)=1;

В общем случае:

, если символ сохраняется с вероятностью р, а "испортится"- с (1-р).

В) В пакете из 4-х символов один символ искажён с вероятностью ¼.

H(u/искаж)=2 (т.к. неизвестно , какой из 4 символов искажен), отсюда

Рассмотрим пропускную способность канала непрерывных сообщений:

Видно , что чем шире полоса пропускания канала , тем выше его пропускная способность. Но...

, где S - спектральная плотность шума.

Обозначим:

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

При увеличении P и уменьшении S( ), увеличивается C_к.

Кодирование информации.

Кодированием информации называется процесс преобразования её в другую форму.

Цели кодирования:

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

- Двоичный код,

- двоично- десятичный код,

-код Грея ( каждое следующее число отличается от предыдущего на 1 разряд)

1. Эффективное кодирование устраняет избыточность кодов.

Примером этого типа кодирования может служить азбука Морзе.

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

1. Кодирование информации с целью сокрытия ее от посторонних пользователей(криптография).

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

Если среднее количество символов на один знак = энтропии одного знака, то это оптимальное кодирование.

1. Код Шеннона – Фано.

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

Пример 1: Пусть источник генерирует z1 c вероятностью p(z1) = 0,5;

z2 c вероятностью p(z2) = 0,25;

z3 c вероятностью p(z3) = 0,125;

z4 c вероятностью p(z4) = 0,125;

p знак код

z1 1

z2 0 1

z3 0 0 1

z4 0 0 0 1

Тогда энтропия будет находиться так:

H(z) = - log₂ - log₂ - log₂ - log₂ = 1,75

А среднее число символов на знак:

Q = 1* + 2* + 3* + 4* = 1,75

Пример 2: Пусть источник генерирует z1 c вероятностью p(z1) = 0,8;

z2 c вероятностью p(z2) = 0,2;

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

Группа

знаков р код

z1 z1 z1 - 0,512 (0,8 * 3) 1

z1 z1 z2 - 0,128 (0,8 * 2 * 0,2) 0 1 1

z1 z2 z1 - 0,128 0 1 0

z2 z1 z1 - 0,128 0 0 1

z2 z2 z1 - 0,032 0 0 0 1 1

z2 z1 z2 - 0,032 0 0 0 1 0

z1 z2 z2 - 0,032 0 0 0 0 1

z2 z2 z2 - 0,032 0 0 0 0 0

H(z)= Q = , где Q – среднее число символов на один знак;

- среднее число символов на три знака;

1. Код Хафмана.

Знаки или группы знаков объединяются попарно и их вероятности суммируются вплоть до получения 1. Образуется " дерево" с общей вершиной. Затем ветви с большей вероятностью приписывается 1 , - с меньшей 0 ( если вероятности равны - выбор произволен)

P

Теоремы Шеннона о передаче информации ( приводятся без доказательства).

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

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

Помехоустойчивые коды.

Корректирующая способность кода, характеризуется:

- количеством ошибок, которые можно обнаружить, r и

- количеством ошибок, которые можно исправить, s.

Для оптимальных кодов r и s максимально, при данных k – число информативных символов в слове - и n – длина слова с учетом добавочных символов.

При данных параметрах k и n количество информативных слов будет 2^k.

При блочном кодировании весь поток информации делится на равные блоки, не обращая внимания на границы слов.

Кодировка осуществляется с помощью алгебраических действий по следующим правилам:

1+1=0

1=-1

1*0=1

1*1=1.

Для описания кода вводится еще одна характеристика называемая кодовым расстоянием, d – это минимальное число разрядов , которыми отличаются различные кодовые слова. Для успешного кодирования должны выполняться два условия:

d>=r+1

d>=2*s+1.

Код Хэмминга.

На примере кода Хэмминга с параметрами n=7 и k=4 рассмотрим помехоустойчивый код.

В основе кода лежит базовая последовательность из 4 слов по 7 символов в каждом (d>=3), причем в каждом слове единиц должно быть не меньше, чем кодовое расстояние. Эта последовательность записывается в виде матрицы g, называемой порождающей,