Syllabus del corso
Obiettivi
Coerentemente con gli obiettivi formativi del Corso di Studio, l'insegnamento si propone di fornire allo studente le conoscenze riguardanti l'acquisizione degli strumenti per la trasmissione di informazione su canali con rumore, al fine di analizzare procedure di scambio ottimali nella rilevazione e correzione di errori. Tempo permettendo verranno impartiti alcuni rudimenti su linguaggi di programmazione simbolica come Magma e Gap. Tali strumenti servono ad enfatizzare gli aspetti sperimentali della scoperta matematica. Verranno altresì fornite le competenze necessarie a comprendere e analizzare le principali tecniche e metodi dimostrativi connessi all teoria, e le abilità utili ad applicarle per risolvere esercizi e affrontare problemi.
-
Conoscenza e capacità di comprensione (Knowledge and understanding)
Gli studenti acquisiranno una conoscenza di base dei principi fondamentali della teoria dei codici correttori, inclusi concetti quali codifica, decodifica, distanza di Hamming, codici lineari, codici ciclici e proprietà di correzione d’errore. Tali conoscenze si baseranno su manuali di testo e materiali didattici aggiornati e saranno il fondamento per studi più approfonditi. -
Conoscenza e capacità di comprensione applicate (Applying knowledge and understanding)
Gli studenti saranno in grado di applicare i concetti appresi per analizzare e progettare semplici sistemi di codifica e decodifica in contesti reali o simulati, riconoscendo le caratteristiche dei codici correttori e la loro applicabilità in ambito delle comunicazioni digitali e informatiche. -
Autonomia di giudizio (Making judgements)
Il corso promuoverà lo sviluppo della capacità di valutare in modo critico l’efficacia e l’efficienza dei diversi codici correttori, di selezionare metodi opportuni per specifici problemi, e di interpretare i risultati ottenuti attraverso metodi teorici e computazionali. -
Abilità comunicative (Communication skills)
Gli studenti impareranno a comunicare in modo chiaro e preciso i concetti della teoria dei codici, utilizzando la terminologia tecnica appropriata, sia in forma scritta che orale, anche in contesti collaborativi e interdisciplinari. -
Capacità di apprendimento (Learning skills)
Il corso stimolerà l’autonomia nello studio, fornendo gli strumenti per approfondire in modo autonomo argomenti correlati, affrontare esercizi complessi e prepararsi ad esami o corsi successivi nel campo della matematica applicata o dell’informatica teorica.
Contenuti sintetici
Teoria dell’Informazione, trasmissione messaggi, probabilita' di errore, entropia, Teorema di Shannon, canale simmetrico, codici correttori di errore, alfabeti, campi finiti, codici lineari, codici di Hamming, ciclici, di Reed-Solomon e Muller, polinomio enumeratore, Teoremi di MacWilliams. Teoria invarianti gruppi finiti.
Programma esteso
Trasmissioni con rumore, alfabeto, parole di lunghezza fissata, codici a blocchi; canale simmetrico m-ario con probabilità p, codici di ripetizione, codice binario di Hamming (7,4,3); distanza di Hamming, lunghezza, dimensione e distanza minima di un codice, sphere packing bound, Gilbert-Varshamov bound, codici perfetti, cenni ai codici di Golay e di Hamming; Codici lineari, peso minimo, estensione di codici; Matrice generatrice di un codice, forma sistematica e standard, codici duali, matrici di controllo, distanza minima di un codice lineare; Cenni all'aritmetica dei campi finiti; Esistenza di codici autoduali, spazi simplettici e ortogonali; Decodifica di codici lineari, coset leaders, sindromi; Spazi proiettivi, decomposizione in spazi affini, codici di Hamming, codici 1-perfetti, unicità monomiale, traslati di codici lineari; Duali di codici di Hamming, codici a peso costante, teorema di Bonisoli; Gruppo degli automorfismi dei codici di Hamming; Struttura campi finiti, elementi primitivi; Polinomi ciclotomici su campi finiti; Fattorizzazione di x^n-1, polinomi minimi, struttura automorfismi campo finito, cenni teoria di Galois; classi ciclotomiche, gradi fattori irriducibili x^n-1, formula d’inversione di Moebius; Definizione di codici ciclici, Teorema di Prange; Duale codice ciclico, polinomi generatori; Generazione di codici ciclici, codici di Golay come codici ciclici, BCH bound; Teorema di MacWilliams sull’estensione di mappe lineari preservanti pesi a trasformazioni globali monomiali; Polinomi enumeratori, teorema di MacWilliams, esempi C=0, C=Rep e loro duali, caratteri di un gruppo; Esempi di anelli con caratteri non degeneri, leggi di ortogonalita'; Teorema di Lloyd sui codici perfetti; Introduzione alla teoria degli invarianti dei gruppi finiti, Teoremi di Noether e di Molien, serie di Hilbert-Poincaré, gruppi generati da pseudo-riflessioni, anelli di Cohen-Macaulay, Teorema di Chevalley-Shephard-Todd.
Prerequisiti
Algebra Lineare, Teoria dei Gruppi, Teoria dei Campi Finiti, Nozioni elementari di Termodinamica e Probabilità.
Modalità didattica
L'insegnamento prevede lezioni frontali per 56 ore (8 CFU), articolate in: lezioni teoriche in cui si fornisce la conoscenza di definizioni, risultati e teoremi rilevanti e altre in cui si intende fornire competenze e abilità necessarie per utilizzare tali nozioni nella risoluzione di esercizi e nell'analisi di problemi
Le attuali disposizioni rettorali prevedono che la lezione sia fruibile sia in presenza che da remoto. Le lezioni verranno videoregistrate e saranno rese disponibili agli studenti sulla piattaforma e-learning del corso.
Materiale didattico
Testo di Riferimento:
- Hall, Notes on Coding Theory, 2005
- Appunti videoscritti delle singole lezioni reperibili su questa piattaforma.
- Appunti scritti in LaTeX in formato pdf reperibili su questa piattaforma.
Altri Testi:
- Huffman and Pless, Fundamentals of error-correcting codes, 2010
- MacWilliams and Sloane, The Theory of Error-Correcting Codes, 1977
- Smith, Polynomial invariants of finite groups, 1995
Periodo di erogazione dell'insegnamento
Secondo semestre
Modalità di verifica del profitto e valutazione
L'esame consiste in un'interrogazione orale in cui vengono accertate sia l'acquisizione dei contenuti teorici impartiti nel corso sia le capacita' di analisi e risoluzione di problemi.
Le attuali disposizioni rettorali richiedono che la prova orale dell’esame si svolga in presenza a meno che lo studente non rientri in particolari e categorie riportate nel decreto rettorale. In tal caso la prova orale potrà essere sostenuta da remoto mediante piattaforma WebEx con accesso reso disponibile sulla pagina e-learning dell’insegnamento.
Orario di ricevimento
Su appuntamento.
Sustainable Development Goals
Aims
In line with the aims of the CdS, the course will provide students the knowhow necessary to deal with transmission of information via noicy channels, in order to analyze optimal error-correcting and -detecting procedures. Time permitting some rudiments of programming languages as Magma and Gap will be imparted. These tools serve to emphasize sperimental aspects of mathematical discovery. We will also impart the necessary skills to comprehend and analyze the main technical and proof methods.
Those will be tested via problem solving and resolutionef exercises related to the contents of the course.
-
Knowledge and understanding
Students will acquire fundamental knowledge of the basic principles of error-correcting codes, including encoding, decoding, Hamming distance, linear codes, cyclic codes, and error-correction properties. This knowledge will be based on textbooks and teaching materials and will provide a foundation for more advanced studies. -
Applying knowledge and understanding
Students will be able to apply the concepts learned to analyze and design basic coding and decoding schemes in real or simulated contexts, recognizing the features of different codes and their applicability in digital communications and information systems. -
Making judgements
The course will develop students' ability to critically evaluate the efficiency and suitability of different error-correcting codes, to choose appropriate methods for specific problems, and to interpret results using both theoretical and computational tools. -
Communication skills
Students will learn to clearly and accurately communicate concepts from coding theory, using appropriate technical terminology, both in written and oral form, including in collaborative and interdisciplinary settings. -
Learning skills
The course will encourage autonomous learning by providing the tools to independently explore related topics, solve complex exercises, and prepare for exams or further study in applied mathematics or theoretical computer science.
Contents
Information Theory, messages transmission, error probability, entropy, Shannon’s Theorem, symmetric channel, Error-correcting codes, alphabet, finite fields, linear codes, Hamming codes, cyclic codes, Reed-Solomon and Reed-Muller codes, Weight preserving maps, MacWilliams’ Theorems, Invariant Theory of Finite Groups.
Detailed program
- Information Theory, messages transmission, noisy channels, error probability, entropy, Shannon’s Theorem, symmetric channel.
- Error-correcting codes, alphabet, finite fields, linear codes, Hamming codes, cyclic codes, Reed-Solomon and Reed-Muller codes.
- Upper and lower Bounds, Sphere Packing, Gilbert-Varshamov, Perfect codes and their classification.
- Weight preserving maps, MacWilliams’ Theorem, Monomial maps, Wilson Theorem.
- Weight enumerator polynomials, MacWilliams’ Theorem, self-dual codes, isotropic vectors, Witt Theorem,.
- Invariant Theory of Finite Groups, primary and secondary invariants, Cohen-Macaulay rings, groups generated by pseudo-reflection, Shephard-Todd Theorem.
Prerequisites
Algebra I and II, Linear Algebra, Group Theory, Finite Field Theory, Elementary notions of Thermodynamics and Probability.
Teaching form
The course consists of Lectures for 8 credits. They will give knowledge of basic definitions, relevant results and theorems. On the other side, we intend to give skills to use results and knowledge in solving exercises and analysing problems
According to the present dispositions lectures can be attended either in presence or remotely; in any case the lectures will be videorecorded and made available on the e-learning platform.
Textbook and teaching resource
**Textbooks:
- Hall, Notes on Coding Theory, 2005
- Tablet taken notes available on this platform.
- LaTeX Notes in pdf format available on this platform.
Further Readings:
- Huffman and Pless, Fundamentals of error-correcting codes, 2010
- MacWilliams and Sloane, The Theory of Error-Correcting Codes, 1977
- Smith, Polynomial invariants of finite groups, 1995
Semester
Second semester
Assessment method
The exam consists of an oral enquiry assessing both the student's acquisition of the course contents and her/his capabilities of analyzing and solving problems.
According to the actual dispositions the exam will be in presence unless the candidate belongs to one of the categories listed in the previously mentioned document. She/he must connect via webex exploiting a link reported on the e-learning page of the course.
Mark range: 18-30/30.
Office hours
By appointment.
Sustainable Development Goals
Staff
-
Andrea Previtali
