New Efficient Decoder of Linear Block Codes Based on Information Sets, Hash Techniques, and Machine Learning Models

Error-correcting codes improve the reliability of data exchanged between transmitters and receivers; achieving efficient and fast decoding is a major challenge. In this work, we propose an efficient, fast, and high-performing decoder named FastSyndISD. The first version of the proposed decoder uses hashing techniques to quickly find the information set that allows for error correction directly from the syndrome of the received word. Hashing information sets significantly reduce space complexity, instead of all correctable errors, compared to HSDec, LRDec, and EL-BoostDec. The second version utilizes a machine learning model (decision tree) to quickly find the information set that enables error correction directly from the syndrome of the received word. This second version does not require storing a hash table, since the information set is determined by a decision tree classifier model. The performance of the proposed decoder FastSyndISD is very encouraging regarding its bit error rate (BER). Indeed, it succeeds in correcting all errors whose weights are equal to or less than the correction capacity of the analyzed codes. Furthermore, a comparison with various other decoders highlights its effectiveness. A detailed study of its space complexity, its time complexity, and the factors influencing its performance has also been conducted, aiming to achieve an optimal BER while reducing computational time and memory usage. This comparison proves the significant success of the proposed decoder.