Coding theory - polynomial

Question

Let $C \in (\mathbb{Z}/5)^3$ be the code consisting of all elements $(x_1,x_2,x_3)$ satisfying $x_1 +3x_2 +2x_3 = 0$

Show that this is a 1-error detecting code. What is the minimal distance of $C$?

Now, as far as I know, there are $5^3 = 125$ possible combinations of $(x_1,x_2,x_3)$, and if I were to write all 125 out, calculate if they satisfy the polynomial and then creat a distance table, I could calculate the minimal distance and error detection.

This is what I know to do, but is there a simpler way?

Answer 1

Observe that:

• The code in question is a linear code (as it is the kernel of a linear map and thus a linear subspace).

• For linear codes the minimal distance is equal to the minimal weight (number of nonzero coordinates) of a nonzero codeword.

• Can you have a codeword with exactly one nonzero coordinate? No (but prove it.)

• Show there are codewords with only two nonzero coordinates.

Then you proved that the minimal distance is two and thus (recall why) it is one-error-detecting.

Answer 2

We can prove 1-error detection as follows. We take $x = (x_1, x_2, x_3) \in C$ and $y = (y_1, y_2, y_3) \in (\mathbb Z / 5)^3$ such that x and y differ in only one coordinate (since we want to prove 1-error detection). Say, we have $x_2 \neq y_2$. Then, from $x_1 + 3 x_2 + 2 x_3 = 0$, we get $y_1 + 3 y_2 + 2 y_3 = (y_1 + 3 y_2 + 2 y_3) - (x_1 + 3 x_2 + 2 x_3) = (y_1 - x_1) + 2 (y_2 - x_2) + 3 (y_3 - x_3) = 2 (y_2 - x_2) \neq 0$ since $y_2 \neq x_2$. So we have shown that if we take a codeword x and change the second coordinate, we don't get another codeword. The cases when we change the first or third coordinate are completely analogous. The important thing is that in the linar equation no coefficient is $0$.

Since we have 1-error detection, the minimal distance can't be $1$. By looking at the codewords $(0,0,0)$ and $(0, 1, 1)$, we see that it's $2$.