ОСНОВЫ ТЕОРИИ ИНФОРМАЦИИ Презентация лекции по курсу «Общая теория связи» © Д.т.н., проф. Васюков В.Н., Новосибирский государственный технический университет, Новосибирск, пр. К. Маркса, 20 Факультет Радиотехники и электроники Кафедра теоретических основ радиотехники

22 Информация относится к предельно широким понятиям (как пространство, время, материя и т.п.) Основные понятия и термины Для решения иноженерных задач требуется количественная характеристика. В теории и технике связи используется определение количества информации, предложенное Клодом Шéнноном (Claude Elwood Shannon, ) информация данные сведения и т.п.

3 Определение количества информации 1. Нужно абстрагироваться от физического воплощения источнока сообщений 2. Нужно абстрагироваться от смыслового (семантического) содержания сообщений Тогда сообщение предстаёт как последовательность символов, случайная с точки зрения наблюдателя (получателя) источнок сообщений

4 Определение количества информации источнок сообщений алфавит источнока ( K – объем алфавита) длина, распределение вероятностей, заданное на множестве всех последовательностей произвольной длины может быть каким угодно, но способ вычисления вероятностей д.б. достаточно простым и удобным

5 Источнок без памяти Источнок без памяти – простейший случай дискретного источнока: символы в последовательности являются независимыми, и распределение полностью определяется набором априорных вероятностей отдельных символов условная вероятность появления конкретного символа в любой позиции последовательности равна безусловной (априорной) вероятности этого символа

6 В моделях источноков с памятью условная вероятность символа зависит от того, какие символы ему предшествуют. В телеграмме на русском языке после буквы «щ» можно ожидать букв «а», «у», «е», но не «ю», «я», «й» и т.п. Щ АБВ…Й…ЭЮЯАБВ…Й…ЭЮЯ

7 Если условная вероятность очередного символа зависит от одного предшествующего символа марковский источнок 1 порядка. Марковские источноки могут иметь порядок 2, 3 и т.д. Обычно чем выше порядок учитываемых связей, тем сильнее условные вероятности символов отличаются от безусловных (априорных). Чем больше учитывается предшествующих символов, тем вернее предсказание очередного: …(.) в скобках может быть всё что угодно …и(.) …ни(.) …чни(.) в скобках могут быть буквы в, к, л, м, ц, с, т …очни(.) …точно(.) …сточно(.) …источно(.) в скобках может быть только буква к Далее рассматриваются источноки без памяти Буквы в порядке убывания (оценок) вероятностей: е t a o i n h s r d l m u w y c f g p b v k x j q z ое(ё)аитнсрвлкмдпуяызь(ъ)бгчйхжюшцщэф

8 Информационная последовательность символов, представляющая собой сообщение, может быть заменена другой, кодовой последовательностью, состоящей из символов кодового алфавита. Целью кодирования может быть: 1. более полное использование канала связи (эффективное кодирование) или 2. Повышение верности передачи (помехоустойчивое кодирование). 3. согласование сообщения с каналом (напр., кодирование в аппарате Бодо). Кодирование

9 Кодирование кодер Естественно, кодовые последовательности характеризуются другими распределениями вероятностей, нежели информационные последовательности.

10 Дискретный канал связи канал связи Полное описание – для всех возможных и описывает вероятностный механизм действия помех в канале. Если количество символов не изменяется в канале, то В случае канала без памяти полностью определяется набором условных вероятностей для всех пар отдельных символов для канала с памятью всё сложнее

11 Информация – это свойство сообщения снимать (или уменьшать) неопределенность относительно исхода некоторого случайного опыта (например, относительно переданного символа). Количество получаемой информации, очевидно, должно быть связано со степенью снятия неопределенности. Так, получая сообщение о событии, которое достоверно известно, информации мы не получаем (неопределенности нет, и снимать нечего). Согласно теории информации Шеннона * * известна ещё алгоритмическая теория информации А.Н. Колмогорова, не получившая (пока?) широкого применения

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

13 Требования к количественной мере информации Если определить «неожиданность» сообщения, то выполняется только второе требование А если ввести логарифмическую меру, то все три: [бит] [нат] [хартли] Ральф Хартли (Ralph Hartley )

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

15 Количество информации, вырабатываемой дискретным источноком Информационная производительность дискретного источнока – среднее количество информации на символ – математическое ожидание этой случайной величины. Энтропия мера информационной производительности (на символ) источнока сообщений Для источнока без памяти среднее количество информации, приходящееся на один символ

16 Основные свойства энтропии 1. Энтропия любого источнока неотрицательна Это следует из того, что вероятность любого события неотрицательна и не превосходит единицы 2. Энтропия равна нулю, если один из символов имеет вероятность 1, а остальные – вероятности 0.

17 3. При заданном объеме алфавита энтропия максимальна, если все символы равновероятны при Составим целевую функцию (по методу неопр. мн. Лаграножа) Условие экстремума Жозе́ф Луи́ Лагра́нож (Joseph Louis Lagrange, )

18 Условие экстремума Решая относительно получаем вероятность не зависит от i, т.о., энтропия максимальна при равных вероятностях символов

19 В частности, при K=2 энтропия максимальна при вероятностях символов ½ и равна 1 биту Таким образом, 1 бит – это количество информации, доставляемое одним из двух равновероятных символов, вырабатываемых источноком без памяти.

20 Совместная энтропия двух источноков очевидно логарифм произведения = сумма логарифмов

21 тогда первое слагаемое Второе слагаемое – условная энтропия

22 Совместная энтропия, таким образом, равна Если источноки статистически независимы, то (аддитивность информации) канал связи рассматривается как новый источнок Условная энтропия двух связанных источноков Канал описывается набором всех условных вероятностей Некоторые из них должны быть близки к 1, остальные к 0.

23 Количество информации в символе относительно символа Если, то столько информации, сколько несет символ Если, то 0,

24 Очевидно Это – взаимная информация символов и

25 Наблюдение выходной последовательности символов не снимает полностью неопределенность относительно переданного сообщения. Канал характеризуется энтропией входного алфавита при условии наблюдения выходных символов. Чем меньше эта условная энтропия, тем лучше канал передаёт информацию:

Свойства условной энтропии Если источноки сообщений являются независимыми Действительно, из независимости Но откуда условная энтропия равна безусловной

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

Пример 28 Пусть на входе двоичного канала действует источнок с равновероятными символами 0 и 1, а искажения символов при передаче происходят с некоторыми вероятностями Найдем количество информации в выходном символе относительно входного Безусловные вероятности выходных символов

29 Взаимные информации

30 а. Канал без помех энтропия источнока равна 1 биту и взаимная информация входных и выходных символов равна также 1 биту при их совпадении, такой канал обеспечивает передачу информации без потерь б. «Обрыв канала» Частные (предельные) случаи

31 Если энтропия входного источнока в отсутствие передачи равна, а после приёма выходного символа она становится равной, то, очевидно, среднее количество передаваемой информации на символ равно разности Это взаимная информация входа и выхода канала (на символ) – ненадежность, равна 0 при отсутствии помех в канале и равна энтропии источнока при обрыве канала

32 Вспомним совместную энтропию Отсюда следует а также Тогда

33 Производительность источнока [бит/с] Скорость передачи информации по каналу [бит/с] Пропускная способность канала [бит/с]