Decodifica per mezzo di algoritmi BCJR e decoder LDPC

A partire dai primi anni ‟90 grazie all‟invenzione dei codici turbo e della decodifica iterativa gli algoritmi che minimizzano la probabilità di errore sul simbolo sono tornati in auge dopo un periodo in cui erano stati soppiantati dagli algoritmi a rivelazione di sequenza,cio è dovuto non tanto alla necessità di minimizzare la probabilità di errore sul simbolo ma principalmente perchè gli algoritmi a massima probabilità a posteriori(MAP) forniscono come dati collaterali delle stime di affidabilità sulle sue decisioni, tali stime sono di primaria importanza quando si attuano delle decodifiche iterative.

Un algoritmo per la minimizzazione della probabilità d‟errore sul simbolo molto diffuso è il BCJR che prende il nome dai suoi autori (Bahl, Cocke, Jelinek e Raviv) [26]-[27], tale algoritmo oltre ad effettuare una stima dei simboli trasmessi, consente il calcolo delle probabilita a posteriori utili nel valutare l‟affidabilità della stima effettuata . Nel seguito faremo riferimento all‟equivalente tempo discreto a rumore bianco dell‟intero sistema di trasmissione illustrato in Fig. 2-16 e tratteremo il caso di modulazioni lineari codificate in presenza di ISI . Con queste ipotesi la relazione che lega l‟ingresso del detector ai simboli codificati è:

Eq. 2-36

∑

Essi rappresentano una statistica sufficiente per il calcolo della probabilità a posteriori del generico simbolo di informazione condizionata all‟osservazione del segnale ricevuto e proprio attraverso la massimizzazione di tale probabilità a posteriori otterremo la minimizzazione della probabilità di errore obiettivo di questo algoritmo. La strategia di decisione MAP si traduce nell‟ espressione:

Eq. 2-37 ̂ * + ( ) * +

Fig. 2-16. Schema dell’equivalente a tempo discreto e rumore bianco dell’intero sistema di trasmissione [27]

In cui è stato soppresso il termine ( ) a denominatore della in quanto indipendente dai simboli è quindi costante nella massimizzazione.

Definendo lo stato del sistema ( ), è possibile determinare univocamente i simboli codificati ( ) a partire dalla coppia ( ) e di conseguenza anche la densità di probabilità(ddp) ( ) ovvero:

Eq. 2-38

( ) ( )

{ | ∑

| }

La cui espressione deriva dal fatto che la variabile aleatoria(va) condizionatamente alla conoscenza dei simboli è una va gaussiana.

Inoltre essendo ( ) ( ) in corrispondenza biunivoca con una coppia costituita dallo stato e da un simbolo precedente (in questo caso ) è evidente che è possibile associare anche a quest‟ ultima coppia la sequenza ( ) di simboli di codice.

Nelle notazioni seguenti indicheremo con ( ) la coppia associata biunivocamente

ad una coppia ( ) fissata, ed in modo analogo con ( ) indicheremo la coppia associata ad una fissata coppia ( ).

L‟espressione Eq. 2-39 ( ) ( _{) (} | ) ∑ ( | ) ( ) ∑ ( _{| ) ( ) ( )} ∑ ( _{| ) ( ) ( ) ( )} ∑ ( _| ) ( ) ( ) ( ) ∑ ( ) ( ) ( ) ( ) ∑ ( ) ( ) ( )

Consente di ricavarci ( ) a partire da quantità calcolabili in maniera iterativa,essa stata ottenuta considerando l‟indipendenza fra e e considerando il processo di generazione degli markoviano, inoltre per semplicità sono state definite le quantità

Eq. 2-40 ( ) ( _{) ( )} Eq. 2-41 ( ) ( )

Queste sono appunto le quantita calcolabili iterativamente attraverso due procedimenti iterativi distinti , uno in avanti per ( ) (forward recursion)

Eq. 2-42 ( ) ∑ ( ) ( ) ( )

ed uno all‟indietro per ( ) (backward recursion) .

Eq. 2-43

( ) ∑ ( ) ( ) ( )

L‟algoritmo è strutturato in questo ordine [26]:

1) vengono calcolate, per mezzo della ricorsione in avanti e di quella all‟indietro le quantità ( ) e ( ) per ogni e per ogni stato .

2) insieme alle densità di probabilità ( ) queste quantità sono poi utilizzate per calcolare le densità di probabilità ( ) attraverso la (Eq. 2-39)

3) infine vengono calcolate le probabilità a posteriori * + che servono per le decisioni finali (Eq. 2-37).

L‟algoritmo non può operare in tempo reale ed ha complessità più elevata dell‟algoritmo di rivelazione di sequenza. L‟algoritmo in compenso fornisce, come risultato collaterale, le probabilità a posteriori dei simboli che possono essere utilizzate per fornire delle stime di affidabilità sulle decisioni. Tipicamente, nel caso di simboli di informazione binari, come

stima dell‟affidabilità della decisione sul bit ak si utilizza il seguente rapporto logaritmico delle probabilità (Log-likelihood ratio LLR) a posteriori

Eq. 2-44

( ) * + * +

La quantità ( ) prende anche il nome di decisione continua (soft decision) e permette per mezzo del segno di determinare la decisione sul simbolo e per mezzo della sua ampiezza di avere una misura della affidabilità della decisione effettuata.

Questa quantita ( ) rappresenta assieme alla decisione sul bit di informazione ̂ l‟output dell‟algoritmo BCJR. Dopo aver estratto a partire dalla LLR ( ) a posteriori (cioe frutto delle esservazioni sui campioni in ingresso al detector ) una stima della LLR a priori ( ), quest‟ ultima puo essere trasferita ad un altro blocco di decodifica, come il decoder Low-density-parity-check (LDPC) per incrementarne le prestazioni. Tale stima della LLR sarà infatti un valore più accurato del valore di LLR a priori iniziale che sarebbe stato altrimenti passato direttamente al secondo decoder e di conseguenza anche il valore di LLR a posteriori calcolato dal secondo decoder (l‟LDPC) risulterà maggiormente accurato, cosi come LLR a priori che è possibile estrarre da esso.

E‟ possibile in questo modo operare iterativamente collegando l‟uscita di un decoder all‟ingresso dell‟altro rendendo progressivamente più accurata la stima della LLR a priori e quindi più affidabile la decisione sul bit di informazione [27].

I codici low-density-parity-check (LDPC) [28]-[29] rappresentano una classe di codici a blocco lineari in cui una parola codificata contenente n bit e composta da k=n-r bit di informazione ed r bit di controllo.Gli n bit soddisfano un sistema di r equazioni (pari al numero di bit di controllo) a controllo di parità del tipo

Eq. 2-45

Dove è la somma modulo 2 ed sono i bit della parola codificata con * +. Tale equazioni rappresentano quindi dei vincoli fra tali bit , vincoli che permettono di identificare quando si è verificato un errore durante la trasmissione lungo il canale e attraverso un algoritmo di correggere questi errori decidendo in favore del vero bit di codice trasmesso. Equivalentemente al sistema di equazioni puo essere costruita una matrice di parità

di dimensioni (n-k)*n (ovvero r*n) in cui c‟è un 1 nella i-esima riga e j-esima colonna se e solo se il j-esimo bit della parola di codice è contenuto nella i-esima equazione di controllo. Il nome low-density deriva dal fatto che la matrice a controllo di parità contiene una quantita di 1 molto bassa in confronto alla quantità di 0, il vantaggio principale di questi codici è quello di avere prestazioni molto vicine al limite di Shannon e una complessita che cresce linearmente.

Per maggiore chiarezza usiamo oltre alla classica rappresentazione con matrici tipica dei codici a blocco lineari anche una rappresentazione grafica ed facciamo riferimento ad un esempio in cui la matrice non è low density perchè cio ci costringerebbe ad utilizzare una matrice di dimensioni molto più grandi di difficile rappresentazione e poco esplicativa. Le considerazioni che verranno fatte potranno però estendersi facilmente ad una matrice realmente low-density.

La Fig. 2-17 mostra una matrice di parità di dimensioni (n-k)Xn (nell‟esempio 4X8) per un codice (n,k) (nell‟esempio (8,4)), nel caso di codifica LDPC regolare la matrice è inoltre descritta da due valori ovvero il numero di 1 in ogni riga (=4)ed il numero di 1 in ogni colonna (=2),questo implica che ogni equazione di controllo contiene lo stesso numero di bit di codice e che ciascun bit di codice è contenuto nello stesso numero di equazioni di controllo, per una matrice veramente low-density dovrebbe essere ed . Nel caso di codifica LDPC irregolare e non sono fissati.

Questa stessa matrice cosi come l‟algoritmo LDPC stesso può essere rappresentato in modo funzionale in un grafico bipartito che fa uso di due tipologie di nodo: i variable nodes(v- nodes) in cui vengono rappresentati i bit della parola codificata (eventualmente corrotta da disturbi) ed i check nodes(c-nodes) che rappresentano le equazioni di controllo ,quindi al primo check node saranno collegati alcuni dei variable node cosi come descritto nella prima equazione di controllo (prima riga della matrice di parità) .

Fig. 2-17.Matrice di controllo di parità e grafico bipartito associato alle equazioni di controllo [28] Un check node è collegato ad un variable node se l‟elemento della matrice è 1, di conseguenza è possibile mettere in corrispondenza matrice e grafico bipartito pensando che ciascuna riga della matrice rappresenta un check node (ad esempio la prima riga mi indica quali bit della parola di codice sono legati dal vincolo di ) mentre ciascuna colonna rappresenta una delle parole di codice (ad esempio la prima colonna mi indica a quali check node è collegato il primo bit della parola di codice).

A fini esplicativi facciamo inizialmente riferimento all‟algoritmo nel caso di hard-decision su un canale binary simmetric channel BSC, esso ha prestazioni notevolmente inferiori rispetto all‟ algoritmo che implementa soft-decision e per questo non trova applicazioni pratiche, tuttavia risulta essere molto più semplice da comprendere.

Facciamo inoltre riferimento alla matrice H ed al grafico in Fig. 2-17, una parola di codice senza errori potrebbe essere per esempio , - per cui la somma modulo 2 dei bit memorizzati nei v-nodes collegati ad uno stesso c-node è (o equivalentemente presentano un numero pari di 1), ora consideriamo invece una parola di codice con un errore, ad esempio il bit flippato a , in questo caso per alcuni c-nodes la somma modulo 2 dei bit memorizzati nei v-nodes ad essi collegati non sarà più , cio rivela la presenza di un errore.

L‟algoritmo procederà in questo modo [28]:

1) in un primo step,tutti i v-nodes inviano ai loro rispettivi c-nodes (collegati da un ramo nel grafico bipartito) un messaggio in cui indicano quello che per loro è il bit corretto memorizzato all‟ interno di se stessi. Alla prima iterazione , l‟unica informazione che ha il v-node è il corrispondente -esimo bit di ricevuto ovvero

. Facendo riferimento al nostro caso specifico di Fig. 2-17, per esempio il v-node invia un messaggio contenente ai c-nodes e ed il v-node invia un messaggio contenente (che è stato flippato) ai c-nodes e , ecc.

2) In un secondo step ogni c-node calcola un messaggio di risposta per ciascun v-node ad esso collegato sulla base delle informazioni fornite dagli altri v-node

collegati a quello stesso , assumendo che tali informazioni siano corrette (Fig. 2-18). Nel nostro caso specifico per esempio quando deve inviare il messaggio a prende i valori , , e calcola che per rispettare la parità, assumendo corrette tali informazioni, deve essere . Da notare che questo potrebbe essere lo step finale nel caso in cui le equazioni di controllo calcolate in ogni c-node vengano soddisfatte ovvero i v-nodes ad esso collegati contengano un numero pari di .

3) Un terzo step prevede che i v-nodes usino le informazioni precedentemente conservate (come il valore di calcolato all‟iterazione precedente o se siamo alla prima iterazione il valore ) e le nuove informazioni appena acquisite dai c-nodes per effettuare le loro decisioni, un criterio di decisione molto semplice da usare per il Fig. 2-18. figura che illustra il passaggio dei messaggi dai v-nodes ai c-nodes e viceversa [28]

nostro esempio potrebbe essere una decisione a maggioranza. Una volta effettuata tale decisione(hard) ,questa viene utilizzata come nuova informazione da inviare ai c- nodes per l‟iterazione successiva, ricominciando quindi con il primo step dell‟algoritmo.

L‟algoritmo è quindi iterativo e se nel passo (2) ciascun c-node vede rispettata la parità allora l‟algoritmo si ferma , in alternativa è possibile fissare una soglia al numero di iterazioni per uscire dal ciclo.

Introducendo qualche notazione è possibile operare allo stesso modo anche per l‟algoritmo soft-decision, in particolare [28]:

 * +

 è un messaggio inviato dal v-node al c-nodes tale messaggio contiene la

probabilità secondo che il suo valore sia ( ( )) e la probabilità secondo che il

suo valore sia ( ( ))

 è un messaggio inviato dal c-nodes al v-node tale messaggio contiene la probabilità secondo che il valore di sia ( ( )) (e che il valore di sia ( ( ))

Fig. 2-19. la figura illustra il passaggio dei messaggi da v-nodes a c-nodes nel caso soft-decision, in tale circostanza i messaggi sono costituiti da probabilità [28]

L‟algoritmo procede in questo modo:

1) Tutti i v-node inviano il messaggio ai rispettivi c-nodes, se questa è la prima iterazione e non si hanno ulteriori informazioni ( ) ed ( )

2) Ciascun c-node allora calcola e invia al v-node ad esso collegato quella che per è la probabilità che ci sia un numero pari di 1 fra gli altri v-node ad esso collegati escludendo proprio , questo corrisponde a ( ) perchè per mantenere la parità deve essere

3) A questo punto i v-node aggiornano i messaggi che inviano ai loro c-node , in

genere tale calcolo viene ricavato dalla produttoria opportunamente normalizzata degli

escludendo dalla produttoria il termine che deriva proprio da quel singolo c-

node a cui si sta passando il messaggio. Nel frattempo i v-node hanno potuto aggiornare le loro stime ̂ dei bit codificati sulla base delle probabilità che il loro valore sia 0 o 1 e decidendo in favore di quella maggiore, tali probabilità sono calcolate ancora con una produttoria normalizzata degli ma sta volta vengono

incluse le informazioni provenienti da tutti i c-node . Una volta ricavate le stime ̂, l‟algoritmo termina se tali valori soddisfano tutte le equazioni di controllo di parità calcolate nei c-nodes oppure se viene raggiunta la soglia massima di iterazioni prefissata per l‟algoritmo, in alternativa si ritorna allo step 2 per un nuovo ciclo di iterazioni e i nuovi messaggi inviati dai v-node vengono utilizzati dai c-node per il calcolo dei .

Nell‟algoritmo invece di passare stime di * + come messaggi è possibile utilizzare le quantità * _* + ₊ da cui essendo * + * + è possibile comunque ricavarsi * + e viceversa, la quantita logaritmica è inoltre una misura dell‟ affidabilità della misura effettuata e le produttorie necessarie per il calcolo delle probabilità inviate come messaggi si traducono in sommatorie di minore complessità computazionale.

La concatenazione di BCJR ed LDPC prevede che oltre ad effettuare delle decisioni i due algoritmi si scambino vicendevolmente le misure di affidabilità (i Log likelyhood ratio LLR) che vengono impiegate per il calcolo delle probabilità a posteriori. Tali probabilità a posteriori in uscita da un algoritmo opportunamente elaborate saranno poi usate come probabilità a priori dall‟altro algoritmo per poter iterare le sue operazioni. Nel caso specifico il BCJR passerà all‟ algoritmo LDPC quelle probabilità a priori * + immagazzinate nei variable- nodes alla prima iterazione , mentre LDPC passerà all‟ algoritmo BCJR quelle probabilità a

priori necessarie al calcolo degli alfa,beta e della probabilità condizionata da massimizzare (Eq. 2-42, Eq. 2-43, Eq. 2-37).