Let $F$ be the field with two elements, $V\_m=F^{2^m}$.Let $R(r, m)\subset V\_m$ be the 
binary Reed-Muller Code. Define $R\_m:=R(1, m)$. Then the dimension of $R\_m$ is 
$1+m$ and its minimal distance is $d(R\_m)=2^{m-1}$. (Cf. for example the book of Luetkebohmert). Hence the information rate is $I(R\_m)=\frac{1+m}{2^m}$ while the relative
minimal distance of $R\_m$ is $rd(R\_m)=\frac{1}{2}$.


Now $R\_5$ has the same relative minimal distance as $R\_4$ (and thus should have approximately the same error correction abilities), while the information rate of $R\_4$ is much better ($I(R\_4)\approx 0.31$ while $I(R\_5)\approx 0.19$).


I furthermore read in Luetkebohmert (and elsewhere) that $R\_5$ was used in practice, e.g. during a Mariner space shuttle mission.


Question: Given the values above, why would anybody use $R\_5$ and not $R\_4$?


(I hope this question is not too easy for MO, but I do not see the answer at the moment.)


Edit: It seems that the code $R\_5$ might have been used for Mariner, because then one has really one code word per pixel of the image. (Compare the comments)


Still let me note that the $R\_m$ all have the same relative minimal distance, that there
exists an efficient (poly time?) algorithm to decode them, and that 
$I(R\_m)$ tends rapidly to zero when $n\to\infty$. And I find this a bit strange: For an "interesting" or even "celebrated" family of codes $(C\_m)\_m$, which all have the same relative minimal distance, I would naively have expected something like $(I(C\_m))\_m$ should be a decreasing (but bounded or even converging) sequence. 



Reed-Muller-Codes
A thing to remember is that the customer is interested in the probability of correct reception after the error-correcting-code has done its magic.


The 5-dimensional Reed-Muller code of length 16 and minimum Hamming distance 8 is capable of correcting 3 errorneous bits. The 6-dimensional Reed-Muller code of length 32 and minimum Hamming distance 16 is capable of correcting 7 errorneous bits. Let us assume a very simplistic model in which all the bits are received errorneously at the same probability $p\in(0,1)$, independently from each other. The probability of correctly decoding a received word of $R(4,1)$ is thus


$$P\_4(p)=\sum\_{i=0}^3{16\choose i}p^i(1-p)^{16-i},$$


and the same probability with the code $R(5,1)$ is


$$P\_5(p)=\sum\_{i=0}^7{32\choose i}p^i(1-p)^{32-i}.$$


Unless I made mistake, we have $P\_5(p)>P\_4(p)$ for most small values of $p$.
For example, $P\_5(0.1)=0.9883$ and $P\_4(0.1)=0.9316$. And at $p=0.01$ we have
$1-P\_5(0.01)=8.5\cdot10^{-10}$ and $1-P\_4(0.01)=1.7\cdot10^{-5}$.


So when transmitting an image of 1000 x 1000 pixels at $p=0.01$, we expect to receive an image free of errors, when using $R(5,1)$, but expect a few dozen garbled pixels, when using $R(4,1)$. Furthermore, to correctly receive 5 pixels worth of image data, we need to correctly receive 5 blocks of $R(5,1)$ instead of 6 blocks of $R(4,1)$. In other words, in terms of payload the fair comparison should be made between $P\_4(p)^6$ and $P\_5(p)^5$.


Above I assumed a decoding logic decoding up to the guaranteed error-correction probability only. One might attempt a more complicated receiver (using soft input) doing full soft decision decoding (which in this case amounts to a simple Walsh-Hadamard transformation). I don't know whether that would change the verdict, though.


**Moral:** long codes often work better. The reason is that in a short block the number of errorneous bits has a higher (relative) variance, and thus it is easier for the number of errors to exceed the error-correcting-capability of the code. Or yet in other words, a short code with the same relative Hamming distance will run into problems handling a burst of errors.


But the question of the code rate is not without merit either!!! In the Mariner application it would have meant that it takes a longer time to transmit a single image using $R(5,1)$ than it would with $R(4,1)$. The eager astronomers can wait a bit longer to get the image, but a serious concern is that the probe uses a fixed amount of battery power per transmitted bit. This would also need to be taken into account, so my figures are not fair to the shorter code. In terrestrial communication systems we carry out extensive simulations before we choose one coding scheme over another, and plot the probability of an error vs. energy per transmitted bit. With Mariner, we could try and estimate the relation between $p$ and energy consumption per bit, but I don't have the time to get into that.




---


Trying to add a more meaningful comparison. Let's have Mariner transmit 5 pixels worth of bits. Using $R(5,1)$ it needs to transmit a total of $5\cdot32=160$ bits as opposed to $6\cdot 16=96$ bits required when using $R(4,1)$. Therefore, for a fair comparison, Mariner can spend $160/96=5/3$ times as much power per bit when using $R(4,1)$. So we can assume that using $R(5,1)$ Mariner transmits a real number $+1$ or $-1$ according to whether a bit zero or one is intended. Then using $R(4,1)$ it can transmit $\pm\sqrt{5/3}$ for the same total power consumption. The receiver interprets a positive received number as the bit zero and a negative as the bit one.


Assume that noise has deviation $\sigma=0.5$. With $R(5,1)$ we then get a bit error, when noise exceeds $+2\sigma$, so this happens with probability $p\_5=1-\Phi(2.0)=0.0228$. The corresponding bit error probability when using $R(4,1)$ is then $p\_4=1-\Phi(2.0\sqrt{5/3})=1-\Phi(2.58)=0.0049$, because this time we need $\sqrt{5/3}$ times as much noise
as earlier to receive a bit incorrectly. The test is then to compare
$$
1-P\_5(0.0228)^5=2.35\cdot10^{-6}
$$
to
$$
1-P\_4(0.0049)^6=6.01\cdot10^{-6}.
$$
We see that we do have a better chance of correctly receiving 5 pixels worth of data using the longer code, but the difference is not nearly as dramatic as the earlier figures, disregarding the energy consumption, would have indicated. 


