Теоремы Шеннона
Помехи в передачи информации — вполне обычное дело во всех сферах профессиональной деятельности и в быту. Один из примеров был приведен выше, другие примеры — разговор по телефону, в трубке которого «трещит», вождение автомобиля в тумане и т.д. Чаще всего человек вполне справляется с каждой из указанных выше задач, хотя и не всегда отдает себе отчет, как он это делает (т.е. неалгоритмически, а исходя из каких-то ассоциативных связей).
Избыточность могла бы быть использована и при передаче кодированных сообщений в технических системах. Например, каждый фрагмент текста («предложение») передается трижды, и верным считается та пара фрагментов, которая полностью совпала. Однако, большая избыточность приводит к большим временным затратам при передаче информации и требует большого объема памяти при ее хранении. Впервые теоретическое исследование эффективного кодирования предпринял К.Шеннон.
Первая теорема Шеннона
Первая теорема Шеннона декларирует возможность создания системы эффективного кодирования дискретных сообщений, у которой среднее число двоичных символов на один символ сообщения асимптотически стремится к энтропии источника сообщений (в отсутствии помех).
Задача эффективного кодирования описывается триадой:
Х = {X 4i} — кодирующее устройство — В.
Здесь X, В — соответственно входной и выходной алфавит. Под множеством хi можно понимать любые знаки (буквы, слова, предложения). В — множество, число элементов которого в случае кодирования знаков числами определяется основанием системы счисления (например, т = 2). Кодирующее устройство сопоставляет каждому сообщению хi из Х кодовую комбинацию, составленную из пi символов множества В. Ограничением данной задачи является отсутствие помех. Требуется оценить минимальную среднюю длину кодовой комбинации.
Задача эффективного кодирования описывается триадой:
Х = {X 4i} — кодирующее устройство — В.
Здесь X, В — соответственно входной и выходной алфавит. Под множеством хi можно понимать любые знаки (буквы, слова, предложения). В — множество, число элементов которого в случае кодирования знаков числами определяется основанием системы счисления (например, т = 2). Кодирующее устройство сопоставляет каждому сообщению хi из Х кодовую комбинацию, составленную из пi символов множества В. Ограничением данной задачи является отсутствие помех. Требуется оценить минимальную среднюю длину кодовой комбинации.
На фотографии изображен Клод Шеннон
Для решения данной задачи должна быть известна вероятность Рi появления сообщения хi, которому соответствует определенное количество символов пi алфавита В. Тогда математическое ожидание количества символов из В определится следующим образом:
n cр = пiРi (средняя величина).
Этому среднему числу символов алфавита В соответствует максимальная энтропия Нтаx = nср log т. Для обеспечения передачи информации, содержащейся в сообщениях Х кодовыми комбинациями из В, должно выполняться условие H4mах ? Н(х), или пcр log т ? — Рi log Рi. В этом случае закодированное сообщение имеет избыточность пcр ? H(x) / log т, nmin = H(x) / log т.
Коэффициент избыточности: Кu = (Hmax – H(x)) / Hmax = (ncp – nmin) / ncp
Nmin = H(x) / log2 = 2,85, Ku = (2,92 — 2,85) / 2,92 = 0,024,
Код практически не имеет избыточности. Видно, что среднее число двоичных символов стремится к энтропии источника сообщений.
n cр = пiРi (средняя величина).
Этому среднему числу символов алфавита В соответствует максимальная энтропия Нтаx = nср log т. Для обеспечения передачи информации, содержащейся в сообщениях Х кодовыми комбинациями из В, должно выполняться условие H4mах ? Н(х), или пcр log т ? — Рi log Рi. В этом случае закодированное сообщение имеет избыточность пcр ? H(x) / log т, nmin = H(x) / log т.
Коэффициент избыточности: Кu = (Hmax – H(x)) / Hmax = (ncp – nmin) / ncp
Nmin = H(x) / log2 = 2,85, Ku = (2,92 — 2,85) / 2,92 = 0,024,
Код практически не имеет избыточности. Видно, что среднее число двоичных символов стремится к энтропии источника сообщений.
Вторая теорема Шеннона
Вторая теорема Шеннона гласит, что при наличии помех в канале всегда можно найти такую систему кодирования, при которой сообщения будут переданы с заданной достоверностью. При наличии ограничения пропускная способность канала должна превышать производительность источника сообщений. Таким образом, вторая теорема Шеннона устанавливает принципы помехоустойчивого кодирования. Для дискретного канала с помехами теорема утверждает, что, если скорость создания сообщений меньше или равна пропускной способности канала, то существует код, обеспечивающий передачу со сколь угодно мглой частотой ошибок.
