Теория информации |
Конспект лекций |
Введение
До середины ХХ века под информацией понимали только передачу сведений от одного человека другому человеку или группе людей с помощью устной или письменной речи, передачу условных знаков (символов) посредством специальных передающих устройств. Наскальные рисунки первобытных людей, передача световых сигналов, чтение книг – все это примеры выполнения операций по хранению, передаче и переработке информации.
Однако лишь к середине ХХ века информация стала предметом научного исследования. Начало развитию теории информации как научной дисциплины было положено в 1949 г. после публикации статьи «Математическая теория связи» К. Шеннона и У. Уивера, которые предложили количественную меру информации и заложили фундамент для дальнейших исследований в этой области.
Теория информации тесно связана с такими разделами математики как теория вероятностей и математическая статистика. С другой стороны теория информации представляет собой математический фундамент для теории связи. Таким образом, теория информации – это математическая теория, которая изучает процессы хранения, преобразования и передачи информации по каналам связи.
Под информацией нужно понимать совокупность упорядоченных данных о каких-либо событиях, процессах, явлениях и т.п., рассматриваемых в аспекте их передачи в пространстве и во времени.
Существует несколько взглядов на сущность информации, однако большинство специалистов считает, что существует информация двух типов:
Современная теория информация исходит из представления о том, что информация (которая обычно, но не обязательно имеет смысл), предназначенная для хранения или передачи по каналу связи не известна заранее с полной определенностью. Заранее известно лишь множество, из которого могут быть выбраны информационные сообщения, и возможно частота появления этих сообщений (т.е. вероятность сообщений). Такая «неопределенность» информационных сообщений допускает количественное выражение, что и определяет возможность хранения и передачи информации.
Основной моделью, которую изучает теория информации, является модель системы передачи сигналов:
Рисунок 1 Модель системы передачи сигналов
Начальным звеномв приведенной выше модели является источник информации. В курсе будут рассматриваться дискретные источники без памяти, в которых выходом является последовательность символов некоторого фиксированного алфавита или сообщения. Множество всех различных символов, порождаемых некоторым источником, называется алфавитом источника, а количество символов в этом множестве – размером алфавита источника. Например, можно считать, что текст на русском языке порождается источником с алфавитом из 33 русских букв, пробела и знаков препинания.
Далее для передачи по каналу связи информация подвергается кодированию. Кодирование – это способ представления информации в удобном для хранения и передачи виде. В связи с развитием информационных технологий кодирование является центральным вопросом при решении самых разных задач программирования, таких как:
Кодирование дискретного источника заключается в сопоставлении символов алфавита А источника символам или группам символов алфавита В (которые называются кодовыми словами). Алфавит В называется кодовым алфавитом. Кодом называется совокупность всех кодовых слов, применяемых для представления порождаемых источником символов. Обратная процедура сопоставления кодовым словам алфавита В символов алфавита А называется декодированием.
Разработка и исследование эффективных конструкций кодирования информации являются одними из основных задач теории информации.
Пример. Азбука Морзе является общеизвестным кодом из символов телеграфного алфавита, в котором буквам русского языка соответствуют кодовые слова (последовательности) из «точек» и «тире».
При передаче закодированного сообщения по каналу связи могут возникать помехи (или шум), которые искажают сообщение, так что при декодировании приемник может получить изменённое сообщение. Для защиты сообщения от помех при передаче по каналу связи существуют специальные методы помехоустойчивого кодирования.
Далее будет рассматриваться только двоичное кодирование, т.е. размер кодового алфавита равен 2. Конечную последовательность битов (0 или 1) назовем кодовым словом, а количество битов в этой последовательности – длиной кодового слова.
Пример 1.1. Код ASCII (американский стандартный код для обмена информацией) каждому символу ставит в однозначное соответствие кодовое слово длиной 8 бит.
Известны два класса методов кодирования дискретного источника информации: равномерное и неравномерное кодирование. Под равномерным кодированием понимается использование кодов со словами постоянной длины. Для того чтобы декодирование равномерного кода было возможным, разным символам алфавита источника должны соответствовать разные кодовые слова. При этом длина кодового слова должна быть не меньше символов, где m – размер исходного алфавита, n – размер кодового алфавита.
Пример 1.2. Для кодирования источника, порождающего 26 букв латинского алфавита, равномерным двоичным кодом требуется построить кодовые слова длиной не меньше .
При неравномерном кодировании источника используются кодовые слова разной длины. Причем кодовые слова обычно строятся так, чтобы часто встречающиеся символы кодировались более короткими кодовыми словами, а редкие символы – более длинными (за счет этого и достигается «сжатие» данных).
Под сжатием данных понимается компактное представление данных, достигаемое за счет избыточности информации, содержащейся в сообщениях. Большое значение для практического использования имеет неискажающее сжатие, позволяющее полностью восстановить исходное сообщение. При неискажающем сжатии происходит кодирование сообщения перед началом передачи или хранения, а после окончания процесса сообщение однозначно декодируется (это соответствует модели канала без шума (помех)).
Методы сжатия данных можно разделить на две группы: статические методы и адаптивные методы. Статические методы сжатия данных предназначены для кодирования конкретных источников информации с известной статистической структурой, порождающих определенное множество сообщений. Эти методы базируются на знании статистической структуры исходных данных. К наиболее известным статическим методам сжатия относятся коды Хаффмана, Шеннона, Фано, Гилберта-Мура, арифметический код и другие методы, которые используют известные сведения о вероятностях порождения источником различных символов или их сочетаний.
Если статистика источника информации неизвестна или изменяется с течением времени, то для кодирования сообщений такого источника применяются адаптивные методы сжатия. В адаптивных методах при кодировании очередного символа текста используются сведения о ранее закодированной части сообщения для оценки вероятности появления очередного символа. В процессе кодирования адаптивные методы «настраиваются» на статистическую структуру кодируемых сообщений, т.е. коды символов меняются в зависимости от накопленной статистики данных. Это позволяет адаптивным методам эффективно и быстро кодировать сообщение за один просмотр.
Существует множество различных адаптивных методов сжатия данных. Наиболее известные из них – адаптивный код Хаффмана, код «стопка книг», интервальный и частотный коды, а также методы из класса Лемпела-Зива.