Циклдық артықтық тексеру коді: Деректер өзгеруін анықтау

Кіріспе

Деректердегі өзгерістерді анықтау коды

Циклдық артық тексеру (CRC) – цифрлық желілер мен сақтау құрылғыларында цифрлық деректердің кездейсоқ өзгерістерін анықтау үшін кеңінен қолданылатын қателерді анықтау коды. Бұл жүйелерге түсетін дерек блоктарына олардың мазмұнының полиномдық бөлінісінен алынған қысқа тексеру мәні қоса тіркеледі. Деректерді қайта алу кезінде есептеу қайталанады және егер тексеру мәндері сәйкес келмесе, деректердің бұзылуын жою үшін шаралар қолданылуы мүмкін. CRC-тер қателерді түзету үшін де қолданылуы мүмкін (биттік сүзгілерге қараңыз). CRC-тер осылай аталады, өйткені тексеру (деректерді растау) мәні артықшылық болып табылады (ол ақпаратты қоспай хабарламаны ұзартады) және алгоритм циклдық кодтарға негізделген. CRC-тер екілік аппараттық құралдарда оңай жүзеге асырылатындығы, математикалық талдауға ыңғайлылығы және тарату каналдарындағы шудың салдарынан туындайтын жиі кездесетін қателерді анықтаудағы тиімділігі үшін танымал. Тексеру мәнінің ұзындығы белгілі болғандықтан, оны құратын функция кейде хэш-функция ретінде пайдаланылады.

Кіріспе

CRC циклдік қателерді түзету кодтарының теориясына негізделген. Байланыс желілерінде қателерді анықтау үшін хабарламаларды белгілі бір ұзындықтағы тексеру мәнін қосу арқылы кодтайтын жүйелі циклдік кодтарды қолдануды алғаш рет 1961 жылы У. Уэсли Петерсон ұсынды. Циклдік кодтарды іске асыру ғана емес, сонымен қатар олар жарылу қателерін анықтауға өте ыңғайлы: хабарламалардағы қателі деректер символдарының тізбектері. Бұл маңызды, себебі жарылу қателері көптеген байланыс арналарында, соның ішінде магниттік және оптикалық сақтау құрылғыларында жиі кездеседі. Әдетте, кез келген ұзындықтағы деректер блогына қолданылған n биттік CRC, n биттен ұзын емес кез келген жарылу қатесін анықтайды, ал ол анықтай алатын барлық ұзын жарылу қателерінің үлесі шамамен (1 − 2−n) құрайды. CRC кодын анықтау үшін генератор полиномы деп аталатын нәрсені анықтау қажет. Бұл полином көпмүшелік бөліністе бөлгіш болады, онда хабарлама бөлінетін сан ретінде қабылданады, ал бөліндісі ескерілмейді және қалдық нәтиже болады. Маңызды ескерту – полиномдық коэффициенттер шекті өрістің арифметикасы бойынша есептеледі, сондықтан қосу операциясы әрқашан біттер бойынша параллель түрде орындалуы мүмкін (сандар арасында ауысу болмайды). Іс жүзінде, барлық қолданылатын CRC екі элементтің шекті өрісін, GF(2) қолданады. Екі элемент әдетте 0 және 1 деп аталады, бұл компьютерлік архитектураға ыңғайлы. CRC, егер оның тексеру мәні n биттен тұрса, n биттік CRC деп аталады. Белгілі бір n үшін әр түрлі полиномдармен бірнеше CRC мүмкін. Мұндай полиномның ең жоғары дәрежесі n болады, яғни оның n + 1 мүшесі бар. Басқаша айтқанда, полиномның ұзындығы n + 1 болады; оны кодтау үшін n + 1 бит қажет. Көптеген полиномдық сипаттамалар MSB немесе LSB-ны жіберіп алады, өйткені олар әрқашан 1 болады. CRC және оған сәйкес полином әдетте CRC n XXX түрінде аталады, мысалы төмендегі кестеде көрсетілгендей. Ең қарапайым қателерді анықтау жүйесі – паритет биті, шын мәнінде 1 биттік CRC: ол генератор полиномын x + 1 (екі мүше) қолданады және CRC 1 деп аталады.

CRCs are based on the theory of cyclic error correcting codes. The use of systematic cyclic codes, which encode messages by adding a fixed length check value, for the purpose of error detection in communication networks, was first proposed by W. Wesley Peterson in 1961. Cyclic codes are not only simple to implement but have the benefit of being particularly well suited for the detection of burst errors: contiguous sequences of erroneous data symbols in messages. This is important because burst errors are common transmission errors in many communication channels, including magnetic and optical storage devices. Typically an n bit CRC applied to a data block of arbitrary length will detect any single error burst not longer than n bits, and the fraction of all longer error bursts that it will detect is approximately (1 − 2−n). Specification of a CRC code requires definition of a so called generator polynomial. This polynomial becomes the divisor in a polynomial long division, which takes the message as the dividend and in which the quotient is discarded and the remainder becomes the result. The important caveat is that the polynomial coefficients are calculated according to the arithmetic of a finite field, so the addition operation can always be performed bitwise parallel (there is no carry between digits). In practice, all commonly used CRCs employ the finite field of two elements, GF(2). The two elements are usually called 0 and 1, comfortably matching computer architecture. A CRC is called an n bit CRC when its check value is n bits long. For a given n, multiple CRCs are possible, each with a different polynomial. Such a polynomial has highest degree n, which means it has n + 1 terms. In other words, the polynomial has a length of n + 1; its encoding requires n + 1 bits. Note that most polynomial specifications either drop the MSB or LSB, since they are always 1. The CRC and associated polynomial typically have a name of the form CRC n XXX as in the table below. The simplest error detection system, the parity bit, is in fact a 1 bit CRC: it uses the generator polynomial x + 1 (two terms), and has the name CRC 1.

Қолдану

CRC-ге қолдау көрсетілген құрылғы, жіберілетін немесе сақталатын әрбір дерек блогы үшін «тексеру мәні» немесе CRC деп аталатын қысқа, белгілі бір ұзындықтағы екілік тізбекті есептейді және оны деректерге қосып, кодты сөзді құрайды. Кодты сөз алынғанда немесе оқылғанда, құрылғы өзінің тексеру мәнін дерек блогынан жаңадан есептелген мәнмен салыстырады немесе, балама ретінде, бүкіл кодты сөзді CRC арқылы өңдеп, нәтижедегі тексеру мәнін күтілетін қалдық тұрақтысымен салыстырады. Егер CRC мәндері сәйкес келмесе, блокта дерек қатесі бар екені білдіріледі. Құрылғы түзету шараларын қолдануы мүмкін, мысалы, блокты қайта оқу немесе оны қайта жіберуді сұрау. Әйтпесе, деректер қатесіз деп есептеледі (бірақ, аздаған ықтималдықпен, оларда анықталмаған қателер болуы мүмкін; мұндай жағдай қателерді тексерудің мәнінде кездеседі).

Математика

Осы бөлінуге ұқсас процестің математикалық талдауы, жақсы қателерді анықтау қасиеттерін қамтамасыз ететін бөлгішті қалай таңдауға болатынын көрсетеді. Бұл талдауда, биттік тізбектердің цифрлары белгілі бір x айнымалысы бойынша көпмүшенің коэффициенттері ретінде қарастырылады – бұл коэффициенттер GF(2) шекті өрісінің элементтері (2 модуль бойынша бүтін сандар, яғни нөл немесе бір), көбірек таныс сандардың орнына. Бинарлық көпмүшелер жиыны математикалық сақина құрайды.

Көптамаларды жобалау

Генераторлық полиномды таңдау – CRC алгоритмін іске асырудың ең маңызды бөлігі болып табылады. Полиномды қателерді анықтау мүмкіндігін барынша арттыру және соқтығысу ықтималдығын азайту үшін таңдау керек. Полиномның ең маңызды қасиеті – оның ұзындығы (полиномдағы кез келген бір мүшенің ең жоғары дәрежесі + 1), себебі ол есептелген тексеру мәнінің ұзындығына тікелей әсер етеді. Ең көп қолданылатын полином ұзындықтары: 9 бит (CRC 8), 17 бит (CRC 16), 33 бит (CRC 32) және 65 бит (CRC 64). Біз осы жағдайды жақсарта аламыз. Егер біз генераторлық полиномды қолдансақ, мұнда – примитивті полиномның дәрежесі , онда максималды жалпы блок ұзындығы болады, ал код бір, екі, үш және кез келген тақ санды қателерді анықтай алады. Максималды жалпы блок ұзындығын қажетті қателерді анықтау күшімен теңестіру үшін басқа факторлауға ие полиномды таңдауға болады. BCH кодтары – мұндай полиномдардың қуатты класы болып табылады. Олар жоғарыдағы екі мысалды қамтиды. Генераторлық полиномның қысқартылатын қасиеттеріне қарамастан, егер оның құрамында "+1" мүшесі болса, код r тізбекті біттерге шектелген қателік үлгілерін анықтай алады. Бұл үлгілер "қателік шоғырлары" деп аталады.

Ерекшеліктер

CRC-нің қателерді анықтау коды ретіндегі түсінігі, оны іске асырушы немесе стандарттау комитеті нақты жүйені жобалағанда қиындыққа ұшырайды. Міне, кейбір қиындықтар:
Кейде іске асыру, тексерілетін біт ағынына белгілі бір біт үлгісін қосымша қосады. Бұл, сағат қателері хабарламаның басына 0 биттерді енгізе алатын жағдайларда пайдалы, мұндай өзгеріс тексеру мәнін өзгерте алмайды. Көбінесе, бірақ әрқашан емес, іске асыру полиномдық бөлу жүргізілгенге дейін, біт ағынына n 0 бит (n – CRC өлшемі) қосады. Мұндай қосымша CRC есептеу мақаласында нақты көрсетілген. Бұл, бастапқы біт ағынына тексеру мәні қосылғандағы қалдық дәл нөлге тең болады, сондықтан CRC-ні тек алынған біт ағынында полиномдық бөлуді орындау және қалдықты нөлмен салыстыру арқылы тексеруге болады. Эксклюзивті немесе операциясының ассоциативтік және коммутативтік қасиеттеріне байланысты, практикалық кестелік іске асырулар тікелей нөлдерді қоспай, эквивалентті тәсілдерді қолдану арқылы нөлге тең нәтижеге қол жеткізе алады.