Optimal implementation of a recursive least squares algorithm : TDC case study

Nowadays, data analysis has a wide range usage all around the world due to its necessity and this usage is increasing day by day. Typically, different algorithms are used to analyse data and they are becoming more crucial with the daily increasing new data sources. Data analysis helps to discover useful information, suggesting conclusions, and supporting decision-making. Data analysis can be done by various ways as according to the conditions and demands of different fields such as science, business, social science dissertation etc. In general, data analysis supports the researcher to reach a conclusion after the collection of data. Modelling the data and estimating the model parameters provides a simple and useful conclusion instead of an enormous number of data set. For the modelling, priori information can be used to estimate the more accurate model. On the other hand, if the estimated model is known before, it is not necessary to use priori information. Estimated model is directly applied to input data and according to it, unknown parameters can be obtainable. In this thesis, general-purpose estimation interface is designed to use for any kind of data and it includes various estimation options. User can easily choose one or more of the options depending on the application. This choice finds the unknown parameters of the chosen model and it provides the user with the graphical interface. It is possible to analyse the final equation and to visualise the data set and estimation according to the user’s choice. For the estimation, different algorithms are designed in C to choose from: o Least Squares Method (LS) o Recursive Least Squares Method (RLS)  Linear Estimation  Second Order Polynomial Estimation  Gaussian Estimation N viii As a case study, Time to Digital Converter (TDC) is chosen and the measurement of the TDC is processed as a collection of data. This data set is processed in designed C code. Working in the real time plays a crucial role, so the recursive method has been chosen. Firstly, a histogram is obtained to create the graph data set that will be processed in coded RLS algorithm in C. According to the obtained graph, Gaussian model is found as a fitting curve. Gaussian RLS method is used to obtain the unknown parameters of the Gaussian equation. Same data are processed in MATLAB and the results are compared with those of the C code. This comparison verified the correctness of the results obtained in C. Bambu that is provided by Politecnico di Milano in Linux is used to implement the designed algorithm in FPGA. Bambu generates HDL description from the C code. C code has been optimized to make it convertible to Verilog by using Bambu and functional Verilog code has been obtained.

Al giorno d’oggi l’analisi dei dati ha un vasto utilizzo in tutto il mondo a causa della sua necessità e il suo uso incrementa di giorno in giorno. Tipicamente, vengono impiegati diversi algoritmi per analizzare i dati, ed essi stanno acquisendo maggiore importanza con l’aumentare quotidiano di nuove sorgenti di dati. L’analisi dei dati è uno strumento utile per scoprire informazioni utili, suggerire conclusioni e prendere decisioni; essa può essere eseguita in diversi modi, a seconda delle condizioni e delle richieste dei vari campi di ricerca, per esempio scienza, business, scienze umane. In generale, l’analisi dei dati aiuta il ricercatore a raggiungere una conclusione dopo la raccolta dei dati. Costruire un modello dei dati e stimare i parametri del modello fornisce una conclusione semplice ed efficace invece di un enorme numero di dati. Nella costruzione del modello, le informazioni a priori possono essere usate per stimare il modello più accurato. D’altra parte, se il modello stimato è già conosciuto, l’utilizzo di informazioni a priori non è necessario. Il modello stimato viene applicato direttamente ai dati inseriti e i parametri sconosciuti possono essere ottenuti sulla base di esso. In questa tesi viene progettata un’interfaccia di stima generica applicabile a ogni tipo di dati, che include diverse opzioni di stima. L’utilizzatore può facilmente scegliere una o più opzioni, a seconda del campo di applicazioni. Questa scelta permette di trovare i parametri sconosciuti del modello prescelto e fornisce l’interfaccia grafica all’utilizzatore. È possibile analizzare l’equazione finale e visualizzare i dati e la stima a seconda della scelta dell’utilizzatore. Per eseguire la stima, è possibile scegliere tra diversi algoritmi progettati in C: o Metodo dei minimi quadrati o Metodo dei minimi quadrati ricorsivi  Stima Lineare  Stima dei Polinomi di Secondo Grado  Stima Gaussiana Come caso studio è stato scelto un Time to Digital Converter (TDC) e la misurazione del TDC è stata processata come raccolta di dati. Questo set di dati è stato processato nel codice C progettato. L’elaborazione in tempo reale gioca un ruolo fondamentale, cosi è stato scelto il metodo ricorsivo. In primo luogo, è stato ottenuto un istogramma per creare il grafico dei dati che saranno processati nell’algoritmo minimi quadrati ricorsivi in C. Sulla base del grafico ottenuto, è stato identificato un modello Gaussiano come fitting curve. Il metodo Gaussiano dei minimi quadrati ricorsivi è stato usato per ottenere i parametri sconosciuti dell’equazione Gaussiana. Gli stessi dati sono stati processati in MATLAB e i risultati sono stati paragonati a quelli del codice C. Questa comparazione ha verificato la correttezza dei risultati ottenuti in C. Per eseguire l'algoritmo progettato in FPGA è stato usato Bambu per Linux fornito dal Politecnico di Milano. Bambu genera una descrizione HDL dal codice C. Il codice C è stato ottimizzato per renderlo convertibile in Verilog utilizzando Bambu ed è stato ottenuto un codice funzionale Verilog.