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.

In a section of study of LexiCode this problem comes . Any help and hint appreciated.

Find an ordering of $\mathbf{F}_{2}^5$ so that the greedy algorithm does not produce a linear code

[Edit: Apparently the greedy algorithm is to produce a code of a chosen minimum Hamming distance.]

share|improve this question
    
I don't know what you mean by "the greedy algorithm" in this context. –  Gerry Myerson Dec 6 '13 at 4:38
    
What I mean of greedy algorithm , is to construct a code in which first we have only 0 ( as a vector) , and later add another ( with some kind of condition till the code will be completed. for example in the construction of lexicode we use greedy algorithm . –  henry Dec 6 '13 at 4:48
2  
The greedy algorithm is to always pick the first answer you can, and never change it later if you find it was wrong. I'm guessing you have been asked to construct a code with some properties (what are they?). In this case, the greedy algorithm would be to choose the codewords one by one, choosing for each one the earliest (in some list) that does not spoil the properties of the code. I cannot give a better answer without knowing the properties of the code that the question as asked for. –  apt1002 Dec 6 '13 at 4:49
2  
"with some kind of condition" "until the code is completed" If you don't have a more precise understanding than that of what the greedy algorithm is, I don't think it will be possible to answer your question. –  Gerry Myerson Dec 6 '13 at 4:49
    
Thanks @GerryMyerson for your kind advice. I gave the definition of greedy algorithm based on lexicode ( first time I see greedy algorithm ).and Yes in construction lexicdoe we use greedy algorithm and we have condition to add the next vector to zero vector and we will not stop until the code is complete ( Repeat the algorithm until there are not more vectors in the lexicographic list to look at this is what the book say ). –  henry Dec 6 '13 at 5:19
show 3 more comments

1 Answer

up vote 1 down vote accepted

The only way the question makes any kind of sense is to interpret it in a way that allows us to also decide on an acceptance criterion. Proffering the following:

  • Let the first vector on the ordering be $10000$.
  • Assume that we are greedily constructing a code with minimum Hamming distance two. Meaning that the next word on the list is rejected if and only if it as at Hamming distacne less than two from a previously accepted word.
  • With these assumptions in place the greedy algorithm will never produce a linear code, because ___ (you fill in the blank, or peek at the spoiler)

The word $00000$ will be rejected, when its turn comes. The zero vector belongs to all vector spaces, so a set without it is not a linear subspace.

There are other ways of achieving non-linearity, but the spoilerized way is the most obvious one. For example the famous $(16,256,6)$ Nordstrom-Robinson could be generated as a result of a greedy algorithm. But it is not included in any linear code of minimum distance six, so if the greedy acceptance criterion of insisting on such a high minimum distance is used, the output will not be a linear code.


As all of the above depends on me having correctly guessed what the question really is about (I'm not entirely convinced that the OP understood it the same way), let me illustrate this with a minimal example. This time the greedy algorithm is used to get us a code of length three and minimum Hamming distance two. First consider the lexicographic ordering $$ \begin{array}{c} 000\\001\\010\\011\\100\\101\\110\\111 \end{array} $$ Here the greedy algorithm will first accept $000$, then reject $001$ and $010$ for being too close, accept $011$, then reject $100$ for being too close $000$, accept $101$, accept $110$ and finally reject $111$. Thus we got the code $\{000,011,101,110\}$.

On the other hand with the ordering $$ \begin{array}{c} 100\\001\\010\\011\\000\\101\\110\\111 \end{array} $$ we first accept $100$, then accept $001$ and $010$ for neither is too close to the preceding ones. Then $011$ is rejected for being too close to $001$ and $000$ for being too close to $100$. In the end we still accept $111$, and thus end up with the code $\{100,001,010,111\}$ which is not closed under addition, and not linear.

share|improve this answer
    
Thanks @Jyrki Lathonen for you answer . Let me fill that blank in detail and how I understand your answer :- Because any other vector in the code should be start with 1 (1**** ) and if the code is linear there should be some code start with 0, but because we ( I mean you ) start with the vector 10000 and we have ordering this leads to that no one of the other vector should start with zero. That is vector like 0**** can not be exist inside the code. –  henry Dec 6 '13 at 15:47
    
Not so fast. If the next word on the list would be $01000$ it would not be rejected. After all, it is at a Hamming distance two from the (so far) only included word $10000$. So it is possible that the resulting code has words beginning with a $0$ Try again! Write the 32 words in some order, and follow the greedy algorithm. Observe the code you end up with. Can you tell at a glance that it is not linera? –  Jyrki Lahtonen Dec 6 '13 at 16:11
    
Yes.. This is what I think when I ask my self what happen if we do not take 00000 as the first vector, and later when I choose the other one and adding another vector to the code, It comes to my mind that ZERO vector nowhere could be added , since as you choose 10000 as first chose this vector ( or any other choice of vector with weight 1 ) will not let ZERO to be added to this list. Thanks for your help. –  henry Dec 8 '13 at 5:12
add comment

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.