Easy way to get all vectors of hamming weight less than t?

[David Lucas]

Hello,

I implemented a first version of a real syndrome decoder.

But it's quite slow for now as I naively did the following to build the syndrome lookup table for a given error bound t:

• take a iterator over the ambient space of the code
• iterate through all the vectors of the ambient space
• compute and store syndrome of the vector only if its hamming weight is less than t

As you see, it's really slow as it builds a lot of useless vectors.

Do you know if there's a simple Sage way to build all vectors of a given length with hamming weight less than t?

I can do it myself of course, but I feel like it should be something like that in Sage, though I wasn't able to find one...

[Johan Rosenkilde]

Subsets can give you all subsets of a given cardinality t of some set. That could represent error positions. It's easy to generate possible error values and then place them at the positions. On the outer level you of course need an iterator through the number of errors (up to t).

[Johan Rosenkilde]

I would be surprised if the exact function you want is already implemented, though. Possibly when the field is F2, but otherwise, probably not.

[David Lucas]

Thanks!

I'll be working on it.

[David Lucas]

Solved