4
$\begingroup$

Suppose I have a list of generator matrices $G_i$, $i=1,\ldots N$, of the same size (each defines an $n$-bit linear binary code encoding $k$ logical bits).

I consider two codes to be equivalent if they contain the same codewords, or if they differ by permutation of the physical bits. This means that, if $G'$ is a generator matrix obtained from $G$ by permutation of columns, or elementary row operations (adding and subtracting rows), then $G'$ defines a code equivalent to the code defined by $G$. I believe this is the standard notion of equivalence.

I want to prune my list of generator matrices to contain only inequivalent codes. One way to partially prune is to put each matrix in reduced row echelon form, and then just delete duplicates, but that doesn't take into account column swaps. Is there a simple way to also take into account column swaps?

If the best solution is exponential time, that is also OK, but I'd like to know what it is.

$\endgroup$
  • 1
    $\begingroup$ I would have thought that the (or at least a) standard notion of equivalence is that the code subspaces are the same. In this case you could just combine pairs of matrices and compute ranks, and compare to the ranks of individual matrices. $\endgroup$ – Steve Huntsman Jan 8 at 13:44
  • $\begingroup$ Can you clarify what you mean? $\endgroup$ – guest17 Jan 14 at 9:38
2
$\begingroup$

There is a nice overview of this problem in the beginning of the following paper by Sendrier and Simos which is a good place to start.

Essentially the problem is harder than Graph Isomporphism (see p.5 of linked paper). The following is a quote.

Due to its relation to Graph Isomorphism, some researchers have tried to solve the Permutation Code Equivalence problem by interpreting graph isomorphism algorithms to codes. This approach, was followed in [5] using the fact that ELC orbits of a bipartite graph correspond to equivalence classes of binary linear codes. Mapping codes to graphs and using the software Nauty by B. D. McKay has been used in [19], for binary, ternary and quaternary codes where the permutation, linear and semi-linear equivalence was considered, respectively

References cited above:

  1. Danielsen, L.E., Parker, M.G.: Edge local complementation and equivalence of binary linear codes. Designs Codes Cryptography: 49, 161–170 (2008)

  2. Ostergard, P.R.J.: Classifying subspaces of hamming spaces. Designs Codes Cryptography: 27, 297–305 (2002)

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.