Campi finiti e segnale GPS

Brecciaroli, Virginia (2013) Campi finiti e segnale GPS. [Laurea magistrale], Università di Bologna, Corso di Studio in Matematica [LM-DM270]
Documenti full-text disponibili:
[img]
Anteprima
Documento PDF
Download (1MB) | Anteprima

Abstract

Lo scopo della tesi è quello di studiare una delle applicazioni della teoria dei campi finiti: il segnale GPS. A questo scopo si descrivono i registri a scorrimento a retroazione lineare (linear feedback shift register, LFSR), dispositivi utili in applicazioni che richiedono la generazione molto rapida di numeri pseudo-casuali. I ricevitori GPS sfruttano il determinismo di questi dispositivi per identificare il satellite da cui proviene il segnale e per sincronizzarsi con esso. Si inizia con una breve introduzione al funzionamento del GPS, poi si studiano i campi finiti: sottocampi, estensioni di campo, gruppo moltiplicativo e costruzione attraverso la riduzione modulo un polinomio irriducibile, fattorizzazione di polinomi, formula per il numero e metodi per la determinazione di polinomi irriducibili, radici di polinomi irriducibili, coniugati, teoria di Galois (automorfismo ed orbite di Frobenius, gruppo e corrispondenza di Galois), traccia, polinomio caratteristico, formula per il numero e metodi per la determinazione di polinomi primitivi. Successivamente si introducono e si esaminano sequenze ricorrenti lineari, loro periodicità, la sequenza risposta impulsiva, il polinomio caratteristico associato ad una sequenza e la sequenza di periodo massimo. Infine, si studiano i registri a scorrimento che generano uno dei segnali GPS. In particolare si esamina la correlazione tra due sequenze. Si mostra che ogni polinomio di grado n-1 a coefficienti nel campo di Galois di ordine 2 può essere rappresentato univocamente in n bit; la somma tra polinomi può essere eseguita come XOR bit-a-bit; la moltiplicazione per piccoli coefficienti richiede al massimo uno shift ed uno XOR. Si conclude con la dimostrazione di un importante risultato: è possibile inizializzare un registro in modo tale da fargli generare una sequenza di periodo massimo poco correlata con ogni traslazione di se stessa.

Abstract
Tipologia del documento
Tesi di laurea (Laurea magistrale)
Autore della tesi
Brecciaroli, Virginia
Relatore della tesi
Scuola
Corso di studio
Indirizzo
Curriculum B: Applicativo
Ordinamento Cds
DM270
Parole chiave
campi finiti registri a scorrimento a retroazione lineare polinomi irriducibili polinomi primitivi correlazione
Data di discussione della Tesi
13 Dicembre 2013
URI

Altri metadati

Statistica sui download

Gestione del documento: Visualizza il documento

^