## 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.