how to relate hamming distance of linear and additive codes

Question

Given a $k \times n$ matrix $G$ over a finite field, you can use this to define two codes :

linear code $C_L$ : closure of rows of $G$ under addition and multiplication by field scalars

additive code $C_A$ : closure under addition only.

For binary codes, the two coincide so $C_A=C_L$. For other fields they could be different. I can calculate the minimum distance $d(C_L)$ using GAP + GUAVA, but I need $d(C_A)$. It doesn't look like additive codes are supported by GUAVA so I'm hoping there's a way to manipulate things to get $d(C_A)$...alternatively I'm open to using other packages if they can handle this case. The field I'm interested in is $GF(4)$.

Answer 1

Supplementing Dilip's fine answer with the following variant that resolves the problem that the natural mapping $GF(2^m)\to GF(2)^m$ will necessarily distort the Hamming weights somewhat in that a non-zero element of $GF(2^m)$ can have any number between $1$ and $m$ non-zero coordinates. The trick I describe is specific to $GF(4)$. Something similar can be cooked for other extension fields, but they are more complicated.

The idea is that instead of using coordinates with respect to a chosen basis, we replace elements of $GF(4)$ with words of a short binary linear code with the property that its non-zero words all have the same weight. There is a 2-dimensional such code of length three, namely the even weight subcode of $GF(2)^3$. Using it we map the elements of $GF(4)=\{0,1,a,a^2=a+1\}$ as follows: $$ \begin{aligned} 0&\mapsto 000,\\ 1&\mapsto 110,\\ a&\mapsto 101,\\ a^2&\mapsto 011. \end{aligned} $$ Call this mapping $\phi$. Because $a^2=a+1$ and modulo two $110+101=011$, we see that $\phi$ is a homomorphism of additive groups. It naturally extends to an additive homomorphism from $\phi:GF(4)^n\to GF(2)^{3n}$. Therefore the image of an additive code will be additive, i.e. binary linear. Furthermore, for any codeword $x\in GF(4)^n$ we see that the binary (resp- 4-ary) Hamming weights of $x$ and its image $\phi(x)\in GF(2)^{3n}$ satisfy the relation $$ w_{2}(\phi(x))=2\cdot w_{4}(x).\tag{1} $$

For example the word $(1,a,a^2,1,a,a^2)\in GF(4)^6$ of weight six gets replaced with the bit string $110\,101\,011\,110\,101\,011$ of weight twelve.

It stands to reason that GAP/GUAVA can easily calculate the weight enumerator of the image of any additive code over $GF(4)$. Equation $(1)$ then tells us that we get the 4-ary weight enumerator of the original code simply by halving all the weights.

The key is that if an additive code $C\subset GF(4)^n$ is generated by words $x_1,x_2,\ldots,x_k$, then the binary words $\phi(x_j), j=1,2,\ldots,k$, generate $\phi(C)$ as a binary linear code. So for the purposes of implementing this idea it probably suffices to implement $\phi$ on the vectors over $GF(4)$.

---

A few caveats that occured to me:

• The length of code is tripled instead of doubled as in Dilip's suggestion. Because the number of codewords is not changed ($\phi$ is 1-1), this is probably not a major problem, but what do I know.
• If we use a bigger field, we need something more complicated. For example with $GF(8)$ we could similarly map all the elements to 7-tuples of bits in such a way that the non-zero elements get replaced with a bit string of weight four. Simply use the words of the $[7,3,4]$ simplex code (= even weight subcode of the binary $[7,4,3]$ Hamming code). The length gets multiplied by seven and the weight by four. These numbers will grow quickly, if you move to bigger fields.
• Using $\phi$ preserves the additive structure, and affects the Hamming weights in a predictable way, but it will destroy a few other constructs like taking the dual code. It should be possible to describe a procedure of relating the properties of the $\phi$-images of a given code $C$ and its dual $C^\perp$, but I don't have the time to think about it now.

Answer 2

The characteristic of a finite field $\mathbb F$ is a prime $p$, and so $\mathbb F = \mathbb F_{p^m}$ for some positive integer $m$. One representation of the elements of $\mathbb F_{p^m}$ is as $m$-tuples or $m$-dimensional vectors over $\mathbb F_p$. So, if we have a $k\times n$ generator matrix over $\mathbb F_{p^m}$ with rows $\mathbf u_1, \mathbf u_2, \ldots, \mathbf u_k$, the codewords in the linear code $C_L$ are all row vectors of the form $$a_1\mathbf u_1 + a_2 \mathbf u_2 + \cdots + a_k \mathbf u_k, ~ a_i \in \mathbb F_{p^m}$$ while the codewords of the additive code $C_A$ are all row vectors of the form $$b_1\mathbf u_1 +b_2 \mathbf u_2 + \cdots + b_k \mathbf u_k, ~ b_i \in \mathbb F_{p}.$$ Since $\mathbb F_{p} \subset \mathbb F_{p^m}$ (in fact a subfield if $m >1$), we get that $C_A \subset C_L$. $C_A$ is not a linear code over $F_{p^m}$ (except when $m=1$) but is a linear code over $\mathbb F_p$. That is, expressing each entry in the $k$-dimensional row vectors $\mathbf u_1, \mathbf u_2, \ldots, \mathbf u_k$ over $\mathbb F_{p^m}$ as a $m$-dimensional row vector, the $k\times n$ generator matrix over $\mathbb F_{p^m}$ is transformed into a $k \times mn$ generator matrix over $\mathbb F_p$ and $C_A$ is a linear code over $\mathbb F_p$ with this generator matrix.

I know very little about GAP and GUAVA but presumably these can work with the $k \times mn$ generator matrix created above to find the minimum distance etc.