本发明提供一种错误检查和纠正(ECC)解码器用以进行BCH解码，以将码字解码为经解码数据。所述ECC解码器包括校验子产生电路、错误定位多项式电路以及解码电路。校验子产生电路可以产生对应于码字的多个校验子。错误定位多项式电路可以通过使用这些校验子进行算术运算，以产生错误定位多项式的多个系数。所述算术运算包含多个运算子，其中这些运算子中的至少一个运算子是查找表电路。解码电路可以求取具有这些系数的错误定位多项式的至少一解，以及依据错误定位多项式的所述解来纠正码字，以产生所述经解码数据。