Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Автоматизовані Системи Управління
Інформація про роботу
Рік:
2024
Тип роботи:
Методичні вказівки
Предмет:
Компютерні мережі
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ ТА НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ
«ЛЬВІВСЬКА ПОЛІТЕХНІКА»
Кафедра:
Автоматизовані системи управління
Методичні вказівки
з курсу «Компютерні мережі»
Лабораторна робота №1
Тема роботи: ВИЗНАЧЕННЯ ЕНТРОПІЙНИХ ХАРАКТЕРИСТИК ОБ’ЄКТІВ КОМП’ЮТЕРНИХ МЕРЕЖ .
Мета роботи: навчитися визначати ентропії джерела інформації, приймача, каналу зв’язку, системи взаємозв’язаних об’єктів.
Теоретичні відомості
Ентропія джерела інформації Х, що генерує незалежні повідомлення xi, обчислюється за формулою:
, (1)
де p(xi)- ймовірність появи повідомлення xi; N - кількість можливих повідомлень (символів, станів об’єкту)
Властивості ентропії
Ентропія завжди невід’ємна: .
Ентропія максимальна, коли значення xi випадкової величини X рівноймовірні:
. (2)
Максимальне значення ентропії
. (3)
Для полегшення обчислень ентропії використовують наведену у додатку 1 таблицю значень добутків
Розглянемо систему, що є об’єднанням двох статистично взаємозв’язаних об’єктів, наприклад, джерела Х з можливими станами x1, xi, xn та приймача Y з можливими станами y1, yj, ym...
Сумісна ентропія системи:
, (4)
де ( ймовірність сумісної появи i-го стану в об’єкті X та j-го стану в об’єкті Y.
Якщо об’єкти X та Y незалежні, то сумісна ентропія дорівнює сумі ентропій окремих об’єктів:
. (5)
Ентропія об’єкту Y (приймача), знайдена за умови, що об’єкт Х згенерував повідомлення хi, називається частковою умовною ентропією об’єкту Y. Її визначають за формулою:
(6)
де p(yj/xi) ( ймовірність події yj за умови, що в об’єкті X відбулася подія xi або ймовірність того, що приймач прийме символ yj за умови, що джерело передало символ xi.
Середню або повну умовну ентропію об’єкту Y відносно об’єкту X називають просто умовною ентропією, позначають H(Y/X) і визначають за формулою:
. (7)
Для незалежних об’єктів
, (8)
. (9)
Формули (10) та (11) показують взаємозв’язок ентропії об’єкту, сумісної та умовної ентропій.
(10)
, (11)
де H(X) ( ентропія (безумовна) об’єкту Х;
H(Y) ( ентропія (безумовна) об’єкту Y;
H(X,Y) – сумісна ентропія;
H(Y/X) ( умовна ентропія об’єкту Y відносно об’єкту Х;
H(X/Y) ( умовна ентропія об’єкту X відносно об’єкту Y.
Через часткову і повну умовну ентропії описують інформаційні втрати при передачі даних в каналі зв'язку з завадами. Для цього застосовують так звані канальні матриці. В якості елементів канальної матриці звичайно використовують умовні ймовірності p(yj/xi) отримання приймачем Y символу yj за умови, що джерелом Х був відправлений символ xi. При цьому канальна матриця P(Y/X)має наступний вигляд:
. (12)
Ймовірності, що є елементами головної діагоналі матриці, описують ймовірність правильного прийому. Втрати, які мали місце при передачі сигналу xi, описуються через часткову умовну ентропію:
(13)
Для обчислення всіх втрат при передачі всіх сигналів використовується умовна (повна) ентропія:
(14)
Для визначення ентропії приймача H(Y) за умови, що відома ентропія джерела H(X) і канальна матриця P(Y/X), необхідно знайти ймовірності появи символів на вході приймача p(yj):
. (15)
Взаємозв'язок переданих і отриманих символів може бути описаний також матрицею сумісних ймовірностей P(X,Y):
. (16)
Сума всіх елементів стовпчика з номером j дає p(yj), сума рядка з номером i дорівнює p(xi), а сума всіх елементів матриці рівна 1. Сумісна ймовірність p(xi, yj) обчислюється таким чином:
. (17)
На практиці джерело Х найчастіше буває недоступне безпосередньому спостереженню, і його стан з’ясовується за допомогою деякого об’єкту Y, певним чином пов’язаного з об’єктом X. Для визначення кількості інформації IY->X, що міститься в об’єкті Y (приймачі) про об’єкт X (джерело) використовують взаємну ентропію H(Y->X).
Взаємна кількість інформації IY->X
IY->X = IX->Y = IY<->X = IX<->Y = H(Y->X) = H(X->Y) = H(X<->Y). (18)
Взаємна ентропія
. (19)
Формули (20) та (21) показують взаємозв’язок взаємної ентропії з іншими видами ентропій:
H(X<->Y) = H(Y) – H(Y/X) = H(X) – H(X/Y), (20)
H(X<->Y) = Н(Х) + Н(Y) – Н(Х, Y) = IX->Y. (21)
Для ілюстрації формули (21) наведено рисунок, що дозволяє краще зрозуміти суть взаємної ентропії та взаємної кількості інформації.
Рис.1 До визначення взаємної інформації.
Хід роботи
Ознайомитися з теоретичним матеріалом пов’язаним з тематикою лабораторної роботи.
Системи X і Y працюють в алфавіті, що нараховує N+2 рівноімовірні символи.
Умовна ймовірність р(yi /xi) = 0,k для всіх j<>i, одна з ймовірностей р(yj/xi) = 1- 0,k.
N – передостання цифра студентського квитка
k – остання цифра студентського квитка
Нарисувати схему ймовірнісних переходів.
Знайти:
ентропію системи X;
ентропію системи Y;
часткову умовну ентропію H(Y/x2);
повну умовну ентропію;
сумісну ентропію;
взаємну ентропію.
Дати графічне представлення втрат в каналі зв’язку для каналу зв’язку, заданого викладачем.
Знайти і порівняти ентропії джерел з різними законами розподілу.
Знайти ентропії українського тексту і тексту, записаного мовою, заданою викладачем. Порівняти іх. Зробити висновок щодо надлишковості мов, що порівнювались.
Оформити звіт по лабораторній роботі.
Лабораторна робота №2
Тема роботи: ЕФЕКТИВНЕ КОДУВАННЯ.
Мета роботи: ознайомитися з алгоритмами ефективного кодування: Шеннона-Фано і Хаффмана.
Теоретичні відомості
Ефективне кодування використовується для зменшення часу передачі або обсягу запам'ятовувального пристрою і базується на основній теоремі Шеннона для каналів без шуму. Шеннон довів, що повідомлення, складені з символів деякого алфавіту, можна закодувати так, що середня кількість двійкових символів на букву буде як завгодно близькою до ентропії джерела цих повідомлень, але не менше цієї величини.
Для кодування символів вихідного алфавіту використовують двійкові коди змінної довжини: чим більша частота появи символа, тим коротший його код. Ефективність коду визначається середньою кількістю двійкових розрядів для кодування одного символу – Lср за формулою
(1)
де k – число символів вихідного алфавіту;
ni – число двійкових розрядів для кодування символу i;
p(xi) – частота символу i; причому
При ефективному кодуванні існує межа стиску, нижче якого не «спускається» жоден метод ефективного кодування - інакше буде загублена інформація. Цей параметр визначається мінімальною кількістю двійкових розрядів у кодовому слові можливого ефективного коду – Lmin:
(2)
де k – кількість символів кодованого алфавіту,
p(xi)– частота появи i-го символу алфавіту.
Існують два класичних методи ефективного кодування: метод Шеннона-Фано і метод Хаффмана. Вхідними даними для обох методів є задана множина символів алфавіту для кодування з частотами їх появи; результат – кодові комбінації ефективного коду.
Метод Шеннона-Фано
Множина вхідних символів впорядковується по спаданню ймовірностей їх появи в алфавіті.
Множина символів ділиться на дві частини (першу і другу) таким чином, щоб сумарні частоти обох частин були приблизно одинакові. У випадку якщо точної рівності досягнути не вдається, різниця між ними повинна бути мінімальна.
Кодовим комбінаціям першої частини записують 1, другої частини записується 0.
Аналізують першу частину, якщо вона містить один символ, то робота з нею завершується – вважається, що код для цієї частини вже побудований і переходимо до кроку 5.
Аналізують другу частину, якщо вона містить один символ, то робота з нею завершується - вважається що код для цієї частини вже побудований і переходимо до кроку 2 і процедура повторюється знову.
Аналізують множину символів котра залишилася, якщо вона пуста - то робота завершена і код побудований, якщо ні переходять до кроку 2.
Приклад 1.
Символи
Частоти
a
0,5
1
b
0,25
0
1
1
c
0,125
0
0
0
d
0,125
0
0
Метод Хаффмана
Цей метод має дві переваги в порівнянні з методом Шеннона-Фано: він усуває неоднозначність кодування, що виникає через рівність сум частот при поділі списку на дві частини (лінія розподілу проводиться неоднозначно), і має, у загальному випадку, більшу ефективність коду.
Алгоритм методу наступний:
1. Вихідна множина символів впорядковується по спаданню ймовірностей появи.
2. Знаходимо два символи з найменшими ймовірностями появи і об’єднуємо їх «склюємо» їх у складне повідомлення з сумарною ймовірністю появи.
3. Записуємо новий ансамбль повідомлень, в якому кількість повідомлень порівняно з попереднім зменшилась за рахунок введення складного повідомлення.
4. Якщо ансамбль містить більше ніж 2 повідомлення переходимо на крок 2, інакше прочинаємо процес розклеювання.
5. Одному з повідомлень в старшому розряді присвоюємо «0» іншому – «1».
6. Здійснюємо зворотню процедуру по відношенню до склеювання, визначаючи на кожному етапі наступний розряд доти, поки не будуть закодовані всі повідомлення.
Приклад 2.
Символи
Частоти
Етапи об’єднання
Перший
другий
a
0,5
0,5
0
0,5
0
b
0,25
0,25
1 0
0,5
1
c
0,125
0,25
1 1
d
0,125
Графічний метод Хаффмана
1.Вихідна множина символів впорядковується по спаданню ймовірностей появи.
2. Знаходимо два символи з найменшими ймовірностями появи. За дпомогою ребер їх з’єднуємо у вузол вищого рангу. Присвоюємо цьому вузлу сумарну ймовірність появи повідомлень, що об’єднуються.
3. Повторюємо крок 2 поки не дійдемо вершини дерева, тобто сумарна ймовірність вузла не рівна 1.
4. Використовуючи побудоване дерево знаходимо кодові комбінації, що відповідають кожному символу.
Приклад 3.
Символи
Частоти
a
0,5
b
0,25
c
0,125
d
0,125
Кодове дерево
Хід роботи
Ознайомитися з теоретичним матеріалом пов’язаним з тематикою лабораторної роботи.
Згідно даних індивідуального завдання побудувати код Шеннона-Фано. Знайти середню Lср і мінімальну Lmin довжину кодового слова.
Згідно даних індивідуального завдання побудувати код Хаффмана звичайним методом. Знайти середню Lср і мінімальну Lmin довжину кодового слова.
Згідно даних індивідуального завдання побудувати код Хаффмана графічним методом. Знайти середню Lср і мінімальну Lmin довжину кодового слова.
Здійснити кодування блоками, використовуючи метод Хаффмана, коли довжина блоку n=2, n=3.іііі
Побудувати графік залежності мінімальної довжини кодового слова Lmin від довжини блоку n.
Оформити звіт по лабораторній роботі.
Варіанти індивідуальних завдань.
Для методу Шеннона-Фано і Хаффмана
P(x1)= 0.1 ; P(x2)= 0.2; P(x3)= 0.4; P(x4)= 0.1; P(x5)= 0.05; P(x6)= 0.05; P(x7)= 0.1
P(x1)= 0.1 ; P(x2)= 0.07; P(x3)= 0.1; P(x4)= 0.03; P(x5)= 0.35; P(x6)= 0.25; P(x7)= 0.1
P(x1)= 0.2 ; P(x2)= 0.1; P(x3)= 0.2; P(x4)= 0.1; P(x5)= 0.1; P(x6)= 0.2; P(x7)= 0.1
P(x1)= 0.15 ; P(x2)= 0.1; P(x3)= 0.3; P(x4)= 0.1; P(x5)= 0.05; P(x6)= 0.25; P(x7)= 0.05
P(x1)= 0.05 ; P(x2)= 0.033; P(x3)= 0.1; P(x4)= 0.05; P(x5)= 0.033; P(x6)= 0.7; P(x7)= 0.034
P(x1)= 0.15 ; P(x2)= 0.35; P(x3)= 0.15; P(x4)= 0.1; P(x5)= 0.05; P(x6)= 0.15; P(x7)= 0.05
P(x1)= 0.01 ; P(x2)= 0.07; P(x3)= 0.3; P(x4)= 0.23; P(x5)= 0.2; P(x6)= 0.1; P(x7)= 0.09
P(x1)= 0.06 ; P(x2)= 0.16; P(x3)= 0.12; P(x4)= 0.16; P(x5)= 0.12; P(x6)= 0.32; P(x7)= 0.06
P(x1)= 0.17 ; P(x2)= 0.21; P(x3)= 0.17; P(x4)= 0.15; P(x5)= 0.17; P(x6)= 0.06; P(x7)= 0.07
P(x1)= 0.25 ; P(x2)= 0.25; P(x3)= 0.25; P(x4)= 0.05; P(x5)= 0.08; P(x6)= 0.08; P(x7)= 0.04
P(x1)= 0.06 ; P(x2)= 0.11; P(x3)= 0.2; P(x4)= 0.09; P(x5)= 0.11; P(x6)= 0.03; P(x7)= 0.4
P(x1)= 0.1 ; P(x2)= 0.2; P(x3)= 0.3; P(x4)= 0.1; P(x5)= 0.1; P(x6)= 0.1; P(x7)= 0.1
P(x1)= 0.25 ; P(x2)= 0.2; P(x3)= 0.18; P(x4)= 0.15; P(x5)= 0.1; P(x6)= 0.08; P(x7)= 0.04
P(x1)= 0.02 ; P(x2)= 0.03; P(x3)= 0.28; P(x4)= 0.05; P(x5)= 0.1; P(x6)= 0.1; P(x7)= 0.42
P(x1)= 0.08 ; P(x2)= 0.13; P(x3)= 0.23; P(x4)= 0.13; P(x5)= 0.08; P(x6)= 0.26; P(x7)= 0.09
Для кодування блоками
P(x1)= 0.3 ; P(x2)= 0.3; P(x3)= 0.4;
P(x1)= 0.6 ; P(x2)= 0.25; P(x3)= 0.15;
P(x1)= 0.1 ; P(x2)= 0.8; P(x3)= 0.1;
P(x1)= 0.3 ; P(x2)= 0.1; P(x3)= 0.6;
P(x1)= 0.8 ; P(x2)= 0.15; P(x3)= 0.05;
P(x1)= 0.16 ; P(x2)= 0.34; P(x3)= 0.5;
P(x1)= 0.3 ; P(x2)= 0.45; P(x3)= 0.25;
P(x1)= 0.73 ; P(x2)= 0.14; P(x3)= 0.13;
P(x1)= 0.45 ; P(x2)= 0.11; P(x3)= 0.44;
P(x1)= 0.20 ; P(x2)= 0.56; P(x3)= 0.24;
P(x1)= 0.45 ; P(x2)= 0.32; P(x3)= 0.23;
P(x1)= 0.1 ; P(x2)= 0.69; P(x3)= 0.21;
P(x1)= 0.9 ; P(x2)= 0.05; P(x3)= 0.05;
P(x1)= 0.2 ; P(x2)= 0.44; P(x3)= 0.36;
P(x1)= 0.25 ; P(x2)= 0.51; P(x3)= 0.24.
Лабораторна робота №3
Тема роботи: СТИСНЕННЯ ІНФОРМАЦІЇ НА ОСНОВІ АЛГОРИТМУ ЛЕМПЕЛА- ЗІВА-ВЕЛЧА
Мета роботи: ознайомитися з роботою алгоритму Лемпела-Зіва-Велча. Навчитися стискати інформацію на основі цього алгоритму.
Теоретичні відомості
Історія алгоритму LZW розпочинається з публікації в травні 1977р. Дж.Зівом (J.Ziv) і А.Лемпелем (A.Lempel). В подальшому цей алгоритм був доопрацьований Террі А. Велчем (Terry A.Welch) і в остаточному варіанті був опублікований в статті "A Technique for High-Performance Data Compression", у червні 1984р. В статті описувалися деталі алгоритму і деякі загальні проблеми з якими можна зіткнутися при його реалізації. Пізніше цей алгоритм отримав назву LZW (Lempel-Ziv-Welch).
Стиснення за допомогою алгоритму LZW є надзвичайно ефективним для текстових файлів, хоча коефіцієнт стиснення більше ніж 50% є можливим і для файлів інших форматів. На сьогодні алгоритм LZW є найкращим алгоритмом багатоцільового стиснення даних. Високошвидкісні модеми для стиснення даних ( V.42 bis) використовують цей алгоритм, так само як і всім відома програма-утиліта ZIP.
До основних переваг алгоритму можна віднести:
Відсутність необхідності попереднього аналізу даних;
Динамічну адаптацію до специфіки даних, що стискаються;
Не потрібно розміщати кодову таблицю у стиснений файл, тобто стиснена інформація містить всі необхідні дані для декомпресії.
Алгоритм кодування LZW
Суть алгоритму кодування LZW (наведеного нижче) полягає в тому, що створюється таблиця, в якій кожному символу або їх групі присвоюється число. Перед початком кодування в ініціюючу частину таблиці записуються всі символи вхідного тексту, які зустрічаються хоча б один раз. Під час кодування здійснюється по символьне читання вхідного тексту. Якщо зчитаний символ є в таблиці, то читається наступний. Якщо комбінації першого і другого символів ще немає в таблиці, то вона записується туди під останнім номером, а замість першого символу виводиться його числове значення з таблиці. Якщо ж комбінація двох символів є в таблиці, то читається наступний символ, і в таблиці вже перевіряється присутність комбінації із трьох символів. Процес триває доти, доки не будуть закодовані усі символи вхідного тексту.
Кодування тексту aaabbabab (див. рис.1)
Алгоритм кодування ЛЗВ
STRING = get first input character
while there are more input characters
CHARACTER = next input character
if STRING + CHARACTER is in STRING TABLE
STRING=STRING + CHARACTER
else
output the code for STRING
add STRING + CHARACTER to STRING TABLE
STRING = CHARACTER
end if
end while
output the code for STRING
Алгоритм декодування LZW
Текст для декодування: 13221621 (див. рис.2)
Алгоритм декодування ЛЗВ
OLDCODE = input first code
CHARACTER = translation of OLDCODE
output translation of OLDCODE
while there is more input data
NEWCODE = get next input code
if NEWCODE is not in STRING TABLE then
STRING = translation of OLDCODE
STRING = STRING + CHARACTER
else
STRING = translation of NEWCODE
end if
output STRING
CHARACTER = first character of STRING
add OLDCODE + CHARACTER to STRING TABLE
OLDCODE = NEWCODE
end of while
Режими роботи програми
Для вивчення роботи і засвоєння алгоритму LZW було створено навчальну програму. Програма передбачає три режими роботи.
Перший режим – Демонстрація роботи алгоритму LZW – надає користувачеві можливість вивчити принцип роботи даного алгоритму шляхом візуальної демонстрації по крокового виконання кодування чи декодування заданого користувачем текстового рядка.
Другий режим – Кодування/декодування файлів – надає користувачеві можливість оцінити ефективність алгоритму LZW при здійсненні стиснення з його допомогою файлів різного формату.
Третій режим – Оцінка вивчення алгоритму LZW – дозволяє користувачеві оцінити свій рівень знання і розуміння алгоритму кодування/декодування LZW.
Демонстрація роботи алгоритму LZW
Для запуску цього режиму роботи у головному вікні програми необхідно виділити відповідний пункт і натиснути кнопку “ЗАПУСК”. Далі відкривається вікно, в якому і здійснюється режим демонстрації. Для початку роботи необхідно задати текст для кодування у відповідному вікні вводу і натиснути кнопку “ВИКОНАТИ”. Якщо вікно вводу буде порожнім, то запуск кодування є неможливим – програма видає відповідне повідомлення. Якщо задано текст і програма знаходиться в режимі кодування, активізуються кнопки “ПОКРОКОВЕ ВИКОНАННЯ” та “ПРИПИНИТИ”. При кожному натисненні кнопки “ПОКРОКОВЕ ВИКОНАННЯ” виконується один крок алгоритму кодування, що підтверджується виділенням відповідного рядка у вікні алгоритму та заповнненням таблиці. Закодувавши введений текст, користувач має можливість спостерігати процес по крокового декодування, вибравши закладку “ДЕКОДУВАННЯ” і натиснути кнопку “ВИКОНАТИ”. Режим декодування є можливим за умови, що попередньо вже було закодовано якийсь текст.
Процес кодування/декодування можна завчасно перервати натиснувши кнопку “ПРИПИНИТИ”.
Оцінка вивчення алгоритму Лемпела-Зіва-Велча
Для запуску цього режиму роботи у головному вікні програми необхідно виділити відповідний пункт і натиснути кнопку “ЗАПУСК”. Далі відкривається вікно, в якому і здійснюється цей режим. Для початку роботи необхідно задати текст для кодування у відповідному вікні вводу і натиснути кнопку “ВИКОНАТИ”. Якщо вікно вводу буде порожнім, то запуск кодування є неможливим – програма видає відповідне повідомлення. Якщо задано текст і програма знаходиться в режимі кодування, активізуються кнопки “ПОКРОКОВЕ ВИКОНАННЯ” та “ПРИПИНИТИ”. При кожному натисненні кнопки “ПОКРОКОВЕ ВИКОНАННЯ” виконується один крок алгоритму кодування, що підтверджується виділенням відпорідного рядка у вікні алгоритму та заповненням таблиці. При здійсненні покрокового виконання користувач власноручно заповнює таблицю кодування/декодування. На кожному кроці програма перевіряє правильність заповнення відповідної комірки таблиці. Якщо виявлено помилку, то видається відповідне повідомлення. Закодувавши введений текст, користувач має можливість перевірити свій рівень знання алгоритму декодування LZW, вибравши закладку “ДЕКОДУВАННЯ” і натиснути кнопку “ВИКОНАТИ”. Режим декодування є можливим за умови, що попередньо вже було закодовано якийсь текст. Процес кодування/декодування можна завчасно перервати натиснувши кнопку “ПРИПИНИТИ”.Виконавши кодування/декодуваня програма відповідно до кількості помилок і розміру вхідного тексту виставляє користувачеві оцінку.
Режим кодування/декодування файлів
Режим кодування/декодування файлів надає користувачеві можливість оцінити ефективність алгоритму LZW при здійсненні стиснення з його допомогою файлів різного формату.
Для запуску цього режиму роботи у головному вікні програми необхідно виділити відповідний пункт і натиснути кнопку “ЗАПУСК”. Далі відкривається вікно, в якому користувач має можливість здійснити компресію чи декомпресію вибраного файлу і оцінити коефіцієнт його стиснення.
Щоб стиснути файл користувач може його вибрати у вікні відображення файлів біжучої директорії. Біжучу директорію та диск можна змінювати у вікні вибору директорії чи диску. Вибравши файл, його ім’я вводиться у вікні вхідного файлу. Водночас автоматично у вікні результуючого файлу з’являється ім’я файлу, в який буде записано стиснуті дані ( ім’я вхідного файлу, проте розширення замінене на .lzw). Користувач також має можливість власноручно задавати ім’я результуючого файлу.
Щоб розпочати процес стиснення користувачеві слід натиснути кнопку “ВИКОНАТИ”. Якщо стиснення пройде успішно, то з’явиться вікно, де будуть графічно показані розміри вхідного і стиснутого файлів. У іншому разі програма видасть відповідне повідомлення.
Для декомпресії користувач вибирає попередньо стиснутий файл. У вікні відобаження файлів біжучої директорії показано вже не всі файли, а тільки ті, які мають розширення .lzw. Ім’я розтиснутого файлу користувач задає сам. Наступні кроки будуть такими самими, як і при виконанні стиснення.
Хід роботи
1.Ознайомитися з теоретичним відомостями по темі лабораторної роботи.
2. Здійснити кодування і декодування власного прізвища записаного два рази без пропуску.
3.Завантажити програму LZWteach.EXE.
4.У Режимі демонстрація роботи алгоритму LZW ознайомитися з роботою алгоритму на прикладі введеної послідовності символів.
5.У Режимі оцінка вивчення алгоритму Лемпела-Зіва-Велча ввести послідовність задану викладачем і самостійно виконувати кодування і декодування заданої послідовності символів.
6.Виконати стиснення декількох файлів різного типу (текстових, програм , рисунків) у Режимі кодування/декодування файлів. Оцінити ефективність стиснення на файлах різного типу- побудувати гістограму в якій для файлів різного типу вказати початковий об’єм файлу і об’єм стисненого файлу. Для прикладу взяти 5 файлів різного типу.
7.Оформити звіт.
Лабораторна робота №4
Тема роботи: КОД ХЕМІНГА
Мета роботи: вивчення кодування та декодування інформації за допомогою коду Хеммінга
Теоретичні відомості
Код Хемінга - це код, який виявляє і виправляє одиничні помилки і виявляє подвійні помилки. Код Хемінга відноситься до систематичних кодів.
Систематичні коди -- це коди, в яких інформаційні та надлишкові символи розташовані на певних наперед визначених місцях. Код Хемінга, як і будь-який (n,k)-код, містить k інформаційних і (n-k) надлишкових символів. Надлишкова частина коду будується таким чином, щоб при декодуванні можна було б встановити не лише факт наявності помилок в даній комбінації,але й вказати номер позиції, в якій помилка. Здійснити це можна шляхом багатократної перевірки прийнятої комбінації на парність. Кількість перевірок рівна кількості надлишкових символів. При кожній перевірці отримують двійковий контрольний символ. Якщо результат перевірки дає парне число, то контрольному символу присвоюється ”0”, якщо непарне - то “1”. В результаті всіх перевірок утворюється (n-k)-розрядне двійкове число, що вказує на номер спотвореного символа. Для виправлення помилки достатньо змінити значення символа, який стоїть у позиції ( перевід (n-k)двійкового розрядного числа у десяткове число) на протилежне.
Необхідна кількість надлишкових символів виводиться з формули:
Кодування
Кодується деяка інформація подана у вигляді у двійковій формі( послідовності нулів і одиниць) k1 k2 k3 k4 k5 k6 ... kn.
Нехай кодова довжина (довжина відрізків, на які ділиться потік) рівна 7 біт. Для того, щоб їх закодувати, потрібно на певні визначені місця внести надлишкові символи, які потім допоможуть декодувати цей потік.
В коді Хемінга надлишкові символи ставляться на тих позиціях в кодовій комбінації, що є степенями числа 2. Тобто, вихідною стрічкою буде потік
b1 b2 b3 b4 b5 b6 b7 b8 b9 b10 b11
r1 r2 k1 r3 k2 k3 k4 r4 k5 k6 k7
де r[i] - надлишкові символи, k[i] - інформаційні символи.
Складають кодову комбінацію з інформаційних і надлишкових символів, позиції надлишкових символів є степенями 2 (1, 2, 4, 8, 16, 32, …), а також при цьому позицію кожного символа(і інформаційних) у кодовій комбінації представляють у двійковій системі числення.
00001 b1 r1=k1 xor k2 xor k4 xor k5
00010 b2 r2=k1 xor k3 xor k4
00011 b3 k1
00100 b4 r3=k2 xor k3 xor k4
00101 b5 k2
00110 b6 k3
00111 b7 k4
01000 b8 r4=k5 xor k6 xor k7
01001 b9 k5
01010 b10 k6
01011 b11 k7
Надлишкові символи знаходять таким чином:
r1-це сума по модулю 2 (xor) тих k[i], в яких в першому розряді порядкового номера є "1";
r2-це сума по модулю 2(xor) тих k[i], в яких в другому розряді порядкового номера є"1";
r3- це сума по модулю 2 (xor) тих k[i], в яких в третьому розряді порядкового номера є "1";
r4- це сума по модулю 2 (xor) тих k[i], в яких в четвертому розряді порядкового номера є "1";
Приклад. Закодувати текст 1111101111 в коді Хемінга, кількість надлишкових і інформаційних дорівнює 9). Для цього потрібно текст поділити і додати надлишкові символи на потрібні позиції.
k1k2k3k4k5.k1k2k3k4k5
1 1 1 1 1 .0 1 1 1 1
Перше слово :
r1 = 1 xor 1 xor 1 xor 1 = 0
r2 = 1 xor 1 xor 1 = 1
r3 = 1 xor 1 xor 1 =1
r4 = 1
Друге слово :
r1 = 0 xor 1 xor 1 xor 1 = 1
r2 = 0 xor 1 xor 1 = 0
r3 = 1 xor 1 xor 1 = 1
r4 = 1 xor 1 xor 1 = 1
Результат : r1r2k1k2k3k4r4k5.r1r2k1r3k2k3k4r4k5
0 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1
Декодування
Для декодування записують систему рівнянь наступного вигляду:
r1 xor k1 xor k2 xor k4 xor k5 xor k7 xor… = С1 ,
r2 xor k1 xor k3 xor k4 xor k6 xor k7xor… = С2 ,
r3 xor k2 xor k3 xor k4 xor …=С3
r4 xor k5 xor k6 xor k7xor… = С4
Якщо кодове слово правильне, то система рівнянь виконується (тобто С1=С2=С3=С4=0). Якщо в кодовому слові є помилка, то права частина системи буде складатись не лише з нулів. Праву частину називають синдромом або розпізнавачем помилки. Щоб знайти помилку, необхідно прочитати синдром знизу вверх (С4С3С2С1) і перевести його в 10-ву систему числення- одержане число буде номером спотвореного символа.
Режими роботи програми
Програма написана для роботи в операційній системі Windows. Після її завантаження користувачу видається головна форма для вибору режиму роботи (навчання чи перегляд; кодування, декодування чи транспортування файлів). В режимах навчання кодування і декодування здійснюється лише над одним словом. В режимі перегляду вводиться рядок довільної довжини. Результати відображаються у нижньому вікні.
У режимі транспортування потрібно вибрати файл який ви хочете транспортувати , ввести рівень завад і кодову довжину і натиснути клавішу TRANSPORT. Програма перетворить цей файл в двійковий (з розширенням *.t2b). Потім закодує (утвориться файл з розширенням *.hem). Виходячи з заданого рівня завад, внесе в нього помилки (*.trp), після цього розкодує з виправленнями помилок(*.rhm) і перетворить назад в текстовий (*.t2b). Після цього треба натиснути клавішу VIEW RESULTS . З’явиться діалогове вікно , в якому треба вибрати відповідний файл (з розширенням *.t2b) і натиснути OPEN. З’явиться форма з двома вікнами. У верхньому показано початковий файл, в нижньому - переданий.
Хід роботи
1.Ознайомитися з теоретичним матеріалом по темі лабораторної роботи.
2.Закодувати повідомлення вручну кодом Хемінга з кодовою відстанню d=3 і d=4.
3. Декодувати повідомлення закодовані в п.2.
4.Запустити на виконання програму Hemming.Exe.
5.Пройти режими Кодування(перегляд) та Декодування(перегляд).
6.Виконати кодування двійкової інформації в режимі Кодування(навчання)
7. Виконати декодування двійкової інформації в режимі Декодування(навчання)
8.Переглянути моделювання передачі текстової інформації по мережі за допомогою режиму Транспортування . Накреслити графіки залежностей рівня завад від кількості виправлених плмилок при різних значеннях кодового слова
9.
31.03.2013 00:03-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора