LECTURES
- Simeon Ball, Universitat Politècnica de Catalunya, Spain: "Maximum Distance Separable Codes"
- [1]
- S. Ball, On sets of vectors of a finite vector space in which every subset of basis size is a basis, J. Eur. Math. Soc., 14 (2012) 733-748.
- [2]
- S. Ball and J. De Beule, On sets of vectors of a finite vector space in which every subset of basis size is a basis II, Des. Codes Cryptogr., 65 (2012) 5-14.
- [3]
- A. Blokhuis, A. A. Bruen and J. A. Thas, Arcs in PG(n,q), MDS-codes and three fundamental problems of B. Segre - some extensions, Geom. Dedicata, 35 (1990) 1-11.
- [4]
- R. C. Bose, Mathematical theory of the symmetrical factorial design, Sankhya, 8 (1947), 107-166.
- [5]
- K. A. Bush, Orthogonal arrays of index unity, Ann. Math. Statist., 23 (1952) 426-434.
- [6]
- D. G. Glynn, The non-classical 10-arc of PG(4,9), Discrete Math., 59 (1986) 43-51.
- [7]
- J. W. P. Hirschfeld, Rational curves on quadrics over finite fields of characteristic two, Rend. Mat., 3 (1971) 772-795.
- [8]
- J. W. P. Hirschfeld and L. Storme, The packing problem in statistics, coding theory and finite projective spaces: update 2001, in Developments in Mathematics, 3, Kluwer Academic Publishers. Finite Geometries, Proceedings of the Fourth Isle of Thorns Conference, pp. 201-246.
- [9]
- F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, North-Holland, 1977.
- [10]
- B. Segre, Ovals in a finite projective plane, Canad. J. Math., 7 (1955) 414-416.
- [11]
- B. Segre, Introduction to Galois geometries, Atti Accad. Naz. Lincei Mem., 8 (1967) 133-236.
- [12]
- J. F. Voloch, Arcs in projective planes over prime fields, J. Geom., 38 (1990) 198-200.
- Oriol Farràs, Universitat Rovira i Virgili, Catalonia, Spain: "Secret Sharing Schemes and Codes"
- Kwankyu Lee, Chosun University, Korea: "Interpolation-based decoding algorithms of algebraic geometry codes"
- Carlos Munuera, Universidad de Valladolid, Spain: "Steganography and codes"
- Lluís Pàmies, Nanyang Technological University, Singapore: "Coding for Distributed Storage Systems"
- Alfred Wassermann, Universität Bayreuth, Germany: "Random network coding and constant dimension codes" and "Computer construction of error-correcting codes"
- Victor Zinoviev, Russian Academy of Science, Russia: "On Codes and Combinatorial Designs"
Maximum Distance Separable Codes
Simeon Ball (Universitat Politècnica de Catalunya, Spain)Let C be a block code of length n and minimum distance d over an alphabet of size a. Since the minimum distance is d, considering n-d+1 coordinates, any vectors of C differ on these n-d+1 coordinates, thus
This bound is called the Singleton bound for block codes. If the bound is attained and |C|=a^{n-d+1} then the code is called maximum distance separable (MDS).
Let C be a block code of length n and minimum distance d over an alphabet of size a. Since the minimum distance is d, considering n-d+1 coordinates, any vectors of C differ on these n-d+1 coordinates, thus
This bound is called the Singleton bound for block codes. If the bound is attained and |C|=a^{n-d+1} then the code is called maximum distance separable (MDS).
If C is a linear MDS code of dimension k over F_{q}, then |C|=q^{k}=q^{n-d+1} and hence k=n-d+1. The dual code C^{perp} is also MDS and has length n and dimension n-k.
Labeling the elements of F_{q}={ x_{1},x_{2},...,x_{q} }, the Reed-Solomon code
is a linear MDS code of length q+1. If k=3 and q is even then this code can be extended to
of length q+2. The code C^{perp} will be an MDS code of length q+2 and dimension q-1. There are other inequivalent 3-dimensional MDS codes of length q+2 over F_{q}, q even, coming from hyperovals of PG(2,q), see [8] for a survey.
In [5], Bush showed that if k >= q+1 then the longest linear MDS codes are equivalent to
of length k+1.
The MDS conjecture deals with the case k <= q, see [9] for example.
Conjecture A k-dimensional linear MDS code over F_{q}, k <= q, has length at most q+1 unless k=3 or q-1 and q is even, in which case it has length q+2.
This conjecture was recently proved over prime fields. Suppose that q=p^{h}, where p is prime. The following theorem is from [1].
Theorem If k <= p then a linear MDS code over F_{q} has length at most q+1 and the longest linear MDS codes are equivalent to Reed-Solomon codes.
The bound in the previous Theorem was proved for k=3 by Bose [4] in 1947 and the classification as Reed-Solomon codes for k=3 was proved by Segre [10] in 1955. Voloch [12] proved the theorem for k <= p/45+c_{1}, where c_{1} is a constant, in 1990.
Some improvements to the Theorem were made in [2] in the case q is not a prime, specifically the following theorem.
Theorem If q is not prime and k <= 2p-2 then a linear MDS code over F_{q} has length at most q+1.
There is a 4-dimensional linear MDS code over F_{q} of length q+1, q even, that is not equivalent to a Reed Solomon code, see [7], and there is a 5-dimensional linear MDS code over F_{9} of length 10, which is not equivalent to a Reed-Solomon code, see [6].
In this talk I will discuss the proof of the MDS conjecture for prime fields, the known examples of MDS codes of length q+1, how to prove the MDS conjecture for small dimensions using projections and the Blokhuis-Bruen-Thas hypersurface associated to an MDS code [3].
References
Secret Sharing Schemes and Codes
Oriol Farràs (Universitat Rovira i Virgili, Catalonia, Spain)A secret sharing scheme is a method to protect a piece of information or data by dividing it into pieces, which are called shares, in such a way that it can only be recovered from certain subsets of shares. Secret sharing is a very important cryptographic primitive. The ?rst secret sharing schemes were constructed by Shamir and Blakley in 1979. The original motivation for constructing these schemes was to protect keys, and to safeguard information in general. However, secret sharing was soon used for many di?erent cryptographic applications and became a very important primitive in cryptography.
McEliece and Sarwate ('81) and Massey ('93) showed a connection between secret sharing schemes and codes that is very important in secret sharing. This talk is a survey of the results in secret sharing that have been obtained by using coding theory.
Interpolation-based Decoding Algorithms of Algebraic Geometry Codes
Kwankyu Lee (Chosun University, Korea)Goppa was the first to define linear error-correcting codes on algebraic curves. For a divisor G whose support is disjoint from a set of rational points on the curve, divisor D being the sum of those rational points, he defined the evaluation code CL(D,G). The dual of the evaluation codes can be decoded efficiently by the syndrome-based Berlekamp-Massey-Sakata algorithm with the Feng-Rao majority voting.
Then Guruswami and Sudan's list decoding provided a fresh point of view that brought the evaluation codes back to the center. Using interpolation, they showed that evaluation codes can be decoded successfully beyond the capacity of the previous decoding algorithms for the dual codes.
In this lecture, we present interpolation-based decoding algorithms for general evaluation AG codes, including the two-point codes on maximal curves such as Hermitian, Suzuki, and Klein curves. These algorithms are simple to present and streamlined to implement and deploy in practice. Thus they are expected to be useful for the recent code-based cryptography.
Steganography and codes
Carlos Munuera (Universidad de Valladolid, Spain)Steganography is the science of writing hidden messages in such a way that no one, apart from the sender and receiver, can detect the existence of a message. In other words, steganography is the science of invisible communications. It is used when even the fact of communicating has to be kept secret. Steganography became widely known in 2001, when FBI and CIA reported that Ben Laden used it to covertly distribute information to his supporters.
The secret message we want to protect is embedded into an apparently innocuous object, the cover. Covers may be images, texts, private letters, computer files, etc. The most known historical example is invisible ink: here the cover is a handwritten document, a private letter, etc, and the secret message is written in the margin or between the lines. Today's typical cover is a computer file, a document, image, a program or a protocol. Media files are ideal for steganographic purposes because of their large size and redundancy. For this reason modern steganography is referred as Digital Steganography. Digital Steganography is a rapidly developing discipline, to the point that almost 90 % of publications on this field have been written in the ten last years.
In this course, we give an introduction to steganography, conducted from a coding theory point of view. We present the current state of research and discuss some problems arising from this application of coding theory.
Coding for Distributed Storage Systems
Lluís Pàmies (Nanyang Technological University, Singapore)The ability to store the vast amount of data that is continuously being created by both individuals and institutions is a cornerstone of our digital society. Popular web services such as Google, Facebook or Dropbox, or distributed computing infrastructures such as the LHC Grid, rely on large distributed storage systems (DSSs) that allow to scale out and accommodate the ever-growing volume of data to be stored. In these environments, coding techniques have shown to be able to provide with the required data reliability in a more economical and more effective way than previous simple replication mechanisms. However, although different coding aspects have been recently studied in the distributed storage community, such as maximizing the fault-tolerance or reducing the costs of repairing failures, this is still a young research field with many optimization trade-offs to be better understood, and new open challenges to be explored. In these series of lectures we will provide a detailed analysis of the architecture and requirements of today's DSSs, identifying the problems of interest from a coding perspective. We will also survey the existing families of codes tailored-made for networked storage systems, providing the main principles and theoretical details of them, as well as analyzing the practical aspects of their real implementation and deployment. Finally, we will discuss other open problems being currently tackled in the field, such as the data insertion problem, or the encoding of already-replicated data.
Random network coding and constant dimension codes
Alfred Wassermann (Universität Bayreuth, Germany)In packet networks with the internet as its most important example, efficient routing of the information packets is of crucial importance to avoid congestion problems. Network coding, introduced in 2000 by Ahlswede, Cai, Li and Yeung has the potential to revolutionize the traditional approach to packet routing. Instead of simply routing packets, intermediate nodes of the network are allowed to "mix" packets.
In this lectures we will study the basic ideas of network coding. We will follow the work by Koetter and Kschischang (2004) who introduced linear network coding and we will explore the connection to subspace codes. In the language of combinatorics, subspace codes of constant-dimension are designs over vector spaces. This is an active research area with many open questions. Until very recently no non-trivial example of an optimal constant-dimenison code was known. We will use the methods of my first lecture to show how to construct the first examples of optimal subspace codes.
The lecture will cover a basic introduction to network codes, finite fields and designs of vector spaces.
Computer construction of error-correcting codes
Alfred Wassermann (Universität Bayreuth, Germany)Beginning with the early days of algebraic coding theory there was the question for the best possible error-correcting block codes. Here, we are interested in the construction of linear [n,k]-codes over an alphabet with q elements.
These are k-dimensional subspaces of the n-dimensional vector space over the finite field with q elements. The codewords of length n are the elements of the subspace, they are written as row vectors. The weight of a codeword is defined to be the number of nonzero entries of and the minimum distance of a code C is the minimum of all weights of the nonzero codewords in C.
For the purpose of error correcting codes we are interested - for codes with a fixed number of codewords - in codes with highest minimum distance d as these allow the correction of a maximum number of errors. On the other hand we are interested in codes of small length n. High minimum distance and small length are contrary goals for the optimization of codes. So, there are bounds giving upper limits for the minimum distance of a linear code of fixed length n. A linear code C is called optimal if its minimum distance is equal to this known upper bound.
On the other hand, these upper bounds are not always exact, meaning that for many parameters (n,k,q) it is not known whether there exist codes whose minimal distance is equal to the upper bound.
We will see that searching for a linear codes with high minimum distance is equivalent to the search for solutions of - usually huge - systems of linear equations and inequalities. This opens a close connection to integer linear programming.
Since for interesting parameters the size of the incidence problem is much too large to be directly solvable by computer, a promising approach is to restrict the search to linear codes having a prescribed group of automorphisms. This strategy has already been very successful in finding other incidence structures with extremal properties, for example combinatorial designs. These will play an important role in my second lecture about network coding.
In the lecture we will cover the necessary topics from group theory and combinatorics. We will learn how to apply methods from group theory to compute the system of equations and inequalities whose solutions are codes having prescribed parameters and a prescribed group of automorphisms. Computer methods to determine the solutions of the system will be discussed.
On Codes and Combinatorial Designs
Victor Zinoviev (Russian Academy of Science, Russia)We consider several classical examples, when combinatorial designs arise from codes and vice versa codes arise from designs. In particular, we consider: perfect codes and Steiner systems; t-designs and completely regular codes; equidistant codes with maximal distance and resolvable BIB designs; Hadamard matrices and optimal binary codes meeting Plotkin bound. Understanding of the lecture does not need any preliminary knowledge on combinatorial designs and codes.