Algebraic Chase Decoding of Elliptic Codes With Generalized Re-Encoding Transform and Improved Root-Finding

Algebraic Chase decoding (ACD) is an effective soft-decision decoding approach for elliptic codes. By identifying η least reliable symbols, 2η test-vectors are formulated, each of which will be decoded through the interpolation and rootfinding processes. To improve the ACD of elliptic codes, this paper proposes the generalized re-encoding transform (GReT) and improved root-finding (IRF) for reducing the decoding complexity. A systematic encoding method for elliptic codes with an arbitrary information set is proposed to re-encode the received symbols with the most reliable information set (MRIS). By assessing the likelihood of the re-encoded codeword, the ACD can be early terminated, saving the decoding computation for all test-vectors. The GReT, which allows arbitrary selection of re-encoding positions, is further proposed for the ACD in reducing the interpolation complexity. It transforms the interpolation polynomials and points using the Gröbner basis associated to the MRIS. Furthermore, the IRF is proposed to reduce the root-finding complexity that also grows exponentially with η. It can directly determine the codeword candidates from the interpolation outcomes and eliminate the restoration of interpolation polynomials in the context of GReT. Our numerical results show that the proposed GReT and IRF significantly reduce the interpolation and root-finding complexity of ACD, respectively. Moreover, with the early termination facilitated by the re-encoding with the MRIS, the average ACD complexity decreases as the channel conditions improve.