FAST DECODING OF REED-SOLOMON CODE

A technique to perform fast decoding of a Reed-Solomon code. A first multiplier unit multiplies a matrix Bh with a column vector v using common adders to produce a column vector v1. The vector v represents one of an error locator polynomial, an error evaluator polynomial, and a derivative polynomial for a (n, k) Reed-Solomon code. The matrix Bh is over GF(2) including first h columns of a matrix B. A second multiplier unit multiplies non-unity components of a column vector A with non-zero components of the column vector v1 component-wise in GF(q) to produce a column vector v2, q being equal to n+1. A third multiplier unit multiplies diagonal sub-matrices of a matrix C with corresponding components of the column vector v2 in GF(2) to produce a column vector v3.