Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
ТЕОРІЯ ІНФОРМАЦІЇ Методичні вказівки до лабораторних робіт
Інформація про навчальний заклад
ВУЗ:
Інші
Інститут:
Не вказано
Факультет:
Комп’ютеризовані системи
Кафедра:
Не вказано
Інформація про роботу
Рік:
2005
Тип роботи:
Методичні вказівки до лабораторної роботи
Предмет:
Теорія інформації
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ КОРАБЛЕБУДУВАННЯ
ім. адмірала Макарова
Кафедра комп’ютеризованих систем управління
Блінцов С.В.
ТЕОРІЯ ІНФОРМАЦІЇ
Методичні вказівки до лабораторних робіт
Миколаїв
2005
Вступ
Даний цикл лабораторних робіт призначений для закріплення і розширення знань по основних розділах курсу «Теорія інформації» для студентів, що навчаються за спеціальністю “Системи управління та автоматики”.
Обов'язковою умовою виконання циклу є наявність персональних комп'ютерів, оснащених програмним забезпеченням TURBO- (BORLAND) PASCAL та MATHCAD, бажано останніх версій.
Програмне забезпечення, розроблене автором керівництва і що увійшло в Додаток циклу, складається в основному з двох модулів: модуля COMMON, в якому зосереджені типи, що визначаються користувачем і модуля OSTIN, що складається з основних і сервісних процедур. Внаслідок відносно великого розміру OSTIN, на початкових етапах циклу припустимо тимчасове вилучення деяких процедур з подальшим відновленням по мірі виконання лабораторних робіт. Обидва модулі мають бути завантажені в комп’ютер на вступному етапі виконання циклу.
Лабораторна робота № 1
Безумовні імовірності випадкових подій
Мета роботи: Дослідження апріорних імовірнісних характеристик методами цифрового статистичного моделювання.
Загальні відомості.
Загальний метод моделювання дискретної випадкової величини заснований на наступному співвідношенні:
Технічні засоби, що використовуються і програмне забезпечення.
У теперішній роботі використовується персональний комп'ютер, середовище програмування TURBO-PASCAL або BORLAND PASCAL (графічний режим). Стандартні процедури і функції:
Procedure RANDOMIZE; – для ініціалізації вбудованого генератора псевдовипадкових чисел;
Function RANDOM[(Range: Word)]; – повертає псевдовипадкове число довжиною в слово у діапазоні 0 ( x < N, де N - значення, задане параметром Range.
Procedure InitGraph(var GrDriver:Integer; var Mode: Integer; Path: String); – ініціалізує графічну систему і переводить апаратуру в графічний режим. Параметр Path – вказує шлях до блоку графічного інтерфейсу EGAVGA.BGI.
Procedure PutPixel(X,Y:Integer; Pixel:Word); – будує елемент зображення в точці з координатами <X,Y>, колір якої визначається параметром Pixel.
Procedure Rectangle(X1,Y1,X2,Y2:Integer); – малює прямокутник, використовуючи поточний колір і тип лінії. Точка з координатами <X1,Y1> визначає лівий верхній кут прямокутника, <X2,Y2> – визначає нижній правий кут. (0(X1<X2(GetMaxX, 0(Y1<Y2(GetMaxY).
Procedure Circle(X,Y:Integer; R:Word); – малює коло з радіусом R. Точка <X,Y> вважається центром кола.
Procedure CloseGraph; – закриває графічний режим.
Увага! Використання процедури CloseGraph обов'язково при виході з графічного середовища.
Зміст домашньої підготовки.
1. Вивчити опис, додаток і літературу, що рекомендується.
2. Підготувати ескіз, що зображає простір елементарних подій у вигляді прямокутної області, площа якої становить приблизно 1/6 частину площі екрана монітора. Виконати розмітку області.
3. Накреслити в області простору елементарних подій прямокутник менших розмірів. Його площа не повинна перевищувати 0.2 площі простору. Прив'язати координати лівого верхнього і правого нижнього кутів до екранних координат.
4. Скласти чорновий варіант програми побудови заданих фігур і заповнення внутрішніх областей крапками з випадковими координатами.
Порядок виконання роботи.
1. Завантажити комп'ютер.
2. У розділі диска, який дозволений для використання в студентських роботах створити особистий каталог.
3. Увійти в середовище редактора TURBO PASCAL або BORLAND PASCAL.
4. Увійти в особистий каталог через меню FILE.
5. Створити файл з ім'ям LAB1.
6. Ввести чорновий варіант програми.
7. Відкомпілювати програму (меню COMPILE або Alt(F9).
8. Виконати програму (меню RUN або Ctrl(F9).
9. При необхідності внести корективи до тексту програми.
10. Шляхом візуальної оцінки підібрати число повторень експерименту.
11. Увести в текст програми блок підрахунку точок, які попали у внутрішню область.
12. Включити в програму розрахунок теоретичного і експериментального значень імовірності.
13. Повторити декілька разів розрахунки для різних положень і розмірів внутрішньої області.
14. Замінити внутрішню область на коло і повторити розрахунки.
Зміст звіту.
Звіт повинен містити остаточний варіант тексту програми, таблицю результатів розрахунку і висновки по результуючим даним.
Контрольні запитання.
1. Як залежать теоретичне і експериментальне значення імовірностей від кількості проведених експериментів?
2. При яких умовах справедлива формула розрахунку теоретичного значення імовірності в експерименті, що проводиться?
3. Як отримати закон розподілу випадкової величини, відмінний від рівномірного?
4. Яку інформацію й у якій кількісті одержано в проведеному експерименті?
5. Чи має місце залежність експериментальних значень імовірностей від форми внутрішніх областей?
Рекомендована література
1. Вентцель Е.С. Прикладные задачи теории вероятностей. – М.:Радио и связь,1983.
Лабораторна робота № 2
Умовні імовірності випадкових подій
Мета роботи: вивчення властивостей випадкових подій, пов'язаних з поняттями залежності і незалежності.
Загальні відомості.
Умовну імовірність деякої випадкової події А відносно гіпотези Н обчислюють як відношення імовірності спільного спостереження подій до безумовної імовірності гіпотези:
Події А і Н вважаються незалежними лише при рівності умовної і безумовної імовірностей: P(A|H) = P(A). Нерівність свідчить про залежність.
Технічні засоби, що використовуються та програмне забезпечення. У даній роботі використовуються технічні засоби і програмне забезпечення з лабораторної роботи №1.
Зміст домашньої підготовки.
1. Вивчити опис, додаток і літературу, що рекомендується.
2. Підготувати ескіз простору елементарних подій з прив'язкою до екранних координат.
3. Внести необхідну корективу тексту програми з ЛР №1 з метою розрахунку значень умовної імовірності.
4. Підготувати два варіанти розміщення пересічних областей: а) події теоретично незалежні; б) має місце залежність випадкових подій.
Порядок виконання роботи.
1. Завантажити комп'ютер і увійти в середу TURBO_PASCAL.
2. Підключиться до особистого каталогу.
3. Скопіювати текст програми з ЛР №1 в новий файл. Для цього необхідно розмітити текст, що копіюється, викликати меню FILE, виконати команду копіювання в буфер (Ctrl(Ins), перемкнутися у вікно нового файла і виконати команду копіювання з буфера (Shift(Ins).
4. Внести необхідну корективу програми. Виправити можливі помилки, виявлені компілятором.
5. Виконати розрахунок декількох варіантів.
Зміст звіту.
Звіт повинен містити остаточний варіант тексту програми, таблицю результатів рахунку і висновки за результатами.
Контрольні питання.
1. У яких випадках значення умовної імовірності дорівнює нулю?
2. Як знайти імовірність пари спільних подій, якщо вони незалежні?
3. Як змінювалися результати експерименту при змінах форми областей?
Рекомендована література.
1. Вентцель Е.С. Прикладные задачи теории вероятностей. – М.:Радио и связь,1983.
2. Розанов Ю.А. Случайные процессы. Краткий курс. – М.: Наука,1979.
Лабораторна робота № 3
Вивчення ентропійних характеристик
дискретних джерел марковського типу
Мета роботи. Мета роботи складається в дослідженні таких характеристик джерел як залежність ентропії від розмірів слова, продуктивності і кореляцій між повідомленнями.
Основні відомості. Дискретним джерелом, з точки зору теорії інформації, вважають будь-який пристрій Ux, який в кожну одиницю часу вибирає одне з повідомлень, що належать деякому ансамблю X. Як правило, множина X одна для кожного моменту часу, хоча в деяких випадках для кожного моменту часу може бути свій ансамбль. Фізична природа джерела не входить в коло питань теорії інформації. Джерело вважається заданим, якщо для слів будь-якої довжини, локалізованих в будь-якому часовому інтервалі, існує спосіб визначення сімейства P(n) розподілу імовірностей, де n =<xt,xt+1,…,xt+n-1> слово з n повідомлень, сформоване джерелом з моменту Т=t. Джерело відноситься до класу стаціонарних, якщо розподіл P(n) не залежить від t. При обмеженій довжині слова середнє число біт, яке доводиться на одне повідомлення, визначають таким чином:
.
У стаціонарному режимі роботи нижні індекси можна прибрати, оскільки P(n) від t не залежить і представити H(X1(X2(…(Xn) як H(Xn). Оскільки H(Xn)= H(Xn-1 (X), то приріст інформації за одну одиницю часу складе (Hn = H(X|Xn-1), що дорівнює умовній ентропії чергового повідомлення відносно слів n-1=<x1,x2,…xn-1>. Інформаційний зв'язок між першим x1 і останнім xn повідомленнями визначається взаємною ентропією
H(X1(Xn) = H(X1) – H(X1|Xn).
Якщо джерело являє собою простий ланцюг Маркова, то його імовірнісні та інформаційні характеристики повністю визначені двома видами імовірностей:
1. абсолютними – qk(m)=P(xm = sk), де sk – повідомлення, яке джерело вибрало в момент t=m;
2. умовними (перехідними) – pj,k (,m) =P(xm =sk | x =sj), 0 ( ( ( m.
Умовна імовірність pj,k (,m) визначає імовірність повідомлення sk в момент t=m, якщо в більш ранній момент < m джерело вибрало повідомлення sj. Звичайно ці умовні імовірності називають імовірностями переходу від повідомлення sj до повідомлення sk за (m- кроків.
Очевидно, що введені імовірності ненегативні і задовольняють умові нормування:
На основі теореми повної імовірності для безумовної імовірності повідомлення sk у момент часу t=m можна написати:
.
Використовуючи формулу повної імовірності і визначення ланцюга Маркова, можна пересвідчитися, що
Ці функціональні рівняння є визначальними для інформаційних характеристик джерела. До самих простих джерел марковського типу відносяться однородні. Однорідне джерело характеризується тим, що імовірності переходу pj,k(,m) залежать тільки від різниці аргументів, тобто pj,k(,m) = pj,k(m – ), m > ( 0. Тому для однорідного джерела матриця імовірностей зміни повідомлень повинна мати вигляд P(,m)=P(m – ).
При цьому отримуємо наступну матричну форму рівнянь Маркова:
P(m-) = P(n-)P(m-n) 0(<n<m
qT(m+) =qT()P(m)
Технічні засоби, що використовуються, і програмне забезпечення. У цій роботі використовують технічні засоби попередніх лабораторних робіт, програмне забезпечення MATHCAD-Professional версій 5 і вище. Приклади з Додатку.
Зміст домашньої підготовки.
1. Отримати у викладача структуру джерела у вигляді графа одноступеневих переходів.
2. Скласти матрицю перехідних імовірностей і задати вектор початкового розподілу абсолютних імовірностей.
3. Використовуючи приклади з Додатку, підготувати ескізний варіант програми розрахунків в системі MATHCAD.
Порядок виконання роботи.
1. Завантажити комп'ютер. Запустити WINDOWS. Запустити MATHCAD.
2. Ввести частину тексту програми, яка торкається розрахунку абсолютних імовірностей і ентропії ансамбля. Вибрати тривалість роботи джерела і по графіку візуально оцінити час переходу до стаціонарного режиму.
3. Виконати розрахунок залежності ентропії повідомлення від часу і вивести на екран графік.
4. Виконати розрахунки ентропії зміни повідомлень і вивести на екран її залежність від часу.
5. Виконати розрахунки для взаємної ентропії повідомлень, розділених інтервалом в один, два і більше тактів.
Зміст звіту. Звіт повинен містити граф зміни повідомлень за один такт, початкові дані, текст програми, результати розрахунків і мотивовані відповіді на контрольні питання.
Контрольні запитання.
1. Як залежить ентропія повідомлення в теперішній момент часу від розміру ансамблю джерела?
2. Як міняється характер перехідного процесу із змінами початкових умов?
3. Чому наявність поглинаючого стану приводить до нульового значення ентропії в сталому режимі?
4. Який зв'язок між продуктивністю джерела і кількістю змін повідомлень?
5. Які характерні риси мають зміни інформаційного зв'язку між першим і останнім повідомленнями слова при змінах його розмірів?
Рекомендована література.
1. Колесник В.А. Курс теории информации. – М.: Наука, 1982.
2. Тихонов В.И. Марковские процессы. – М.: Советское Радио,1977.
Лабораторна робота № 4
Високоімовірні множини повідомлень
двійкових джерел без пам'яті
Мета роботи. Метою цієї роботи є вивчення класу типових послідовностей, що визначають інформаційні характеристики двійкових джерел без пам'яті.
Основні відомості. Ідея про те, що загальний випадок нерівноймовірних можливостей (станів) асимптотичне зводиться до випадку рівноймовірних, лежить в основі теорії кодування у відсутність перешкод. Ця ідея належить Л.Больцману, який одним з перших вивів формулу для ентропії. К.Шеннон відродив цю ідею і широко використав для отримання нових результатів. Візьмемо набір незалежних реалізацій n =<x1,x2,…,xn> випадкового повідомлення =xi, що приймає одне з двох значень «1» або «0» з імовірностями P(=1) =p і P(=0) = q =1-p. Покладемо для визначеності р<0.5. Очевидно, що число всіляких різних наборів n дорівнює 2n Нехай реалізація n має в своєму складі m одиниць та n-m нулів. Імовірність такої реалізації, очевидно, дорівнює
P(n) =pmqn-m.
Звичайно ці імовірності різні при різних m. Причому відношення самої великої імовірності до самої малої велике і дуже росте із зростанням n. Про яку ж рівноімовірність може йти мова? Справа в тому, що згідно із законом великих чисел кількість одиниць =x1+x2+…+xn має тенденцію приймати значення, близькі до свого середнього: M{} = M{xi } = n M{xi} = np.
Дисперсія D{m} внаслідок незалежності доданків рівна npq і
.
Таким чином, середнє відхилення також росте із зростанням n, але повільніше, ніж росте середнє значення np і довжина усього можливого діапазону 0 ( m ( n. Ця закономірність дозволяє зробити наступне твердження: всі 2n реалізацій n можна розділити на дві множини An і Bn так, що P(n( An) ( 0 при n ( (, а реалізації з другої множини Bn стають асимптотично рівноімовірними в значенні
Число M елементів множини Bn таке, що
при n ( (.
.
Критерієм приналежності до множини Bn служить система нерівностей:
Повідомлення джерела, що задовольняють вище означеним умовам мають бути однозначно закодовані.
Технічні засоби, що використовуються і програмне забезпечення. У наданій роботі використовується персональний комп'ютер і математичне забезпечення MATHCAD.
Зміст домашньої підготовки. Вивчити опис і джерела літератури, що рекомендуються. Скласти чорновий варіант програми обчислень ентропії двійкового ансамблю, значень кількості власної інформації, що доводиться на один символ слова, яке складається з n символів, верхньої та нижньої межи множини Bn.
Порядок виконання роботи. Завантажити комп'ютер і запустити Windows. Завантажити систему MATHCAD. Ввести текст програми розрахунків. Для побудови графіків в прямокутній системі координат доцільно використати панель інструментів системи MATHCAD і довідкову (Help) інформацію. Виконати розрахунки, побудувати графіки і зафіксувати результати.
Зміст звіту. Звіт повинен містити текст налагодженої програми, результати розрахунків та відповіді на контрольні запитання.
Контрольні питання.
1. Яка кількість слів, що складені із n символів утворить множину Bn при імовірності р=0.1?
2. Як змінюється розмір інтервалу, який включає типові послідовності, при змінах довжини слова і постійній імовірності р?
3. Які слова джерела повинні увійти в безліч Bn, якщо р=0.5?
4. При яких умовах кількість власної інформації слова, що складається з n>1 символів виявиться рівним одному біту?
Література, що рекомендується.
1. Дмитриев В.И. Прикладная теория информации. –M.: Высшая Школа, 1989
2. Стратонович Р.Л. Теория информации. –М.: Советское Радио,1975.
Лабораторна робота № 6.
Оптимальне нерівномірне кодування
методом Шеннона–Хафмана.
Мета роботи. Метою даної роботи є вивчення властивостей нерівномірних кодів і методів їх отримання програмним шляхом.
Основні відомості. У задачу ефективного кодування входить такий спосіб обробки дискретного сигналу, при якому середня кількість одиниць інформації на елементарне повідомлення настільки мала, наскільки це принципово можливе. При цьому потрібно так записати повідомлення, щоб по запису можна було відновити повідомлення без втрат і помилок. К. Шенноном було доведено (1948 р.), що завжди можна побудувати таку систему ефективного кодування дискретного повідомлення, при якій середня кількість двійкових знаків на символ початкового повідомлення як бажано близька, але не менше, за ентропію повідомлення, що визначається його статистичними властивостями. У системі нерівномірного кодування кодові слова мають різну довжину m(xi), яка залежить від повідомлення xi, що кодується. Такий код характеризують середньою довжиною кодових слів
Код вважається оптимальним, якщо (X) ( min при обмеженні (X) ( H(X). Якщо в повідомленнях джерела кодують не кожний символ, а блоками n ( Xn, то оптимізаційна задача формулюється таким чином: мінімізувати (Xn) при обмеженні (Xn) ( H(Xn), де n - довжина блоку n (слова). Доведена теорема, згідно з якою середня довжина оптимального нерівномірного коду укладена в інтервалі
H(Xn) ( (Xn) ( H(Xn)+1.
При невеликих об'ємах нерівномірний код може наочно представлятися у вигляді кодових дерев, як показано на наступному малюнку:
Вузли дерева, що відходять від кореня на i ребер утворять ярус порядку i. Порядком вузла називають номер його ярусу. Порядком дерева називають максимальний з порядків його вузлів. Вузол з якого не вийде жодного ребра, називається кінцевим. Якщо кодові слова відповідають тільки кінцевим вузлам, то код є префіксным. Для існування префіксного двійкового коду необхідно і досить виконання наступної нерівності:
яке називають нерівністю Крафта. Якщо вибрати розміри n слів n, що кодуються і знайти довжини кодових слів, виходячи з нерівності:
(((n ( ( (((n( ( (((n(+1,
то отримаємо код, який буде асимптотично оптимальним. Однак для фіксованих n може виявитися, що слова n можна закодувати краще, тобто з меншою тривалістю (Xn). Хаффман (Huffman D.A. 1952) знайшов нескладний спосіб оптимального кодування, якому відповідає мінімальна середня тривалість з всіх можливих для заданого джерела. Ключовим моментом в алгоритмі побудови оптимального коду є процес творення кодових слів за принципом: повідомленню з мінімальною імовірністю ставиться у відповідність найдовше кодове слово. Якщо двійковий код оптимальний, то кодове дерево повинно мати наступну обов'язкову властивість:
З кожного внутрішнього вузла, а також з кореня, завжди повинні вийти 2 дуги. У іншому випадку єдину дугу можна було б «стиснути» в цей неповний вузол і тим самим скоротити середню довжину кодового слова. Процес побудови кодового дерева починається від кінцевих вершин, яким на першому етапі привласнюються номери повідомлень, що кодуються разом з їх імовірностями. Другий етап, що складається з повторюваних операцій, виконується доти, поки не буде отримано корінь кодового дерева. На початку цього етапу відшукують пару вершин vi, vj, які не мають дуг, що заходять і мають мінімальні імовірності Р(vi) і Р(vj). Потім додають нову вершину vk і з'єднують її парою дуг з vi і vj. Імовірність Р(vk) знаходять як
Р(vk)=Р(vi)+Р(vj).
Після завершення цього кроку кількість вузлів не маючих дуг, що заходять меншає на одиницю. Якщо таких вузлів залишиться два, то вузол, що знову додається буде коренем. Даний алгоритм приводиться в Додатку (модуль OSTIN, Procedure HSHF_OPCOD).
Технічні засоби, що використовуються і програмне забезпечення. У даній роботі використовується персональний комп'ютер, середа програмування TURBO_PASCAL або BORLAND_PASCAL. Програмні модулі з Додатку.
Зміст домашньої підготовки. Вивчити опис лабораторної роботи і Додаток. Відповісти на контрольні питання. Підготувати три варіанти кодових дерев по завданню викладача. Підготувати попередній варіант програм, використовуючи приклади з Додатку.
Порядок виконання роботи. Завантажити комп'ютер. Викликати TURBO-PASCAL. Створити файли даних під іменами LAB6P.DAT(для розподілу імовірностей), LAB6M.DAT(для матриці коду) і програмні файли з іменами LAB6A.PAS і LAB6B.PAS. Файл LAB6A.PAS повинен містити програму, що формує оптимальний нерівномірний код. Файл LAB6B.PAS програму декодування двійкових послідовностей зі статистичною оцінкою інформаційних характеристик джерела. Файл LAB6P.DAT повинен містити масив розподілу імовірностей ансамбля повідомлень. Файл LAB6M.DAT матриці нерівномірних кодів. Робота виконується в декілька етапів. На першому етапі необхідно в файл LAB6M.DAT ввести в режимі редагування заготовлені в період домашньої підготовки матриці нерівномірних кодів. Приклад організації файла матриці для ансамбля з п'яти повідомлень приведено нижче.
9
0 0 0 0 0 1 3 5 7
0 0 0 0 0 2 4 6 8
6 6 7 7 8 8 9 9 0
0 1 0 1 0 1 0 1 10
У першому рядку файла вказують кількість L=2(M-1 стовпців матриці, де М число повідомлень джерела. Перші M стовпців матриці відповідають номерам повідомлень (вузлів) джерела. Перший рядок матриці складається з посилань на вузли при надходженні на вхід декодера двійкового символу «0», друга - з посилань на вузли при надходженні «1». Третій рядок містить інформацію про кодове дерево і складається з посилань на внутрішні вузли кодового слова. Четвертий рядок складається з двійкових кодових символів приписаних дугам кодового дерева. Виключення складає останній елемент четвертого рядка, який має сенс ознаки кінця кодової комбінації. Після запису в файл матриці звертаються до програми розміщеної в файлі LAB6P.PAS, яка здійснює декодування двійкової послідовності і виконує найпростіші статистичні розрахунки. На другому етапі в файл LAB6M.PAS завантажують програму формуючу матрицю оптимального нерівномірного коду і виконують розрахунки, скориставшись статистичними результатами попереднього етапу (режим 4).
Зміст звіту. Звіт повинен містити вихідні дані. Текст налагоджених програм. Досліджені варіанти кодових дерев та їхні зображення. Отримані кількісні характеристики. Порівняльний аналіз отриманих результатів і відповіді на контрольні запитання.
Контрольні питання.
1. Що уявляють собою префіксні коди?
2. Що означає термін “код, що дешифрується"?
3. Приведіть необхідну і достатню умову існування коду, що дешифрується по Крафту.
4. Що таке кодове дерево? Приведіть приклад кодових дерев.
5. Назвіть вади оптимальних нерівномірних кодів.
6. Назвіть шлях отримання нерівномірного коду, в якому витрата бітів на одне повідомлення буде якомога близька до мінімально можливої ?
7. Чи можливо декодувати повідомлення, якщо початок передачі невідомий?
8. Чи достатньо мати рівномірний розподіл, щоб алгоритм Хафмана сформував рівномірний код ?
9. Як може відбитися одиночна поразка символу на результат декодування ?
Рекомендована література.
1. Дмитриев В.И. Прикладная теория информации. –М.: Высшая Школа, 1989
2. Стратонович Р.Л. Теория информации. –М.: Советское Радио,1975.
Лабораторна робота № 7
Кодування двійкових джерел без пам'яті
методом «довжин серій».
Мета роботи. Метою роботи є вивчення методу перекодування двійкових послідовностей для потреб стиснення інформації.
Основні відомості. На відміну від поширених методів, метод, що отримав назву «кодування довжин серій» не пов'язаний з групуванням послідовності повідомлень на слова фіксованої довжини. З цього методу слідує, що крім задачі вибору оптимального коду для даної безлічі особливу зацікавленість викликає також задача вибору хорошої множини повідомлень, що кодуються. Нехай джерело породжує послідовність двійкових незалежних символів «0» і «1», причому імовірність появи «1» рівна р<1/2.
Ця послідовність розбивається на сегменти вигляду: <1>, <01>, <001>,…,<000…01> і
<0000…00>, де довжини сегментів відповідно дорівнюють 1, 2, …, N. Ккількість сегментів дорівнює N+1 (два останніх сегменти <000…01> і <000…00> мають однакову довжину). Якщо відомий початок передачі повідомлень, то групування на сегменти однозначне. Далі сегменти розглядаються як повідомлення деякого джерела; імовірність появи i - го сегмента дорівнює pqi-1, i=1,2,…, N, q = 1- p. Імовірність появи сегмента <000…00> рівна qN. Ці сегменти кодуються нерівномірним кодом так, що останньому сегменту зіставляється слово одиничного розміру, а іншим - слова довжини M+1. Значення вибирають з інтервалу:
N ( 2M <N+1.
Середня кількість інформації, яку буде мати сегмент, очевидно, дорівнює
А середня довжина сегменту має вигляд:
Прийнятий метод кодування забезпечує наступне значення середньої довжини кодового слова:
s(N)= 1 + M(1- qN).
Щоб кодування не мало втрат інформації, необхідно забезпечити наступну нерівність:
Hs(N) ( s(N).
Середня довжина кодового слова при цьому повинна знаходитися в інтервалі:
1+(1-qN)Log2(N) ( s(N) < 1+(1-qN)Log2(N+1).
Якщо кількість сегментів вибрати з умови N=2M, то середня довжина кодових слів буде автоматично задовольняти перерахованим нерівностям.
Характер поведінки нижньої межі інтервалу, ентропії ансамбля сегментів та їх середнього розміру при імовірності р = 0,25, показаний на наступному малюнку:
Як видно з графіка, ентропія і середній розмір сегмента асимптотично наближаються до постійних значень при необмеженому збільшенні n. Середній розмір кодових слів, починаючи з певних значень n починає обганяти спочатку значення ентропії, а потім і середній розмір сегмента. Така поведінка свідчить про існування деякого оптимального значення n при фіксованій імовірності р.
Технічні засоби, що використовуються і програмне забезпечення. У даній роботі використовують персональний комп'ютер, середовище TURBO- або BORLAND PASCAL, систему MATHCAD, програмні модулі Додатку.
Зміст домашньої підготовки. Вивчити опис лабораторної роботи. Підготувати матрицю кодовго дерева відповідно до правил кодуванн довжин серій для кількості сегментів заданих викладачем. Підготувати чорновий варіант MATHCAD-програми розрахунків оптимального значення кількості сегментів при фіксованих значеннях ймовірності p. Підготувати PASCAL-програму розрахунків розподілу ймовірностей ансамбля сегментів, використовуючи модуль OSTIN із Додатоку.
Внести відповідні зміни у програму із попередніх лабораторних робот для перевірки на оптимальність методу КДС.
Порядок виконання роботи. Завантажити комп'ютер системою MATHCAD. Ввести програму розрахунків оптимального значення кількості сегментів. Для заданого інтервалу значення ймовірності p визначити кількість сегментів ансамблю. Виконати розрахунок середньої довжини і ентропії ансамблю сегментів. Виконати розрахунки середньої довжини кодових слів. Зберегти отриманий розподіл ймовірностей ансамблю сегментів у файлі LAB6P.DAT. Відредагувати файл, доповнивши його початок розміром. Викликати PASCAL і відкрити файл LAB6M.PAS. Виконати програму у режим «зчитування розподілу із зовнішнього файлу». Зберегти отриманий результат.
Зміст звіту. Звіт повинен містити вихідні дані. Зображення отриманих кодових дерев. Тексти програм. Кількісні характеристики коду та порівняльний аналіз. Відповіді на контрольні запитання.
Контрольні запитання.
1. Як буде виглядати кодове дерево методу «довжин серій», якщо кількість сегментів належать інтервалу 9.. 14 ?
2. Як має змінюватись значення оптимальної довжини коду при змінах ймовірності р?
3. Як має змінюватись швидкість кодування при змінах кількості сегментів ?
4. Як варто змінити структуру сегментів, якщо ймовірність р >0.5 ?
5. Яким умовам повинно відповідати значення ймовірністі р, щоб метод Хафмана сформував код відповідаючий структурі КДС ?
6. Поразка яких кодових символів у словах КДС може призвести до трекових помилк при декодуванні ?
Рекомендована література.
1. Дмитриев В.И. Прикладная теория информации. –М.: Высшая Школа, 1989
2. Колесник В.Д. Курс теории информации. –М.: Наука,1982.
ДОДАТОК
UNIT COMMON;{ Модуль типів, що задає користувач }
INTERFACE
USES Crt,Graph;
CONST
DANTE='C:\BPFW\W_PROG\DATAFILS\'; {початок шляху до файлу даних (задають відповідно до конфігурації)}
MaxLaeng=64; {максимальна довжина одномірного масиву}
TYPE
Diapazon=0..MaxLaeng;
Rib=array[Diapazon] of integer;
VectX=array[byte] of real;
ZwoBIT=0..3;
T_MC=array[0..3] of rib;
VectorP=Array[Diapazon] of real;
MINTERM=Array[byte] of word;
TPunct=array[0..2] of Longint;
Trecht=array[0..1] of TPunct;
IMPLEMENTATION {Пусто}
BEGIN END.
МОДУЛЬ ОСНОВНИХ І СЕРВІСНИХ ПРОЦЕДУР
UNIT OSTIN;
INTERFACE
USES Crt,COMMON, Graph;
{сервисные процедуры}
Procedure Warten;
Procedure WritVectorP(P:vectorP;NAME:String;Np,Sv:byte);
Procedure ReadVectorP(var P:vectorP;NameP:string;var Np:byte);
Procedure WrtCODENCOD(MC:T_MC;NAME:string;L,nn:byte);
Procedure ReadCODENCOD(var MCD:T_MC;NAME:string;var L:byte);
Procedure ReadMINTERM(var Mnt:Minterm;var N,Mt:word;NAME:string);
{основные процедуры}
Function DCDHUFF(C:byte;MCC:T_MC;L:byte):byte;
Procedure HSHF_OPCOD(var MC:T_MC;Var Ls:Real;Var L:byte;P:vectorP;M:byte);
Function Log2(x:real):real;
Function HentN1(P:vectorP;N:byte):real;
Function Hent2(p:real):real;
Function DistI(P,Q:vectorP;N:byte):real;
Procedure FormyPs(var Ps:vectorP;p:real;N:byte);
Function Unrnd(p:real):byte;
Function EXP2(M:word):word;
Function Prb(P:VectorP;M,N:Word):real;
Function Stufe(A,x:real):real;
Function InStufe(A:real;x:integer):real;
{графические процедуры}
Function IN_CIRCLE(X1,Y1,R,X,Y:Real):Boolean;
Function IN_Rectangle(X1,Y1,X2,Y2,X,Y:real):Boolean;
Procedure GraphIn;
Procedure WartenGR;
IMPLEMENTATION
{сервисные процедуры}
Procedure Warten; {Процедура затримки цифрового зображення на екрані}
var CVC:Char;
begin
Repeat cvc:=ReadKey Until cvc='P';
end; {Для виходу з процедури необхідно натиснути клавішу ( }
Procedure WritVectorP;
Var i:byte;F:TEXT;
Begin
Case Sv of
1:Begin {Запис на диск та вивід на екран}
Assign(F,NAME);Reset(F);Rewrite(F);Write(F,Np);Writeln(F);
for i:=1 to Np do
begin
Write(F,P[i]:12:6);write(P[i]:9:4);
end;
Close(F);
end;
2:Begin {Режим виводу тільки на єкран}
For i:=1 to Np do
begin
Write(P[i]:9:4);if ((i-1) mod 8)=7 then Writeln;
end;
end;
End;{CASE}Writeln;
End;
Procedure ReadVectorP; {Читання розподілу ймовірностей із зовнішнього файла }
var i:byte;F:TEXT;
Begin
Assign(F,NameP);Reset(F); Read(F,NP);
for i:=1 to Np do Read(F,P[i]);
Close(F);
End;
Procedure ReadMINTERM;{Процедура считывания конституент единицы}
var i:word;F:TEXT;
Begin
assign(F,NAME); Reset(F); Read(F,N,Mt);
for i:=1 to Mt do
begin
Read(F,Mnt[i]);
if Mnt[i]>(Exp2(N)-1)
Then
begin
writeln(' в данных ошибка ');Close(F);Exit;
end;
end;
Close(F);
End;
Procedure WrtCODENCOD;
{процедура вывода матрицы кодирования_декодирования
MC[0],MC[1] - декодер MC[2] - дерево реверсного кодирования MC[3] - кодовые символы}
var
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора