Теорема Шеннона для канала без помех

Способы сокращения избыточности.

Выделим в сообшениях этого источника двуместные блоки вида AA, AB, BA, BB. Поскольку символы А и В независимы, то соотвествующие веоятности их появления p(AA)=0.81, p(AB)=0.09, p(BA)=0.09, p(BB)=0.01.

В этом случае N=4,

H=∑p_i*log(p_i)=1.14бит/сим,

H_max=2бит/с.

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

D=1-(1.14/2)=0.43.

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

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

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

Выводы: 1. Избыточность сообщений, составленных из равновероятных символов, меньше избыточности сообщений, составленных из не равновероятных символов.

2. Информационная статистическая избыточность первичного источника сообщений явление естественное и заложена такая избыточность в статистических характеристиках первичного алфавита.

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

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

Что такое производительность источника. Пусть источник генерирует 1 символ за время τ=1 мксек. Тогда, если энтропия источника например 2бит/символ, то его производительность

Сист.=Н/τ=2Мбит/сек.

Система передачи информации, в которой аппаратура не вносит никаких искажений, а канал связи — затуханий и помех, называется информационной системой без шумов. В такой системе, как бы ни были закодированы сигналы, потерь информации не будет. Но это еще не значит, что в такой системе автоматически решаются все технические проблемы передачи информации. Для однозначного декодирования принятых сообщений, а также для передачи больших объемов информации при меньших временных и материальных затратах коды должны, в частности, удовлетворять следующим требованиям:

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

2. Кoд должен быть построен так, чтобы можно было четко отделить начало и конец кодовых слов.

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

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

Второе требование может быть удовлетворено следующим образом:

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

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

- либо созданием кода, в котором все буквы передаются комбинациями равной длины, т. е. равномерного кода.

При этом следует отметить, что равномерные коды обладают известными преимуществами; длину каждой буквы можно определить простым подсчетом элементарных символов, что позволяет автоматизировать процесс декодирования и строить простые декодирующие устройства. Однако равномерные коды имеют один существенный недостаток: все кодовые слова алфавитов, представленных ими, имеют равную длину независимо от вероятности появления отдельных символов кодируемого алфавита. Такой код может быть оптимальным только для случая равновероятных и взаимонезависимых символов сообщений, что довольно часто встречается в телемеханике и никогда — при передаче текстовых сообщений.

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

Согласно N=mⁿ чтобы, передать N неповторяющихся сообщений при помощи m символов вторичного алфавита, их надо комбинировать по n штук в кодовом слове. В случае равновероятного первичного источника из N символов его энтропия

H=logN.

Очевидно, что при этом длина кодового слова кодера источника

n=logN/log(m).

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

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

L=H/log(m)

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

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

В этом смысле предельно короткими являются так называемые оптимальные коды - коды с нулевой (или близкой к нулю) избыточностью. Классическим примером кода с нулевой избыточностью может быть код Шеннона – Фано., построение которых мы рассмотрим на следующих лекциях.

Таким образом величина

L=H/log(m)

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

N=2^k,

k — целое число и k представляет собой минимальную длину кодового слова L для кодирования символов первичного источника в двоичном алфавите.

Для двоичных алфавитов (m = 2)

Для m- значного равновероятного алфавита длина кодового слова

(А)

Подводя итоги, можно сказать, что в общем случае средняя минимальная длина кодового слова L для первичного источника из N символов, составленного из алфавита с m знаками

С другой стороны можно показать что

или

(В)

Доказательство (см. например учебник Цымбала гл.14стр.113, 114) основано на очевидно понятном соотнощении

[Х]-X<1,

где [X] -целая часть Х, то есть на том, что разность между округлением числа Х до целого в большую сторону и самим числом Х меньше 1.

Выражения (А) и (В) представляют собой соответственно верхнюю и нижнюю границы минимально необходимой средней длины кодового слова. Используя эти выражения, получаем

(C).

Рассмотрим теперь условия, при которых будет уменьшаться разность между верхней и нижней границами, то есть условия, при которых средняя минимальная длина кодового слова будет приближаться к значению H/log(m).

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

Предположим, что передаются равновероятные символы некоторого первичного алфавита при помощи равномерного двоичного кода m = 2. Для передачи восьми букв алфавита минимальная длина кодового слова

Для передачи пяти букв

L₂=log₂5=2.322

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

µ=2.322/3=0.774

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

D=1-µ=1-0.774=0.226

Цифра 0,226 характеризует степень недогруженности кода. Выражение

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

Рассмотрим теперь случай поблочного кодирования (смотри пример из первой части лекции, где каждый из блоков состоит из М независимых букв a₁,a₂,…,a_м).

Выражение для энтропии сообщения из всех букв блока, согласно правилу сложения энтропии,

По аналогии с формулой (C) запишем выражение для средней длины такого кодового блока

где L_М – среднее количество символов в блоке.

Для такого блочного кодирования, очевидно, имеет место соотношение

L_М=L*M,

тогда

L=Lм/M.

Нетрудно заметить, что теперь L можно получить, разделив все части неравенства (С) на М. Тогда общее выражение для среднего числа элементарных символов на кода на символ первичного источника сообщений

(D)

Из этого видно, что при М → ∞ среднее число элементарных символов кодового слова, затрачиваемых на передачу одной буквы, неограниченно приближается к величине

Выражение (D) является основным выражением фундаментальной теоремы кодирования Шеннона при отсутствии шумов. Сама теорема может быть сформулирована следующим образом:

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

,

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

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

Если кодируемый алфавит равновероятный и N= 2ⁱ (где i — целое число), то среднее число двоичных знаков на букву в точности равно энтропии источника сообщений.

Выводы:

1. Чем длиннее первичное кодовое слово, тем точнее величина

характеризует среднюю длину кодового слова.

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

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

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

Дата добавления: 2014-01-04