1.4.Теоремы кодирования Шеннона

Теоретической основой построения эффективных кодов является теорема кодирования 1 Шеннона (без вывода):

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

Из этой теоремы следует, что среднее число бит на символ источника, требуемое для кодирования выхода дискретного источника без памяти с произвольно малой вероятностью ошибки декодирования, ограничено снизу энтропией источника Н(Х). Чем больше энтропия источника, тем больше (в среднем) потребуется символов для кодирования сообщений источника.

Базой для помехоустойчивого кодирования является теорема кодирования 2 Шеннона (без вывода):

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

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

Производительность источника определяется как отношение энтропии источника к интервалу времени формирования сообщений:

.

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

.

Предельные возможности скорости передачи информации оцениваются пропускной способностью (емкостью) канала связи.

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

.

В противном случае осуществить такое кодирование невозможно.

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

Задачи

1. Алфавит источника состоит из восьми символов. Определить избыточность сообщений, если вероятности появления символов в сообщениях имеют значения: р₁ = 0,03; р₂ = 0,26; р₃ = 0,09; р₄ = 0,05; р₅ = 0,16; р₆ = 0,1; р₇ = 0,09; р₈ = 0,22.

2. Определить скорость создания информации системой, которая описывается дискретной случайной величиной х со следующим рядом распределения: р (х₁) = 0,03; р (х₂) = 0,05; р (х₃) = 0,02; р (х₄) = 0,1; р (х₅) = = 0,5; р (х₆) = 0,1; р (х₇) = 0,2, если система генерирует элемент сообщения за 0,02 с.

3. Определить скорость создания информации системой, которая описывается дискретной случайной величиной х со следующим рядом распределения: р (х₁) = 0,1; р (х₂) = 0,2; р (х₃) = 0,35; р (х₄) = 0,05; р (х₅) = = 0,25; р (х₆) = 0,05, если длительности элементов сообщений данного источника, соответственно, составляют: t₁ = 0,02 c; t₂ = 0,03 c; t₃ = 0,01 c; t₄ = 0,04 c; t₅ = 0,01 c; t₆ = 0,02 c.

4. Записать число 129 в двоичной системе счисления.

5. Определить вес кодовых комбинаций 1001001010100111,

11000111010101110 и кодовое расстояние между ними.