Erasures and Error-Correcting Codes
Martin Tomlinson, Cen Jung Tjhai, Marcel Ambroze, Mohammed Ahmed, Mubarak Jibril · Signals and communication technology · 2017
It is shown that the number and weight of low-weight codewords of a linear code determine the erasure correcting performance of the code. Analysis is given of the probability density function of the number of erasures correctable by a given code in terms of the weight enumerator polynomial of the code. For finite-length codes and the erasure channel the best performance is achieved with maximum distance separable (MDS) codes and maximum likelihood decoding. Unfortunately, for the case of binary codes, there are no MDS codes, apart from trivial cases. However it is shown that for those binary codes that have a codeword weight distribution that is close to a binomial distribution the erasure correction performance is almost equal to that of MDS codes. Such binary codes include BCH, Goppa and double-circulant codes, and the erasure correction performance using several examples of these codes is presented. The contrasting performance of some LDPC and turbo codes is also given. A probabilistic method based on the parity-check matrix, is described which is particularly effective at finding low-weight codewords of any linear code. The method is based on randomly chosen erasure patterns and for most codes quickly determines the minimum Hamming distance of the code.