• Artykuły
  • Forum
  • Ciekawostki
  • Encyklopedia
  • Cykliczny kod nadmiarowy

    Przeczytaj także...
    Pakiet telekomunikacyjny (pot. pakiet) – sformatowana jednostka informacji przesyłana poprzez sieć wykorzystującą komutację pakietów. Sieci, które nie obsługują przesyłania pakietów, takie jak np. tradycyjne połączenia modemowe lub połączenia CSD w sieci komórkowej, transmitują dane jako strumień bitów. Łącze telekomunikacyjne — kompleks środków technicznych do przesyłania sygnałów, przeznaczony do realizacji określonej usługi telekomunikacyjnej.
    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.

    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.

    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.

    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.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.
    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:

    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:

    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.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.
    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ę
    

    Zastosowanie[ | edytuj kod]

    Metoda ta jest szeroko wykorzystywana do wykrywania błędów przypadkowych, powstających np. podczas transmisji danych cyfrowych przez łącza telekomunikacyjne. Nie nadaje się jednak do ochrony integralności danych w zastosowaniach kryptograficznych, ponieważ CRC nie chroni przed celowym sfałszowaniem, tzn. można tak zmodyfikować przesyłany ciąg bitów, aby dawał on poprawny wynik, mimo kontroli CRC. Jest to jednak algorytm wykrywania błędów lepszy od prostej sumy kontrolnej, gdzie wiele jednoczesnych błędów może nie zmienić jej wartości.

    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.Sektor – w informatyce, najmniejsza fizyczna jednostka zapisu danych na dyskach twardych, dyskietkach i innych nośnikach danych naśladujących dyski.

    W rzeczywistych realizacjach CRC, wykorzystuje się najczęściej dzielnik CRC o długości 17 lub 33 bity, co daje odpowiednio: 16-bitowy lub 32-bitowy cykliczny kod nadmiarowy. CRC jest szeroko wykorzystywany w technice komputerowej, np. dodawany jest do danych każdego sektora dysku lub pakietu telekomunikacyjnego cyfrowej sieci telekomunikacyjnej, w celu ciągłego sprawdzania integralności danych.

    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.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.

    Zobacz też[ | edytuj kod]

  • Adler-32
  • funkcja skrótu
  • Linki zewnętrzne[ | edytuj kod]

  • CRC-32 w Oprogramowaniu



  • w oparciu o Wikipedię (licencja GFDL, CC-BY-SA 3.0, autorzy, historia, edycja)

    Warto wiedzieć że... beta

    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

    Czas generowania strony: 0.023 sek.