A New Early-Termination Method for the Berlekamp-Massey Algorithm

The Berlekamp-Massey algorithm is a primary algorithm for decoding Reed-Solomon codes. As an inherent property of the algorithm, the early termination can effectively reduce the latency and power of decoding. It has been known that the algorithm can be terminated at the completion of the <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$(t+e)$</tex> -th iteration (where <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$e$</tex> is the number of errors and <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$t$</tex> is the error-correction capability of the code). In this paper, we explore a new mechanism for the early termination. Specifically, assuming <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$e\leq t$</tex>, we present a detection method that can identify the <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$2e$</tex> -th iteration. Since the error locator polynomial will have been found at the completion of the <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$2e$</tex> -th iteration, we can terminate the algorithm at this point based on the proposed method. As an application, a hardware-friendly algorithm variant, dubbed Reformulated Early-Terminating Parallel Inversionless Berlekamp-Massey (RETPIBM) algorithm, is presented, which yields a systolic architecture. The derivative architecture consists of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$3t+1$</tex> processing elements (PEs) and has the critical path of one multiplier and one adder. To the best of the authors' knowledge, this is literally the first architecture that achieves the early termination for Berlekamp-Massey algorithm.