Recovering erroneous data bits using error estimating code

Abstract

Error correction techniques play an important role to guarantee reliable communication in wireless networks. The widely used error-correcting codes (ECCs) such as Hamming code introduce the benefit of error correction without retransmitting the data packet, but they suffer from high redundancy and communication overhead. In the recent years, error estimating code (EEC) was proposed to estimate the bit-error-rate (BER) of a packet efficiently with very low data redundancy. However, the ability of error correction using EEC remains unexplored. In this paper, we argue that EEC can be used to recover erroneous bits from the data packet. To show the capacity of error recovery with EEC, we propose an error correction scheme based on the parity check information provided by the EEC bits. We first introduce a filtering algorithm to rule out the correct data bits and obtain a set of suspicious bits containing most of the errors. Then we apply a polynomial randomized algorithm called Rand_flipping to examine the suspicious bits and flip the most promising erroneous bits aiming to minimize the total numbers of errors in the packet. Theoretical analysis proves that under some constraints the proposed Rand_flipping algorithm can correct most of the erroneous bits with probability higher than 1-1/e. Extensive experiments based on a real WiFi trace are conducted, which shows that the proposed algorithm corrects over 80% erroneous bits of the trace in practice.