Verso il limite di Shannon

Se c’è una cosa in cui la comunità scientifica riesce bene è quella di dividersi e contrapporsi. Ad esempio, fino ad un certo punto c’era una specie di rivalità tra gli analitici e gli algoritmici: mentre i primi si inerpicavano su per diseguaglianze, somme integrali e deduzioni poggiate sui conti, i secondi tramutavano le relazioni analitiche in codice eseguibile e lasciavano che fosse il computer a pervenire a risultati inoppugnabili. Spesso avevano ragione entrambi, motivo in più per non collaborare.

Con il divenire dei computer via via più potenti, ad un certo punto gli algoritmici hanno iniziato a lavorare su idee che sembravano ormai affermate, oppure che erano troppo avanzate al momento della loro comparsa. Come ad esempio nel caso della codifica di canale, quella cosa che imballa i bit nel polistirolo, metafora del processo di aggiunta di ridondanza che permette di correggere gli errori di trasmissione, almeno finché il tasso informativo non eccede la capacità di canale, come un certo Claude Shannon dimostrò a metà secolo scorso, senza spiegare come fare. In quel caso, oltre alla tecnica a blocco (metodo analitico) che data la parola ricevuta ottiene quella corretta in un sol colpo, si fecero strada le tecniche convoluzionali in cui il processo di correzione diviene quello della ricerca del percorso di minimo costo all’interno di un grafo (metodo algoritmico). Sorpresa, funziona alla grande!

Sembrava fatta, e che non ci fossero altri metodi migliori, quando ad inizio anni ’90 dei francesi proposero di applicare un metodo iterativo (che più algoritmico non si può) ad una doppia codifica convoluzionale, basato sul reciproco scambio di informazione estrinseca tra due decoder, ovvero un specie di fonte di diversità costituita dalle conclusioni a cui giunge un decodificatore a partire da informazioni non disponibili all’altro. Dato che nel disegno che tentava (con risultati direi deludenti) di spiegare come funziona la questione si rappresentava lo scambio di informazione come una specie di controreazione, la tecnica prese il nome di codice turbo, in analogia all’omonima innovazione motoristica della stessa epoca.

All’inizio non ci credeva quasi nessuno, ma poi si sono tutti tuffati sul nuovo metodo, almeno finché altri ricercatori non si sono ricordati di una cosa detta da un altro scienziato, un certo Gallager, e cioè che il trucco era di avere matrici di controllo molto grandi, con molti pochi uni all’interno, definendo così i codici a bassa densità di uni o LDPC. A quel punto il metodo di decodifica prende il nome di Belief Propagation, rappresentato graficamente da un grafo bipartito (di Tanner) i cui nodi si ripartiscono tra due insiemi, che si scambiano anche in questo caso informazione estrinseca che con il progredire delle iterazioni si diffonde a tutti i nodi, i quali finiscono per addivenire ad una opinione condivisa che guardacaso è anche la migliore a posteriori. Con il senno di poi, la definirei intelligenza collettiva. Lo sapevi? Questo nuovo metodo batte anche il turbo! Portando il limite teorico di prestazione a meno di un dB da quanto è possibile ottenere in pratica!

Ora però, un passo indietro: non è che gli algoritmici hanno vinto così, a testa bassa: anche dietro le loro conquiste ci sono fior fiore di conti! Per seguire i quali si rischia però di perdere il filo ed il succo del discorso. E così, anche questa storia è entrata nella revisione del capitolo sulla teoria dell’informazione, che puoi trovare presso questa pagina. In realtà il capitolo si è scisso in due, con la prima parte che si occupa della codifica di sorgente, ora trattata in modo più esteso e rigoroso.

La prossima edizione sarà magnifica… ho ancore tre importanti innovazioni che vorrei inserire: la Software Defined Radio (SDR), i sistemi MIMO, ed i segnali sui grafi …ora vediamo quanto ci metto!

Photo by Alexandru Tudorache on Unsplash   

One comment

  1. Congratulazioni per il tuo lavoro di approfondimento e di ottimizzazione della presentazione dell’argomento, nonché per l’ulteriore evoluzione degli argomenti iniziali per tenere la materia trattata sempre più aggiornata.
    Teodoro A: De Angelis

Rispondi a Teodoro Antonio De Angelis Annulla risposta

Il tuo indirizzo email non sarà pubblicato.