Кодирование информации

Теория кодирования - раздел теории информации, связанный с задачами кодирования и декодирования сообщений, поступающих к потребителям и посылаемых из источников информации. Эти задачи теория кодирования решает с учетом задачи наилучшего согласования посылаемой информации с каналами связи (каналами передачи данных). Под этим понимается стремление максимально использовать пропускную способность канала, а также обеспечить передаваемым сообщениям нужную степень защищенности от помех.

Термин «кодирование информации» можно рассматривать в широком и узком смыслах.

Широкий смысл термина подразумевает следующее.

При любых видах работы с информацией всегда идет речь о ее представлении в виде определенных символических структур. Наиболее распространены одномерные представления информации, при которых сообщения имеют вид последовательностей символов. Так информация представляется в письменных текстах, при передаче по каналам связи, в памяти ЭВМ. Однако широко используются и многомерные представления информации, причем под многомерностью понимают не только расположение элементов информации на плоскости или в пространстве (в виде рисунков, схем, графов, объемных макетов и т.д.), но и множественность признаков используемых символов. Например, информацию могут нести не только значения букв и цифр, но и их цвет, размер, вид шрифта. Всякое событие, всякое явление служит источником информации. Всякое событие, всякое явление может быть выражено по-разному, разным способом, разным «алфавитом», т. е. по-разному закодировано.

Таким образом, формирование представления информации называется ее кодированием.

Часто термин «кодирование» употребляется в более узком смысле, как переход от исходного представления информации к представлению, удобному для ее хранения, передачи или обработки. В этом случае обратный переход к исходному представлению информации называется декодированием. Иногда приводят и такое определение: кодирование – это запись информации по определённым правилам. Отсюда код – это правила сопоставления кодовых слов, т. е. определенных комбинаций символов, и передаваемых сообщений на передающем и приемном концах канала связи.

Информация не может существовать без материального носителя, без передачи энергии. Это хорошо иллюстрирует уже известный вам «демон» Максвелла. Закодированное сообщение приобретает вид сигналов — носителей информации. Они-то и текут по каналу. Выйдя на приемный конец канала связи, сигналы должны обрести вновь общепонятный вид. С этой целью сигналы пробегают декодирующее устройство, приобретая форму, удобную для абонента. Как правило, на разных этапах сложного информационного процесса информация перекодируется неоднократно. Кодирование и декодирование считаются одними из самых важных логических операций в ЭВМ.

В теории кодирования фундаментальное значение имеют две теоремы, доказанные известным американским ученым К. Шенноном, с которых, собственно, и началось развитие теории кодирования. Первая теорема Шеннона говорит о том, что при канале, не вносящем своих помех, можно закодировать сообщения таким образом, чтобы среднее число элементов кода, приходящихся на один элемент кодируемого алфавита, было бы минимальным (этот минимум определяется некоторым параметром H - энтропией источника информации, характеризующего статистические свойства источника). Такое кодирование называется эффективным статистическим кодированием.

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

Специальным разделом в теории кодирования является теория арифметических кодов, используемых для повышения надежности работы вычислительных устройств. Арифметические коды позволяют обнаруживать и исправлять ошибки, возникающие в арифметических устройствах ЭВМ. Правда, за такой сервис приходится расплачиваться лишним временем и оборудованием. Поэтому арифметические коды используются только в специальных ЭВМ, предназначенных для решения ответственных задач, когда ошибки в работе машины могут привести к весьма нежелательным последствиям (например, арифметические коды используются во многих ЭВМ, которые устанавливают на космических кораблях).

При кодировании могут ставиться разные цели и, соответственно, применяться разные методы. Наиболее распространенные цели кодирования - это экономность, т. е. уменьшение избыточности сообщения; повышение скорости передачи или обработки; надежность, т. е. защита от случайных искажений; сохранность, т. е. защита от нежелательного доступа к информации; удобство физической реализации (например, двоичное кодирование информации в ЭВМ); удобство восприятия. Эти цели часто противоречат друг другу, но именно они определяют выбор языка для кодирования. Экономные сообщения могут оказаться ненадежными, так как они не содержат лишних символов, и искажение любого символа может изменить смысл сообщения.

Например, обычная запись чисел цифрами гораздо экономнее и удобнее для вычислений, чем запись словами. Однако искажение или удаление любой цифры изменяет величину числа. Поэтому в финансовых документах, где надежность крайне важна, цифровые представления чисел в некоторых местах заменяются или дублируются словесными представлениями.

Теория кодирования подробно исследует проблемы разумного сочетания экономности и надежности при передаче информации.

Экономное сообщение может повысить скорость обработки, но может и уменьшить ее. Например, очень экономно использовать вместо фамилий и имен учеников школы коды типа 10А5 (десятый класс «А», пятый по порядку в журнале). Но тогда надо либо помнить все соответствия между фамилиями и кодами, либо каждый раз обращаться к журналу. Повысить качество всех параметров одновременно нельзя: улучшение одного из них, как правило, ухудшает другой. Выход из положения нашли в том, что на разных этапах передачи информации совершенствуют разные параметры, т. е. в процессе передачи информацию несколько раз перекодируют, причём с разными целями. Например, текст телеграммы, написанный на обычном языке, преобразуют в один из телеграфных кодов, который технически удобнее передавать, а при приёме снова превращают в обычный текст. Но иногда выбирают наиболее важный параметр и улучшают в первую очередь его.

Рассмотрим более подробно двоичное кодирование.

При двоичном кодировании, как правило, интересуются только одним параметром — экономностью записи; в сообщениях не должно быть лишних символов. Но именно это и делает передачу информации ненадёжной: если пропадает или изменяется хотя бы один символ, часть информации утрачивается либо искажается. На помощь приходят математические методы кодирования, они позволяют обнаруживать и исправлять ошибки, возникающие при передаче. Такое кодирование называют помехоустойчивым.

При наличии помех принять сообщение без ошибок помогает, прежде всего, его избыточность. Если сообщение неизбыточно, избыточность вводят специально, например, повторяют одно и то же несколько раз.

Самый простой и экономный способ борьбы с ошибками в двоичной информации — контроль чётности, когда последовательность нулей и единиц разбивают на группы с одинаковым числом символов, В каждой группе подсчитывают число единиц. Если оно чётное, то справа добавляют 0; если нечётное, — добавляют 1. Тогда в любом случае число единиц получается чётным.

Добавочный символ не несёт информации, зато позволяет обнаружить ошибку. Если при передаче возникает ошибка, то 0 изменяется на 1 или 1 — на 0 и, следовательно, число единиц становится нечётным. При приёме сообщений снова в каждой группе символов подсчитывают число единиц. Если оно чётное, ошибок нет. Конечно, такой вывод верен только тогда, когда заранее известно, что парные ошибки в одной группе практически невозможны. Поэтому количество символов в группах подбирают в зависимости от того, насколько часто появляются ошибки. Чем реже они случаются, тем длиннее могут быть группы. При этом уменьшается число самих групп и добавочных символов, а значит, и избыточность. Этот метод широко применяется в компьютерах, где вероятность ошибок невелика.

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

Часто приходится решать обратную задачу — уменьшать естественную избыточность текстов. Такая процедура называется сжатием или упаковкой информации. Её применяют в тех случаях, когда хранить информацию приходится долго, но работать с ней — редко, а также при передаче длинных текстов.

Дата добавления: 2013-12-13