Лабораторна робота вс-2

Тема: Перешкодозахисні коди. Код Хемінга.

Мета: Практично вивчити можливості коду Хеммінга.

Завдання. Створити додаток, що демонструє перетворення числа в діапазоні від 0 до 255 в код Хеммінга і дозволяє коректувати одиночну помилку.

Додаток повинен забезпечити:

• ручне введення числа в двійковій системі счислення і його контроль на відповідність діапазону;

• приведення вхідної величини до коду Хеммінга і представлення його в двійковій системі;

• ручне введення погрішності в число, представлене кодом Хеммінга в двійковій системі;

• визначення і висновок номера помилкового біта даного в коді Хеммінга.

Допуски:

• кількість кнопок 0…2;

• кількість рядків редагування 4;

• кількість написів 4…8.

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

При виконанні роботи слід витримати наступний порядок:

7. Визначити зовнішній вигляд діалогового вікна додатку і скласти ескіз;

8. Визначити типи даних для зберігання і відображення вхідних і вихідних змінних;

9. Скласти схеми алгоритмів для реалізації обчислень, згідно завданню;

10. Визначити типи даних проміжних змінних, що з'явилися при розробці схем алгоритмів;

11. Вибрати системні події, значущі для реалізовуваного додатку, по яких будуть викликані раніше складені обчислювальні алгоритми;

12. Користуючись раніше складеними ескізом, схемами алгоритмів, розподілом реакцій додатку на події, реалізувати на мові Visual C++ діалогове додатки згідно завданню.

Методичні рекомендації.

Всі коди володіють кодовою відстанню – числом позицій, в яких коди не співпадають.

Мінімальна кодова відстань d – це мінімальна відстань між двома будь-якими кодовими комбінаціями в заданому коді.

Для всіх коректуючих кодів d > 1. Для виявлення помилки кратності t потрібен, щоб

d = t + 1, (1)

а для її виправлення —

d = 2t + 1. (2)

Із збільшенням значення d росте коректуюча здатність коду, яка кількісно може бути виражена як вірогідність виявлення або виправлення помилок різних типів.

Коди, запропоновані Хеммінгом, призначені для виправлення одиночних помилок (при d = 3), або для виправлення одиночних і виявлення без виправлення подвійних помилок (d = 4).

Припустимо, що є r-значное число, що містить g інформаційних розрядів і n контрольних розрядів. Кожний з контрольних розрядів є знаком парності для певної групи інформаційних знаків слова. При декодуванні виробляється n групових перевірок на парність за допомогою операції що ВИКЛЮЧАЄ АБО. В результаті кожної перевірки у відповідний розряд регістра помилки записується 0, якщо перевірка була успішною, або 1, якщо була знайдена непарність.

Властивість кодів Хеммінга така, що контрольне число указує номер позиції, де відбулася помилка. За відсутності помилки в коді дана послідовність міститиме тільки нулі. Одержане число описує таким чином r=(g+n+1) подій. Отже, справедлива нерівність

2n ≥ (g+n+1)

(3)

Помилка можлива в одній з n позицій. Отже, число контрольних знаків, а значить, і число розрядів регістра помилок повинне задовольняти умові

n ≥ log2(r + 1)

(4)

Звідси

а ≤ r – log2(r + 1)

(5)

Особливість кодів Хеммінга у тому, що всім можливим помилкам заданої кратності ставляться у відповідність r-бітові комбінації синдромів Q. В даному випадку синдром помилки – це номер помилкового бита.

Перевірочна матриця кодів Хеммінга складається з r стовпців і n рядків, причому, стовпцями є двійкові числа синдромів, розставлені в порядку зростання (1, 2, 3, 4,…):

Перевірочна матриця задає номери біт кодової комбінації, які беруть участь в кожній з n перевірок. Як перевірочні біти вибирають такі, які входять тільки один раз в кожну перевірку, тобто такі, для яких qi містить лише один ненульовий біт, це биті, номери яких є цілим ступенем 2, тобто q1, q2, q4, q8 і т.д. При цьому всі біти кодової комбінації одержують номери, починаючи з 1, зліва направо (тоді як інформаційні біти нумеруються з 0 і справа наліво):

Розглянемо побудову перевірочної матриці, таблиці перевірок, а також самих кодів Хеммінга на прикладі передачі байтового первинного коду. Оскільки інформаційна частина містить 8 біт, згідно (4) для виправлення одноразових помилок потрібен включення в код 4-х перевірочних біт. Перевірочна матриця H(r x n) для нього матиме вигляд:

Тут номер стовпця перевірочної матриці відповідає представленню синдрому помилки в десятковій системі числення, а кожен її рядок hn визначає перелік біт кодової комбінації, що перевіряються:

Перевірочні біти	Статья II.Контрольовані біти
1	1 3 5 7 9 11 13 15 17 19 21
2	2 3 6 7 10 11 14 15 18 19 22
4	4 6 7 12 13 14 15 20 21 22
8	8 9 10 11 12 13 14 15 24 25 26
16	16 17 18 19 20 21 22 23 24 25 26
32	32 33 34 35 36 37 38 39 40 41 42

З таблиці можна видно, що для будь-якого номера перевірочного біта m, група з m біт підряд (включно) виявляються тією, що перевіряється, потім слідує група m біт, що не перевіряються, потім групи повторюються.