Jimy Ma's Zone
0%

How Many Different (7, 4) Hamming Codes?

Posted on Edited on In ,

According to Theorem 1.31 in [1], it is easy to construct a (7, 4) Hamming parity check matrix $\mathcal{H}$ by making all columns distinct and nonzero. However, two different parity check matrices may define identical code. For example, consider the two Hamming codes defined by

These two matrices define same Hamming code because

which assert that the null space of $\mathcal{H}_1$ is same as $\mathcal{H}_2$’s. Hence, it is a little tricky to find the quantities of different (7, 4) Hamming codes.

Question

Find the quantities of different (7, 4) Hamming codes.

Solution

lemma 1 : Two parity check matrices $\mathcal{H}_1$ and $\mathcal{H}_2$ define identical (7, 4) Hamming codes iff $\mathcal{H}_2 = \mathcal{T}\mathcal{H}_1$, which $\mathcal{T}$ is a $3 \times 3$ invertible matrices.
Proof : Two matrices have identical null space $\Leftrightarrow$ Two matrices are equivalent $\Leftrightarrow$ Two matrices map to get each other by primary raw-transformation.
Proposition 2 : The order of $GL_3(GF(2))$ is $(2^3-1)\times(2^3-2)\times(2^3-4)$ $=7 \times 6 \times 4.$
Proof : The order of $GL_3(GF(2))$ $\Leftrightarrow$ The count of basis $(q_1,q_2,q_3)$ of $GF(2)^3$, and the possible values of $q_1$, $q_2$ and $q_3$ are $(2^3-1)=7$, $(2^3-2)=6$ and $(2^3$-$2^2)=4$.
Proposition 3: the count of the (7, 4) Hamming codes is 30.
Proof : All the parity check matrices can be mapped by $\phi: S \times \mathcal{H} \rightarrow \mathcal{H}$. $S$ is a seven numbers permutation group. $\mathcal{H}$ is an arbitrary parity check matrix. All the parity check matrices which define identical Hamming codes can be mapped by $\tau:GL_3(GF(2))$ $\times\mathcal{H} \rightarrow \mathcal{H}$. And $GL_3(GF(2))$ is a subgroup of $S$. So there are $|S|/|GL_3(GF(2))|$ $=30$ cosets of $GL_3(GF(2))$. All matrix in the same coset define identical Hamming codes. And matrices in different cosets difine different Hamming codes.

Simulation

We can get all 30 Hamming code word sets by simulation. The following list them by decimal:

1st 2nd 3rd 4th 5th 6th 7th 8th 9th 10th 11th 12th 13th 14th 15th 16th
0 7 25 30 42 45 51 52 75 76 82 85 97 102 120 127
0 7 25 30 43 44 50 53 74 77 83 84 97 102 120 127
0 7 26 29 41 46 51 52 75 76 81 86 98 101 120 127
0 7 26 29 43 44 49 54 73 78 83 84 98 101 120 127
0 7 27 28 41 46 50 53 74 77 81 86 99 100 120 127
0 7 27 28 42 45 49 54 73 78 82 85 99 100 120 127
0 11 21 30 38 45 51 56 71 76 82 89 97 106 116 127
0 11 21 30 39 44 50 57 70 77 83 88 97 106 116 127
0 11 22 29 37 46 51 56 71 76 81 90 98 105 116 127
0 11 22 29 39 44 49 58 69 78 83 88 98 105 116 127
0 11 23 28 37 46 50 57 70 77 81 90 99 104 116 127
0 11 23 28 38 45 49 58 69 78 82 89 99 104 116 127
0 13 19 30 38 43 53 56 71 74 84 89 97 108 114 127
0 13 19 30 39 42 52 57 70 75 85 88 97 108 114 127
0 13 22 27 35 46 53 56 71 74 81 92 100 105 114 127
0 13 22 27 39 42 49 60 67 78 85 88 100 105 114 127
0 13 23 26 35 46 52 57 70 75 81 92 101 104 114 127
0 13 23 26 38 43 49 60 67 78 84 89 101 104 114 127
0 14 19 29 37 43 54 56 71 73 84 90 98 108 113 127
0 14 19 29 39 41 52 58 69 75 86 88 98 108 113 127
0 14 21 27 35 45 54 56 71 73 82 92 100 106 113 127
0 14 21 27 39 41 50 60 67 77 86 88 100 106 113 127
0 14 23 25 35 45 52 58 69 75 82 92 102 104 113 127
0 14 23 25 37 43 50 60 67 77 84 90 102 104 113 127
0 15 19 28 37 42 54 57 70 73 85 90 99 108 112 127
0 15 19 28 38 41 53 58 69 74 86 89 99 108 112 127
0 15 21 26 35 44 54 57 70 73 83 92 101 106 112 127
0 15 21 26 38 41 51 60 67 76 86 89 101 106 112 127
0 15 22 25 35 44 53 58 69 74 83 92 102 105 112 127
0 15 22 25 37 42 51 60 67 76 85 90 102 105 112 127
  1. 1.Elwyn R. Berlekamp (2014), Algebraic Coding Theory, World Scientific Publishing (revised edition), ISBN 978-9-81463-589-9. ↩