A Reed-Solomon decoder (199) processes a codeword containing n m-bit symbols to determine coefficients of an error locator polynomial sigma (x), and thereafter generates an error evaluator polynomial omega (x). The decoder comprises a bank (B103) of syndrome registers (103) for storing syndrome values; a bank (B101) of error locator registers (101) for accumulating therein coefficients of an error locator polynomial sigma (x); and, a bank (B102) of intermediate registers (102) for accumulating therein coefficients of an intermediate polynomial tau (x). The decoder (199) further includes a register update circuit (50) which, for a given codeword, conducts two-phased error locator iterations in order to update values in the error locator registers and the intermediate registers. In contrast to prior art techniques, the register update circuit (50) of the present invention updates coefficients of the intermediate polynomial tau (x) during the first phase of each error locator iteration, and updates coefficients of the error locator polynomial sigma (x) during the second phase of each error locator iteration. In further contrast, the decoder (199) of the present invention requires only one bank of error locator registers (101) and one bank of intermediate registers (102) and facilitates serial data shifting rather than parallel data transfer, thereby reducing circuit real estate.