A study on set variable representations in constraint programming

Il lavoro presentato in questa tesi si colloca nel contesto della programmazione con vincoli, un paradigma per modellare e risolvere problemi di ricerca combinatoria che richiedono di trovare soluzioni in presenza di vincoli. Una vasta parte di questi problemi trova naturale formulazione attraverso il linguaggio delle variabili insiemistiche. Dal momento che il dominio di tali variabili può essere esponenziale nel numero di elementi, una rappresentazione esplicita è spesso non praticabile. Recenti studi si sono quindi focalizzati nel trovare modi efficienti per rappresentare tali variabili. Pertanto si è soliti rappresentare questi domini mediante l'uso di approssimazioni definite tramite intervalli (d'ora in poi rappresentazioni), specificati da un limite inferiore e un limite superiore secondo un'appropriata relazione d'ordine. La recente evoluzione della ricerca sulla programmazione con vincoli sugli insiemi ha chiaramente indicato che la combinazione di diverse rappresentazioni permette di raggiungere prestazioni di ordini di grandezza superiori rispetto alle tradizionali tecniche di codifica. Numerose proposte sono state fatte volgendosi in questa direzione. Questi lavori si differenziano su come è mantenuta la coerenza tra le diverse rappresentazioni e su come i vincoli vengono propagati al fine di ridurre lo spazio di ricerca. Sfortunatamente non esiste alcun strumento formale per paragonare queste combinazioni. Il principale obiettivo di questo lavoro è quello di fornire tale strumento, nel quale definiamo precisamente la nozione di combinazione di rappresentazioni facendo emergere gli aspetti comuni che hanno caratterizzato i lavori precedenti. In particolare identifichiamo due tipi possibili di combinazioni, una forte ed una debole, definendo le nozioni di coerenza agli estremi sui vincoli e sincronizzazione tra rappresentazioni. Il nostro studio propone alcune interessanti intuizioni sulle combinazioni esistenti, evidenziandone i limiti e svelando alcune sorprese. Inoltre forniamo un'analisi di complessità della sincronizzazione tra minlex, una rappresentazione in grado di propagare in maniera ottimale vincoli lessicografici, e le principali rappresentazioni esistenti.

Caratterizzazione e generazione di segnali PWM per amplificatori in classe D ad alta efficienza

The convergence of information technology and consumer electronics towards battery powered portable devices has increased the interest in high efficiency, low dissipation amplifiers. Class D amplifiers are the state of the art in low power consumption and high performance amplification. In this thesis we explore the possibility of exploiting nonlinearities introduced by the PWM modulation, by designing an optimized modulation law which scales its carrier frequency adaptively with the input signal's average power while preserving the SNR, thus reducing power consumption. This is achieved by means of a novel analytical model of the PWM output spectrum, which shows how interfering harmonics and their bandwidth affect the spectrum. This allows for frequency scaling with negligible aliasing between the baseband spectrum and its harmonics. We performed low noise power spectrum measurements on PWM modulations generated by comparing variable bandwidth, random test signals with a variable frequency triangular wave carrier. The experimental results show that power-optimized frequency scaling is both feasible and effective. The new analytical model also suggests a new PWM architecture that can be applied to digitally encoded input signals which are predistorted and compared with a cosine carrier, which is accurately synthesized by a digital oscillator. This approach has been simulated in a realistic noisy model and tested in our measurement setup. A zero crossing search on the obtained PWM modulation law proves that this approach yields an equivalent signal quality with respect to traditional PWM schemes, while entailing the use of signals whose bandwidth is remarkably smaller due to the use of a cosine instead of a triangular carrier.