Coding Theory/Teoria de Codigos

Dates:       Monday 9/6            de 9 a 12 h.                  Monday 22/6          de 9 a 12 h.

                Wednesday 10/6    de 9 a 12 h.                   Tuesday 23/6         de 9 a 12 h.

                Thursday 11/6        de 15 a 18 h.                 Thursday 25/6        de 9 a 12 h.

Abstract


           To get acquainted with the mathematical basis and the
           practical design of algebraic codes for error correction in
           communication networks and digital data storage. These codes
           allow for effective communication and data storage in
           unreliable and noisy media that introduce data errors.


           Familiarizar al estudiante con las bases matematicas y la
           implementacion de codigos algebraicos para correccion de
           errores en sistemas de comunicaciones y almacenamiento de
           datos digitales. Estos codigos permiten la comunicacion y
           almacenamiento de datos en canales y medios imperfectos o
           ruidosos, que introducen errores en los datos.


           Syllabus / Temario:


           1. Introduction: The q-ary symmetric channel. Maximum
           likelihood decoding. Error correction, error detection and
           erasure correction.


           2. Linear codes: Representation with generating matrices and
           parity checks. Syndrome decoding. Hamming codes.


           3. Introduction to finite fields: Two-error correcting
           codes. Irreducible polynomials. Primitive polynomials.


           4. Bounds for parameters of codes: Singleton's bound. MDS
           codes. Hamming's spherical packing upper boud. Perfect
           codes. Gilbert-Varshamov's bound. Asymptotic bounds.


           5. Reed-Solomon codes and related codes: Generalized
           Reed-Solomon codes (GRS). GRS decoding with Euclid's
           algorithm. Berlekamp-Massey algorithm for GRS decoding. BCH
           codes and alternating codes as subcodes of the subfields of
           GRS codes.Concatenated codes.


           6. Finite fields structures and cyclic codes: Cyclotomic
           cosets and minimal polynomials. Cyclic codes.BCH codes as
           cyclic codes. The BCH bound.


           1. Introduccion: El canal simetrico q-ario. Decodificacion
           usando maxima verosimilitud. Correccion de errores,
           deteccion de errores y correccion de borrados.


           2. Codigos lineales: Representacion mediante matrices
           generadoras y de chequeo de paridad. Decodificacion usando
           sindromes. Codigos de Hamming


           3. Introduccion a cuerpos finitos y a codigos que corrigen
           dos errores: Polinomios irreductibles. Polinomios
           primitivos. Codigos que corrigen 2 errores.


           4. Cotas en los parametros de los codigos: La cota de
           Singleton; codigos MDS. La cota de empaquetamiento esferico
           de Hamming; Codigos perfectos. La cota de Gilbert-Varshamov
           . Cotas asintoticas.


           5. Codigos de Reed-Solomon y otros codigos relacionados:
           Codigos generalizados de Reed-Solomon (GRS). Decodificacion
           de los codigos GRS usando el algoritmo de Euclides. El
           algoritmo de decodificacion de Berlekamp-Massey . Codigos
           BCH y codigos alternantes como subcodigos que son subcuerpos
           de los codigos GRS. Codigos concatenados.


           6. Estructuras de cuerpos finitos y codigos ciclicos: Cosets
           ciclotomicos y polinomios minimales. Codigos ciclicos.
           Codigos BCH como codigos ciclicos. La cota BCH.


           ………………………………………………………………………………………………………………


           The course is open to any interested person. Please confirm
           to conrado@lsi.upc.edu your interest.


           Supported by the MICINN program "ayudas de movilidad de
           profesores en másters oficiales" 2008-2009.