Forum Informatica Unict

LAUREA TRIENNALE (D.M. 270/04) => Reti di Calcolatori, 9 CFU => Topic started by: sblite82 on 25-05-2013, 15:12:55



Title: Codifica di trellis e decodifica di viterbi
Post by: sblite82 on 25-05-2013, 15:12:55
Cari colleghi quacuno pò gentilmente spiegarmi passo passo la codifica di trellis e la decodifica di viterbi? Grazie di cuore


Title: Re:Codifica di trellis e decodifica di viterbi
Post by: Shin on 25-05-2013, 15:21:38
Questa è una bozza di un riassunto che mi ero preparato tempo fa:

Utilizza una macchina a stati finiti dove il passaggio da uno stato all'altro significa un bit, e avviene tramite l'invio di due bit (ad esempio, partendo dal primo stato, se devo mandare 0 metto 00 e rimango nello stesso stato; altrimenti, se devo mandare 1, scrivo 11 e passo allo stato successivo).

Ogni stato è caratterizzato da due possibili passi, entrambi alla massima distanza (ad esempio il primo stato ha 00 e 11, il secondo stato ha 10 e 01, e così via) e tali che a distanza di due salti ho tutte e quattro le possibili combinazioni.

Con queste caratteristiche si ottiene la possibilità di rilevare e correggere un errore ogni quattro bit.

 Ad esempio supponiamo di trovarci al tempo n nel primo stato, che ammette i due cammini 00 e 11, e che invece arriva 01, capiamo immediatamente che c'è un errore. Dopo di che, essendo “01” a distanza 1 da entrambi i passi consentiti (00 e 11) non ci resta che analizzare, per ognuno dei due passi 00 e 11, i loro rispettivi due passi successivi (quindi in questo caso 4 in tutto), cioè al tempo n+1, e confrontare la loro distanza con la sequenza che è arrivata al tempo n+1.

Salvo ulteriori errori, confrontando ciò che è arrivato al tempo n+1 con tutte le 4 possibilità (date dagli ipotetici successori di 00 e 11) riusciamo a capire qual'era il percorso giusto e quindi a correggere l'errore del passo al tempo n semplicemente prendendo tra le 4 possibilità quella con distanza minore da ciò che è arrivato al tempo n+1.

... se ti è poco chiaro ti consiglio di andare direttamente a ricevimento dal prof per fartelo spiegare come si deve ;)


Title: Re:Codifica di trellis e decodifica di viterbi
Post by: sblite82 on 25-05-2013, 16:32:24
Grazie per la spiegazione non è che mi sia molto chiaro. Vi chiedo se possibile postare un esempio. Per esempio se devo trasmettere la sequenza 011001 come bisogna fare? vi sarei molto grato per la vostra collaborazione... purtroppo essendo fuori sede non riesco ad andare al ricevimento dal prof come vorrei...


Title: Re:Codifica di trellis e decodifica di viterbi
Post by: Shin on 26-05-2013, 11:02:33
Grazie per la spiegazione non è che mi sia molto chiaro. Vi chiedo se possibile postare un esempio. Per esempio se devo trasmettere la sequenza 011001 come bisogna fare? vi sarei molto grato per la vostra collaborazione... purtroppo essendo fuori sede non riesco ad andare al ricevimento dal prof come vorrei...

dipende com'è fatta la macchina a stati:

Quote
Utilizza una macchina a stati finiti dove il passaggio da uno stato all'altro significa un bit, e avviene tramite l'invio di due bit (ad esempio, partendo dal primo stato, se devo mandare 0 metto 00 e rimango nello stesso stato; altrimenti, se devo mandare 1, scrivo 11 e passo allo stato successivo).

Supponiamo che la macchina sia questa (http://www.alantro.com/viterbi/fsm.gif) e di trovarci inizialmente nello stato #0 (nell'immagine gli stati sono i cerchietti azzurri).

Quote
per esempio se devo trasmettere la sequenza 011001 come bisogna fare?

Per trasmettere logicamente: 011001

Dobbiamo mandare:

00 11 01 01 11 11

- la prima coppia "00" significa "0" e rimaniamo nello stato #0 della macchina
- la seconda coppia "11" significa "1" e stiamo passando dallo stato #0 allo stato #1
- allo stato #1 per mandare "1" dobbiamo passare allo stato #3 scegliendo "01"
- allo stato #3 per mandare "0" dobbiamo passare allo stato #2 scegliendo "01"
- in #2 scegliamo "11" per mandare "0" tornando allo stato #0
- siamo nuovamente nello stato #0, e dobbiamo trasferire "1", quindi scegliamo di spostarci allo stato #1 scegliendo "11"

spero di non aver sbagliato qualche passaggio, è più chiaro adesso?