Sorry Alec, maybe there is a language problem here. I gave you an algorithm which I believe is one way to implement erasure decoding. It is exponential time. I don't have the time right now to look into this further (I have 2 sets of exams to grade this weekend, to prepare lecture notes for Monday morning, on top of all the other stuff I have to do), but if you have the time you can implement my algorithm, or your own if you have a better one and submit a patch. There are a lot of functions missing in the coding theory modules.
On Fri, Apr 16, 2010 at 8:55 PM, Alec Mihailovs <[email protected]> wrote: > On Apr 16, 8:10 pm, David Joyner <[email protected]> wrote: >> Perhaps I don't understand your program, but it appears to not address >> the issue. Here is the algorithm, if I understand the question correctly: >> >> Let I denote the subset of range(n) which represents the erasures. >> Let v denote the vector in GF(q)^n which you want to decode. >> Let C denote the [n,k,d] code with generator matrix G (so the >> rows of G are a basis for the vector space C over GF(q)). >> For each w in GF(q)^n, let w^I denote those coordinates of w not in I. >> Let L = [] be an empty list. >> For each c in C >> if c^I = v^I then append c to L >> return L >> >> This gives you the list of codewords desired. >> >> I don't see how the output of your programs agree with this. > > I may be understanding the problem wrong. Originally I thought that > the problem was as follows (in this example): given a message m in > GF(3)^10, we used matrix G to encode it making a vector w in GF(3)^27. > During a transmission, there were 8 or so errors in known positions > (erasures is the list of these positions in my code). > Assuming that we still can restore the original message m, i.e. if it > is unique, the procedure 'decode' gives it from w and the list of the > positions of erasures, and the procedure 'correct' produces the > correct codeword corresponding to it. > > Maybe, I still don't understand it right, but it seems as if you are > saying, that the problem is to do a similar thing in cases when the > solution is not unique, producing the list of all the solutions. That > can be done similarly, just using the version of solve_left in > 'decode1' producing the list of all solutions (plain solve_left gives > only one solution even if there is more than 1), and then multiplying > each of them by G, as in 'correct', > > If I again understood it wrong, could you, please, give a simple > example (with smaller sizes), with the correct answer? > > Alec > > -- > To post to this group, send email to [email protected] > To unsubscribe from this group, send email to > [email protected] > For more options, visit this group at > http://groups.google.com/group/sage-support > URL: http://www.sagemath.org > -- To post to this group, send email to [email protected] To unsubscribe from this group, send email to [email protected] For more options, visit this group at http://groups.google.com/group/sage-support URL: http://www.sagemath.org
