[Math] How many unique Hamming (7,4,3) Codes are there

abstract-algebracoding-theorycombinatorics

I cannot find an answer to this on Google so I thought I would ask here. By unique I mean "distinct sets of codewords."

By my count, there are $7!$ ways to choose an ordering of message bits and parity bits, but each choice generates a $G$ with $4$ columns that can be reordered to yield $4!$ possible orderings that generate the same exact code. So, my guess is that there are $\frac{7!}{4!} = 7 \times 6 \times 5 = 210$ unique codes. I haven't encountered this number online so I feel like my count is wrong. It also seems unrealistically large, and a stupid guess is that the answer is actually ${{7}\choose{4}}=35$ unique codes – this feels right but I have no idea why I would divide by $3!$.

Edit: A canonical code is defined by the map $\phi$:

$$\phi: \left(\begin{array}{c} x_1 \\ x_2 \\ x_3 \\ x_4\end{array}\right) \mapsto \left(\begin{array}{c} \\ x_1 \\ x_2 \\ x_3 \\ x_4 \\ x_1 + x_2 + x_4 \\ x_1 + x_3 + x_4 \\ x_2 + x_3 + x_4\end{array}\right) $$

This determines the generating matrix $G$:

$$G{\bf x} = \left(\begin{array}{cccc} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 1 & 0 & 1 \\ 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 1\end{array}\right)\left(\begin{array}{c}x_1 \\ x_2 \\ x_3 \\ x_4\end{array}\right)$$

And the codewords are just $GI_4$. Reordering the columns of $G$ is the same as reordering the columns/rows of $I_4$, so each $G$ generates the same codewords as $4!$ total $G$ (including itself).

Best Answer

I interpret the question as follows. It is well known that up to reordering of the bits the $(7,4,3)$ Hamming code is unique. And we want to know how many distinct versions of the Hamming code we can get by such reordering. Two reordered versions of a Hamming code are considered distinct unless they are exactly the same set of binary 7-tuples.

The group of all permutations of the seven bit positions is $S_7$ and it is of size $|S_7|=7!=5040$. This acts transitively on the set $X$ of distinct versions of the Hamming code. By basic properties of group actions we get that $$ |X|=\frac{|S_7|}{|G|}, $$ where $G\le S_7$ is the group of permutations that maps a given version $C$ of the Hamming code to itself, i.e. $G=\operatorname{Stab}_{S_7}(C)$.

It is easy (see below) to see that $G$ is isomorphic to the general linear group $GL_3(\mathbb{F}_2)$. This group has order $|G|=7\cdot6\cdot4=168$. Therefore $$ |X|=\frac{5040}{168}=30. $$


A proof for the structure of the automorphism group of a $(7,4,3)$ Hamming code $C$.

Let $V$ be a 3-dimensional vectorspace over the field of two elements. A version of the Hamming code consists of the characteristic functions of 2-dimensional and affine subspaces of $V$ (together with the all zeros/all ones words), where we puncture away the origin. In other words, we view the words of $C$ as functions from $V^*=V\setminus\{0\}$ to $\mathbb{F}_2$. If $W\subset V$ is a coset of a two-dimensional subspace of $V$, then this gives rise to the function $f_W:V^*\to \mathbb{F}_2$ such that $f_W(x)=1$, if $x\in W$ and $f_W(x)=0$ otherwise.

An automorphism of $C$ is then such a bijection $\pi:V^*\to V^*$ that $f_W\circ\pi$ is a codeword of $C$ for all such subsets $W$. In particular, if $|W|=3$ gives rise to a word of weight three, then $W$ must be a 2-dimensional subspace of $V$ sans the zero vector. So $W=\{x,y,x+y\}$ for some vectors $x,y\in V^*, x\neq y$. Furthermore, any pair $(x,y)$ of distinct non-zero vectors of $V$ gives rise to a word of weight three in this way. Because $f_w\circ\pi^{-1}$ is a word of weight three, its support $\pi(W)$ must consist of three vectors in $V^*$ such that any one of them is the sum of other two. But $\pi(W)=\{\pi(x),\pi(y),\pi(x+y)\}$, so this means that $\pi(x+y)=\pi(x)+\pi(y)$. Therefore $\pi\in GL_3(\mathbb{F}_2)$. OTOH any linear permutation of $V^*$ is an automorphism of $C$ for the same reason. The claim follows from this.