Informations pratiques sur cette ressource

Description de la ressource pédagogique

Description (résumé)

This session will be about the support splitting algorithm. For the q-ary case, there are three different notions of equivalence. The general one: two codes of length n are semi-linear equivalent if they are equal up to a fixed linear map. Each linear map is the composition of a permutation, a scalar multiplication, which could vary for each coordinate, and a field automorphism. But for this session, we consider a more restrictive definition, which coincides with the general case for binary linear code. Two codes are permutation-equivalent if they are equal up to a fixed permutation on the codeword coordinates. Given two linear codes, we have two different problems. First of all, decide whether two given codes are equivalent and on that case retrieve the permutation mapping. In this paper, it has been discussed the difficulty of this problem. They showed that the code equivalence problem is not NP-complete but it is at least as hard as the Graph Isomorphism problem. We have the following known algorithms to solve the Code Equivalence problem. The Support Splitting Algorithm, which solves the permutation equivalence problem in polynomial-time for binary codes.

"Domaine(s)" et indice(s) Dewey

• Analyse numérique (518)
• Théorie de l'information (003.54)
• données dans les systèmes informatiques (005.7)
• cryptographie (652.8)
• Mathématiques (510)

Thème(s)