Paper 2011/571

Lower Bound on Covering Radius of Reed-Muller Codes in Set of Balanced Functions

Brajesh Kumar Singh and Sugata Gangopadhyay

Abstract

In this paper, we derive a general lower bound on covering radius, $\hat{\rho }(0,2,n)$ of Reed-Muller code $RM(2,n)$ in $R_{0,n}$, set of balanced Boolean functions on $n$ variables where $n=2t+1$, $t$ is an odd prime satisfying one of the following conditions \begin{enumerate} \item[(i)] $or{d}_t(2)=t-1$; \item[(ii)] $$, $$ is odd, and $$. \end{enumerate} Further, it is proved that $$, which is improved upon the bound obtained by Kurosawa et al.'s bound ({\em IEEE Trans. Inform. Theory}, vol. 50, no. 3, pp. 468-475, 2004).