Sommario:
Sono codici a blocco lineari con l’ulteriore proprietà che se c∈C ogni permutazione ciclica ∈C.
Esempio:
c≡(101110)∈C ⇒
(010111)∈C
(101011)∈C
(110101)∈C
(111010)∈C
(011101)∈C
Lo studio dei codici ciclici si sviluppa più facilmente grazie alla loro rappresentazione polinomiale:
100111 ↔ p5+p2+p+1
c ↔ c(p) polinomio codice
Ogni blocco binario di lunghezza n è associato ad un polinomio di grado ≤n-1
Un codice ciclico C(n,k) è descrivibile attraverso un polinomio generatore g(p) di grado n-k.
Ogni parola codice c(x) è un multiplo di g(p) cioè:
c(p)=g(p)x(p)
con x(p) polinomio informazione di grado ≤k-1
Lo schift ciclico di una posizione della parola codice
c=(c1,c2, … ,cn) è c(1)=(c2,c3, … ,cn,c1).
In rappresentazione polinomiale: vedi figura
= c(p)(pn+1) mod(pn+1)+c(p)mod(pn+1)=
= c(p) mod(pn+1) = c(p)
Con n shift ciclici si riottiene la parola codice c.
In ogni codice ciclico (n,k) ogni polinomio codice è multiplo di un polinomio g(x) di grado n-k detto polinomio generatore:
g(p) = pn-k+g2pn-k-1+g3pn-k-2+….gn-k-1p+1 multiplo di pn+1
Detto x(p) il polinomio che rappresenta la sequenza di informazione:
x(p) = x1pK-1+x2pK-2+……+xk
c(p) = x(p)⋅(g(p)
Per generare un codice ciclico (7,4) abbiamo bisogno di un polinomio generatore di grado 7-4=3.
p7+1 = (p+1)(p3+p2+1)(p3+p+1)
I possibili polinomi generatori sono allora:
p3+p2+1, p3+p+1
Scegliamo il primo e moltiplichiamolo per tutti i possibili polinomi x(p) (sono 16=24) ottenendo così le 16 parole codice.
Come realizzare il prodotto tra i due polinomi x(p) e g(p)?
Con un filtro FIR con matematica binaria
Il codice realizzato con la relazione:
c(p)=x(p)g(p)
non è sistematico, cioè i primi k simboli binari non coincidono con i k simboli di informazione.
Procedura per realizzare un codice ciclico sistematico: vedi figura
I polinomi codice sono allora multipli di g(p).
vedi figura
r(p) si calcola con un circuito divisore cioè l’inverso di un circuito FIR IIR (in logica binaria).
vedi figura in alto
vedi figura in basso
dopo quattro clock nel registro è presente il resto della divisione che definisce gli n-k simboli di parità.
Deriviamo la matrice generatrice di un codice ciclico in forma sistematica.
Ogni riga è un multiplo di g(p) perché è una parola codice.
La riga k-sima sarà un polinomio di grado n-k perché si hanno k-1 zeri seguiti da un 1⇒pn-k è presente.
Inoltre anche l’ultimo termine (il termine noto) deve essere presente altrimenti se fosse zero con uno shift avremmo i primi K simboli tutti nulli con la presenza di almeno un simbolo di parità non nullo: ciò non è possibile per i codici lineari.
Quindi la riga k-sima è un polinomio pn-k+…+1 che è una parola codice che coincide con il polinomio generatore.
Codice ciclico (7,4) con g(p)= p3+p2+1.
La 3a riga si ottiene: p4mod(p3+p2+1)=p2+p+1 ↔ 0010111
La 2a riga si ottiene: p5mod(p3+p2+1)=p+1 ↔ 0100011
La 1a riga si ottiene: p6mod(p3+p2+1)= p2+p ↔ 1000110
I codici di Hamming sono codici ciclici.
Il codificatore è un circuito moltiplicatore in logica binaria (circuito FIR in matematica binaria).
Il decodificatore divide la parola ricevuta per g(p) ed utilizza il resto della divisione per effettuare la correzione.
I codici BCH sono una sottoclasse dei codici ciclici: essi possono correggere t errori. E’ stato proposto un algoritmo particolarmente semplice per decodificare i codici BCH: algoritmo di Berlekamp-Massey.
Per ogni t e m esiste un codice BCH con parametri:
n = 2m – 1
n – k ≤ mt
dmin = 2t + 1
Poiché t e m sono arbitrari il progettista ha una grande possibilità di selezione nella famiglia dei codici BCH.
Esistono tabelle in cui i coefficienti del polinomio g(p) sono riportati in ottale.
Esempio: Il codice BCH (15,5) ha g(p) espresso in ottale pari a 2467 cioè: 10, 100, 110, 111 p10+p8+p5+p4+p2+p+1
Sono un sottoinsieme dei codici BCH.
Sono codici non binari, cioè le componenti di ogni parola codice appartengono ad un alfabeto q-ario con q=2k.
vedi figura in alto
I codici di Reed-Solomon sono in grado di correggere fino a:
vedi figura in basso
Sono utili per canali con errori a burst e si utilizzano spesso in congiunzione con modulazioni q-arie.
Per quali valori di k esiste un codice ciclico C(6,k)?
Il polinomio g(p) deve essere un fattore qualsiasi di p6+1.
Determinare un polinomio generatore, se esiste, per un codice ciclico C(7,3) e la distanza minima.
g(p) deve essere di grado n-k=4
Riassunto della lezione
Cenni sulla caratterizzazione dei canali con fading
Argomenti della lezione 14
1. Schema canonico di un sistema di trasmissione numerico punto-punto
4. Rappresentazione geometrica dei segnali
5. Trasmissione numerica su canale AWGN
6. Prestazioni del ricevitore ottimo su canale AWGN I
7. Prestazioni del ricevitore ottimo su canale AWGN II
8. Demodulazione MV non coerente di segnali FSK
9. Trasmissione su canale AWGN a banda limitata
10. Capacità di canale e codifica
11. Codifica di canale a blocchi
13. Codici ciclici
G.Proakis, M.Salehi, “Communication Systems Engineering”, p. 615-623.