## Tesi etd-05262010-170955 |

Thesis type

Tesi di dottorato di ricerca

Author

DUBBINI, NEVIO

email address

dubbini@mail.dm.unipi.it, nevio.dubbini@gmail.com

URN

etd-05262010-170955

Title

Left invertibility of I/O quantized systems: IFS, number theory, cryptography, algorithms

Settore scientifico disciplinare

ING-INF/04

Corso di studi

MATEMATICA

Supervisors

**tutor**Prof. Bicchi, Antonio

**correlatore**Piccoli, Benedetto

Parole chiave

- Kronecker's theorem
- left invertibility
- IFS theory
- Mahler measure
- density of fractional parts
- quantized systems

Data inizio appello

03/06/2010;

Consultabilità

Parziale

Data di rilascio

03/06/2050

Riassunto analitico

This thesis addresses left invertibility for dynamical discrete--time control systems evolving in a continuous state--space, with inputs and outputs in discrete sets. More precisely, inputs are arbitrary sequences of symbols in a finite alphabet, each symbol being associated to a specific action on the system. Information available on the system is represented by

sequences of output values in a discrete set. Such outputs are obtained by quantization, i.e. are generated by the system evolution according to a given partition of the state-space. Left

invertibility has to do with the injectivity of I/O map, that is the possibility of recovering the unknown inputs that generate the observed output sequences.

Two class of systems are examined: nonlinear systems with a contraction property (called joint contraction), and linear I/O quantized systems with uniform output generating partition (with no

contraction hypothesis). For joint contractive systems left invertibility is addressed using the theory of Iterated Function Systems (IFS), a tool developed for the study of fractals: the IFS

naturally associated to a system and the geometric properties of its attractor are linked to the invertibility property of the system.

Our main result here is a necessary and sufficient condition for left invertibility. For linear I/O quantized systems left invertibility is reduced, under suitable conditions, to the notion of left D-invertibility: these conditions have to do with density of fractional parts in the unit cube, and are found using number

theoretic methods, involving a generalization of the classical theorem of Kronecker in terms of Mahler measure of minimal polynomials. While left invertibility takes into account membership

to sets of a given partition, left D-invertibility considers only membership to a single set, and is therefore much easier to

detect: one important result here is a method to compute left D-invertibility for all linear systems with no eigenvalue of modulus one. The main results for linear I/O quantized systems show the equivalence between left D-invertibility and left invertibility for a full measure set of matrices, and stronger results in this

direction are proved for unidimensional system, and for multi-input single-output (MISO) systems.

Moreover a cryptographic system based on left invertibility of I/O quantized systems is presented, which provides a secure

communication method. Finally algorithms are given, to check left invertibility of a I/O quantized linear systems, and to recover

inputs from the knowledge of the output sequences.

sequences of output values in a discrete set. Such outputs are obtained by quantization, i.e. are generated by the system evolution according to a given partition of the state-space. Left

invertibility has to do with the injectivity of I/O map, that is the possibility of recovering the unknown inputs that generate the observed output sequences.

Two class of systems are examined: nonlinear systems with a contraction property (called joint contraction), and linear I/O quantized systems with uniform output generating partition (with no

contraction hypothesis). For joint contractive systems left invertibility is addressed using the theory of Iterated Function Systems (IFS), a tool developed for the study of fractals: the IFS

naturally associated to a system and the geometric properties of its attractor are linked to the invertibility property of the system.

Our main result here is a necessary and sufficient condition for left invertibility. For linear I/O quantized systems left invertibility is reduced, under suitable conditions, to the notion of left D-invertibility: these conditions have to do with density of fractional parts in the unit cube, and are found using number

theoretic methods, involving a generalization of the classical theorem of Kronecker in terms of Mahler measure of minimal polynomials. While left invertibility takes into account membership

to sets of a given partition, left D-invertibility considers only membership to a single set, and is therefore much easier to

detect: one important result here is a method to compute left D-invertibility for all linear systems with no eigenvalue of modulus one. The main results for linear I/O quantized systems show the equivalence between left D-invertibility and left invertibility for a full measure set of matrices, and stronger results in this

direction are proved for unidimensional system, and for multi-input single-output (MISO) systems.

Moreover a cryptographic system based on left invertibility of I/O quantized systems is presented, which provides a secure

communication method. Finally algorithms are given, to check left invertibility of a I/O quantized linear systems, and to recover

inputs from the knowledge of the output sequences.

File

Nome file | Dimensione |
---|---|

1 file non consultabili su richiesta dell'autore. |