Programma di Geometria Superiore II modulo (2004/05)

Versione pdf

Nozioni fondamentali

  1. Codici a blocchi:
    1. Definizione
    2. Distanza di Hamming
    3. Distanza minima e correzione di errori
    4. Raggio di copertura e impacchettamento
    5. Limitazione di Singleton e codici MDS
    6. Limitazione di Hamming e codici perfetti
  2. Codici lineari:
    1. Definizione
    2. Peso minimo
    3. Matrice generatrice e matrice di controllo di parità
    4. Forma standard e codifica sistematica
    5. Equivalenza di codici
    6. Codice duale
    7. Codici di Hamming
    8. Decodifica dei codici di Hamming binari
    9. Decodifica a sindrome
    10. Limitazione di Plotkin e codici equidistanti
  3. Combinazione di codici:
    1. Accorciamento
    2. Estensione
    3. Punzonatura
    4. Allungamento
    5. Condivisione temporale
    6. Somma
    7. Prodotto
  4. Cenni di Geometria Finita:
    1. Strutture di incidenza
    2. Disegni
    3. Ordine di un disegno e disegni simmetrici
    4. Matrici di incidenza e legame con i parametri di un disegno
    5. Teorema di Fisher
    6. Enunciato del teorema di Bruck-Ryser-Chowla
    7. Piani proiettivi e il piano di Fano
  5. Codici da disegni:
    1. Costruzioni
    2. Il codice binario di Golay: proprietà e costruzioni
  6. I codici ciclici:
    1. Definizione
    2. Relazione fra codici ciclici e ideali
    3. Polinomio generatore
    4. Legami fra polinomio generatore, polinomio di controllo di parità e codice ortogonale
    5. Idempotenti
    6. Codifica e forma "antisistematica"
    7. Decodifica
    8. Definizione di errore consecutivo (burst) e proprietà
  7. I codici BCH e di Reed-Solomon
    1. Costruzione come codici ciclici
    2. Trasformata discreta di Fourier e limitazione BCH
    3. Proprietà MDS per Reed-Solomon
    4. L'equazione chiave
    5. Decodifica dei codici BCH
    6. Altre costruzioni dei codici di Reed-Solomon
    7. Decodifica dei codici di Reed-Solomon
    8. Definizione di cancellatura (erasure) e proprietà

Argomenti di approfondimento

  1. Modelli di canale e limitazioni asintotiche per famiglie di codici
  2. Dimostrazione del teorema di Bruck-Ryser-Chowla e piani proiettivi
  3. Disegni e codici di Hadamard
  4. Codici ciclici e decodifica di errori consecutivi
  5. Rappresentazioni dei codici BCH e relative proprietà
  6. Decodifica di cancellature mediante i codici di Reed-Solomon
  7. Decodifica a lista per i codici di Reed-Solomon
  8. Codici di Reed-Muller e geometria finita
  9. Grafi e codici LDPC