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 loctor 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.