Кодирование и измерение количества информации
Определение количества информации в сообщении в соответствии с формулой обобщенной гипергеометрической вероятности. Вычисление энтропии источника сообщений, который вырабатывает ансамбль независимых символов. Расчет экономности кода по методу Шеннона-Фено
| Рубрика | Математика |
| Вид | контрольная работа |
| Язык | русский |
| Дата добавления | 16.05.2014 |
| Размер файла | 49,5 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
- Содержание
- Задача 1
- Задача 2
- Задача 3
- Задача 4
- Задача 5
- Задача 6
- Литература
Задача 1
Условие задачи:
В урне 7 белых и 5 черных шаров. Из урны вынимают сразу 5 шаров. Какое количество информации содержится в сообщении о том, что 2 из них будут белыми?
Решение:
Количество информации в сообщении определяется по формуле:
Приведем обозначение задачи в соответствии с формулой обобщенной гипергеометрической вероятности. По условию задачи в урне 12 шаров.
|
Имеем |
Выбираем |
||
|
Черные шары |
5 |
3 |
|
|
Белые шары |
7 |
2 |
|
|
Всего |
12 |
5 |
P=
где p - вероятность наступления события (2 из 5 вынутых шаров белые),
число сочетаний из 5 по 3 (варианты выбора 3х черных шаров);
число сочетаний из 7 по 2 (варианты выбора 2х белых шаров).
P=
Количество информации в сообщении «два из пяти вынутых шаров белые»
I = - log(7/3168) = log(31288/7) = 8,8 бит.
Задача 2
Условие задачи:
Вычислить энтропию источника сообщений, который вырабатывает ансамбль независимых символов Х с частотами n.
Таблица 1
Частота появления для ансамбля независимых символов Х
|
n |
||||||||
|
2 |
1 |
2 |
3 |
14 |
1 |
23 |
2 |
Решение
Энтропия источника для случая неравновероятных и независимых сообщений определяется формулой:
(3)
H(X)= - [3*(2/48)*log(2/48) + 2*(1/48)*log(1/48) + (3/48)*log(3/48) +
(14/48)*log(14/48) + (23/48)*log(23/48)]= 2,08 бит
Задача 3
Условие задачи:
В двух урнах по n шаров, причем в первой урне k1 красных, b1 белых и c1 черных, а во второй соответственно - k2, b2 и с2 . Из каждой урны вынимается по одному шару. Определить, для какой урны исход опыта является более определенным.
Таблица 2
Данные для задачи 3
|
K1 |
B1 |
C1 |
K2 |
B2 |
C2 |
|
|
6 |
3 |
11 |
3 |
7 |
10 |
Решение:
Определим энтропию для каждой из урн:
А) В первой урне 6 красных, 3 белых и 11 черных шара, всего 20 шаров.
Вероятность, что вынутый шар будет красным
P1 = 6/20 = 0,3
Вероятность, что вынутый шар будет белый
P1 = 3/20 = 0,15
Вероятность, что вынутый шар будет черным
P2 = 11/20 = 0,55
Энтропия
H = - (0,3*log0,3+0,15*log 0,15+0,55*log 0,55)= 1,406 бит
Б) Во второй урне 3 красных, 7 белых и 10 черных шара, всего 20 шаров.
Вероятность, что вынутый шар будет красным
P1 = 3/20 = 0,15
Вероятность, что вынутый шар будет белым:
P2 = 7/20 = 0,35
Вероятность, что вынутый шар будет черным
P3 = 10/20 = 0,5
Энтропия
H =- (0,15*log0,15+0,35*log0,35+0,5*log0,5) = 1,4406 бит
Вывод: для первой урны исход опыта более определен.
Задача 4
Условие задачи:
Закодировать по методу Шеннона-Фено следующее сообщение и найти экономность кода.
Решение
Длина сообщения 26 символов, всего 16 различных символов:
2 буквы «м», частота 2/26
1 буква «я», частота 1/26
2 буквы «к», частота 2/26
4 буквы «и», частота 4/26
1 буква «н», частота 1/26
2 буквы «а», частота 2/26
2 буквы «л», частота 2/26
2 буквы «е», частота 2/6
1 буква «с», частота 1/26
1 буква «й», частота 1/26
2 буквы «в», частота 2/26
1 буква «д», частота 1/26
1 буква «р», частота 1/26
1 буква «о», частота 1/26
1 буква «ч», частота 1/26
2 знака пробела (нижнее подчеркивание) частота 2/26.
1. Построим таблицу частот (Таблица 2), запишем в таблицу частоты ni и вероятности pi = ni /N для каждой буквы
гипергеометрический вероятность энтропия код
Таблица 3
Вероятности каждой буквы
|
х |
и |
к |
м |
а |
л |
е |
я |
н |
с |
й |
в |
д |
р |
о |
ч |
_ |
|
|
n |
4 |
3 |
2 |
2 |
2 |
2 |
1 |
1 |
1 |
1 |
2 |
1 |
1 |
1 |
1 |
2 |
|
|
p |
0,15 |
0,12 |
0,08 |
0,08 |
0,08 |
0,08 |
0,04 |
0,04 |
0,04 |
0,04 |
0,08 |
0,04 |
0,04 |
0,04 |
0,04 |
0,08 |
2. Запишем символы (в порядке убывания частоты появления) для нашего набора символов в Таблицу 4.
Таблица 4
Кодирование по методу Шеннона - Фано
|
Символы |
Частота |
1е разбиение |
2е разбиение |
3е разбиение |
4е разбиение |
5е |
|
|
и |
0,15 |
0 |
0 |
0 |
|||
|
к |
0,08 |
1 |
0 |
||||
|
м |
0,08 |
1 |
|||||
|
а |
0,08 |
1 |
0 |
||||
|
л |
0,08 |
1 |
0 |
||||
|
е |
0,08 |
1 |
|||||
|
в |
0,08 |
1 |
0 |
0 |
0 |
||
|
пробел |
0,08 |
1 |
|||||
|
н |
0,04 |
1 |
0 |
||||
|
с |
0,04 |
1 |
|||||
|
я |
0,04 |
1 |
0 |
0 |
|||
|
д |
0,04 |
1 |
0 |
||||
|
р |
0,04 |
1 |
|||||
|
о |
0,04 |
1 |
0 |
||||
|
й |
0,04 |
1 |
0 |
||||
|
ч |
0,04 |
1 |
3. Разбиваем символы на 2 группы с приблизительно равными суммами вероятностей.
4. Присваиваем верхней группе 0, а нижней 1.
5. Каждую группу разбиваем по такому же принципу и присваиваем 0 и 1.
6. Продолжаем разбиение до тех пор, пока в каждой группе не останется по 1 символу.
7. Запишем кодовую таблицу (Таблица 5)
Таблица 5
Кодовая таблица для букв
|
И 000 |
К 0010 |
М 0011 |
А 010 |
|
|
Л 0110 |
Е 0111 |
В 1000 |
Пробел 1001 |
|
|
Н 1010 |
С 1011 |
Я 1100 |
Д 11010 |
|
|
Р 11011 |
О 1110 |
Й 11110 |
Ч 11111 |
Вычислим максимальную энтропию (предположим, что частота появления символов в сообщении одинакова)
Hmax = log216= 4
t ср(средняя длина кода) = =
= 0,15*3+0,08*3+5*0,08*4+4*0,04*4+4*0,04*5= 3,93
Экономичность - это отношение энтропии кода к максимальной энтропии в предположении, что все символы имеют одинаковую вероятность.
Вычислим экономичность кода, то есть отношение энтропии кода (средней длины кода) к максимальной энтропии:
Э = t ср/ Hmax= 3,393/4 = 0,9877
Значение экономичности близко к 1, значит код близок к оптимальному!
Задача 5
Условие задачи:
Найти
а) Избыточность R1 источника сообщений при статистический независимости букв;
б) избыточность R2 с учетом зависимости между буквами для сообщения «женьшень»
Решение:
Длина сообщения «женьшень» 8 символов, 5 букв, буквы встречаются с частотами:
«ж» 1/8
«е» 2/8
«н» 2/8
«ь» 2/8
«ш» 1/8
Вычислим энтропию
= -3*2/8*log(2/8)-2*1/8*log(1/8) = 3,25
H (A)на символ = 3,25/8= 0,468 бит/символ
Если бы все символы имели одинаковую частоту, энтропия источника сообщений была бы максимальна:
Hmax = log28 = 3 бит/символ
Избыточность R1 при передаче сообщения «женьшень» без учета статистической зависимости букв будет равна:
R1 = 1- (H(A)на символ/Hmax) = 1-(0,468/3) = 0,844
б) Избыточность с учетом статистической зависимости появления букв рассчитывается по формуле:
R2 = 1-H стат(А)/Hmax
Где Н стат= энтропия сообщения с учетом статистической зависимости появления букв.
Условные вероятности появления i ой буквы после k ой буквы в сообщении «женьшень»:
Таблица 6
Условные вероятности появления букв
|
i ая буква |
|||||||
|
k ая |
ж |
е |
н |
ь |
ш |
У pi/pk |
|
|
ж |
0 |
1 |
0 |
0 |
0 |
1 |
|
|
е |
0 |
0 |
1 |
0 |
0 |
1 |
|
|
н |
0 |
0 |
0 |
1 |
0 |
1 |
|
|
ь |
0 |
0 |
0 |
0 |
1 |
1 |
|
|
ш |
0 |
1 |
0 |
0 |
0 |
1 |
Энтропия двухбуквенного текста рассчитывается по формуле:
В случае передачи сообщения «женьшень»
0
H(A)статна символ=H(A) на символ =0,468 бит/символ
Избыточность R2 при передаче сообщения «женьшень» с учетом статистической зависимости букв будет равна R1:
R2=1- (H(A)статна символ/Hmax)=1-(0,468/3)=0,844
Задача 6
Условие задачи
Имеется источник информации с энтропией в единицу времени Н (бит) и К каналов связи; каждый из которых может передавать в единицу времени S бит. В результате помехи каждое значение бита заменяется противоположным с вероятностью Р.
Требуется выяснить: достаточна ли пропускная способность этих каналов для передачи информации, поставляемой источником?
Таблица 5
Данные для задачи
|
Н |
К |
S |
Р |
|
|
180 |
4 |
120 |
0.28 |
Решение
Определяем потерю информации из-за помех на один символ:
H =-(p*log2p-(1-p)*log2(1-p)) = 0,514+0,341 = 0,855 бит/символ
С учетом потерь максимальное количество информации, передаваемое по одному каналу в единицу времени равно:
С = 120*(1-0,855) = 17,36 бит
По четырем каналам максимум можно передать:
С3 = 4* 17,36 = 69, 39 бит/с,
что меньше, чем энтропия источника 180.
Вывод:
Для передачи информации, поставляемой источником, недостаточно пропускной способности четырех каналов.
Литература
1. Вентцель Е.С. Теория вероятностей: Учеб. для вузов. -- 6-е изд. стер. -- М.: Высш. шк., 1999.-- 576 c
2. Яглом А.М., Яглом И.М. Вероятность и информация. М.: Наука, 1973, с. 238
Размещено на Allbest.ru
...Подобные документы
Система передачи информации, ее количество и логарифмическая мера. Ансамбль сообщений, виды единиц информации. Свойства количества информации. Энтропия как содержательность и мера неопределенности информации, ее свойства. Понятие избыточности сообщений.
реферат [35,1 K], добавлен 01.08.2009Определение вероятности появления поломок. Расчет вероятности успеха, согласно последовательности испытаний по схеме Бернулли. Нахождение вероятности определенных событий по формуле гипергеометрической вероятности. Расчет дискретной случайной величины.
контрольная работа [69,3 K], добавлен 17.09.2013Вычисление по классической формуле вероятности. Определение вероятности, что взятая наугад деталь не соответствует стандарту. Расчет и построение графиков функции распределения и случайной величины. Вычисление коэффициента корреляции между величинами.
контрольная работа [708,2 K], добавлен 02.02.2011Возникновение теории вероятности как науки. Классическое определение вероятности. Частость наступления события. Операции над событиями. Сложение и умножение вероятности. Схема повторных независимых испытаний (система Бернулли). Формула полной вероятности.
реферат [175,1 K], добавлен 22.12.2013Определение вероятности наступления события, используя формулу Бернулли. Вычисление математического ожидания и дисперсии величины. Расчет и построение графика функции распределения. Построение графика случайной величины, определение плотности вероятности.
контрольная работа [390,7 K], добавлен 29.05.2014Определение вероятности случайного события; вероятности выиграшных лотерейных билетов; пересечения двух независимых событий; непоражения цели при одном выстреле. Расчет математического ожидания, дисперсии, функции распределения случайной величины.
контрольная работа [480,0 K], добавлен 29.06.2010Применение классического определения вероятности для нахождения среди определенного количества деталей заданных комбинаций. Определение вероятности обращения пассажира в первую кассу. Использование локальной теоремы Муавра-Лапласа для оценки отклонения.
контрольная работа [136,0 K], добавлен 23.11.2014Вычисление вероятности непогашения кредита юридическим и физическим лицом, с помощью формулы Байеса. Расчет выборочной дисперсии, его методика, основные этапы. Определение вероятности выпадания белого шара из трех, взятых наудачу, обоснование результата.
контрольная работа [419,7 K], добавлен 11.02.2014Определение вероятности определенного события. Вычисление математического ожидания, дисперсии, среднеквадратического отклонения дискретной случайной величины Х по известному закону ее распределения, заданному таблично. Расчет корреляционных признаков.
контрольная работа [725,5 K], добавлен 12.02.2010Применение классического определения вероятности в решении экономических задач. Определение вероятности попадания на сборку бракованных и небракованных деталей. Вычисление вероятности и выборочного значения статистики при помощи формулы Бернулли.
контрольная работа [309,4 K], добавлен 18.09.2010Характеристика полной группы событий как совокупность всех возможных результатов опыта. Способы определения вероятности событий в задачах разного направления. Нахождение вероятности количества нестандартных деталей. Построение функции распределения.
задача [37,9 K], добавлен 19.03.2011Определение числа всех равновероятных исходов испытания. Правило умножения вероятностей независимых событий, их полная система. Формула полной вероятности события. Построение ряда распределения случайной величины, ее математическое ожидание и дисперсия.
контрольная работа [106,1 K], добавлен 23.06.2009Классическое определение вероятности события. Способы вычисления наступления предполагаемого события. Построение многоугольника распределения. Поиск случайных величин с заданной плотностью распределения. Решение задач, связанных с темой вероятности.
задача [104,1 K], добавлен 14.01.2011Определение вероятности наступления определенного события по законам теории вероятности. Вычисление математического ожидания, дисперсии и среднего квадратичного отклонения. Нахождение выборочного уравнения регрессии по данным корреляционной таблицы.
контрольная работа [212,0 K], добавлен 01.05.2010Определение вероятности появления события в каждом из независимых испытаний. Случайные величины, заданные функцией распределения (интегральной функцией), нахождение дифференциальной функции (плотности вероятности), математического ожидания и дисперсии.
контрольная работа [59,7 K], добавлен 26.07.2010Порядок составления гипотез и решения задач на вероятность определенных событий. Вычисление вероятности выпадения различных цифр при броске костей. Оценка вероятности правильной работы автомата. Нахождение функции распределения числа попаданий в цель.
контрольная работа [56,6 K], добавлен 27.05.2013Обработка данных измерений величин и представление результатов с нужной степенью вероятности. Определение среднего арифметического и вычисление среднего значения измеренных величин. Выявление грубых ошибок. Коэффициенты корреляции. Косвенные измерения.
реферат [116,2 K], добавлен 16.02.2016Построение статистического ряда исходной информации. Определение среднего значения показателя надежности и среднеквадратического отклонения. Проверка информации на выпадающие точки. Определение доверительных границ при законе распределения Вейбулла.
контрольная работа [65,7 K], добавлен 31.01.2014Число возможных вариантов, благоприятствующих событию. Определение вероятности того что, проектируемое изделие будет стандартным. Расчет возможности, что студенты успешно выполнят работу по теории вероятности. Построение графика закона распределения.
контрольная работа [771,9 K], добавлен 23.12.2014Нахождение количества способов, которыми можно выбрать по 6 карт из колоды, содержащей 36 карт. Поиск вероятности того, что при выдаче изделия со склада оно будет стандартным. Вероятность того, что пассажир дождется троллейбуса в течение ближайших минут.
контрольная работа [145,1 K], добавлен 28.01.2014
