Computational Complexity Analysis of Hamming Codes Polynomial Co-Decoding
Flavio Ellero, G. Palese, E. Tomat, F. Vatta · 2021
In mathematical terms, Hamming codes are a class of binary linear codes. Due to the limited redundancy that they add to the data, they can only detect and correct errors when the error rate is low. This is the case in computer memory – usually random-access memory (RAM) – where bit errors are extremely rare and Hamming codes are widely used. A RAM with this correction system is a so-called error correction code (ECC) RAM (also known as ECC memory). ECC memory is used in most computers where data corruption cannot be tolerated under any circumstances, like industrial control applications, critical databases, and infrastructural memory caches. The parity-check matrix of a Hamming code contains all length k non-zero binary vectors. This paper is focused on their cyclic version, in order to exploit the mathematical advantages of cyclic codes. Since, as far as the Authors know, the computational complexity of Hamming codes polynomial decoding has not been addressed directly in the literature, in this paper the computational complexity of their co-decoding in polynomial form is analyzed in detail.