1 страница. В правой части от P (U) зависит только H (Z), следовательно, максимизировать нужно только его H (Z)

.

В правой части от P (U) зависит только H (Z), следовательно, максимизировать нужно только его H (Z). В соот­ветствии со 2 свойством энтропии, максимальное значение H (Z) = log N и реализуется оно тогда, когда все принятые символы z_j равновероятны и независимы. Легко убедиться, что это условие выполняется, если и входные символы рав­новероятны и независимы (при p (u_k) = 1 / N). В этом случае, по формуле полной вероятности имеем:

В соответствие с 1.26, последовательная сумма включает в себя одно слагаемое (1 – p) и (N – 1) – слагаемое p / (N – 1). Поэтому, можно записать:

p (z_j) = 1 / N (1 – p + (N – 1) * p / (N – 1),

т.е z_j имеет равномерное распределение. При этом, H (Z) = log N и пропускная способность в расчете на один символ будет равна

(1.27)

Отсюда, пропускная способность С равна:

(1.27a)

Для двоичного симметричного канала (N = 2), пропускная способность:

(1.28)

Зависимость C / v_k (p) в соответствие с 1.28 имеет вид:

При p = 1 / 2, пропускная способность двоичного канала С = 0, т.к. при такой вероятности ошибки последо­вательность выходных двоичных данных символов можно получить, совсем не передавая сигналы по каналу, а выбирая их наугад.

Т.о., при р = 1 / 2, последовательность на вход и выход канала независимы (обрыв канал).

То, что пропускная способность при р = 1 в двоичном канале такая же, что и р = 0 объясняется тем, что при р = 1 доста­точно все входные символы проинвертировать, чтобы абсолютно правильно восстановить входной сигнал.

Вопрос 14: Задача согласования дискретного источника с дискретным каналом без шума.

П

редположим, что мы имеем дискретный канал, вероятность возникновения ошибки равна 0 (в идеале 0). Такой канал называют идеальным каналом без памяти (каналом без шума). В соответствии с 1.25, пропускная способность такого канала C = v_k * log N. При наличии идеального канала естественно поставить вопрос о возможности передачи по нему без потерь от произвольного дискретного источника, характеризующегося некоторой производительностью H’ (U) со скоростью, равной пропускной способности канала. Схема построения такой системы передачи информации показано на рисунке 2.1:

Необходимость включения кодера и декодера в состав этой системы обусловлено следующими обстоятельст­вами:

Как показано в параграфе 1.6, для того, чтобы скорость передачи информации в канале была равна его пропу­скной способности, на вход канала должен действовать дискретный источник с определенными статическими свойст­вами, максимизирующие величину I (Z, Z). В частности, в интересующем нас случае идеальном канале без помех такой источник должен просто обладать максимальной энтропии или нулевой избыточностью, т.е. выдавать независимые рав­новероятные сообщения. В то же время в своей постановке задачи мы пожелали иметь возможность передавать с мак­симальной скоростью сообщения от произвольного источника с любыми статистическими свойствами, т.е. имеющего ненулевую избыточность. Т.о. функции кодера, осуществляющего согласование в статическом смысле сообщения ис­точника со входного канала, является полным устранением избыточности сообщения. Кодер осуществляет кодирование сообщения, т.е. каждому дискретному сообщению по определенным правилам ставит в соответствие последователь­ность символов из алфавита объемом N. При этом по отношению ко входу канала, выдаваемые кодером символы сами являются дискретными элементарными сообщениями, статистические свойства которых должны отличаться от стати­стических свойств сообщений исходного источника. Возможность построения кодера, полностью устраняемого избы­точность произвольного источника сообщений, и определяет возможность решения поставленной задачи без ошибочной передачи информации со скоростью, равной пропускной способности канала.

При полном ее решении оказывается справедливым равенство:

H’ (U) = V_c × H (U) = V_k × log M = C (2.1)

откуда имеем η = V_k / V_c = H(U) / log M (2.1а), где H(U) - энтропия источника передаваемых сообщений, V_k и V_c - средние количества символов соответственно сообщения и кода передаваемых в единицу времени. η = V_k / V_c - среднее количество символов кода приходящиеся на одно сообщение.

Степень приближения к точному выполнению равенств (2.1) и (2.1а) зависит от степени уменьшения избыточ­ности источника сообщений.

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

1) памятью источника;

2) неравномерностью сообщений.

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

Вопрос 15: Теорема Шеннона для канала без шума. Первый способ доказательства.

П

редельные возможности статистического кодирования раскрывается в теореме Шеннона для канала без шума, которая является одним из основных положений теории передачи информации. Эта теорема может быть сформулирована сле­дующим образом (обозначения те же, что и в пункте 2.1). Пусть источник сообщений имеет производительность H’ (U) = V_c H(U), а канал имеет пропускную способность C =V_klog M. Тогда можно закодировать сообщения на выходе источ­ника таким образом, чтобы получить среднее число кодовых символов приходящихся на элемент сообщения

η = V_k / V_c = (H(U) / log M) + ε (2.2),

где ε - сколь угодно мало (прямая теорема).

Получить меньшее значение η невозможно (обратная теорема). Обратная часть теоремы утверждающая, что невозможно получить значение

η = V_k / V_c < H(U) / log M (2.3),

может быть доказана если учесть, что неравенство (2.3) эквивалентно неравенству u V_c H (U) > V_k log M и H’ (U) > C. Последнее неравенство не может быть выполнено, т.к. рассматриваемое кодирование должно быть обратимым преобразованием (т.е. без потерь информации). Энтропия в секунду на входе канала или производительность кодера не может превышать пропускную способность канала (см. пункт 1.6).

Докажем прямую теорему двумя различными способами, при этом источник сообщений будем полагать источником без памяти, имея в виду, что к нему со сколь угодно высокой степенью точности может быть сведен любой источник, если блоки элементов сообщения достаточно большой длинны К1 рассматривать, как элементарные сообще­ния Ui с объемом алфавита N_блока. Первый способ доказательства состоит в рассмотрении множества сообщений из К символов создаваемых источником. Каждую из таких последовательностей содержащую К элементарных сообщений u_i выбираемых из алфавита объемом 0 … Nu – 1 будем считать сообщением α =(u_k-1, …, u₀). Вероятность этих сообщений для источников без памяти P(α) = P(u_k-1) P(u_k-2) … P(u₀). При этом количество L отличных друг от друга сообщений a будет равно L = N_u^k. При достаточно большой длине сообщения К все множество L возможных сообщений может быть разбито на 2 подмножества. Одно из них (назовем его высоко вероятным или типичным) содержит К1 наиболее вероят­ных сообщений, сумма вероятностей которых 1-δ близка к единице, второе содержит остальные К2=L-K1 сообщений (мало вероятных или нетипичных), суммарная вероятность которых δ близка к нулю. Увеличивая К можно сделать δ сколь угодно малым. Сказанное следует из закона теории вероятностей, согласно которому при достаточно большом числе испытаний количество каждого из возможных исходов близко к своему математическому ожиданию (закон боль­ших чисел). В данном случае числом испытаний является число К элементов сообщений, исходом являются значения элементов u_i и математическое ожидание количества исходов u_i = K P(u_i). Поэтому достаточно длинное сообщение со­держит близкое к K P(0) число элементов 0, K P(1) число элементов 1, …, к K P(N_u-1) число элементов N_u-1. Такие со­общения и составляют высоко вероятное подмножество. Вероятность того, что сообщения содержат другие числа эле­ментов при К → ∞ ничтожно мала. Поскольку при отсутствии памяти у источника вероятность того или иного сочета­ния различных элементов сообщения зависит только от их количества, то все сообщения принадлежащие к высоко веро­ятному подмножеству т.е. содержащие примерно одно и тоже количество разных элементов и отличающихся только расположением этих элементов в последовательности, имеют одну и туже вероятность близкую к P(0)^{K P(0)} * P(1)^{KЧ P(1)} * P(Nu-1)^KP(Nu-1) = P. Прологарифмируем полученное равенство:

В силу равновероятности число сообщений в высоковероятном подмножестве К1>1/P, учитывая полученное выражение для логарифма P, К1 можно выразить через энтропию источника.

P=2-^{K H(U)}, K1=1/P=2^{K H(U)} (2.4)

Поскольку L=N_u^K=2^{K log(Nu)}

(2.5),

где m - избыточность источника. Анализ выражения (2.5) показывает, что при любой не нулевой избыточности ис­точника m число сообщений высоковероятного подмножества составляет сколь угодно малую часть от всех возмож­ных сообщений если длина сообщения К достаточно велика (сколь угодно малую вероятность имеет большая часть дос­таточно длинных сообщений). Это большинство и позволяет добиться близкого к минимуму числа h кодовых символов на элемент сообщения, применен следующий способ кодирования. Высоко вероятной группе сообщений поставим в однозначное соответствие различные короткие (их мало) кодовые комбинации равномерного кода длинны n1, оставив одну для использования в качестве разделительного сигнала. Для остальных К₂=L-K₁ >L сообщений, составляющих мало вероятное подмножество. Используем более длинные кодовые комбинации, содержащие n₂ символов, начинаю­щихся с упомянутой выше разделительной комбинации длинны n1 (для того, чтобы при декодировании можно разгра­ничить принимаемые сообщения). Длины кодов n1 и n2 определим из условия

(2.6),

где S - число различных кодовых комбинаций равномерного кода, m - объем алфавита кодовых символов, n - число символов (длинна кодовой комбинации).

Полагая в (2.6) S=K₁+1+l, n=n₁, где l - число дополняющее К1+1 до можно записать , где . Увеличи­вая, число К можно сколь угодно уменьшить число q по сравнению с тем числом, с которым оно суммируется (при КR? и К1R?). Рассуждая, аналогично получим выражение для n2 с учетом разделительной комбинации.
,
, (про y и g можно сказать тоже самое, что про l и q).

Поскольку средняя длинна кодовой комбинации при этом равна , то среднее число ко­довых символов приходящихся на один элемент сообщения равно , где . Где x становится сколь угодно малым при больших К. Это и доказывает прямую тео­рему.

В приведенном доказательстве мы полагали, что множество маловероятных последовательностей кодируется длинными кодовыми комбинациями (длину n₂+n₁), делает возможным их однозначное декодирование. Однако в прин­ципе всем сообщениям этой группы можно поставить в соответствие одну и туже разделительную комбинацию длиной n1, и, определив по ней принадлежность принятого сообщения к мало вероятной группе отбрасывать их как ошибоч­ные. Поскольку с ростом К вероятность нетипичных сообщений становится сколь угодно малой, сколь угодно малой будет вероятность ошибки. Данное замечание не меняет существа приведенного доказательства, но позволяет назвать рассмотренный в нем вариант кодирования равномерным кодированием.

Вопрос 16: Множество высоковероятных типичных и маловероятных нетипич­ных сообщений дискретного источника.

Первый способ доказательства состоит в рассмотрении множества сообщений из К символов создаваемых источником. Каждую из таких последовательностей содержащую К элементарных сообщений u_i выбираемых из алфавита объемом 0 … Nu – 1 будем считать сообщением α =(u_k-1, …, u₀). Вероятность этих сообщений для источников без памяти P(α) = P(u_k-1) P(u_k-2) … P(u₀). При этом количество L отличных друг от друга сообщений a будет равно L = N_u^k. При достаточно большой длине сообщения К все множество L возможных сообщений может быть разбито на 2 подмножества. Одно из них (назовем его высоко вероятным или типичным) содержит К1 наиболее вероят­ных сообщений, сумма вероятностей которых 1-δ близка к единице, второе содержит остальные К2=L-K1 сообщений (мало вероятных или нетипичных), суммарная вероятность которых δ близка к нулю. Увеличивая К можно сделать δ сколь угодно малым. Сказанное следует из закона теории вероятностей, согласно которому при достаточно большом числе испытаний количество каждого из возможных исходов близко к своему математическому ожиданию (закон боль­ших чисел). В данном случае числом испытаний является число К элементов сообщений, исходом являются значения элементов u_i и математическое ожидание количества исходов u_i = K P(u_i). Поэтому достаточно длинное сообщение со­держит близкое к K P(0) число элементов 0, K P(1) число элементов 1, …, к K P(N_u-1) число элементов N_u-1. Такие со­общения и составляют высоко вероятное подмножество. Вероятность того, что сообщения содержат другие числа эле­ментов при К → ∞ ничтожно мала. Поскольку при отсутствии памяти у источника вероятность того или иного сочета­ния различных элементов сообщения зависит только от их количества, то все сообщения принадлежащие к высоко веро­ятному подмножеству т.е. содержащие примерно одно и тоже количество разных элементов и отличающихся только расположением этих элементов в последовательности, имеют одну и туже вероятность близкую к P(0)^{K P(0)} * P(1)^{KЧ P(1)} * P(Nu-1)^KP(Nu-1) = P. Прологарифмируем полученное равенство:

В силу равновероятности число сообщений в высоковероятном подмножестве К1>1/P, учитывая полученное выражение для логарифма P, К1 можно выразить через энтропию источника.

P=2-^{K H(U)}, K1=1/P=2^{K H(U)} (2.4)

Поскольку L=N_u^K=2^{K log(Nu)}

(2.5),

где m - избыточность источника. Анализ выражения (2.5) показывает, что при любой не нулевой избыточности ис­точника m число сообщений высоковероятного подмножества составляет сколь угодно малую часть от всех возмож­ных сообщений если длина сообщения К достаточно велика (сколь угодно малую вероятность имеет большая часть дос­таточно длинных сообщений). Это большинство и позволяет добиться близкого к минимуму числа h кодовых символов на элемент сообщения, применен следующий способ кодирования. Высоко вероятной группе сообщений поставим в однозначное соответствие различные короткие (их мало) кодовые комбинации равномерного кода длинны n1, оставив одну для использования в качестве разделительного сигнала. Для остальных К₂=L-K₁ >L сообщений, составляющих мало вероятное подмножество. Используем более длинные кодовые комбинации, содержащие n₂ символов, начинаю­щихся с упомянутой выше разделительной комбинации длинны n1 (для того, чтобы при декодировании можно разгра­ничить принимаемые сообщения). Длины кодов n1 и n2 определим из условия

(2.6),

где S - число различных кодовых комбинаций равномерного кода, m - объем алфавита кодовых символов, n - число символов (длинна кодовой комбинации).

Полагая в (2.6) S=K₁+1+l, n=n₁, где l - число дополняющее К1+1 до можно записать , где . Увеличи­вая, число К можно сколь угодно уменьшить число q по сравнению с тем числом, с которым оно суммируется (при КR? и К1R?). Рассуждая, аналогично получим выражение для n2 с учетом разделительной комбинации.
,
, (про y и g можно сказать тоже самое, что про l и q).

Поскольку средняя длинна кодовой комбинации при этом равна , то среднее число ко­довых символов приходящихся на один элемент сообщения равно , где . Где x становится сколь угодно малым при больших К. Это и доказывает прямую тео­рему.

В приведенном доказательстве мы полагали, что множество маловероятных последовательностей кодируется длинными кодовыми комбинациями (длину n₂+n₁), делает возможным их однозначное декодирование. Однако в прин­ципе всем сообщениям этой группы можно поставить в соответствие одну и туже разделительную комбинацию длиной n1, и, определив по ней принадлежность принятого сообщения к мало вероятной группе отбрасывать их как ошибоч­ные. Поскольку с ростом К вероятность нетипичных сообщений становится сколь угодно малой, сколь угодно малой будет вероятность ошибки. Данное замечание не меняет существа приведенного доказательства, но позволяет назвать рассмотренный в нем вариант кодирования равномерным кодированием.

Вопрос 17: Второй способ доказательства прямой теоремы Шеннона для канала без шума.

В

торой способ доказательства прямой теоремы предполагает другой способ эффективного кодирования, который заклю­чается в следующем: по-прежнему рассматриваем сообщение a_i представляющее собой последовательность элементар­ных сообщений u_j длинной К. Расположим все сообщения a _i в порядке убывания их вероятностей, пусть эти вероятно­сти будут P1³ P2 ³ ¼ ³ PL, где L = N u_k число сообщений a_i. Пусть

,

т.е. Q_s накопленная вероятность до P (S-1) включительно. Закодируем сначала все сообщения в двоичную сис­тему. Двоичный код для сообщения a_s получиться путем записи дробной части разложения Q_s, как двоичного числа (при S=1, Q_s =0). Разложение производиться до m_s позиции, где m_s целое число, удовлетворяющее соотношению

(2.7).

Пример: Пусть мы имеем 4 сообщения

a1	a2	a3	a4
P(a1) = 1/2	P(a2) = 1/4	P(a3) = 1/8	P(a4) = 1/8
Q1 = 0	Q2 = 1/2	Q3 = 3/4	Q4 = 7/8
m1 = 1	m2 = 2	m3 = 3	m4 = 4
код 0	код 10	код 110	код 111

Коды показанные в последней строчке таблицы - это коды Шеннона дробной части.
Таким образом высоко вероятные сообщения представляются короткими кодами, а маловероятные длинными (это видно из (2.7)). Из этих неравенств вытекает следующая система неравенств (2.8). Оно показывает, что при выборе m_s в соответствии с системой неравенств (2.7) вероятность сообщения с номером s P_s не меньше веса послед­него младшего разряда двоичного разложения Q_s. Вследствие этого код для Q_s будет отличаться от всех после­дующих кодов одной и более из своих m_s позиций, т.к. все остающиеся Q_i, по крайней мере, на величину больше и поэтому их двоичное разложение отличается от кода для Q_s, ходя бы в младшем разряде. Это говорит об однозначности предложенного способа кодирования. Среднее количество символов кода приходящихся на одно сообщение a можно определить, как (2.9), а среднее количество символов кода, приходящихся на одно элементарное сообще­ние U_k . Умножая все части системы неравенств (2.7) на и усредняя их по ан­самблю сообщений a_i приходим к неравенствам

(2.10),

Но

,

где Н_a - энтропия источника укрупненных сообщений a представляющих собой объединение К элементных неза­висимых сообщений Ui (рассматриваем источник без памяти). Поэтому вследствие свойства аддитивности энтропии H_α = K× H(U). В свою очередь

.

Таким образом неравенство (2.10) можно записать в виде

(2.11).

Неравенство (2.11) показывает, что с неограниченным ростом значение К, среднее количество h символов кода приходиться на одно элементарное сообщение источника, сколь угодно близко приближается к значению энтропии этого источника. Поскольку мы рассматривали двоичный код с объемом алфавита равного 2 и log₂M=log₂2=1 выполне­ние неравенства (2.11) эквивалентно выполнению условия (2.2), это и доказывает прямую теорему. Полученный резуль­тат позволяет дать следующее толкование энтропии: энтропия источника есть наименьшее количество двоичных симво­лов на сообщение, на выходе наилучшего кодера для этого источника при условии, что сообщения могут быть восстанов­лены по выходу кодера сколь угодно точно. Два рассмотренных варианта доказательства прямой теоремы иллюстрируют два возможных подхода к построению эффективных кодов, основанных на использовании равномерного и неравномерного кодирования. При неравномерном кодировании обеспечивается однозначное декодирование всех сообщений.
Второй способ доказательства мы рассмотрели в той же трактовке, в которой он был дан Шенноном, а именно на основе построения двоичного эффективного кода возможен более общий подход, базируется на построении неравномерного статистического кода с произвольным основанием М непосредственно приводящей к результату (2.2). Такой вариант доказательства дан в книге Колесник-Бондарев.

Вопрос 18: Эффективное кодирование. Метод Фано. Оптимальные коды.

П

редложенный Шенноном метод эффективного кодирования практически совпадает с методом предложенным другим американским ученым Фано по которому сообщение длинны К, записанное в порядке не возрастания вероятностей раз­деляется на две части так, чтобы суммарные вероятности сообщений в каждой части были по возможности равны. Со­общениям первой части приписывается в качестве первого символа 0, сообщениям второй части 1. Затем каждая из этих частей (если она содержит более одного сообщения) опять делится на две примерно равные части и в качестве второго символа для первой из них берется 0, а для второй 1. Этот процесс повторяется до тех пор, пока в каждой из полученных частей не останется по одному сообщению. Существуют и другие методы эффективного кодирования. Кодирование по методу Шеннона – Фано так же как и другими методами может применятся не только к последовательностям из К эле­ментных сообщений, но и непосредственно к источникам не равновероятных элементарных сообщений. При этом уменьшается выигрыш в эффективности. В том случае, когда левая часть системы неравенств (2.11) обращается в равен­ство, имеем h_min = H(U) (2.12). Код, обладающий h_min называется оптимальным для того, чтобы сообщение источника можно было закодировать двоичным оптимальным кодом необходимо и достаточно, чтобы все вероятности источника сообщения представляли собой числа равные целой отрицательной степени числа 2, т.е. Pi= , где аi - целое. Действи­тельно как видно из неравенства (2.8) в таком случае вероятности Ps при выбранном нами способе определении длины кодового слова ms определятся, как . При этом среднее число символов кода приходящихся на одно сообще­ние в соответствии с (2.9) равно . В свою очередь энтропия источника сообщений Нa равна . Таким образом получили, что h_с = h с min = Н_α откуда после деления обеих частей последнего равенства на К можно придти к выражению (2.12). Рассуждая аналогич­ным образом можно показать, что и в случае кодирования сообщений источника неравномерным кодом с произвольным основанием М оптимальный код может быть получен при условии равенства вероятности всех сообщений целым отри­цательным степеням числа М, т.е. при , где аi - целое и при этом . Если распределение вероятностей кодированного источника не обладает указанным свойством, эффективный код не будет оптимальным и соответствующая ему h > h _min. Величина Y = h_min/ h (2.12а), характеризующая степень близости неравномерного стати­стического кода к оптимальному называется эффективностью кода. Таким образом нижний предел в условии теоремы, может быть, достигнут лишь при определенном распределении вероятности источника сообщений. Однако приближе­ние к нему может быть сколь угодно близким при увеличении длинны К последовательности кодируемых сообщений. При этом рост эффективности системы передачи информации сопровождается увеличением задержки сообщений. И так из рассмотренной теоремы вытекает, что для любого источника дискретных сообщений (т.е. характеризуется любым многомерным распределением вероятностей) скорость передачи информации по идеальному каналу может быть сделана сколь угодно близкой к пропускной способности канала при отсутствии потерь информации. При этом приближение тем больше, чем больше длина сообщения К, что указывает на возможность обмена задержки на скорость передачи информа­ции.