поддержка
проекта:
разместите на своей странице нашу кнопку!И мы
разместим на нашей странице Вашу кнопку или ссылку. Заявку прислать на
e-mail
код нашей кнопки:
Теория кодирования
Раздел теории информации, связанный с задачами кодирования и
декодирования сообщений, поступающих к потребителям и посылаемых из
источников информации. Эти задачи теория кодирования решает с учетом
задачи наилучшего согласования посылаемой информации с каналами связи
(каналами передачи данных). Под этим понимается стремление максимально
использовать пропускную способность канала, а также обеспечить
передаваемым сообщениям нужную степень защищенности от помех.
На рис. 1 показана обобщенная схема передачи данных. Множество М\
описывает множество потенциально возможных сообщений, которые может
передать источник информации. Из этого множества выбирается некоторое
сообщение т\. Но прежде чем его направить в канал, оно кодируется и
преобразуется в некоторое сообщение т2 из множества М2, характеризующего
множество закодированныхсообщений. Поскольку
способов кодирования может быть много, то М2 отличается от М1
и установление соответствия между элементами этих множеств требует
специальной договоренности.
Например, хорошо известная азбука Морзе, применяемая для кодирования
букв алфавита для передачи сообщений по каналу связи, кодирует сообщения
совершенно не так, как их кодирует матрос, передающий такое же сообщение
с борта корабля на берег с помощью пары сигнальных флажков.
Закодированное сообщение поступает в канал связи и под воздействием
помех этого канала превращается в искаженное сообщение т3 из множества
М3 (вспомним многочисленные и подчас весьма забавные искаженные тексты
телеграмм, получаемых по линиям связи). На приемном конце
канала связи необходимо провести декодирование искаженного сообщения.
Сначала надо превратить в сообщение из множества М2. Потом, пользуясь
информацией о способах кодирования, получить то сообщение т\, которое
было послано. Но переход от тз к сообщению из М2 при сильных искажениях
неоднозначен. Если, например, передавалось слово "рука", а на приемном
конце канала было получено "щука", то в М2 этому может соответствовать
масса допустимых слов: мука, бука, рука и т. п. Поэтому искаженные
сообщения декодировать нелегко.
Одна из важных задач, решаемых в теории кодирования, - это разработка
специальных корректирующих кодов, которые позволяют находить и
исправлять ошибки, возникающие при передаче сообщений. Один из
простейших кодов такого типа мог бы быть таким. Вместо четырех букв,
входящих в слово "рука", источник сообщения мог бы передавать их в
удвоенном виде. Тогда сообщение, поступившее в канал связи, выглядело бы
как "ррууккаа". Если искажению подверглась одна буква передаваемого
слова, то на приемном конце канала появилось бы сообщение "рщууккаа".
Восстановление правильного сообщения значительно облегчается благодаря
принятому виду кодирования. Ясно, что ошибки в трех последних позициях
нет. Ошибка имеется только в первой позиции, так как буквы в ней
различаются. Для исправления обнаруженной ошибки достаточно проверить
две гипотезы: в mi есть либо "щука", либо "рука". Первая гипотеза
отклоняется, так как в М2 нет слова "щука".
Наш пример показывает, что поиск и исправление ошибок требуют
избыточности в передаваемом сообщении. И естественно, хотелось бы, чтобы
эта избыточность была минимальной. В противном случае передача сообщений
будет идти с низкой скоростью.
Проблема кодирования с минимальной избыточностью - одна из задач,
исследуемых и решаемых в теории кодирования. Созданы многие десятки
корректирующих и обнаруживающих ошибки кодов для каналов связи с
различными характеристиками шумов и искажений, вносимых при передаче
сообщений.
В теории кодирования фундаментальное значение имеют две теоремы,
доказанные известным американским ученым К. Шенноном, с которых,
собственно, и началось развитие теории кодирования. Первая теорема
Шеннона говорит о том, что при канале, не вносящем своих помех, можно
закодировать сообщения таким образом, чтобы среднее число элементов
кода, приходящихся на один элемент кодируемого алфавита, было бы
минимальным (этот минимум определяется некоторым параметром Н -
энтропией источника информации, характеризующего статистические свойства
источника). Такое кодирование называется эффективным статистическим
кодированием.
Вторая теорема Шеннона относится к каналам с искажениями. Согласно этой
теореме, для таких каналов всегда существует способ кодирования, при
котором сообщения будут передаваться с какой угодно высокой
достоверностью, если только скорость передачи не превышает пропускной
способности канала связи.
Специальным разделом в теории кодирования является теория арифметических
кодов, используемых для повышения надежности работы вычислительных
устройств. Арифметические коды позволяют обнаруживать и исправлять
ошибки, возникающие в арифметических устройствах ЭВМ. Правда, за такой
сервис приходится расплачиваться лишним временем и оборудованием.
Поэтому арифметические коды используются только в специальных ЭВМ,
предназначенных для решения ответственных задач, когда ошибки в работе
машины могут привести к весьма нежелательным последствиям (например,
арифметические коды используются во многих ЭВМ, которые устанавливают на
космических кораблях).