## Reed Solomons code, for binary input [closed]

I want to write a linear code above the binary alphabet (a linear transformation {0,1}^n --> {0,1}^m where m is polynomial in n) using Reed Solomon code, and the restriction is that the Hamming distance divided by the length of the coded word will be at list 0.4 .

The thing is that Reed Solomon is a non-binary code. It operates above an alphabet of a large field.

The first thing you might think to do to overcome the problem is to choose some large power of a prime q>=m to be the size of the field F(q) and convert every log(q) bits into a letter in F(q) , then code the word using RS and then convert the coded word back into binary.

The problem with this solution is that the Hamming distance divided by the length of the word before converting to binary was (m-n+1)/m, but after converting into binary is (m-n+1)/(m*log(q)) because the number of different bits (in the worse case) stays m-n+1 but every letter in F(q) is now represented by log(q) bits so the length of the word is m*log(q) .

(m-n+1)/(m*log(q)) goes to 0 when m,q go to infinity. And so, the restriction that the hamming distance divided by the length will be at list 0.4 doesn't hold.

Any suggestions to a solution?

-
 Please add some clarity and remove some typos (although "humming distance" made me smile). At the moment it seems too much like a stream of consciousness for me to understand. – darij grinberg Dec 3 2011 at 23:33 If it's an exercise, please read mathoverflow.net/faq#whatnot – David Roberts Dec 4 2011 at 0:55 I don't think that this is an exercise. Coding theory has developed several bounds showing that this impossible for most combinations of $m$ and $n$. Therefore I suspect that this is a misguided attempt to do something impossible. Agree that MO is not the forum for this, and would advice the OP to ask the question elsewhere, where s/he can be educated about those bounds. – Jyrki Lahtonen Dec 4 2011 at 11:41