Циклічні коди

До ефективних кодів, що виявляють одиночні, кратні помилки і пачки помилок, відносяться циклічні коди (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, то приклади циклічних кодівAig(Х) чиселAiу кодовій групі при цьому утворюючому поліномі можна бачити в наступній табл. 3.1.

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

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

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

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

Число	Циклічний код	Число	Циклічний код
0000000000.
.	.	.	.

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

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

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

---