M.Sc Thesis


M.Sc StudentTevel Einat
SubjectSignal Digitization using Shortest Path Methods
DepartmentDepartment of Electrical and Computers Engineering
Supervisors PROF. Alfred Bruckstein
PROFESSOR EMERITUS Arie Feuer
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.