Техника за откриване на грешки в цифрови данни (Cyclic Redudancy Check Codes)
CRC (Cyclic Redudancy Check Codes) са техника за откриване на грешки в цифрови данни, но без да се извършват корекции, когато са открити такива.
Те се използват предимно в предаването на данни. В CRC методът, определен брой проверяващи битове, често наричани checksum, са приложени към съобщението, което се предава. Приемникът на информацията може да определи дали проверовъчнтие битове съвпадат с информацията и дали не е възникнала грешка при предаването. Ако е възникнала грешка приемника изпраща сигнал “NEGATIVE ACKNOWLEDGEMENT” (NAK), към предавателя, като изисква съобшението да бъде предадено наново.
Тази техника понякога също се прилага и на устройства за съхранение на данни като дискове. В този случай всеки блок на дисковото устройство, ще притежава проверовъчни битове. Така дисковото устройство може автоматично да предприеме препрочитане на информацията, където е възникнала грешката или да съобщи за грешката на софтуера.
Съществуват няколко техники за генериране на проверовъчни битове, които могат да бъдат добавени към съобщение. Може би най–лесният е да се добави единичен бит, наричан „проверовъчен бит”, който прави общият брой на единичните битове в кодовият вектор (съобщение с добавен паритетен бит) четен (или нечетен). Ако един бит бъде променен при предаването, това ще промени паритетният бит от четен на нечетен (или обратното). Предавателя генерира паритетен бит като просто сумира съобщението по модул от 2. В последствие паритетният бит се допълва към съобщението. Приемникът може да провери съобщението като просто сумира всичките съобщения по модул от 2 и да провери дали сумата съвпада в паритетният бит. Еквивалентно на този начин приемникът може да сумира всичките битове (на съобщението и паритетният) и да провери дали сумата е 0.
Друга техника за пресмятането на checksum е като се формира exclusive or на всичките байтове в съобщението, или да се пресметне сумата с end-around carry на всичките байтове. В последният метод съдържанието на всяка 8 битова сума се прибавя към най – незначимият бит от тези които сумираме. Смята се, че така има по – голяма възможност да се открият грешки отколкото с exclusive or, или когато сумата на байтовете с carry е отхвърлена.
Техниката която се смята, че би била по – добра от гледна точка на откриването на грешки и по – проста за реализация е CRC.
Това е още един обичаен начин за смятане на checksum–а, обикновено с дължина 8, 16 или 32 бита, в зависимост от съобщението. Тук ще направим един кратък обзор на теорията на този метод и ще дадем някои алгоритми за пресмятане на най – често използваните 32 битови checksum-и.
За серийно побитово предаване и приемане, хардуерното генериране и проверяване на единичен паритетен бит е изключително просто. То се състои от единичен exclusive или слепен с някоя контролна грешка (неистинност). За паралелно побитово предаване на данни може да се използва exclusive or дърво .
От всички разновидности на систематичните кодове,цикличните кодове са получили най-голямо разпространение,което се обуславя от тяхните високи,големи,коригиращи способности и сравнитвлно проста реализация на кодиращите и декодиращите устройства,в които се използват те.
Приложение:
CRC код е базиран на полиноми, в частност деленето на един полином в GF(2) [Поле на Галоуа с два елемента] с друг полином. Това е все едно да вземем дадено съобщение като много дълго двоично число и да изчислим остатъка от делението на това число, със достатъчно голямо просто число като 232-5 . Полином в Поле на Галоуа е полином с една променлива Х, чиито коефициенти са 0 и 1. Събирането и изваждането стават по модул от 2.
Умножението на такива полиноми е точно определено. Умножението на един коефициент по друг трябва да е все едно прилагането на логическия оператор ‘и’, а частичното произведение е сумиране, използващо exclusive or . Умноженито не е нужно за пресмятането на CRC checksum – а.
Построяване на циклични полиноми
Построяването на всеки CRC код с n-разредни комбинации, в които r-разреда са проверовъчни, се извършва чрез един специален полином P(x), който има степен r и се нарича производящ, образуващ или генераторен полином. Производящ полимон P(x) на един цикличен код с n-разредни комбинации има следните две важни свойства:
- Полиномът P(x) дели без остатък полиномите, съответстващи на всяка от разрешените комбинации на кода;
- Биномът xn + 1, имащ степен, равна на броя на разредите в кодовите комбинации, се дели без остатък на производящ полином P(x);
Във връзка с тези две свойства е и следната дефиниция на цикличните кодове:
Циклични се наричат (n, k)-кодовете, полиномите на разрешените комбинации със степен n-1, на които се делят без остатък на един полином P(x), имащ степен n – k = r и явяващ се един от множителите на разложението на бинома xn – 1. Построяването на цикличен код при избран производящ полином P(x) може да се извърши по следните три начина:
1. Чрез поизводяща матрица G(n, k) – за нейн първи ред може да се вземе комбинацията, съответсваща на полинома xk-1. P(x).Този полином е от степен k – 1 + r = n – 1 и комбинацията му е разрешена, комбинация на цикличния код, защото се дели без остатък на производящия полином P(x). Ако се извършат след това k – 1 циклични премествания на тази комбинация, ще се получат останалите k – 1 реда на производящата матрица.
2. Ако с G(x) означим полинома от степен k – 1 съответстващ на дадена k-разредна комбинация на простия код, а с F(x) полином от степен n – 1, съответстващ на разрешената n-разредна комбинация на цикличния код, то съгласно 2-ро свойство на производящия полином кодирането може да се извърши чрез просто умножение на G(x) и P(x): F(x) = G(x). P(x);
3. Да умножим полинома на комбинацията на простия код G(x) с xr и произведението да рзделим на производящия полиним x. При делението ще се получи едно частно Q(x) и остатък R(x), ако P(x) не е множител на xr G(x). Като се има предвид, че изваждането по модул 2 е еквивалентно на сумирането xr G(x) + R(x) = Q(x) P(x).
Тъй като P(x) има степен r, частното Q(x) от делението на xr G(x) ще има същата степен както и G(x) и на него ще съответства една k-разредна комбинация. Но при простите кодове всички k-разредни комбинации са разрешени и следователно Q(x) съответства на комбинацията на простия код. Това означава, че проиведението Q(x) P(x) е разрешена комбинация на цикличния код, получена по втория от разгледаните начини:
F(x) = G(x). P(x);
Но тогава и лявата страна е също разрешена комбинация
F(x) = xr G(x) + R(x);
От тук следва и третия начин за кодиране, който се свежда до прибавяне към xr G(x) на остатъка от делението на xr G(x), на производящия полиом P(x). Този начин се реализира най-просто технически, тъй като умножението с xr е равносилно на добавяне на r нули в нисшите разреди ( изместване с r такта ), а R(x), ще има винаги степен, по-малка от r, следователно на него съответстват по-малко от r-разреди.
Методи за проверка при циклични кодове
Проверка при цикличните кодове могат да се извършат по два начина: чрез проверовъчна матрица или чрез деление на пристигналата в приемната страна комбинация на производящия полином P(x).
Проверовъчна матрица при цикличните кодове може да се построи по два начина:
1. От производяща матрица;
2. Като се използва свойството на P – 1(x)1 да дели без остатък бинома
x n + 1. За целта се изполва делението:
h (x) = x n + 1 / P – 1(x)
Полученият полином h (x) се нарича проверовъчен полином. Вторият начин за проверка се базира на свойството на цикличните кодове всяка разрешена комбинация F(x) да се дели без остатък на P(x). Ако се яви някаква грешка това е сигурна индикация за грешка. Този метод е най-често използван в реалните декодиращи устройства, тъй като се реализира изключително просто чрез един преместващ регистър с логически обратни връзки.
Цикличните кодве, които са били създадени за опростяване на схемите на кодиращите и декодиращите устройства, сега са най-масово използвани шумоустойчиви кодове. Това се дължи на по-късно установената им ефикастност по отношение на грешки с голяма кратност и най-вече на пакети от грешки. Всеки цикличен код с производящ полином от степен r открива всички пакети от грешки с определена дължина b, изпълняваща условието b<=r.
Пакет от грешки с дължина b се нарича серия от елементарни импулси, започваща и завършваща със сгрешен разред и съдържаща общо m сгрешени импулса, като между никои два сгрешени импулса няма повече от b несгрешени.
- CRC – 12 се използва за предаване на 6 битови знакови потоци, а останалите за 8 битови или 8 байтови от произволна информация.
- CRC – 16 се използа при IBM`s BISYNCH комуникационните стандарти. CRC – CCITT полинома, още познат като ITU – TSS, се използва в комуникационни протоколи като XMODEM, X.25, IBM`s SDLC, и ISO`s HDLC .
- CRC – 32 още познат като AUTODIN – II и UTI – TSS (UTI – TSS е дефиниран като 16 и 32 битов полином) се използва в PKZip, Ethernet, AAL5 (ATM Adaptation layer 5), FDDI (Fiber Distributed Data Interface), в IEEE – 802 LAN/MAN стандарта и някои DOD приложения.
Сходни статии:
- Телекомутационна техника, технологии и мрежи Технологиите са основния двигател на след индустриалното общество. Развитието на съвременното общество зависи главно от следните технологии: електронни, компютърни и телекомуникационни. През последните десетилетия сме свидетели на обединението на горните...
- Системи за откриване на атаки Откриване на атаки (intrusion detection) Процес на идентификация и реагиране на подозрителна дейност, насочена към компютърните или мрежовите ресурси. Атака – всяко несанкционирано действие, което води до реализация на заплаха...
- Разпределени бази данни. Предимства и недостатъци на работата с база данни Осигурява икономия при използването на персоналните компютри, намалява грешките от централизацията на данните и нараства отговорностите към мениджърските нужди. Данните могат да бъдат разделени на части и базирани на регионален,...
- База данни в Delphi Програмирането на бази данни е свързано с използването на някои специфични инструменти и подходи. Най-общо, базите данни представляват съвкупност от един или няколко файла, които съдържат записно-ориентирани съвкупности от данни...
- Информационни системи за управление СИСТЕМА ЗА ОБРАБОТКА НА ТРАНЗАКЦИИ Предназначение – за обработка на първични данни на изпълнителско ниво. Използват се за решаване на добре структурирани (формализирани) задачи, за които са известни изходните данни...