Cykliczny kod nadmiarowy, Informatyka, Technikum, SOiSK, Klasa 4


Cykliczny kod nadmiarowy

1. Dfefinicja

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

2. Obliczanie

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ład

Załóżmy n= 3.

Ustalmy (n+1)-bitowy dzielnik w postaci liczby 1011.

Weźmy 14-bitowy ciąg danych: 11010011101110.

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

dodajemy do ciągu danych 3 wyzerowane bity,

w linii poniżej wpisujemy 4-bitowy dzielnik CRC,

jeżeli mamy 0 nad najstarszą pozycją dzielnika, to przesuwamy dzielnik w prawo o jedną pozycję, aż do napotkania 1,

wykonujemy operację XOR pomiędzy bitami dzielnika i odpowiednimi bitami ciągu danych, uwzględniając dopisane 3 bity

wynik zapisujemy w nowej linii poniżej,

jeżeli liczba bitów danych jest większa lub równa 4, przechodzimy do kroku 2,

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:

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ę



Wyszukiwarka

Podobne podstrony:
Stopa błędów, Informatyka, Technikum, SOiSK, Klasa 4
Dane techniczne przewodu UTP kat 5e, Informatyka, Technikum, SOiSK, Klasa 4
DNS, Informatyka, Technikum, SOiSK, Klasa 4, strona
IP, Informatyka, Technikum, SOiSK, Klasa 4
Sieci komputerowe, Informatyka, Technikum, SOiSK, Klasa 4, strona
Frame Relay, Informatyka, Technikum, SOiSK, Klasa 4
Serwer, Informatyka, Technikum, SOiSK, Klasa 4, strona
Ramka ETERNIT, Informatyka, Technikum, SOiSK, Klasa 4
Zadanie 1, Informatyka, Technikum, SOiSK
Podpisywanie sterowników w systemie Windows, Informatyka, Technikum, UTK, klasa 3
Maska podsieci, Informatyka, Technikum, UTK, klasa 3, karta sieciowa
okna dialogowe, Informatyka, Technikum, SOiSK
Zadanie na SOiSK, Informatyka, Technikum, SOiSK
ustawienia kjarty sieciowej, Informatyka, Technikum, UTK, klasa 3, karta sieciowa
Lab 13 14 15 16 Multimedia Klasa 4 2011 2012 Lista4, Informatyka, Technikum, Grafika
informatyka(1), technik informatyk, soisk utk
Kod błędu bluescreen, Technik Informatyk - materiały, SO I SK
Korloy Frezowanie Informacje techniczne 2011
Informator techniczny Wonderware 010

więcej podobnych podstron