On Correctable Errors of Binary Linear Codes
Kenji Yasunaga, Toru Fujiwara · IEEE Transactions on Information Theory · 2010
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$. Themonotone error structureand its related notionslarger halfandtrial set, which were introduced by Helleseth, Kløve, and Levenshtein, are mainly used to derive the results.