Формування коригувального коду Хеммінга. Звіт до лабораторної роботи з Методи та засоби тестування, відлагодження та діагностики комп’ютерних систем. Робота № 526848

Перехід до торгівельного партнера Binance

Формування коригувального коду Хеммінга

Інформація про навчальний заклад

ВУЗ:

Національний університет Львівська політехніка

Інститут:

Не вказано

Факультет:

РТ

Кафедра:

Не вказано

Інформація про роботу

Рік:

2014

Тип роботи:

Звіт до лабораторної роботи

Предмет:

Методи та засоби тестування, відлагодження та діагностики комп’ютерних систем

Завантажити

Частина тексту файла (без зображень, графіків і формул):

Міністерство освіти і науки України Національний університет „ Львівська політехніка ” Звіт до лабораторної роботи №2 з дисципліни „ Методи та засоби тестування, відлагодження та діагностики комп'ютерних систем” Тема: „Формування коригувального коду Хеммінга” Львів 2014 Мета роботи: Ознайомитися з методиками формування коду Хеммінга. Здобути практичні навички побудови кодів. Короткі теоретичні відомості На основі формування розрядів парності (чи непарності) побудовані різні методи контролю вірогідності переданої інформації, наприклад, кориту вальні коди Хеммінга, групові коригувальні коди, циклічні коди та ін. Коригувальні коди застосовують в ЕОМ для передачі інформації в просторі і часі, в оперативних запам'ятовувальних пристроях. Використання таких кодів дає змогу не тільки виявити, а й виправити помилки. Простий код Хеммінга. Велике поширення дістав простий коригувальний код Хеммінга. Цей код має мінімальну кодову відстань, рівну трьом (dmin = 3), що свідчить про його належність до кодів, які дають змогу виявляти до двох помилок і виправляти одиничні помилки. В основу побудови коду Хеммінга для інформаційних /?7-розрядних слів покладено метод формування контрольних розрядів парності. Кількість контрольних розрядів відповідає кількості контрольних груп колу Хеммінга і визначається виразом: (Л.2.1) де т кількість інформаційних розрядів слова; r — кількість контрольних розрядів слова. Кількість розрядів формованого кодового слова Хеммінга дорівнює сумі інформаційних і контрольних розрядів., тобто к = т + r. Усі розряди кодового слова нумеруються від 1 до к, починаючи з правого (молодшого) розряду. У кожну контрольну групу входять розряди кодового слова, якщо в їхніх двійкових номерах міститься «1», що вказує на належність цих розрядів до визначеної групи. Наприклад, п’ятий розряд входить у першу і другу контрольні групи, а перший, другий і четвертий розряди — тільки в одну з контрольних груп: першу, другу і третю відповідно. Розряди кодового слова, що входять тільки в одну контрольну групу (1; 2; 4; 8;...), є контрольними розрядами цих груп. Розряди, присутні у більш ніж одній контрольній групі, є інформаційними розрядами вихідного слова (3; 5; 6; 7; 9; 10; 11; 12;...). Формування кодового слова Хеммінга починається з послідовного запису (біт за бітом) вихідного інформаційного слова у відповідні розряди формованого коду (маючи визначені контрольні розряди, як показано на рис. Л.2.1). Розглянемо формування коду Хеммінга для 8-розрядного інформаційного слова. Для цього запишемо номери розрядів кодового слова Хеммінга в десятковій та двійковій системі числення (табл. Л.2.1) Контрольні розряди кожної контрольної фупи визначаються додаванням за модулем 2 інформаційних розрядів відповідної групи: Таким чином, сума за модулем 2 усіх розрядів кожної контрольної групи дорівнює нулю: Числа Е1, Е2. Е3 і Е4 утворюють позиційне двійкове коригувальне число Е4 Е3 Е2 Е1 що при формуванні коду Хеммінга дорівнює 0000. При прийнятті (чи зчитуванні) кодового слова Хеммінга коригувальне число свідчить про безпомилкову передачу чи про наявність помилки і її місце в кодовому числі. Під час прийняття кодового слова виконується повторне формування коригувального числа. Для цього знов формуються контрольні розряди а1', а2', а4', а8', ..., які зіставляються через додавання за модулем 2 з контрольними розрядами а1, а2, а4, а8,..., що були сформовані передавальним пристроєм: Після визначення контрольних сум кожної контрольної групи можна записати коригувальне число. Якщо Е4 Е3 Е2 Е1— 0 0 0 0, то це означає, що помилки в кодовому слові не виявлені (тобто помилок немає чи їхня кількість кратна трьом). У разі, якщо коригувальне число відмінне від нуля, його величина в двійковій системі числення буде дорівнювати порядковому номеру розряду кодового слова Хеммінга, в якому виявлена помилка. Це пояснюється тим, що помилка в деякому розряді кодового слова порушить парність сум у тих контрольних групах, у яких даний розряд присутній. Наприклад, п’ятий біт кодового слова належить першій і третій контрольним групам. Тому помилка в п’ятому розряді кодового слова приведе до зміни парності цих груп. У цьому випадку Е1 = 1, Е2 = 0, Е3 = 1 і Е4 = 0, тобто кориіувальне число матиме значення Е4 Е3 Е2 Е1 = 0 1 0 1. Це значення відповідає п’ятому розряду кодового слова. Корекція помилки в обчисленому розряді виконується досить просто: поточне значення «дефектного» біта перед наступною передачею інвертується через додавання за модулем 2 зі словом розузго- дження (рис. Л.2.2). У такий спосіб код Хеммінга виявляє свої коригувальні можливості в разі виникнення одиничних помилок. При виникненні двох помилок у кодовому слові коригувальне число також буде ненульовим Це буде означати, шо в кодовому слові з явилися помилки. Величина коригувального числз вказува-ткме на деякий розряд кодового слова Хеммінга. Інвертування цього розряду призведе не до корекції помилок, а до внесення ще однієї, третьої, помилки. Наявні помилки будуть замасковані, «заховані». Кодове слово з двома помилками в разі внесення третьої помилки перейде з «дефектного» стану в новий дозволений стан, однак він не буде відповідати вихідному інформаційному слову. Це пояснюється тим, що помилки в двох розрядах кодового слова компенсують одна одну. Розглянемо цю ситуацію на прикладах: Помилка в третьому і п'ятому інформаційних розрядах. Помилка в третьому розряді порушить парність у першій і другій контрольних групах, а помилка в п’ятому розряді — у першій і третій контрольних групах. Дві помилки у першій контрольній групі компенсують одна одну, і парність у цій групі не порушиться (Е1 = 0). Зберігається одночасне порушення парності в другій і третій контрольних групах (Е2 = 1 і Е3=1 ), що буде вказувати нібито на помилку в шостому розряді кодового слова. Помилки в контрольних першому і другому розрядах. Оскільки ці розряди входять тільки у свої контрольні групи, ці дві помилки спричинять порушення парності в цих групах (Е1 = І і Е2 = 1) і приведуть до рекомендації коригувати третій розряд. Помилки в контрольних четвертому й інформаційному п’ятому розрядах. Помилка п’ятого розряду порушить парність у першій і третій контрольних групах, але помилка в четвертому розряді компенсує помилку п’ятого розряду в третій групі. Порушення парності буде виявлятися тільки в першій контрольній групі (Е1 = 0), що вказуватиме на необхідність корекції першого розряду. Посилений код Хсммінга. За ненульовим коригувальним числом простого колу Хсммінга неможливо визначити причину: одинична чи подвійна помилка виникла при передачі інформації. Щоб уникнути такої невизначеності і бути впевненим, що виконується корекція одиничної помилки, а не маскування подвійної помилки, застосовують модифікаційний (посилений) код Хеммінга. Для його формування необхідно для вихідного інформаційного слова створити простий код Хеммінга. а потім додати ще один додатковий розряд —- контрольний розряд парності (чи непарності) усього кодового слова Хеммінга. Мінімальна кодова відстань при цьому збільшується до чотирьох (4п = 4), але цього недостатньо для корекції двох помилок. Можливість корекції одиничної помилки зберігається, але при виникненні двох помилок з'являється можливість однозначно констатувати цей факт і свідомо прийняти рішення про маскування цих помилок або про відмову приймати таке кодове слово. Порядок виконання роботи Вибераю відповідно до номера отриманого варіанта вихідне число в десятковій системі числення. Номер варіанту Число 11 56 Закодовую його в двійковій системі числення. 5610= 1110002 Мінімальна кількість контрольних бітів для кодування обчислюємо з нерівності m + r + 1≤2r, де m - кількість інформаційних бітів, r - контрольні біти. Відповідно, в даному випадку знадобиться 4 контрольних біта. В результаті повинні отримати кодове число довжиною 12 біт . Домовимося нумерувати біти зліва направо, починаючи з 1. Біти з номерами рівними ступенями 2 (1, 2, 4, 8 і т.д.) будуть контрольними, решта - інформаційні. Код буде виглядати наступним чином 1 1 КР4 1 0 0 КР3 0 КР2 КР1 Знаходимо контролюючі розряди КР1= 0xor 0 xor 1xor 1 xor =0 КР2=0 xor 0 xor 1 xor 1 =0 КР3=0 xor 0 xor 1= 1 КР4= 1 xor 1=0 У підсумку, отримано наступне кодове число 1101001000. Модифікований код Хемінга буде мати вигляд 01101001000 Проводимо для нашого коду помилку 01111001000. Проводимо перевірку: Визначаємо чи була ця помилка одиночною 0 xor 1xor1xor1xor1xor0xor01xor0xor0xor0=1 Отже помилка одинична. Визначимо в якому біті вона виникла: Е1= 0xor0xor0xor1xor1=0 Е2=0xor0xor0xor0xor1xor1=0 Е3=1xor0xor0xor1= 0 Е4=1xor1xor1=1 Таким чином, отримаємо Е4Е3Е2Е1=1000 і це означає, що помилка у 8 біті. Висновок Під час виконання лабораторної роботи я навчився формувати код Хеммінга, та здобув практичні навички побудови кодів.

Звіт до лабораторної роботи Методи та засоби тестування, відлагодження та діагностики комп’ютерних систем

odwtaras

21.12.2014 16:12-

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, або зареєструйтесь.

Ділись своїми роботами та отримуй миттєві бонуси!

Маєш корисні навчальні матеріали, які припадають пилом на твоєму комп'ютері? Розрахункові, лабораторні, практичні чи контрольні роботи — завантажуй їх прямо зараз і одразу отримуй бали на свій рахунок! Заархівуй всі файли в один .zip (до 100 МБ) або завантажуй кожен файл окремо. Внесок у спільноту – це легкий спосіб допомогти іншим та отримати додаткові можливості на сайті. Твої старі роботи можуть приносити тобі нові нагороди!

поділитись