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

НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

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

Основы

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

и

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

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

для студентов 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. Конспект лекций для студентов 1 курса дневной и заочной форм обучения специальности 070800 «Экология и охрана окружающей среды» (включая изучающих русский язык как иностранный)

    План-конспект
    для студентов 1 курса дневной и заочной форм обученияспециальности 6.070800 «Экология и охрана окружающей среды»(включая изучающих русский язык как иностранный)
  2. Конспект лекций для студентов 1 курса всех форм обучения Кемерово 2010

    План-конспект
    В курсе общей биологии рассмотрены основные аспекты существования и функционирования живых систем, во взаимосвязи с окружающей средой. А также, основы селекции живых организмов и генной инженерии.
  3. Конспект лекций Для студентов Iкурса медицинского и аграрного факультетов

    План-конспект
    Пособие представляет собой конспект лекций, читаемых авторами студентам I курса медицинского факультета (специальность “Лечебное дело”) и аграрного факультета (специальности “Агрономия”, “Ветеринария”, “Зоотехния”).
  4. Конспект лекций для студентов всех форм обучения специальности 080110 «Экономика и бухгалтерский учет»

    План-конспект
    Конспект лекций составлен в соответствии с рабочей программой дисциплины «Налоги и налогообложение» и с учетом требований государственного образовательного стандарта по специальности 080110 «Экономика и бухгалтерский учет» (в пищевой
  5. Конспект лекций для студентов специальности «Лингвистика и межкультурная коммуникация»

    План-конспект
    Учебно-методическое пособие представляет программный материал по всем разделам курса «Стилистика английского языка», разработанным в соответствии с новым государственным образовательным стандартом, утвержденным 14.
  6. Конспект лекций для студентов филологических специальностей москва

    План-конспект
    Учебно-методическое пособие составлено в соответствии с государственным образовательным стандартом высшего профессионального образования, утвержденным 14.
  7. Конспект лекций для студентов по специальностям 190302 «Вагоны»

    План-конспект
    Тексты лекций по курсу «Химические источники тока и защита металлов от коррозии» предназначены для студентов дневного и заочного отделений специальностей «Электрический транспорт железных дорог», «Вагоны», «Электроснабжение железных дорог».
  8. Конспект лекций для студентов всех специальностей дневной и заочной формы обучения Челябинск

    План-конспект
    Тексты лекций по химии предназначены для студентов дневного и заочного отделений всех специальностей. Общетеоретическую базу лекций составляют учение о строении вещества, термодинамика и кинетика химических реакций, теории обменных
  9. Конспект лекций Для студентов ссузов Кемерово 2010 (1)

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

Другие похожие документы..