Error Estimating Codes With Constant Overhead: A Random Walk Approach

The paper studies the construction of Error-Estimating Codes (EEC), which estimate the Bit-Error-Rate (BER) of packet transmissions. The concept of EEC was first proposed by Chen et.al, who provided a construction based on group sampling, which term Group-Sampling Error-Estimating Codes (GSEEC). In this paper, RAndom walK based Error-Estimating codes (RAKEE) are proposed, which achieves constant communication overhead and linear coding complexity respect to packet length. Compared with GSEEC, better error decaying performance is proved for ALEEC. Numerical experiments show that RAKEE improves GSEEC on both estimating bias and estimating mean square error.