Reed-Solomon Codes

[gopunk]

not sure if this is HT, but hope it is

can somebody please put in non-math terms how the reed-solomon codes operate in a somewhat detailed fashion? so you have a message of m elements... the reed-solomon codes then produces a set of N polynomials. if N is greater than m, it works?

http://www.siam.org/siamnews/mtc/mtc193.htm

Mathematically, Reed-Solomon codes are based on the arithmetic of finite fields. Indeed, the 1960 paper begins by defining a code as "a mapping from a vector space of dimension m over a finite field K into a vector space of higher dimension over the same field." Starting from a "message" $(a_0, a_1, . . ., a_{m-1})$, where each $a_k$ is an element of the field K, a Reed-Solomon code produces $(P(0), P(g), P(g^2), . . ., P(g^{N-1}))$, where N is the number of elements in K, g is a generator of the (cyclic) group of nonzero elements in K, and P(x) is the polynomial $a_0 + a_1x + . . . + a_{m-1} x^{m-1}$. If N is greater than m, then the values of P overdetermine the polynomial, and the properties of finite fields guarantee that the coefficients of P--i.e., the original message--can be recovered from any m of the values.

In today's byte-sized world, for example, it might make sense to let K be the field of degree 8 over $Z_2$, so that each element of K corresponds to a single byte (in computerese, there are four bits to a nibble and two nibbles to a byte). In that case, $N = 2^8 = 256$, and hence messages up to 251 bytes long can be recovered even if two errors occur in transmitting the values $P(0), P(g), . . ., P(g^{255})$. That's a lot better than the 1255 bytes required by the say-everything-five-times approach.

ok so i don't understand... is the set of polynomials used for the entire set of messages? or is each P supposed to match up to an a? can someone give me a complete example? their example is not really that complete.... i don't understand why messages up to 251 bytes can be recovered (why not 252?)

thanks for any assistance

 

[Geniere]

Have no clue, but try - mathforum.org