On Correctable Errors of Binary Linear Codes

The error correction capability of binary linear codes with minimum distance decoding, in particular the number of correctable/uncorrectable errors, is investigated for general linear codes and the first-order Reed-Muller codes. For linear codes, a lower bound on the number of uncorrectable errors is derived. The bound for uncorrectable errors with a weight of half the minimum distance asymptotically coincides with the corresponding upper bound for Reed-Muller codes and random linear codes. For the first-order Reed-Muller codes, the number of correctable/uncorrectable errors with a weight of half the minimum distance plus one is determined. This result is equivalent to deriving the number of Boolean functions of m variables with nonlinearity 2 ^m-2+1 . The monotone error structure and its related notions larger half and trial set, which were introduced by Helleseth, Klÿve, and Levenshtein, are mainly used to derive the results.