4
$\begingroup$

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.

  • 0
    $\mathbf{Z}_p^p$ would be even better notation for the vector space containing $C$ as a subspace :-)2011-06-22

3 Answers 3

2

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$?

  • 0
    @user10106: A matrix $M$ is nonsingular iff $\det M \neq 0$.2011-04-27
1

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$.

0

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.

b) In your comment to Gerry Myerson's answer, you seem to have answered this yourself.

  • 0
    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.2011-04-27