ОТЧЕТ
ПО ЛАБОРАТОРНОЙ РАБОТЕ
по дисциплине «Информационные технологии»
ИССЛЕДОВАНИЕ СВОЙСТВ ЭНТРОПИИ ДИСКРЕТНОГО ИСТОЧНИКА
2012

Реферат

Отчет по лабораторной работе 9 с., 1 ч., 2 рис., 2 табл., 4 источ., 1 прил.
ТЕОРИЯ ИНФОРМАЦИИ, КОЛИЧЕСТВО ИНФОРМАЦИИ, ВЕРОЯТНОСТЬ, ШЕННОН, МЕРА НЕОПРЕДЕЛЕННОСТИ, ЭНТРОПИЯ, ДИСКРЕТНЫЙ ИСТОЧНИК
Предметом исследования являются формулы К. Шеннона для вычисления количества информации в сообщениях дискретного источника и его энтропии, а также простейшие модели дискретных источников.
Цель работы – исследование свойств энтропии как количественной меры неопределенности дискретного источника.
В ходе работы проводились теоретические исследования энтропии, а также численное моделирование простейших дискретных стационарных и нестационарных источников.
В результате аналитических исследований были найдены условия минимального и максимального значения энтропии. Численно были получены значения энтропии стационарных источников двух и нескольких видов сообщений. Произведено моделирование и исследована динамика изменения энтропии нестационарного источника.
Количественная оценка значения энтропии применяется при моделировании и кодировании источников.

Введение

Понятие информации предполагает наличие двух объектов: источника информации и потребителя [1, 2]. Информация представляется в виде специальных знаков, символов; характерным носителем информации является сообщение, под которым обычно понимают все то, что подлежит передаче. Статистический подход к оценке качества информации представлен в обширном разделе кибернетики – теории информации, которая занимается математи¬ческим описанием и оценкой методов передачи, хранения, извлече¬ния и классификации информации.
Основы теории информации были заложены в 1948 г. американским математиком К. Шенноном, который ввел понятие энтропии как меры неопределенности источника и количества информации через изменение этой неопределенности.
Пусть имеется дискретный источник, заданный ансамблем сообщений X = {x1, x2, … xN} и вероятностями формирования этих сообщений P = {p1, p2, … pN}. В силу свойств ансамбля, сообщения множества X являются несовместными событиями и
∑ pi = 1.    (1)
Количество собственной информации Ii, содержащееся в конкретном сообщении xi, может быть найдено по следующей формуле:
Ii = – log pi ,    (2)
где pi – вероятность появления этого сообщения. Единицы измерения количества информации определяет основание логарифма. Использование логарифма по основанию два дает результат в битах.
Среднее значение (математическое ожидание) собственной ин¬формации назы¬вается энтропией. Для дискретного источника сообщений случайная величина собственной ин-формации принимает значения I1, I2, … IN c вероятностями p1, p2, … pN соответственно, и ее мат. ожидание может быть найдено следующим образом:
H = M[Ii] = ∑ pj Ij  = –∑ pj log pj,    (3)
где j = 1 .. N. В случае pj = 0 слагаемое pj log pj принимается равным нулю. Единицы измерения определяются основанием логарифма.
Малые значения энтропии источника говорят о его малой информативности; большие – о неопределенности того, какое именно сообщение будет сформировано источником в определенный момент. Значение энтропии в битах определяет минимальный размер двоичного кода (на одно сообщение в среднем), необходимого для взаимнооднозначного кодирования сообщений источника.
Целью данной лабораторной работы является исследование свойств энтропии, предложенной Шенноном, как количественной меры неопределенности дискретного источника.
Оформление отчета по лабораторной работе было выполнено согласно требованиям ГОСТ.

1 Основные свойства энтропии дискретного источника

1.1 Минимальное значение энтропии

Формула энтропии (3) зависит только от вероятностей P. Рассмотрим функцию (– pi)log pi в случаях pi = 0, pi (0; 1) и pi = 1.
В случае pi = 0 произведение (– pi)log pi (неопределенность вида 0) полагается равным своему предельному значению – нулю. В случае pi = 1 произведение (– pi)log pi обращается в ноль в силу свойств логарифма. При pi (0; 1) величина log pi всегда отрицательна, а произведение ( pi)log pi больше нуля.
Следовательно, энтропия как сумма слагаемых вида (– pi)log pi является неотрицательной функцией. Нулевое значение энтропии возможно только при обращении в ноль всех ее слагаемых, что возможно в случае, когда вероятность одного из сообщений равна единице, а другие сообщения невозможны. Таким образом, минимальным значением энтропии является ноль.

1.2 Максимальное значение энтропии

Энтропия достигает максимального значения, когда вероятности появления возможных сообщений одинаковы (p1 = p2 = … = pN = 1/N ), что может быть доказано методом неопределенных множителей Лагранжа [3]. Следовательно, максимальное значение энтропии (3) составит
Hmax = –∑ (1/N) log (1/N) = log N .    (4)

1.3 График энтропии источника с двумя состояниями

Пусть источник формирует всего два вида сообщений с вероятностью P = {p1, p2}. Из (1) следует, что p2 = 1 – p1, следовательно, энтропия (3) является функцией одной переменной. График энтропии такого источника представлен на рисунке 1.

Рисунок 1 – График энтропии источника с двумя состояниями

Энтропия источника с двумя состояниями u1 и u2 при изменении соотношения их вероятностей p(u1)=p и p(u2)=1-p определяется выражением:
H(U) = -[p log p + (1-p) log (1-p)],
и изменяется от 0 до 1, достигая максимума при равенстве вероятностей.
Отсюда следует, что количество передаваемой инфор¬мации можно увеличить не только за счет числа сооб¬щений, но и путем повышения энтропии источника, т. е. информационной емкости его сообщений.

2 Вычисление энтропии простейших систем

2.1 Идеальная монета

Результат броска идеальной монеты может быть представлен в виде стационарного источника с двумя равновероятными состояниями. Имея P = {0,5; 0,5}, вычислим значение энтропии в битах по формуле (3):
H = –∑ pj log2 pj = – 0,5 log2 0,5 – 0,5 log2 0,5 = 0,5 бит + 0,5 бит = 1 бит.        (5)

Согласно (4) полученное значение является максимально возможным значением энтропии системы с двумя состояниями.

2.2 Фальшивая монета

Фальшивая монета имеет смещенный центр тяжести, из-за чего вероятности выпадения «орла» или «решки» различны. Представим результат броска такой монеты в виде источника с двумя неравновероятными состояниями, положим P = {0,23; 0,77} и вычислим значение энтропии в битах по формуле (3):
H = –∑ pj log2 pj = – 0,2 log2 0,2 – 0,8 log2 0,8 = 0,7219 бит      (6)
Полученное в (6) значение энтропии меньше значения энтропии (5), что говорит о меньшей неопределенности результата броска фальшивой монеты. Действительно, результат броска фальшивой монеты более предсказуем: сторона, ближе к которому смещен центр тяжести, чаще будет оказываться снизу.

2.3 Игральная кость

Результатом броска игральной кости является случайная дискретная величина, принимающая шесть равновероятных значений: P = {0,166; 0,166; 0,166; 0,166; 0,166; 0,166}
H = –∑ pj log2 pj = – 0,166 log6 0,166 -0,166 log6 0,166 – 0,166 log6 0,166 – 0,166 log6 0,166 – 0,166 log6 0,166 – 0,166 log6 0,166 =1 бит                      (7)

2.4 Фальшивая игральная кость

Предположим, что в игральной кости центр тяжести смещен так, чтобы шестерка выпадала более часто (единица на противоположной грани кости будет выпадать реже; значения 2÷5 выпадают по-прежнему с вероятностью 1/6). Пусть вероятности составят, например, P = {0,31; 0,17; 0,17; 0,17; 0,17; 0,01}
H = –∑ pj log2 pj = – 0,31 log6 0,31 -0,17 log6 0,17 – 0,17 log6 0,17- 0,17 log6 0,17 – 0,17 log6 0,17- 0,01 log6 0,01=0,9008 бит   (8)
Полученное в (8) значение энтропии меньше значения энтропии (7), что говорит о меньшей неопределенности результата броска фальшивой игральной кости.

3 Вычисление энтропии нестационарного дискретного источника

Для стационарных источников вероятности сообщений не изменяются во времени, следовательно, значение энтропии также остается постоянным. Рассмотрим нестационарный источник, о котором априорно известно:
–    мощность ансамбля сообщений (число возможных сообщений) N = 14;
–    множество сообщений (в данном случае, букв) X ={а,л,ы,м,о,в,_,т,р};
множество абсолютных частот этих сообщений F0 = {5,1,1,2,1,1,1,1,1}, которые следует уменьшать на единицу для каждого принятого сообщения.
Пусть таким источником была сформирована строка “алымова_тамара”. Перед принятием первой буквы частоты составляли F0 . После принятия буквы “а” частота, соответствующая этой букве, уменьшается на единицу; F1 ={4,1,1,2,1,1,1,1,1} Таблица А.1 приложения А содержит последовательные вычисления Fk, где k – количество принятых сообщений (букв), fk∑ – сумма всех частот Fk (кол-во сообщений, которые следует ожидать), sk – (k + 1)-е принятое сообщение.
Перед принятием (k + 1)-го сообщения на основе имеющихся частот Fk и свойства полноты вероятностей (1) может быть найдено распределение вероятностей Pk следующим образом:
pki = fki / fk∑ ,    (7)
где i = 1 .. N ; fk∑ – сумма всех fki в Fk . Имея вероятности Pk перед принятием (k + 1)-го сообщения по формуле (3) может быть найдено значение энтропии источника Hk. Построим таблицу А.2 значений Pk и Hk, подобную таблице А.1, где pk∑ – сумма вероятностей для проверки условия (1).
Полученные значения Hk, представленные в таблице А.1, отображены графически на рисунке 2.

Рисунок 2 – Гистограмма значений энтропии перед принятием каждого сообщения
Как подтверждает гистограмма, значение энтропии нестационарного источника меняется с изменением значений вероятностей. В данном примере начальное значение энтропии H0 перед принятием первого сообщения – буквы “а” – составляет 0,89 бит; по мере уточнения вероятностей не принятых сообщений энтропия в среднем все более уменьшается; при принятии последней буквы H14 = 0 (никакой определенности нет, так как из частот F14 достоверно следует, что последним сообщением будет буква “а”).

Заключение

В результате выполнения работы изучен необходимый теоретический материал: рассмотрено понятие и основные свойства энтропии, ее формула.
В данной лабораторной работе в соответствии с вариантом задания, решены все задачи в полном объеме. Получены практические навыки расчёта информационных характеристик источников дискретных сообщений средствами MS Excel.
Понятие энтропии является одним из фундаментальных свойств любых систем с вероятностным поведением. Энтропия находится во всем. В природе, в человеке, в различных науках.
Деятельность людей всегда связана с передачей информации. Эффективная организация обмена информацией приобретает всё большее значение, прежде всего, как условие успешной практической деятельности людей. Объём информации, необходимой для нормального функционирования современного общества, растёт примерно пропорционально квадрату развития производительных сил. Практическая значимость работы состоит в том, что подход к информации как к мере уменьшения неопределенности знаний позволяет количественно ее измерять. Следует ожидать, что идеи и методы теории информации, касающиеся источников сообщений, сигналов и каналов, будут успешно использоваться в дальнейшем, особенно при создании сложных систем, объединяющих различные по целям, функциям и даже физическому воплощению подсистемы.
Таким образом, задание на лабораторную работу выполнено в полном объёме.

Список использованных источников

1 Советов, Б. Я. Информационная технология [Текст] : Учеб. для студ. вузов по спец. «Автоматизир. системы обраб. информ. и управления» / Б. Я. Советов. – М. : Высш. шк., 1994. – 366 c.
2 Дмитриев, В. И. Прикладная теория информации [Текст] : Учеб. для студ. вузов по спец. «Автоматизированные системы обработки информации и управления» / В. И. Дмитриев. – М. : Высш. шк., 1989. – 320 с. : ил.
3 Кушниренко А.Г. и др. [Текст]: Проб. учеб. для сред. учеб. заведений «Основы информатики и вычислительной техники», 2 -е изд. – М.: Просвещение, 1991. – 302с.
4 Теоретические основы информационных процессов [Текст] : Учеб. пособие для вузов по спец. «Автоматизация и механизация процессов обработки и выдачи информации» / Л. Ф. Куликовский, В. В. Мотов. – М. : Высш. шк., 1987. – 248 с.

Приложение А

Таблицы расчета состояния нестационарного источника
Таблица А.1 – Динамика частот сообщений при принятии строки
k    Fk    м    fk
а    л    ы    м    о    в    _    т    р
1    5    1    1    2    1    1    1    1    1    а    14
2    4    1    1    2    1    1    1    1    1    л    12
3    4    0    1    2    1    1    1    1    1    ы    11
4    4    0    0    2    1    1    1    1    1    м    10
5    4    0    0    1    1    1    1    1    1    о    9
6    4    0    0    1    0    1    1    1    1    в    8
7    4    0    0    1    0    0    1    1    1    а    7
8    3    0    0    1    0    0    1    1    1    _    6
9    3    0    0    1    0    0    0    1    1    т    5
10    3    0    0    1    0    0    0    0    1    а    4
11    2    0    0    1    0    0    0    0    1    м    3
12    2    0    0    0    0    0    0    0    1    а    2
13    1    0    0    0    0    0    0    0    1    р    1
14    1    0    0    0    0    0    0    0    0    а    0
Таблица А.2 – Динамика вероятностей и энтропии при принятии строки
k    Fk    Sks    Pks    Hks
а    л    ы    м    о    в    _    т    р
1    0,357    0,071    0,071    0,143    0,071    0,071    0,071    0,071    0,071    а    1    0,894418
2    0,333    0,083    0,083    0,167    0,083    0,083    0,083    0,083    0,083    л    1    0,962287
3    0,364    0    0,091    0,182    0,091    0,091    0,091    0,091    0,091    ы    1    0,705331
4    0,4    0    0    0,2    0,1    0,1    0,1    0,1    0,1    м    1    0,837282
5    0,444    0    0    0,111    0,111    0,111    0,111    0,111    0,111    о    1    0,830698
6    0,5    0    0    0,125    0    0,125    0,125    0,125    0,125    в    1    0,749229
7    0,571    0    0    0,143    0    0    0,143    0,143    0,143    а    1    0,651608
8    0,5    0    0    0,167    0    0    0,167    0,167    0,167    _    1    0,701376
9    0,6    0    0    0,2    0    0    0    0,2    0,2    т    1    0,578984
10    0,75    0    0    0,25    0    0    0    0    0,25    а    1    0,098197
11    0,667    0    0    0,333    0    0    0    0    0,333    м    1    0,456357
12    1    0    0    0    0    0    0    0    0,5    а    1    0,157732
13    1    0    0    0    0    0    0    0    1    р    1    0
14    1    0    0    0    0    0    0    0    0    а    1    0

Скачать одним архивом (бесплатно):