Low-Complexity Chase Decoding of Elliptic Codes

This paper proposes two low-complexity Chase (LCC) decoding algorithms for elliptic codes, which are realized by K¨otter’s interpolation and the basis reduction (BR) interpolation, respectively. They are both developed from the perspective of computing the Gr¨obner bases of the interpolation modules. By identifying η unreliable symbols, 2η decoding testvectors are formulated and the corresponding interpolation modules can be defined. The re-encoding transform (ReT) is further introduced to facilitate the interpolation. The LCC-K ¨otter decoding performs interpolation for the common elements, producing an intermediate outcome shared by all test-vectors. The desired Gr¨obner basis w.r.t. each test-vector can be obtained in a binary tree growing fashion. The new interpolation process can start from intermediate nodes of the previously interpolated paths, resulting in a low complexity. But the decoding latency cannot be contained. In contrast, the LCC-BR decoding performs the common computation in basis construction, which partly substantiates the bases for all interpolation modules. The subsequent basis construction and reduction can be performed in parallel. Besides a low complexity, it offers a latency advantage over the LCC-K¨otter decoding. The decoding complexity and latency are analyzed and verified numerically. The LCC decoding performance are also presented, demonstrating their advantage over both the Guruswami-Sudan decoding and the algebraic soft decoding. Moreover, the performance advantage of elliptic codes over the Reed-Solomon (RS) codes is demonstrated.