Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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

3 Answers 3

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

share|improve this answer
    
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$.

share|improve this answer

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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.