Parameters of subfield subcode of Hamming code

Question

I have Hamming code $Ham(3,4)$ which is $[21,18,3]$ code. What are the parameters for $Ham(3,4)\mid_{F_2}=Ham(3,4)\cap F_2^{21}$?

Answer 1

I assume that $Ham(3,4)$ means the linear code with alphabet $\Bbb{F}_4$ with a check matrix having as columns some maximal set of $21$ pairwise linearly independent vectors of $\Bbb{F}_4^3$ (points of a projective plane over $\Bbb{F}_4$ if you like). Otherwise I cannot make sense out of the question.

Even so, the answer may to some extent depend on the choice of particular set of $21$ columns. I only consider the following. Let $\beta\in\Bbb{F}_{64}$ be a fixed primitive root of unity of order $21$. One exists, because $21\mid (64-1)$. Define $Ham(3,4)$ as the $\Bbb{F}_4$-linear code determined by the check matrix $$ H=(1,\beta,\beta^2,\ldots,\beta^{20}). $$ This has the benefit of turning the resulting code into a cyclic one, and we do the familiar business of viewing codewords as (cosets of) polynomials in the ring $\Bbb{F}_4[x]/\langle x^{21}-1\rangle$. Then we easily see the following facts (leaving the details to you):

• The codewords of $Ham(3,4)$ are polynomials $p(x)\in\Bbb{F}_4[x]$ of degree at most $20$ such that $p(\beta)=0$.
• The code $Ham(3,4)$ is the cyclic code with a cubic generator polynomial $g(x)$ that is the minimal polynomial of $\beta$ over $\Bbb{F}_4$.
• This implies that the subfield subcode consists of those polynomial $p(x)\in\Bbb{F}_2[x]$ of degree at most $20$ such that $p(\beta)=0$.
• Therefore the subfield subcode is generated by the minimal polynomial $m(x)$ of $\beta$ over $\Bbb{F}_2$.
• The minimal polynomial $m(x)$ of $\beta$ over the prime field $\Bbb{F}_2$ has degree six, so the subfield subcode has rank $21-6=15$.
• $\beta^7$ is a primitive third root of unity, so $1+\beta^7+(\beta^7)^2=0$. Therefore $p(x)=1+x^7+x^{14}$ is a weight three word of the subfield subcode. Because $Ham(3,4)$ has minimium distance three, the subfield subcode cannot have non-zero words of weight $<3$

When constructed this way the subfield subcode is a binary $[21,15,3]$-code.

---

I am not sufficiently familiar with this business of subfield subcodes to be able to tell right away, whether you always get a $[21,15,3]$ code no matter how you select the $21$ columns of $H$. It would be my guess that this is the case though. After all, a single check equation over $\Bbb{F}_4$ amounts to two check equations over ${}{}{}{}\Bbb{F}_2$. However, it may be possible to select $H$ in such a way that there will be no words of weight three in the subfield subcode. Not sure whether the resulting code should then be called an alternant code or something else.

Answer 2

This is not an answer but rather an extended comment on the last part of @JyrkiLahtonen's answer.

The columns of the parity check matrix of an arbitrary (not necessarily cyclic) Hamming code with redundancy $3$ over $\mathbb F_4$ are $21$ nonzero $3$-tuples over $\mathbb F_4$ with the property that no column is a scalar multiple of another column. In fact, one method of choosing the columns is to start with the set $S_{63}$ of $63$ nonzero $3$-tuples, pick one for the first column and delete its two scalar multiples from $S_{63}$ leaving a set $S_{60}$ of $60$ nonzero $3$-tuples; pick a $3$-tuple from $S_{60}$ as the second column and delete its two scalar multiples from $S_{60}$ leaving $S_{57}$; $\ldots$ and so on, till we have chosen $21$ columns. This gives an arbitrary linear $[21,18,3]_4$ Hamming code.

Jyrki wonders whether the subfield subcode of every linear $[21,18,3]_4$ Hamming code is necessarily a $[21,15,3]_2$ code (as happens with the cyclic Hamming code). Might the subfield subcode be a $[21,15,4]_2$ code for some noncyclic $[21,18,3]_4$ code? An alternative speculation is: Might the subfield subcode be a $[21,16,3]_2$ code in for some noncyclic $[21,18,3]_4$ code? Note that shortening a $[31,26,3]_2$ Hamming code results in a $[21,16,3]_2$ single-error-correcting code, that is, a $[21,16,3]_2$ code is not a figment of the imagination whose existence is prohibited by some bound or the other. Similarly, a $[21,15,4]_2$ code can be produced by shortening the extended $[32,26,4]_2$ Hamming code. The question is: are binary codes with these parameters obtainable as subfield subcodes of some suitably chosen $[21,18,3]_4$ code? Like Jyrki, I have no ready answer.