- •В.Г. Ланских теория информации
- •Предисловие
- •Содержание
- •Лекция 1 введение
- •Глава 1.
- •1.1. Случайные события и их вероятности
- •Случайные величины и процессы
- •1.2.1. Дискретные случайные величины и процессы
- •1.2.2. Непрерывные случайные величины и процессы
- •1.3. Методы спектрального описания случайных процессов
- •1.3.1. Понятие спектра детерминированного процесса
- •1.3.2. Спектральное описание случайных процессов
- •1.4. Дискретизация и квантование
- •1.4.1. Дискретизация
- •1.4.2. Квантование
- •1.5. Классификация помех
- •1.6. Модели каналов
- •1.6.1. Модели дискретных каналов
- •1.6.2. Модели непрерывных каналов
- •1.7. Методы модуляции
- •1.7.1. Непрерывные методы модуляции и манипуляции
- •1.7.2. Методы импульсной модуляции
- •1.7.3. Методы цифровой модуляции
- •1.8. Согласование характеристик сигнала и канала
- •Глава 2 количественные оценки информационных объектов и процессов
- •2.1. Подходы к определению количества информации
- •Основы статистического подхода к определению количества информации
- •2.3. Энтропия объединения (ансамбля)
- •2.4. Основная теорема Шеннона для дискретного канала
- •2.5. Энтропийные характеристики непрерывных информационных
- •Глава 3 основы теории кодирования
- •3.1. Назначение и классификация кодов
- •3.2. Эффективное кодирование
- •3.3. Помехоустойчивое кодирование
- •3.3.2. Классификация избыточных двоичных кодов
- •3.3.3 Простейшие блоковые коды с обнаружением ошибок
- •3.3.4. Групповые коды с обнаружением и исправлением ошибок
- •Важнейшие классы полиномиальных кодов
- •3.3.5. Сверточные коды
- •3.3.6. Каскадные коды
- •3.3.7. Оценка эффективности применения корректирующих кодов
Основы статистического подхода к определению количества информации
Интуитивно понятно, что количество информации, которое получает адресат, приняв сообщение, некоторым образом связано с априорной неопределенностью (доопытной, существовавшей до получения сообщения), которая, в свою очередь, зависит от числа возможных сообщений. Чем больше число возможных сообщений, тем больше априорная неопределенность получения одного из них и тем большее количество информации получает адресат, когда эта неопределенность снимается после получения сообщения.
Первая попытка ввести научно обоснованную меру количества информации была сделана в 1928 году Р. Хартли. Он предложил и обосновал количественную меру, позволяющую сравнивать способность различных систем передавать информацию. Эта мера подходит как для систем передачи, так и для систем хранения информации, поэтому она явилась отправной точкой для создания теории информации.
Естественным требованием, предъявляемым к информационной мере, является ее аддитивность: количество информации, которое можно сохранить в двух однотипных ячейках, должно быть в два раза больше, а в n одинаковых ячейках в n раз больше, чем в одной ячейке. Если ячейка для хранения информации имеет m возможных состояний, то две такие ячейки будут иметь m2 возможных состояний, а n одинаковых ячеек – mn возможных состояний. Следовательно, существует экспоненциальная зависимость между числом возможных состояний и числом ячеек. Учитывая эту зависимость, для количественной оценки способности системы хранить или передавать информацию Хартли ввел логарифмическую меру информационной емкости
Ih=log m, (2.1)
где m -число различных состояний системы. Такая мера удовлетворяет требованию аддитивности. Емкость устройства, состоящего из n ячеек и имеющего mn состояний, равна емкости одной ячейки, умноженной на число ячеек
C= log mn=n log m.
За единицу измерения информационной емкости принята двоичная единица – бит, равная емкости одной ячейки с двумя возможными состояниями.
Хартли ограничился рассмотрением информационной емкости как величины характеризующей физическую систему. Эта оценка дает представление о потенциальной максимально возможной информационной емкости информационной системы, в ней не учтены вероятности различных состояний. Таким образом, мера Хартли, строго говоря, является не статистической, а структурной мерой количества информации.
Дальнейшее развитие теория информации получила в трудах К.Шеннона, который ввел в нее понятия неопределенности и энтропии. Он ограничил применимость формулы Хартли (2.1) лишь тем случаем, когда все m исходов опыта X (т.е. состояний системы) равновероятны. В этом случае вероятность любого исхода и тогда формулу Хартли (2.1.) можно переписать в следующем виде
. (2.2.)
Принципиальное отличие этой формулы от (2.1.) состоит в том, что она показывает, что неопределенность исхода зависит от вероятности исхода.
Далее Шеннон применил эту формулу к разновероятным событиям, усреднив затем полученные неопределенности по всем исходам.
Для опыта X = {x1,. . . xm}, где x1,. . . xm - возможные исходы с вероятностями p1,. . . pm, неопределенность каждого исхода -logp1,. . . -logpm, а математическое ожидание по формуле
. (2.3.)
Получаемую по формуле (2.3) величину Шеннон назвал энтропией.
Таким образом, неопределенность каждой ситуации характеризуется величиной, называемой энтропией. Понятие энтропии существует в ряде областей знаний. Энтропия в термодинамике означает вероятность теплового состояния вещества, в математике – степень неопределенности ситуации или задачи, в теории информации – способность источника отдавать информацию. Все эти понятия родственны между собой. Так, например, согласно второму закону термодинамики энтропия замкнутого пространства выражается как , где N - общее количество молекул в данном пространстве, ni - количество молекул, имеющих скорость vi. Но есть частоты событий, следовательно, вероятности того, что молекулы имеют скорость vi ,равна . Тогда , что аналогично (2.3). Выбор основания логарифма несуществен, поскольку определяет лишь единицы измерения энтропии.
Поясним далее соотношение понятий энтропии и количества информации.
В соответствии с определением понятия энтропия является мерой априорной неопределенности, существовавшей до получения сообщения. Под количеством информации, содержащимся в сообщении, понимается мера снятой неопределенности после получения сообщения.
Предположим, что до получения сообщения ситуация характеризовалась энтропией H1, после получения сообщения энтропия уменьшилась и стала равной H2. Тогда количество информации, содержащееся в этом сообщении, равно I = H1 - H2. Если неопределенность в результате получения сообщения снимается полностью, т.е. H2 = 0, то I = H1.
Энтропия обладает следующими свойствами:
1. Энтропия всегда неотрицательна, т.к. значения вероятностей выражаются числами, не превосходящими единицу, а их логарифмы, следовательно, отрицательными числами, так что члены суммы в формуле (2.3) всегда положительны.
2. Энтропия равна 0 в том и только в том случае, когда вероятность одного из исходов pk = 1, следовательно, вероятность всех остальных исходов равна 0. Это соответствует тому случаю, когда исход опыта может быть предсказан с полной достоверностью и отсутствует всякая неопределенность, сообщение об исходе не несет никакой информации.
3. Энтропия имеет наибольшее значение, когда вероятности всех исходов равны между собой p1 = p2 . . . = pm = 1/m, тогда
. (2.4.)
Если полученное выражение сравнить с (2.1), то это явится еще одним доказательством того, что мера Хартли дает представление о потенциальных возможностях информационной системы. В случае неравенства вероятностей количество информации по Шеннону меньше информационной емкости системы.
Рассмотрим простейший пример с элементарным двоичным событием:
1) пусть p1 = p2 = 0,5, тогда H = -(0,5log0,5 + 0,5log0,5) = 1 бит;
2) пусть p1 = 0,9, p2 = 0,1, тогда H = -(0,9log0,9 + 0,1log0,1) = 0,46 бит;
3) пусть p1 = 1, p2 = 0, тогда H = -(1log1 + 0log0) = 0 бит.
Если во всех полученных выражениях под опытом X понимать способность некоторого дискретного источника формировать то или иное сообщение из их совокупности X, то все сказанное о количестве информации и энтропии может быть отнесено к источнику информации.
Введение понятия энтропии источника позволяет дать точные определения упомянутых во введении характеристик, называемых избыточностью источника и производительностью источника.
Относительная избыточность источника определяется по формуле
, (2.5)
где m - объем алфавита источника, т.е. способность формировать m различных сообщений (символов). Относительная избыточность показывает, какая доля максимально возможной при данном объеме алфавита энтропии не используется источником.
Пусть, например, источник выдает символы x1, x2, x3, x4 с вероятностями p(x1)=0,2, p(x2)=0,3, p(x3)=0,4, p(x4)=0,1. Найти количество информации в каждом из символов источника при их независимом выборе (источник без памяти). Требуется найти энтропию и избыточность данного источника. Количество информации в каждом из символов xi определяется по формуле (2.2)
Энтропия источника, выдающего эти символы, по формуле (2.3)
бит/символ.
Избыточность источника находится по формуле (2.5)
.
Избыточность источника зависит как от степени неравновероятности отдельных символов, так и от наличия и протяженности статистических связей между последовательно выбираемыми символами, т.е. от памяти источника.
Если источник без памяти, т.е. последовательно передаваемые символы независимы, и все символы равновероятны, то H(X) = Hmax и отн = 0.
Источник, как и случайный процесс, называется стационарным, если описывающие его вероятностные характеристики не меняются во времени.
Пусть, например, стационарный источник выдает за время Т=106 секунд 107 бит информации двоичными посылками длительностью =10 мс. За какое время и каким количеством двоичных посылок можно передать тот же объем информации, если соответствующей обработкой полностью устранить избыточность источника. Определить избыточность источника.
Заданное количество информации I = 107 бит источник передает n посылками или символами, где n = Т/ = 108. Тогда среднее количество информации, приходящееся на одну посылку или символ, H = I/n =0,1 бит/символ. Если в результате соответствующей обработки избыточность полностью устранена, то каждый символ двоичного источника несет в себе Hmax = 1 бит информации. Тогда заданное количество информации может быть передано n0= I/ Hmax = 107 посылками при той же их длительности =10 мс за время T0 = n0 =105 c.
Избыточность источника по формуле (2.5)
.
Если дискретный источник выдает сообщения, затрачивая в среднем время Т на каждое сообщение, то производительностью (в битах в секунду) такого источника называется суммарная энтропия сообщений, переданных в единицу времени
, (2.6)
где - скорость источника, под которой понимается количество сообщений (символов), выдаваемых источником в единицу времени.