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.

Computational complexity analysis of hamming codes polynomial co-decoding

Palese G.;Tomat E.;Vatta F.
2021-01-01

Abstract

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.
File in questo prodotto:
File Dimensione Formato  
Computational_Complexity_Analysis_of_Hamming_Codes_Polynomial_Co-Decoding.pdf

Accesso chiuso

Descrizione: Articolo principale
Tipologia: Documento in Versione Editoriale
Licenza: Copyright Editore
Dimensione 667.59 kB
Formato Adobe PDF
667.59 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11368/3021251
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? ND
social impact