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

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

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

Если же , то такого способа нет.

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

При этом число символов (разрядность цифрового кода) равно .

Тогда число :

Число типичных последовательностей длительности может быть определено как:

Условие теоремы можно записать как равенство:

где - любая малая величина.

Откуда получаем, что :

Пусть , тогда:

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

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

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

Поскольку при и , вероятность нетипичной последовательности стремится к 0, а величина , определяющая превышение пропускной способности канала над производительностью источника, бесконечно мала, то первая часть теоремы доказана.

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

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

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

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

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

где - задержка на технические операции (кодирование, декодирование, проход по каналу и т.д.).

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

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