Поиск

Полнотекстовый поиск:
Где искать:
везде
только в названии
только в тексте
Выводить:
описание
слова в тексте
только заголовок

Рекомендуем ознакомиться

Информатика->Реферат
Основные идеи современной информационной технологии базируются на концепции, согласно которой данные должны быть организованы в базы данных с целью ад...полностью>>
Информатика->Реферат
Пособие предназначено для студентов экономических специальностей и со­ставлено на основе программы по курсу «Мировая экономика» В пособии содержатся м...полностью>>
Информатика->Реферат
В истории вычислительной техники можно проследить развитие двух основных областей ее использования Первая область - применение вычислительной техники ...полностью>>
Информатика->Реферат
На первом этапе проектирования базы данных необходимо определить цель создания базы данных, основные ее функции и информацию, которую она должна содер...полностью>>

Главная > Дипломная работа >Информатика

Сохрани ссылку в одной из сетей:

1.2.2 Дешифровані коди

Найпростіший варіант кодування вибірки інформаційного джерела - установлення відповідності між конкретними символами алфавіту й кодами, що мають цілу довжину в одиницях подання інформації. Природно зажадати, щоб код, отриманий у результаті такого кодування, був дешифрованим, тобто по будь-якій комбінації кодів символів можна було б відновити закодоване повідомлення. Необхідна умова дешифруємості було запропоновано й доведене Макмілланом. Формулювання виглядає в такий спосіб: якщо система кодів із цілими довжинами {li}Ni=1 дешифровані, те виконується нерівність

(1.7)

де m - підстава системи подання інформації.

Виконання нерівності (1.7) спричиняє виконання більше важливої нерівності:

(1.8)

Для доказу досить скористатися опуклістю функції logm (x). Таким чином, ефективність дешифрованого посимвольного кодування обмежена величиною ентропії імовірнісного розподілу появи символів на виході інформаційного джерела.

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

Будемо використати раніше уведені позначення. Джерело, що послідовно перебуває в станах s1, s2,..., sn, як і раніше, характеризується імовірнісними розподілами

.

Через pi1, i2,..., in позначається ймовірність появи повідомлення "i1, i2,... in", через li 1, i2,..., in - довжина коду повідомлення. Ефективність кодування повідомлень довжини n з розрахунку на один символ визначається по формулі

Коди для повідомлень довжини n повинні бути дешифрованими, тому можна скористатися нерівністю (1.8):

Права частина нерівності являє собою вираження для ентропії. Таким чином, ефективність кодування з розрахунку на один символ не може перевершувати величину ентропії повідомлення, що доводити на один символ. Використовуючи формулу (1.5), одержуємо більше зручну з обчислювальної крапки зору оцінку:

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

1.2.3 Оптимальна довжина коду

Тому що код виходить для повідомлення в цілому, не можна говорити про коди для конкретних символів, що становлять повідомлення. Проте виникає необхідність визначати деякий внесок у результуючу довжину коду повідомлення, внесень кожним вхідної в нього символом. Фізичний зміст такого внеску - середнє збільшення довжини коду повідомлення, обумовлене входженням у нього даного символу. Позначимо через xi внесок, внесень символом з індексом i (у загальному випадку величина внеску являє собою речовинне число). Через xi1, i2,..., in позначимо внесок, внесень повідомленням s = i1, i2,..., in - Виходячи зі змісту поняття "внесок", для випадку стаціонарної незалежної вибірки логічно зажадати виконання наступних властивостей:

(адитивність)

,

де li1, i2,..., in - довжина реального коду повідомлення (ціле число), а M (n) - ненегативна функція, така що M (n) /n - > 0 при n - > оо

Асимптотичне поводження функції M (n) /n дозволяє зробити висновок:

(1.9)

Таким чином, отримане узагальнення нерівності Макміллана на випадок внесків символів у результуючу довжину повідомлень.

Узагальнена нерівність (1.9) дозволяє обчислити точне значення величини внеску xa символу з індексом a для випадку оптимального кодування. Для обчислення точного значення необхідно вирішити задачу про мінімізацію суми

,

яка визначає середню ефективність кодування, за умови виконання нерівності (1.9). У крапці мінімуму похідна від зазначеної суми звертається в нуль:

(1.10)

Підстановка рішення задачі про мінімізацію в нерівність (1.9), мабуть, повинне перетворювати його в рівність. Звідси будь-який оптимальний внесок xk легко виражається через внески інших символів:

Підставляючи вираження для xk у рівняння (1.10), одержуємо

Після узяття похідної рівняння здобуває наступний вид:

, або

Індекс k може приймати одне з N значень, тобто реально для шкірного фіксованого індексу a є N рівнянь. Просумувавши ці рівняння, одержимо

що з урахуванням виконання рівності у вираженні (1.9) рівносильне

Звідси отримаємо формулу для xa:

(1.11)

Таким чином, оптимальний внесок символу, що з'являється з імовірністю p: у довжину результуючого коду становить logm p одиниць інформації в системі подання з підставою m. - анный висновок може бути використаний для обчислення оптимальної довжини коду в рамках тієї або іншої імовірнісної моделі. Одержуючи оцінку ймовірності появи чергового символу на деякому етапі кодування, можна точно визначити оптимальну довжину відповідного інформаційного опису.

1.3 Методи генерації коду

1.3.1 Префіксне кодування

Серед кодів, що задовольняють нерівності Макміллана, особливе місце займають префіксні коди. Система кодів називається префіксною, якщо жоден з кодів, що належить системі, не є качаном (префіксом) іншого коду із цієї ж системи. Очевидне достоїнство префіксного кодування полягає в тім, що одержуваний код може бути легко декодований. Завдяки властивості префікса для того, щоб визначити черговий закодований символ (повідомлення), досить проаналізувати качан відповідної чергової порції коду. При цьому довжина аналізованої порції ніколи не перевищує довжину коду чергового закодованого символу (повідомлення).

Геометрична трактування систем префіксних кодів - m-арные дерева. Властивість префікса гарантує відсутність циклів у графі, ребрам якого зіставлені різні значення інформаційної одиниці. Таким чином, граф є деревом зі ступенем розгалуження, що збігає з підставою системи подання інформації m. Слід зазначити, що нумерація ребер може бути здійснена довільним образом; значення має тільки конкретна структура дерева, а точніше - набір відстаней від кореневого вузла до листових вузлів. Ці відстані відповідають довжинам кодів префіксної системи. Крафт показав, що виконання нерівності (1.7) є гарантією існування кодового дерева зі структурою, що відповідає набору довжин , що фігурують у нерівності. Інакше кажучи, якщо система довжин задовольняє нерівності (1.7), можна побудувати систему префіксних кодів з відповідними довжинами. Дане твердження дозволяє відмовитися від розгляду систем кодів, відмінних від префіксних. Будь-яка система дешифрованих кодів задовольняє нерівності (1.7), а виходить, вона може бути без шкоди для ефективності замінена системою префіксних кодів. Нерівність (1.7) стосовно до систем префиксних кодів називають також нерівністю Крафта.

Розглянемо блокове кодування повідомлень довжини n, породжуваних деяким інформаційним джерелом. Як і раніше, позначимо через

імовірнісний розподіл появи j-ro символу повідомлення (sj - відповідний стан джерела), через pi1, i2,..., in - імовірність появи повідомлення "i1, i2,..., in". Відповідно до твердження Крафта, можна побудувати систему префіксних кодів із длинами

(Для доказу досить підставити ці довжини в нерівність Крафта й переконатися в тім, що воно виконується) Оцінимо ефективність кодування з розрахунку на один символ повідомлення:

Використовуючи альтернативне вираження для ентропії (1.5), одержуємо

Для випадку стаціонарного джерела з розподілом імовірностей

маємо:

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

1.3.2 Алгоритм Шеннона

Алгоритм побудови системи префиксних кодів з довжинами, що залежать від імовірностей по формулі , був запропонований Шенноном. Алгоритм працює в такий спосіб. Імовірності появи повідомлень p1,p2,...,pn розташовуються в порядку убування (тут N - потужність множини повідомлень). Не обмежуючи спільності, можна вважати

.

Як код повідомлення з індексом i беруться перші m-ичных розрядів числа так називаної накопиченої ймовірності. Тому що довжини кодів у такій системі не убувають зі зменшенням імовірності й імовірності появи повідомлень із індексами i+1, i+2,...,N відрізняються від імовірності появи повідомлення з індексом i принаймні на , код повідомлення з індексом i не є початком кодів повідомлень із індексами i+1, i+2,...,N. Таким чином, система кодів є префіксною. Розглянемо геометричне трактування алгоритму Шеннона. Інтервал [0,1) може бути розбитий на N підінтервалів

,

відповідним повідомленням з індексами i = 1, 2,...,N. Для ідентифікації i-го повідомлення необхідно вибрати деяке число з підінтервалу [ai, bi), представиме як можна меншою кількістю m-ічних розрядів. Для цього потрібно побудувати на інтервалі [0,1) одномірну мережу з постійним періодом, що містить крапок (місце розташування будь-якої крапки визначається li-розрядним числом), рівно одна з яких (ідентифікуюча) належить інтервалу [ai, bi). Ясно, що шукана мережа повинна мати період, що не перевищує pi, тобто . Звідки отримуємо .

Алгоритм Шеннона дозволяє генерувати коди, довжина яких відрізняється від оптимальних значень, обумовлених по формулі (1.11), менш чим на одну інформаційну одиницю. Таким чином, різниця між ефективністю кодування й ентропією (так називана надмірність) не перевищує одиниці.



Загрузить файл

Похожие страницы:

  1. Системи когенерації енергії

    Реферат >> Промышленность, производство
    ... і теплову енергію в централізованих системах теплозабезпечення (у вигляді пару і гарячої ... газотурбінної установки. В системах з замкненим тепловим циклом процеси ... іни з триступеневим розширенням і двоступеневим стисненням і процесом рекуперації. Рис. 9. ...
  2. Система живлення ВАЗ-2121

    Курсовая работа >> Транспорт
    ... палива "L-Jetronic” із карбюраторною системою живлення. Система живлення дизелів має відпов ... багато автомобілів іноземного виробництва із системою впорскування палива (інжектором). Застосування карбюратор ... об’єм,л 1.69 Степінь стиснення 83 Потужність,кВт 58 ...
  3. Система обробки аудіоінформації. Підсистема фільтрації і обробки сигналу

    Дипломная работа >> Информатика, программирование
    ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 11 1. РОЗРОБКА СИСТЕМИ ОБРОБКИ Аудиоинформация ... ... 14 1.1. Обґрунтування ... Функціональне призначення системи .. 20 1.3.3. Особливості системи та умови її ...
  4. Система охолодження ВАЗ-2107

    Курсовая работа >> Транспорт
    ... можна встановлювати і з двигунів 2108. система охолодження вентилятор термостат / —- крильчатка; ... водою і підводять у радіатор стиснене повітря під тиском 1 кгс/ ... навколишнього середовища, технічного обслуговування системи охолодження, її неполадки та методи ...
  5. Система запалювання від магнето

    Реферат >> Транспорт
    ... . Завдання : - визначити призначення та принцип дії системи запалювання від магнето - охарактеризувати особливості конструкц ... ів, кількості ділянок дотикання та сили їх стиснення. Параметром, що використовується для ...

Хочу больше похожих работ...

Generated in 0.0020229816436768