Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
I corsi di Ingegneria
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Luigi Paura » 13.Codici ciclici


Codici ciclici

Sommario:

  • Definizione e proprietà dei codici ciclici
  • Definizione del polinomio generatore

Definizione

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

Rappresentazione polinomiale

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

Proprietà dei codici ciclici

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

Proprietà dei codici ciclici

Lo schift ciclico di una posizione della parola codice

c=(c1,c2, … ,cn) è c(1)=(c2,c3, … ,cn,c1).

In rappresentazione polinomiale: vedi figura


Proprietà dei codici ciclici


Proprietà dei codici ciclici

= 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

Proprietà dei codici ciclici

Detto x(p) il polinomio che rappresenta la sequenza di informazione:

x(p) = x1pK-1+x2pK-2+……+xk

c(p) = x(p)⋅(g(p)

Esempio

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.

Implementazione con filtri FIR

Come realizzare il prodotto tra i due polinomi x(p) e g(p)?

Con un filtro FIR con matematica binaria


Implementazione con filtri FIR


Codici sistematici

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.

Codici sistematici

Procedura per realizzare un codice ciclico sistematico: vedi figura

I polinomi codice sono allora multipli di g(p).


Codici sistematici

vedi figura

r(p) si calcola con un circuito divisore cioè l’inverso di un circuito FIR IIR (in logica binaria).


Esempio


Circuito divisore

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à.


Matrice generatrice di un codice ciclico

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.

Matrice generatrice di un codice ciclico

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.

Esempio

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


Codici di Hamming

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.

Codici BCH

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

Codici BCH

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

Codici di Reed-Solomon

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.


Codici di Reed-Solomon

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.


Esempio 1

Per quali valori di k esiste un codice ciclico C(6,k)?

Il polinomio g(p) deve essere un fattore qualsiasi di p6+1.


Esempio 2

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


Esempio 2

Se scegliamo p4+p2+p+1: vedi figura

Il minimo peso di Hamming è 4, quindi dmin=4.


Considerazioni conclusive

Riassunto della lezione

  • Sono stati introdotti i codici ciclici, le loro proprietà e le strutture del codificatore e decodificatore.
  • E’ stato mostrato che il codice di Hamming rientra nella famiglia dei codici ciclici.
  • Sono stati presentati i codici ciclici BCH e di Reed-Solomon.

Prossima lezione

Cenni sulla caratterizzazione dei canali con fading

Argomenti della lezione 14

  • Introduzione ai canali wireless
  • Classificazione del fading
  • Modello lineare tempo-variante: multipath e doppler spread
  • Cenni sul modello statistico
  • Modello di canale mediante filtro trasversale
  • Banda di coerenza e tempo di coerenza

I materiali di supporto della lezione

G.Proakis, M.Salehi, “Communication Systems Engineering”, p. 615-623.

  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion