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.

Show that every (q+1,M,3 ) code ternary has $M\leq q^{q-1}$ where
q+1 is the lenght of the wordcorde
M is the number of elementes in the Code
3 is the minimum distance of the code

My work up to now. It's clear that $M\leq q^{q+1}$ beacuse of the permutation of q simbols in q+1 vectors. But if the min distance is 3 it's clear that I can chose from q possibilities for the first q-2 positions.
Then I have 3 empty positions in the vector so I can choose from q possiblities and just repeating it 3 times (my decision scheme is going to consider them equal). So it is
$q^{q-2}*q$
Do you think it's correct?

share|improve this question
    
Could you explain what you mean you "can choose from q possiblities and just repeating it 3 times"? There might not be any codewords ending with the same letter three times. –  Colin McQuillan Oct 9 '12 at 15:56
    
A ternary code means that the alphabet has size three. Therefore the number of $(q+1)$-tuples is $3^{q+1}$. May be you meant to write $q$-ary code? –  Jyrki Lahtonen Oct 13 '12 at 11:43

2 Answers 2

up vote 1 down vote accepted

Your construction scheme doesn't give rise to a code with minimum distance three. After all you may have two "early parts" (= the first $q-2$ components) that differ in only one position, and then you fill them in with the same three repeated symbols.

By fixing Colin McQuillan's argument (the subwords of the first $q-1$ symbols must be distinct) we get the upper bound $q^{q-1}$. If $q$ is a power of a prime number, then this upper bound can also be attained by the following construction.

Let $\{0,1,x_3,\ldots,x_q\}$ be a listing of the elements of the finite field of $q$ elements. Then define a code with the following parity check matrix $$ H=\left( \begin{array}{cccccccc} 1&1&1&1&1&\cdots&1&0\\ 0&1&x_3&x_4&x_5&\cdots&x_q&1 \end{array}\right). $$ There are $q+1$ columns in this matrix, so the length of the code is $q+1$. There are two check equations, so the code has dimension $q-1$, and hence $q^{q-1}$ words. Its minimum distance is at least three, because any pair of columns are linearly independent.

share|improve this answer

Warning: as Jyrki Lahtonen points out in the comments, this argument is off by one.

If the code hs minimum distance $3$ then distinct codewords cannot agree on the first $q-2$ letters. The function that takes every codeword to its first $q-2$ letters is therefore an injection from the set of codewords (this set has order $M$) to the set of words of length $q$ (this set has order $q^{q-2}$). So $M\leq q^{q-2}$.

share|improve this answer
    
That's the same things I thinked as first but the statements was asking for $q^{q-1}$ so I'm wondering if it's going to be as I wrote before or just saying that $q\geq1$ and so if $M\leq q^{q-2}\leq q^{q-1}$ –  Laura Oct 9 '12 at 16:21
    
Something wrong here!!!! The length of the words was supposed to be $q+1$, so it is certainly possible that two words agree on the first $q-2$ components (and disagree on the last three). –  Jyrki Lahtonen Oct 13 '12 at 20:02

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.