Linear time decoding of real-field codes over high error rate channels

This paper proposes a novel algorithm for decoding real-field codes over erroneous channels, where the encoded message is corrupted by sparse errors, i.e., impulsive noise. The main problem of decoding such a corrupted encoded message is to reconstruct the error vector; recently, a common way to reconstruct it is to find the sparsest solution to an underdetermined system that is constructed using a parity-check matrix. Unlike the conventional approaches reconstructing the high-dimensional error vector directly, the proposed method crossly recovers the elements of error vector from two (or several) groups of low-dimensional equations. Compared with the traditional algorithms, the proposed method can decode an encoded message with a much higher corruption rate. Furthermore, the complexity of our method is linear, which is much lower than those of the traditional methods. The experimental results verified the high error correction ability and speed of the proposed method.