Мета: Практично вивчити можливості коду Хеммінга.
Завдання. Створити додаток, що демонструє перетворення числа в діапазоні від 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 3 5 7 9 11 13 15 17 19 21 | |
| 2 3 6 7 10 11 14 15 18 19 22 | |
| 4 6 7 12 13 14 15 20 21 22 | |
| 8 9 10 11 12 13 14 15 24 25 26 | |
| 16 17 18 19 20 21 22 23 24 25 26 | |
| 32 33 34 35 36 37 38 39 40 41 42 |
З таблиці можна видно, що для будь-якого номера перевірочного біта m, група з m біт підряд (включно) виявляються тією, що перевіряється, потім слідує група m біт, що не перевіряються, потім групи повторюються.
Раздел 2.01 Також очевидно, що номер позиції перевірочного біта un для кодової комбінації Хеммінга U пов'язаний з номером рядка перевірочної матриці H співвідношенням:
un=2(h-1)
Розглянемо побудову коду Хеммінга для конкретного байта первинного коду; хай це буде G = {01110101}. Розміщуємо його по інформаційних осередках коду Хеммінга. На місця перевірочних біт ставимо 0. Після цього обчислюємо значення перевірочних біт відповідно до таблиці перевірок, використовуючи операцію що ВИКЛЮЧАЄ АБО: u1 = 0; u2 = 1; u4 = 0; u8 = 0, після чого заповнюємо відповідні перевірочні осередки. Одержимо комбінацію U = {010011100101}.
Хай в результаті спотворень на приймальному кінці одержана комбінацій U' = {010010100101}, тобто помилково переданий 6-й біт. Декодер здійснює перевірки згідно рядкам перевірочної матриці:
h1 = u1 || u3 || u5 || u7 || u9 || u11 = 1 || 1 = 0 Ю немає помилки
h2 = u2 || u3 || u6 || u7 || u10 || u11 = 1 Ю є помилка
h3 = u4 || u5 || u6 || u7 || u12 = 1 Ю є помилка
h4 = u8 || u9 || u10 || u11 || u12 = 0 Ю немає помилки.
Отже, синдром помилки Q = {0110}. По перевірочній матриці одержуємо, що помилка міститься в 6-у біті. Помилка локалізована і для її виправлення достатньо інвертувати значення біта.
При написанні програми слід розділити змінні введення і відображення а також змінні для зберігання інформації і обчислень:
- для введення вхідної змінної має сенс використовувати компоненту EditBox і тип CString;
- для зберігання і обробки інформації рекомендується використовувати масив типу unsigned char, який буде модифікований тільки нулями і одиницями, або внутрішню змінну типу unsigned short. Останній варіант істотно спрощує алгоритм за рахунок ускладнення рядкових операцій. Методику розрахунків і алгоритми пропонується розробити самостійно, використовуючи приведені вище відомості про код Хеммінга;
- для відображення результатів обчислень рекомендується використовувати компоненту EditBox і тип CString.
- для введення введення одноразового спотворення в код Хеммінга рекомендується значення використовувати окрему компоненту EditBox і тип CString;
- для відображення номера помилкового біта можна використовувати будь-яку цілочисельну змінну.
Звіт повинен містити
6. Номер, тему, мету, завдання лабораторної роботи.
7. Ескіз інтерфейсу розробленого додатку.
8. Зведену таблицю вхідних і вихідних змінних з описом їх призначень.
9. Схеми алгоритмів всіх доданих обробників подій, оформлених згодне вимог ЄСПД з попередньою зведеною таблицею позначень внутрішніх змінних в представлених схемах.
10. Висновки про результат виконаної роботи.
Лабораторна робота ВС-3
Тема: Перешкодозахисні коди. Циклічні коди.