69635

Особливості застосування ентропії

Реферат

Коммуникация, связь, радиоэлектроника и цифровые приборы

Поняття ентропії Ентропія в теорії інформації міра хаотичності інформації невизначеність появи будь якого символу первинного алфавіту. Якщо ж врахувати що деякі поєднання символів зустрічаються дуже рідко то невизначеність ще більше зменшується у цьому випадку говорять...

Украинкский

2014-10-08

283 KB

9 чел.

Міністерство освіти І науки України

національний університет “Львівська політехніка”

Кафедра ЕОМ

Реферат

з дисципліни «Теоретичні основи цифрових комунікацій»

на тему:

«Особливості застосування ентропії»

 Виконала:

студентка групи КІ-31

Тостоган  А. С.

 Прийняв:

Парамуд Я.С.

Львів – 2011


Зміст

  1.  Історія винаходу…………………………………………………..3
  2.  Поняття ентропії…………………………………………………...3
  3.  Види ентропії, їх властивості та  застосування …………………4
  4.  Ефективність ентропії……………………………………………..6
  5.  Додаток (задачі на обчислення ентропії)………………………...7

  1.  Історія винаходу

      У 1948 році,  досліджуючи проблему раціональної передачі інформації через зашумлений комунікаційний канал, Клод Шеннон запропонував революційний

імовірнісний  підхід  до розуміння  комунікацій і створив першу, істинно математичну,теорію ентропії. Його сенсаційні ідеї швидко послужили основою розробки двохосновних напрямків: теорії інформації (виникла для опису передачі і прийому повідомлень в процесі діяльності людини) та теорії кодування.
      Поняття ентропії, як міри випадковості, введено Шенноном у його статті «Математична теорія зв'язку», опублікованій у двох частинах у Bell System Technical Journal в 1948 році.

      Понятя ентропії використовується в таких галузях науки як фізика, хімія та ін. проте в даному випадку будемо говорити про використання цього терміну в теорії інформації.

  1.  Поняття ентропії

      Ентропія в теорії інформації - міра хаотичності інформації, невизначеність появи будь якого символу первинного алфавіту. При відсутності інформаційних втрат чисельно дорівнює кількості інформації на символ переданого повідомлення.
      Так, візьмемо, наприклад, послідовність символів, що складають яку-небудь пропозицію українською мовою. Кожен символ з'являється з різною частотою, отже, невизначеність появи для деяких символів більша, ніж для інших. Якщо ж врахувати, що деякі поєднання символів зустрічаються дуже рідко, то невизначеність ще більше зменшується (у цьому випадку говорять про ентропіїю n-ого порядку)

Ентропія – це кількість інформації, яка в середньому приходиться на один символ в повідомленні.

Эн-mpone” (від грецького) – звертання. Ентропія – міра змістовності повідомлення.

Ентропія – це міра невизначеності. Дійсно, найбільше значення Н приймає при найбільшій невизначеності (див. Графік),

Коли розглядаються повідомлення з однаковою ймовірністю Р10=0,5;

При прийомі сигналу невизначеність зрозуміло пропадає (при умові, що сигнал не був спотворений в результаті дії завади).

  1.  Види ентропії, їх властивості та  застосування

Виділяють такі види ентропій:

  1.  Безумовна ентропія
  2.  Умовна ентропія
  3.  Ентропія обєднання

      Безумовна ентропія – це питома кількість інформації на один елемент повідомлень, складених з алфавітів, між символами яких немає взаємозалежності.

      Коли говорять про безумовну ентропію, то слово ”безумовна” опускають. Оговорюють інші види ентропії як менш поширені.

      Ентропія джерела повідомлень    і являє собою невизначеність появи на виході джерела повідомлень букви первинного алфавіту.

      Ентропія приймача повідомлень  являє собою невизначеність появи на вході приймача букви після її появи на виході джерела повідомлень.

      Властивості безумовної ентропії.

  1.  Якщо відомо, що подія точно відбудеться (це еквівалентно передачі повідомлення з однією якісною ознакою), то його ентропія рівна нулю.
  2.  Якщо відомо, що подія точно не відбудеться (це еквівалентно відсутності i-ої якісної ознаки), то його ентропія рівна нулю.
  3.  Якщо дослід являє собою послідовність рівноімовірних подій (це еквівалентно передачі повідомлень з рівноімовірними взаємонезалежними символами), то ентропія є максимальною.
  4.  Якщо подія з рівною імовірністю може відбутися або не відбутися, то його ентропія максимальна.
  5.  Ентропія зі скінченою кількістю результатів завжди є додатною величиною.
  6.  Ентропія бінарного відношення володіє властивістю симетрії: збільшення або зменшення ймовірності будь-якого з елементів бінарного повідомлення на одну і ту ж величину приводить до однакової зміни ентропії.
  7.  Ентропія складного повідомлення, яке складається з деяких часткових повідомлень, рівна сумі ентропій складових повідомлення: .

      Використання безумовної ентропії не дозволяє визначити властивості передачі повідомлень у повному обсязі.

      На практиці часто зустрічаються взаємозалежні символи та повідомлення. При передачі змістовних повідомлень одні букви зустрічаються частіше, інші рідше, одні букви і слова часто ідуть за іншими. Наприклад, в англійській мові найчастіше використовується буква е; у французькій після букви q завжди іде буква u,якщо q не стоїть в кінці слова. Щодо взаємодіючих систем, то переважно стан однієї з них впливає на стан іншої. В таких випадках ентропія не може визначатись лише на основі безумовних імовірностей.

      При підрахунку середньої кількості інформації на символ повідомлення взаємозалежність враховують через умовні імовірності появи одних подій відносно інших. А отриману при цьому ентропію називають умовною ентропією.

      Умовна ентропія  використовується при визначенні взаємозалежності між символами первинного алфавіту, для визначення втрат при передачі інформації по каналах зв’язку, при обчисленні ентропії об’єднання.

Формули умовної ентропії, використовуючи формулу Шеннона:

 ;    

 ,

де індекс i вибрано для характеристики довільного стану джерела повідомлень A, індекс j вибрано для характеристики довільного стану адресату B.

  

Властивості умовної ентропії.

  1.  Якщо ансамблі повідомлень A та B взаємонезалежні, то умовна ентропія A відносно B рівна безумовній ентропії A і навпаки:

.

  1.  Якщо ансамблі повідомлень A та B настільки жорстко статично пов’язані, що поява одного з них означає обов’язкову появу іншого, то їх умовні ентропії рівні нулю:

.

      Ентропія об’єднання використовується для обчислення ентропії сумісної появи статично залежних повідомлень. Наприклад, передаючи сто раз цифру 5 по каналу зв’язку з завадами, зауважили, що цифра 5 була прийнята 90 раз, цифра 6 – 8 раз і цифра 4 – 2 рази. Невизначеність виникнення комбінацій виду 5-4, 5-5, 5-6 при передачі цифри 5 може бути описана за допомогою ентропії об’єднання.

Ентропія обєднання визначається таким чином

Властивості ентропії об’єднання:

  1.  Властивість симетрії:  .
  2.  При відсутності статичної залежності між елементами ансамблів A та B умовні імовірності перетворюються на безумовні, тоді

.

  1.  При повній статичній залежності між елементами ансамблів A та B (наприклад, коли результат однієї події однозначно визначає інформацію про другу подію) умовні ентропії рівні нулю, тому

.

  1.   Ефективнісь ентропії

       Оригінальний алфавіт, що зустрічається на практиці, має імовірнісний розподіл, який далекий  від оптимального. Якщо вихідний алфавіт мав N символів, тоді він може може бути порівняний з «оптимізованим алфавітом», імовірнісний розподіл якого є однорідним. Співвідношення ентропії вихідного і оптимізованого алфавіту - це ефективність вихідного алфавіту, яка може бути виражена у відсотках.
З цього випливає, що ефективність вихідного алфавіту з n символами може бути визначена просто як рівна його n-арної ентропії.
Ентропія обмежує максимально можливе стиснення без втрат (або майже без втрат), яке може бути реалізовано при використанні теоретично типового 

набору або, на практиці, - кодування Хаффмана, кодування Лемпеля-Зіва або арифметичного кодування.

  1.   Додаток

Приклад 1. Обчислити ентропію джерела повідомлень, що видає два символи 0 і 1 з ймовірностями p (0) = 3 / 4, p () = 1 / 4 і умовними ймовірностями: p (0 / 0) = 2 / 3, p (/ 0) = 1 / 3, p (0 / 1) = 1, p (/ 1) = 0, тобто після 1 завжди йде 0. 
Рішення: Для випадку взаємозалежних, не рівноймовірно елементів ентропія дорівнює: 
 
Приклад 2. Визначити ентропію джерела повідомлень, якщо імовірність-ності появ символів на вході приймача, рівні: P (b 1) = 0,1; P (b 2) = 0,3; P (b3) = 0,4, P (b4) = 0,2 а канальна матриця має вигляд: 
P (a / b) =  . 
Сума ймовірності при однойменних умовах дорівнює 

Рішення: Визначимо ентропію джерела 
 . 

= 0,1 × 0,99 +0,3 × 0,2 +0,4 × 0 = 0,105; 
 = 0,1 × 0,01 +0,3 × 0,98 +0,4 × 0,01 +0, × 2 × 0,01 = 0,301; 
 0,1 × 0 +0,3 × 0 +0,4 × 0,98 +0,2 × 0,02 = 0,396; 
 0,1 × 0 +0,3 × 0 +0,4 × 0,01 +0,2 × 0,97 = 0,198; 
Перевірка: 
0,105 +0,301 +0,396 +0,198 = 1. 
При цьому ентропія джерела дорівнює: 
H (A) =- (0,105 × log 0,105 +0,301 × log 0,301 +0,396 × log 0,396 +0,198 × log 0,198) = 1,856 біт / симв. 
Приклад 3. Визначити ентропію джерела і умовну ентропію повідомлень, переданих по каналу зв'язку, і складаються з рівноймовірно символів, якщо вплив перешкод у каналі описується матрицею: 
 . 
Рішення: Для рівноймовірно символів в повідомленні ентропія джерела повідомлень дорівнює: 
 біт / симв. 
Повна умовна ентропія дорівнює: 

 
 
=   
         біт/симв. 
Приклад 4. Визначити ентропію приймача повідомлень, якщо ймовірності появи символів a 1, a 2 і a 3 на вході джерела повідомлень рівні P (a 1) = 0,5; P (a 2) = 0,3 та P (a 3) = 0,2, а канальна матриця має вигляд: 
 , 
Рішення: Ентропія приймача дорівнює: 
 . 
Ймовірності появи символів на вході приймача 

 ; 
 ; 
 . 
Перевірка: 
 . 
При цьому: 

6


 

А также другие работы, которые могут Вас заинтересовать

9794. Описание типов. Типизированные константы 117 KB
  Описание типов В простейшем случае тип переменной указывается при ее описании явно. Однако Pascal допускает отдельное определение типа. Иными словами, можно сопоставить типу некоторое имя и в дальнейшем вместо явного указания типа использовать введе...
9795. Работа с массивами 70.5 KB
  Работа с массивами Постановка задачи Задан массив M=(3,4,5,-6,3,8,1,-5,-4,9). Найти сумму, произведение всех элементов массива количество положительных, отрицательных элементов номер максимального и минимального элементов массива. Алгоритм решения...
9796. Задача поиска. Линейный поиск (последовательный поиск) 48.5 KB
  Задача поиска Постановка задачи: Задан массив содержащий n фамилий. Необходимо определить существует ли в этом массиве заданная фамилия. Если существует, необходимо вывести её номер, иначе сообщить об её отсутствии. Линейный поиск (последовательный ...
9797. Процедуры и функции. Блочная структура программы 112.5 KB
  Процедуры и функции. Блочная структура программы Введение Систематический подход к программированию предполагает повышенное внимание к аспектам, связанным со структурой программы. Представление программы как совокупности (иерархии) относительно обос...
9798. Принятие решений в условиях риска, Эффективность выпуска новых видов продукции 66 KB
  Принятие решений в условиях риска. Элементы неопределенности, присущие функционированию и развитию многих экономических процессов, обуславливают появление ситуаций, не имеющих однозначного исхода (решения). Это обстоятельство усложняет процесс...
9799. Принятие решений в условиях неопределенности 72 KB
  Принятие решений в условиях неопределенности. При принятии решений в условиях неопределенности, когда вероятности возможных вариантов обстановки неизвестны, может быть использованы ряд критериев, выбор каждого из которых, наряду с характером решаем...
9800. Проблемы сравнительной оценки вариантов решений с учетом риска 273.5 KB
  Проблемы сравнительной оценки вариантов решений с учетом риска. Как отмечалось ранее, на методы принятия решений в условиях риска существенное влияние оказывает многообразие критериев и показателей, посредством которых оценивается уровень риска. В р...
9801. Учет риска при инвестировании капитальных вложений 86 KB
  Учет риска при инвестировании капитальных вложений. В условиях рыночной экономики, особенно в период ее становления, инвестирование развития сопряжено с риском неполучения ожидаемых результатов в установленные (желаемые) сроки. В связи с этим возник...
9802. Система критериев принятия рискового решения 133.5 KB
  Система критериев принятия рискового решения. Принятие рискового решения на ведение конкретной операции (сделки) в предпринимательской деятельности является заключительной процедурой на стадии анализа риска в технологии риск-менеджмента. Объективная...