Skip to main content
If you continue browsing this website, you agree to our policies:
  • Condizioni di utilizzo e trattamento dei dati
Continue
x
e-Learning - UNIMIB
  • Home
  • My Media
  • More
Listen to this page using ReadSpeaker
English ‎(en)‎
English ‎(en)‎ Italiano ‎(it)‎
 Log in
e-Learning - UNIMIB
Home My Media
Percorso della pagina
  1. Science
  2. Master Degree
  3. Matematica [F4002Q - F4001Q]
  4. Courses
  5. A.A. 2024-2025
  6. 1st year
  1. Information Theory and Error-Correcting Codes
  2. Summary
Insegnamento Course full name
Information Theory and Error-Correcting Codes
Course ID number
2425-1-F4001Q122
Course summary SYLLABUS

Course Syllabus

  • Italiano ‎(it)‎
  • English ‎(en)‎
Export

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.

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

ISTRUZIONE DI QUALITÁ
Export

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.

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

  1. Information Theory, messages transmission, noisy channels, error probability, entropy, Shannon’s Theorem, symmetric channel.
  2. Error-correcting codes, alphabet, finite fields, linear codes, Hamming codes, cyclic codes, Reed-Solomon and Reed-Muller codes.
  3. Upper and lower Bounds, Sphere Packing, Gilbert-Varshamov, Perfect codes and their classification.
  4. Weight preserving maps, MacWilliams’ Theorem, Monomial maps, Wilson Theorem.
  5. Weight enumerator polynomials, MacWilliams’ Theorem, self-dual codes, isotropic vectors, Witt Theorem,.
  6. 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

QUALITY EDUCATION
Enter

Key information

Field of research
MAT/02
ECTS
8
Term
Second semester
Activity type
Mandatory to be chosen
Course Length (Hours)
56
Degree Course Type
2-year Master Degreee
Language
Italian

Staff

    Teacher

  • Andrea Previtali
    Andrea Previtali

Students' opinion

View previous A.Y. opinion

Bibliography

Find the books for this course in the Library

Enrolment methods

Manual enrolments
Self enrolment (Student)

Sustainable Development Goals

QUALITY EDUCATION - Ensure inclusive and equitable quality education and promote lifelong learning opportunities for all
QUALITY EDUCATION

You are not logged in. (Log in)
Policies
Get the mobile app
Powered by Moodle
© 2025 Università degli Studi di Milano-Bicocca
  • Privacy policy
  • Accessibility
  • Statistics