Iterative Erasure Correcting Algorithm for q-ary Reed-Muller Codes based on Local Correctability

In this paper, we propose a novel iterative erasure correcting algorithm for q-ary RM codes based on their local correctability. The proposed algorithm consists of two phases. In the first phase, the algorithm tries to find all the lines that help to correct as many erasure symbols as possible, and then local erasure correction procedures based on Lagrange interpolation are executed in the second phase. These two phases are repeated until the number of iterations reaches a given number. In both phases, most of computation processes are independent and thus the proposed algorithm provides massive parallelism. Computer experiments show that the convergence of an iterative decoding process is very fast in many cases. With some parameter setting, it is observed that the algorithm yields near ML decoding performance. If an decoding process is carried out with n-parallel processors (n represents the code length), the algorithm runs with sublinear-time on n if certain conditions are met.