M.Sc Student | Tevel Einat |
---|---|

Subject | Signal Digitization using Shortest Path Methods |

Department | Department of Electrical Engineering |

Supervisors | Professor Alfred Bruckstein |

Professor Emeritus Arie Feuer | |

Full Thesis text |

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.