- •Министерство образования и науки рф
- •080801 Прикладная информатика (по областям применения)
- •Сочи, 2010 г.
- •1. Меры информации 20
- •2. Квантование сигналов 46
- •3.8. Помехоустойчивое кодирование 96
- •Введение Курс лекций
- •Определение понятия информация
- •Некоторые определения
- •Фазы обращения информации
- •1. Меры информации
- •1.1. Структурные меры количества информации
- •1.1.1. Геометрическая мера
- •1.1.2. Комбинаторная мера
- •1.1.3. Аддитивная мера (мера Хартли)
- •1.2. Статистические меры
- •1.2.1. Энтропия и ее свойства.
- •1.2.1.1. Энтропия и средняя энтропия простого события
- •Метод множителей Лагранжа
- •1.2.1.2. Энтропия сложного события, состоящего из нескольких независимых событий
- •1.2.1.3. Вывод формулы среднего значения энтропии на букву сообщения
- •1.2.1.4. Энтропия сложного события, состоящего из нескольких зависимых событий
- •1.2.2. Некоторые выводы, касающиеся статистической меры количества информации Шеннона
- •1.2.3. Литература
- •1.2.4. Избыточность сообщения
- •1.2.5. Пример оценки количества информации при помощи статистической меры Шеннона
- •1.3. Семантические меры информации
- •1.3.1. Содержательность информации
- •1.3.2. Целесообразность информации
- •1.3.3. Динамическая энтропия
- •1.4. Общие замечания об измерении информации
- •1.5. Энтропия непрерывных сообщений
- •1.5.1. Экстремальные свойства энтропии непрерывных сообщений
- •1.5.1.1. Первый случай (значения сл. Величины ограничены интервалом)
- •1.5.1.2. Второй случай (заданы дисперсия и математическое ожидание сл. Величины)
- •1.5.1.3. Третий случай (сл. Величина принимает только положительные значения)
- •2. Квантование сигналов
- •2.1. Виды дискретизации (квантования)
- •2.2. Критерии точности представления квантованного сигнала
- •2.3. Элементы обобщенной спектральной теории сигналов
- •2.4. Дискретизация по времени
- •2.4.1. Разложение в ряд Котельникова (Теорема Котельникова)
- •2.4.1.1. Свойства функции отсчетов
- •2.4.1.2. О практическом использовании теоремы Котельникова
- •2.4.2. Выбор периода дискретизации (квантования по времени) по критерию наибольшего отклонения
- •2.4.2.1. Интерполяция при помощи полиномов Лагранжа
- •2.4.2.2. Оценка максимального значения ошибки при получении воспроизводящей функции на основе полинома Лагранжа
- •2.4.2.3. Схема дискретизации-передачи-восстановления сигнала
- •2.4.2.4. Расчет периода дискретизации при использовании для получения воспроизводящей функции полинома Лагранжа нулевого порядка
- •2.4.2.5. Расчет периода дискретизации при использовании для получения воспроизводящей функции полинома Лагранжа первого порядка
- •2.4.2.6. Расчет периода дискретизации при использовании для получения воспроизводящей функции полинома Лагранжа второго порядка
- •2.4.2.7. Обобщение на случай использования полиномов Лагранжа произвольного порядка
- •2.4.3. Выбор интервала дискретизации по критерию среднеквадратического отклонения
- •2.5. Квантование по уровню
- •2.5.1. Оптимальное квантование по уровню
- •2.5.2. Дисперсия ошибки в случае использования равномерной шкалы квантования по уровню
- •2.5.3. Расчет неравномерной оптимальной в смысле минимума дисперсии ошибки шкалы квантования.
- •2.5.4. Расчет неравномерной оптимальной в смысле максимума количества информации в квантованном сигнале шкалы квантования
- •2.5.5. Закон компандирования при условии равномерного закона распределения квантуемого сигнала
- •3. Кодирование информации
- •3.1. Общие понятия и определения. Цели кодирования
- •3.2. Элементы теории кодирования
- •3.3. Неравенство Крафта
- •3.4. Теорема об обобщении некоторых результатов, полученных для префиксных кодов, на все однозначно декодируемые коды
- •3.5. Основная теорема кодирования для канала связи без шума (теорема 3)
- •3.6. Теорема о минимальной средней длине кодового слова при поблочном кодировании (теорема 4)
- •3.7. Оптимальные неравномерные коды
- •3.7.1. Лемма 1. О существовании оптимального кода с одинаковой длиной кодовых слов двух наименее вероятных кодируемых букв
- •3.7.2. Лемма 2. Об оптимальности префиксного кода нередуцированного ансамбля, если префиксный код редуцированного ансамбля оптимален
- •3.7.3. Коды Хаффмена12
- •3.7.4. Коды Шеннона−Фэно
- •3.7.5. Параметры эффективности оптимальных кодов
- •3.7.6. Особенности эффективных кодов.
- •3.8. Помехоустойчивое кодирование
- •3.8.1. Классификация кодов
- •3.8.2. Простейшие модели цифровых каналов связи с помехами
- •3.8.3. Расчет вероятности искажения кодового слова в дсмк
- •3.8.4. Общие принципы использования избыточности
- •3.8.5. Граница Хэмминга
- •3.8.6. Избыточность помехоустойчивых кодов
- •3.8.7. Математическое введение к алгебраическим кодам
- •3.8.8. Линейные коды
- •3.8.9. Упрощённый способ построения линейного кода
- •Определение числа добавочных разрядов m.
- •Построение образующей матрицы
- •Порядок кодирования
- •4. Порядок декодирования
- •3.8.10. Двоичные циклические коды
- •3.8.11. Некоторые свойства циклических кодов
- •3.8.12. Построение кода с заданной корректирующей способностью
- •3.8.13. Матричное описание циклических кодов
- •3.8.14. Выбор образующего полинома
- •4. Передача информации
- •4.1. Виды каналов передачи информации
- •4.2. Разделение каналов связи
- •4.2.1. Частотное разделение
- •4.2.2. Временное разделение
- •4.2.3. Кодовое разделение
- •4.2.4. Разделение по уровню
- •4.2.5. Корреляционное разделение
- •4.2.6. Комбинированные методы разделения
- •4.3. Пропускная способность каналов связи
- •4.4. Пропускная способность дискретного канала связи с шумом
- •4.4.1. Типичные последовательности и их свойства
- •4.4.2. Основная теорема Шеннона для дискретного канала с шумом
- •4.4.3. Обсуждение основной теоремы Шеннона для канала с шумом
- •4.5. Пропускная способность непрерывного канала при наличии аддитивного шума
- •Литература
- •Приложение 1. Таблица неприводимых полиномов
- •Учебно-лабораторный практикум л абораторная работа 1: Исследование информативности источников дискретных сообщений.
- •Теоретическое введение
- •Шаг 2. Ввод текстовых файлов в Excel-таблицу с разбиением каждой строки текста на отдельные символы.
- •Шаг 3. Используя инструмент «гистограмма» пакета анализа надстройки Анализ данных, находим частоты появления каждого символа в текстах и по ним находим вероятности их появления в данном языке.
- •Шаг 4. Находим среднюю энтропию, приходящуюся на 1 букву сообщения.
- •Шаг 6. Возьмем короткий отрезок текста на одном из заданных языков и найдем количество заключенной в нем информации
- •Шаг 7. Проделаем те же операции с учетом зависимости двух соседних букв того же текста.
- •Шаг 8. Напишем отчет о выполненной работе с описанием всех вычислений и о том, как они выполнялись. Прокомментируйте результаты.
- •Шаг 9. Сдайте или отослать по электронной почте (alexm5@fromru.Com) отчет на проверку преподавателю. Шаг 10. Защитите лабораторную работу у преподавателя. Варианты задания
- •Результаты работы
- •Сдача работы
- •Вопросы для самопроверки
- •Литература
- •Приложение 1: Пример оформления титульного листа
- •Приложение 2: Порядок создания нестандартных функций при использовании табличного процессора Excel Введение
- •Подключение возможности использования нестандартных функций.
- •Создание нестандартной функции
- •Приложение 3: Описание функции впр
- •Лабораторная работа 2. Исследование методов дискретизации непрерывных сообщений по времени
- •Теоретическое введение.
- •Последовательность выполнения практической части работы
- •1. Знакомство с программой Wavosaur для записи и обработки звука.
- •2. Подключите к компьютеру головную гарнитуру (головной телефон и микрофон, рис. 2, слева) и нажмите кнопку Monitor input with vu meter, указанную на рис. 2 справа синей стрелкой.
- •3. Запись голоса и подготовка сигнала.
- •4. Импорт текстовых данных в Excel
- •Результаты работы
- •Литература
- •Вопросы для самопроверки
- •Иллюстрация к порядку вычисления ряда Найквиста-Котельникова
- •Лабораторная работа 3. Исследование оптимального квантования непрерывных сообщений по уровню.
- •Теоретическое введение.
- •Возможный вариант выполнения работы
- •Результаты работы
- •Литература
- •Вопросы для самопроверки
- •Лабораторная работа 4. Исследование оптимальных (в смысле минимальной средней длины кодового слова) кодов на примере кодов Шеннона-Фэно и Хаффмена.
- •Теоретическое введение.
- •Коды Хаффмена
- •Коды Шеннона−Фэно
- •Параметры эффективности оптимальных кодов
- •Особенности эффективных кодов.
- •Выполнение работы
- •Результаты работы
- •Литература
- •Вопросы для самопроверки
- •Лабораторная работа 5. Исследование кодов, обнаруживающих и исправляющих ошибки на примере линейного кода, исправляющего однократные ошибки.
- •Теоретическое введение.
- •Определение числа добавочных разрядов m.
- •Построение образующей матрицы
- •Порядок кодирования
- •4. Порядок декодирования
- •Выполнение работы
- •Результаты работы
- •Литература
- •Вопросы для самопроверки
- •12 Дэвид Хаффман (р. 9 августа 1925, Альянс, Огайо — 7 октября 1999, Санта Круз, Калифорния) — первопроходец в сфере информатики.
Литература
Темников Ф. Е. и др. Теоретические основы информационной техники: Учеб. пособие для вузов. Ф. Е. Темников, В.А. Афонин, В.И. Дмитриев. – 2-е изд., перераб. и доп. –М.: Энергия, 1979. –512 с., ил.
Кузин Л. Т. Математические основы кибернетики. Том 1. Учеб. пособие. –М.: Энергия, 1973. –504 с.
Цымбал В.П. Теория информации и кодирования. −Киев: Вища школа; 1977. −288 с.
Кэтермоул К.В. Принципы импульсно-кодовой модуляции. −М.:Связь, 1974. −408 с.
Советов Б.Я. Теория ин формации. −Л.:Из-во ЛГУ, 1977. −184 с.
Яглом Л. М., Яглом И. М. Вероятность и информация. −М.:Наука, 1973. −512 с.
Шляпоберский В. И. Основы техники передачи дискретных сообщений. −М.: Связь, 1973. −480 с.
Липкин И. А. Основы статистической радиотехники, теории информации и кодирования. –М.:Советское радио. 1978. –240 с.
Галлагер Р. Теория информации и надежная связь. Пер с англ., под ред. М. С. Пинскера и Б. С. Цыбакова. –М.:Советское радио, 1974. −720 с.
Элементы теории передачи дискретной информации. Под ред. Л. П. Пуртова. −М.:Связь, 1972. −232 с.
Приложение 1. Таблица неприводимых полиномов
(По книге Темников Ф.Е. и др. Теоретические основы информационной техники. 3-е изд. –М.:Энергия, 1979. –512 с.)
№ п/п |
Сте-пень |
Полином |
Двоичная последовательность |
1 |
1 |
Х+1 |
11 |
2 |
2 |
х2+х+1 |
111 |
3 |
3 |
Х3+Х+1 |
1011 |
4 |
Х3+Х2+1 |
1101 |
|
5 |
4 |
Х4+Х+1 |
10011 |
6 |
Х4+Х8+1 |
11001 |
|
7 |
Х4+Х3+Х2+Х+1 |
11111 |
|
8 |
5 |
Х5+Х2+1 |
100101 |
9 |
Х5+Х3+1 |
101001 |
|
10 |
Х5+Х3+Х2+Х+1 |
110111 |
|
11 |
Х5+Х4+Х2+Х+1 |
110111 |
|
12 |
Х5+Х4+Х3+Х+1 |
111011 |
|
13 |
Х5+ Х4+Х3+Х2+l |
111101 |
|
14 |
6 |
х6+X1+1 |
1000011 |
15 |
X6+X3+1 |
1001001 |
|
16 |
X6+х4+х2+х+1 |
1010111 |
|
17 |
х6+х4+X3+х+1 |
1011011 |
|
18 |
х6+х5+1 |
1100001 |
|
19 |
х6+х5+х2+х+1 |
1100111 |
|
20 |
х6+х5+х3+х2+1 |
1101101 |
|
21 |
X6+х5+х4+х+1 |
1110011 |
|
22 |
х6+х5+х4+х2+1 |
1110101 |
|
23 |
7 |
х7+х+1 |
10000011 |
24 |
х7+х3+1 |
10001001 |
|
25 |
х7+х3+х2+х+1 |
10001111 |
|
26 |
X7+Х4+1 |
10010001 |
|
27 |
X7+х4+х3+х2+1 |
10011101 |
|
28 |
X7+X5+X2+X+1 |
10100111 |
|
29 |
х7+х5+х3+х+1 |
10101011 |
|
30 |
X7+X5+X4+X3+1 |
10111001 |
|
31 |
X7+X5+X4+X3+X2+X+1 |
10111111 |
|
32 |
X7+X6+11 |
11000001 |
|
33 |
X7+X6+X3+X+1 |
11001011 |
|
34 |
х7+х6+х4+х+1 |
11010011 |
|
35 |
X7+X6+X5+X4+X2+1 |
11110101 |
|
36 |
X7+X6+X5 +X2+1 |
11100101 |
|
37 |
X7+X6+X5+X3+X2+X+1 |
11101111 |
|
38 |
X7+X6+X5+X4+1 |
11110001 |
|
39 |
X7+X6+X5+X4+X2+X+1 |
11110111 |
|
40 |
X7+X6+X5+X4+X3+X2+1 |
11111101 |
|
41 |
8 |
х8+х4+X3+х + 1 |
100011011 |
42 |
X8+X4+X3+X2+1 |
100011101 |
|
43 |
х8+х8+х3+х+1 |
100101011 |
|
44 |
X8+X5+X3+X2+1 |
100101101 |
|
45 |
Х8+Х5+Х4+Х3+1 |
100111001 |
|
46 |
Х8+Х5+ х4+х3+х2+х+1 |
100111111 |
|
47 |
X8+X6 +X3+X2+1 |
101001101 |
|
48 |
X8+X6+X4+X3+X2+X+1 |
101011111 |
|
49 |
X8+X6+X5 +X+1 |
101100011 |
|
50 |
X8+X6+X5 +X2+1 |
101100101 |
|
51 |
X8+X6+X5+X3+1 |
101101001 |
|
52 |
X8+X6+X5+X4+1 |
101110001 |
|
53 |
X8+X6+X5+X4+X2+X+1 |
101110111 |
|
54 |
X8+X6+X5+X4+X3+X+1 |
101111011 |
|
55 |
X8+X7 +X2+X+1 |
110000111 |
|
56 |
х8+х7+х3+х+1 |
110001011 |
|
57 |
х8+х7+х3+х2+1 |
110001101 |
|
58 |
X8+X7+X4+X3+X2+X+1 |
110011111 |
|
59 |
X8+X7+X5+X+1 |
110100011 |
|
60 |
X8+X7+X5+X3+1 |
110101001 |
|
61 |
х8+х7+х5+х4+1 |
110110001 |
|
62 |
х8+х7+х5+х4+х3+х2+1 |
110111101 |
|
63 |
х8+х7+х6+х+1 |
111000011 |
|
64 |
X8+X7+X6+X3+X2+X+1 |
111001111 |
|
65 |
х8+х7+х6+х4+х2+х+1 |
111010111 |
|
66 |
X8+X7+X6+X4+X3+X2+1 |
111011101 |
|
67 |
X8+X7+X6+X5+X2+X+1 |
111100111 |
|
68 |
X8+X7+X6+X5+X4+X+1 |
111110011 |
|
69 |
X8+X7+X6+X5+X4+X2+1 |
111110101 |
|
70 |
X8+X7+X6+X5+X4+X3+1 |
111111001 |
|
71 |
9 |
х9+х+1 |
1000000011 |
72 |
X9+ X4+1 |
1000010001 |
|
73 |
X9+X4+X2+X+1 |
1000010111 |
|
74 |
X9+X4+X3+X+1 |
1000011011 |
|
75 |
Х9+Х5+1 |
1000100001 |
|
76 |
X9+X5+X3+X2+1 |
1000401101 |
|
77 |
X9+X5+X4+X+1 |
1000110011 |
|
78 |
X9+X6+X3+X+1 |
1001001011 |
|
79 |
X9+X6+X4+X3+1 |
1001011001 |
|
80 |
х9+х6+х4+х3+х2+X+1 |
1001011111 |
|
81 |
X9+X6+X5+X2+1 |
1001100101 |
|
82 |
X9+X6+X5+X3+1 |
1001101001 |
|
83 |
X9+X6+X5+X3+X2+X+1 |
1001101111 |
|
84 |
X9+X6+X5+X4+X2+X+1 |
1001110111 |
|
85 |
X9+X6+X5+X4+X3+Х2+1 |
1001111101 |
|
86 |
X9+X7+X2+X+1 |
1010000111 |
|
87 |
Х9+Х7+Х4+Х2+1 |
1010010101 |
|
88 |
х9+х7+х4+х3+1 |
1010011001 |
|
89 |
Х9+Х7+Х5+Х+1 |
1010100011 |
|
90 |
х9+х7+х5+х2+1 |
1010100101 |
|
91 |
х9+х7+х5+х3+х2+х+1 |
1010101111 |
|
92 |
х9+х7+X5+х4+х2+х+1 |
1010110111 |
|
93 |
х9+х7+х5+х4+х3+х2+1 |
1010111101 |
|
94 |
х9+х7+х6+ х3+х2+х+1 |
1011001101 |
|
95 |
X9+X7+X6+X4+1 |
1011010001 |
|
96 |
X9+X7+X6+X4+X3+X+1 |
1011011011 |
|
97 |
х9+х7+х6+х5+х4+х2+1 |
1011110101 |
|
98 |
х9+х7+х6+х5+х4+х3+1 |
101111100J |
|
99 |
х9+х8+1 |
1100000001 |
|
100 |
х9+х8+х4+х+1 |
1100010011 |
|
101 |
X9+X8+X4+X2+1 |
1100010101 |
|
102 |
X9+X8+X4+X3+X2+X+1 |
1100011111 |
|
103 |
х9+х8+х5+х+1 |
1100100011 |
|
104 |
X9+X8+X5+X4+1 |
1100110001 |
|
105 |
X9+X8+X5+X4+X3+X+1 |
1100111011 |
|
106 |
X9+X5+X6+X3+1 |
1101001001 |
|
107 |
Х9+х8+х6+Х3+х2+х+1 |
1101001111 |
|
108 |
X9+X8+X6+X4+X3+X+1 |
1101011011 |
|
109 |
х9+х8+х6+х5+1 |
1101100001 |
|
110 |
X9+X8+X6+X5+X3+X+1 |
1101101011 |
|
111 |
X9+X8+X6+X5+X3+Х2+1 |
1101101101 |
|
112 |
X9+X8+X6+X5+X4+X+1 |
1101110011 |