# Codes: Distance, number of codewords, etc

Let $p\geq 3$ be any prime and consider the code $C = N(H)\subseteq\mathbb{Z}_p^2$, where $H = \begin{pmatrix} 1 & 1 & 1 & \dots & 1 & 1 \\ 0 & 1 & 2 & \dots & p-2 & p-1 \end{pmatrix}\in \mathbb{Z}_p^{2\times p}$.

a) How many codewords does the code $C$ contain? I've got an idea on this part. It should just be $p^2$, shouldn't it?

b) Show that every selection of two distinct columns of $H$ results in a non-singular 2x2 matrix.

c) Find a codeword in $C$ of weight 3 and use (b) to conclude that the code $C$ has distance 3.

Parts b and c I have no clue on where to start. I'm sure that I could probably reason my way through c if I could figure out b, since finding the codeword of weight 3 should be trivial. However, I'm willing to take any assistance on this problem.

-
What's $N(H)$? Is it the nullspace of $H$? If so, shouldn't it be in ${\bf Z}_2^p$, not ${\bf Z}_2^2$? –  Gerry Myerson Apr 27 '11 at 1:46
Yes, it should. My apologies. –  user10106 Apr 27 '11 at 2:17
$\mathbf{Z}_p^p$ would be even better notation for the vector space containing $C$ as a subspace :-) –  Jyrki Lahtonen Jun 22 '11 at 5:54

For part b, what does a selection of two distinct columns look like? What's the condition for a matrix to be non-singular?

For part c, can't you find a vector $v=(a,b,c,0,\dots,0)$ such that $Hv=0$?

-
The selection of two distinct columns would be a 2x2 matrix, and to be non-singular would mean that it has an inverse. But I'm not entirely sure what to do with this information. Would picking a matrix like $\begin{pmatrix} 1 & 1 \\ x & x + n \end{pmatrix}$ be the place to start? The determinant is clearly nonzero, which should imply linear dependence (and also rules out a code distance of 2), but is that helpful in any other way? –  user10106 Apr 27 '11 at 2:07
@user10106: A matrix $M$ is nonsingular iff $\det M \neq 0$. –  Brandon Carter Apr 27 '11 at 2:17

A row vector $C$ is a codeword in a linear code if $HC^T = 0$ where $H$ is the parity check matrix of the code. If this codeword has Hamming weight $w$, then the corresponding $w$ columns of $H$ are linearly dependent vectors. Thus, if all sets of $1$, $2, \ldots, d-1$ columns of $H$ are sets of linearly independent vectors, then no vector of Hamming weight $1$, $2, \ldots, d-1$ can be a codeword, and hence the minimum weight (and minimum distance) of the code is at least $d$. For the OP's question,

• no column of $H$ is the all-zero column
• every set of $2$ different columns of $H$ constitutes a $2\times 2$ nonsingular matrix and so no pair of columns is linearly dependent

Therefore, the minimum weight is at least $3$. But since there exists a codeword of weight $3$, the minimum weight (and minimum distance) is exactly $3$.

-
In coding theory terminology,The matrix $H$ is called the parity check matrix. If the code takes $k$ data symbols and produces $n$ coded symbols, the rate of the code is $\frac{k}{n}$ and the parity check matrix will be of size $(n-k) \times n$.
a) In your case, $n-k = 2$ and $n=p$. Therefore, $k = p-2$ which means that the code C has $p^{p-2}$ codewords.
Another way to approach a): the code is a nullspace; the dimension of the nullspace plus the rank of the matrix is the number of columns of the matrix; and you know the number of elements in a vector space of dimension $d$ over the field of $p$ elements. –  Gerry Myerson Apr 27 '11 at 5:09