Cyclic Redundancy Check

Cyclic Redundancy Check (CRC, орчуулбал Илүүдлийг циклээр шалгах), ихэвчлэн тоон холбооны сүлжээнүүдийн болон санах ойн төхөөрөмжүүдийн боловсруулалт хийгдээгүй өгөгдлүүдэд гардаг санамсаргүй өөрчлөлтүүдийг олоход ашиглагддаг, хэрэглэхэд хялбар, найдвартай, алдаа олдог алгоритм юм. Энэхүү системд нэвтэрч буй блок өгөгдлүүд хавсаргагдсан богино шалгалтын утга авдаг ба эдгээрийн агууламжийн олон гишүүнт хуваарьлалтын үлдэгдэл дээрээс суурилсан болно. Сэргээхэд тооцоолол ахин давтагддаг бөгөөд хэрэв шалгагдсан утга таарахгүй тохиолдолд тааварлагдсан өгөгдөл дээр засварлах аргууд ашиглаж болно.

CRC гэж нэрлэгдэж буй учир нь шалгалт (өгөгдөлийн баталгаажуулалт) утга нь өөрөө илүүдэл юм (мэссэжийг нэмэлт мэдээлэл нэмэхгүйгээр дэлгэрүүлдэг) мөн алгоритм нь цикл код юм. Binary техник хангамжинд хэрэгжүүлхэд хялбар учир CRC их алдартай бөгөөд математикийн аргаар анализ хийхэд хялбар, мөн түүнчлэн дамжуулагч сувгуудад байдаг чимээнээс үүдсэн хэвшимэл алдаануудыг илрүүлхэд сайн байдаг. Учир нь шалгалтын утга нь тогтмол урттай байдаг ба функц нь ХАШ ФУНКЦ шиг санамсаргүйгээр боловсруулалт хийдэг.

CRC-ийг В.Вэслэй Пэтэрсон анх 1961 онд санаачилжээ. Ethernet-ийн 32 битийн CRC функц болон бусад стандартууд нь олон судлаачдын ажил бөгөөд анх 1975 онд хэвлэгдсэн юм.

Тооцоолол

Өгөгдлийн CRC кодийг олохдоо: Өгөгдөл: 11001
CRC: Энэ жишээн дээр 3 битийн урттай 101 - г авч үзье. (x^2 + 1) 11001 гэсэн өгөгдөл байхад үүсгэгдсэн код буюу 101 - т хувааж гарна.

         11
101 | 11001 (Өгөгдлийн битүүд)
      101
       110
       101
        111
        101
      -------
         10 (CRC)

Харин хүлээж авагч талд шалгахдаа:

          111
101 | 1100110 (Өгөгдлийн битүүд + CRC)
      101
       110
       101
        111
        101
         101
         101
      ------- 
          000 (Алдаа байхгүй)

Үлдэгдэл нь 0 гарснаар алдаа байхгүйг илтгэх бөгөөд CRC нь алдаа засах биш зөвхөн илрүүлэх код юм.

Өгөгдлийн олон гишүүнт үүсгэх

Тухайн өгөгдлийн CRC нь өгөгдлийн олон гишүүнтийг үүсгэгдсэн олон гишүүнтэд хуваагдсан үлдэгдэл юм. Дээрх жишээн дээрх 11001 нь олон гишүүнт болохдоо $x^{4}+x^{3}+1$ болно. Үүнийг $x^{2}+1$ - т хувааж үлдэгдэл нь уг өгөгдлийн CRC код болох юм.

                      $x^{2}+x+1$

$x^{2}+1$ | $x^{4}+x^{3}+1$

      $x^{4}+x^{2}$
        $x^{3}+x^{2}$
        $x^{3}+x$
           $x^{2}+x$
           $x^{2}+1$
       ------------------------
               $x+1$ 

$x+1$ энэ нь өгөгдлийн CRC код болох юм.