Encoding information into constant weight words

Nicolas Sendrier

INRIA (projet CODES)


To be presented at ISIT 2005, Adelaide, Australie.


We present here a new algorithm for encoding binary information into words of prescribed length and weight.
Existing solutions use a combinatorial approach and, though they are optimal in terms of information theory,
they have a rather high algorithmic complexity as they require the computation of binomial coefficients. The
solution we propose has linear complexity. The price to pay is variable length encoding and a small loss of
(information theoretic) efficiency.