• Гідрологія і Гідрометрія
• Господарське право
• Економіка будівництва
• Економіка природокористування
• Економічна теорія
• Земельне право
• Історія України
• Кримінально виконавче право
• Медична радіологія
• Методи аналізу
• Міжнародне приватне право
• Міжнародний маркетинг
• Основи екології
• Предмет Політологія
• Соціальне страхування
• Технічні засоби організації дорожнього руху
• Товарознавство продовольчих товарів

Порядок виконання роботи

1. Використовуючи методику Хаффмена і Шеннона-Фано, здійснити оптимальне і ефективне кодування ансамблю повідомлень з вірогідністями відповідно:

z1 = 0,22; z2 = 0,20; z3 = 0,16; z4 = 0,16; Z5 = 0,10; Z6 = 0,10;

z7 = 0,04; z8 = 0,02.

2. Перевірити оптимальність коду.

3. Розрахувати середню довжину кодового слова.

4. Ввести текст для кодування англійською мовою.

5. Виконати кодування методом Хаффмена.

6. Записати та проаналізувати результати кодування. Проверить оптимальность кода.

7. Виконати кодування методом Шенона-Фано.

8. Записати та проаналізувати результати кодування. Проверить оптимальность кода.

9. Порівняти результати стиснення обома методами.

10. Завантажити програму huffman.exe.

11. Ознайомитись з панеллю програми.

12. Ввести текст для кодування англійською мовою.

13. Виконати кодування методом Хаффмена та Шенона-Фано.

14. Порівняти результати кодування обома методами.

Контрольні запитання

1. Який код називається оптимальним?

2. Який код називається префіксним?

3. Який принцип алгоритму кодування Хаффмена?

4. Який принцип алгоритму кодування Шенона-Фано?

5. До яких кодів належить метод Хаффмена?

6. До яких кодів належить метод Шенона-Фано?

7. У чому полягає сутність оптимального кодування і практичний результат його застосування?

8. Як оцінюється ефективність ОНК?

9. Як перевірити оптимальність коду?

10. Які коди називаються оптимальними нерівномірними кодами?

Лабораторна робота № 5

Дослідження завадозахищених кодів

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

Теоретичні відомості

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

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

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

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

Друга теорема Шеннона:

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

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

При цьому можна в якості самостійних розглянути дві ситуації:

• кодування забезпечує тільки встановлення факту спотворення інформації - в цьому випадку виправлення здійснюється шляхом її повторної передачі;

• кодування дозволяє локалізувати і автоматично виправити помилку передачі (зберігання).

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

Надійність забезпечується тим, що поряд з бітами, безпосередньо кодуючими повідомлення (будемо називати їх інформаційними бітами), передаються (зберігаються) додаткові біти, станом яких можна судити про правильність передачі (будемо називати їх контрольними бітами). При рівномірному кодуванні повідомлення довжина кодової ланцюжка на знак (або групу знаків) k до складається з довжини інформаційної частини k_i, і числа контрольних бітів k_c. Очевидно, k ≥ k_i. Зручно визначити надмірність повідомлення для реального каналу L наступним чином:

Надлишкові завадозахисні коди широко застосовуються для виявлення й виправлення помилок при передачі даних і їхньому зберіганні в ЗП ЕОМ. Коригувальна здатність таких кодів оцінюється, в першу чергу, за такими показниками: кратність помилок, що виявляють у кодовому слові (r) і кратність помилок, що виправляють (s). Значення перших двох показників визначаються мінімальною кодовою відстанню D_min, при цьому справедливо D_min ≥ r + 1, D_min ≥ 2s + 1 і D_min ≥ r + s + 1. Значення r і s, визначені виходячи з D_min, гарантовані у всіх випадках. У деяких ситуаціях, наприклад, кратність помилок, що виявляють, може бути й вище.

Сфера застосування різних надлишкових кодів визначається особливостями їхньої технічної реалізації.

Нагадаємо, що відносна надмірність повідомлення — це характеристика, що показує, у скільки разів потрібно подовжити повідомлення, щоб забезпечити його надійну (безпомилкову) передачу (зберігання).

Кодова відстань (відстань Хеммінга)—це мінімальна кількість символів, яку потрібно змінити у кодовому слові, щоб отримати наступне (найближче) кодове слово.

Вагою W(А) кодової комбінації A називається число двійкових одиниць, що міститься в ній.

Можна сказати, що кодова відстань визначається числом позицій, в яких їх двійкові знаки не збігаються. Це означає, що кодова відстань між двійковими комбінаціями X і Y дорівнює вазі W(Z) деякої третьої комбінації Z, одержуваної порозрядним складанням за модулем 2 цих комбінацій тобто d = W (Z) = W (X Y).

Наприклад: Х = 100011100001011; Y = 100101000110011;

Z = X Y

X = 100011100001011

Y = 100101000110011

Z = 000110100111000, тобто d = 6.

Найбільш поширеним є код з контролем парності.

Код з перевіркою на парність утворюється додаванням до групи інформаційних двійкових знаків одного контрольного. Значення його вибирається таким чином, щоб загальне число одиниць у слові було парним або непарним. Після читання або запису даних у пам'ять перевіряється, чи збережено принцип запису. Код, у якому при D_min = 2, дозволяє виявляти однократні помилки в кодових словах. Варіант такого коду, що передбачає об'єднання кодових слів у блоки з контролем парності по рядку й стовпцю, має D_min = 4 і забезпечує s = 1 і r = 3. Такий код часто використовується при асинхронній посимвольній передачі даних. Виявляються одиночні помилки і групові з непарною кратністю. Доцільно доповнювати "до непари", щоб відрізнити "0" від відсутності інформації в слові, тому що в цьому випадку в слові буде хоча б одна одиниця.

Код Хеммінга дозволяє виправити поодинокі помилки в окремих кодових словах. Це, зокрема, необхідно при збереженні даних у напівпровідниковій пам'яті. Помилки, що виникають, з'являються в різних розрядах незалежно, а це означає, що імовірність однократної помилки на кілька порядків вище, ніж дво-, трикратної і т.д. Таким чином, головна задача — виправлення саме однократних помилок. Так, у коді 7,4 (тут n = 7 — загальне число розрядів, а k = 4 — кількість інформаційних розрядів у кодовому слові) D_min = 3 і s = 1. Такий код найчастіше застосовується при контролі даних в оперативному запам’ятовуючому пристрої (ОЗП).

Коди Хеммінга мають більшу відносну надмірність, ніж коди з перевіркою на парність і призначені або для виправлення одиночних помилок (при D_min = 3) або для виправлення одиночних і виявлення без виправлення подвійних помилок (D_min = 4). У такому коді n-значне число має m інформаційних і k контрольних розрядів. Кожен з контрольних розрядів є знаком парності для визначеної групи інформаційних знаків слова. При декодуванні виробляється k групових перевірок на парність. У результаті кожної перевірки у відповідний розряд регістра помилки записується 0, якщо перевірка була успішною, або 1 при виявленні непарності.

Групи для перевірки утворяться таким чином, що в регістрі помилки після закінчення перевірки виходить k-розрядне двійкове число, що показує номер позиції помилкового двійкового розряду. Зміна цього розряду — виправлення помилки.

Надлішкові завадозахісні коди широко застосовуються для виявлення й виправлення помилок при передачі даних и їхньому зберіганні в ЗП ЕОМ. Коригувальна здатність таких кодів оцінюється, в першу чергу, за такими Показники: Кратність помилок, что віявляють у кодовому слові (r) и кратність помилок, что віправляють (с). Значення перших двох показніків візначаються мінімальною кодовою відстанню D_min, при цьому справедливо D_min ≥ r + 1,

D_min ≥ 2s + 1 і D_min ≥ r + s + 1. Значення r і с, візначені віходячі з D_min, гарантовані у всех випадка. У деяк сітуаціях, наприклад, кратність помилок, что віявляють, может буті ї вищє.

Сфера застосування різніх надлишково кодів візначається особливістю їхньої технічної реализации.

Найбільш поширеним є код з контролем парності, який при D_min = 2 дозволяє віявляті однократні помилки в кодових слів. Варіант такого коду, что передбачає об'єднання кодових слів у блоки з контролем парності по рядку й стовпцю, має D_min = 4 і забезпечує s = 1 і r = 3. Такий код часто вікорістовується при асінхронній посімвольній передачі даних.

Код Хеммінга дозволяє виправити поодінокі помилки в окремому кодовому слові. Це, зокрема, застосовується при збереженні даних у напівпровідніковій пам'яті. Помилки, что вінікають, з'являються в різніх розряда незалежно, а це означає, что імовірність однократної помилки на кілька порядків вищє, ніж дво-, трікратної и т.д. Таким чином, головна задача - виправлення самє однократних помилок. Так, у коді 7,4 (тут n = 7 - загальне число розрядів, а k = 4 - кількість інформаційних розрядів у кодовому слові) D_min = 3 і s = 1. Такий код найчастіше застосовується при контролі даних в оперативному запам'ятовуючому пристрої (ОЗП).

Читайте також:

1. I. Аналіз контрольної роботи.
2. I.1. Порядок збільшення розміру статутного капіталу АТ за рахунок додаткових внесків у разі закритого (приватного) розміщення акцій
3. II. Вимоги безпеки перед початком роботи
4. II. Вимоги безпеки праці перед початком роботи
5. II.ТЕОРЕТИЧНІ ПИТАННЯ КУРСОВОЇ РОБОТИ
6. III. Виконання бюджету
7. III. Вимоги безпеки під час виконання роботи
8. III. Вимоги безпеки під час виконання роботи
9. III. Вимоги безпеки під час виконання роботи
10. III. ПОРЯДОК ПРОВЕДЕННЯ РОЗРАХУНКІВ КУРСОВОЇ РОБОТИ
11. Internet. - це мережа з комутацією пакетів, і її можна порівняти з організацією роботи звичайної пошти.
12. IV Етап: Вибір стратегії керування виявленими ризиками й виділення пріоритетних напрямків роботи

Переглядів: 540