PPT Slide

The Distance of Reed Solomon Codes

• If we have two messages m1 ? m2 what is the closest (Hamming Distance) that their encodings C(m1) and C(m2) could be?

• Let M1(x) be the poly for m1, and M2(x) the poly for m2.

• Let p = m1- m2 ? P(x) = M1(x) - M2(x) ? C(p) = C(m1) - C(m2)

M1(x0)

M1(x1)

M1(x2)

M1(x3)

M1(xi)

M1(xn-1)

M2(x0)

M2(x1)

M2(x2)

M2(x3)

M2(xi)

M2(xn-1)

P(x0)

P(x1)

P(x2)

P(x3)

P(xi)

P(xn-1)

How many of these are non-zero?

At most k-1 roots of P(x) ? distance of n - k + 1

? [n,k, n-k+1]q

Previous slide

Next slide

Back to first slide

View graphic version