Source: http://infocom.uniroma1.it/alef/libro/html/libro/libro-8.4.html
Timestamp: 2017-10-17 18:41:30+00:00

Document:
Gestione degli errori di trasmissione
Prec Sezione 8.3: Errori nelle trasmissioni numeriche di banda base Su Capitolo 8: Trasmissione dati in banda base Sezione 8.5: Protocolli ARQ Segue
8.4 Gestione degli errori di trasmissione
La figura a lato, già proposta a pag. 1↑, ricorda ancora una volta come le conseguenze prodotte dagli errori del decisore, siano alcuni bit diversi da quelli trasmessi. Al § 8.3↑ abbiamo svolto il calcolo della probabilità di errore Pe dovuta a rumore additivo, mentre al § 8.2.2.3↑ è stato illustrato come anche una non perfetta temporizzazione, od una alterazione dell’impulso g(t), possano causare errori di decisione dovuti all’isi. Sempre al primo capitolo è proposta anche la figura replicata appresso, che illustra come la Pe possa essere ridotta adottando tecniche di codifica di canale e controllo di errore, che sono discusse di seguito.
8.4.1 Controllo di errore↓
Con questo termine si individuano le strategie atte a proteggere le informazioni da trasmettere, aumentando il numero effettivo dei bit inviati (che passano da fb a f’b > fb bit/secondo, vedi figura), in modo che i bit aggiunti siano dipendenti dagli altri, permettendo la gestione degli eventuali errori di trasmissione. Vedremo che la quantità di bit aggiunti, indicata anche come ridondanza (§ 149↓), può essere appena sufficiente ad accorgersi della presenza di errori di trasmissione, o (se più elevata), a correggere fino ad una certa percentuale dei bit errati. Sussistono dunque due diverse modalità di gestione degli errori:
Forward error correction o FEC ↓
Se la quantità di bit aggiunti permette di correggere direttamente gli errori, ciò può essere utilmente sfruttato nei casi in cui il sistema di trasmissione possa essere considerato unidirezionale, o perché lo è effettivamente, oppure perchè la trasmissione coinvolge informazioni generate in tempo reale, non memorizzate in trasmissione, e consumate immediatamente in ricezione [309] [309] Come nel caso di un segnale multimediale ottenuto mediante tecniche di codifica numerica (cap. 12↓), oppure ancora nel caso di informazioni memorizzate in forma numerica su data storage [310] [310] Come as esempio per cd/dvd, chip di memoria, hard disk.... In questi casi non è possibile chiedere la ritrasmissione (o ri-lettura) dei dati errati, oppure questa introdurrebbe un ritardo tale da compromettere l’efficacia della trasmissione. La correzione di errore in avanti o fec si è sviluppata nel contesto storico della codifica di canale (vedi § 8.4.2↓), appannaggio del mondo delle telecomunicazioni.
Automatic repeat request o ARQ↓
Se al contrario è presente un canale di comunicazione a ritroso, e non sussistono rigidi vincoli temporali sul massimo ritardo tra trasmissione e ricezione corretta, allora ci si può accontentare di minore livello ridondanza, sufficiente ad accorgersi, o rivelare, gli errori, ma non a correggerli. Infatti, ora è possibile invocare la ritrasmissione del dato errato, dando luogo alle strategie di richiesta di ripetizione [311] [311] L’aggettivo automatic si riferisce al fatto che spesso la gestione della ritrasmissione avviene a carico di uno strato protocollare di livello inferiore a quello che effettivamente consuma il messaggio, che in definitiva neanche si avvede della presenza del meccanismo di ritrasmissione. o arq (vedi § 8.5↓), sviluppatesi nel contesto storico della scienza dei computer e della trasmissione dati, e che hanno dato origine ai protocolli a finestra.
8.4.1.1 Errori su parole↓
I metodi di controllo di errore operano tipicamente su gruppi di n bit denominati anche parole o word [312] [312] Il raggruppamento può derivare da una suddivisione dell’asse dei tempi in trame (§ 19.3.1↓), oppure a seguito della modalità di trasmissione a pacchetto, vedi § 17.5.1↓. in cui ogni bit può rivelarsi sbagliato con probabilità Pbite = p, e sussite la necessità di ricevere intere parole prive di errore. Se gli eventi di errore sono statisticamente indipendenti (§ 5.1.5↑) e sotto opportune ipotesi [313] [313] La probabilità che solo il primo bit su n sia sbagliato è pari a p1 = p⋅(1 − p)n − 1≃p, in cui l’approssimazione è valida se p≪1 ed n non è troppo grande; lo stesso risultato si ottiene anche per gli altri n − 1 casi possibili di un bit sbagliato e gli altri corretti, cosicché la probabilità di un solo generico bit sbagliato su n assomma quelle di tutti i casi possibili. relative a p ed n, la probabilità di un solo bit errato su n è praticamente pari a np, cioè n volte la probabilità di errore sul bit nel flusso di partenza..
D’altro canto, la probabilità di i bit errati su n è fornita dalla distribuzione binomiale (vedi § 17.1↓) P(i, n) = (ni)pi(1 − p)n − i che, se p≪1 ed n non è troppo grande, può essere approssimata come
(10.76) P(i, n) ≈ (n(n − 1)⋯(n − i + 1))/(i!)pi
e risulta molto inferiore [314] [314] Ad esempio, la probabilità di due bit errati può essere approssimata come (1)/(2)n(n − 1)p2. Infatti, la distribuzione binomiale fornisce P(2, n) = ⎛⎜⎝n 2⎞⎟⎠p2(1 − p)n − 2, in cui ⎛⎜⎝n 2⎞⎟⎠ = (n!)/(2!(n − 2)!) = (n(n − 1))/(2) e, se p≪1 ed n non è troppo elevato, (1 − p)n − 2≃1. All’aumentare di p e di n, l’approssimazione non è più valida, e la probabilità di più di un bit errato può risultare maggiore di quella di un solo bit errato. alla probabilità np di un singolo errore su n. Sotto le medesime ipotesi possiamo inoltre scrivere che P(i + 1, n)≪P(i, n), e quindi si può considerare la probabilità di ricevere i o più bit errati su n, praticamente uguale a quella di osservare solo i errori.
All’aumentare di p e di n, questi risultati perdono di validità, ma in tal caso il sistema di trasmissione è praticamente inusabile, e dunque in pratica ci si trova sempre [315] [315] Ciò non toglie che in sede di progetto sia necessario verificare la validità della (10.76↑). nelle condizioni di p ed n sufficientemente piccoli da permettere le approssimazioni.
L’esposizione prosegue formalizzando il problema della codifica di canale e descrivendo alcune soluzioni che realizzano in tal modo la correzione degli errori, rimandandone l’approfondimento al § 11.2↓. Al § 8.4.3↓ sono quindi illustrate tre tecniche utilizzate comunemente per la detezione di errore, ed infine al § 8.5↓ sono descritti i protocolli arq adottati nel contesto della trasmissione dati.
8.4.2 Correzione di errore↓ e codifica di canale↓
Approfondiamo ora su quali basi scegliere i bit di ridondanza, allo scopo di realizzare un sistema di tipo fec basato sulle tecniche di codifica di canale, anche se nessuno impedisce una loro applicazione anche al caso della dei sistemi arq. Quindi, descriviamo due semplici metodi di correzione di errore, ossia il codice a ripetizione e l’interleaving. L’argomento viene ripreso al § 11.3↓, dove sono illustrate soluzioni abbastanza più articolate.
8.4.2.1 Codice a blocchi↓
La codifica a blocchi opera su gruppi di bit indipendenti, corrispondenti ognuno a k bit consecutivi del messaggio originale, distinti dai precedenti e successivi gruppi di k. Per ogni k bit da trasmettere, il codificatore produce n = k + q bit in uscita,
dipendenti ovviamente dai k di ingresso, e che sono dunque trasmessi al loro posto.
L’operazione compiuta dal codificatore può essere pensata o realizzata come l’accesso ad una tabella (o memoria) denominata codebook↓ (o cifrario), dove i k bit da codificare rappresentano un indice che individua 2k differenti righe, in cui si trovano le parole di codice (codeword↓), costituite ognuna da n = k + q bit. Un codice siffatto è detto codice (n, k).
Ridondanza↓
Come anticipato, la misura del grado di protezione offerto dal codificatore di canale è rappresentata dalla ridondanza ρ, definita come il rapporto tra il numero di bit di protezione e quelli di informazione, e che è espressa in termini percentuali come
ρ = (q)/(k)⋅100 %
Ad esempio, in una trasmissione con ridondanza del 50%, per ogni coppia di bit di informazione ne viene inserito uno di protezione.
Distanza di Hamming↓↓
L’entità della ridondanza introdotta migliora la capacità del codice di correggere uno o più errori, in quanto non tutte le 2n possibili codeword (di n bit) sono utilizzate, ma solamente 2k tra esse: le configurazioni assenti dal codebook possono comunque presentarsi in ricezione, a causa di errori di trasmissione, ma non essendo previste dal codebook, è possibile rilevare l’errore ed eventualmente correggerlo. La dissimilarità tra due qualsiasi codeword ci, cj viene misurata in base alla valutazione della distanza di Hamming dH(ci, cj) che le separa, definita come il numero di bit in cui differiscono [316] [316] Valutabile eseguendo l’or esclusivo delle rispettive rappresentazioni binarie, ovvero ci⊕cj, e contando il numero di uni del risultato. Ad esempio, 011010⊕010110 = 001100, corrispondente a dH = 2., e la capacità di rivelazione e correzione di una particolare scelta del codebook è quantificata dalla minima dH tra tutte le possibile coppie di codeword dm = mini ≠ j dH(ci, cj), indicata come distanza del codice↓. Si dimostra infatti che un codice di canale è in grado di correggere (dm − 1)/(2) errori per parola, e di rivelare dm − 1 errori per parola [317] [317] Ad esempio, se d = 3, la presenza di un solo bit errato fa sì che la sequenza ricevuta abbia un solo bit di differenza rispetto alla codeword trasmessa, ed al minimo due bit di differenza rispetto a tutte le altre codeword, permettendo al ricevitore di correggere l’errore. Se invece sono presenti due errori, la procedura di correzione porterebbe a scegliere una codeword errata. Occorre quindi decidere a priori se utilizzare il codice a fini di correzione oppure di detezione, e nel secondo caso, lo stesso codice con d = 3 può rivelare fino a due errori per parola.. Ad un codice a blocchi (n, k) corrisponde una distanza dm ≤ n − k + 1.
Efficienza↓
L’efficienza del codice è misurata dal tasso di codifica↓ (code rate)
che rappresenta la frazione di bit informativi sul totale di quelli trasmessi, e che consente di scrivere la velocità di uscita dal codificatore come
f’b = (fb)/(Rc) > fb
Ad esempio, in una trasmissione con un tasso di codifica pari a 0.5, il numero di bit uscenti (per unità di tempo) dal codificatore di canale è il doppio del numero dei bit entranti.
L’argomento dei codici a blocchi è molto vasto [318] [318] Senza pretesa di esaustività, possiamo annoverare l’esistenza dei codici di Hamming, di Hadamard, BCH, Reed-Solomon, Reed-Muller, di Golay, di Gallager, turbo, a cancellazione, a fontana, punturati..., e fornisce molteplici soluzioni, la cui trattazione esauriente eccede il livello di approfondimento del presente capitolo (vedi però il § 11.3.1↓); gli stessi tre casi di controllo di errore trattati al § 8.4.3↓ (parità, somma di controllo e crc) possono essere inquadrati nel contesto dei codici a blocchi. Qui ci limitiamo ad un esempio di codice a correzione molto elementare, il codice a ripetizione, mentre al § 11.3.1.1↓ è illustrata una tecnica nota come codice di Hamming, in grado di conseguire una efficienza ben più elevata.
8.4.2.2 Codice a ripetizione↓
Un esempio di codice a blocchi molto semplice e con proprietà correttive è il codice a ripetizione n:1, che per ogni bit in arrivo ne produce n identici in uscita, in modo che (se gli errori sono indipendenti) il decisore possa correggere l’errore in base ad una “votazione a maggioranza” (majority voting). Ponendo ad esempio n = 3, definiamo il codice a ripetizione 3:1, composto da due codeword, 000 ed 111, per le quali risulta dm = 3: pertanto, il codice è in grado di correggere un errore e rivelarne due [319] [319] Poniamo di dover trasmettere 0110. La sequenza diventa 000 111 111 000 e quindi, a causa di errori, ricevo 000 101 110 100. Votando a maggioranza, ricostruisco la sequenza corretta 0 1 1 0.. L’esercizio a pag. 1↓ mostra come, se la probabilità di errore per un bit Pe è molto piccola, l’applicazione della decisione a maggioranza permetta di ridurne il valore a Pdece⋍3P2e. Per il codice a ripetizione si riscontra una distanza del codice massima, ovvero dm = n − k + 1, ed essendo k = 1, questa risulta pari a dm = n; d’altra parte, il tasso di codifica risulta mediocre, e pari solamente a Rc = 1 ⁄ n.
8.4.2.3 Errori a burst ed interleaving↓
Nonostante le capacità di correzione dei codici a blocchi possano sembrare adeguate a ridurre il valore di probabilità di errore, gli errori possono presentarsi in maniera non indipendente, ma concentrati in un breve intervallo di tempo: questa circostanza è indicata come caso degli errori a pacchetto (od a burst=scoppio). In tal caso, si usa ricorrere alla tecnica nota come scrambling [320] [320] Letteralmente: arrampicamento, ma anche “arruffamento”, vedi scrambled eggs, le uova strapazzate dell’english breakfast. o interleaving [321] [321] Leave = foglia, sfogliare, rastrellare, ed il termine potrebbe essere tradotto come intercalamento., attuabile a patto di accettare un ritardo di trasmissione. Si tratta infatti di modificare l’ordine dei dati inviati, in modo che gli errori che occorrono su bit vicini si riflettano in errori su bit... lontani, e quindi appartenenti a codeword differenti, come illustrato in fig. 8.28↑. Ovviamente, occorre prevedere un processo inverso (descrambling o deinterleaving) all’altro capo del collegamento. E’ appena il caso di notare che lo scrambler (similmente al codice di Gray) non altera il numero dei bit trasmessi.
Figura 8.28 Schema di principio della trasmissione a dati intercalati
8.4.3 Detezione di errore↓
In questo caso ci si limita a mettere il ricevitore in grado di accorgersi della presenza di errori, senza poterli correggere. Le parole errate possono essere scartate, oppure re-inviate su richiesta.
8.4.3.1 Parità↓
Viene comunemente usata nell’ambito della trasmissione asincrona (§ 8.6.1↓) e sincrona orientata al carattere (pag. 1↓) per rivelare errori sul bit, e consiste nell’aggiungere alla parola da trasmettere un ulteriore bit, in modo che in totale ci sia un numero pari di uni [322] [322] Ad esempio, alla sequenza 001001 verrà aggiunto uno 0, mentre a 010101 si aggiungerà ancora un 1, perché altrimenti gli uni complessivi sarebbero stati 3, che è dispari., applicando quindi una regola di parità pari (even). Il caso opposto, ossia l’aggiunta di un bit in modo da rendere dispari il numero di uni, prende nome di parità odd.
In entrambi i casi [323] [323] Il ricevitore deve comunque essere al corrente del fatto se la parità sia odd o even !, quando il ricevitore raggruppa i bit pervenuti, esegue un controllo detto appunto di parità, semplicemente contando il numero di uni, ed accorgendosi così se nella parola si sia verificato un errore (uno zero divenuto uno o viceversa). In tal caso, il ricevitore invierà all’altro estremo del collegamento una richiesta di ritrasmissione del gruppo di bit errati. Se invece si fosse verificato un errore che coinvolge due bit della parola, questo passerebbe inosservato, in quanto la parità prescritta verrebbe mantenuta. Infatti, la distanza di Hamming (vedi pag. 1↑) tra codeword ottenute aggiungendo il bit di parità è pari a due [324] [324] Considerando parole di 3 bit, le codeword (di 4 bit, in cui l’ultimo è una parità pari) risultano: (0000, 0011, 0101, 0110, 1001, 1010, 1100, 1111). E’ facile constatare che ognuna di esse differisce da tutte le altre per due bit..
Esempio: indicando la probabilità di errore sul bit con p (es 10 − 3) ed applicando la (10.76↑) si ottiene che la probabilità di i = 2 errori in n bit (es n = 10) vale (1)/(2)n(n − 1)p2 (es 4.5⋅10 − 5), e rappresenta il tasso residuo di errore su parola legato all’uso di un bit di parità; la trasmissione di n − 1 bit non protetti sarebbe invece stata esposta ad una probabilità np (es 0.9⋅10 − 2) di un bit errato su n.
Il calcolo del bit di parità pari può essere effettuato svolgendo la somma modulo due [325] [325] La somma modulo due è equivalente all’operazione di or esclusivo, viene a volte indicata con il simbolo ⊕, e corrisponde alle definizioni: 0⊕0 = 0, 0⊕1 = 1, 1⊕0 = 1, 1⊕1 = 0. di tutti i bit che compongono la parola (ovvero complementando il risultato, nel caso di parità dispari).
Il concetto di parità può essere esteso calcolando q bit di parità, ognuno a partire da un diverso sottoinsieme dei k bit di ingresso, con sottoinsiemi eventualmente sovrapposti. Un codice del genere prende il nome di codice di Hamming, descritto al § 11.3.1.1↓.
8.4.3.2 Somma di controllo↓
Quando il messaggio è composto da M diverse parole di N bit, la probabilità che almeno una di queste sia errata aumenta in modo circa proporzionale ad M, in base ad un ragionamento del tutto analogo a quello della nota 8.4.1.1↑.
Per aumentare le capacità di rivelazione del controllo di parità applicato sulle singole parole (indicato ora come parità di riga, o trasversale), si aggiunge al gruppo di M parole una ulteriore parola (detta somma di controllo o checksum), i cui bit si ottengono applicando il controllo di parità a tutti i bit “omologhi” delle M parole incolonnate, generando così una parità di colonna (o longitudinale), come esemplificato in figura.
A volte, si preferisce calcolare la somma di controllo mediante una operazione di somma modulo uno [326] [326] La somma modulo uno è l’equivalente binario dell’operazione di somma (decimale) tradizionale, comprese quindi le operazioni di riporto verso le cifre più elevate. Il riporto finale viene poi nuovamente sommato al risultato della somma., direttamente realizzabile in software in modo veloce. In tal caso, il ricevitore calcola una nuova somma di controllo longitudinale, includendo anche la somma di controllo originaria: in assenza di errori, il risultato deve fornire zero.
8.4.3.3 Codice polinomiale e CRC↓
L’utilizzo di una somma di controllo può produrre risultati scadenti nel caso di distribuzioni temporali dei bit errati particolarmente sfavorevoli, mentre la tecnica nota come ↓Cyclic Redundancy Check (o crc) [327] [327] Tale denominazione indica un’azione di controllo (check) realizzata mediante l’aggiunta di una ridondanza ottenuta applicando un codice ciclico - vedi § 11.3.1.2↓. garantisce prestazioni più uniformi. Questo metodo consiste nell’aggiungere ad una parola P di k bit che si desidera trasmettere, un gruppo R di q < k
ulteriori bit di protezione, calcolati a partire dai primi k, in modo da permettere la detezione di eventuali errori; sotto questo aspetto, il crc rientra nella categoria dei codici a blocchi (§ 8.4.2.1↑).
L’aggettivo polinomiale trae origine dalla associazione tra un numero binario B di n + 1 bit, indicati con bi, i = 0, 1, …n, ed un polinomio [328] [328] L’insieme di tutti i polinomi di grado minore od uguale ad n costituisce un particolare spazio algebrico, per il quale è possibile dimostrare una serie di proprietà, la cui verifica trascende dallo scopo di questo testo, e che consentono di stabilire le capacità del codice di rivelare gli errori. B(x) a coefficienti binari nella variabile x, di grado n, con espressione
B(x) = bnxn + bn − 1xn − 1 + … + b1x1 + b0
Un codice polinomiale↓ è definito a partire da un polinomio generatore↓ G(x) di grado q, i cui coefficienti binari identificano una parola G = gqgq − 1…g1g0 di q + 1 bit.
Indicando ora con P la sequenza dei k bit pi da proteggere, aggiungiamo a destra di questi un gruppo di q bit pari a zero, ottenendo una nuova parola P⋅2q lunga k + q bit, che quindi dividiamo per G (mediante aritmetica modulo due [329] [329] Per fissare le idee, consideriamo k = 8 bit a da proteggere, pari a P = 11100110, q = 4 bit di crc, ed un generatore G = 11001. La sequenza P⋅2q risulta pari a 11100110 0000, e la divisione modulo 2 tra P e G fornisce un quoziente Q = 10110110 (che viene ignorato) ed un resto R pari a 0110. Pertanto, viene trasmessa la sequenza T = P⋅2q⊕R = 11100110 0110 con k + q = 12 bit.
La divisione modulo 2 si realizza come mostrato nella figura a lato: considerando i bit più significativi di P⋅2q e G, l’uno nell’uno ci sta una volta, e scriviamo uno come primo bit di Q. Riportiamo ora G sotto P⋅2q, ed anzichè sottrarre i bit, ne calcoliamo l’or-esclusivo ⊕ bit-a-bit, ottenendo 00101, a cui aggiungiamo un uno abbassando il successivo bit (1) di P⋅2q. Stavolta l’uno nello zero ci sta zero volte, e dunque aggiungiamo uno zero a Q, riportiamo cinque zeri (come la lunghezza di G) allineati sotto al resto parziale, eseguiamo l’exor, ed abbassiamo un’altra cifra (1) di P. Il confronto ora è tra il quinto bit da destra del resto parziale (1) ed il bit più significativo (il quinto, 1) di G, ottendo la terza cifra di Q (1). Ripetiamo il procedimento, e quando tutti i bit del divisore sono stati usati, l’ultima operazione ⊕ fornisce il resto R cercato.
), ottenendo un quoziente Q, ed un resto R con al massimo q bit. Pertanto, possiamo scrivere
(P⋅2q)/(G) = Q⊕(R)/(G)
Le sequenze Q ed R costituiscono rispettivamente i coefficienti dei polinomi quoziente Q(x) e resto R(x), ottenibili dalla divisione di P(x)⋅2q per G(x). I q bit R del resto sono quindi utilizzati come parola di protezione, in modo da esprimere la sequenza T da trasmettere come T = P⋅2q⊕R di k + q bit, ovvero con i k bit più significativi pari a P ed i q bit in coda pari ad R. Il ricevitore effettua anch’esso una divisione, stavolta tra T e G, che in assenza di errori produce un resto nullo
(T)/(G) = (P⋅2q⊕R)/(G) = (P⋅2q)/(G)⊕(R)/(G) = Q⊕(R)/(G)⊕(R)/(G) = Q
in quanto sommando in aritmetica modulo due un numero per se stesso, si ottiene un risultato nullo. Pertanto, se T⁄G = Q con resto nullo, la parola P è riottenuta semplicemente shiftando T a destra di q posizioni.
Nel caso invece in cui si siano verificati errori, indichiamo con E la sequenza binaria di errore, di lunghezza k + q bit, ognuno dei quali è pari ad uno se in quella posizione si verifica errore, o zero in caso contrario, in modo da rappresentare il segnale ricevuto R come R = T⊕E. Se E ≠ 0 la divisione operata al ricevitore ora fornisce
(10.77) (R)/(G) = (T⊕E)/(G) = (T)/(G)⊕(E)/(G) = Q⊕(E)/(G)
e quindi si verifica la presenza di un resto diverso da zero [330] [330] Dalla (10.77↑) sembrerebbe che il resto sia E, ma dato che E(x) può avere grado > q, esso è divisibile per G(x), e dunque il resto non è E - altrimenti, sarebbe possibile correggerlo!! , che indica appunto la presenza di errori, tranne nei casi in cui E risulti perfettamente divisibile per G, evento con bassa probabilità se G è scelto opportunamente. Nel caso in cui q = 1 si ricade nel caso del controllo di parità (§ 8.4.3.1↑), a cui corrisponde G(x) = x + 1.
Per applicare il metodo, sia il trasmettitore che il ricevitore devono utilizzare lo stesso generatore G(x), per il quale esistono diverse scelte standardizzate [331] [331] Ecco quattro scelte utilizzate nei sistemi di trasmissione:
crc-12 G(x) = x12 + x11 + x3 + x2 + x + 1
crc-16 G(x) = x16 + x15 + x2 + 1
crc-ccitt G(x) = x16 + x12 + x5 + 1
crc-32 G(x) = x32 + x26 + x23 + x22 + x16 + x12 + x11 + x10 + x8 + x7 + x5 + x4 + x2 + x + 1
Come discusso, un polinomio di ordine q genera un crc di q bit; pertanto il crc-12, che è usato per caratteri a 6 bit, genera 12 bit di crc, mentre crc-16 e crc-ccitt, utilizzati in America ed in Europa rispettivamente per caratteri ad 8 bit, producono 16 bit di crc. In alcuni standard di trasmissione sincrona punto-punto, è previsto l’uso di crc-32.. Si può dimostrare che scegliendo G(x) in modo opportuno, il metodo discusso permette di rivelare
tutti gli errori singoli;
se G(x) contiene il temine noto + 1, tutti gli errori a burst che si estendono per q o meno bit;
se x + 1 è un fattore di G(x), tutti gli errori in numero dispari;
se G(x) è un polinomio primitivo [332] [332] https://it.wikipedia.org/wiki/Polinomio_primitivo, tutti gli errori doppi;
se G(x) è un polinomio primitivo di grado q − 1 moltiplicato per il fattore x + 1, tutti gli errori doppi entro un intervallo di 2q − 1 − 1 bit, e tutti gli errori in numero dispari.
Calcolo del CRC
L’aspetto che ha reso popolare questo motodo è la maniera in cui è possibile calcolare i q bit di controllo, che vengono essi stessi indicati come crc. Infatti la divisione binaria illustrata alla nota 8.4.3.3↑ è realizzabile a livello circuitale in modo relativamente semplice [333] [333] Vedi ad es. http://en.wikipedia.org/wiki/Computation_of_cyclic_redundancy_checks.
Si tratta di utilizzare un registro a scorrimento controreazionato
(vedi figura a lato), in cui i k bit da proteggere sono immessi ad uno ad uno da destra verso sinistra, seguiti da q zeri consecutivi. Per ogni valore immesso, quelli già presenti scorrono a sinistra nel registro, ed il bit che trabocca, oltre a rappresentare una cifra del quoziente, alimenta gli or esclusivi presenti nel registro; questi ultimi sono posti in corrispondenza dei coefficienti di G(x) pari ad uno, tranne che per quello corrispondente ad xq.
Al termine dell’inserimento dei k + q bit di P⋅2q, lo stato del registro a scorrimento costituisce proprio il resto R, da usare come crc. L’esempio in figura rappresenta il caso mostrato alla nota 8.4.3.3↑, in cui di G(x) = x4 + x3 + 1: con un pò di pazienza, è possibile verificare che il circuito effettivamente svolge i calcoli prescritti dalla procedura di divisione, e che si ottiene lo stesso risultato.

References: § 8
 § 8
 § 8
 § 8
 § 17
 § 17
 § 11
 § 8
 § 8
 § 11
 § 11
 § 8
 § 11
 § 11
 § 11