- •Министерство образования и науки рф
- •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, Санта Круз, Калифорния) — первопроходец в сфере информатики.
4.2.5. Корреляционное разделение
В основу такого разделения положено
использование системы ортогональных
нормированных функций
на интервале (0;Т).
В канал связи подается сумма:
.
Информация с i-го канала здесь передается амплитудой сигнала аi.
На приемном конце получают сигнал bi:
,
так как
.
За отрезок времени Т можно таким образом одновременно передать n величин ai (1<=i<=n). Следующая порция n величин ai передается за следующий отрезок времени длиной Т.
На рис. 4.3 изображена блок-схема системы корреляционного разделения каналов.
Рис. 4.3. Схема многоканальной системы передачи информации, основанной на корреляционном разделении каналов.
Видно, что эта схема во многом подобна схеме частотного разделения. Это не случайно. Действительно, здесь есть сходство. Частотное разделение основано на использовании одного из видов ортонормированных функций – набора синусоидальных функций. Но они образуют лишь одну из множества возможных систем ортонормированных функций. Существуют еще системы функций Радемахера, Хара, Уолша, Лежандра и другие, которые также можно использовать для разделения каналов и которые при определенных условиях обладают преимуществами по сравнению с остальными.
4.2.6. Комбинированные методы разделения
Комбинированные методы разделения каналов позволяют увеличить число каналов и уменьшить их взаимное влияние.
Можно, например, сочетать временное или кодовое разделение с частотным, амплитудным или корреляционным.
В заключение отметим, что в здесь перечислены далеко не все возможные методы разделения каналов связи. Благодаря непрерывающимся исследованиям, появляются новые и усовершенствуются ранее известные методы разделения каналов передачи информации.
4.3. Пропускная способность каналов связи
Эта тема является одной из центральных в теории информации. В ней рассматриваются предельные возможности каналов связи по передаче информации, определяются характеристики каналов, влияющие на эти возможности, исследуются в самом общем виде предельные возможности кодирования, обеспечивающие максимум помехоустойчивости и объема передаваемой информации.
Определения:
Скорость передачи информации – среднее количество информации, передаваемой через канал за единицу времени.
В случае канала без шума эта скорость равна Vк*Hк, где Vк – количество символов, передаваемых через канал в единицу времени, Hк – средняя энтропия одного символа сообщения на входе и выходе канала.
Производительность источника – средняя скорость поступления информации от источника сообщений.
Производительность источника находится по формуле Vи*Hи, где Vи – количество символов, генерируемых источником в единицу времени, Hи – средняя энтропия одного символа сообщения на выходе источника.
Пропускная способность канала связи – максимально возможная для данного канала скорость передачи информации. Будем обозначать ее Ск.
Отметим еще одну важную характеристику канала – максимальную скорость передачи символов Vк max через него. Она всегда ограничена. Поэтому максимальная скорость передачи информации достигается при использовании максимальной скорости передачи символов и максимальной средней энтропии Vк max передаваемого символа. Ранее доказывалось, что максимальная средняя энтропия в расчете на одни символ достигается при равной вероятности и независимости их появления.
Поскольку источник информации совсем не обязательно выдает символы с такими характеристиками, для достижения максимально эффективного использования канала их необходимо кодировать. Ранее при изучении эффективного кодирования доказывалось, что именно эффективное кодирование обеспечивает получение после кодирования символов с требуемыми параметрами. Энтропия символов вторичного алфавита в результате такого кодирования при кодировании бесконечно больших блоков информационной последовательности в пределе равна log2m, где m – объем вторичного алфавита, используемого на выходе кодирующего устройства.
Учитывая это: Ск=Vк * Hmax = Vк * log2m .
Если же m=2 (для кодирования используется двоичный код), то энтропия одного символа на выходе кодера будет равна 1, т.е. каждый символ двоичного эффективного кода будет нести 1 бит информации, а сами символы будут равновероятны и статистически независимы.
В этом случае Ск=Vк .
При передаче информации через канал связи стремятся к наиболее эффективному (в смысле объема передаваемой информации) его использованию.
Найдем требования к источнику информации, при которых возможна максимальная скорость передачи информации через канал.
Будем описывать источник информации параметрами Vи и Hи. Допустим, шум в канале связи отсутствует. Канал связи описывается своей пропускной способностью и объемом m алфавита.
Поскольку шума в канале нет, информация при передаче через него не искажается и не теряется. Поэтому скорости передачи информации на выходе источника Vи*Hи и на выходе канала будут совпадать. Наиболее эффективным будет такое использование канала, при котором производительность источника будет равна пропускной способности канала:
Ск=Vк max * log2m = Vи * Hи .
Таким образом, если известна средняя энтропия одного символа сообщения, поступающего с выхода источника, наиболее эффективного использования канала можно достичь, если скорость поступления этих символов от источника выбрать в соответствии с формулой: Vи=Vк max * log2m / Hи или Vи=Vк max / Hи при использовании наиболее часто употребляемого двоичного кодирования.
Заметим, что эта формула предполагает использование эффективного кодирования информации, поступающей от источника перед передачей ее в канал связи без помех (шума).
Рассмотрим следующую модель канала связи с помехами (рис. 4.4):
Рис. 4.4. Модель канала связи с помехами.
По виду передаваемых через канал сигналов различают дискретные и непрерывные каналы связи.
Важнейшей характеристикой канала является его пропускная способность, определяемая как наибольшая скорость передачи информации через него. Пропускная способность дискретного канала может быть рассчитана, например, по следующей формуле:
С= Vk*Imаx ,
где Vk – скорость передачи символов алфавита через канал;
Imаx – максимально возможное количество информации, приходящейся на один передаваемый через канал символ.
Количество информации, приходящееся на 1 передаваемый через канал символ зависит от энтропии (степени неопределенности получения символа) на входе и выходе канала. Согласно мере Шеннона
I = Hаприорная - Hапостериорная = H(X) – H(X/Y) .
Здесь Hаприорная = H(X) и Hапостериорная = H(X/Y) – условная энтропия, характеризующая неопределенность о переданном на выход канала символе X по принятому символу Y на выходе. Наличие этой неопределенности – следствие действия на передаваемый через канал символ помех. H(X/Y) – характеристика канала.
