5
$\begingroup$

Here in Wikipedia is written: "The automorphism group of the binary Golay code is the Mathieu group M23."

What is "automorphism group of code" ?

PS

Are there other nice examples of relation between groups and codes ? E.g. if we take the most simple codes - Hamming codes what are their automorphism groups ?

$\endgroup$
7
  • 4
    $\begingroup$ For a binary code $C$ the automorphism group is just the group of permutations of the coordinates that permute $C$. (For a code of length $n$ over an arbitrary field $k$, it's the stabilizer of $C$ in the semidirect product of $S_n$ with $(k^*)^n$; when $|k|=2$ you don't see the $k^*$ factor.) For the Hamming code of length $7$ this is $GL_3({\bf Z}/2{\bf Z})$; for the extended Hamming code of length $8$, it's affine $GL_3$. This should be thoroughly explained in standard texts such as MacWilliams and Sloane. $\endgroup$ Mar 4, 2012 at 19:23
  • $\begingroup$ I think it is the integral isometry group of an associated lattice. The three books I have in this direction are SPLAG by Conway and Sloane, more introductory Lattices and Codes by Wolfgang Ebeling, also From Error Correcting Codes Through Sphere Packing to Simple Groups by Thomas M. Thompson. I quite like the Ebeling book, see my answers to my own question at mathoverflow.net/questions/69444/… $\endgroup$
    – Will Jagy
    Mar 4, 2012 at 19:31
  • 1
    $\begingroup$ @W.Jagy: Aut$(C)$ is certainly contained in the isometries of the associated lattice (modulo $\lbrace \pm 1 \rbrace^n$), but sometimes there are other automorphisms: $E_7$ and $E_8$ have more isometries than you get from the Hamming and extended Hamming codes. $\endgroup$ Mar 4, 2012 at 19:44
  • $\begingroup$ @Noam, I suspected something might be different, so I just mentioned the books. I've never paid attention to codes...Oh, about use of the @ sign, Gerry Myerson told me on MSE that the first three characters of the other person's on-site name are what matter, as far as them being informed by the software that there is a message and where it is. I'm guessing it is similar on MO. It is hard to tell if I see a message before the usual delay about being informed (the little envelope at the top of the page, next to my name, turns orange). $\endgroup$
    – Will Jagy
    Mar 4, 2012 at 20:04
  • 1
    $\begingroup$ The @user message notification is a SE 2.0 feature which does not work on MO at all. $\endgroup$ Mar 6, 2012 at 17:09

2 Answers 2

6
$\begingroup$

The commenters got it right. The automorphism group of a binary code is the set of permutations of coordinates that stabilizes the code. If instead of using the binary alphabet we use a ternary, quaternary,... alphabet, then there is some variation in that some sources allows signed permutations of coordinates. After all, these are also automorphisms that preserve the Hamming distance (or Lee distance) between a pair of inputs. Whichever way gives you a more interesting group is the way to go!

In addition to the celebrated Golay codes (binary and ternary) some other families of codes have a useful group of automorphisms. I will list the Reed-Muller codes. These codes have length $n=2^m$, and the code $RM(r,m)$ has dimension $$ k=\sum_{i=0}^r{m\choose i}.$$ Their coordinate positions can naturally be put into a bijective correspondence with the vectors $v$ of the $m$-dimensional space $F_2^m$ over the field of two elements in such a way that all the the affine linear transformations $f_{A,u}:v\mapsto Av+u$ for all $A\in GL_m(F_2), u,v\in F_2^m$ become automorphisms of the codes. The Hamming codes belong to the hierarchy of Reed-Muller codes --- the extended Hamming code of length $2^m$ is the code $R(m-2,m)$. It is known (see MacWilliams & Sloane) that this is the full automorphism group of the code $RM(r,m)$, when $r\lt m-1$. The codes $RM(m,m)$ (resp. $RM(m-1,m)$) consists of all the binary words of length $2^m$ (resp. of all the binary words of an even weight), and both these codes are stable under all the permutations of the $2^m$ bit positions.

Also the extended BCH-codes have a useful group of automorphisms. In this case the bit positions can be put into a bijective correspondence between the elements $x$ of the finite field $F=GF(2^m)$. The codes can be defined by means of power sum equations, and it is easy to see that the affine linear mappings $x\mapsto ax+b, a\in F^*, b\in F$ are all automorphisms. Together with Frobenius automorphisms, $x\mapsto x^{2^i}$, those will form the entire group of automorphisms in many a case, but unfortunately I'm not up to speed about exactly when that happens. This is a much smaller group of automorphisms in comparison to that of the Reed-Muller codes. Yet, it is doubly transitive, and many an algebraic proof has been simplified by this fact.

$\endgroup$
2
  • $\begingroup$ @Jyrki Lahtonen Thank you for the answer! May I ask you to clarify. Do you mean that Affine transformations of F_2^m become automorphisms of Reed-Muller ? What parameters (n,k) of RM you mean ? $\endgroup$ Mar 6, 2012 at 11:33
  • $\begingroup$ Sorry about leaving it somewhat sketchy, @Alexander. Does it look clearer now? $\endgroup$ Mar 6, 2012 at 16:36
1
$\begingroup$

Here is a view point from the application side.

A codebook $\mathscr C$ of length $n$ over an alphabet $\Sigma$ is a subset $\mathscr C \subset \Sigma^n$. The automorphism group $\mathrm{Aut}(\mathscr C)$ of a codebook is the subset of permutations on $\{1,2,\dotsc,n\}$ (which acts on $\Sigma^n$) that fix $\mathscr C$.

Code designers prefer codes with more structures; so the alphabet $\Sigma = \mathbb F_q$ is usually taken to be finite fields, especially $\mathbb F_2$; less commonly the alphabet is taken to be a ring, such as $\mathbb Z/4\mathbb Z$. Once the field structure is given, code designers will focus on codebooks (subsets of $\mathbb F_q^n$) that happen to be subspaces of $\mathbb F_q^n$. This is the case for all codes mentioned in this page: Hamming, Golay, Reed--Muller, BCH, and their extended versions are all linear codes. And hence the discussion of automorphisms of codes is commonly limited to those codes who already have a lot of algebraic structures. [1]

IMO, there are several reasons why code designers like to talk about automorphism groups:

  • It is easier to design the decoder if you have a big Aut.

    • Example: The optimal decoder of the first-order Reed--Muller RM$(1, m)$ is basically a majority voting system, where the "voters" are vectors in $\mathbb F_2^m$.
    • Example: Some belief-propagation decoder of polar codes uses the Aut of RM codes (not the Aut of polar codes) to permute the Tanner graph.
  • It is easier to analyze the code performance if its Aut is big enough. Example:

    • Reed--Muller codes achieving capacity over binary erasure channels. The proof uses the fact that the Auts are $2$-transitive.
    • The computation of code invariants, such as weight enumerators and Tutte polynomials, may be 10x or 100x faster if you can "quotient" the computation by the Aut.
  • The general paradigm has that the performance of a code is linked to the size of its Aut.

    • Example: Golay codes are so good and have large Auts.
    • Example: Even for codes that are known to be good for other reasons, people would try to figure out its Aut for the sake of "maybe we can improve this code by making Aut larger".

More on the very last bullet point.

Recently, as polar codes succeed in practice, people start looking at ways to improve polar codes further. It is reported that RM codes perform better (in fact, nearly optimal) if a high-complexity decoder is used. So one promising path is to make polar codes, which usually assume a low-complexity decoder, "more RM" and see what we got. The latest result I am aware of proves that almost-RM codes achieve constant rates over binary symmetric channels. [2002.03317]

Hope that RM can achieve capacity over BSC and confirm the long-standing conjecture.

Footnote

[1] Making the codebook a subspace is good in practice because a cellphone/satellite can simply implement an injective linear map $\mathscr E: \mathbb F_q^k \to \mathbb F_q^n$ to encode messages, where $k$ is the dimension of $\mathscr C$ as a vector space over $\mathbb F_q$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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