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

Информационная способность кода и избыточность.

Получатель сообщения в каком-либо коде не знает, какой из символов к нему поступит, поэтому сообщения (сигналы) в любом коде можно рассматривать как системы со многими случайными состояниями. Число возможных состояний равно числу всех различимых сигналов (символов) кода. Это дает возможность говорить об энтропии кода. Если считать, что все N символов (сигналов) кода при передаче сообщений могут появляться с равной вероятностью, то вероятность каждого их них будет .

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

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

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

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

Теорема неконструктивна: в ней не затрагивается вопрос о путях построения кодов.

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

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

Рассматриваемый код обладает значительной избыточностью

,

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

Общее число элементов n корректирующего кода определяется как сумма рабочих (информационных) элементов n₀ и контрольных элементов k:

n = n₀+k.

Полное число комбинаций 2ⁿ. Основной сигнал и его искажения в одном элементе занимает n+1 комбинаций. Отсюда количество возможных колебаний кода обнаруживающего и исправляющего единичную ошибку определяется неравенством

Из неравенства при заданном N определяются n₀, n и затем k.

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

d=r+s+1,

где r – число обнаруживаемых ошибок; s – число исправляемых ошибок.

Пример кода с автоматическим исправлением ошибок рассмотрим на практическом занятии.

В заключении приведем основную теорему Шеннона о кодировании для канала с помехами.

В качестве примера рассмотрим определение избыточности приведенного ранее n-элементарного (n=4) кода на одно сочетание (k=2), обеспечивающего 6 комбинаций.

, округляем до n₀=3.

Тогда

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