- •Министерство образования и науки рф
- •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, Санта Круз, Калифорния) — первопроходец в сфере информатики.
Фазы обращения информации
Система управления состоит из объекта управления, комплекса технических средств, состоящего из компьютера, входящих в его состав устройств ввода-вывода и хранения информации, устройств сбора передачи и хранения информации, а также, возможно, человека-оператора.
В процессе обращения информации можно выделить несколько фаз (рис. 0.2).
1 фаза ─ восприятие информации - выполняется автоматически или с участием человека и состоит из выделения нужного сигнала от объекта и преобразования его в форму, удобную для передачи к месту хранения или обработки. Аналоговые сигналы при этом обычно квантуются. ТИ занимается среди прочих вопросами оптимального квантования.
Рис. 0.2. Фазы обращения информации
2 фаза ─ передача информации - состоит в кодировании и переносе ее на расстояние или во времени посредством сигналов различной природы по различным каналам. ТИ используется здесь при решении вопросов, связанных с улучшением качества и скорости передачи. Это наиболее плодотворная область применения ТИ.
3 фаза ─ обработка информации – в случае автоматизации заключается в обработке с помощью компьютерной техники, как правило, с участием человека.
4 фаза ─ хранение информации. При прохождении любой фазы неизбежны периоды хранения информации в разного рода запоминающих устройствах. ТИ используется здесь для анализа пропускной способности технических средств и помехоустойчивого кодирования, которое необходимо для преодоления вредного влияния сбоев оборудования и влияния внешней среды.
5 фаза ─ представление информации ─ используется тогда, когда в цикле обращения информации участвует человек. На этом этапе информация представляется в форме удобной для восприятия человеком. Результаты исследований, проведенных в рамках ТИ, наряду со сведениями из других наук применяются в этом случае для определения наилучшего режима передачи информации человеку.
6 фаза ─ воздействие ─ состоит в передаче управляющего воздействия на объект управления.
Некоторые определения
Данные или сигналы, организованные в определенные последовательности, несут информацию не потому, что они повторяют объекты реального мира, а по общественной договоренности о кодировании, т.е. однозначной связи знаков и объектов, например: предметы и слова для их обозначения. Кроме того, первичные сигналы могут быть порождены естественными законами реального мира, например: напряжение на выходе термопары под действием температуры.
Информация, основанная на однозначной связи знаков или сигналов с объектами реального мира, называется семантической или смысловой.
Информация, заключенная в характере (порядке и взаимосвязи) следования знаков сообщений, называется синтаксической.
Также в общей науке о знаках (семиотике), кроме перечисленных, выделяют сигматический и прагматический аспекты информации. В первом случае изучается вопрос о выборе знаков для обозначения объектов реального мира, во втором случае ─ о ценности информации для достижения поставленных целей.
Очевидно, что наибольший практический интерес представляют смысловой (семантический) и прагматический аспекты. Однако до сих пор не определены объективные количественные критерии меры ценности и полезности информации. В курсе теории информации изучаются проблемы синтаксического уровня, касающиеся создания теоретических основ построения систем связи, основные показатели функционирования которых были бы близки к предельно возможным.
Иначе говоря, рассмотрению подлежат вопросы доставки получателю информации как совокупности знаков. При этом игнорируется ее смысловое и прагматическое содержание. Синтаксическая мера информации имеет практическую ценность потому, что интересующая в конечном итоге получателя семантическая информация заключена в заданной последовательности знаков или первичных сигналов. Чем больше знаков передаются в определенный интервал времени, тем в среднем больше передается и смысловой информации.
Классическая теория информации представляет собой ветвь статистической теории связи. Для того, чтобы более конкретно обозначить предмет этой науки введем некоторые понятия и определения.
Информация передается и хранится в виде сообщений.
Под сообщением понимают совокупность знаков или первичных сигналов, содержащих информацию. Иначе говоря, сообщение ─ это информация, представленная в какой-либо форме. Пример сообщений: текст телеграммы, данные на выходе компьютера, речь, музыка и т.д.
Для того чтобы сообщение можно было передать получателю, необходимо воспользоваться некоторым физическим процессом, способным с той или иной скоростью распространяться от источника к получателю. Изменяющийся во времени физический процесс, отражающий передаваемое сообщение, называется сигналом.
Сообщения могут быть функциями времени (когда информация представлена в виде первичных сигналов: речь, музыка) и не являться ими (когда информация представлена в виде совокупности знаков).
Сигнал всегда является функцией времени.
В зависимости от того, какие значения могут принимать аргумент (время t) и уровни сигналов, сигналы делят на 4 типа.
Непрерывные или аналоговые сигналы (случайные сигналы этого типа называются непрерывными случайными процессами). Они определены для всех моментов времени и могут принимать все значения из заданного диапазона (рис. 0.3).
Рис. 0.3. Аналоговый сигнал.
Чаще всего физические процессы, порождающие сигналы, являются непрерывными. Этим и объясняется второе название сигналов данного типа ─ аналоговые, т.е. аналогичные порождающим процессам.
2) Дискретизированные или дискретно-непрерывные сигналы (случайные сигналы этого типа называют процессами с дискретным временем или непрерывными случайными последовательностями). Они определены лишь в отдельные моменты времени и могут принимать любые значения уровня (рис. 0.4).
Рис. 0.4. Дискретизация по времени.
Временной интервал t = tk+1 - tk между соседними отсчетами называется шагом дискретизации. Часто такие сигналы называют дискретными по времени.
3) Квантованные или дискретные по уровню сигналы (случайные сигналы этого типа называют дискретными случайными процессами). Они определены для всех моментов времени и принимают лишь разрешенные значения уровней, отделенные друг от друга на величину шага квантования X=Xk+1 - Xk (рис. 0.5).
Рис. 0.5. Квантование по уровню.
4) Дискретизированные и по уровню и по времени сигналы (случайные сигналы этого типа называют дискретными случайными последовательностями). Они определены лишь в отдельные разрешенные моменты времени и могут принимать лишь разрешенные значения уровней (рис. 0.6).
Рис. 0.6. Одновременные дискретизация по времени и квантование по уровню
Совокупность технических средств, используемых для передачи сообщений от источника к потребителю информации, называется системой связи (рис. 0.7).
Рис. 0.7. Общая схема системы связи.
Она состоит из 5 частей.
Источник сообщений, создающий сообщения или последовательность сообщений, которые должны быть переданы. Сообщения могут быть разных типов: последовательности букв или цифр (как в системах телеграфа и передачи данных), одна или более функций времени (как в системах передачи звука в моно- и стереозвучании) и т.д.
Передатчик преобразует сообщения в сигналы со свойствами зависящими от характеристик используемого канала.
Канал - комплекс технических средств, обеспечивающий передачу сигналов от передатчика к приемнику. В состав канала входит каналообразующая аппаратура, осуществляющая сопряжение выходного и входного сигналов соответственно передатчика и приемника с линией связи, и самой линии связи.
Линией связи называется среда, используемая для передачи сигнала от передатчика к приемнику. Это может быть, например, пара проводов, коаксиальный кабель, область распространения радиоволн, световод и т.д. Обычно входными и выходными сигналами линии связи являются сигналы первого типа, т.е. непрерывные. Вместе с тем, на входе и выходе канала могут присутствовать сигналы и других типов.
Канал называется дискретным, если на его входе и выходе присутствуют сигналы, дискретные по уровню (сигналы типа 3,4).
Если сигналы на входе и выходе канала непрерывны по времени (типа 1 или 2) то он называется непрерывным.
Если сигналы на входе (выходе) дискретны, а на выходе (входе) непрерывны по уровню, то канал называется дискретно-непрерывным (непрерывно-дискретным) или полунепрерывным.
В общем случае при передаче по каналу сигнал искажается шумом, что соответствует наличию в схеме (рис. 0.7) источника шума.
Приемник обычно выполняет операцию обратную по отношению к операции, производимой передатчиком, т.е. восстанавливает переданное сообщение по принятому сигналу. Сложность построения приемника обусловлена изменением формы принимаемых сигналов, что связано с наличием шума.
Получатель - это лицо или аппарат, для которого предназначено сообщение.
Процесс преобразования сообщения в сигнал, осуществляемый в передатчике, и обратный ему процесс, реализуемый в приемнике, назовем, соответственно, кодированием и декодированием.
Тогда круг проблем, составляющих основное содержание классической ТИ (далее просто ТИ), можно охарактеризовать как исследование методов кодирования для экономичного представления сообщений различных источников и для надежной их передачи по каналам связи с шумом.
Классическая ТИ базируется на статистическом описании источников сообщений и каналов связи. При этом используется статистическая мера количества информации, определяемая только вероятностными свойствами сообщений и не зависящая ни от каких других их свойств.
На основе ТИ можно ответить на вопросы о предельных возможностях (т.е. о максимально достижимых характеристиках) различных систем, определить в какой мере проектируемая система уступает теоретически возможной. В некоторых случаях логика рассуждений, используемая в ТИ, подсказывает путь, на котором может быть найдено конструктивное решение для реальной системы.
Датой рождения ТИ является 1948 год ─ год появления основополагающей статьи Клода Шеннона Математическая теория связи. Начиная с этого времени, ТИ интенсивно развивалась, в немалой степени благодаря работам и наших соотечественников Колмогорова, Добрушина, Харкевича, Хинчина и других.
