3
$\begingroup$

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?

  • 0
    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?2012-10-13

2 Answers 2

1

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.

1

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

  • 0
    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).2012-10-13