Pages: [1]   Go Down
Print
Author Topic: Codifica di trellis e decodifica di viterbi  (Read 3064 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
sblite82
Matricola
*
Offline Offline

Posts: 26


« 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
Logged
Shin
Forumista
***
Offline Offline

Gender: Male
Posts: 822

Io sono ciò che sono per ciò che siamo tutti


WWW
« Reply #1 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 Wink
Logged

"Il peggiore analfabeta è l’analfabeta politico. Egli non sente, non parla, nè s’importa degli avvenimenti politici. Egli non sa che il costo della vita, il prezzo dei fagioli, del pesce, della farina, dell’affitto, delle scarpe e delle medicine dipendono dalle decisioni politiche.

L’analfabeta politico è così somaro che si vanta e si gonfia il petto dicendo che odia la politica.

Non sa, l’imbecille, che dalla sua ignoranza politica nasce la prostituta, il bambino abbandonato, l’assaltante, il peggiore di tutti i banditi,
che è il politico imbroglione, il mafioso corrotto, il lacchè delle imprese nazionali e multinazionali."

(Bertolt Brecht)

Collettivo SDAI: collettivosdai.altervista.org, facebook.
Movimento Studentesco Catanese: www.movimentostudentesco.org

https://github.com/ShinDarth
http://shinworld.altervista.org
http://www.openprogrammers.it

LinuxMint user.
sblite82
Matricola
*
Offline Offline

Posts: 26


« Reply #2 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...
Logged
Shin
Forumista
***
Offline Offline

Gender: Male
Posts: 822

Io sono ciò che sono per ciò che siamo tutti


WWW
« Reply #3 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 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?
« Last Edit: 26-05-2013, 22:06:48 by Shin » Logged

"Il peggiore analfabeta è l’analfabeta politico. Egli non sente, non parla, nè s’importa degli avvenimenti politici. Egli non sa che il costo della vita, il prezzo dei fagioli, del pesce, della farina, dell’affitto, delle scarpe e delle medicine dipendono dalle decisioni politiche.

L’analfabeta politico è così somaro che si vanta e si gonfia il petto dicendo che odia la politica.

Non sa, l’imbecille, che dalla sua ignoranza politica nasce la prostituta, il bambino abbandonato, l’assaltante, il peggiore di tutti i banditi,
che è il politico imbroglione, il mafioso corrotto, il lacchè delle imprese nazionali e multinazionali."

(Bertolt Brecht)

Collettivo SDAI: collettivosdai.altervista.org, facebook.
Movimento Studentesco Catanese: www.movimentostudentesco.org

https://github.com/ShinDarth
http://shinworld.altervista.org
http://www.openprogrammers.it

LinuxMint user.
Pages: [1]   Go Up
Print
Jump to: