Міністерство освіти і науки України Національний університет „ Львівська політехніка ”
Звіт до лабораторної роботи №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, то це означає, що помилки в кодовому слові не виявлені (тобто помилок немає чи їхня кількість кратна трьом). У разі, якщо коригувальне число відмінне від нуля, його величина в двійковій системі числення буде дорівнювати порядковому номеру розряду кодового слова Хеммінга, в якому виявлена помилка. Це пояснюється тим, що помилка в деякому розряді...