МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ
Филиал федерального государственного бюджетного образовательного учреждения
высшего профессионального образования
«Астраханский государственный университет»
в г. Знаменске Астраханской области
«УТВЕРЖДАЮ»
Директор филиала ФГБОУ ВПО АГУ
в г. Знаменске Астраханской области
__________________
Дисциплина блока общие математические и естественно-научные дисциплины
Компонент дисциплины и курсы по выбору
Кафедра математики и информатики
Теория информации и кодирования
учебно-методический комплекс
для специальности
230201.65 Информационные системы и технологии (Знаменск)
3 курс
Автор - составитель:
e-mail:
*****@***ru
Теория информации и кодирования
Учебно-методический комплекс
Автор составитель
д. т.н.,профессор,
Ответственный редактор
Зав. кафедрой математики и информатики,
к. т.н., профессор,
Учебно-методический комплекс обсужден
на заседании кафедры математики и информатики
Протокол № 1 от 01.01.2001 г.
РАБОЧАЯ УЧЕБНАЯ ПРОГРАММА ДИСЦИПЛИНЫ
Данный курс является дисциплиной по выбору специальности «Информационные системы и технологии».
Предмет курса – основы теории информации и кодирования и практическая реализация основных алгоритмов обработки информации.
К основным задачам курса относится изучение:
теоретических основ кодирования и хранения информации, способов передачи информации по каналам связи, алгоритмов кодирования информации источника и помехоустойчивого кодирования, простейших математических моделей для описания процессов передачи информации.
В результате изучения дисциплины студенты должны знать:
- теоретические основы кодирования и хранения информации;
- способы передачи информации по каналам связи;
- основные алгоритмы обработки информации;
- простейшие математические модели для описания процессов передачи информации
Студенты должны уметь применять полученные знания в научно-исследовательской и практической работе.
Курс связан с дисциплинами «Теория вероятностей», «Линейная алгебра», «Криптография», «Программное обеспечение информационной безопасности» и др.
Изучение курса завершается итоговой оценкой в соответствии с суммой набранных баллов по системе текущего контроля студентов. В течение семестра каждый студент выполняет лабораторные работы и контрольные работы на семинарских занятиях. Студенты, не набравшие необходимого количества баллов по рейтинговой системе контроля знаний, сдают тест по дисциплине.
Планы семинарских и практических занятий составлены в соответствии с программой курса и Госстандартом данной специальности.
Каждая тема включает в себя основные теоретические и практические материалы, необходимые для освоения дисциплины.
РАСПРЕДЕЛЕНИЕ ЧАСОВ
ПО ТЕМАМ И ВИДАМ УЧЕБНЫХ ЗАНЯТИЙ
Наименование тем | Количество аудиторных часов | |||
Всего | в том числе по видам учебных занятий | |||
Лекции | Практические, семинарские занятия | Лабораторные занятия | ||
1 | 2 | 3 | 4 | 5 |
Тема 1. Основные понятия и определения теории информации: информация, канал связи, линия связи, система передачи информации. Количественная оценка информации. Схема цифровой системы связи. Тема 2. Способы представления информации. Математические основы теории информации и кодирования. Примеры простейших кодов. Тема 3. Алфавит источника сообщений. Код и кодирование сообщений. Кодовое слово. Префиксные коды. Кодовое дерево. Дешифрация сообщений с использованием кодового дерева. Экономичность кодирования. Средняя длина кодового слова. Теорема Шеннона о средней длине кодовых слов. Теорема Крафта о существовании мгновенных кодов. Методы оптимального кодирования Шеннона-Фано и Хафмена. Программы-архиваторы, как пример оптимального кодирования информации. Тема 4. Энтропия и ее свойства. Условная энтропия. Энтропия объединения (взаимная энтропия). Информационные характеристики канала связи. Канальные матрицы источника и приемника сообщений. Количество информации при передаче сигналов по каналу связи без помех и с помехами. Свойства количества информации. Тема 5. Избыточность источника сообщений. Оптимальный источник. Поток информации источника сообщений. Скорость передачи информации. Пропускная способность канала связи. Пропускная способность двоичного симметричного канала связи с помехами. Основная теорема Шеннона. Тема 6. Передача информации по каналам связи. Методы повышения надежности передачи информации. Обнаружение и исправление ошибок кодирования. Избыточность. Помехоустойчивое кодирование. Понятие синдрома. Тема 7. Линейные блочные коды. Циклические коды. Коды Рида-Соломона. | 4 4 4 6 5 8 2 | 2 2 2 4 2 4 1 | 2 2 2 2 3 4 1 | |
Итого аудиторных часов | 34 | 17 | 17 | |
Количество часов самостоятельной работы студентов | 25 | |||
Всего часов | 59 |
СОДЕРЖАНИЕ КУРСА
Теоретическая часть.
Тема 1.
Основные понятия и определения теории информации: информация, канал связи, линия связи, система передачи информации. Количественная оценка информации. Схема цифровой системы связи.
Тема 2.
Способы представления информации. Математические основы теории информации и кодирования. Примеры простейших кодов.
Тема 3.
Алфавит источника сообщений. Код и кодирование сообщений. Кодовое слово. Префиксные коды. Кодовое дерево. Дешифрация сообщений с использованием кодового дерева. Экономичность кодирования. Средняя длина кодового слова. Теорема Шеннона о средней длине кодовых слов. Теорема Крафта о существовании мгновенных кодов. Методы оптимального кодирования Шеннона-Фано и Хафмена. Программы-архиваторы, как пример оптимального кодирования информации.
Тема 4.
Энтропия и ее свойства. Условная энтропия. Энтропия объединения (взаимная энтропия). Информационные характеристики канала связи. Канальные матрицы источника и приемника сообщений. Количество информации при передаче сигналов по каналу связи без помех и с помехами. Свойства количества информации.
Тема 5
Избыточность источника сообщений. Оптимальный источник. Поток информации источника сообщений. Скорость передачи информации. Пропускная способность канала связи. Пропускная способность двоичного симметричного канала связи с помехами. Основная теорема Шеннона.
Тема 6
Передача информации по каналам связи. Методы повышения надежности передачи информации. Обнаружение и исправление ошибок кодирования. Избыточность. Помехоустойчивое кодирование. Понятие синдрома.
Тема 7
Линейные блочные коды. Циклические коды. Коды Рида-Соломона.
Практическая часть (семинарские занятия)
Тема 1
Простейшие коды. Проверка на четность. Обнаружение пакетов ошибок. Конечный автомат.
Тема 2
Взвешенные коды. Контрольная сумма.
Тема 3
Экономное кодирование. Коды Фано. Выигрыш по сравнению с равномерными кодами.
Тема 4
Мгновенные коды. Неравенство Крафта и метод Шеннона при построении мгновенных кодов.
Тема 5
Оптимальное кодирование. Коды Хаффмена. Архивация данных.
Тема 6
Обнаружение и исправление ошибок. Коды Хемминга.
Тема 7
Энтропия и ее свойства.
Практическая часть (лабораторные работы)
Лабораторные занятия проводятся в компьютерных классах филиала АГУ на базе ПК IBM PC.
Тема 1
Шифрование данных.
Тема 2
Взвешенные коды.
Тема 3
Архивация данных
Тема 4
Методы обнаружения и исправления ошибок.
Тема 5
Модель канала передачи данных.
Тема 6
Исследование энтропии.
РЕКОМЕНДУЕМАЯ ЛИТЕРАТУРА
1. , , и др. Теория информации и кодирование: Учебное пособие для вузов Ростов: Феникс 2002г., - 288с.
2. Вводный курс теории информации и кодирования. - М.: Техносфера, 20с.
3. Липкин радиотехника. Теория информации и кодирования.-М.:Вуз. кн., 2002.-214 с.:ил.
4. , Кишенский информации и кодирования: Учеб. пособие. - М.: МГТУ ГА, 19с.
5. Хохлов, теории информации : доп. УМО по образованию в области информационной безопасности в качестве учеб. пособ. для студентов вузов... "Комплексное обеспечение информационной безопасности автоматизированных систем". - М. : Академия, 20с. - (Высшее профессиональное образование). - ISBN 4576-4 : 123-42
6. Панин, теории информации : Рек. УМО в обл. "Ядерные физика и технологии" в качестве учеб. пособ. для студ. вузов, ... по спец. № 000 "Электроника и автоматика физических установок". - 2 изд. ; испр. и доп. - М. : БИНОМ. Лаборатория знаний, 20с.
КАЛЕНДАРНЫЙ План ЛЕКЦИОННЫХ ЗАНЯТИЙ
Порядковый номер | Содержание занятия | Количество аудиторных часов | Объем материала | Форма контроля | Задания для самостоятельной работы студентов |
1. | Основные понятия и определения теории информации: | 2 часа | www. ido. ***** Модуль1 | ||
2. | Способы представления информации. | 2 часа | www. ido. ***** Модуль2 | ||
3. | Алфавит источника сообщений. Код и кодирование сообщений. | 2 часа | www. ido. ***** Модуль3 | ||
4. | Энтропия и ее свойства. Условная энтропия. Энтропия объединения (взаимная энтропия). | 2 часа | www. ido. ***** Модуль4 | ||
5. | Информационные характеристики канала связи. Канальные матрицы источника и приемника сообщений. | 2 часа | www. ido. ***** Модуль4 | ||
6. | Поток информации источника сообщений. Скорость передачи информации. Пропускная способность канала связи. | 2 часа | www. ido. ***** Модуль5 | ||
7. | Передача информации по каналам связи. Методы повышения надежности передачи информации. | 2 часа | www. ido. ***** Модуль6 | ||
8. | Избыточность. Помехоустойчивое кодирование. Понятие синдрома. | 2 часа | www. ido. ***** Модуль7 | ||
9. | Линейные блочные коды. Циклические коды. Коды Рида-Соломона. | 1 час | www. ido. ***** Модуль8 |
КАЛЕНДАРНЫЙ План ЛАБОРАТОРНЫХ ЗАНЯТИЙ
Порядковый номер | Содержание занятия | Количество аудиторных часов | Объем материала | Форма контроля | Задания для самостоятельной работы студентов |
1 | Шифрование данных | 2 часа | www. ido. ***** Модуль1 | Отчет по лабораторной работе | |
2 | Взвешенные коды. | 2 часа | www. ido. ***** Модуль2 | Отчет по лабораторной работе | |
3 | Архивация данных | 4 часа | www. ido. ***** Модули3,4 | Отчет по лабораторной работе | |
4 | Методы обнаружения и исправления ошибок. | 4 часа | www. ido. ***** Модуль5 | Отчет по лабораторной работе | |
5 | Модель канала передачи данных. | 2 часа | www. ido. ***** Модуль6 | Отчет по лабораторной работе | |
6 | Исследование энтропии. | 3 часа | www. ido. ***** Модуль6 | Отчет по лабораторной работе |
ПРОБНЫЕ ТЕСТЫ (ПРИМЕРЫ ТЕСТОВЫХ ВОПРОСОВ)
 |
1. На рисунке изображена схема системы передачи сигналов. Определите соответствие:
1) источник
2) кодер
3) канал
4) декодер
5) приемник
6) шум
2. Последовательностью цифр может быть представлена информация:
Дискретная
Непрерывная
Комбинированная
Линейная
Нелинейная
3. К неравномерным кодам относятся:
Фано
Хаффмена
Хемминга
БЧХ
4. Из перечисленных ниже кодов однозначно декодируемыми являются:
{0, 10, 110, 111}
{ 0, 01, 011, 111}
{0, 01, 001, 111}
{1, 01, 011, 111}
5. Дискретная случайная величина X, задана распределением:
Х | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
Р | 0,1 | 0,2 | 0,1 | 0,05 | 0,1 | 0,05 | 0,3 | 0,1 |
Н(Х) приблизительно равна:
2,75 бит
0,826 бит
1,25 бит
6. Значения дискретных случайных величин Х1 и Х2 определяются подбрасыванием двух идеальных монет, а дискретная случайная величина Y равна сумме количества "гербов", выпавших при подбрасывании этих монет. Сколько информации об Х1 содержится в Y?
0,5 бит/символ
1 бит/символ
2 бит/символ
ПРИМЕРЫ ЗАДАЧ:
1. В большинстве научных книг и учебников в настоящее время ставится номер ISBN (International Standart Book Number — номер книги по международному стандарту) Этот номер обычно состоит из 10 цифр и является кодовым словом, которое издательство присваивает своим книгам. Типичным является номер 0—13—212571—4, хотя черточки могут стоять в разных местах (они вообще несущественны). Цифра 0 означает Соединенные Штаты и некоторые другие англоязычные страны Число 13 обозначает издательство Prentice-Hall. Следующие 6 цифр составляют номер книги, присваиваемый ей издательством, а последняя цифра является взвешенной суммой. Арифметика по модулю 10 непригодна, поскольку 10 — составное число. Поэтому используется проверочная сумма по модулю 11, и если проверочная цифра равна 10, выбирается символ X. Проверьте:
a) ISBN 0——6
b) ISBN 0——4.
2. Выясните, обладают ли свойством однозначной декодируемости следующие коды:{110, 11,100, 00, 10};{100, 001, 101, 1101, 11011}.
3. Двоичный (8,4)-код задан порождающей матрицей: 
Найти его проверочную матрицу и кодовое расстояние.
4. Для (16,5)-кода Рида — Маллера первого порядка исправить или обнаружить ошибки в слове:
5. Закодировать двоичным кодом Фано следующее множество сообщений: P1=P2=l/4; Р3=Р4=Р5=1/8; P6=P7=1/18; . Найти среднюю длину кода. Выяснить, каков выигрыш по сравнению с равномерным кодированием.
6. Используя метод Шеннона, найти префиксный код с указанными ниже длинами слов: L1=L2=2; L3=L4=3; L5=L6=L7=4;
7. Построить код Хаффмена для p1=27/40, р2=9/40, р3=3/40 , р4=1/40.
ПЕРЕЧЕНЬ ВОПРОСОВ К ЗАЧЕТУ:
1. Предмет теории информации и кодирования. Объект исследования данной науки. Место теории информации и кодирования в системе других наук.
2. Математические основы теории информации и кодирования. Взаимосвязь теории кодирования и теории информации.
3. Модель системы передачи сигналов.
4. Представление информации в ЭВМ. Примеры простейших кодов.
5. Алфавит источника сообщений. Код и кодирование сообщений. Кодовое слово.
6. Экономичность кодирования. Средняя длина кодового слова. Теорема Шеннона о средней длине кодовых слов.
7. Теорема Крафта о существовании мгновенных кодов. Методы оптимального кодирования Шеннона-Фано и Хафмена. Префиксные коды. Кодовое дерево. Дешифрация сообщений с использованием кодового дерева.
8. Программы-архиваторы, как пример оптимального кодирования информации.
9. Передача информации по каналам связи. Методы повышения надежности передачи информации.
10. Обнаружение и исправление ошибок кодирования. Избыточность.
11. Помехоустойчивое кодирование. Понятие синдрома.
12. Обнаружение и исправление ошибок. Алгебраический и геометрический подход.
13. Использование математического аппарата линейной алгебры в теории помехоустойчивого кодирования.
14. Коды с исправлением ошибок.
15. Количественная оценка информации. Энтропия и ее свойства. Условная энтропия. Энтропия объединения (взаимная энтропия).
16. Информационные характеристики канала связи. Канальные матрицы источника и приемника сообщений.
17. Количество информации при передаче сигналов по каналу связи без помех и с помехами. Свойства количества информации.
18. Избыточность источника сообщений. Оптимальный источник. Поток информации источника сообщений.
19. Скорость передачи информации. Пропускная способность канала связи. Пропускная способность двоичного симметричного канала связи с помехами.
20. Основная теорема Шеннона.
МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ ПО ИЗУЧЕНИЮ
ДИСЦИПЛИНЫ И ОРГАНИЗАЦИИ САМОСТОЯТЕЛЬНОЙ
РАБОТЫ СТУДЕНТОВ
Самостоятельная работа студентов – совокупность всей самостоятельной деятельности обучаемых как в отсутствие преподавателя, так и в контакте с ним, в учебной аудитории и за ее пределами (в том числе и в ходе учебных занятий). При изучении данной дисциплины целесообразно использовать следующие формы учебной работы:
- обзорные лекции;
- самостоятельная работа студентов с учебной и методической литературой;
- выполнение контрольных заданий (упражнений, тестов, задач).
Планируя время на изучение дисциплины, студентам можно руководствоваться предложенным учебно-методическим планом, где указано распределение времени, отведенного на изучение дисциплины, между лекциями, семинарами и самостоятельной подготовкой.
В ходе самостоятельной работы студентам необходимо разбираться с изучаемым вопросом, используя учебники (смотри список основной литературы) и материалы лекций. Для подготовки докладов к семинарским занятиям, или для углубления знаний по той или иной теме, целесообразно воспользоваться дополнительной литературой (смотри список дополнительной литературы). Учебники и другую литературу можно взять в библиотеке.
При подготовке докладов, сообщений можно воспользоваться Интернет-ресурсами. При этом следует обратить внимание на то, чтобы используемая информация была актуальна и достоверна.
При подготовке докладов следует выписывать полные ссылки из тех источников, которыми воспользовались. Это позволит преподавателю проверить качество выполненной работы.
Для проверки знаний можно использовать тестовые материалы или вопросы для самостоятельной подготовки, предложенные в УМК.
Для контроля усвоения данной дисциплины учебным планом предусмотрен зачет. Вопросы к зачету приведены в разделе «Контрольные вопросы по дисциплине в целом».
НЕСКОЛЬКО ПРАКТИЧЕСКИХ СОВЕТОВ:
Не старайтесь записать дословно все, что говорит преподаватель — это невозможно, да и не нужно. Если вы будете к этому стремиться, в ваших записях неизбежны недописанные' предложения, пропуски, а значит — нарушения логики изложения материала, которые сделают конспект бесполезным. Учитесь формулировать мысли кратко и своими словами, записывая только самое существенное.
Учитесь «на слух» отделять главное от второстепенного. Но это не означает, что записывать нужно только основные положения и определения, которые без примеров и иллюстраций могут впоследствии, при чтении конспектов, оказаться непонятными. Поэтому факты, которые приводит лектор, также лучше отмечать; иногда для этого бывает достаточно нескольких ключевых слов.
Записи должны быть сжатыми, логично связанными, представлять собой нечто вроде развернутого плана лекции.
Если в лекции предлагаются схемы, таблицы, чертежи, обязательно полностью заносите их в тетрадь, выполняя аккуратно и внимательно.
По ходу лекции преподаватель обычно отмечает те или иные мысли, положения, поэтому сразу делайте соответствующие смысловые выделения в ваших записях. Для этого можно использовать не только разные виды подчеркиваний (прямая, волнистая линии, пунктир и т. п.), разноцветные выделения, но и различные значки, например:! — «важно», ? — «проверить, уточнить», NB (nota bene) — «обратить внимание» и др.
Оставляйте в тетради поля, которые можно использовать в дальнейшем для уточняющих записей, комментариев, дополнений и т. п.
Используйте красную строку для выделения смысловых частей в записях.
Постарайтесь выработать свою собственную систему сокращения часто встречающихся слов или их замены определенными знаками. Это даст вам возможность меньше писать, больше слушать и думать.
Сразу после лекции постарайтесь просмотреть записи и по свежим следам восстановить пропущенное, дописать недописанное, завершить выделение существенных моментов.
ИННОВАЦИОННОЕ ОБУЧЕНИЕ.
Все принципы и формы работы, предусматриваемые инновационным методом, направлены на повышение эффективности обучения. Ключевые идеи, позволившие решить эту задачу, состоят в следующем:
1. Обучение оказывается эффективнее, когда участники решают свои реальные практические проблемы и для этого осваивают новые методы и средства работы. Обучение, таким образом, выступает в единстве с творческим решением проблем;
2. Объединение обучения и исследования, представление обучения как вида исследовательской работы создает дополнительную заинтересованность и повышает качество адаптации к своей картинке мира новых идей и нового материала;
3. Эффективное обучение - не усвоение некоторого комплекса сведений или приобретение новых навыков. Эффективное обучение - всегда развитие человека, изменение его сознания, взглядов, установок, ценностей, норм. Кроме того, интересна идея о том, что истинное знание - это способность действовать в соответствии с этим знанием;
4. Эффективность обучения резко повышается в условиях интенсивного погружения, отвлечения от текущих дел и при глубокой концентрации на материале. В таких условиях начинают включаться внутренние резервы личности человека, открываются нереализованные и новые способности;
5. Одна из ключевых идей, плодотворно работающих в развивающем обучении - идея о том, что все люди талантливы с детства. Способности никуда не уходят, они всегда остаются с человеком, - экономические, культурные и бытовые условия жизни могут лишь воспрепятствовать их проявлению и развитию. ?Презумпция талантливости¦ каждого творит чудеса - люди обнаруживают в себе способности, о которых даже не подозревали;
6. Все обучение строится не от простого к сложному, а от сложного к простому. Действительно, приходя в этот мир, ребенок встречает его уже существующим, во всей сложности и противоречии. И лишь с годами, постепенно он учится вычленять в мире простые составляющие. То же происходит при встрече с новой профессией, организацией, с новым языком, новой культурой. Техника, помогающая осмыслить сверхсложную информацию и свести ее к простым составляющим, называется? сведением¦. Резервные возможности сознания и психики человека проявляются и активизируются в ходе усвоения и переработки сверхбольших объемов информации;
7. Обучению и развитию участников способствует и интенсивное развитие группы, которое активизирует каждого участника за счет резкого ускорения проходимых группой этапов развития. За несколько дней семинара группы проходят путь, для которого в обычных условиях могут понадобиться месяцы, а то и годы. Групповой фактор - один из наиболее мощных в повышении эффективности обучения и развития человека и организации;
8. Последняя базовая идея, положенная в основу инновационного обучения, - отказ от последовательности - ?от знаний - к практическим действиям¦ и признание последовательности? от действий - к знаниям¦ более продуктивной.
В результате инновационного обучения участники приобретают качество, наиболее важное для успешной деятельности в наше время, - способность гибко, нестандартно и своевременно реагировать на огромное количество изменений, непрерывно обрушивающихся на каждого из нас. Более того, - предвосхищать эти изменения и участвовать в их формировании.
Метод инновационного обучения - это ещё один шаг в решении проблемы эффективности обучения, над которой бьются сотни и тысячи специалистов во всём мире. Кардинальное решение этой проблемы будет означать начало новой цивилизации, поскольку каждый человек сможет за короткое время овладевать огромным культурным багажом, обучившись самообучению и саморазвитию.
