Implementazione dell’ algortimodi Viterbi attraverso la soluzionedel problema di cammino mi-nimo tramite software specifico.

Università degli studi di Cagliari

Corso di Ricerca Operativa A.A. 1998/99

Prof. Paola Zuddas

Studenti: Simona

Andrea

Struttura della tesina

Problema fisico Modello matematico Presentazione del software Test del software Risultati ottenuti Conclusioni

Problema fisico

Introduzione ai sistemi di telecomunicazione

Trasmissione binaria Rumore come causa di perdita

d’informazione Codifica di uno stream Ridondanza

Codifica di un messaggio binario

mj-2

mj-1

mj

|

jx

||

jx

Bit del messaggio

Fig. 1.2 Codificatore in esame

Codificatore convoluzionale : registro a scorrimento.

Code trellis

00=a

01=b

10=c

11=d

a=00

b=01

c=10

d=11

00

11

11

00

10 01

01

10

Output

Algoritmo di Viterbi Schematizzazione dell’algortimo

11 01 11 00 01 10 00 11 112

0

3

3

0

2

2

3

1

1

2

2

2

1

3

3

2

1

3

3

3

3

3 3

3

2

2

2

1

4

4

Cammino a max. verosimiglianza

Y=

T

T T

T

Fig. 1.4 Schematizzazione dell’algoritmo di Viterbi.

Modello matematico

Shortest path

Minimizzare

m

i

m

j

ijij

xc

1 1

con

mise

moise

ise

xx

m

k

ki

m

j

ij

1

10

11

11

xij 0 i,j =1,2,….., m

Massimizzare w1 – w

m

con wi – w

j c

ij i,j = 1,2,….,m

wi i = 1,2,…..,m

Presentazione del software

Informazioni generali

Algoritmo di Dijkstra

ftp://theory.stanford.edu/pub/glodberg/stan-cs-93-1480.ps

Linguaggio C

Utilità del programma

calcolo del cammino minimo in un grafo orientato

percorso

peso associato al percorso

Test del software

Creazione file di test (manuale)

Nome del file: test.c linea di commento[opzionale] - c seguito da

un commentolinea del titolo [opzionale] – t seguita dal

titololinea tipo problema - sp (shortest path) con

parametri: numero di nodi, numero di archi

Creazione file di test (manuale)

linea del nodo – n seguito dal numero del nodo iniziale

linea dell’arco – a seguito dalla coda, testa, lunghezza

File di test: esempio

File input: Test.c

c Algoritmo_per_il_percorso_minimo

t Algoritmo di Viterbi

p sp 51 94

n 1

a 1 2 2

a 1 3 0

……….

Creazione file di test (automatica)

Uso del file “input.exe” Generazione file di test con un numero di

nodi prefissati e pesi random

Input.exe Two_q_run.exe

Test del software: caso analizzato

Risultati ottenuti

File di output……….

1 1 0

2 1 2

3 1 0

4 2 3

5 2 3

6 3 2

7 3 0

8 6 2

9 4 3

10 7 1

11 7 1

……….

Esame file di output

Estrapolazione albero cammino minimo

Peso vari cammini

Peso shortest path

2

4 5

9

1

3

6 7

11

14

8

22

15 12

16 17

23

25

18

21 20

13

19

10

27

30 31

32

36 37

43

26

28

24

29

35 34 33

38

40

44

49

41

47

42

45

50 51

33

46

48

Fig. 4.2 Albero ricavato dall’output del programma.

Conclusioni

Conclusioni

Test del software

Tipo di processore Tempo per 1003 nodi Tempo per 5003 nodi Tempo per 8807 nodi

Pentium 133 con 48 MB 0’ 50’’ 3’ 42’’ 5’ 11’’

Pentium 200 con 32 MB 0’ 22’’ 1’ 45’’ 3’ 12’’

Pentium 333 con 128 MB 0’5’’ 0’23’’ 0’39’’