Abstract Linear error-correcting codes form the mathematical backbone of modern digital communication and storage systems, but identifying champion linear codes (linear codes achieving or exceeding the best known minimum Hamming distance) remains challenging. By training a transformer to predict the minimum Hamming distance of a class of linear codes and pairing it with a genetic algorithm over the search space, we develop a novel method for discovering champion codes. This model effectively reduces the search space of linear codes needed to achieve a best minimum Hamming distance. Our results present the use of this method in the study and construction of error-correcting codes, applicable to codes such as generalised toric, Reed--Muller, Bose--Chaudhuri--Hocquenghem, Algebraic--Geometry, and potentially quantum codes.
Abstract Linear error-correcting codes form the mathematical backbone of modern digital communication and storage systems, but identifying champion linear codes (linear codes achieving or exceeding the best known minimum Hamming distance) remains challenging. By training a transformer to predict the minimum Hamming distance of a class of linear codes and pairing it with a genetic algorithm over the search space, we develop a novel method for discovering champion codes. This model effectively reduces the search space of linear codes needed to achieve a best minimum Hamming distance. Our results present the use of this method in the study and construction of error-correcting codes, applicable to codes such as generalised toric, Reed--Muller, Bose--Chaudhuri--Hocquenghem, Algebraic--Geometry, and potentially quantum codes.
Abstract Linear error-correcting codes form the mathematical backbone of modern digital communication and storage systems, but identifying champion linear codes (linear codes achieving or exceeding the best known minimum Hamming distance) remains challenging. By training a transformer to predict the minimum Hamming distance of a class of linear codes and pairing it with a genetic algorithm over the search space, we develop a novel method for discovering champion codes. This model effectively reduces the search space of linear codes needed to achieve champion codes. Our results present the use of this method in the study and construction of error-correcting codes, applicable to codes such as generalised toric, Reed–Muller, Bose–Chaudhuri–Hocquenghem, algebrogeometric, and potentially quantum codes.
Error-correcting codes and machine learning algorithms are two fundamental pillars in ensuring the reliability and accuracy of data transmission and storage systems. Error-correcting codes have long been instrumental in detecting and correcting errors during data communication and retrieval, while machine learning techniques have emerged as powerful tools for data analysis and pattern recognition. Integrating machine learning into error correction processes presents exciting opportunities to enhance error detection and correction performance, especially in complex and dynamic environments. In this article, we provide an in-depth overview of error-correcting codes, including traditional techniques like Hamming codes, Reed-Solomon codes, Turbo codes, and Convolutional codes. We explore the challenges faced by traditional error correction methods in handling modern data complexities. Subsequently, we delve into the integration of machine learning algorithms, such as neural networks, support vector machines, and decision trees, for error correction tasks. We discuss how machine learning enables adaptive, efficient, and dynamic error correction strategies. Furthermore, we examine real-world applications of machine learning-based error correction in communication systems, data storage, DNA sequencing, and quantum computing. Additionally, we highlight the challenges that researchers and engineers need to overcome, such as computational complexity, real-time processing, and adversarial attacks. Ultimately, the collaboration between error-correcting codes and machine learning offers exciting prospects for a future where data transmission and storage systems are more secure, efficient, and adaptable. By addressing challenges and embracing innovations, we can pave the way for error-free data management in an ever-evolving data-driven world.
Facing the challenge of enormous data sets variety, several machine learning-based algorithms for prediction (e.g, Support vector machine, multi layer perceptron and logistic regression) have been highly proposed and used over the last years in many fields. Error correcting codes (ECCs) are extensively used in practice to protect data against damaged data storage systems and against random errors due to noise effects. In this paper, we will use machine learning methods, especially multi-class logistic regression combined with the famous syndrome decoding algorithm. The main idea behind our decoding method which we call logistic regression decoder (LRDec) is to use the efficient multi-class logistic regression models to find errors from syndromes in linear codes such as bose, ray-chaudhuri and hocquenghem (BCH), and the quadratic residue (QR). Obtained results of the proposed decoder have a significant benefit in terms of bit error rate (BER) for random binary codes. The comparison of our decoder with many competitors proves its power. The proposed decoder has reached a success percentage of 100% for correctable errors in the studied codes.
Abstract. Error-correcting codes are fundamental tools used to transmit digital infor-mation over unreliable channels. Their study goes back to the work of Hamming [Ham50] and Shannon [Sha48], who used them as the basis for the field of information theory. The problem of decoding the original information up to the full error-correcting potential of the system is often very complex, especially for modern codes that approach the theoretical limits of the communication channel. In this thesis we investigate the application of linear programming (LP) relaxation to the problem of decoding an error-correcting code. Linear programming relaxation is a standard technique in approximation algorithms and operations research, and is central to the study of efficient algorithms to find good (albeit suboptimal) solutions to very difficult optimization problems. Our new "LP decoders " have tight combinatorial characterizations of decoding success that can be used to analyze error-correcting performance. Furthermore, LP decoders have the desirable (and rare) property that whenever they output a result, it is guaranteed to be the optimal result: the most likely (ML) information sent over the channel. We refer to this property as the ML certificate property.
Insertion-deletion (insdel for short) codes have received extensive attention due to their ability to correct synchronization errors. It is usually a very challenging problem to determine the insdel distances of linear codes. In this paper, a good lower bound on the insdel distance of a linear code with a certain algebraic structure is provided and it indeed gives an affirmative answer to an open problem proposed by Hao Chen (IEEE Transactions on Information Theory, 68(8): 5126–5132, 2022). Applying this lower bound to binary first-order Reed-Muller codes and binary simplex codes, we obtain that they possess linear subcodes that can correct arbitrary insdel errors while maintaining Hamming distances robustness. The application of this bound on Reed-Muller codes completely solves an open problem left by Lara Dolecek and Venkat Anantharam (IEEE Transactions on Information Theory, 53(4): 1430–1443, 2007). In order to enhance the code rate, we further perform puncturing on these subcodes and determine the Hamming distances of the punctured subcodes while ensuring that their insdel distances remain unchanged.
Mitigating errors in computing and communication systems has seen a great deal of research since the beginning of the widespread use of these technologies. However, as we develop new methods to do computation or communication, we also need to reiterate the method used to deal with errors. Within the field of quantum computing, error correction is getting a lot of attention since errors can propagate fast and invalidate results, which makes the theoretical exponential speed increase in computation time, compared to traditional systems, obsolete. To correct errors in quantum systems, error-correcting codes are used. A subgroup of codes, topological codes, is currently the focus of many research papers. Topological codes represent parity check matrices corresponding to graphs embedded on a d-dimensional surface. For our research, the focus lies on the toric code with a 3D square lattice. The goal of any decoder is robustness to noise, which can increase with code size. However, a reasonable decoder performance scales polynomially with lattice size. As error correction is a time-sensitive operation, we propose a neural network using an inductive bias: equivariance. This allows the network to learn from a rather small subset of the exponentially growing training space of possible inputs. In addition, we investigate how transformer networks can help in correction. These methods will be compared with various configurations and previously published methods of decoding errors in the 3D toric code.