Логарифмом числа а по основанию b называется показатель степени, в которую надо возвести число a, чтобы получить число b.

a ^log_a^b = b, a > 0, b > 0, a ≠ 1

Вычисление логарифмов чисел по основанию 2 с помощьюэлектронного калькулятора

log₂ 6 = log 6 / log 2, где log 6 и log 2 – десятичные логарифмы

Программа вычисления логарифма числа 6 по основанию 2 (log₂ 6) с помощью инженерного калькулятора: 6, log, /, 2, log, =

Количество информации в случае различных вероятностей событий определяется по формуле:
Формула Шеннона: (американский учёный, 1948 г.)

где Pi – вероятность i-го события, N – количество возможных событий

Задача. В озере живут караси и окуни. Подсчитано, что карасей 1500, а окуней - 500. Сколько информации содержится в сообщениях о том, что рыбак поймал карася, окуня, поймал рыбу?

Решение.
События поимки карася или окуня не являются равновероятными, так как окуней в озере меньше, чем карасей.

Общее количество карасей и окуней в пруду 1500 + 500 = 2000.
Вероятность попадания на удочку карася

p₁ = 1500/2000 = 0,75, окуня p₂ – 500/2000 = 0,25.

I₁ = log2(1/p1), I₁ = log2(1/p2), где I₁ и I₂ – вероятности поймать карася и окуня соответственно.

I₁ = log2(1 / 0,75)» 0,43 бит, I₂ = log2(1 / 0,25)» 2 бит – количество информации в сообщении поймать карася и поймать окуня соответственно.

Количество информации в сообщении поймать рыбу (карася или окуня) рассчитывается по формуле Шеннона

I = - p₁log2p1 - p₂log2p2

I = - 0,75*log20,75 - 0,25*log20,25 = - 0,75*(log0,75/log2)-0,25*(log0,25/log2) =

= 0,604 бит» 0.6 бит.

Ответ:в сообщении содержится 0,6 бит информации

Отчет

Отчет должен быть оформлен в текстовом редакторе и содержать:

¾ наименование работы;

¾ цель работы;

¾ задание;

¾ последовательность выполнения работы;

¾ ответы на контрольные вопросы;

¾ вывод о проделанной работе.

Контрольные вопросы

1. Какое количество информации несет в себе жесткий диск емкостью 4 терабайта, если производитель рассчитывает 1000 за 1024?

2. Чем отличается вероятностный подход к измерению информации от алфавитного?

3. Какие единицы измерения информации используют для флэш-накопителей?

 

 

Практическое занятие № 3

Тема программы: Способы измерения информации.

Тема:Скорость передачи информации.

Цель: научиться измерять и вычислять скорость передачи информацию.

Время выполнения: 2 часа

Оборудование: ПК.

Раздаточный материал: дидактический материал

Программное обеспечение: операционная система, текстовый редактор.

 

Теоретические основы

Скорость передачи информации определяется количеством элементов двоичной информации,, передаваемых за 1 с.В синхронной передачиданных по коммутируемым каналамрекомендуется использовать скоростииз следующего ряда: 600, 1200, 2400, 4800, 9600 бит/с.Для асинхронной передачи по коммутьируемым каналм рекомегндуется скорость 300 бит/с.

В синхронной передачиданных по арендованным каналам рекомендуется использовать скоростииз следующих рядов:

а) предпочтительные: 600, 1200, 2400, 4800, 9600, 14400 бит/с;

б) дополнительные: 3000, 6000, 7200, 12000 бит/с;

в) допустимого диапазона: Nx600 бит/с (1<=N<=24)

Следует отличать скорость передачи информации от модуляционной (линейной) скорости, измеряемой в Бодах (количество элементовмодулированного сигнала, передаваемого за 1 с). Для простых видовмодуляции скоростьпередачи информации совпадает с модуляционной скоростью.

При синхронной передаче скорость должна отличаться от номинального значения не более, чем на 0,01%, а при асинхронной – неболее, чем на 2,5%.

Оба компьютера, как правило, могут одновременно обмениваться информацией в обе стороны. Этот режим работы называется полным дуплексным.

Дуплексный режим передачи данных – режим, при котором передача данных осуществляется одновременно в обоих направлениях.

В отличие от дуплексного режима передачи данных, полудуплексный подразумевает передачу в каждый момент времени только в одном направлении.

Кроме собственно модуляции и демодуляции сигналов модемы могут выполнять сжатие и декомпрессию пересылаемой информации, а также заниматься поиском и исправлением ошибок, возникнувших в процессе передачи данных по линиям связи.

Одной из основных характеристик модема является скорость модуляции (modulation speed), которая определяет физическую скорость передачи данных без учета исправления ошибок и сжатия данных. Единицей измерения этого параметра является количество бит в секунду (бит/с), называемое бодом.

Любой канал связи имеет ограниченную пропускную способность (скорость передачи информации), это число ограничивается свойствами аппаратуры и самой линии (кабеля).

Объем переданной информации вычисляется по формуле Q=q*t, где q – пропускная способность канала (в битах в секунду), а t – время передачи

Пример 1. Скорость передачи данных через ADSL-соединение равна 128000 бит/c. Через данное соединение передают файл размером 625 кбайт. Определить время передачи файла в секундах.

Решение:

1) выделим в заданных больших числах степени двойки и переведем размер файла в биты, чтобы «согласовать» единиц измерения:

128000 бит/c = 128 · 1000 бит/с = 27 · 125 · 8 бит/с = 27 · 53 · 23 бит/с = 210·53 бит/с

625 кбайт = 54 кбайт = 54 · 213 бит.

2) чтобы найти время передачи в секундах, нужно разделить размер файла на скорость передачи:

t=(54 · 213)бит / 210·53 бит/с = 40 с.

Ответ: 40 с.

Пример 2. Скорость передачи данных через ADSL-соединение равна 512000 бит/c. Передача файла через это соединение заняла 1 минуту. Определить размер файла в килобайтах.

Решение:

1) выделим в заданных больших числах степени двойки; переведем время в секунды (чтобы «согласовать» единицы измерения), а скорость передачи – в кбайты/с, поскольку ответ нужно получить в кбайтах:

1 мин = 60 с = 4 · 15 с = 22 · 15 с

512000 бит/c = 512 · 1000 бит/с = 29 · 125 · 8 бит/с = 29 · 53 · 23 бит/с = 212 · 53 бит/с = 29 · 53 бит/с = (29 · 53) / 210 кбайт/с = (53 / 2) кбайт/с

2) чтобы найти объем файла, нужно умножить время передачи на скорость передачи:

Q=q*t = 22 · 15 с *(53 / 2) кбайт/с = 3750 кбайт

Ответ: 3750 кбайт.

Пример 3. C помощью модема установлена связь с другим компьютером со скоростью соединения 19200, с коррекцией ошибок и сжатием данных.
а) Можно ли при таком соединении файл размером 2,6 килобайт передать за 1 секунду? Обоснуйте свой ответ.
б) Всегда ли при таком соединении файл размером 2,3 килобайт будет передаваться за 1 секунду? Обоснуйте свой ответ.
в) Можно ли при таком соединении оценить время передачи файла размером 4 Мб? Если можно, то каким образом?

Решение:

а) Для начала узнаем, какое количество килобайт мы можем передать за 1 секунду: 19200/1024/8 = 2,3 (Кбайт). Следовательно, если бы не было сжатия информации, то данный файл за одну секунду при данной скорости соединения было бы невозможно передать. Но сжатие есть, 2.6/2.3 < 4, следовательно, передача возможна.
б) Нет не всегда, так как скорость соединения это максимально возможная скорость передачи данных при этом соединении. Реальная скорость может быть меньше.
в) Можно указать минимальное время передачи этого файла: 4*1024*1024/4/19200, около 55 с (столько времени будет передаваться файл на указанной скорости с максимальной компрессией). Максимальное же время передачи оценить вообще говоря нельзя, так как в любой момент может произойти обрыв связи.

 

Практические задания

Задание 1. Решите задачу о передаче информации с помощью модема.

Вариант 1	Скорость передачи данных через АDSL-соединение равна 512000 бит/с. Через данное соединение передают файл размером 1500 Кб. Определите время передачи файла в секундах.
Вариант 2	Скорость передачи данных через АDSL-соединение равна 1024000 бит/с. Через данное соединение передают файл размером 2500 Кб. Определите время передачи файла в секундах.
Вариант 3	Скорость передачи данных через АDSL-соединение равна 1024000 бит/с. Передача файла через данное соединение заняла 5 секунд. Определите размер файла в килобайтах.
Вариант 4	Скорость передачи данных через АDSL-соединение равна 512000 бит/с. Передача файла через данное соединение заняла 8 секунд. Определите размер файла в килобайтах.

Задание 2. Решите задачу о передаче графической информации.

Вариант 1	Определите скорость работы модема, если за 256 с он может передать растровое изображение размером 640х480 пикселей. На каждый пиксель приходится 3 байта.
Вариант 2	Сколько секунд потребуется модему, передающему информацию со скоростью 56 000 бит/с, чтобы передать цветное растровое изображение размером 640 х 480 пикселей, при условии, что цвет каждого пикселя кодируется тремя байтами?
Вариант 3	Определите скорость работы модема, если за 132 с он может передать растровое изображение размером 640х480 пикселей. На каждый пиксель приходится 3 байта.
Вариант 4	Сколько секунд потребуется модему, передающему информацию со скоростью 28800 бит/с, чтобы передать цветное растровое изображение размером 640 х 480 пикселей, при условии, что цвет каждого пикселя кодируется тремя байтами?

Отчет

Отчет должен быть оформлен в текстовом редакторе и содержать:

¾ наименование работы;

¾ цель работы;

¾ задание;

¾ последовательность выполнения работы;

¾ ответы на контрольные вопросы;

¾ вывод о проделанной работе.

Контрольные вопросы

1. Дайте определение пропускной способности (передача информации)?

2. В чем измеряется пропускная способность?

3. Зависит ли скорость передачи информации от объема передаваемой информации?

Практическое занятие № 4

Тема программы: Способы измерения информации.

Тема:Поиск энтропии случайных величин.

Цель: научиться вычислять энтропию случайной величины.

Время выполнения: 2 часа

Оборудование: ПК.

Программное обеспечение: операционная система, калькулятор, текстовый редактор.

Теоретические основы

Энтропия в теории информации — мера хаотичности информации, неопределённость появления какого-либо символа первичного алфавита. При отсутствии информационных потерь численно равна количеству информации на символ передаваемого сообщения.

Так, возьмём, например, последовательность символов, составляющих какое-либо предложение на русском языке. Каждый символ появляется с разной частотой, следовательно, неопределённость появления для некоторых символов больше, чем для других. Если же учесть, что некоторые сочетания символов встречаются очень редко, то неопределённость ещё более уменьшается (в этом случае говорят об энтропии n-ого порядка.Концепции информации и энтропии имеют глубокие связи друг с другом, но, несмотря на это, разработка теорий в статистической механике и теории информации заняла много лет, чтобы сделать их соответствующими друг другу.

Энтропия независимых случайных событий x с n возможными состояниями (от 1 до n) рассчитывается по формуле:

Эта величина также называется средней энтропией сообщения. Величина называется частной энтропией, характеризующей только i-e состояние.

Таким образом, энтропия события x является суммой с противоположным знаком всех произведений относительных частот появления события i, умноженных на их же двоичные логарифмы (основание 2 выбрано только для удобства работы с информацией, представленной в двоичной форме). Это определение для дискретных случайных событий можно расширить для функции распределения вероятностей.

Шеннон вывел это определение энтропии из следующих предположений:

§ мера должна быть непрерывной; т. е. изменение значения величины вероятности на малую величину должно вызывать малое результирующее изменение энтропии;

§ в случае, когда все варианты (буквы в приведенном примере) равновероятны, увеличение количества вариантов (букв) должно всегда увеличивать полную энтропию;

§ должна быть возможность сделать выбор (в нашем примере букв) в два шага, в которых энтропия конечного результата должна будет является суммой энтропий промежуточных результатов.

Шеннон показал, что любое определение энтропии, удовлетворяющее этим предположениям, должно быть в форме:

где K — константа (и в действительности нужна только для выбора единиц измерения).

Шеннон определил, что измерение энтропии (H = − p₁ log₂ p₁ − … − p_n log₂ p_n), применяемое к источнику информации, может определить требования к минимальной пропускной способности канала, требуемой для надежной передачи информации в виде закодированных двоичных чисел. Для вывода формулы Шеннона необходимо вычислить математическое ожидания «количества информации», содержащегося в цифре из источника информации. Мера энтропии Шеннона выражает неуверенность реализации случайной переменной. Таким образом, энтропия является разницей между информацией, содержащейся в сообщении, и той частью информации, которая точно известна (или хорошо предсказуема) в сообщении. Примером этого является избыточность языка — имеются явные статистические закономерности в появлении букв, пар последовательных букв, троек и т.д.

В общем случае b-арная энтропия (где b равно 2,3,...) источника = (S, P) с исходным алфавитом S = { a ₁, …, a_n } идискретным распределением вероятности P = { p ₁, …, p_n } где p_i является вероятностью a_i (p_i = p (a_i)) определяется формулой:

Определение энтропии Шеннона очень связано с понятием термодинамической энтропии. Больцман и Гиббс проделали большую работу по статистической термодинамике, которая способствовала принятию слова «энтропия» в информационную теорию. Существует связь между понятиями энтропии в термодинамике и теории информации. Например, демон Максвеллатакже противопоставляет термодинамическую энтропию информации, и получение какого-либо количества информации равно потерянной энтропии.

СВОЙСТВА ЭНТРОПИИ

1. Энтропия является вещественной и неотрицательной величиной.

2. Энтропия – величина ограниченная.

3. Энтропия обращается в нуль лишь в том случае, если вероятность одного из состояний равна единице; тогда вероятности всех остальных состояний, естественно, равны нулю. Это положение соответствует случаю, когда состояние источника полностью определено.

4. Энтропия максимальна, когда все состояния источника равновероятны.

5. Энтропия источника и с двумя состояниями u1 и u2 изменяется от нуля до единицы, достигая максимума при равенстве их вероятностей:

р(и1) = р= р(u2) = 1 — р = 0,5.

6. Энтропия объединения нескольких статистически независимых источников информации равна сумме энтропии исходных источников.

7. Энтропия характеризует среднюю неопределенность выбора одного состояния из ансамбля. При ее определении используют только вероятности состояний, полностью игнорируя их содержательную сторону. Поэтому энтропия не может служить средством решения любых задач, связанных с неопределенностью.

8. Энтропия как мера неопределенности согласуется с экспериментальными данными, полученными при изуче­нии психологических реакций человека, в частности реакции выбора. Установлено, что время безошибочной реакции на последовательность беспорядочно чередующихся равновероятных раздражителей (например, загорающихся лампочек) растет с увеличением их числа так же, как энтропия. Это время характеризует неопределенность выбора одного раздражителя. Замена равновероятных раздражителей неравновероятными приводит к снижению среднего времени реакции ровно настолько, насколько уменьшается энтропия.

Дифференциальной энтропией случайной величины X называется величина:

H_Д(x)=H(x)-H(y)= -

Если произвести квантование случайных величин Х₁, Х₂…Х_n по уровню с числом уровней квантования равным m, то возможное число реализаций длительностью Т_n станет конечным и равным М = тⁿ.

Каждая из реализаций С₁, С₂,….С_i,…С_m будет иметь определенную вероятность появления в эксперименте по наблюдению реализаций. Тогда неопределенность (энтропия) и количество информации в реализации (в среднем по всем реализациям) определяются равенством

 

Энтропия и количество информации на одну степеньсвободы (на одну выборку) равны

Избыточность показывает, какая доля максимально возможной при заданном объеме алфавита неопределенности не используется источником.

=(H_max-H_u)/H_max,

Где Н_u – энтропия рассматриваемого источника, Н_max – максимально возможное значение его энтропии, которое может быть достигнуто подбором распределения и ликвидацией взаимозависимости элементов алфавита. Так, для дискретного источника с М элементами

H_max=logM

Выполнение расчетных задач

Задача №1

Доказать, что H(x,y)≤H(x)+H(y).

Решение:

По определению, .

Для статистически зависимых событий .

- это частная энтропия Y при условии, что известно состояние X=x_i.

Наличие информации о состоянии X не может увеличить неопределенность состояния Y, но может уменьшить его в случае зависимости Y от X. Значит, условная энтропия не больше безусловной энтропии , то есть . Тогда средняя условная энтропия ,

то есть .

Значит,

Задача №2

Показать, что для регулярной марковской цепи энтропия H(x)^(r) за r шагов равняется энтропии за один шаг, умноженной на число шагов r.

Решение:

Регулярная цепь Маркова полностью характеризуется матрицей переходных вероятностей и предельным стационарным распределением вероятностей состояний .

В стационарном режиме энтропия за один шаг не зависит от номера шага и равна ,

- стационарная вероятность k -го состояния,

- энтропия в k -м состоянии.

Энтропия за r шагов равна сумме энтропий за каждый шаг. Так как энтропия за каждый шаг одинакова, то сумма энтропий равна .

 

Задача №3

Вычислить энтропию H_д(x) распределения p_x(x) изображенного на рисунке.

Построить график зависимости H_д(x) в функции параметра d.

 

 

Ответ:

 

Решение:

Из условия нормировки .

Плотность данного распределения

Дифференциальная энтропия

.

Задача 4

В результате полной дезорганизации управления m самолетов летят произвольными курсами. Управление восстановлено, и все самолеты взяли общий курс со среднеквадратической ошибкой отклонения от курса σ=3⁰. Найти изменение энтропии, считая, что в первом случае имело место равномерное распределение вероятностей углов, а во втором случае – нормальное.

Ответ: 4.86 бита

Решение.

Начальное распределение вероятностей углов курсов самолетов равномерное в интервале от до с плотностью вероятности .

Дифференциальная энтропия этого распределения

бит.

Конечное распределение вероятностей углов курсов самолетов нормальное с параметрами и плотностью вероятности .

Дифференциальная энтропия этого распределения

Изменение энтропии бит.

Энтропия уменьшилась на 4,86 бит.

Задача 5

Измерительное устройство вырабатывает вре­менные интервалы, распределенные случайным образом в пределах от 100 до 500 мс. Как изменится энтропия случайной величины при изменении точности измерения с 1 мс до 1 мкс?

 

Ответ: Энтропия увеличивается примерно на 10 бит

Решение.

При точности 1мс дискретная случайная величина Х – результат измерения – может равновероятно принимать одно из значений. Энтропия равна .

При точности 1мкс дискретная случайная величина Х – результат измерения – может равновероятно принимать одно из значений. Энтропия равна .

Изменение энтропии

бит.

Энтропия увеличилась примерно на 10 бит.

 

Задача 6

Записать отношения между энтропиями:

H(x), H(y), H(x|y), H(y|x), H(x,y), H(x|y_j), H(y|x_i)

 

Решение.

Связь между энтропией совместного распределения и полными энтропиями и средними условными энтропиями

.

Если x и y независимы, то и энтропия совместного распределения максимальна, так как .

Связь между частными и средними условными энтропиями

.

 

Задача 7

На рисунке представлена диаграмма канала со слабым разрешением. Определить количество информации, передаваемое по каналу.

 

Ответ: I (x,y)=H(x)

Решение:

Количество переданной по каналу информации равно .

– энтропия полученных элементов y до отправления элемента x; - энтропия полученных элементов y после отправления элемента x. Для данного канала со слабым разрешением , так как полученный элемент y однозначно определяется по отправленному элементу x.

Получаем .

 

Задача 2

На рисунке представлена диаграмма канала с неоднозначностью. Определить количество информации, передаваемое по каналу.

ответ: I (x,y)=H(x)

 

Решение:

Количество переданной по каналу информации равно .

– энтропия отправленных элементов x до получения элемента y; - энтропия отправленных элементов x после получения элемента y. Для данного канала с неоднозначностью , так как полученный элемент y однозначно определяет отправленный элемент x.

Получаем .