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?
