ПОНЯТИЕ О ТЕОРЕМАХ ШЕННОНА - Кодирование информации
Ранее отмечалось, что при передаче сообщений по каналам связи могут возникать помехи, способные привести к искажению принимаемых знаков. Так, например, если вы попытаетесь в ветреную погоду передать речевое сообщению человеку, находящемуся от вас на значительном расстоянии, то оно может быть сильно искажено такой помехой, как ветер. Вообще, передача сообщений при наличии помех является серьезной теоретической и практической задачей. Ее значимость возрастает в связи с повсеместным внедрением компьютерных телекоммуникаций, в которых помехи неизбежны. При работе с кодированной информацией, искажаемой помехами, можно выделить следующие основные проблемы: установления самого факта того, что произошло искажение информации; выяснения того, в каком конкретно месте передаваемого текста это произошло; исправления ошибки, хотя бы с некоторой степенью достоверности.
Помехи в передачи информации - вполне обычное дело во всех сферах профессиональной деятельности и в быту. Один из примеров был приведен выше, другие примеры - разговор по телефону, в трубке которого "трещит", вождение автомобиля в тумане и т. д. Чаще всего человек вполне справляется с каждой из указанных выше задач, хотя и не всегда отдает себе отчет, как он это делает (т. е. неалгоритмически, а исходя из каких-то ассоциативных связей). Известно, что естественный язык обладает большой избыточностью (в европейских языках - до 7%), чем объясняется большая помехоустойчивость сообщений, составленных из знаков алфавитов таких языков. Примером, иллюстрирующим устойчивость русского языка к помехам, может служить предложение "в словох всо глосноо зомононо боквой о". Здесь 26% символов "поражены", однако это не приводит к потере смысла. Таким образом, в данном случае избыточность является полезным свойством.
Избыточность могла бы быть использована и при передаче кодированных сообщений в технических системах. Например, каждый фрагмент текста ("предложение") передается трижды, и верным считается та пара фрагментов, которая полностью совпала. Однако, большая избыточность приводит к большим временным затратам при передаче информации и требует большого объема памяти при ее хранении. Впервые теоретическое исследование эффективного кодирования предпринял К. Шеннон.
Первая теорема Шеннона декларирует возможность создания системы эффективного кодирования дискретных сообщений, у которой среднее число двоичных символов на один символ сообщения асимптотически стремится к энтропии источника сообщений (в отсутствии помех).
Задача эффективного кодирования описывается триадой:
Х = {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
Выпишем эти значения в виде табл. 1.8. Имеем:
Nmin = H(x) / log2 = 2,85, Ku = (2,92 - 2,85) / 2,92 = 0,024,
Т. е. код практически не имеет избыточности. Видно, что среднее число двоичных символов стремится к энтропии источника сообщений.
Таблица 1
Пример к первой теореме Шеннона
N |
РхI |
XI |
Код |
NI |
ПI- - РI |
РхI - log РхI |
1 |
0,19 |
X1 |
10 |
2 |
0,38 |
-4,5522 |
2 |
0,16 |
X2 |
001 |
3 |
0,48 |
-4,2301 |
3 |
0.16 |
X3 |
011 |
3 |
0,48 |
-4,2301 |
4 |
0,15 |
X4 |
101 |
3 |
0,45 |
-4,1054 |
5 |
0,12 |
X5 |
111 |
3 |
0,36 |
-3,6706 |
6 |
0,11 |
X6 |
111 |
3 |
0,33 |
- 3,5028 |
7 |
0,09 |
X7 |
1011 |
4 |
0,36 |
-3,1265 |
8 |
0,02 |
X8 |
1001 |
4 |
0,08 |
-3,1288 |
У=1 |
У=2,92 |
У=2,85 |
Вторая теорема Шеннона гласит, что при наличии помех в канале всегда можно найти такую систему кодирования, при которой сообщения будут переданы с заданной достоверностью. При наличии ограничения пропускная способность канала должна превышать производительность источника сообщений. Таким образом, вторая теорема Шеннона устанавливает принципы помехоустойчивого кодирования. Для дискретного канала с помехами теорема утверждает, что, если скорость создания сообщений меньше или равна пропускной способности канала, то существует код, обеспечивающий передачу со сколь угодно мглой частотой ошибок.
Доказательство теоремы основывается на следующих рассуждениях. Первоначально последовательность Х = {xi} кодируется символами из В так, что достигается максимальная пропускная способность (канал не имеет помех). Затем в последовательность из В длины п вводится r символов и по каналу передается новая последовательность из п + r символов. Число возможных последовательностей длины и + т больше числа возможных последовательностей длины п. Множество всех последовательностей длины п + r может быть разбито на п подмножеств, каждому из которых сопоставлена одна из последовательностей длины п. При наличии помехи на последовательность из п + r выводит ее из соответствующего подмножества с вероятностью сколь угодно малой.
Это позволяет определять на приемной стороне канала, какому подмножеству принадлежит искаженная помехами принятая последовательность длины п + r, и тем самым восстановить исходную последовательность длины п.
Эта теорема не дает конкретного метода построения кода, но указывает на пределы достижимого в создании помехоустойчивых кодов, стимулирует поиск новых путей решения этой проблемы.
Похожие статьи
-
КОДИРОВАНИЕ ИНФОРМАЦИИ., АБСТРАКТНЫЙ АЛФАВИТ - Кодирование информации
АБСТРАКТНЫЙ АЛФАВИТ Информация передается в виде сообщений. Дискретная информация записывается с помощью некоторого конечного набора знаков, которые...
-
ОБНАРУЖЕНИЕ И ИСПРАВЛЕНИЕ ОШИБОК В СООБЩЕНИЯХ - Теория и практика информации и кодирования
Задача 4 1. Чему равно кодовое расстояние между комбинацией 10010111 и комбинациями 11111111, 00000000, 00010111? Решение Для того чтобы определить...
-
МЕЖДУНАРОДНЫЕ СИСТЕМЫ БАЙТОВОГО КОДИРОВАНИЯ - Кодирование информации
Информатика и ее приложения интернациональны. Это связано как с объективными потребностями человечества в единых правилах и законах хранения, передачи и...
-
Задача 3 Можно ли назвать полным информационное описание канала связи, предоставленного матрицей вида? Решение Для полного и всестороннего описания...
-
Задача 1 Какие из приведенных ниже кодовые комбинации содержат ошибку, если известно, что они передавались стандартным телеграфным кодом №3: 0101010;...
-
Задача 6 Определить объем и количество информации в принятом тексте: "Товарищ, верь: взойдет она, Звезда пленительного счастья, Россия вспрянет ото...
-
Эффективное кодирование - Основы построения телекоммуникационных систем и сетей
Эффективное кодирование - это процедуры направленные на устранение избыточности. Основная задача эффективного кодирования: обеспечить, в среднем,...
-
Способы осуществления атак. - Пути реализации угроз компьютерной информации
Реализация угроз компьютерной информации может осуществляться как: А - непосредственное несанкционированное воздействие на информационные ресурсы в...
-
КОДИРОВАНИЕ ИНФОРМАЦИИ В ЭВМ, СИСТЕМЫ СЧИСЛЕНИЯ - Цифровые устройства и микропроцессоры
СИСТЕМЫ СЧИСЛЕНИЯ В позиционных СС "вес" каждого разряда зависит от его позиции в числе. К числу непозиционных относится "римская" СС, например число -...
-
Клавиатура - основное устройство для ввода информации. - Понятие экспертных систем (ЭС)
Существуют также устройства, облегчающие работу оператора, такие, как мышь, световое перо и пр. Также для ввода информации широко используются сканеры....
-
Эффективное кодирование - Техника передачи дискретных сообщений
Эффективное кодирование - это процедуры направленные на устранение избыточности. Основная задача эффективного кодирования: обеспечить, в среднем,...
-
Весовые коэффициенты 32768 16384 8192 4096 2048 1024 512 256 128 64 32 16 8 4 2 1 1 0 0 0 1 1 1 1 0 1 Микропроцессоры обрабатывают упорядоченные двоичные...
-
Системы исчисления - Кодирование информации в микропроцессорных системах
Любое неотрицательное число в позиционной системе счисления может быть представлено в виде: Где А - основание системы счисления, Х I - разряды (числа от...
-
СЖАТИЕ ИНФОРМАЦИИ - Теория и практика информации и кодирования
Задача 6 Восстановить исходный массив чисел по следующему ниже сжатому массиву: 2 4 6 8 1 3 5 7 7 2 1 Решение Сжатый массив: 2 4 6 8 1 3 5 7 7 2 1...
-
Кодирование и передача информации - Характеристика изделия 9C467-2
Сопряжение КСА с РЛС и ПРВ осуществляется с помощью устройства коммутации сигналов "СССП" УКМ (коробка КР14), устройства коммутации и усиления...
-
Основы линейного кодирования. Полученный в результате квантования и двоичного кодирования цифровой поток оптимален с точки зрения ошибок квантования, но...
-
ПОМЕХОУСТОЙЧИВОЕ КОДИРОВАНИЕ - Расчет параметров системы передачи дискретных сообщений
В связи с тем, что при приеме сообщений необходимо обеспечить вероятность ошибки не более 10-6 , используются помехоустойчивые коды, исправляющая и...
-
Принцип спектрального уплотнения (WDM) Потенциальные ресурсы волокна. До настоящего времени на многих коммерческих линиях использовалась скорость...
-
Универсальный тезис о пользе стандартизации, справедливый для всех отраслей, в компьютерных сетях приобретает особое значение. Суть сети - это соединение...
-
Метод временного мультиплексирования (TDM) Суть TDM: процесс передачи разбивается на ряд временных циклов, каждый из которых в свою очередь разбивается...
-
Понятие экспертных систем. - Понятие экспертных систем (ЭС)
Экспертные системы (ЭС) возникли как значительный практический результат в применении и развитии методов искусственного интеллекта (ИИ)- совокупности...
-
Дискретизатор преобразует сообщение в последовательность отсчетов, взятых с интервалом по времени At. Затем каждый отсчет квантуется по уровню...
-
Определение энергетического потенциала системы. Энергетический потенциал - определяется как допустимые оптические потери оптического тракта или ЭКУ между...
-
В каждый исторический период жизни общества и, шире - историческую эпоху - человечество вырабатывает и отрабатывает систему передачи информации,...
-
Разработка протокола обмена информацией и форматов сообщений - Радиосистема пожарной сигнализации
В системе, содержащей несколько устройств, для обмена информацией необходимо составить протокол обмена, который определяет очередность установления связи...
-
Задача8 Чему равна пропускная способность канала связи, описанного следующей матрицей: ? Решение Найдем безусловные вероятности источника и приемника:...
-
Оценка оптических несущих. Целью данного пункта является определения промежуточных частот и расстояния между соседними каналами. Рассмотрим подробно 3-е...
-
Новые подходы к защите передачи информации - Кодировщики голоса
Однако с выходом Постановления "Об утверждении положений о лицензировании отдельных видов деятельности, связанных с шифровальными (криптографическими)...
-
Анализ путей решения поставленной задачи Постановка задачи следующая: необходимо в несколько раз повысить пропускную способность магистральной ВОЛС...
-
ВВЕДЕНИЕ, Системы визуального отображения информации (видеосистемы) - Внешние устройства ЭВМ
Персональный компьютер (ПК)- это не один электронный аппарат, а Небольшой комплекс взаимосвязанных устройств, каждое из которых выполняет определенные...
-
Базовые понятия - Триггеры: общая характеристика
Триггер -- это запоминающий элемент с двумя (или более) устойчивыми состояниями, изменение которых происходит под действием входных сигналов и...
-
В результате анализа различных вариантов построения цифровых сотовых систем подвижной связи (ССПС) в стандарте GSM принят многостанционный доступ с...
-
Определение необходимого числа элементов памяти Для построения схемы необходимо три элемента памяти: Y 1 , Y 2 , Y 3 . Число элементов памяти...
-
В протоколе 802.11g предусмотрена передача на скоростях 1, 2, 5,5, 6, 9, 11, 12, 18, 22, 24, 33, 36, 48 и 54 Мбит/с. Некоторые из данных скоростей...
-
Синтез устной речи - это преобразование заранее не известной текстовой информации в речь. Речевой вывод информации - это речевого интерфейса, без которой...
-
АРМ - Понятие и структура. - Понятие экспертных систем (ЭС)
Современные масштабы и темпы внедрения средств автоматизации управления в народном хозяйстве с особой остротой ставит задачу проведения комплексных...
-
В результате сравнения производителей систем передач были выбраны две наиболее подходящие это система Cisco ONS 15808 и система ПУСК, выпущенная в России...
-
В современных системах связи все больше требуются скоростные широкополосные каналы связи для передачи информации. Отвечать растущим объемам передаваемой...
-
Рецептор - объект, который находится под воздействием электромагнитных помех. Внутри РЭС рецепторами выступают маломощные чувствительные элементы и узлы...
-
Железнодорожный транспорт на сегодняшний день является самым безопасным и надежным видом транспорта. Безопасность на железнодорожном транспорте...
ПОНЯТИЕ О ТЕОРЕМАХ ШЕННОНА - Кодирование информации