The invention provides a method for decoding an error correction code. First, an error syndrome of the error correction code is calculated. A plurality of coefficients of an error locator polynomial of the error correction code is then sequentially determined according to the error syndrome. When a new coefficient of the error locator polynomial is determined, it is also determined whether the new determined coefficient is equal to zero. When the new determined coefficient is equal to zero, a speculated error locator polynomial is built according to a plurality of low-order-term coefficients of the error locator polynomial, wherein the orders of the low-order-term coefficients are lower than that of the new determined coefficient. A Chien search is then performed to determine a plurality of roots of the speculated error locator polynomial. The error correction code is then corrected according to the roots of the speculated error locator polynomial.