Title: A view of Gaussian elimination applied to early-stopped Berlekamp-Massey algorithm
Authors: Liu, Chih-Wei
Lu, Chung-Chin
Department of Electronics Engineering and Institute of Electronics
Keywords: BCH codes;Berlekamp-Massey algorithm;decoding;error-correcting codes;Gaussian elimination
Issue Date: 1-Jun-2007
Abstract: In this paper, we adopt a restricted Gaussian elimination on the Hankel structured augmented syndrome matrix -to reinterpret an early-stopped version of the Berlekamp-Massey algorithm in which only (t + e) iterations are needed to be performed for the decoding of BCH codes up to t errors, where e is the number of errors actually occurred with e <= t, instead of the 2t iterations required in the conventional Berlekamp-Massey algorithm. The minimality of (t + e) iterations in this early-stopped Berlekamp-Massey (ESBM) algorithm is justified and related to the subject of simultaneous error correction and detection in this paper. We show that the multiplicative complexity of the ESBM algorithm is upper bounded by (te + e(2) - 1) for all e <= t and except for a trivial case, the ESBM algorithm is the most efficient algorithm for finding the error-locator polynomial.
URI: http://dx.doi.org/10.1109/TCOMM.2007.898827
ISSN: 0090-6778
DOI: 10.1109/TCOMM.2007.898827
Volume: 55
Issue: 6
Begin Page: 1131
End Page: 1143
Appears in Collections:Articles

Files in This Item:

  1. 000247389700009.pdf