Permutation decoding of linear error-correcting codes


Title:  Permutation decoding of linear error-correcting codes

Speaker:  Nicola Pace (DIT)

Date:  Monday, 11th April 2016

Time:  4pm

Location:  Agriculture. 1.01 (Seminar Room).


Abstract:

Linear error-correcting codes with large automorphism groups are of interest from different points of view. Geometrically, they correspond to sets of points in a projective space with many symmetries. From a coding theory point of view, a large automorphism group can reduce the number of computations needed for encoding and decoding. In 1964, MacWilliams developed a method, called permutation decoding, that is feasible when a sufficiently large automorphism group ensures the existence of a set of automorphisms—called a PD-set—with specific properties.

Let C be a linear code and G be its automorphism group. There are two main problems:

1) Determine whether G admits a PD-set.

2) If G admits a PD-set, construct a PD-set of smallest possible size.

Problems (1) and (2) were studied for very particular classes of codes, such as linear codes from strongly regular graphs. However, not much is known for the general case and no efficient computational algorithms are known.

In this talk, we consider linear codes with a prescribed automorphism group and use these examples to illustrate some computational approach to problems (1) and (2). This talk is based on a joint work with A. Sonnino.

 

Series: Algebra