69635

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

Реферат

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

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

Украинкский

2014-10-08

283 KB

8 чел.

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

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

Кафедра ЕОМ

Реферат

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

на тему:

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

 Виконала:

студентка групи КІ-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


 

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

83752. Правовое регулирование упрощенной системы налогообложения: общие положения, налогоплательщики, основные элементы налога, особенности уплаты 42.57 KB
  В связи с применением УСН налогоплательщики освобождаются от уплаты налогов применяемых общей системой налогообложения налога на имущество организаций налога на добавленную стоимость и др.13 НК РФ Переход на УСН с ЕНВД с начала того месяца в котором была прекращена их обязанность по уплате единого налога на вмененный доход п. СТАВКИ И ПОРЯДОК РАСЧЕТА Расчет налога производится по следующей формуле статья 346.
83753. Правовое регулирование системы налогообложения в виде единого налога на вмененный доход для отдельных видов деятельности: общие положения, налогоплательщики, основные элементы налога 40.79 KB
  ЕНВД применяется в отношении отдельных видов предпринимательской деятельности п. Налог на прибыль организаций В отношении прибыли полученной от предпринимательской деятельности облагаемой единым налогом 2. Налог на имущество организаций В отношении имущества используемого для ведения предпринимательской деятельности облагаемой единым налогом 3.
83754. Правовое регулирование системы налогообложения при выполнении соглашений о разделе продукции: общие положения, налогоплательщики, особенности уплаты 41.83 KB
  Система налогообложения при выполнении соглашений о разделе продукции особая система налогообложения специальный налоговый режим применяемый при выполнении соглашений которые заключены в соответствии с Федеральным законом от 30. № 225ФЗ О соглашениях о разделе продукции. Режим применяется в течение всего срока действия соглашения о разделе продукции.
83755. Правовое регулирование транспортного налога: общие положения, налогоплательщики, основные элементы налога, особенности регионального законодательства 42.78 KB
  Налогоплательщиками транспортного налога признаются лица на которых в соответствии с законодательством Российской Федерации зарегистрированы транспортные средства ст. Плательщиками налога также признаются физические лица получившие транспортные средства по доверенности выданной до 29 июля 2002 года. Следовательно по истечении трех лет с момента выдачи доверенности на право владения и распоряжения транспортным средством выданной до 29 июля 2002 года плательщиком транспортного налога признается физическое лицо на которое зарегистрировано...
83756. Правовое регулирование налога на игорный бизнес: налогоплательщики, основные элементы налога, особенности регионального законодательства 41.92 KB
  365 НК РФ Объект налогообложения налогом на игорный бизнес являются ст. Каждый объект налогообложения должен быть зарегистрирован в налоговой инспекции по месту установки не позднее чем за 2 рабочих дня до даты его установки. Регистрация игрового оборудования или пункта приема ставок проводится налоговым органом на основании заявления налогоплательщика с обязательным ой получением выдачей свидетельства о регистрации объекта объектов налогообложения. Любое изменение количества объектов необходимо также зарегистрировать в налоговых органах...
83757. Правовое регулирование налога на имущество организаций: общие положения, налогоплательщик, основные элементы налога, особенности исполнения и уплаты налога 46.96 KB
  1 указанного Федерального закона в отношении имущества используемого ими исключительно в связи с организацией и или проведением XXII Олимпийских зимних игр и XI Паралимпийских зимних игр 2014 года в городе Сочи и развитием города Сочи как горноклиматического курорта. 375 НК РФ определяется как среднегодовая стоимость имущества признаваемого объектом налогообложения. В случае если для отдельных объектов основных средств начисление амортизации не предусмотрено стоимость указанных объектов для целей налогообложения определяется как разница...
83758. Правовое регулирование земельного налога: общие положения, налогоплательщики, основные элементы налога, особенности местного (муниципального) законодательства 43.68 KB
  Плательщики налога Плательщиками налога признаются физические лица обладающие земельными участками признаваемыми объектом налогообложения в соответствии со ст. В отношении земельных участков используемых предназначенных для использования в предпринимательской деятельности налоговая база по налогу и исчисление суммы налога суммы авансовых платежей по налогу производится индивидуальными предпринимателями самостоятельно на основании сведений государственного кадастра недвижимости о каждом земельном участке. Ставки налога Налоговые ставки...
83759. Правовое регулирование налога на имущество физических лиц: общие положения, налогоплательщики, основные элементы налога, особенности местного (муниципального) законодательства 43.26 KB
  1991 № 2003–1 О налогах на имущество физических лиц далее Закон №2003–1. Плательщиками налога признаются физические лица собственники имущества признаваемого объектом налогообложения ст.2009 № 283ФЗ Ставки налога Ставки налога устанавливаются нормативными правовыми актами представительных органов местного самоуправления законами городов федерального значения Москвы и СанктПетербурга в зависимости от суммарной инвентаризационной стоимости объектов налогообложения.
83760. Правовое регулирование страховых взносов в государственные внебюджетные фонды: общие положения, налогоплательщики, основные элементы и особенности уплаты 40.83 KB
  В соответствии с пунктом 10 Положения о Государственном фонде занятости населения Российской Федерации утвержденного постановлением Верховного Совета Российской Федерации от 08. Статьей 22 Закона Российской Федерации от 19.91 О занятости населения в Российской Федерации в редакции Закона Российской Федерации от 15.92 N 33071 О внесении изменений и дополнений в Закон РСФСР О занятости населения в РСФСР установлено что Фонд занятости образуется за счет: обязательных страховых взносов работодателей; обязательных страховых взносов с...