Reed-Solomon error correction ( $RS_{k} (a_{1}, \dots, a_{n})$ )

For distinct elements

a_{1}, \dots, a_{n}

of a finite field, a Reed-Solomon code consists of the evaluation vectors

(f (a_{1}), \dots, f (a_{n}))

of polynomials with degree less than

k

. It has dimension

k

and minimum Hamming distance

n - k + 1

, so it is a maximum distance separable code. A nonzero polynomial has at most its degree many distinct polynomial roots. Primitive cyclic Reed-Solomon codes use all nonzero field elements, ordered as powers of a primitive root of unity; arbitrary evaluation sets need not give a cyclic code.

Table of contents
- Primitive cyclic Reed-Solomon code Reed-Solomon error correction
  - Reed-Solomon key equation Primitive cyclic Reed-Solomon code
  - Duality of primitive cyclic Reed-Solomon codes Primitive cyclic Reed-Solomon code
- Generalized Reed-Solomon code Reed-Solomon error correction

Primitive cyclic Reed-Solomon code ( $C_{k, b} = ⟨ \prod_{ℓ = b}^{b + n - k - 1} (x - ω^{ℓ})⟩$ )

Let

n = q - 1

and let

ω

be a primitive root of unity in

F_{q}

n

cyclic code with consecutive zeros of a cyclic code

ω^{b}, \dots, ω^{b + n - k - 1}

k

. It equals the generalized Reed-Solomon code of vectors

(ω^{j (1 - b)} f (ω^{j}))_{j = 0}^{n - 1}

,

de g f < k

b = 1

is the unweighted Reed-Solomon code on these evaluation points; allowing other offsets makes this family closed under dual codes.

Reed-Solomon key equation ( $Λ (z) S (z) \equiv Ω (z) (mod z^{n - k})$ )

S_{ℓ} = \sum_{i} E_{i} X_{i}^{b + ℓ}

and distinct error-location values

X_{i}

, form

S (z) = \sum_{ℓ = 0}^{n - k - 1} S_{ℓ} z^{ℓ}

and the error locator polynomial

Λ (z) = \prod_{i} (1 - X_{i} z)

. There is an error evaluator polynomial

Ω

of degree less than the number of errors satisfying the key equation. When the number of errors is at most

⌊(n - k) /2 ⌋

, the Berlekamp-Massey algorithm or extended Euclidean algorithm recovers these polynomials, normalized by

Λ (0) = 1

.

Duality of primitive cyclic Reed-Solomon codes ( $C_{k, b}^{⊥} = C_{n - k, 1 - b}$ )

For

n = q - 1

and

a_{j} = ω^{j}

, the two evaluation forms are

a_{j}^{1 - b} f (a_{j})

and

a_{j}^{b} h (a_{j})

, with

de g f < k

and

de g h < n - k

. Their dot product is

\sum_{j} a_{j} f (a_{j}) h (a_{j}) = 0

, since every appearing exponent is between one and

n - 1

and the sums of those powers of

a_{j}

vanish. Comparing dimensions proves equality with the dual code. In particular, the dual of the unweighted evaluation code has multipliers

a_{j}

; it need not be an unweighted evaluation code on the same ordered points.

Generalized Reed-Solomon code ( $GRS_{k} (a, v)$ )

A generalized Reed-Solomon code consists of

(v_{i} f (a_{i}))_{i = 1}^{n}

, where the evaluation points are distinct, all coordinate multipliers

v_{i}

are nonzero, and

de g f < k

. It remains a maximum distance separable code. Its dual code is another generalized Reed-Solomon code with dimension

n - k

and multipliers proportional to

v_{i}^{- 1} \prod_{j \neq = i} (a_{i} - a_{j})^{- 1}

.

 Ancestors (6)

 Synonyms (2)

 View article source

 Discussion (0) New discussion

There are no discussions about this article yet.

 Articles by others on the same topic (1)

Reed–Solomon error correction by

Wikipedia Bot  1

Reed–Solomon error correction is a type of error-correcting code that is widely used in digital communications and data storage systems to detect and correct errors in data. It is named after Irving S. Reed and Gustave Solomon, who developed the code in the 1960s. ### Key Features of Reed-Solomon Codes: 1. **Block Code**: Reed-Solomon codes operate on blocks of symbols, rather than on individual bits.

 Read the full article

  See all articles in the same topic Create my own version