Мета: Практично вивчити можливості циклічних кодів.
Завдання. Створити додаток, що демонструє перетворення числа в діапазоні від 0 до 255 в код циклічний код по заданому поліному, що породжує, і дозволяюче коректувати одиночну помилку.
Додаток повинен забезпечити:
- ручне введення числа в двійковій системі счислення і його контроль на відповідність діапазону;
- приведення вхідної величини до циклічного коду і представлення його в двійковій системі;
- ручне введення погрішності в число, представлене циклічним кодом в двійковій системі;
- визначення і висновок номера помилкового біта даного в циклічному коді.
Допуски:
- кількість кнопок 0…2;
- кількість рядків редагування 4;
- кількість написів 4…8.
Порядок виконання роботи
При виконанні роботи слід витримати наступний порядок:
13. Визначити зовнішній вигляд діалогового вікна додатку і скласти ескіз;
14. Визначити типи даних для зберігання і відображення вхідних і вихідних змінних;
15. Скласти схеми алгоритмів для реалізації обчислень, згідно завданню;
16. Визначити типи даних проміжних змінних, що з'явилися при розробці схем алгоритмів;
17. Вибрати системні події, значущі для реалізовуваного додатку, по яких будуть викликані раніше складені обчислювальні алгоритми;
18. Користуючись раніше складеними ескізом, схемами алгоритмів, розподілом реакцій додатку на події, реалізувати на мові Visual C++ діалогове додатки згідно завданню.
Методичні рекомендації.
Циклічні коди — це сімейство перешкодостійких кодів, включаюче як один з різновидів коди Хеммінга, але в цілому забезпечуюче велику гнучкість з погляду можливості реалізації кодів з необхідною здатністю виявлення і виправлення помилок, що виникають при передачі кодових комбінацій по каналу зв'язку. Циклічний код відноситься до систематичних блокових (n, до) -кодам, в яких до перших розрядів є комбінацією первинного коду, а подальші (n ? до) розрядів є перевірочними.
У основі побудови циклічних кодів лежить операція розподілу передаваної кодової комбінації на не приводиться поліном ступеня r, що породжує. Залишок від розподілу використовується при формуванні перевірочних розрядів. При цьому операції розподілу передує операція множення, що здійснює зрушення вліво к-розрядній інформаційній кодовій комбінації на r розрядів.
При декодуванні прийнятої n-розрядної кодової комбінації знову виробляється розподіл на поліном, що породжує.
Синдромом помилки в цих кодах є наявність залишку від розподілу прийнятої кодової комбінації на виробляючий поліном. Якщо синдром рівний нулю, то вважається, що помилок немає. Інакше, за допомогою одержаного синдрому можна визначити номер розряду прийнятої кодової комбінації, в якому відбулася помилка, і виправити її.
Проте не виключається можливість виникнення в кодових комбінаціях багатократних помилок, що може привести до помилкових виправлень и/или не виявлення помилок при трансформації однієї дозволеної комбінації в іншу.
Опис циклічних кодів і їх побудову зручно проводити за допомогою многочленів (або поліномів). Запис комбінації у вигляді полінома знадобився для того, щоб відобразити формалізованим способом операцію циклічного зрушення початкової кодової комбінації. Так, n-елементну кодову комбінацію можна описати поліномом (n ? 1) ступеня, у вигляді:
An?1(x) = an^1 xn^1 + an^2 xn^2 + … + a1 x + a0,
де ai = {0, 1}, причому ai = 0 відповідають нульовим елементам комбінації, ai = 1 — ненульовим.
Запишемо поліноми для конкретних 4-елементних комбінацій:
1101 <=> A1(x)= x3 + x2 + 1
1010 <=> A2(x)= x3 + x
Операції складання і віднімання виконуються по модулю 2. Вони є еквівалентними і асоціативними:
G1(x)+ G2(x) => G3(x)
G1(x)? G2(x) => G3(x)
G2(x)+ G1(x) => G3(x)
Операція розподілу є звичним розподілом многочленів, тільки замість віднімання використовується складання по модулю 2:
G1(x)= x6 + x4 + x3
G2(x)= x3 + x2 + 1
Ідея побудови циклічних кодів базується на використовуванні многочленів, що не приводяться. Тим, що не приводиться називається многочлен, який не може бути представлений у вигляді твору многочленів нижчих ступенів, тобто такий многочлен ділитися тільки на самого себе або на одиницю і не ділитися ні на який інший многочлен. На такий многочлен ділитися без залишку двочлен xn + 1. Многочлени, що не приводяться, в теорії циклічних кодів виконують роль створюючих поліномів.
Повертаючись до визначення циклічного коду і враховуючи запис операцій циклічного зрушення кодових комбінацій, можна записати матрицю циклічного коду, що породжує, в наступному вигляді:
де p(x) — початкова кодова комбінація, на базі якої одержана вся решта (m ? 1) базових комбінацій, Ci = 0 або Ci = 1 (0, якщо результуючий ступінь полінома p(x)· xi не перевершує (n ? 1), 1, якщо перевершує).
Комбінація p(x) називається комбінацією, що породжує (що породжує, генераторної). Для побудови циклічного коду достатньо вірно вибрати p(x). Потім вся решта кодових комбінацій виходить такими ж, як і в груповому коді.
Поліном, що породжує, повинен задовольняти наступним вимогам:
1. p(x) повинен бути ненульовим;
2. Вага p(x) не повинна бути менше мінімальної кодової відстані: v(p(x))? dmin;
3. p(x) повинен мати максимальний ступінь до (до — число надмірних елементів в коді);
4. p(x) повинен бути дільником полінома (xn ? 1).
Виконання умови 4 призводить до того, що всі робочі кодові комбінації циклічного коду придбавають властивість подільності на p(x) без залишку. Враховуючи це, можна дати інше визначення циклічного коду. Циклічний код — код, всі робочі комбінації якого діляться на той, що породжує без залишку.
Для визначення ступеня полінома, що породжує, можна скористатися виразом:
r ^log2(n+1),
де n — розмір передаваного пакету за раз, тобто довжина циклічного коду, що будується.
Хай заданий поліном P(x)= ar^1 xr + ar^2 xr^1 + … + 1, визначаючий коректуючу здатність коду і число перевірочних розрядів r, а також початкова комбінація простого к-елементного коду у вигляді многочлена Ak^1(x).
Вимагається визначити дозволену кодову комбінацію циклічного коду (n, до).
Умножаємо многочлен початкової кодової комбінації на xr:
Ak^1(x) · xr.
Визначаємо перевірочні розряди, доповнюючі початкову інформаційну комбінацію до дозволеної, як залишок від розподілу одержаного в попередньому пункті твору на поліном, що породжує:
Ak^1(x) · xr ^ Pr(x) => R(x).
Остаточно дозволена кодова комбінація циклічного коду визначиться як
An^1(x) = Ak^1(x) · xr + R(x).
Для виявлення помилок в прийнятій кодовій комбінації достатньо поділити її на виробляючий поліном. Якщо прийнята комбінація — дозволена, то залишок від розподілу буде нульовим. Ненульовий залишок свідчить про те, що прийнята комбінація містить помилки. По вигляду залишку (синдрому) можна в деяких випадках також зробити висновок про характер помилки, її місцеположенні і виправити помилку.
Приклад. Хай вимагається закодувати комбінацію вигляду 1101, що відповідає А(х)= х3 + х2 + 1.
Визначаємо число контрольних символів r = 3. З таблиці візьмемо многочлен P(х)= х3 + х + 1, тобто 1011.
Помножимо А(х) на хr:
А(x)· xr = (x3 + x2 + 1) · x3 = x6 + x5 + x3 ? 11010000
Розділимо одержаний твір на створюючий поліном g(х):
А(x)· xr ^ P(x)= (x6 + x5 + x3) ^ (х3 + х + 1) = х3 + х2 + х + 1 + 1 ^ (х3 + х + 1) ^ 1111 + 001 ^ 1011
При розподілі необхідно враховувати, що віднімання виробляється по модулю 2. Залишок підсумовуємо з h(х)· хr. В результаті одержимо закодоване повідомлення:
F(x)= (x3 + x2 + 1) · (x3 + x + 1) = (x3 + x2 + 1) · x3 + 1 ^ 1101001
У одержаній кодовій комбінації циклічного коду інформаційні символи А(х)= 1101, а контрольні R(х)= 001. Закодоване повідомлення ділиться на створюючий поліном без залишку.
Алгоритм визначення помилки
Хай маємо n-елементні комбінації (n = до + r) тоді:
Одержуємо залишок від розподілу Е(х) відповідного помилці в старшому розряді [1000000000], на поліном Pr(x), що породжує:
E1(x)^ Pr(x)= R0(x)
Ділимо одержаний поліном Н(х) на Pr(x) і одержуємо поточний залишок R(x).
Порівнюємо R0(x) і R(x).
Якщо вони рівні, то помилка відбулася в старшому розряді.
Якщо ні, то збільшуємо ступінь прийнятого полінома на x і знову проводимо розподіли:
H(x)· x ^ Pr(x)= R(x)
Знову порівнюємо одержаний залишок з R0(x).
Якщо вони рівні, то помилки в другому розряді.
Якщо ні, то умножаємо Н(х)· х2 і повторюємо ці операції до тих пір, поки R(x) не буде рівний R0(x).
Помилка буде в розряді, відповідному числу, на яке підвищений ступінь Н(х), плюс один.
Наприклад: H(x)· x3 ^ Pr(x)= R0(x)
Звіт повинен містити
11. Номер, тему, мету, завдання лабораторної роботи.
12. Ескіз інтерфейсу розробленого додатку.
13. Зведену таблицю вхідних і вихідних змінних з описом їх призначень.
14. Схеми алгоритмів всіх доданих обробників подій, оформлених згодне вимог ЄСПД з попередньою зведеною таблицею позначень внутрішніх змінних в представлених схемах.
15. Висновки про результат виконаної роботи.