Finding the permutation between equivalent codes: the support splitting algorithm.

Nicolas Sendrier
INRIA, projet CODES
BP 105
78153 Le Chesnay Cedex, France
Nicolas.Sendrier@inria.fr

IEEE Transactions on Information Theory, 46(4):1193-1203, July 2000. Regular paper.

Abstract

Two linear codes are permutation-equivalent if they are equal up to a fixed permutation on the codeword coordinates. We present here an algorithm able to compute this permutation. It operates by determining a set of properties invariant by permutation, one for each coordinate, called a signature. If this signature is fully discriminant i.e., different for all coordinates the support of the code splits into singletons, and the same signature computed for any permutation-equivalent code will allow the reconstruction of the permutation. A procedure is described to obtain a fully discriminant signature for most linear codes. The total complexity of the support splitting algorithm is polynomial in the length of the code and exponential in the dimension of its hull, i.e., the intersection of the code with its dual.

Keywords

Equivalence, hull, invariant, linear codes, signa-ture, support splitting algorithm, weight enumerator.

See also
N. Sendrier. The support Splitting Algorithm. Rapport de recherche RR-3637, INRIA, March 1999.