Конспект лекций для студентов III курса фпми по специальностям “Прикладная математика и информатика” (010500) icon

Конспект лекций для студентов III курса фпми по специальностям “Прикладная математика и информатика” (010500)


Смотрите также:
Программа дисциплины опд. Фз...
Программа дисциплины дс. 11...
Периоды исторического развития математики...
Программа государственного экзамена «Вычислительная математика» для студентов проходящих...
Методические указания по выполнению контрольной работы для студентов направления 010500...
Программа дисциплины дс...
Программа дисциплины дс...
Программа дисциплины ф дифференциальные уравнения для студентов специальности 010501 (прикладная...
Программа дисциплины дс...
Программа дисциплины ен. Ф...
Рабочая программа по дисциплине «Методы и средства защиты компьютерной информации» для...
Рабочая программа по дисциплине «Теория вычислительных процессов» для направления 010500...



Загрузка...
страницы:   1   2   3   4
скачать
НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ


Т.А. Гультяева


Основы

теории информации

и

криптографии


Конспект лекций

для студентов III курса ФПМИ по специальностям

“Прикладная математика и информатика” (010500),

“Математическое обеспечение и администрирование

информационных систем” (010503),

“Прикладная информатика в менеджменте” (080801)


Новосибирск

2010

Рецензенты:

Н.Л. Долозов, канд. техн. наук, доц. кафедры программных систем и баз данных.

^ В.Е. Хиценко, канд. техн. наук, доц. кафедры защиты информации


Составитель: Т. А. Гультяева, ассистент кафедры программных систем и баз данных.


Работа подготовлена на кафедре программных систем и баз данных

для студентов III курса ФПМИ по специальностям

“Прикладная математика и информатика” (010500),

“Математическое обеспечение и администрирование

информационных систем” (010503),

“Прикладная информатика в менеджменте” (080801)


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

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

^






Тема №1

Основные аспекты теории информации





    1. Введение в теорию информации.

Задачи, решаемые в рамках теории информации


Теория информации – наука, появившаяся в 1948 г. в результате публикации работы Клода Шеннона «Математическая теория связи».

Ниже представлена структурная схема типичной системы передачи или хранения информации (рис. 1).




Рис. 1. Структурная схема типичной системы передачи или

хранения информации


Источник – любое устройство или объект живой природы, порождающие сообщения, которые должны быть перемещены во времени или пространстве. Например, клавиатура, человек.

^ Цель кодера источника – представление информации в наиболее компактном виде. Это надо для того, чтобы эффективно использовать ресурсы канала связи или запоминающего устройства.

^ Кодер канала производит обработку информации с целью защиты сообщений от помех при передаче по каналу связи либо от возможных искажений при их хранении.

Модулятор используется для преобразования сообщений, формируемых кодером канала, в сигналы, согласованные с физической природой канала связи или средой накопления информации.

Остальные блоки выполняют обратные действия и представляют полученную информацию в удобном для использования виде.


Таким образом, в теории информации можно выделить следующие задачи:

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

  2. Кодирование информации для передачи по каналу с шумом (защита информации от помех в канале связи).

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

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

  5. Секретная связь, системы защиты информации от несанкционированного доступа.




    1. Вероятностно-статистические модели сообщений

и их свойства


      1. ^ Источники дискретных сообщений

и их вероятностные модели


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

Отдельные символы сообщения: – это случайная величина, принимающая всевозможные значения из алфавита сообщений : .

Если мощность конечна: , то это источник дискретного сообщения (ИДС). Иначе – источник непрерывного сообщения.

Мы будем использовать модель ИДС как наиболее часто рассматриваемую.

– это символы алфавита; – мощность алфавита. Появление символа алфавита в сообщении описывается дискретной вероятностной моделью.

Дискретный ансамбль – это полная совокупность состояний (символов алфавита) с вероятностью их появления:

,

где .

Понятно, что данная модель описывает лишь одиночный случайный символ сообщения.

^ Сообщение, порождаемое ИДС – это, в общем случае, последовательность случайных символов: . При этом полное вероятностное описание ИДС задается вероятностной моделью случайного временного ряда (случайного процесса) с дискретным временем N и дискретным пространством состояний : ,

где n-мерное дискретное распределение вероятностей n-символьного сообщения.

ИДС является стационарным, если случайный процесс инвариантен относительно сдвига начала отсчета . Стационарный ИДС является источником без памяти, если порождаемые ИДС случайные символы независимы в совокупности и одинаковы распределены.



      1. ^ Собственная информация


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

Собственная информация сообщения , выбираемого из дискретного ансамбля – это:


.

(1.1)








Если , то количество информации измеряется в битах; – натах; –ди/хартли (Хартли впервые предложил эту формулу в виде в 1928 г.).


Свойства собственной информации:

  1. .

  2. Монотонность: если , то .

  3. Аддитивность: (для независимых сообщений) .


Пример

Дан ансамбль: . Кодирование будем производить, используя 0 и 1.



.●


Видно, что чем выше вероятность появления символа в сообщение (чем чаще он появляется), тем меньшим числом бит его надо кодировать, чтобы сэкономить на длине закодированного сообщения.

Таким образом, собственная информация характеризует степень неожиданности появления конкретного сообщения.


^ Пример

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


Решение

Случайная величина – яркость одного элемента изображения. .

. Изображение содержит элементов. Так как яркости элементов независимы, то .●


Пример

На экране радара полос; изображение появляется в виде яркой отметки. Все положения равновероятны. Определить количество собственной информации, содержащейся в сообщениях: (а) объект находится в 46 квадранте, (б) объект находится в 5-ой горизонтальной строке.


Решение

(а) .

(б) .●



      1. Взаимная информация


Рассмотрим два ансамбля сообщений: . – ансамбль сообщений на входе системы, – на выходе. Естественно, что они зависимы.

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


.

(1.2)


Это и есть определение взаимной информации.


Свойства взаимной информации:

  1. .

Если , то считается, что наступление события делает наступление события менее вероятным, чем оно было априори до наблюдения .

  1. , – взаимная информация не превышает свою собственную.

При данном взаимная информация достигает своего максимума, когда принятый символ однозначно определяет переданный символ .

При этом и это максимальное значение равно , то есть собственной информации, определяемой только априорной вероятностью символа .

  1. Симметрия: . Информация, содержащаяся в относительно , равна информации, содержащейся в относительно . Поэтому – это именно взаимная информация.

  2. Аддитивность: , только при условии, что ансамбли независимы от .


Информация, содержащаяся в реализации принятого сигнала относительно ансамбля передаваемых сообщений , определяется следующей формулой:




(1.3)


Наконец, средняя взаимная информация между ансамблем принимаемых сигналов и ансамблем передаваемых сообщением определяется формулой (4):




(1.4)


то есть то количество информации, которое содержится в среднем в ансамбле принимаемых символов относительно ансамбля передаваемых символов .




Пример.

По дискретному каналу передаются сообщения и . Вследствие шумов на выходе канала появляются сигналы . Вероятности их совместного появления заданы в таблице:












1/4

1/16

1/8



1/8

3/16

1/4

Необходимо найти взаимную информацию и .


Решение

.

, .

. Значит, .

Аналогично: .●


Пример

Дан ансамбль сообщений:




















1/2

1/4

1/8

1/32

1/32

1/32

1/32

Код

001

010

100

011

101

110

111

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


Решение

Найдем взаимную информацию, содержащуюся в первом кодовом символе ‘1’ относительно сообщения : (см. следующий рисунок).



1

?

?
Кодовое слово на выходе:


, где – это гипотеза о том, что было передано 4-ое сообщение.

– это вероятность появления ‘1’ на первом месте в кодовом слове.

.

Таким образом, .

Информация, содержащаяся во втором кодовом символе ‘0’ при условии, что первый кодовый символ равен ‘1’:

, где

.



1

0

?
Кодовое слово на выходе:


Информация, содержащаяся в третьем кодовом символе ‘1’ при условии, что первые два кодовых символа равны ‘10’:

.


1

0

1
Кодовое слово на выходе:


Так как сообщение и кодовые слова однозначно связаны, то

.


По свойству 2) получаем тот же ответ: .●


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



      1. Энтропия


Пусть ИДС описывается некоторым дискретным ансамблем: . Тогда энтропия ИДС (или энтропия случайного символа ) вычисляется по формуле (5):


.

(1.5)


Впервые эта мера была предложена Клодом Шенноном в “Математической теории связи”. Вид этой формулы совпадает с полученным ранее результатом Больцмана для энтропии термодинамических систем.

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


Свойства энтропии:

  1. .

, если неслучайно.

  1. .

, если . Это возможно, если источник без памяти или все сообщения равновероятны.

  1. Аддитивность: в последовательности независимых символов энтропия равна сумме энтропий, содержащихся в отдельных символах:

.

  1. Если распределение вероятностей ансамблей одинаково, а ансамбли отличаются только порядком следования элементов, то их энтропии равны.


Пример

Рассмотрим двоичный ансамбль: .

Энтропия: .




Рис. 2. График функции


Таким образом, максимальное среднее количество информации, переносимое двоичным сигналом – это 1 бит.●


Пример

На измерительной станции есть 2 прибора:

1-ый имеет 100 делений, его показания меняются каждые 0.05 секунд.

2-ой имеет 10 делений, его показания меняются каждые 0.01 секунд.

Какова наибольшая средняя информация, поставляемая двумя приборами в 1 секунду?


Решение

Так как все деления на приборах равновероятны, то энтропия ^ 1-ого прибора:

. Аналогично для 2-ого прибора: .

Число измерений в секунду 1-ым прибором: , 2-ым: . Энтропия двух приборов в 1 секунду (их показания независимы друг от друга): .●


Пример

Производится стрельба по двум мишеням. По 1-ой сделано 2 выстрела, по 2-ой – 3. Вероятность попадания при одном выстреле: 1/2 и 1/3 соответственно. Исход стрельбы (при одном попадании) по какой мишени более не определен?


Решение

Исход стрельбы определяется числом попаданий в мишень, которое подчиняется биномиальному закону распределения: . Здесь – это число попаданий в мишень, – вероятность попадания в мишень.

Ряд распределения для числа попаданий в 1-ую мишень при (число выстрелов по мишени) и при вероятности попадания в мишень приведен далее.



0

1

2

(вероятность попаданий)

1/4

1/2

1/4


Аналогично – ряд для 2-ой мишени:



0

1

2

3

(вероятность попаданий)

8/27

4/9

2/9

1/27

Мера неопределенности исхода стрельбы – это энтропия числа попаданий по мишени.

Энтропия при стрельбе по ^ 1-ой мишени:

.

Энтропия при стрельбе по 2-ой мишени: .

Таким образом, исход стрельбы по 2-ой мишени обладает большей неопределенностью.●



      1. Условная энтропия


Пусть имеются два статистически независимых конечных ансамбля символов . Пары символов с вероятностью – это элементарные символы объединенного ансамбля с энтропией, вычисляемой по формуле (6):


.

(1.6)


Появление символа вызывает появление символа с вероятностью .

Частная условная энтропия:


.

(1.7)


Средняя условная энтропия ансамбля при условии, что ансамбль известен:




(1.8)


Свойства условной энтропии:

  1. , при условии, что зависимы.

Кроме того:

.

  1. , если независимы.

  2. , причем равенство только в случае, если независимы.

  3. .

  4. .

Причем равенство только в случае, если условно независимы при всех .


Далее приводятся формулы для связи средней взаимной информации и энтропии:

  1. .

  2. .

  3. , то есть энтропия – это частный случай функционала средней взаимной информации.

  4. .

Причем равенство нулю возможно тогда и только тогда, когда статистически независимы.




Пример

Вычислить энтропию , условную энтропию и среднюю взаимную информацию , если дано двух ансамблей :












0.5

0

0.5



0.25

0.25

0.5



0.75

0.25





Решение

Найдем :










1

0



0.5

0.5

Энтропия ,

,

,

.

Средняя взаимная информация: .●



      1. Избыточность


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

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


.

(1.9)


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

Статистические связи между сигналами наблюдаются в случае ИДС с памятью: здесь вероятность выдачи им очередного элемента сообщения зависит от того, какие элементарные сообщения были выданы ранее.

Примером ИДС с памятью является источник связного русского текста, где в качестве элементарных сообщений выступают буквы. Сочетание ‘ар’ будет встречаться чаще, чем ‘аъ’.

Избыточность показывает, какая доля максимально возможной при заданном объеме алфавита неопределенности (энтропии) не используется источником.


Пример

Дан ансамбль: .

Символы в последовательности независимы. Найти энтропию источника и вычислить избыточность.


Решение

Энтропия: .

Избыточность за счет неоптимальности (не равновероятности) распределения элементарных сообщений в источнике: , где .●




Пример

Алфавит источника состоит из трех букв . Определить энтропию на 1 букву текста для следующих случаев:

(а) появление букв не равновероятно: , а символы в последовательности на выходе источника статистически зависимы. Условные вероятности переходов заданы таблицей:

i – индекс предыдущей

буквы

j – индекс последующей буквы




1

2

3

1

0.4

0.2

0.4

2

0.0

0.6

0.4

3

0.3

0.0

0.7

(б) вероятности букв те же, что и в пункте (а), но символы независимы;

(в) символы в последовательности независимы, а вероятности букв одинаковы.

Вычислить избыточность источника для случаев (а) и (б).


^ Решение

(а) В случае не равновероятных и зависимых сообщений энтропию текста будем считать по свойству 1) условной энтропии, где

а условную энтропию по формуле (8):



Энтропия на один символ:




(б) При не равновероятных, но независимых сообщениях энтропия по свойству 2) условной энтропии:



Избыточность, обусловленная статистической зависимостью:

=.


(в) В случае равновероятных и независимых сообщениях энтропия:

.


Избыточность, обусловленная неоптимальностью распределения:

.


Полная избыточность (за счет неоптимальности распределения и наличия статистических зависимостей):

.●




оставить комментарий
страница1/4
Т. А. Гультяева
Дата04.03.2012
Размер0,87 Mb.
ТипКонспект, Образовательные материалы
Добавить документ в свой блог или на сайт

страницы:   1   2   3   4
хорошо
  1
отлично
  4
Ваша оценка:
Разместите кнопку на своём сайте или блоге:
rudocs.exdat.com

Загрузка...
База данных защищена авторским правом ©exdat 2000-2017
При копировании материала укажите ссылку
обратиться к администрации
Анализ
Справочники
Сценарии
Рефераты
Курсовые работы
Авторефераты
Программы
Методички
Документы
Понятия

опубликовать
Загрузка...
Документы

наверх