- •Министерство образования и науки, молодёжи и спорта украины
- •Тема 1. Предмет теории информации и количественная мера информации
- •1.2 Этапы обращения информации
- •1.3 Система передачи информации
- •1.4 Задачи и постулаты прикладной теории информации
- •1.5. Количественная оценка информации дискретного источника. Энтропия.
- •1.6 Фундаментальные свойства энтропии
- •Тема 2. Основные виды энтропии дискретных источников. Условная и взаимная энтропии.
- •2.1 Условная энтропия.
- •2.2 Основные свойства условной энтропии.
- •2.3 Взаимная энтропия. Свойства энтропии объединения.
- •Тема 3. Эффективное кодирование источника дискретных сообщений в канале без помех.
- •3.1 Избыточность информации, причины ее появления.
- •3.2 Способы сокращения избыточности.
- •3.3 Теорема Шеннона для канала без помех.
- •4.1 Общие понятия и элементы теории кодирования
- •4.2 Цели кодирования
- •4.3 Оптимальные неравномерные коды
- •4.4 Коды Шеннона-Фэно
- •4.5 Коды Хаффмена
- •4.6 Особенности эффективных кодов.
- •Тема 4. Кодирование источника дискретных сообщений в канале с помехами. Общие принципы помехоустойчивого кодирования.
- •5.1 Кодирование информации для канала с помехами. Теорема Шеннона для канала с помехами.
- •5.2 Общие принципы использования избыточности
- •5.3 Связь корректирующей способности кода с кодовым расстоянием
- •6.1 Корректирующие свойства кодов с избыточностью.
- •6.2 Классификация корректирующих кодов
- •Тема 5. Регулярные методы построения двоичных помехоустойчивых кодов
- •7.1 Линейные коды. Общие медоды построения.
- •7.2 Определение числа добавочных разрядов r.
- •7.3 Построение образующей(порождающей) матрицы |om|.
- •7.4 Порядок кодирования
- •7.5 Порядок декодирования
- •7.6 Систематические коды. Код Хэмминга.
- •7.7 Обнаружение и исправление ошибок в коде Хэмминга
- •8.1 Двоичные циклические коды
- •8.2 Некоторые свойства циклических кодов
- •8.3 Матричное описание циклических кодов
- •8.4 Выбор образующего полинома
- •8.5 Декодирование циклических кодов
- •Тема 6. Построение кодов заданой помехоустойчивости. Применение недвоичных помехоустойчивых кодов.
- •9.1 Матричное описание циклических кодов.
- •9.2 Коды Боуза — Чоудхури — Хоквингема (бчх)
- •9.3 Систематический вид циклического кода.
- •9.4 Коды Рида–Соломона и их применение.
- •9.5 Циклический избыточный код crc
- •Тема 7. Информационные характеристики источников непрерывных сообщений. Источники с максимальной энтропией. Максимальная пропускающая способность канала связи с помехами.
- •10.1 Информационные характеристики источников непрерывных сообщений
- •10.2 Энтропия равномерного закона распределения
- •10.3 Энтропия гауссового закона распределения.
- •11.1 Пропускная способность канала связи с помехами для непрерывных сообщений
- •Тема 8. Методы кодирования информации со сжатием.
- •12.1 Подстановочные или словарно-ориентированные алгоритмы сжатия информации. Методы Лемпела-Зива.
- •13.1 Описание алгоритма сжатия lzw
- •Декодирование по lzw
- •Достоинства и недостатки lzw
- •13.2 Применение lz-алгоритмов упаковки данных
- •14.1 Кодирование длин повторений
- •14.2 Дифференциальное кодирование
- •Тема 9. Методы кодирования со сжатием и с потерями информации..
- •15.1 Методы сжатия с потерей информации
- •15.2 Точность. Помехи и искажения. Приближенное восстановление
- •15.5 Кодирование преобразований. Стандарт сжатия jpeg
- •Или же, в матричной форме,
- •Тема 10. Методы кодирования физических сигналов в компьютерных сетях.
- •16.1 Кодирование на физическом уровне.
- •16.2 Самонихронизирующиеся коды - коды rz и Манчестер-II
- •16.3 Несамосинхронизирующиеся коды. - код nrz
- •16.4 Высокоскоростные коды - код mlt-3 и pam 5
- •Еще более высокоскоростной код - код pam 5
- •16.5 Требуемая полоса частот для передачи данных и ширина спектра сигнала
- •Ширина спектра сигнала
Тема 2. Основные виды энтропии дискретных источников. Условная и взаимная энтропии.
Лекция 2
2.1 Условная энтропия.
Для дальнейшего изложения нам понадобятся некоторые известные сведения из теории вероятности.
1) Свойства вероятностей для ансамбля случайных событий А и В:
P(A,B)=P(A)*P(B/A); -> P(B/A)=P(A,B)/P(B);
P(A,B)=P(B)*P(B/A); -> P(A/B)=P(A,B)/P(A);
P(A/B)=P(A)*P(B/A)/P(B); P(B/A)=P(B)*P(A/B)/P(A);
Если А и В независимы, то
P(A/B)=P(A); P(B/A)=P(B):
P(A,B)=P(A)*P(B);
Еще раз определение энтропии по Шеннону для источника дискретных сообщений:
Ее свойства:
Н > 0 ;
Нmах = log N;
При независимых источниках H(A,B)=H(A)+H(B);
УСЛОВНАЯ ЭНТРОПИЯ
Если состояния элементов системы не зависят друг от друга или если состояние одной системы не зависит от состояния другой системы, то неопределенность того, что некоторый элемент системы (или некоторая система) будет находиться в одном из возможных состояний, полностью определялась бы вероятностными характеристиками отдельных элементов системы. В этом случае удельное количество информации на состояние элемента системы или на один символ сообщений называется средней энтропией, а при ее вычислении используется выражение
При подсчете среднего количества информации на символ сообщения взаимозависимость учитывают через условные вероятности наступления одних событий относительно других, а полученную при этом энтропию называют условной энтропией.
Рассмотрим передачу сообщений источника случайных символов А через канал передачи информации. При это полагается, что при достоверной передаче при при передаче символа a1 получаем b1, a2 - b2 и т.д. При этом для канала с помехами передача искажается, и при получении сивола b1 можно лишь сговорить о вероятности перередачи символа a1. Вполне может быть, что были переданы символы a2, a3 и т.д.
Искажения описываются матрицей условных вероятностей канала P(A/B)={p(ai/bi}.
Рассмотрим процесс передачи сигналов по каналу связи с помехами и используем его для уяснения механизма вычисления условной энтропии.
Если источник сообщений выдает символы
al, а2, ..., ai ..., аn
с вероятностями соответственно
р (а1), р (а2) ... ..., р (аi), ..., р (аn),
а на выходе канала передачи мы получаем символы
b1 ,b2, ..., bi ..., bn
с вероятностями соотетственно
р (b1), р (b2), ..., р (bi, ..., р (bn),
то понятие условной энтропии Н (B/ai) выражает неопределенность того, что, отправив ai, мы получим bi., понятие H(A/bi) неуверенность, которая остается после получения bi в том, что было отправлено именно ai. Графически это представлено на вышеприведеном рисунке. Если в канале связи присутствуют помехи, то с различной степенью вероятности может быть принят любой из сигналов bj и, наоборот, принятый сигнал bj может появиться и результате отправления любого из сигналов ai. Если в канале связи помехи отсутствуют, то всегда посланному символу а1 соответствует принятый символ b1, а2— b2, ..., аn— bn.
При этом энтропия источника сообщений H(А) равна энтропии приемника сообщений Н (В). Если в канале связи присутствуют помехи, то они уничтожают или искажают часть передаваемой информации.
Информационные потери полностью описываются через частную и общую условную энтропию. Вычисление частных и общей условной энтропии удобно производить при помощи канальных матриц. Термин «канальная матрица», означающий: матрица, статистически описывающая данный канал связи, применяется для краткости. Если канал связи описывается со стороны источника сообщений (т. е. известен посланный сигнал), то вероятность того, что при передаче сигнала ai по каналу связи с помехами мы получим сигнал bj обозначается как условная вероятность р (bj/ai). а канальная матрица имеет вид
Вероятности, которые расположены по диагонали (выделенные полужирным шрифтом), определяют вероятности правильного приема, остальные — ложного. Значения цифр, заполняющих колонки канальной матрицы, обычно уменьшаются по мере удаления от главной диагонали и при полном отсутствии помех все, кроме цифр, расположенных на главной диагонали, равны нулю.
Прохождение символа ai со стороны источника сообщений в данном канале связи описывается распределением условных вероятностей вида р(bj/ai), сумма вероятностей которого всегда должна быть равна единице. Например, для сигнала а1
Потери информации, приходящиеся на долю сигнала ai описываются при помощи частной условной энтропии. Например, для сигнала a1
Суммирование производится по j, так как i-е состояние (в данном случае первое) остается постоянным.
Потери при передаче всех сигналов по данному каналу связи описываются при помощи общей условной энтропии. Дли ее вычисления следует просуммировать все частные условные энтропии, т. е. произвести двойное суммирование по i и по j.
В случае неравновероятного появления символов источника сообщений следует учесть вероятность появления каждого символа, умножив на нее соответствующую частную условную энтропию. При этом общая условная энтропия
Если иследовать ситуацию со стороны приемника сообщений (то есть когда известен принятый сигнал) , то то с получением символа bj предполагается, что был послан какойто из символов a1, a2, …, ai,…,am. В этом случае канальная матрица имеет вид:
В этом случае единице должны равняться суммы условных вероятностей не по строкам, а по столбцам канальной матрицы
Частная условная энтропия
А общая условная энтропия
Общая условная энтропия системы В относительно системы А характеризует количество информации, содержащейся в любом символе источника сообщений, через который мы представляем состояния элементов исследуемых систем.
Общую условную энтропию определяют путем усреднения по всем символам, т. е. по всем состояниям аi с учетом вероятности появления каждого из них. Она равна сумме произведений вероятностей появления символов источника на неопределенность, которая остается после того, как адресат принял символы:
Если в канале связи помехи отсутствуют, то все элементы канальной матрицы, кроме расположенных на главной диагонали, равны нулю. Это говорит о том, что при передаче сигнала а1 мы наверняка получим b1 при передаче а2 -b2, ..., аm— bm. Вероятность получения правильного сигнала станет безусловной, а условная энтропия будет равна нулю.
Своего максимума условная энтропия достигает в случае, когда при передаче символа аi может быть с равной вероятностью получен любой из сигналов b1, b2, ..., bm.