CYCLIC REDUNDANCY CHECK

Controllo ciclico di ridondanza

La tecnica di rivelazione degli errori di trasmissione si  avvale di due metodi :

 1)      Ridondanza di codice (Character Mode) ottenuta aggiungendo al momento della trasmissione un bit di ridondanza alla stringa da inviare

2)      Ridondanza di blocco (Block Mode) che consiste nell’aggiunta di  n di bit di ridondanza.

Nell’ambito della  ridondanza di blocco, utilizzata prevalentemente nella trasmissione sincrona di gruppi di caratteri, particolare importanza riveste la modalità di rivelazione detta CRC (Cyclic Redundancy Check).   
Il CRC è caratterizzato dalla proprietà di aggiungere alla fine di un blocco una serie di bit in numero di 12 o 16 ( CRC-12 o CRC-16) corrispondenti ai coefficienti di un polinomio ottenuto come resto della divisione tra un polinomio prefissato (detto polinomio generatore  g ) e il blocco di caratteri da  trasmettere. Ovviamente il ricevente deve eseguire un’operazione identica, in modo tale che il confronto tra i due resti fornisca la conferma della correttezza della trasmissione. Il polinomio generatore  g, che  deve essere lo stesso per il ricevente e il trasmittente per rilevare la presenza d’eventuali errori, è standardizzato. Esistono dei polinomi standard normalmente riconosciuti: 

In seguito è  riportata una trattazione matematica del CRC.
Consideriamo una parola di n bit che vogliamo trasmettere ( bn-1,….bo). Fissiamo un polinomio generatore  g(x)  con grado g £ n-1. Alla stringa ( bn-1,….bo) cui corrisponde il Polinomio b(x), sarà aggiunto un blocco di g bits che sono i coefficienti del polinomio resto derivante dalla divisione del polinomio g(x) scelto b(x) ovvero r(x). Il primo passo consiste nell’aggiungere g bit zero in coda al blocco da trasmettere. In termini di polinomio vuol dire moltiplicare b(x) per x^g 

p(x)= x^g * b(x)  

quindi p(x) può essere scritto in funzione di g(x) dove q(x) e r(x) sono il quoziente e il resto della divisione tra p(x) e g(x).

             p(x)=q(x)*g(x)+r(x)

 La stringa che trasmetteremo è l’unione tra il blocco ( bn-1,….bo) e il blocco di g bit ( rg-1, r0). Il che equivale a sostituire in p(x) i g bit a zero introdotti all’inizio. In termini di matematica binaria corrisponde alla funzione xor quindi si trasmetterà la stringa corrispondente al polinomio: 

            m(x) = p(x)+r(x) = q(x)*g(x)+r(x) +r(x) = q(x)*g(x)

 essendo  r(x) +r(x) = 0 ovvero in aritmetica binaria la somma ( xor )di due quantità uguali è zero.
Quindi la stringa trasmessa m(x) è perfettamente divisibile per g(x). Questo significa che il ricevente, dividendo m(x) per g( x) che conosce, dovrà avere un resto nullo se non ci sono errori.
Il successo di questo tipo di codice è legato alla sua efficienza ma anche alla semplicità con cui è possibile implementarlo a livello hardware. Infatti bastano solo porte logiche EX-OR (exclusive OR) e  registri a scorrimento (shift register )   

top_page

English

CRC (Cyclic Redundancy Check) 

The error checks on telecomunication systems use two methods: 

1)      Character Mode which adds one redundancy bit to the sending data

2)     Block Mode which adds a redundancy block of n bit to the sending data

 In the Block mode, used in the syncronous trasmision, the most important method is the CRC (Cyclic Redundancy Check).
 This method is characterizated by the fact to add at the end of the sending data a n bit block where n is 12 or 16 ( CRC-12 o CRC-16) on the basis of the generator polynomial choosed. This added bits are the coefficient of the rest polynomial due to the divison of the sending data and the generator polynomial g. The recipient must to run the same algorithm to check the rigth of the data, so the polynomial g must be the same for the trasmiter and recipient. There are some standard polynomials: 

Below a matematical discussion about the CRC is made.

Consider a n bit word ( bn-1,….bo) and fix the polynomial g(x)  which have a degree g £ n-1

At the polynomial b(x), correspondent to the ( bn-1,….bo), is added a block of g bit which are the coefficients of the rest polynomial r(x) due to the divison between b(x) and  g(x).   
The first step is to add g bit zero to the end of the sending data. This is equivalent to multiplier b(x) with  x^g . We have the poynomial p(x): 

p(x)= x^g * b(x) 

so p(x) can be written as function of g(x) where q(x) and r(x) are the quozient and the rest of the division between p(x) and g(x). 

            p(x)=q(x)*g(x)+r(x); 

Then, the sending block  is the merge between ( bn-1,….bo) and a block of g bit ( rg-1, r0).  This is equivalent to substitute in p(x) the g bit with the bit of the ( rg-1, r0).Using the binary mathematic, this operation is equal to the XOR function. The data to send can be written:  

            m(x) = p(x) + r(x) = q(x)*g(x)+r(x) +r(x) = q(x)*g(x) 

being  r(x) +r(x) = 0 ( xor  property) 

m(x) is perfectly divisible for g(x). This means that the recipient, excuting the division between m(x) and g(x),  have a rest r(x)=0 if there are not error. 
The success of this technique is due to its efficiency but to the easy implemetation hardware.  
It needs XOR logic gate and shift register for hardware implementation.