- •Сибирский государственный аэрокосмический университет
- •© Сибирский государственный аэрокосмический университет имени академика м. Ф. Решетнева, 2007
- •Оглавление
- •Предисловие
- •1. Информационная метрика
- •1.1. Энтропия и ее свойства
- •1.2. Энтропия сложной системы
- •1.3. Условная энтропия. Объединение зависимых систем
- •1.4. Определение информационных потерь в каналах связи
- •2. Кодирование информации
- •2.1. Количественное определение избыточности в сообщениях
- •2.2. Оптимальное неравномерное кодирование
- •2.2.1. Кодирование методом шеннона-фано
- •2.2.2. Кодирование методом хаффмана
- •2.2.3. Кодирование методом хаффмана. Кодовое дерево
- •2.2.4. Определение оптимальности закодированных сообщений
- •2.3. Корректирующие коды
- •2.3.1. Код хемминга
- •2.3.2. Линейные групповые коды
- •3. Указания к выполнению лабораторных работ
- •3.1. Лабораторная работа № 1
- •3.2. Лабораторная работа № 2
- •3.3. Лабораторная работа № 3
- •3.4. Лабораторная работа № 4
- •3.5. Лабораторная работа № 5
- •Заключение
- •Библиографический список
1.1. Энтропия и ее свойства
Рассмотрим некоторую систему Х, которая может принимать конечное множество состояний х1, х2, ... хn. Вероятность возникновения каждого состояния р1, р2, ... рn.
Примером системы Х может быть алфавит, у которого под множеством состояний понимаются символы алфавита
В качестве меры неопределенности этой системы в теории информации применяется специальная характеристика, называемая энтропией.
Энтропией системы может быть определена как сумма произведений вероятностей различных состояний системы на логарифмы этих вероятностей, взятая с обратным знаком.
(1)
Энтропия обладает рядом свойств:
1. Энтропия системы всегда больше нуля.
2. Энтропия обращается в ноль, когда одно из состояний достоверно, а другие невозможны.
3. Энтропия принимает максимальное значение, когда все состояния равновероятны.
4. Энтропия обладает свойством аддитивности, когда несколько систем объединяются в одну, их энтропии складываются.
Рассмотрим простейший случай. Система имеет два состояния и эти состояния равновероятны.
хi |
х1 |
х2 |
рi |
0,5 |
0,5 |
По формуле (1) имеем:
Н(х)=-(0,5log2 0,5+0,5log20,5)=1 бит/символ
Логарифм в формуле может быть взят при любом основании а>1. Выбор основания равносилен выбору определенной единицы измерения энтропии. На практике удобнее всего пользоваться логарифмами при основании два и измерять энтропию в двоичных единицах или битах. Таким образом, это энтропия одного двоичного числа, если он с одинаковой вероятностью может быть нулем или единицей.
Для вычисления энтропии вводят специальную функцию:
,
Тогда формула энтропии примет следующий вид:
При выполнении преобразований часто более удобной оказывается другая форма записи энтропии, а именно, представление ее в виде математического ожидания
,
где logР(х) – логарифм вероятности любого(случайного) состояния системы, рассматриваемый как случайная величина.
1.2. Энтропия сложной системы
Под объединением двух систем X и Y с возможными состояниями x1, x2, …, xn, y1, y2, …, ym понимается сложная система (X, Y), состояние которой (xi,yj) представляют собой все возможные комбинации состояний xi,yj . При этом число возможных состояний системы (X, Y) равно nm.
В качестве примера сложной системы может быть взят алфавит, имеющий двухбуквенные сочетания.
Обозначим pij вероятность того, что система (X, Y) будет находиться в состоянии (xi,yj). Тогда вероятности pij можно представить в виде таблицы.
|
x1 |
x2 |
… |
xn |
y1 |
p11 |
p21 |
… |
pn1 |
y2 |
p12 |
p22 |
… |
pn2 |
… |
… |
… |
… |
… |
ym |
p1m |
p2m |
… |
pnm |
Энтропия сложной системы равняется сумме произведений вероятностей всех возможных ее состояний на их логарифмы с обратным знаком
.
Энтропию сложной системы, как и энтропию простой, тоже можно записать в форме математического ожидания
.
Если системы X и Y независимы одна от другой, то при объединении систем их энтропии складываются
.
Это положение называется теоремой сложения энтропий.