Основная теорема Шеннона для дискретного канала с помехами

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

Формулировка теоремы:

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

Формула 1

Доказательство: число типичных последовательностей достаточно большой длительности , которое может создавать источник производительностью равно:

Формула 2

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

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

Поскольку постольку Формула 1 только усилится, если его записать в виде:

Тогда можно написать следующее:

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

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

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

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

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

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

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

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

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

Ибо осреднению по всем возможным способам кодирования соответствует равновероятный выбор кодовой комбинации любой входной последовательности.

Соответственно, средняя вероятность того, что конкретная комбинация не была использована при кодировке выглядит так:

Формула 3

Средняя же вероятность того, что не исполнены:

Т.к. основание этой степени меньше 1, то увеличим показатель степени на 1 и воспользуемся разложением правой части в ряд Тейлора, тогда:

Формула 4

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

Формула 5

Используя Формулу 1,2,3,5 получаем:

Формула 6

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

Пусть вероятность появления нетипичной последовательности будет , тогда вероятность появления типичной последовательности равна .

Тогда при , в соответствии с Формулой 6, вероятность ошибки ,следовательно .

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

Как и в предыдущей теореме, кодирование связано с задержкой передачи сообщения, которая равна:

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

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

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

Оценим количество информации приходящейся в среднем на 1 символ канала при выполнении условия Формулы 1.

Избыточность входного сообщения:

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

Удлинение кодовых последовательностей при использовании кодов Шеннона вызывает не снижение , а лишь задержку в приеме информации.

Смысл теоремы Шеннона сводится к следующему:

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

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

Шеннон показал, что эти определения с точки зрения теории тождественны: пропускная способность канала является верхней границей скорости передачи по каналу

Поиск по сайту: