Ottimizzazione e proposta di nuovi algoritmi per trovare la distanza minima di codici LDPC

The error correction capabilities of an error correcting code are strictly related to the minimum distance between any two codewords in it. Therefore, finding the minimum distance of codes is of great importance. For linear codes, this can be done by finding the minimum non null codeword, which is a well known NP-hard problem. Information Set Decoding (ISD) is the most efficient family of algorithms for finding the minimum weight codeword of generic codes. We investigate the use of ISD algorithms with Low-Density Parity-Check (LDPC) codes, a family of codes characterized by sparse parity-check matrices. A new ISD algorithm, called SparseISD, is proposed, together with a novel ensemble of codes that comprehends LDPC codes. We prove that these codes have a weight distribution analog to those of random codes, that are, conventionally, the target of ISD algorithms. SparseISD performs better than state of the art ISD algorithms when applied to codes from our ensemble. A proof-of-concept implementation is presented.

Un codice a correzione d'errore ha capacità di correzione strettamente legate alla distanza minima tra le parole in codice che lo compongono, dette codeword. Per codici lineari, i più utilizzati nella pratica, la distanza minima è pari al peso della codeword non nulla con peso minore, ossia con il minor numero di simboli diversi da zero. Trovare la parola a peso minimo di codici generici è un problema NP-hard, ovvero, gli algoritmi esistenti impiegano un tempo che cresce esponenzialmente con la dimensione del codice considerato. La famiglia di algoritmi più utilizzata a questo scopo è Information Set Decoding (ISD). Informalmente, si può pensare agli algoritmi ISD come una variante degli attacchi a forza bruta, nel quale si fanno assunzioni sulla distribuzione dei simboli nelle codeword. In questa tesi proponiamo un algoritmo ISD, chiamato SparseISD, per trovare la parola a peso minimo di codici Low-Density Parity-Check (LDPC). Questi codici presentano una matrice di parità sparsa, cioè con la maggioranza degli elementi nulli. SparseISD sfrutta questa caratteristica per creare condizioni di ricerca favorevoli. Studiamo il problema presentando un ensemble di codici creato come generalizzazione dell'ensemble dei codici random, che sono tipicamente il bersaglio degli algoritmi ISD. Dimostriamo che i codici LDPC presentano una distribuzione di peso che tende a quella dei codici random. Presentiamo inoltre, un'implementazione proof of concept di SparseISD, per dimostrarne il funzionamento.