Теория информации. Курс лекций (500,00 руб.)

Стр.1

Стр.1

Стр.2

Стр.3

Стр.4

Стр.5

Стр.6

Стр.1

В. М. Белов, С. Н. Новиков, О. И. Солонская ТЕОРИЯ ИНФОРМАЦИИ Курс лекций Допущено Сибирским региональным отделением УМО по образованию в области информационной безопасности в качестве учебного пособия для студентов, обучающихся специальности 090302 – «Информационная безопасность телекоммуникационных систем» Москва Горячая линия - Телеком 2012

Стр.1

УДК 621.391 (075.8) ББК 32.811 Б78 Белов В. М., Новиков С. Н., Солонская О. И. Б78 Теория информации. Курс лекций. Учебное пособие для вузов. – М.: Горячая линия–Телеком, 2012. – 143 с.: ил. ISBN 978-5-9912-0237-4. Рассмотрены в доступной форме основные положения теории информации. Материалы систематизированы по следующим ключевым разделам: определение информационных потерь в каналах связи с помехами, построение оптимальных кодов, обнаружение и исправление ошибок при использовании различных методов передачи и обработки информации, представление кодов в памяти ЭВМ в сжатом виде и в виде разнообразных структур. Для студентов специальности 090302 – «Информационная безопасность телекоммуникационных систем». Может быть полезно студентам других инфокоммуникационных и радиотехнических специальностей, аспирантам и специалистам. ББК 32.811 Адрес издательства в Интернет www.techbook.ru Белов Виктор Матвеевич, Новиков Сергей Николаевич, Солонская Оксана Игоревна Теория информации. Курс лекций. Учебное пособие для вузов Обложка художника В. Г. Ситникова Подписано в печать 19.02.2012. Формат 60×88/16. Уч. изд. л. 9,14. Тираж 500 экз. (1-й завод 100 экз.) ISBN 978-5-9912-0237-4 © В. М. Белов, С. Н. Новиков, О. И. Солонская, 2012 © Издательство «Горячая линия–Телеком», 2012

Стр.2

Содержание Предисловие . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1. Введение в теорию информации . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.1. Краткая истори÷еская справка о развитии систеì переäа÷и инфорìаöии (систеì связи) и теории инфорìаöии (теории связи) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.1.1. Краткая история развития систеì связи . . . . . . . . . . . . . 8 1.1.2. О понятии «инфорìаöия». Краткая история развития теории инфорìаöии . . . . . . . . . . . . . . . . . . . . . . . . .10 1.1.2.1. О понятии «инфорìаöия». . . . . . . . . . . . . . . . . . . .10 1.1.2.2. Краткая истори÷еская справка о развитии теории инфорìаöии. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .11 1.2. Инфорìаöионные ìетрики . . . . . . . . . . . . . . . . . . . . . . . . . .13 1.2.1. Структурные ìеры инфорìаöии. . . . . . . . . . . . . . . . . . .13 1.2.1.1. Геоìетри÷еская ìера . . . . . . . . . . . . . . . . . . . . . . .13 1.2.1.2. Коìбинаторная ìера . . . . . . . . . . . . . . . . . . . . . . .14 1.2.1.3. Аääитивная ìера . . . . . . . . . . . . . . . . . . . . . . . . . .16 1.2.2. Статисти÷еская ìера . . . . . . . . . . . . . . . . . . . . . . . . . . .16 1.2.3. Сеìанти÷еская ìера. . . . . . . . . . . . . . . . . . . . . . . . . . . .17 2. Энтропия вероятностной схемы . . . . . . . . . . . . . . . . . . . . . . . . . . .18 2.1. Энтропия, как ìера степени неопреäеëенности физи÷еской систеìы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .18 2.2. Еäиниöы изìерения энтропии. . . . . . . . . . . . . . . . . . . . . . . .20 2.3. Основные свойства энтропии простой физи÷еской систеìы .21 2.4. Энтропия и ìатеìати÷еское ожиäание. . . . . . . . . . . . . . . . . .23 2.5. Усëовная энтропия и энтропия объеäинения. . . . . . . . . . . . .24 Контроëüные вопросы к ãëаваì 1 и 2 . . . . . . . . . . . . . . . . . . . . . . . .29 3. Основные теоремы Шеннона о характеризации источников информации . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .31 3.1. Коëи÷ество инфорìаöии в äискретноì сообщении. Дискретные исто÷ники сообщений без паìяти и с паìятüþ. Избыто÷ностü äискретноãо исто÷ника сообщений . . . . . . . . . . . .31 3.2. Первая теореìа Шеннона . . . . . . . . . . . . . . . . . . . . . . . . . . .35 3.2.1. Пряìая и обратная теореìы Шеннона äëя канаëа связи без øуìа. Первый способ äоказатеëüства пряìой теореìы Шеннона . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .35 3.2.2. Второй способ äоказатеëüства пряìой теореìы Шеннона äëя канаëа связи без øуìа. Метоä Фано. Оптиìаëüные коäы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .40 3.2.3. Практи÷еское приìенение первой теореìы Шеннона . .44

Стр.3

4 3.3. Вторая теореìа Шеннона и ее сëеäствия . . . . . . . . . . . . . . . .45 3.3.1. Пряìая теореìа Шеннона äëя äискретноãо постоянноãо канаëа с øуìоì . . . . . . . . . . . . . . . . . . . . . . . . .45 3.3.2. Обратная теореìа Шеннона äëя äискретноãо постоянноãо канаëа с øуìоì . . . . . . . . . . . . . . . . . . . . . . . . .47 3.3.3. Сëеäствие из второй теореìы Шеннона. . . . . . . . . . . . .49 3.4. Статисти÷еский анаëиз сëу÷айных посëеäоватеëüностей. Энтропийные и инфорìаöионные характеристики сëу÷айных посëеäоватеëüностей. . . . . . . . . . . . . . . . . . . . . . . . . .52 Контроëüные вопросы к ãëаве 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . .53 4. Статистические модели каналов связи . . . . . . . . . . . . . . . . . . . . . .55 4.1. Матеìати÷еские ìоäеëи канаëов связи . . . . . . . . . . . . . . . . .55 4.1.1. Схеìа переäа÷и инфорìаöии. Кëассификаöия канаëов связи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .55 4.1.2. Непрерывные канаëы связи . . . . . . . . . . . . . . . . . . . . . .58 4.1.3. Дискретные канаëы связи . . . . . . . . . . . . . . . . . . . . . . .60 4.2. Вëияние øуìов на пропускнуþ способностü äискретноãо канаëа связи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .62 4.3. Пропускная способностü систеì переäа÷и инфорìаöии . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .63 5. Оптимальное кодирование . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .67 5.1. Префиксные коäы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .67 5.2. Неравенство Крафта . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .75 5.3. Инфорìаöионная избыто÷ностü. Граниöы äëя среäней äëины коäов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .79 Контроëüные вопросы к ãëаваì 4 и 5 . . . . . . . . . . . . . . . . . . . . . . . .82 6. Обнаружение и исправление ошибок в сообщениях. Понятие об идее коррекции ошибок. . . . . . . . . . . . . . . . . . . . . . . . . .84 7. Линейное кодирование. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .88 7.1. Свойства поìехозащищаþщих коäов. . . . . . . . . . . . . . . . . . .88 7.1.1. Поìехоустой÷ивые коäы и их приìенение. . . . . . . . . . .88 7.1.2. Основные параìетры поìехоустой÷ивых коäов . . . . . . .89 7.1.3. Грани÷ные соотноøения ìежäу параìетраìи поìехоустой÷ивых коäов. . . . . . . . . . . . . . . . . . . . . . . . . . . . .89 7.1.4. Кëассификаöия поìехоустой÷ивых коäов. . . . . . . . . . . .90 7.2. Линейные коäы. Параìетры и свойства. . . . . . . . . . . . . . . . .92 7.3. Коä Хэììинãа . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .98 Контроëüные вопросы к ãëаваì 6 и 7 . . . . . . . . . . . . . . . . . . . . . . .100 8. Циклические коды. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .101 8.1. Опреäеëение и свойства äвои÷ных öикëи÷еских коäов . . . . 101 8.2. Систеìати÷еские öикëи÷еские коäы . . . . . . . . . . . . . . . . . .105 8.3. Обнаружение пакетов оøибок . . . . . . . . . . . . . . . . . . . . . . .108

Стр.4

5 9. Построение и декодирование конкретных циклических кодов . . . .110 9.1. Коäы, исправëяþщие оäино÷нуþ оøибку, коäовое расстояние d0 = 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . .110 9.2. Коäы, обнаруживаþщие трехкратные оøибки, d0 = 4 . . . . .112 9.3. Цикëи÷еские коäы, исправëяþщие äве и боëüøее коëи÷ество оøибок, d0 l 5. . . . . . . . . . . . . . . . . . . . . . . . . . . . .113 10. Обнаружение и исправление ошибок при передаче и обработке информации на стандартной аппаратуре. . . . . . . . . . . . . . . . . . . . . .116 11. Сжатие информации . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .121 Контроëüные вопросы к ãëаваì 8, 9, 10, 11. . . . . . . . . . . . . . . . . . .126 12. Структурное кодирование. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .128 Контроëüные вопросы к ãëаве 12 . . . . . . . . . . . . . . . . . . . . . . . . . .139 Примерные вопросы к экзамену по дисциплине «Теория информации» . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .140 Библиография . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .142

Стр.5

Предисловие Дисöипëина «Теория инфорìаöии» опреäеëена в ãосуäарственноì образоватеëüноì станäарте высøеãо профессионаëüноãо образования спеöиаëüности 090302 «Инфорìаöионная безопасностü теëекоììуникаöионных систеì» как феäераëüный коìпонент общих ìатеìати÷еских и естественнонау÷ных äисöипëин. Теория инфорìаöии тесно связана с äруãиìи äисöипëинаìи, изу÷аеìыìи стуäентаìи. Она преäпоëаãает знания таких äисöипëин как «Матеìати÷еский анаëиз», «Аëãебра», «Теория вероятностей и ìатеìати÷еская статистика», явëяется базой äëя äисöипëин «Теория раäиотехни÷еских сиãнаëов» и «Криптоãрафи÷еские ìетоäы защиты инфорìаöии». Преäëаãаеìое у÷ебное пособие по «Теории инфорìаöии» отве÷ает требованияì боëüøинства разäеëов проãраììы оäноиìенноãо курса, ÷итаеìых стуäентаì, обу÷аþщиìся по спеöиаëüности 090302 «Инфорìаöионная безопасностü теëекоììуникаöионных систеì». Цеëü у÷ебноãо пособия — поìо÷ü освоитü основные поëожения теории инфорìаöии и коäирования, нау÷итü опреäеëятü инфорìаöионные потери в канаëах связи с поìехаìи, строитü оптиìаëüные коäы, обнаруживатü и исправëятü оøибки при разëи÷ных ìетоäах переäа÷и и обработки инфорìаöии, преäставëятü коäы в паìяти ЭВМ в сжатоì виäе и в виäе разнообразных структур. Материаë у÷ебноãо пособия разбит на 12 теì. В кажäой теìе преäëожен необхоäиìый ìиниìуì теорети÷еских свеäений. Авторы выражаþт ãëубокуþ бëаãоäарностü коëëеãаì, работаþщиì в обëасти защиты инфорìаöии, А. Б. Архиповой, Е. Н. Пивкину, О. В. Воробüевой за неоöениìуþ поìощü в поäãотовке ìатериаëов äëя äанноãо пособия.

Стр.6