Does Reed-Muller codes $\mathrm{RM}(r,m)$ exist for $r = 0$ and $m = 0$? Namely, does $\mathrm{RM}(0,0)$ exist? Some books mention that $m$ should be a natural number whereas some books mention that it can be a whole number including $0$, for example Shu Lin and Daniel Costello Error Control Coding book.

  • $\begingroup$ When r and are non zero, also it is said that r can be equal to m. In such a case n = k = 2 raised to m. How can the message length be equal to codeword length? Is it that r should be less than m? k is given as mC0+mC1+.....mCr. And n is given as 2 raised to m. $\endgroup$ – Seetha Rama Raju Sanapala Feb 24 '16 at 10:53

The codewords in a Reed-Muller code of degree $d$ and length $2^n$ are binary vectors of the form $$\big(f(0,0,\ldots, 0, 0), f(0,0, \ldots, 0, 1), f(0,0, \ldots, 1, 0), f(0,0, \ldots, 1, 1), \cdots, f(1,1,\ldots, 1,1) \big)$$ where $f$ is the corresponding binary polynomial of degree at most $d$ in $n$ variables.

Suppose first that $n > 0$. The dimension of the code is $$k = \sum_{i=0}^d \binom{n}{i}\tag{1}$$ If $d=0$, then $k = \binom{n}{0}=1.$ There are only two "polynomials" of degree $0$ in $n$ variables, namely the constants $0$ and $1$, and consequently the codewords of length $2^n$ are $000\cdots 0$ and $111\cdots 1$.

If $n=0$ also, the codewords (if any) are of length $2^0 = 1$. Now, you might want to claim from $(1)$ that $k = \binom{0}{0} = \frac{0!}{0!(0-0)!} = 1$ and so there are $2^k = 2$ codewords (which, of course, are $0$ and $1$). Alternatively, the $k$ in Equation $(1)$ is the total number of subsets of cardinality $d$ or less of a set of $n$ elements. There is exactly one subset (of cardinality $0$) of the set of $0$ elements (namely,the empty set $\emptyset$). and that subset is $\emptyset$ itself. Thus, the Reed-Muller code of order $0$ and length $2^0$ is the $(1,1)$ code consisting of two codewords $0$ and $1$. As a linear code, this is the identity map.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.