טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentEinat Tevel
SubjectSignal Digitization using Shortest Path Methods
DepartmentDepartment of Electrical Engineering
Supervisors Full Professor Bruckstein Alfred
Professor Emeritus Feuer Arie
Full Thesis textFull thesis text - English Version


Abstract

Signal digitization is the process of representing a signal (usually analog) by a sequence of bits. For a general signal traversing in time and space there are countless ways of obtaining such a representation and numerous measures for deciding which is the ’best’. The classical approach for obtaining a digitized representation of an analog signal is by two, usually distinct, operations: sampling and quantization. Those two operations are usually employed consecutively one after the other. A more general digitization scheme can be thought of as defining areas in space and composing a sequence of the places that the signal has visited. This scheme has many degrees of freedom and raises many questions, for example: how are the areas chosen,what is the representation of the signal within an area, what is the cost of representing a transition of the signal from one area to another, etc.In our work we approach the problem of signal digitization through a graph theory point of view. We treat the problem as an optimization problem with nomenclature and solutions taken from graph-theory algorithms with respect to the classical rate-distortion problem. The outcome is an efficient scheme utilizing shortest path methods for the digitization of signals under a distortion constraint which is optimal in the operational rate distortion sense.