{"id":1241,"date":"2005-05-20T00:00:00","date_gmt":"2005-05-19T22:00:00","guid":{"rendered":""},"modified":"-0001-11-30T00:00:00","modified_gmt":"-0001-11-29T22:00:00","slug":"1241","status":"publish","type":"post","link":"https:\/\/www.vialattea.net\/content\/1241\/","title":{"rendered":"Ho letto un articolo su un quotidiano (dal titolo “Ho scoperto il DNA dei computers”) su un tizio che sosteneva di aver scoperto un algoritmo di compressione in grado di ridurre i dati di un intero CD a qualche kByte. È possibile questo? Esiste un “limite teorico” calcolabile matematicamente che determina la “dimensione minima” dell’informazione?"},"content":{"rendered":"

Il problema della codifica delle stringhe binarie \u00e8 nato all’inizio
\ndegli anni ’70, proprio per progettare i supporti di archiviazione ottici.<\/font><\/p>\n

<\/p>\n

<\/font><\/p>\n

Il processo di scrittura su supporto ottico \u00e8 assimilabile ad un processo
\ndi codifica di un segnale sorgente binario in cui avviene,
\ncontestualmente, compressione del segnale.<\/font><\/p>\n

<\/p>\n

<\/font><\/p>\n

Si supponga di voler registrare su supporto ottico la stringa di binaria
\ndi n<\/i> bit<\/font><\/p>\n

<\/p>\n

<\/font><\/p>\n

\"\"\/<\/sub>, dove \"\"\/<\/sub><\/font><\/p>\n

<\/p>\n

<\/font><\/p>\n

Al termine del processo di scrittura, che introduce necessariamente
\nerrori, alcuni dei bit della stringa originale verranno alterati. Si supponga
\nche la probabilit\u00e0 di alterare un bit, a prescindere dalla sua posizione
\nsia p < \u00bd<\/i>, da cui, per contro, la probabilit\u00e0 di non alterarlo
\nsia (1-p)<\/i>.<\/font><\/p>\n

<\/p>\n

<\/font><\/p>\n

La registrazione su supporto ottico corrisponde quindi a sommare una
\nstringa <\/font><\/p>\n

<\/p>\n

<\/font><\/p>\n

\"\"\/<\/sub>, dove \"\"\/<\/sub><\/font><\/p>\n

<\/p>\n

<\/font><\/p>\n

che ha k<\/i> bit alterati con probabilit\u00e0 pk<\/sup>, <\/i>da
\ncui l’espressione che determina la probabilit\u00e0 della stringa z<\/u>:<\/font><\/p>\n

<\/p>\n

<\/font><\/p>\n

\"\"\/<\/sub><\/i><\/font><\/p>\n

<\/p>\n

<\/font><\/p>\n

ove w(z<\/u>)<\/i> \u00e8 il cosiddetto peso<\/i> della stringa z<\/u>,
\novvero il numero di 1 che essa contiene. La probabilit\u00e0 di z<\/u> si
\ncalcola facilmente osservando che per ogni 1 interviene un termine di probabilit\u00e0
\np<\/i> e per ogni zero uno di probabilit\u00e0 (1-p)<\/i>, mentre se w(z<\/u>)
\n<\/i>\u00e8 il numero di 1, n – w(z<\/u>) <\/i>\u00e8 il numero di 0.<\/font><\/p>\n

<\/p>\n

<\/font><\/p>\n

In un CD, le stringhe binarie vengono scritte a lotti di n<\/i> bit,
\nsolitamente 16, ma n<\/i> pu\u00f2 essere variato a piacimento in base al
\nsistema di codifica; essendo un CD assimilabile ad una stringa binaria
\npraticamente infinita (circa 108<\/sup> bit), per esso vale la legge
\ndei grandi numeri<\/i>, ovvero il numero di errori medio che si commette
\nnella registrazione \u00e8 np<\/i>, ovvero:<\/font><\/p>\n

<\/p>\n

<\/font><\/p>\n

\"\"\/<\/sub><\/font><\/p>\n

<\/p>\n

<\/font><\/p>\n

All’atto della scrittura su CD, si somma in XOR una stringa z<\/u>
\nall’originale della sorgente x<\/u>, il che equivale a dire che si ottiene
\nuna nuova stringa y<\/u> :<\/font><\/p>\n

<\/p>\n

<\/font><\/p>\n

\"\"\/<\/sub><\/font><\/p>\n

<\/p>\n

<\/font><\/p>\n

ove S(x<\/u><\/i>,<\/u> np) <\/i>\u00e8 detta sfera<\/i> di centro
\nx <\/u>e raggio np<\/i>, ottenuta alterando np<\/i> bit della stringa
\nx <\/u>di partenza.<\/font><\/p>\n

<\/p>\n

<\/font><\/p>\n

Qualsiasi sistema di decodifica, per essere affidabile, deve sempre
\nconsentire di ricostruire la stringa x<\/u> originale, a partire dalla
\nstringa y<\/u> registrata sul supporto, altrimenti si avrebbe fenomeno <\/p>\n

detto di aliasing<\/i>, ovvero una decodifica inversa che non restituisce
\nl’originale.<\/font><\/p>\n

<\/p>\n

<\/font><\/p>\n

Ci\u00f2 significa che qualsiasi sistema di decodifica deve garantire la
\nnon intersezione delle sfere di appartenenza delle stringhe dopo il processo
\ndi decodifica, ovvero:<\/font><\/p>\n

<\/p>\n

<\/font><\/p>\n

\"\"\/<\/sub>, per ogni x<\/u>‘,
\nx<\/u>”<\/i>.<\/font><\/p>\n

<\/p>\n

<\/font><\/p>\n

Stabilire un codice vuol dire, quindi, identificare un set di stringhe
\nnon confondibili, centri delle sfere in cui cade il segnale dopo la codifica.
\nIl problema principale \u00e8 stabilire la miglior codifica possibile, ovvero
\nfar si che il codice C<\/i>, composto dalle stringhe non confondibili,
\ncopra tutto lo spazio S <\/i>dei segnali da codificare:<\/font><\/p>\n

<\/p>\n

<\/font><\/p>\n

\"\"\/<\/sub><\/font><\/p>\n

<\/p>\n

<\/font><\/p>\n

ove d<\/i> \u00e8 la distanza in bit tra due stringhe.<\/font><\/p>\n

<\/p>\n

<\/font><\/p>\n

La capacit\u00e0 di correzione di errore<\/i> di un codice \u00e8 direttamente
\nlegata alla cardinalit\u00e0 del codice stesso, ma in modo asintotico:<\/font><\/p>\n

<\/p>\n

<\/font><\/p>\n

\"\"\/<\/sub><\/font><\/p>\n

<\/p>\n

<\/font><\/p>\n

relazione che esplicita la capacit\u00e0 di correggere errori in un codice
\ndi cardinalit\u00e0 |C|. Si dimostra che un codice caratterizzato da capacit\u00e0
\ndi correzione R(e)<\/i> garantisce nR(e)<\/i> bit detti “liberi”, destinati
\nad ospitare il controllo di ridondanza per la correzione di e\/2 <\/i>errori.<\/font><\/p>\n

<\/p>\n

<\/font><\/p>\n

In soldoni, riducendo la cardinalit\u00e0 del codice C, ovvero aumentando
\nil passo di compressione<\/i>, ci si scontra inevitabilmente con l’incapacit\u00e0
\ndi riprodurre il segnale originale.<\/font><\/p>\n

<\/p>\n

<\/font><\/p>\n

Si dimostra che R(e) <\/i>\u00e8 limitato superiormente ed inferiormente
\n(per e <\/i>< \u00bd) dalle disuguaglianze di Gilbert-Varshamov ed Hamming:<\/font><\/p>\n

<\/p>\n

<\/font><\/p>\n

\"\"\/<\/sub><\/font><\/p>\n

<\/p>\n

<\/font><\/p>\n

dove h<\/i> \u00e8 l’entropia binaria del segnale, definita come h
\n= -(p log2<\/sub> p+ (1-p) log2<\/sub>
\n(1-p))<\/i>.<\/font><\/p>\n

<\/p>\n

<\/font><\/p>\n

L’entropia rappresenta, praticamente, il grado di caoticit\u00e0 del segnale
\nin ingresso che, ricordiamo, \u00e8 costituito da sequenze di 0 e 1. Il massimo
\ndell’entropia si ha per p = \u00bd<\/i>, ovvero quando le stringhe sono composte
\nindifferentemente da 0 e da 1, mentre il minimo dell’entropia si ottiene
\nquando si tende ad avere lunge sequenze di 0 o 1.<\/font><\/p>\n

<\/p>\n

<\/font><\/p>\n

Si dimostra, ancora, che l’entropia del segnale concorre a determinare
\nnon solo il tasso di errore, ma anche\u00a0 la lunghezza media della stringa
\nottenuta dopo la codifica, ovvero:<\/font><\/p>\n

<\/p>\n

<\/font><\/p>\n

|y<\/u>| = nh(p)<\/i><\/font><\/p>\n

<\/p>\n

<\/font><\/p>\n

Riassumendo, l’entropia del segnale in ingresso determina:<\/font><\/p>\n

<\/p>\n

<\/font><\/p>\n