Low-Complexity Classical and Machine Learning Algorithms to Locally and Globally Recover Algebraic Codes over Finite Fields

Recovering algebraic codes over a finite field through algebraic-geometric methods can be computationally challenging, especially when dealing with extensive searches necessitated by the larger cardinality of the field. In response to these computational demands, we present low-complexity classical and machine learning algorithms for both local and global recovery of algebraic codes over finite fields. Our classical algorithm could be utilized to locally and globally recover codes over the field of cardinality n with the complexity of O (r log r) as opposed to O(r^3), where r < n is the locality of the field. Recognizing that algebraic codes are limited to local recovery, we present globally recovered codes with a neural network architecture. This approach utilizes a structured neural network grounded in discrete cosine transform architecture, so-called DCT-StNN, which incorporates both frozen and learnable weight matrices for enhanced performance. We present numerical results for both the classical algorithm and the DCT-StNN architecture. Although the DCT-StNN has similar accuracy and requires 90% fewer FLOPs and parameters than conventional feed-forward networks, the classical algorithm is the one that has the lowest FLOPs and inference time. However, it’s worth noting that while the classical approach struggles to predict unseen algebraic codes, the DCT-StNN excels in this regard. This is a joint work with Hansaka Aluvihare, Xianqi Li, and Sirani M. Perera