Analysis of the distribution of the number of erasures correctable by a binary linear code and the link to low-weight codewords |
The number and weight of low-weight codewords of a binary linear code determine the erasure channel performance. Analysis is given of the probability density function of the number of erasures correctable by the code in terms of the weight enumerator polynomial. For finite-length codes, zero erasure decoder error rate is impossible, even with maximum-distance-separable (MDS) codes and maximum-likelihood decoding. However, for codes that have binomial weight spectra, for example BCH, Goppa and double-circulant codes, the erasure correction performance is close to that of MDS codes. One surprising result is that, for many (n, k) codes, the average number of correctable erasures is almost equal to n - k, which is significantly larger than dmin - 1. For the class of iteratively decodable codes (LDPC and turbo codes), the erasure performance is poor in comparison to algebraic codes designed for maximum dmin. It is also shown that the turbo codes that have optimised dmin have significantly better performance than LDPC codes. A probabilistic method, which has considerably smaller search space than that of the generator matrix-based methods, is presented to determine the dminof a linear code using random erasure patterns. Using this approach, it is shown that there are (168, 84, 24) and (216, 108, 24) quadratic double-circulant codes.
Tomlinson M, Tjhai CJ, Cai J, Ambroze MA