ON THE COVERING RADIUS OF REED-MULLER CODES

We present lower and upper bounds on the covering radius of Reed-Muller codes, yielding asymptotical improvements on known results. The lower bound is simply the sphere covering one (not very new). The upper bound is derived from a thorough use of a lemma, the 'essence of Reed-Mullerity'. The idea is to find a 'seed' upper bound-a properly chosen combination of binomial coefficients-well fitted to the respective growths of m (log of length) and r (order), to initiate double induction on m and r. Surprisingly enough, these two simple ingredients suffice to essentially fill the gaps between lower and upper bounds, a result stated in our theorem.