Помехоустойчивое кодирование. Теорема Шеннона

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

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

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

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

Н(х) = Vх · Н(х) [бит/сек].

В соответствии с теоремой о эффективном кодировании среднее количество символов на одну букву lсрН(х), т.е. в первом приближении можно получить, что

Н(х) = Vх · lср [бит/сек].

Условие пропуска информации по каналу Н(х) ≤ C = Vk.

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

Ck = Vk · [1 – H(Pош)].

Теорема о помехоустойчивом кодировании требует чтобы

Vx · lср = Н(х) ≤ Ck = Vk · [1 – H(Pош)].

где lср – средняя длина кодовой комбинации для записи одной буквы.

По сравнению с эффективным кодом lср увеличивается до:

Помехоустойчивое кодирование. Теорема Шеннона

Однако, такой величины lср1 помехоустойчивые коды не достигают. Это можно рассматривать как теоретический предел.

Обеспечение передачи информации с весьма малой вероятностью ошибки и достаточно высокой эффективностью возможно при кодировании чрезвычайно длинных последовательностей знаков. На практике степень достоверности и эффективности ограничивается двумя факторами: размерами и стоимостью аппаратуры кодирования и декодирования и временем задержки передаваемого сообщения. http://peredacha-informacii.ru/ В настоящее время используются относительно простые методы кодирования, которые не реализуют возможностей, указанных теорией. Однако постоянно растущие требования в отношении достоверности передачи и успехи в технологии создания больших интегральных схем способствуют внедрению для указанных целей все более сложного оборудования.