Per i casi i = 0 (tutti giusti) ed i = n (tutti sbagliati) il risultato è immediato, in quanto risulta P(0, n) = (1 − p)ⁿ e P(n, n) = pⁿ. Per 0 < i < n ci troviamo in un classico caso di prove ripetute [776]   [776] Vedi ad es. https://it.wikiversity.org/wiki/Prove_ripetute, in quanto si tratta di osservare l’evento di errore (con probabilità p) su n ripetizioni. La probabilità che ci siano esattamente (ad es. i primi) i bit errati ha valore pⁱ(1 − p)^n − i, ma dato che i bit errati possono essere comunque distribuiti su n, e che vi sono ⎛⎜⎝n i⎞⎟⎠ = n(n − 1)⋯(n − i + 1)i! modi di scegliere i oggetti su n, il risultato cercato è espresso dalla d.d.p. di Bernoulli (vedi § 22.1) che, se np < 0.1, può essere approssimata come [777]   [777] Dal confronto tra (21.26) e (21.27) osserviamo che l’approssimazione consiste nel considerare (1 − p)^n − i ≃ 1. Per verificare che ciò sia lecito qualora np≪1, cerchiamo il valore di p tale che (1 − p)ⁿ > 0.9, da cui discende che anche (1 − p)^n − i > 0.9 per qualunque i. Dato che si può scrivere (vedi nota 1306 a pag. 22.1) (1 − p)ⁿ = ∑ⁿ_k = 0⎛⎜⎝n k⎞⎟⎠p^k > 1 − np, otteniamo la condizione (1 − p)ⁿ > 1 − np > 0.9, da cui si ottiene np < 1 − 0.9 = 0.1: ad esempio, se n = 1000 occorre che sia almeno p = 10^− 4. Altrimenti l’approssimazione non è valida, e la (21.28) deve essere verificata; qui sotto mostriamo la d.d.p. di Bernoulli (21.26) per diversi valori di np, evidenziando come qualora np < 0.1 essa risulti monotona decrescente con i.

La (21.27) applicata al caso di un singolo errore (i = 1) su n fornisce P(1, n) ≃ np [778]   [778]  In linea di principio, dato che la probabilità che solo il primo bit su n sia sbagliato è pari a p(1 − p)^n − 1 e che lo stesso risultato si ottiene anche per gli altri n − 1 casi possibili, la probabilità P(1, n) di un solo (generico) bit sbagliato su n è pari a P(1, n) = np(1 − p)^n − 1, che si approssima come np qualora si consideri (1 − p)^n − 1 ≃ 1 in virtù della condizione np≪1., ovvero la probabilità di un solo bit errato su n è circa pari ad n volte la P^bi_e nel flusso binario. D’altro canto, per la probabilità di due bit errati su n la (21.27) fornisce P(2, n) ≃ 12 n(n − 1) p² e, sempre se np < 0.1, osserviamo che P(2, n) ≪ np ≃ P(1, n), ovvero inferiore a quella di un solo bit errato. Più in generale, risulta che 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/o di n, l’approssimazione perde validità, e la probabilità P(i, n) può invece aumentare con i, e in tal caso il sistema di trasmissione è praticamente inusabile. E’ questo il motivo per cui non è opportuno che la lunghezza n delle parole [779]   [779] Così come non è opportuno aumentare di troppo la dimensione di un pacchetto dati, anche se in tal modo si riduce l’overhead, vedi § 22.5.1. ecceda il limite np < 0.1 imposto dalla probabilità di errore sul bit p = P^bit_e offerta dal collegamento.

L’esposizione prosegue introducendo per prime definizioni e soluzioni che realizzano la correzione degli errori, il cui approfondimento è svolto al § 17.4, mentre al § 15.6.3 sono illustrate tre tecniche comunemente utilizzate per la detezione di errore; la descrizione dei protocolli arq è infine rimandata al § 22.6.

Notiamo come questo codice sia particolarmente poco efficiente, dato che per esso si ottiene un tasso di codifica R_c = kn = 1n; d’altra parte, il codice a ripetizione è uno dei pochi per cui d_m = q + 1, e non meno.

La trattazione della codifica di canale di tipo fec prosegue in modo più approfondito al § 17.4, dove sono illustrate le tecniche più avanzate.

In entrambi i casi [789]   [789] Il ricevitore deve comunque essere al corrente del fatto se la parità sia odd o even ! dopo aver raggruppato i bit pervenuti il ricevitore esegue un controllo detto appunto di parità, semplicemente contando [790]   [790] La conta può essere realizzata in forma algoritmica o circuitale, eseguendo la somma modulo due di tutti i bit che compongono la parola (ovvero complementando il risultato, nel caso di parità dispari). La somma modulo due è equivalente all’operazione di or esclusivo, viene a volte indicata con il simbolo ⊕, e corrisponde alla regola 0⊕0 = 0, 0⊕1 = 1, 1⊕0 = 1, 1⊕1 = 0. 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 errato. Se invece si è 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) relativa ad un codebook ottenuto aggiungendo ad ogni possibile parola di k bit il corrispondente di parità, è pari a due [791]   [791] 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 almeno due bit..

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 [792]   [792] 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.

L’aggettivo polinomiale trae origine dalla associazione tra un numero binario B di n + 1 bit, indicati con b_i, i = 0, 1, …n, ed un polinomio [794]   [794] 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 Un codice polinomiale è definito a partire da un polinomio generatore G(x) di grado q, i cui coefficienti binari identificano una parola G = g_qg_q − 1…g₁g₀ di q + 1 bit.

Indicando ora con P la sequenza dei k bit p_i da proteggere, aggiungiamo a destra di questi un gruppo di q bit pari a zero, ottenendo una nuova parola P ⋅ 2^q lunga k + q bit, che quindi dividiamo per G (mediante aritmetica modulo due [795]   [795]  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 ⋅ 2^q risulta pari a 10 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 ⋅ 2^q ⊕ 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 ⋅ 2^q e G, l’uno nell’uno ci sta una volta, e scriviamo uno come primo bit di Q. Riportiamo ora G sotto P ⋅ 2^q, 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 ⋅ 2^q. 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 Le sequenze Q ed R costituiscono rispettivamente i coefficienti dei polinomi quoziente Q(x) e resto R(x), ottenibili dalla divisione di P(x) ⋅ 2^q 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 ⋅ 2^q ⊕ 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 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 e quindi si verifica la presenza di un resto diverso da zero [796]   [796] Dalla (21.30) 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à (§ 15.6.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 [797]   [797] 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

Si tratta di utilizzare un registro a scorrimento controreazionato (vedi figura seguente), 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 x^q.

Al termine dell’inserimento dei k + q bit di P ⋅ 2^q, 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 795, in cui di G(x) = x⁴ + x³ + 1: con un po’ di pazienza, è possibile verificare che il circuito effettivamente svolge i calcoli prescritti dalla procedura di divisione, e che si ottiene lo stesso risultato.