Correcting Erroneous Data Bits Based On Error Estimating Code

Error Correction Code (ECC) is an important technique to guarantee reliable com-munication in wireless networks. Currently, ECC techniques introduce the benefit of error correction without retransmitting the data packet, but they suffer from high redun-dancy and communication overhead, which decreases network transmission efficiency. 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, since EEC does not have error correction ability, the entire packet is retransmitted to correct erro-neous bits, when errors occur.This paper discusses the error correction based on EEC and investigates when EEC detects errors, whether the error bits could be corrected without retransmitting the entire packet. Our research result shows that, bit-error-rate in most of erroneous packets is small(smaller than 0.06). By utilizing the EEC probabilistic characteristics, most of error bits in these packets with small BER can be corrected (the recovery rate can reach more than 80%)We propose an error correction scheme based on the parity check information provided by the EEC bits. Firstly, the filtering algorithm is introduced to rule out the correct data bits and obtain a set of suspicious bits containing most of the errors. Then a polynomial randomized algorithm called Rand-flipping is applied to examine the suspicious bits and flip the most promising erroneous bits aiming to minimize the total numbers of errors in the packet. We present theoretical analysis to the algorithm and prove that Rand-flipping can correct most of the erroneous bits with high probability when BER is small enough; performance evaluation based on a real WiFi trace shows the effectiveness of the proposed algorithms.By exploring the real WiFi trace, we find that the distribution of BER in the pack-ets follows the power law distribution and errors are always burst, i.e. they tend to occur continuously and batchly. Motivated by the above findings, we design a novel protocol called EEC-PPR to recovery partial packet in wireless networks. The proto-col first encodes the original packet by both EEC and block check codes. Depending on the estimating value of BER and a predefined threshold, the protocol recovers par-tial packet with EEC error correction scheme when BER is small enough, or, alter-natively block-retransmission scheme when BER is high. The protocol avoids a plu-rality of packet retransmission, by employing EEC error correction scheme, decreases the wastage caused by the entire packet retransmission by utilizing block based par-ity check. Comparison of different partial packet recovery based on a real WiFi trace shows the effectiveness of our protocol.The main contributions of this thesis are as follows:1. We formulate the error correction problem based on Error Estimation Code. By formalization of using EEC to recovery the errors bits as an optimization prob-lem, error bits in the packet are recovered through optimizing the objective func-tion.2. We proposed an error correction scheme based on EEC. This scheme introduces the filtering algorithm to obtain a set of suspicious bits. Then, the randomized algorithm called Rand_flipping is used to flip the most possible erroneous bits in the suspicious bit set aiming to minimize the total numbers of errors in the packet. Theoretical analysis proves that our scheme can correct most of the er-roneous bits with high probability when the bit-error-rate is small enough.3. We Proposed a partial packet recovery protocol for wireless communications: EEC-PPR. Based on low redundancy code, this protocol effectively reduces the number of packet retransmission, by utilizing the error correction ability of EEC, and effectively decreases the amount of retransmission data by employing block code.4. We conduct performance evaluation based on a real WiFi trace, which shows the effectiveness of the proposed algorithms.