МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА” Кафедра САПР ЗВІТ про виконання лабораторної роботи №4 на тему: «Метод Хеммінга» з курсу: “Проблемно-орієнтовані методи та засоби інформаційних технологій” МЕТА РОБОТИ Мета роботи - вивчення методiв побудови кодiв Хемiнга та їх програмна реалiзацiя для практичного використання. КОРОТКІ ТЕОРЕТИЧНІ ВІДОМОСТІ 2.1. Завадостійке кодування. Завадостійкі коди – це один із найефективніших засобів забезпечення високої достовірності передачі інформації. Розвиток цього напрямку зумовлений використанням мікропроцесорної техніки у системах зв’язку. Завадостійке кодування базується на теоремі Шеннона для передачі дискретної інформації по каналу із завадами: “Імовірністть помилкового декодування може бути як завгодно малою при виборі відповідного способу кодування”. Теорема вказує на принципову можливість але не визначає спосіб кодування. Це обумовило інтерес до розробки завадостійких кодів. Під завадостійкими розуміють коди які дозволяють виявляти чи виявляти і виправляти помилки які виникли через вплив завад. Завадостійкість кодування забезпечується за рахунок внесення надлишковості в кодові комбінації тобто крім інформаційних є і надлишкові (додаткові) розряди. Всі завадостійкі коди поділяються на два класи:блочні та неперервні [1]. В блочних кодах кожному повідомленню (або елементу повідомлення) відповідає кодова комбінація (блок) із певної кількості сигналів. Блоки кодуються і декодуються окремо один від одного. Блочні коди можуть бути рівномірними (довжина кодових комбінацій n – постійна) або нерівномірними (n – міняється). Нерівномірні практично не використовуються через складність їх технічної реалізації. В неперервних кодах внесення надлишковості в послідовність вхідних символів здійснюється без розбивки на окремі блоки. Для неперервних кодів процеси кодування та декодування мають теж неперервний характер. Цей напрям тільки розвивається. Блочні і неперервні коди в залежності від методів внесення надлишковості поділяють на роздільні та нероздільні. В роздільних чітко визначена роль окремих символів. Одні символи є інформаційні інші є перевірочними і забезпечують виявлення і виправлення помилок. Роздільні блочні коди називають ще n k – кодами де n – довжина кодових комбінацій k – кількість інформаційних символів в комбінаціях. У нероздільних кодах немає чіткого поділу символів кодової комбінації на інформаційні та перевірочні. Таких кодів мало. Роздільні блочні коди поділяються на систематичні і несистематичні. Несистематичні будуються таким чином що перевірочні символи визначаються як сума підблоків на які поділяється блок інформаційних символів. Більшість відомих роздільних кодів є систематичними кодами. Для цих кодів перевірочні символи визначаються в результаті проведення лінійних операцій над певними інформаційними символами. Декодування зводиться до перевірки на парність певних груп символів. В результаті цих перевірок отримується інформація про наявність помилок а при потребі і про позицію помилкових символів. 2.2. Основні принципи завадостійкого кодування. Будемо розглядати блочні рівномірні двійкові завадостійкі коди. Кількість розрядів n в кодовій комбінації називається довжиною коду. Символи коду – 01. Кількість одиниць в кодовій комбінації називається її вагою w. Наприклад: 100101100 – n=9 w=4. Кодова віддаль d визначається кількістю позицій чи символів в яких кодові комбінації відрізняються одна від одної і рівна вазі суми (по модулю 2) цих кодових комбінацій 100101100 + 110110101 _________ 010011001 w=4 d=4. За рахунок впливу завад в одному чи кількох рядках кодової комбінації можуть з’являтися помилки (0 ( 1 1(0). По кількості помилкових розрядів помилки бувають одно двох і більше кратними. Експериментальні дослідження показали що помилки символів при передачі по каналу зв’язку групуються у пачки різної тривалості. Пачка – це участок послідовності символів які починаються і закінчується помилковими символами. В середині пачки можуть бути і окремі правильні символи. Для визначення місця помилкових символів у кодовій комбінації використовується вектор помилки е (n – розрядна комбінація одиниці якої вказують місце помилкових символів). Наприклад е = 01100 – третій і четвертий символи справа – помилкові. Сума по модулю 2 спотвореної кодової комбінації і вектора помилки дає правильну комбінацію. Звадостійкість кодування забезпечується надлишковістю (k<n). Тобто із загальної кількості No = 2n можливих кодових комбінацій для передачі інформації використовується тільки N = 2k комбінацій тобто множина No ділиться на дві групи N=2k – множина дозволених і (No-N)=2n-2k множина заборонених комбінацій. Якщо прийнята комбінація заборонена то це означає що сигнал створений в каналі. Якщо дозволена – то або комбінація без спотворень або був перехід з однієї дозволеної в іншу. У загальному випадку кожна із N дозволених комбінацій може перетворитись у будь-яку із No можливих тобто можливі N* No варіантів передачі з них N варіантів безпомилкові N*(N-1) - перехід із одних дозволених у інші дозволені N*(No-N) – перехіід із дозволених у заборонені. Таким чином не всі спотворення можуть бути виявлені. Частка помилкових комбінацій що можуть бути виявлені визначається як
; Для використання коду як коректуючого множина заборонених кодових комбінацій розбивається на N підмножин Mі що не перетинаються. Кожна їз цих підмножин відповідає одній із дозволених комбінацій Аі . Якщо прийнята заборонена комбінація належить підмножині Mі то вважається що передана комбінація Аі. Помилка буде виправлена лише тоді коли заборонена комбінація утворилася із Аі . Таким чином помилка виправляється в (N0-N) випадках (тільки для заборонених комбінацій). Частка виправлених помилкових комбінацій із загальної кількості виявлених помилкових рівна
; Спосіб розбиття на підмножини залежить від того які помилки повинні виправлятися даним кодом. Результат виконання програми: Текст для кодування : hello world Аналог в двійковій системі 0110100001100101011011000110110001101111001000000111011101101111011100100110110001100100 Закодований Код 1100110111000011001100100101110011001111001100110011110011001101111111010101000000000001111000111111001101111111000111101010101100110011110011001101001100 Код з помилками : 0100110111000011001100100101110011001111001100110011110011001101111111010101000000000001111000111111001101111111000111101010101100110011110011001101001100 Результат : 1100110111000011001100100101110011001111001100110011110011001101111111010101000000000001111000111111001101111111000111101010101100110011110011001101001100 (Знайдено 1 помилку) Висновок : На цій лабораторній роботі я навчився працювати з кодами Хемінга та реалізував їх програмно.