Два варіанти побудови|шикування| циклічних кодів, що розглянуті, для простоти реалізації можуть використовувати так зване матричне подання [1]. Проблема виявлення різного типу помилок за допомогою циклічного коду, як вже указувалося, зводиться до знаходження потрібного твірного полінома.

2.4 Аналіз CRC-кодів

Прикладом використання сімейства циклічних кодів є контроль помилок за допомогою циклічного надлишкового коду, тобто CRC - коду ( Cyclic redundancy check), які називають також кодом Абрамсона [1-3]. При передачі даних в пакетних режимах, ці коди використовуються для визначення цілісності блоків даних (FCS - Frame Checking Sequence). Прикладом систем з FCS є стандарти передачі даних Х.25 (HDSL), ISDN, DECT і LAN.

CRC кодами є розширення циклічних код Хеммінга. Хай р(Х) - примітивний многочлен степеня m, тоді породжуючий многочлен g(x) CRC коду, можна записати у вигляді добутку:

g(x)= (1 + Х)р(x). (2.3)

За допомогою породжуючого многочлена g(Х) може бути побудований циклічний CRC (n,k) -код з параметрами n = 2r - 1, k = 2r - r -2, що має r + 1 перевірочних символів і dmin = 4.

CRC-коди| володіють п'ятьма важливими властивостями:

Таблиця 2.3 - Породжувальні многочлени CRCкоду

1. Всі помилки кратності 3 або менше виявляються.

2. Всі помилки непарної кратності виявляються.

3. Всі пакети помилок довжини L = r + 1 або менше виявляються.

4. Частка пакетів помилок довжини L= r + 2, що не виявляються, складає 2-r .

5. Частка пакетів помилок довжини L ? r + 3, що не виявляються складає 2-(r-1).

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

Здатність контрольної суми виявляти помилки логічніше вимірювати не в кількості помилкових бітів, а у ймовірності не виявлення помилки. При використанні CRC проходить непоміченими лише поєднання помилок, що задовольняють вельми спеціальній умові, а саме такі, вектор помилок (двійкове число, одиничні біти якого відповідають помилковим бітам прийнятого блоку, а нульові - правильно прийнятим) яких ділиться на G (твірний поліном) без остачі. При випадковому розподілі помилок ймовірність цього може бути грубо оцінена як 1/G, тому збільшення розрядності контрольної суми у поєднанні з вибором простих G забезпечує досить швидкий і дешевий спосіб перевірки цілісності навіть досить довгих блоків. 32- розрядний CRC забезпечує практично повну гарантію того, що дані не були пошкоджені, а 8-розрядний - упевненість, достатню для багатьох цілей.

Обчислення значення коду CRC| виконується за допомогою ділення многочлена, що відповідає початковому (поліном-повідомлення), на фіксований многочлен (поліном-генератор). Залишо від такого ділення і є код CRC, що відповідає початковому повідомленню. Для коду CRC-16 поліном-генератор має степінь 16, а для CRC-32 - 32. Поліноми-генератори підбираються спеціальним чином і стандартизовані Міжнародним консультативним комітетом з телеграфного і телефонного зв'язку (CCITT). Для CRC-16, наприклад, стандартним є поліном-генератор x16 + x12 + x5 + 1.

Розглянемо приклад побудови коду CRC-4 для повідомлення 11010111, використовуючи поліном-генератор x4+x3+x2+1. Початковому повідомленню відповідає поліном x7+x6+x4+x2+x+1, тобто нумерація бітів тут починається справа:

Поліному x2+1 відповідають біти 0101 - це і є CRC-4 код. Існують швидкі алгоритми для розрахунку CRC-кодів, що використовують спеціальні таблиці, а не ділення многочленів із залишком

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

Коди CRC використовуються дуже широко: модемами, телекомунікаційними програмами, програмами архівації і перевірки цілісності даних і багатьма іншими програмними і апаратними компонентами обчислювальних систем.

2.5 Варіантний аналіз основної проектної задачі і технічне обґрунтування вибору оптимального алгоритму завадостійкого кодування

Всі схеми завадостійкого кодування можна розділити на дві групи: кодування з виявленням помилок і кодування з виправленням помилок (корегуючі коди).

Найпростішими серед корегуючих є коди з повторенням. Це коди з високими корегуючими характеристиками та дуже великою надлишковістю. Тут один інформаційний символ повторюється n раз (n непарне), тобто це (n,1)-коди. Основним недоліком даного коду є низька швидкість, цифрові потоки або розміри файлів зростають в три і більше разів.

Коди Хеммінга це лінійні коди з відстанню dmin=3 та коди з відстанню dmin=4. Перші, виправляють всі одиничні помилки, а другі виправляють всі одиничні помилки і виявляють подвійні.

Хоча коди Хеммінга доволі економічні коди і прості в реалізації, але їх корегуюча здатність невелика, цифрові потоки можуть зростати на 30 і більше процентів.

Корегуючу здатності кодів Хеммінга можна збільшити за рахунок каскадного включення декількох кодерів Хеммінга. Цей підхід дозволив істотно підвищити ефективність застосування кодування в порівнянні з базовими некаскадними методами. Мінімальна відстань сформованого каскадного коду буде рівна

D=d1•d2, (2.4)

де d1 і d2 - мінімальні відстані складових кодів.

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

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

Найважливішими відмінностями згортних кодів від блокових є такі [8].

1. Згортні коди дозволяють проводити кодування і декодування потоків даних безперервно в часі.

2. Згортні коди не потребують блокової синхронізації.

3. Застосування згортних кодів дозволяє досягти дуже високої надійності передачі інформації.

Оскільки передбачається кодування файлів, які можна розбити на блоки, то застосування згортних кодів недоцільно, оскільки вони призначені для кодування потоку бітів в каналах зв'язку. Ці коди також характеризуються великою надлишковістю.

Циклічні коди є різновидністю поліноміальних кодів [8]. В таких кодах вважається, що елементи a1, a2, …an-1 деякого кодового слова є коефіцієнтами полінома від x:

(2.5)

Процес кодування можна подати як результат множення полінома m(x), що являє собою інформаційну послідовність на породжувальний многочлен g(x), а декодування як результат ділення на цей поліном. При деяких значеннях n поліноміальні ходи характеризуються властивістю циклічності. Це означає, що циклічна перестановка кодового слова знову приводить до кодового слова даного коду. Хоча декодери для циклічних кодів доволі прості, однак у порівнянні з кодами Хеммінга, вони все ж складніші.

Хоча циклічні коди можуть використовуватись для кодування з виправленням помилок, але найчастіше їх використовують саме для формування контрольних сум. Циклічні надлишкові CRC (Cyclic redundancy code) коди [1-2] вже стали основою багатьох стандартів, де застосовуються контрольні суми. Контрольна сума - деяке значення, розраховане з послідовності даних шляхом застосування певного алгоритму, яке використовується для перевірки правильності передачі даних. Популярність використання контрольних сум для перевірки цілісності даних обумовлена тим, що подібна перевірка просто реалізовується і добре підходить для виявлення загальних помилок, викликаних наявністю шуму в каналах передачі даних або спробами несанкціонованої зміни даних. Слід зазначити, що застосування контрольних сум вносить мінімальну надлишковість в дані, що передаються, тому навіть у випадку повторної передачі цифрові потоки можуть бути значно меншими у порівнянні з корегуючими кодами.

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

Основні переваги і недоліки завадостійких кодів зведемо в табл. 2.4.

Таблиця 2.4 - Характеристики завадостійких кодів

Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13