Лабораторна робота 3 Шифрування даних циклічним кодом

вибрати твірний поліном

визначити зв’язки на схемі кодера

визначити зв’язки на схемі декодера

розробити формули для кодера

розробити формули для декодера

закодувати вхідну послідовність

розкодувати послідовність; знайти помилку, якщо є.

4. розробити програму (FormApplication, мовою С++ або С#) для реалізації кодування та декодування слів

5. оформити звіт для захисту лабораторної роботи за зразком

• назва роботи

• мета роботи

• алгоритм розв’язку задачі

• програмний код розв’язання задачі

• "скріншоти" роботи програми кодування

• висновки

Теоретичні відомості.

Необхідність використання складних алгоритмів.

Розглянемо приклад у ситуації, коли помилка не може бути виявлена:

Нехай контрольна сума обчислюється як сума чисел у повідомленні узята по модулі 256, тоді

Ймовірність виникнення такої помилки - 1/256. Для поліпшення виявлення помилок можна перейти від 8-бітної контрольної суми до 16-бітної, тобто підсумовуючи по модулі 65536. Це, мабуть, зменшить ймовірність пропуску помилки до 1/65536. Але в даному прикладі збільшення довжини контрольної суми не дозволить відловити помилку (нам треба інший алгоритм). Це відбувається в результаті того, що у якості контрольної функції використовується операції додавання, майже кожний біт вихідного повідомлення впливає тільки на один біт контрольної суми, поза залежністю від її довжини. Тому, крім довжини контрольної суми, звертають увагу на такий фактор як хаотичність: формула повинна дозволяти будь-якому біту повідомлення змінювати будь-яку кількість біт контрольної суми.

Основна ідея CRC-алгоритмів.

В основі контрольної функції CRC-алгоритмів лежить арифметична операція - ділення. Послідовність біт вихідного повідомлення розглядається як величезне двійкове число, відбувається його цілочисельне ділення на фіксоване значення (твірний поліном), і залишок береться як контрольна сума.

Поліноміальна арифметика

Схема розподілу методів CRC трохи відрізняється від звичайної. У цьому пункті приводяться деякі ідеї, що дозволяють глибше зрозуміти сутність застосованих схем.

У зв'язку з алгоритмами CRC часто можна зустріти термін "поліноміальний". Кажуть, що даний CRC алгоритм використовує деякий поліном. Та, взагалі, кажуть, що CRC алгоритми використовують поліноміальну арифметику.

Ділене, дільник, частка і залишок розглядаються не як додатні цілі, а як поліноми з двійковими коефіцієнтами. Тобто число записується у виді двійкового рядка, біти якого служать коефіцієнтами полінома. Наприклад числу 23 (010111b) відповідає поліном:

1*x^4 + 0*x^3 + 1*x^2 + 1*x^1 + 1*x^0, чи простіше: x^4 + x^2 + x^1 + x^0

Ми можемо здійснювати арифметичні операції, розуміючи їх як операції над поліномами. Наприклад, помножимо 13 (01101b) на 11 (01011b):

(x^3 + x^2 + x^0)(x^3 + x^1 + x^0) =

(x^6 + x^4 + x^3 + x^5 + x^3 + x^2 + x^3 + x^1 + x^0) =

x^6 + x^5 + x^4 + 3*x^3 + x^2 + x^1 + x^0

Для того, щоб одержати у відповіді 143, ми повинні в якості x узяти 2 і привести коефіцієнти до двійкових, перенести 1 з 3*x^3 у старші розряди. Одержуємо:

x^7 + x^3 + x^2 + x^1 + x^0 , що відповідає 010001111b = 143

Це звичайна арифметика, просто основа системи числення тут виписана явно. Суть у тому, що якщо ми не знаємо х, то ми не можемо робити переноси. Ми не знаємо, що 3*x^3 = x^4+x^3 (якщо x=2 тоді 3*x^3=3*2^3=24; x^4+x^3=2^4+2^3=24), тому що ми не знаємо, що х = 2. У поліноміальній арифметиці відносини між коефіцієнтами не визначені, і коефіцієнти при різних ступенях цілком ізольовані.

Можна придумати різні типи поліноміальної арифметики, визначаючи правила роботи з коефіцієнтами. Для нас важлива одна зі схем - "поліноміальна арифметика по модулі 2", де всі коефіцієнти обчислюються по модулі 2, і відсутні переноси. Повертаючи до попереднього прикладу:

(x^3 + x^2 + x^0)(x^3 + x^1 + x^0) =

(x^6 + x^4 + x^3 + x^5 + x^3 + x^2 + x^3 + x^1 + x^0) =

x^6 + x^5 + x^4 + 3*x^3 + x^2 + x^1 + x^0 =

x^6 + x^5 + x^4 + x^3 + x^2 + x^1 + x^0

Двійкова арифметика без переносу

Неважко помітити зі скасуванням переносу зникають і розходження між додаванням і відніманням. Для кожної позиції є 4 варіанти:

Однак 0111010111b не можна скласти зі зсувів 011b, тому кажуть, що 0111010111b не ділиться на 011b.

Типи помилок

Передане повідомлення Т кратне дільнику. Тому, останні W біт повідомлення T це залишок від ділення повідомлення M' на поліном. Тобто Т=М'+CRC ( + означає додавання (еквівалентно операції XOR), а не додавання в кінець ), а оскільки додавання одночасне є відніманням, то воно "зменшує" M' до найближчого кратного G.

Тепер припустимо, що повідомлення прийшло з помилками. Це можна записати так T+E, де E - вектор помилки. Приймач ділить T+E на G. Оскільки T mod G = 0, то (T+E) mod G = E mod G. Тому здатність методу виокремлювати специфічні помилки буде визначатися кількістю E кратних G, оскільки такі перешкоди не можуть бути виявлені.

Перелічимо деякі типи помилок, які ми в першу чергу можемо очікувати при передачі.

• Помилка в одному біті. E = 100...000. Такі помилки можна відловити якщо в G не менш 2-х бітів встановлено в 1. Як би ми не складали зсув таких G, завжди одержимо рядок у який принаймні 2 одинички, значить E не може бути кратне G.

• Помилка в двох бітах. Треба підібрати G для який не служать кратними числа типу 011, 0101, 01001, і.т.д.

• Помилка в непарній кількості біт. Такі помилки можна відловити, узявши G, у якому кількість біт парна. Це випливає з того, що:

  • CRC-множення це просто XOR константи в акумулятор з різними зсувом.

  • XOR - порозрядная операція, що інвертує ті біти акумулятора, напроти яких у рядку, що додається, є 1.

  • Якщо зробити XOR значення з парним числом одиниць, то в акумуляторі інвертується парна кількість одиниць, у результаті чого парна кількості одиниць акумулятора збережеться.

• Помилка пакета. E = 000...000111...111000...000. Тобто помилка локалізована в безупинному пакеті усередині повідомлення. Таке E можна представити у вигляді добутку: E=(1000.....00)*(111111111), де в першій дужці Z нулів, а в другий - N одиниць. Якщо в G молодший біт - 1, то лівий множник не може бути дільником G, тоді, якщо G довше правого множника, то помилка буде виловлена.