- Introduzione su CRC calcoli
- Gratuito per il calcolo del CRC routine per scaricare
Introduzione su CRC calcoli
ogni volta che i dati digitali memorizzati o interfacciato, la corruzione di dati può verificarsi. Fin dall’inizio dell’informatica, le persone hanno pensato a modi per affrontare questo tipo di problema., Per i dati seriali hanno trovato la soluzione per collegare un bit di parità a ciascun byte inviato. Questo semplice meccanismo di rilevamento funziona se un numero dispari di bit in un byte cambia, ma un numero pari di falsi bit in un byte non verrà rilevato dal controllo di parità. Per superare questo problema le persone hanno cercato meccanismi sonori matematici per rilevare più falsi bit. Il calcolo CRC o il controllo di ridondanza ciclica è stato il risultato di questo. Al giorno d’oggi i calcoli CRC sono utilizzati in tutti i tipi di comunicazioni. Tutti i pacchetti inviati tramite una connessione di rete vengono controllati con un CRC., Inoltre, ogni blocco di dati sul disco rigido ha un valore CRC collegato ad esso. Mondo dei computer moderno non può fare a meno di questi calcolo CRC. Quindi vediamo perché sono così ampiamente utilizzati. La risposta è semplice, sono potenti, rilevano molti tipi di errori e sono estremamente veloci da calcolare soprattutto quando vengono utilizzati chip hardware dedicati.
Si potrebbe pensare che l’uso di un checksum possa sostituire i calcoli CRC corretti. È certamente più facile calcolare un checksum, ma i checksum non trovano tutti gli errori. Prendiamo una stringa di esempio e calcoliamo un checksum di un byte., La stringa di esempio è “Lammert” che converte i valori ASCII . Il checksum di un byte di questo array può essere calcolato aggiungendo tutti i valori, piuttosto che dividerlo per 256 e mantenendo il resto. Il checksum risultante è 210. È possibile utilizzare la calcolatrice sopra per verificare questo risultato.
In questo esempio abbiamo usato un checksum lungo un byte che ci dà 256 valori diversi. L’utilizzo di un checksum a due byte comporterà 65.536 possibili valori di checksum diversi e quando viene utilizzato un valore di quattro byte ci sono più di quattro miliardi di valori possibili., Potremmo concludere che con un checksum di quattro byte la possibilità che accidentalmente non rileviamo un errore è inferiore a 1 a 4 miliardi. Sembra piuttosto buono, ma questa è solo teoria. In pratica, i bit non cambiano in modo puramente casuale durante le comunicazioni. Spesso falliscono a raffica o a causa di picchi elettrici. Supponiamo che nel nostro array di esempio sia impostato il bit significativo più basso del carattere ‘L‘ e che il bit significativo più basso del carattere ‘a‘ venga perso durante la comunicazione. Il ricevitore vedrà l’array che rappresenta la stringa “M’mmert”., Il checksum per questa nuova stringa è ancora 210, ma il risultato è ovviamente sbagliato, solo dopo che due bit sono cambiati. Anche se avessimo usato un checksum lungo quattro byte non avremmo rilevato questo errore di trasmissione. Quindi il calcolo di un checksum può essere un metodo semplice per rilevare gli errori, ma non fornisce molta più protezione del bit di parità, indipendentemente dalla lunghezza del checksum.
L’idea alla base di un calcolo del valore di controllo è semplice. Utilizzare una funzione F (bval,cval) che immette un byte di dati e un valore di controllo e emette un valore di controllo ricalcolato., In effetti i calcoli di checksum come descritto sopra possono essere definiti in questo modo. Il nostro esempio di checksum di un byte potrebbe essere stato calcolato con la seguente funzione (in linguaggio C) che chiamiamo ripetutamente per ogni byte nella stringa di input. Il valore iniziale per cval è 0.
int F_chk_8( int bval, int cval ) { retun ( bval + cval ) % 256;}
L’idea alla base del calcolo CRC è di guardare i dati come un grande numero binario. Questo numero è diviso per un determinato valore e il resto del calcolo è chiamato CRC., Dividere nel calcolo CRC in un primo momento sembra costare un sacco di potenza di calcolo, ma può essere eseguita molto rapidamente se usiamo un metodo simile a quello imparato a scuola. Ad esempio, calcoleremo il resto per il carattere ‘ m ‘ —che è 1101101 in notazione binaria-dividendolo per 19 o 10011. Si prega di notare che 19 è un numero dispari. Ciò è necessario, come vedremo più avanti. Si prega di fare riferimento ai vostri libri di scuola come il metodo di calcolo binario qui non è molto diverso dal metodo decimale che hai imparato quando eri giovane. Potrebbe sembrare solo un po ‘ strano., Anche le notazioni differiscono tra i paesi, ma il metodo è simile.
1 0 1 = 5 -------------1 0 0 1 1 / 1 1 0 1 1 0 1 1 0 0 1 1 | | --------- | | 1 0 0 0 0 | 0 0 0 0 0 | --------- | 1 0 0 0 0 1 1 0 0 1 1 --------- 1 1 1 0 = 14 = remainder
Con i calcoli decimali è possibile verificare rapidamente che 109 diviso per 19 dia un quoziente di 5 con 14 come resto. Ma quello che vediamo anche nello schema è che ogni bit in più per controllare costa solo un confronto binario e nel 50% dei casi una sottrazione binaria., È possibile aumentare facilmente il numero di bit della stringa di dati di test—ad esempio a 56 bit se usiamo il nostro valore di esempio “Lammert” – e il risultato può essere calcolato con 56 confronti binari e una media di 28 sottrazioni binarie. Questo può essere implementato direttamente nell’hardware con solo pochissimi transistor coinvolti. Anche gli algoritmi software possono essere molto efficienti.
Per i calcoli CRC, non viene utilizzata alcuna sottrazione normale, ma tutti i calcoli vengono eseguiti modulo 2. In questa situazione si ignorano i bit di trasporto e in effetti la sottrazione sarà uguale a un’operazione or esclusiva., Questo sembra strano, il resto risultante ha un valore diverso, ma da un punto di vista algebrico la funzionalità è uguale. Una discussione su questo avrebbe bisogno di conoscenza a livello universitario della teoria algebrica dei campi e immagino che la maggior parte dei lettori non sia interessata a questo. Si prega di guardare alla fine di questo documento per i libri che discutono questo in dettaglio.
Ora abbiamo un metodo di calcolo CRC che è implementabile sia nell’hardware che nel software e ha anche una sensazione più casuale rispetto al calcolo di un checksum ordinario. Ma come si esibirà in pratica quando uno o più bit sono sbagliati?, Se scegliamo il divisore-19 nel nostro esempio – per essere un numero dispari, non è necessaria la matematica di alto livello per vedere che verrà rilevato ogni singolo errore di bit. Questo perché ogni singolo errore di bit lascerà cambiare il dividendo con una potenza di 2. Se, per esempio, il bit n cambia da 0 a 1, il valore del dividendo aumenterà con 2n. Se, invece, il bit n cambia da 1 a 0, il valore del dividendo diminuisce con 2n. Perché non è possibile dividere una qualsiasi potenza di due da un numero dispari, il resto del calcolo del CRC cambierà e l’errore non passerà inosservato.,
La seconda situazione che vogliamo rilevare è quando due singoli bit cambiano nei dati. Ciò richiede alcune matematiche che possono essere lette nel libro di Tanenbaum menzionato di seguito. È necessario selezionare il divisore con molta attenzione per essere sicuri che indipendentemente dalla distanza tra i due bit errati li rileverai sempre. È noto che i valori comunemente usati 0x8005 e 0x1021 dei calcoli CRC16 e CRC-CCITT funzionano molto bene a questo problema., Si noti che altri valori potrebbero o meno, e non è possibile calcolare facilmente quale valore divisore è appropriato per rilevare due errori di bit e quale no. Fare affidamento su un’ampia ricerca matematica su questo problema fatta alcuni decenni fa da matematici altamente qualificati e utilizzare i valori ottenuti da queste persone.
Inoltre, con il nostro calcolo CRC vogliamo rilevare tutti gli errori in cui cambia un numero dispari di bit. Questo può essere ottenuto utilizzando un divisore con un numero pari di bit impostati. Usando la matematica modulo 2 puoi mostrare che vengono rilevati tutti gli errori con un numero dispari di bit., Come ho detto prima, nella matematica del modulo 2 la funzione di sottrazione è sostituita dall’or esclusivo. Ci sono quattro possibili operazioni XOR.
0 XOR 0 => 0 even => even0 XOR 1 => 1 odd => odd1 XOR 0 => 1 odd => odd1 XOR 1 => 0 even => even
Vediamo che per tutte le combinazioni di valori di bit, la stranezza dell’espressione rimane la stessa. Quando si sceglie un divisore con un numero pari di bit impostati, la stranezza del resto è uguale alla stranezza del dividendo. Pertanto, se la stranezza del dividendo cambia perché cambia un numero dispari di bit, cambierà anche il resto., Quindi tutti gli errori che cambiano un numero dispari di bit saranno rilevati da un calcolo CRC che viene eseguito con un tale divisore. Potresti aver visto che i valori di divisore comunemente usati 0x8005 e 0x1021 hanno effettivamente un numero dispari di bit, e nemmeno come indicato qui. Questo perché all’interno dell’algoritmo c’è un bit extra “nascosto” 216 che rende il valore effettivo del divisore utilizzato 0x18005 e 0x11021 all’interno dell’algoritmo.,
Ultimo ma non meno importante vogliamo rilevare tutti gli errori di burst con il nostro calcolo CRC con una lunghezza massima da rilevare e tutti gli errori di burst più lunghi da rilevare con un’alta probabilità. Un errore di burst è abbastanza comune nelle comunicazioni. È il tipo di errore che si verifica a causa di fulmini, commutazione del relè, ecc. dove durante un piccolo periodo tutti i bit sono impostati su uno., Per capire veramente questo devi anche avere una certa conoscenza dell’algebra modulo 2, quindi ti preghiamo di accettare che con un divisore a 16 bit sarai in grado di rilevare tutti i burst con una lunghezza massima di 16 bit e tutti i burst più lunghi con almeno il 99,997% di certezza.
In un approccio matematico puro, il calcolo CRC viene annotato come calcoli polinomiali. Il valore del divisore non è spesso descritto come un numero binario, ma un polinomio di un certo ordine. Nella vita normale alcuni polinomi sono usati più spesso di altri., I tre utilizzati nel calcolo CRC on-line in questa pagina sono CRC16 a 16 bit e CRC-CCITT e CRC32 a 32 bit. Quest’ultimo è probabilmente più utilizzato ora, perché tra gli altri è il generatore CRC per tutta la verifica e la convalida del traffico di rete.
Per tutti e tre i tipi di calcoli CRC ho una libreria di software libero disponibile. Il programma di test può essere utilizzato direttamente per testare file o stringhe. Puoi anche guardare i codici sorgente e integrare queste routine CRC nel tuo programma., Si prega di essere consapevoli dei valori di inizializzazione del calcolo CRC e possibile post-elaborazione necessaria come flipping bit. Se non lo fai, potresti ottenere risultati diversi rispetto ad altre implementazioni CRC. Tutto questo pre e post-elaborazione viene eseguito nel programma di esempio, quindi non dovrebbe essere difficile far funzionare la propria implementazione. Un test comune è quello di calcolare il valore CRC per la stringa ASCII “123456789”., Se il risultato della routine corrisponde al risultato del programma di test o al risultato su questo sito Web, l’implementazione funziona e è compatibile con la maggior parte delle altre implementazioni.
Proprio come riferimento le funzioni polinomiali per i calcoli CRC più comuni. Ricorda che il termine di ordine più alto del polinomio (x16 o x32) non è presente nella rappresentazione dei numeri binari, ma implicito dall’algoritmo stesso.,
| Letteratura | ||
| 2002 | Reti di computer, descrivendo i sistemi di rete comuni e la teoria e gli algoritmi alla base della loro implementazione. | Andrew S. Tanenbaum |
| vari | L’arte della programmazione informatica è il principale riferimento per gli algoritmi semi-numerici. I calcoli polinomiali sono descritti in profondità. Un certo livello di matematica è necessario per comprenderlo appieno. | Donald E. Knuth |
| – | DNP 3.,0, o distributed Network protocol è un protocollo di comunicazione progettato per l’uso tra computer sottostazione, unità terminali remoti RTU, dispositivi elettronici intelligenti IEDs e stazioni master per l’industria utility elettrica. Ora è utilizzato anche in industrie familiari come il trattamento delle acque reflue, il trasporto e l’industria petrolifera e del gas. | Gruppo di utenti DNP |
Lascia un commento