Cykliczny kod nadmiarowy

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do wyszukiwania

Cykliczny kod nadmiarowy, cykliczna kontrola nadmiarowa (ang. Cyclic Redundancy Code, Cyclic Redundancy Check, CRC) – system sum kontrolnych wykorzystywany do wykrywania przypadkowych błędów pojawiających się podczas przesyłania i magazynowania danych binarnych.

Wielomian – wyrażenie algebraiczne złożone ze zmiennych i stałych połączonych działaniami dodawania, odejmowania, mnożenia i podnoszenia do potęgi o stałym wykładniku naturalnym.Integralność danych, także spójność (ang. data integrity) – funkcja bezpieczeństwa polegająca na tym, że dane nie zostały zmienione, dodane lub usunięte w nieautoryzowany sposób.

Obliczanie[ | edytuj kod]

n-bitowy cykliczny kod nadmiarowy (n-bitowy CRC) definiuje się jako resztę z dzielenia ciągu danych przez (n+1)-bitowy dzielnik CRC, zwany również wielomianem CRC. Przykładowe założenia n = 3. (n+1)-bitowy dzielnik w postaci liczby 1011. 14-bitowy ciąg danych: 11010011101110.

Algorytm postępowania w celu obliczenia 3-bitowego CRC jest następujący:

Kryptologia (z gr. κρυπτός – kryptos – "ukryty" i λόγος – logos – "słowo") – dziedzina wiedzy o przekazywaniu informacji w sposób zabezpieczony przed niepowołanym dostępem. Współcześnie kryptologia jest uznawana za gałąź zarówno matematyki, jak i informatyki; ponadto jest blisko związana z teorią informacji, inżynierią oraz bezpieczeństwem komputerowym.Funkcja skrótu, inaczej: funkcja mieszająca lub funkcja haszująca – jest to funkcja, która przyporządkowuje dowolnie dużej liczbie krótką, zwykle posiadającą stały rozmiar, nie specyficzną, quasi-losową wartość, tzw. skrót nieodwracalny.
  1. do ciągu danych dodaje się 3 wyzerowane bity,
  2. w linii poniżej wpisuje się 4-bitowy dzielnik CRC,
  3. jeżeli nad najstarszą pozycją dzielnika jest wartość 0, to przesuwa się dzielnik w prawo o jedną pozycję, aż do napotkania 1,
  4. wykonuje się operację XOR pomiędzy bitami dzielnika i odpowiednimi bitami ciągu danych, uwzględniając dopisane 3 bity
  5. wynik zapisuje się w nowej linii – poniżej,
  6. jeżeli liczba bitów danych jest większa lub równa 4, przechodzi się do kroku 2,
  7. 3 najmłodsze bity stanowią szukane CRC, czyli cykliczny kod nadmiarowy:
11010011101110 000 <--- 14 bitów danych + 3 wyzerowane bity
1011               <--- 4-bitowy dzielnik CRC
01100011101110 000 <--- wynik operacji XOR
 1011
00111011101110 000
  1011
00010111101110 000
   1011
00000001101110 000
       1011
00000000110110 000
        1011
00000000011010 000
         1011
00000000001100 000
          1011
00000000000111 000 
           101 1
00000000000010 100
            10 11 
------------------
00000000000000 010 <--- CRC

Po stronie odbiorczej wykonywane jest sprawdzenie poprawności otrzymanych danych, przy wykorzystaniu, utworzonego po stronie nadawczej, kodu nadmiarowego CRC. Jeżeli w przesłanych danych nie ma przekłamań, to po wykonaniu powyższej procedury reszta z dzielenia przez dany dzielnik CRC wynosi 0:

Suma kontrolna (ang. checksum) – liczba uzyskana w wyniku sumowania lub wykonania innych operacji matematycznych na przesyłanych danych, przesłana razem z danymi i służąca do sprawdzania poprawności przetwarzanych danych.Dane binarne (ang.) binary data – dane zapisane lub przesyłane w postaci takiej jak są reprezentowane w systemie komputerowym, w przeciwieństwie do danych przesyłanych z użyciem systemów kodowania znaków np. alfanumerycznie. Dane binarne zazwyczaj zajmują mniej miejsca niż dane zapisane alfanumerycznie.
11010011101110 010 <--- przesłany bez przekłamań ciąg 14 bitów danych + CRC
1011               <--- ustalony uprzednio, 4-bitowy dzielnik
01100011101110 010 <--- wynik operacji XOR
 1011
00111011101110 010
  1011
00010111101110 010
   1011
00000001101110 010
       1011
00000000110110 010
        1011
00000000011010 010
         1011
00000000001100 010
          1011
00000000000111 010 
           101 1
00000000000010 110
            10 11 
------------------
00000000000000 000 <--- wynik operacji równy 0 oznacza poprawną transmisję
Sektor – w informatyce, najmniejsza fizyczna jednostka zapisu danych na dyskach twardych, dyskietkach i innych nośnikach danych naśladujących dyski.Sieć telekomunikacyjna – obiekt techniczny będący zbiorem łączy telekomunikacyjnych i innych urządzeń wymaganych do przysyłania informacji pomiędzy dwoma lub więcej węzłami sieci.


Podstrony: 1 [2] [3]




Warto wiedzieć że... beta

Algorytm – w matematyce skończony ciąg jasno zdefiniowanych czynności, koniecznych do wykonania pewnego rodzaju zadań. Słowo "algorytm" pochodzi od starego angielskiego słowa algorism, oznaczającego wykonywanie działań przy pomocy liczb arabskich (w odróżnieniu od abacism – przy pomocy abakusa), które z kolei wzięło się od nazwiska, które nosił Muhammad ibn Musa al-Chuwarizmi (أبو عبد الله محمد بن موسى الخوارزمي), matematyk perski z IX wieku.
Adler-32 - suma kontrolna opracowana przez Marka Adlera w oparciu o sumę kontrolną Fletchera. Jest trochę mniej efektywna przy wykrywaniu przypadkowych przekłamań danych w porównaniu do CRC-32, ale za to znacznie szybciej obliczana przez oprogramowanie.

Reklama