Finding the permutation between equivalent codes: the support splitting
INRIA, projet CODES
78153 Le Chesnay Cedex, France
IEEE Transactions on Information Theory, 46(4):1193-1203, July
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.
Equivalence, hull, invariant, linear codes, signa-ture, support splitting algorithm, weight enumerator.
The support Splitting Algorithm.
Rapport de recherche RR-3637, INRIA, March 1999.