Учебно-методический комплекс по дисциплине теория информации для специальности (направления) 210400

Федеральное агентство по образованию

Государственное образовательное учреждение высшего профессионального образования

Владимирский государственный университет

Кафедра радиотехники и радиосистем

УТВЕРЖДАЮ

Проректор по УР

_________________ В.А.Немонтов В.А.

«____»____________________
УЧЕБНО-МЕТОДИЧЕСКИЙ КОМПЛЕКС

По дисциплине ТЕОРИЯ ИНФОРМАЦИИ

для специальности (направления) 210400

«Радиотехника»

вид обучения очное

Владимир 2011 г.


Учебно-методический комплекс по дисциплине “Теория информации” составлен в соответствии с требованиями Государственного образовательного стандарта высшего профессионального образования по специальности: 210302 Радиотехника,

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

Федеральное агентство по образованию

Государственное образовательное учреждение высшего профессионального образования

Владимирский государственный университет

Кафедра радиотехники и радиосистем

УТВЕРЖДАЮ

Проректор по УР

_________________ В.А.Немонтов В.А.

«____»____________________

Рабочая программа

По дисциплине ТЕОРИЯ ИНФОРМАЦИИ

для специальности (направления) 210400

«Радиотехника»

вид обучения дистанционное

Учебный план курса

Вид занятий	Количество часов
	Всего	Распределение по семестрам
		8
Лекции	2	2
Практические	17	17
Курсовые проекты (работы)
СРС	44	44
Экзамен		экзамен
Всего по ГОС	63	63

Владимир 2011 г.
1. ЦЕЛИ И ЗАДАЧИ ДИСЦИПЛИНЫ
Целью преподавания дисциплины является изучение студентами специальностей 210400 (Радиотехника) основных положений теории информации. Эффективное и надежное функционирование информационных систем невозможно без знания основных теоретических принципов получения, преобразования, передачи, хранения и представления информации. Изучение этих принципов и составляет основное содержание дисциплины «Теория информации». Теория информации исследует общие закономерности информационных процессов, позволяет оценить качество функционирования информационных систем. Данная дисциплина имеет тесную связь со следующими курсами: «информационные технологии», «Высшая математика».
2. ТРЕБОВАНИЯ К УРОВНЮ ОСВОЕНИЯ ДИСЦИПЛИНЫ
В результате изучения дисциплины специалист должен

• 
  иметь представление об основных подходах к измерению информации и об основных принципах преобразования и передачи информации;
  

• 
  знать и уметь использовать основные теоретические принципы теории информации и кодирования для обеспечения эффективной и надежной передачи информации;
  

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

3. СОДЕРЖАНИЕ ДИСЦИПЛИНЫ

3.1. РАЗДЕЛЫ ДИСЦИПЛИНЫ И ВИДЫ ЗАНЯТИЙ

№	Раздел дисциплины	Лекции, час.	Практ. занятия, час.
1	Измерение информации	1	2
2	Модели сигналов		4
3	Преобразование сигналов		2
4	Источники сообщений		2
5	Кодирование информации	1	4
6	Передача информации		3

3.2. СОДЕРЖАНИЕ РАЗДЕЛОВ ДИСЦИПЛИНЫ


Раздел 1. Измерение информации

Понятие информации. Различные подходы к измерению информации и их применение. Структурные меры информации. Статистический подход. Энтропия и ее свойства. [1 – 3, 5, 6]
Раздел 2. Модели сигналов

Понятие сигнала и его модели. Различные формы представления детерминированных сигналов. [1 – 3, 5]
*Раздел 3. Преобразование сигналов

Дискретизация сигналов. Основные методы. Ошибки при восстановлении сигналов. Теорема В.А. Котельникова и ее применение. Квантование сигналов. Оценка ошибок. Различные виды модуляции сигналов.[1, 3, 5]
Раздел 4. Источники сообщений

Различные модели источников сообщений: дискретные, непрерывные. Однородный марковский источник. Информационные характеристики источников: энтропия, избыточность.[1 – 3, 5]

Раздел 5. Кодирование информации

Основные задачи кодирования. Эффективное и помехоустойчивое кодирование. Основные теоремы Шеннона о кодировании. Эффективные коды: код Шеннона-Фано, код Хаффмана, и их характеристики. Методики построения помехоустойчивых кодов: код с проверкой четности, код с тройным повторением, код Хэмминга.[1 – 4, 5]
*Раздел 6. Передача информации

Различные модели каналов связи: дискретные, непрерывные. Информационные характеристики каналов: скорость передачи информации, пропускная способность. [1 – 3, 5]

3.3. ПРАКТИЧЕСКИЕ ЗАНЯТИЯ

№	№ раздела дисциплины	Наименование практических занятий
1	1	Меры информации
2	2	Формы представления сигналов
3	4	Информационные характеристики источников сообщений
4	5	Эффективные коды
5	5	Помехоустойчивые коды
6	6	Информационные характеристики каналов связи

4. САМОСТОЯТЕЛЬНАЯ РАБОТА

Студент специальности РТ должен выполнить контрольную работу, состоящую из 7 задач по разделам: измерение информации, источники сообщений, кодирование информации, передача информации.
ЗАДАНИЕ НА КОНТРОЛЬНУЮ РАБОТУ
1 – 10. Определить количество информации (по Хартли), содержащееся в системе, информационная емкость которой характеризуется десятичным числом Q. Закодировать это число по двоичной системе счисления.

№	1	2	3	4	5	6	7	8	9	10
Q	500	1000	750	1250	250	1500	650	900	1100	1600

11 – 20. Определить среднее количество информации, содержащееся в сообщении, используемом три независимых символа S₁, S₂, S₃. Известны вероятности появления символов p(S₁)=p₁, p(S₂)=p₂, p(S₃)=p₃. Оценить избыточность сообщения.

№	11	12	13	14	15	16	17	18	19	20
p1	0,1	0,2	0,3	0,1	0,15	0,1	0,2	0,2	0,05	0,15
p2	0,15	0,1	0,15	0,3	0,2	0,4	0,25	0,3	0,15	0,25
p3	0,75	0,7	0,55	0,6	0,65	0,5	0,55	0,5	0,8	0,6

21 – 30. В условии предыдущей задачи учесть зависимость между символами, которая задана матрицей условных вероятностей P(S_j / S_i).
21. 22. 23.
24. 25. 26.


27. 28. 29.
30.
31 – 40. Провести кодирование по одной и блоками по две буквы, используя метод Шеннона – Фано. Сравнить эффективности кодов. Данные взять из задач №11 –20.
41 – 50. Алфавит передаваемых сообщений состоит из независимых букв S_i. Вероятности появления каждой буквы в сообщении заданы. Определить и сравнить эффективность кодирования сообщений методом Хаффмана при побуквенном кодировании и при кодировании блоками по две буквы.

№	p(Si)	№	p(Si)
41	(0,6;0,2;0,08;0,12)	46	(0,7;0,2;0,06;0,04)
42	(0,7;0,1;0,07;0,13)	47	(0,6;0,3;0,08;0,02)
43	(0,8;0,1;0,07;0,03)	48	(0,5;0,2;0,11;0,19)
44	(0,5;0,3;0,04;0,16)	49	(0,5;0,4;0,08;0,02)
45	(0,6;0,2;0,05;0,15)	50	(0,7;0,2;0,06;0,04)

51 – 60. Декодировать полученное сообщение c, если известно, что использовался (7, 4) – код Хэмминга. Провести кодирование кодом с проверкой четности.

№	c	№	c
51	1100011	56	1011011
52	1010011	57	1010101
53	1101101	58	0110111
54	1101001	59	1110101
55	1100111	60	1000101

61 – 70. Определить пропускную способность канала связи, по которому передаются сигналы S_i. Помехи в канале определяются матрицей условных вероятностей P(S_j / S_i). За секунду может быть передано N = 10 сигналов.
61. 62. 63.
64. 65. 66.
67. 68. 69.
70.

6. ИНФОРМАЦИОННО-МЕТОДИЧЕСКОЕ ОБЕСПЕЧЕНИЕ ДИСЦИПЛИНЫ

Основная литература

1. Самсонов Б.В., Плохов Е.М., Филоненков А.И., Кречет Т.В. Теория информации и кодирование. Ростов н/Д.: Феникс, 2002.

2. Вентцель Е.С. Теория вероятностей. М.: Высшая школа, 2002. М.: КНОРУС, 2010.

3. Душин В.К. Теоретические основы информационных процессов и систем. М.: Дашков и К., 2003.

4. Яблонский С.В. Введение в дискретную математику. М.: Высшая школа, 2002.

Дополнительная литература

5. Дмитриев В.И. Прикладная теория информации. М.: Высшая школа, 1989.

6. Пугачев В.С. Теория вероятностей и математическая статистика. М.: Физматлит, 2002.


МЕТОДИЧЕСКИЕ УКАЗАНИЯ ДЛЯ СТУДЕНТОВ
Задачи изучения дисциплины «Теория информации и кодирования» состоят

• 
  в получении количественных оценок информации;
  
• 
  в расчете информационных характеристик основных элементов систем передачи информации;
  
• 
  в построении кодов.
  

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

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

Рассмотрим аддитивную меру (меру Хартли). Из комбинаторики известно, что число сочетаний с повторениями из h элементов по l равно

.

Таким образом, число всех двоичных кодовых комбинаций длины l равно 2^l (h = 2). В качестве меры информации Хартли предложил взять

(бит). (1)

Тогда 1 бит – это количество информации, содержащееся в двоичной кодовой комбинации единичной длины. Количество информации по Хартли эквивалентно количеству двоичных знаков «0» и «1» при кодировании сообщений по двоичной системе счисления.

Пример 1. Рассмотрим систему, информационная емкость которой определяется десятичным числом Q = 121. Определим количество информации, содержащееся в системе, используя меру Хартли (1),

(бит).

Заметим, что округление результата до целого необходимо проводить в сторону увеличения. Полученный результат означает, что при кодировании числа достаточно использовать 7 двоичных знаков (число возможных двоичных кодовых комбинаций равно 2⁷ = 128)

.

Замечание. Разложение по двоичной системе производится для числа на 1 меньше в силу того, что отсчет ведется от нуля, а число комбинаций равно 121.

Для получения двоичного числа можно использовать метод последовательного деления числа на 2. При каждом делении определяется один двоичный знак кодовой комбинации: если деление без остатка – «0», в противном случае – «1». Ниже приведена таблица, иллюстрирующая метод, столбец справа показывает двоичные знаки кодовой комбинации.

120	2								«0»
	60	2							«0»
		30	2						«0
			15	2					«1»
				7	2				«1»
					3	2			«1»
						1	2		«1»
							0

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

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

(2)

Размерность энтропии определяется основанием логарифма: при основании 2

энтропия измеряется в битах.

Определим количество информации, соответствующее i исходу, как

,

тогда энтропию можно определить как среднее количество информации, приходящееся на один исход,

.

Энтропия принимает максимальное значение в случае равновероятных исходов

, (3)

где n – число исходов.

Рассмотрим дискретный источник сообщений X. Пусть x_i – независимые элементы алфавита сообщений, а p(x_i) – их вероятности (i = 1, 2, …, n), тогда среднее количество информации на один элемент алфавита сообщений определяется через энтропию источника по формуле, аналогичной (2)

(4)

Максимальное количество информации соответствует случаю равных вероятностей элементов алфавита и определяется по формуле (3).

Определим абсолютную и относительную избыточность передаваемого сообщения по следующим формулам

, (5)

. (6)

Пример 2. Пусть в сообщении используются два независимых символа x₁ и x₂. Заданы вероятности появления символов р(x₁)=0,3 и р(x₂)=0,7.

Максимальное среднее количество информации на символ сообщения имеет место при равновероятном распределении и равно, согласно формуле (3),

(бит).

Рассчитаем среднее количество информации на символ сообщения при заданных вероятностях по формуле (4)

,

(бит)

Оценим избыточность сообщения по формулам (5) и (6)

(бит),

.

3. Рассмотрим сложный опыт (X, Y), исходы которого обозначим через (x_i, _j). Энтропия вводится аналогичным образом

. (7)

Если составляющие X, Y сложного опыта независимы, то энтропия сложного опыта равна сумме энтропий составляющих

. (8)

В общем случае вводится понятие – условная энтропия H(Y |X)

, (9)

и формула (8) приобретает следующий вид

.

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

(10)

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

Пример 3. Учтем зависимость между символами в примере 2, заданную матрицей условных вероятностей: .

Рассчитаем энтропию источника по формуле (10)



Подставим числовые данные, используя пример 2,



Таким образом, среднее количество информации на символ сообщения равно 0,64 бит, что меньше 0,88 бит, полученных в примере 2. Это вызвано учетом известной зависимости между символами, что естественно уменьшает неопределенность опыта.

4. Рассмотрим некоторые коды, позволяющие сделать передачу информации более эффективной, что достигается путем сжатия сообщения. Начнем с кода Шеннона–Фано. Алгоритм состоит в следующем: буквы исходного алфавита сообщения выписываются в столбец в порядке убывания их вероятностей; производится разбиение на две группы с равной по возможности суммарной вероятностью, всем буквам верхней группы в качестве первого символа кодовой комбинации приписывается «1», а нижней – «0»; затем производятся следующие разбиения до тех пор, пока в каждой подгруппе не останется одна буква (при каждом разбиении появляется новый символ кодовой комбинации по правилам, изложенным выше).

Эффективность кода рассчитывается следующим образом

,

причем в случае двоичного алфавита формула имеет вид

, (11)

где средняя длина кодовой комбинации равна

, (12)

n(z_i) – число символов в кодовой комбинации. Эффективность является безразмерной величиной и всегда меньше либо равна 1, т.е. æ ≤ 1. Чем ближе этот показатель к единице, тем эффективнее код.

Пример 4. Проведем кодирование методом Шеннона–Фэно и рассчитаем характеристики кода. Пусть исходный алфавит состоит из восьми букв и заданы их вероятности. Проведем разбиения по алгоритму Шеннона–Фэно и составим кодовые комбинации.

zi	p(zi)	кодовые комбинации
z1	0,25		1		1
z2	0,20		1		0
z3	0,15		0		1		1
z4	0,10		0		1		0
z5	0,10		0		0		1		1
z6	0,10		0		0		1		0
z7	0,06		0		0		0		1
z8	0,04		0		0		0		0

Рассчитаем энтропию по формуле (4)



Рассчитаем среднюю длину кодовой комбинации по формуле (12)



Эффективность кода, согласно (11), равна



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

Пример 5. Проведем блоковое кодирование по методу Шеннона–Фано. Пусть алфавит состоит из двух независимых букв с заданными вероятностями p(z₁)=0,8 и p(z₂)=0,2.

Рассчитаем энтропию

(бит).

Очевидно, что при кодировании по одной букве l_ср=1 и æ₁=0,72.

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

zi zj	p(zi zj)	код. комб.
z1 z1	0,64	1
z1 z2	0,16	0	1
z2 z1	0,16	0	0	1
z2 z2	0,04	0	0	0

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

p(z_i z_j) = p(z_i)∙p(z_j).

Рассчитаем основные характеристики

l_ср= 0,64∙1+0,16∙2+0,16∙3+0,04∙3 ≈ 1,56;

.

В последней формуле учли, что энтропия увеличится в 2 раза, согласно (8),

.

При кодировании блоков из трех букв эффективность возрастает еще больше.

z1 z1 z1	0,512	1
z1 z1 z2	0,128	0	1	1
z2 z1 z1	0,128	0	1	0
z1 z2 z1	0,128	0	0	1
z1 z2 z2	0,032	0	0	0	1	1
z2 z2 z1	0,032	0	0	0	1	0
z2 z1 z2	0,032	0	0	0	0	1
z2 z2 z2	0,008	0	0	0	0	0

l_ср= 0,512∙1+0,128∙9+0,032∙15+0,008∙5 ≈ 2,184;

.

Таким образом, имеем æ₁ ‹ æ₂ ‹ æ₃ .

Алгоритм кода Хаффмана состоит в следующем. Буквы исходного алфавита выписываются в столбец в порядке убывания их вероятностей. Последние две буквы столбца объединяются в одну – вспомогательную букву, которой приписывается суммарная вероятность. Затем формируется следующий столбец с учетом новой буквы по принципу убывания вероятностей. Процесс повторяется и продолжается до тех пор, пока останется одна буква с вероятностью, равной 1. Кодовые комбинации легко получить, построив кодовое дерево. Вершиной дерева является последняя буква, процесс ветвления проводится с учетом полученной таблицы, двигаясь в обратном направлении. Каждому из двух ребер, участвующих в объединении, приписывается кодовый символ: ребру с большей вероятностью – «1», с меньшей – «0». Двигаясь от вершины дерева до одной из букв алфавита по соответствующим ребрам, получаем ее кодовую комбинацию.

Пример 6. Проведем кодирование по методу Хаффмена. Исходный алфавит состоит из шести букв с заданными вероятностями. Составим таблицу.

zi	p(zi)	Вспомогательные столбцы
z1	0,40	0,40	0,40	0,40	0,60 0,40	1,00
z2	0,25	0,25	0,25	0,35 0,25
z3	0,15	0,15	0,20 0,15
z4	0,10	0,10 0,10
z5	0,06 0,04
z6

Строим кодовое дерево и выписываем кодовые комбинации букв.

z1	z2	z3	z4	z5	z6
0	10	110	1111	11101	11100

Характеристики кода рассчитываются по тем же формулам, что и для кода Шеннона–Фано







Код Хаффмана можно использовать и для кодирования блоков из букв так, как это было рассмотрено выше для кода Шеннона–Фано, что увеличит эффективность передачи информации.

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

Код с проверкой четности позволяет обнаружить однократную ошибку, т. е. ошибку в одном разряде двоичного слова. Алгоритм кодирования состоит в следующем: к передаваемому двоичному слову добавляем в конце один символ («0» или «1») с тем, чтобы сумма всех символов была равна 0. Суммирование проводится по модулю 2 (mod 2)

0  0 = 0,

0  1 = 1,

1  0 = 1,

1  1 = 0.

При декодировании проверяем сумму символов принятого слова. Если она не равна 0, значит, имеем однократную ошибку.

Пример 7. Проведем кодирование сообщения a = 010110 кодом с проверкой четности.

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

0  1  0  1  1  0 = 1.

Следовательно, добавочный символ равен 1 и закодированное сообщение имеет вид

b = 0101101.

Теперь рассмотрим код, позволяющий исправить однократную ошибку. Это – код Хэмминга. Разберем алгоритм кода. При кодировании сообщение разбивается на слова длиной m, к слову добавляется r контрольных символов. Таким образом, закодированное слово имеет длину n = m + r, причем выполнено

2^r ≥ n + 1.

Например, если m = 4, то легко видеть, что

2³ ≥ (4 + 3) + 1 = 8

и таким образом, число контрольных символов r = 3 и длина кодового слова n = 7. В этом случае имеем (4, 7) код Хэмминга. Контрольные символы размещаются в разрядах с номерами, равными степеням 2, т. е. 2⁰ = 1, 2¹ = 2, 2² = 4, и т. д. Информационные символы располагаются по порядку в оставшихся разрядах. Если исходное слово a = a₁ a₂ a₃ a₄, а закодированное – b = b₁b₂b₃b₄b₅b₆b₇, то для определения значений контрольных символов b₁ , b₂, b₄ используем следующую систему

(13)

Пример 8. Закодируем двоичное слово a = 0101 кодом (4, 7) Хэмминга. Учитывая, что b₃ = 0, b₅ = 1, b₆ = 0, b₇ = 1. Для определения контрольных символов используем систему (13)



Следовательно, = 0, = 1, = 0. Таким образом, закодированное слово имеет вид b = 0100101.

Рассмотрим процесс декодирования. Если обозначить искаженное слово через c = c₁c₂c₃c₄c₅c₆c₇. Тогда, используя следующую систему, определяем разряд, в котором произошла ошибка.

(14)

Двоичное число (e₁e₂e₃)₂ определяет номер разряда, в котором произошла ошибка.

Пример 9. Декодируем сообщение c = 0101111, если при кодировании использовался (4, 7) код Хэмминга.

Используя систему (12), определяем разряд, в котором произошла ошибка



Следовательно, ошибка в разряде с номером 2: 010₂ = 2₁₀. Исправляя ошибку и исключая контрольные символы, получаем информационное сообщение a = 0111.

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

, (15)

где есть среднее количество информации, передаваемое по каналу связи одним сигналом. В формуле (15) максимум берется по всем возможным вероятностным распределениям источника сообщений p(x), H(Y | X) – условная энтропия, определяемая помехами в данном канале (9).

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

.

Причем N = 10 сигн/сек.

Рассчитаем условную энтропию по формуле (9)



так как p(x₁) + p(x₂) = 1.

Используя формулу (15), имеем

бит/сек.

Здесь использовано, что (бит).


МЕТОДИЧЕСКИЕ УКАЗАНИЯ ДЛЯ ПРЕПОДАВАТЕЛЕЙ

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

МАТЕРИАЛЫ ТЕКУЩЕГО, ПРОМЕЖУТОЧНОГО И ИТОГОВОГО КОНТРОЛЯ ЗНАНИЙ СТУДЕНТОВ

Тестовые задания

Тест 1