Помехоустойчивое кодирование. Теорема Шеннона
Теория помехоустойчивого кодирования базируется на результатах исследований, проведенных Шенноном и сформулированных им в виде теоремы:
- при любой производительности источника сообщений, меньшей, чем пропускная способность канала, существует такой способ кодирования, который позволяет обеспечить передачу всей информации, создаваемой источником сообщений, со сколь угодно малой вероятностью ошибки;
- не существует способа кодирования, позволяющего вести передачу информации со сколь угодно малой вероятностью ошибки, если производительность источника сообщений больше пропускной способности канала.
Хотя доказательство этой теоремы, предложенной Шенноном, в дальнейшем подвергалось более глубокому и строгому математическому представлению, идея его осталась неизменной. Доказывается только существование искомого способа кодирования, для чего находят среднюю вероятность ошибки по всем возможным способам кодирования и показывают, что она может быть сделана сколь угодно малой. При этом существует хотя бы один способ кодирования, для которого вероятность ошибки меньше средней.
Источник создает информацию со скоростью 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/ В настоящее время используются относительно простые методы кодирования, которые не реализуют возможностей, указанных теорией. Однако постоянно растущие требования в отношении достоверности передачи и успехи в технологии создания больших интегральных схем способствуют внедрению для указанных целей все более сложного оборудования.
|