- •Введение
- •1. Энтропия источников сообщений
- •1.1. Дискретные ансамбли и источники
- •1.2. Количество информации в дискретном сообщении. Энтропия ансамбля
- •1.3. Условная информация. Условная энтропия. Совместная энтропия дискретного источника
- •1.4. Энтропия дискретного стационарного источника на сообщение
- •1.5. Избыточность источника дискретных сообщений
- •1.6. Эффективное кодирование. Кодирование источника равномерными кодами
- •1.7. Высоковероятные множества постоянного дискретного источника
- •1.8. Энтропия источника без памяти как скорость создания информации
- •1.9. Избыточность источника непрерывных сигналов. Количество информации в непрерывном канале
- •1.10. Скорость передачи информации и пропускная способность в непрерывном канале
- •2. Кодирование информации
- •2.1. Неравномерное кодирование с однозначным декодированием
- •2.2. Оптимальные неравномерные двоичные коды
- •2.3. Кодирование для исправления ошибок: Основные положения
- •2.4. Постановка задачи кодирования
- •2.5. Прямая теорема о кодировании в канале с шумами
- •2.6. Обратная теорема кодирования
- •2.7. Основная теорема Шеннона, ограничение возможностей использования оптимального кодирования на практике
- •3. Коды, исправляющие ошибки
- •3.1. Блоковые и сверточные коды
- •3.2. Хеммингово расстояние, Хемминговы сферы и корректирующая способность
- •3.3. Линейные блоковые коды
- •3.4. Порождающая и проверочная матрицы. Кодирование с помощью матриц g и н
- •3.5. Декодирование по стандартной таблице
- •3.6. Циклические коды
- •3.7. Кодирующие устройства циклических кодов
- •3.8. Декодирование циклических кодов по синдрому
- •3.9. Мажоритарное декодирование
- •4. Энтропия в контексте защиты информации от помех при передаче по каналу связи
- •4.1. Меры искажения. Постановка задачи защиты информации от помех при передаче по каналу связи
- •4.2. Свойства функции скорость-искажение
- •4.3. Простые примеры вычисления функции скорость-искажение
- •4.4. Функция скорость-искажение для гауссовских последовательностей
- •4.5. Эпсилон-производительность источника
- •4.6. Дифференциальная энтропия
- •4.7. Свойства дифференциальной энтропии
- •4.8. Эпсилон - энтропия источника сообщений
- •4.9. Обратная теорема кодирования для дискретного постоянного источника при заданном критерии качества
- •4.10. Прямая теорема кодирования с заданным критерием качества
- •4.11. Аксиоматическое введение в теорию энтропии вероятностных схем
- •4.12. Энтропия и условная энтропия объединенной вероятностной схемы и их свойства
- •Заключение
- •Библиографический список
- •Оглавление
- •394026 Воронеж, Московский просп., 14
4.11. Аксиоматическое введение в теорию энтропии вероятностных схем
Исходным понятием для построения рассматриваемой теории является понятие вероятностной схемы. Пусть (Ω, М, Р) - вероятностное пространство, {aj}- полная группа попарно несовместимых событий.
Определение 1. Пара А = ({aj},(p(aj))) называется вероятностной схемой.
Говорят, что вероятностная схема А дискретна, если число событий {aj}не более чем счётно. В этом случае А будем записывать в виде:
(4.34)
где ак - исход вероятностной схемы, р(ак) - вероятность исхода,
Если число событий {ак} более чем счётно, то вероятностная схема А называется непрерывной. Тогда её задают, описывая множество возможных исходов и указывая с помощью плотности распределения вероятностей р(х) вероятностное распределение на исходах. На протяжении данного курса будем, как правило, рассматривать конечные вероятностные схемы.
Важной характеристикой схемы является энтропия - средняя мера неравновероятности исходов схемы. Энтропия и близкое понятие информация по-разному определялись рядом авторов. Приведём некоторые из этих определений.
Согласно Р. Хартли количество информации, содержащееся в сообщении, должно удовлетворять двум требованиям:
а. Пусть сообщение Т1, записанное в алфавите A1, имеет длину l1 а сообщение Т2, записанное в алфавите А2, , имеет длину l2. Тогда если выполнено , то сообщения Т1 и Т2 несут одинаковое количество информации.
b. Количество информации, содержащееся в сообщении, пропорционально его длине.
Из этих положений Хартли получил формулу для количества информации в сообщении:
(4.35)
где n=|А| - мощность алфавита, l - длина сообщения.
К. Шеннон рассматривал порождение сообщений в условиях вероятностной схемы:
Относительно количества информации, содержащегося в сообщении Т длины l составленном по схеме независимых испытаний, высказываются следующие требования:
a. Пустое сообщение не содержит информации.
b. Количество информации, содержащееся в сообщении, пропорционально его длине.
По Шеннону, количество информации, содержащееся в сообщении равно:
(4.36)
где - энтропия вероятностной схемы, или количество информации, приходящееся на один символ порождённого сообщения.
Величина а (а > 1) - основание логарифмов, определяет единицу измерения количества информации. Если а = 2, то информацию измеряют в двоичных единицах битах; если а = е, то информация измеряется в натуральных единицах натах; если а = 10, то информация измеряется в десятичных единицах дитах.
А. Я. Хинчин к определению энтропии вероятностной схемы подошёл с аксиоматических позиций. В его работе установлено, что энтропия конечной вероятностной схемы однозначно определяется с точностью до постоянного множителя при задании системы аксиом.
Аксиомы Хинчина
1. - ненулевая непрерывная по переменным в симплексе
2. - симметрична по переменным .
3. .
4.
5.
Система аксиом Фаддеева эквивалентна системе аксиом Хинчина и позволяет получить тот же результат.
Аксиомы Фаддеева
1'. непрерывна при и положительна хотя бы в одной точке.
2'. симметрична по .
3'. При где
Разница в этих системах аксиом заключается в том, что аксиома 5 (экстремальность функции энтропии) заменяется требованием положительности энтропии в одной точке. Аксиомы Хинчина 3 и 4 заменяются аксиомой 3'. Аксиома 3' естественна, так как неопределённость схемы
отличается от неопределённости схемы
на неопределённость, происходящую от подразделения аn на два подсобытия b1,b2 с условными вероятностями . Эта неопределённость должна быть преодолена только в случае, если реализуется событие аn, вероятность которого равна рn.
Если рассматривать энтропию как количественную меру неопределённости в реализации вероятностной схемы, то последняя аксиома естественна.
Установим равносильность аксиом 2, 3, 4 и 2', 3', следуя упомянутой работе Фаддеева.
Лемма 1. Из аксиом 2, 3, 4 следует, что .
Доказательство.
Подсчитаем двумя способами:
По аксиоме 3:
По аксиоме 2:
Применим аксиому 4:
Отсюда следует, что
Лемма 2. Из аксиом 2, 3, 4 следует аксиома 3'.
Доказательство. Рассмотрим набор среди есть нуль. Из аксиом 2 и 3 следует, что перестановками аргументов можно представить в виде:
.
Применим аксиому 4:
Лемма 3. Из аксиом 2', 3' следует, что Н(1,0) = 0.
Доказательство. Подсчитаем двумя способами
Следовательно, Н(1,0) = 0.
Лемма 4. Из аксиом 2', 3' следует аксиома 3.
Доказательство.
Лемма 5. Из аксиомы 3' следует
Здесь m > 2,
Доказательство. При m = 2 утверждение леммы совпадает с аксиомой 3'. При лемма доказывается индукцией по m.
Лемма 6. Из аксиом 2', 3' следует
Здесь
Доказательство. Нужно n раз применить лемму 5 к каждой группе аргументов, что возможно в силу симметрии. Приняв m1 = m2 = ... = mn = m, получим, что из аксиом 2', 3' следует аксиома 4.
Установлена равносильность групп аксиом 2, 3, 4 и 2', 3'.
Перейдём к доказательству теоремы единственности функции энтропии. Введём определение:
, при и
Применяя лемму 6 к случаю m1 = m2 = ... = mn = m получим
(4.37)
Применим лемму 5 к :
Обозначим
Лемма 7. При
и
Доказательство. В силу непрерывности при .
при
Далее,
Отсюда, складывая эти соотношения для k = 1,2.., имеем:
Получаем
Однако - среднее арифметическое первых членов стремящейся к нулю последовательности
Следовательно,
и , при
Далее,
Лемма доказана.
В силу формулы (4.37) функция F(n) будет определена при всех натуральных n, как только зададим значения функции F на простых числах.
Именно, если n, где - простые, то
.
Положим,
, где p - простое число. (4.38)
Тогда
Лемма 8. Среди чисел ср (р = 2,3,5,7,...) существует наибольшее.
Доказательство. Допустим противное и покажем, что это предположение противоречит предположению о непрерывности при р = 0. Действительно, если в последовательности ср (р = 2,3,5,7,...) нет наибольшего числа, то можно построить бесконечную последовательность простых чисел так, что , рi - есть наименьшее простое число, такое, что cpi > cpi-1. Из способа построения этой последовательности ясно, что как только простое число q меньше рi, то cq < срi .
Пусть i > 1 и есть каноническое разложение числа .
Рассмотрим
Ясно, что
так как и в силу чётности (pi - 1) среди qj присутствует число 2 с ненулевым показателем.
Далее, при i →
Следовательно,
что невозможно.
Таким же образом устанавливается, что среди ср существует наименьшее.
Лемма 9. Функция , где с - постоянное. Доказательство. Достаточно установить, что все ср равны друг другу. Допустим, что найдётся такое простое число р’ что cр' > c2. Обозначим через р то простое число, для которого ср принимает наибольшее значение. Тогда cр > c2 и р > 2.
Пусть m - натуральное число и Рассмотрим:
При переходе к пределу при получим 0, что невозможно. Таким образом, для всех р' имеет место
Совершенно таким же образом устанавливается, что при всех р’ Лемма доказана.
С учётом доказанных лемм 7, 8, 9 в системе аксиом Фаддеева может быть доказана:
Теорема 1. Справедливо представление функции :
(4.39)
Доказательство. Рассмотрим случай n = 2
Пусть - при натуральных г и s. Применим лемму 1.1.6 к соединив аргументы в две группы из r и s - r элементов. Получим:
Отсюда
В силу непрерывности Н(р,1 - р) полученная формула может быть распространена и на иррациональные значения р. Постоянная С > 0 в силу положительности Н(р ,1- р), хотя бы в одной точке.
Переход к общему случаю осуществляется методом математической индукции на основании аксиомы 3'.
Выводы этой фундаментальной теоремы Д. К. Фаддеева о представлении функции энтропии для дискретной вероятностной схемы позволят в дальнейшем характеризовать производительность источника информации, оценивать возможности сжатия информации, получить формулу для вычисления пропускной способности дискретного канала связи.