Характеристика основних методів кодування інформації

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

Надіслати свою гарну роботу до бази знань просто. Використовуйте форму нижче

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

Розміщено на http://www.allbest.ru

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

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

Кодування Хаффмана є простим алгоритмом побудови кодів змінної довжини, мають мінімальну середню довжину. Цей дуже популярний алгоритм є основою багатьох комп'ютерних програм стиснення текстової та графічної інформації. Деякі з них використовують безпосередньо алгоритм Хаффмана, а інші беруть його як один із ступенів багаторівневого процесу стиснення. Метод Хаффмана робить ідеальне стиснення (тобто стискає дані до їх ентропії), якщо ймовірності символів точно рівні негативним ступеням числа 2. Алгоритм починає будувати кодове дерево знизу вгору, потім ковзає вниз по дереву, щоб побудувати кожен індивідуальний код справа наліво (від самого молодшого біта до найстаршого). Починаючи з робіт Д. Хаффмана 1952 року, цей алгоритм був предметом багатьохдосліджень.

Коди Хаффмана викладаються у всіх технічних ВНЗ світу та, крім того, входять до програми для поглибленого вивчення інформатики у школі.

Тому вивчення кодування інформації та методів кодування, зокрема методу кодування Хаффмана є актуальним.

Об'єкт дослідження: кодування та методи кодування інформації.

Предмет дослідження: програмне застосування, що показують основні принципи кодування з прикладу методу кодування Хаффмана.

Метою курсової є вивчення основ кодування інформації зокрема метод кодування Хаффмана і застосувати в процесі програмної реалізації цього методу. Ця мета зумовила виділення наступних завдань:

1) розглянути основні поняття та принципи кодування інформації;

2) вивчити метод кодування Хаффмана,

3) розробити алгоритми та програму для реалізації програмного продукту «Код Хаффмана», з використанням сучасної технології програмування;

1. Теоретичні основи кодування інформації

1.1 Основи та основні поняття кодування інформації

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

Кодування - це перетворення повідомлень на сигнал, тобто. перетворення повідомлень на кодові комбінації. Код – система відповідності між елементами повідомлень та кодовими комбінаціями. Кодер - пристрій,що здійснює кодування. Декодер - пристрій, яке здійснює зворотну операцію, тобто. перетворення кодової комбінації на повідомлення. Алфавіт – безліч можливих елементів коду, тобто. елементарних символів (кодових символів) X = де i = 1, 2. m. Кількість елементів коду - m називається його основою. Для двійкового коду xi = і m = 2. Кінцева послідовність символів даного алфавіту називається кодовою комбінацією (кодовим словом). Число елементів кодової комбінації - n називається значимістю (довжиною комбінації). Число різних кодових комбінацій (N = mn) називається обсягом чи потужністю коду.

1) Підвищення ефективності передачі за рахунок досягнення максимальної швидкості передачі.

2) Підвищення перешкодостійкості під час передачі даних.

Відповідно до цих цілей теорія кодування розвивається у двох основних напрямках:

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

2. Теорія завадостійкого кодування займається пошуком кодів, що підвищують достовірність передачі в каналах з перешкодами.

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

Декодування - процес зворотного перетворення коду до форми вихідної символьної системи, тобто. отримання вихідного повідомлення. Наприклад: переклад з абетки Морзе до письмового тексту українською мовою.

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

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

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

Ще одна важлива обставина: вибір способу кодування інформації може бути пов'язаний з передбачуваним способом обробки. Покажемо це з прикладу уявлення чисел -- кількісної інформації. Використовуючи українську абетку, можна записати число «тридцять п'ять». Використовуючи жалфавіт арабської десяткової системи числення, пишемо: "35". Другий спосіб не тільки коротший за перший, але й зручніше для виконання обчислень. Який запис зручніший для виконання розрахунків: «тридцять п'ять помножити на сто двадцять сім» чи «35 х 127»? Очевидно – друга.

Однак якщо важливо зберегти число без спотворення, його краще записати в текстовій формі. Наприклад, у грошових документах часто суму записують у текстовій формі: "триста сімдесят п'ять руб." замість "375 руб.". У другому випадку спотворення однієї цифри змінить значення. При використанні текстової форми навіть граматичні помилки можуть змінити сенсу. Наприклад, малограмотний чоловік написав: «Тристо сімдесят п'ять крб.». Проте зміст зберігся.

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

Головною властивістю випадкових подій є відсутність повної впевненості у їхньому наступі, що створює відому невизначеність при виконанні пов'язаних з цими подіями дослідів. Однак цілком зрозуміло, що ступінь цієї невизначеності в різних випадках буде зовсім різним. Для практики важливо вміти чисельно оцінювати ступінь невизначеності найрізноманітніших дослідів, щоб мати змогу порівняти їх із цього боку. Розглянемо дванезалежних досвіду і а також складний досвід, що полягає в одночасному виконанні дослідів та. Нехай досвід має k рівноймовірних наслідків, а досвід має l рівноймовірних наслідків. Очевидно, що невизначеність досвіду більша за невизначеність досвіду, оскільки до невизначеності тут додається ще невизначеність результату досвіду. Природно вважати, що ступінь невизначеності досвіду дорівнює сумі невизначеностей, що характеризують досліди, тобто.

при задовольняє лише одна функція - :

Розглянемо досвід А, що складається з дослідів і мають ймовірність. Тоді загальна невизначеність для досвіду А дорівнюватиме:

Це останнє число називатимемо ентропією досвіду і позначатимемо через .

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

Ми розглянемо тут лише найпростіший випадок повідомлень, записаних за допомогою деяких «букв», частоти прояву яких на будь-якому місці повідомлення повністю характеризується ймовірностями р1, р2, … …, рп, де, зрозуміло, р1 + р2 + … + рп = 1, у якому ймовірність pi прояви i-ї літери будь-якому місці повідомлення передбачається однієї й тієї ж, незалежно від цього, які літери стояли всіх попередніх місцях, тобто. послідовні літери повідомлення незалежні друг від друга. Насправді, у реальних повідомленнях це частіше буває не так; зокрема, українською мовою ймовірність появи тієї чи іншої літери істотно залежить від попередньої літери. ОднакСуворий облік взаємної залежності букв зробив би всі подальші розгляди дуже складними, але не змінить майбутні результати.

Ми поки що розглядатимемо двійкові коди; узагальнення отриманих при цьому результатів на коди, що використовують довільне число елементарних сигналів, є, як завжди, вкрай простим. Почнемо з найпростішого випадку кодів, що зіставляють окреме кодове позначення – послідовність цифр 0 та 1 – кожній «літері» повідомлення. Кожному двійковому коду для п-літерного алфавіту може бути зіставлений деякий метод відгадування деякого загаданого числа х, що не перевищує п, за допомогою питань, на які відповідає лише «так» (1) або «ні» (0), що і призводить до нас двійковий код. При заданих ймовірностях р1, р2, … …, рп окремих букв передача багатолітерного повідомлення найбільш економний код буде той, для якого при цих ймовірностях п значень х середнє значення запитань (двійкових знаків: 0 і 1 або елементарних сигналів) виявляється найменшим.

Насамперед, середня кількість двійкових елементарних сигналів, що припадають у закодованому повідомленні на одну літеру вихідного повідомлення, не може бути меншою за Н, де Н = - p1 log p1 - p2 log p2 - … - pn log pn - ентропія досвіду, що полягає в розпізнаванні однієї літери тексту (чи, коротше, просто ентропія однієї літери). Звідси відразу випливає, що з будь-якому методі кодування для запису довгого повідомлення з М літер потрібно щонайменше ніж МН двійкових знаків, і може перевищувати одного біта.

Якщо ймовірності р1, р2, … …, рп в повному обсязі рівні між собою, то Н 0 do