Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
Maybe it was the dual of $R_5$? –  Noam D. Elkies May 14 '12 at 18:33
    
Perhaps I am missing something, but what do you do if you need to encode 64 and not 32 'things'? (BTW, this was actually the case for Mariner). –  quid May 14 '12 at 19:10
    
I think quid's comment is correct, i.e. the choice of code was governed by the number of messages to be encoded. Another reason for using Reed--Muller codes was that they could be efficiently encoded and decoded using the Fast Fourier Transform: see van Lint's survey article alexandria.tue.nl/repository/freearticles/593591.pdf. –  Mark Wildon May 14 '12 at 19:30
    
@quid: As far as I understand, every pixel was a number in 0 ... 63, and thus required six bit to store, which fits well with the fact that the dimension of $R_5$ is $6$. So it seems to be one code word per pixel. I am now wondering whether this is the only (simple) reason. On the other hand, if use some other binary code, can always subdivide the (long) bit stream appropriately, so it still sounds strange to me... –  Sebastian Petersen May 14 '12 at 19:31
3  
@Sebastian Petersen: The Reed--Muller codes $R_m$ meet one of the Plotkin bounds, so are the largest binary binary codes of their length and minimum distance. So, in the Hamming setup of hard nearest neighbour decoding, they are an optimal choice for sending one of $2^{m+1}$ messages over a channel where the probability of any single bit getting corrupted is (a bit less than) $1/4$. However they don't achieve the channel capacity, and they're not asymptotically good. (Indeed, as far as I know, there are no explicit examples of asymptotically good binary codes.) Hope this is some use. –  Mark Wildon May 14 '12 at 20:11
show 6 more comments

2 Answers 2

up vote 8 down vote accepted

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 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 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,19$ is then $p_4=1-\Phi(2.0\sqrt{5/3})=1-\Phi(2.58)=0.0049$, because this time we $\sqrt{5/3}$ times as much noise as earlier. 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.

share|improve this answer
    
Thanks a lot for the detailed answer! –  Sebastian Petersen Jun 4 '12 at 9:05
add comment

This began as a comment on the comments by @Chris and @Jyrki but posted as an answer because I don't have sufficient reputation on this site.

The standard decoding algorithm for Reed-Muller codes uses majority-logic decoding which in turn requires hard-decision demodulation. That is, the input to the decoder is a $32$-bit vector that is obtained from a demodulator a device that processes $\mathbf x$, a vector of $32$ real numbers, to produce a $32$-bit sequence. However, for first-order Reed-Muller codes, it is possible to use soft-decision demodulation and decoding in Euclidean space, that is, the decoder finds the (binary) codeword that is closest in the Euclidean metric to $\mathbf x$. This is because the $64$ codewords of $R_5$, regarded as vectors in $\{+1, -1\}^n$ (instead of $\{0, 1\}^n$) are just the rows of a $32\times 32$ Hadamard matrix $H$ (or the negatives of the rows). All that needs to be done is to compute $\mathbf y = \mathbf x H$. The location of the entry with the largest magnitude in $\mathbf y$ together with the sign of the entry, tells us which of the $64$ codewords is the nearest in Euclidean distance to $\mathbf x$. If the codewords are arranged so that $H$ is in Sylvester form, then a fast Hadamard transform algorithm (very similar to a Fast Fourier Transform algorithm) can be used to compute $\mathbf x H$ using $160 = 32\log_2 32$ additions ans subtractions. In fact, this form of the computation was used in the Mariner program; the machine devised to carry out the calculations was referred to as the Green Machine.

An article describing many of the details of the coding for the Mariner missions can be found in a conference proceedings published by Wiley under the title Error-Correcting Codes, H. B. Mann (ed.), 1969. Some details, and a diagram of part of the Green Machine can be found in Chapter 14 of MacWilliams and Sloane's The Theory of Error-Correcting Codes, North-Holland, 1978. I am sure that Jyrki has the latter on his bookshelf.

share|improve this answer
    
+1 For the historical account alone! I didn't know that soft-decision reception/decoding was done already at that time. –  Jyrki Lahtonen Jul 19 '12 at 4:33
    
Hadamard decoding can be used for any linearblock code over F_2 –  Alexander Chervov Jan 2 '13 at 9:31
1  
@AlexanderChervov Could you provide some details of how Hadamard transform decoding can be used for any linear block code over $\mathbb F_2$? I am not aware of this result. –  Dilip Sarwate Jan 21 '13 at 1:49
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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