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)] $ord_t(2) = t - 1$; \item[(ii)] $t=2s + 1$, $s$ is odd, and $ord_t(2) = s$. \end{enumerate} Further, it is proved that $\hat{\rho}(0, 2, 11) \geq 806$, 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).