Циклічні коди - Кодування інформації

До ефективних кодів, що виявляють одиночні, кратні помилки і пачки помилок, відносяться циклічні коди (CRC - Cyclic Redundance Code). Вони високонадійні і можуть застосовуватися при блоковій синхронізації, при якій виділення, наприклад, біта непарності було б важко.

Один із варіантів циклічного кодування полягає у множенні вихідного коду на утворює поліном g(x), а декодування - у розподілі на g(x). Якщо залишок від розподілу не дорівнює нулю, то сталася помилка. Сигнал про помилку надходить на передавач, що викликає повторну передачу.

Поліном, що утворює, є двійкове уявлення одного з простих множників, на які розкладається число X n -1, де X n позначає одиницю в n-му розряді, n дорівнює числу розрядів кодової групи. Так, якщо n = 10 і Х = 2, то X n -1 = 1023 = 11*93, і якщо g(X)=11 або у двійковому коді 1011, то приклади циклічних кодів A i *g(Х) чисел A i в кодовій групі при цьому утворює полінома можна бачити в наступній табл. 3.1.

Основний варіант циклічного коду, широко застосовуваний на практиці, відрізняється від попереднього тим, що операція поділу на утворює поліном замінюється наступним алгоритмом: 1) до вихідного числа А справа приписується До нулів, де К - число бітів утворює поліном, зменшене на одиницю; 2) над отриманим числом А*(2 К ) виконується операція О, що відрізняється від поділу тим, що на кожному кроці операції замість віднімання виконується порозрядна операція "що виключає АБО": 3) отриманий залишок і є CRC - надлишковий К-розрядний код, який замінює в закодованому числі З приписані праворуч до нулів, тобто.

На приймальному кінці над кодом виконується операція О. Якщо залишок не дорівнює нулю, топід час передачі відбулася помилка і потрібна повторна передача коду А.

.П р і м е р. Нехай А = 1001 1101 утворює поліном 11001.

Так як К = 4, то А * (2 K) = 100111010000. Виконання операції Про розрахунок циклічного коду показано на рис. 3.2.

ЧислоЦиклічний кодЧислоЦиклічний код
00000000000.130010001111
10000001011140010011010
20000010110150010100101
30000100001160011000110
50000110111180011000110
60001000010190011010001
....

Позитивними властивостями циклічних кодів є мала ймовірність невиявлення помилки та порівняно невелика кількість надлишкових розрядів.

Мал. 3.2. Приклад отримання циклічного коду

Загальноприйняте позначення поліномів, що утворюють, дає наступний приклад:

g(X) = X 16 + X 12 + X 5 + 1,

що еквівалентно коду 10001000000100001. Цей поліном використовується в протоколі V.42 для кодування кодових груп в 240 розрядів з двома надлишковими байтами. У цьому протоколі можливий утворює поліном для чотирьох надлишкових байтів.

g(X) = X 32 + X 26 + X 23 + X 22 + X 16 + X 12 + X 11 + X 10 + X 8 + X 7 + X 5

Якщо Ви не знайшли, що шукали, то рекомендую скористатися пошуком по сайту: