Diversity embedding for broadband communication

Given uncertainty in environment, a conservative approach is to design for the worst case, leading to a game-theoretic situation where the environment is controlled by an adversary. However, in many cases, the uncertainty arises from randomness, not an adversary. Wireless fading channels are an example of such a system, where the random fading causes uncertainty (at the transmitter) about rates supported by the channel. The question asked in the thesis is if this difference can be utilized to design communication schemes that opportunistically utilize the randomness, while giving some guarantees in performance for a worst case situation. The use of multiple transmit and receive antennas to deliver higher data rate at higher reliability, while transmitting over wireless channels, has been an extremely active research area over the past decade. The codes designed for such systems are referred to as space time codes. Diversity order, which captures reliability in terms of error performance, and rate impose a fundamental trade-off in space-time coding. High-rate space-time codes come at a cost of lower diversity order, and high reliability (diversity order) results in a lower rate. Over the past few years, this trade-off has been quite well understood for flat fading channels while far less attention has been given to Inter Symbol Interference (ISI) or broadband channels. Given the tradeoff between rate and reliability, if the overall system is designed for a fixed rate-diversity operating point it might be over-provisioning a resource which could be flexibly allocated to different applications. A new paradigm for the design of wireless links is proposed in this thesis which makes it possible to design a high rate code with an embedded high reliability code. This allows a form of communication where the high-rate code opportunistically takes advantage of good channel realizations whereas the embedded high-diversity code ensures that at least part of the information is received reliably. In this thesis the problem is studied from the point-of-view of information theoretic bounds on performance as well as explicit algebraic code designs for flat fading and ISI channels. Construction of a class of space-time codes which can flexibly allocate rate and reliability to an application is given. The constructions can be viewed as a generalization of classical multi-level codes to the fading multiple antenna channel. A systematic class of such codes is given using a construction which lifts rank properties of sets of binary matrix to the complex domain. These codes permit flexible allocation of rate and reliability for different streams. Diversity embedded codes for broadband (ISI) channels are developed by constructing maximal sets of Toeplitz binary matrices with rank guarantees. These constructions might be of independent interest in other distributed settings. From an information-theoretic point of view a channel is said to be successively refinable if it is possible to operate simultaneously at multiple points on the rate reliability tradeoff. In this thesis it is shown that the diversity multiplexing tradeoff for ISI channels with single degree of freedom, i.e., one transmit and many receive antennas or many transmit and one receive antennas, is successively refinable. This implies that one can design almost ideal opportunistic coding strategies for broadband (ISI) wireless channels. This observation could have an impact on the operation of broadband wireless links. The techniques developed for proving the result could also contribute to an understanding and design of schemes for systems with multiple transmit and receive antennas. Finally, the system implications of embedded diversity codes are explored by examining value to unequal error protection, rate opportunism, cell coverage extension and packet delay optimization. The delivery of images using a layered source coder, matched with appropriate choices of diversity embedded codes, is investigated and the benefits of the diversity embedded codes are illustrated. These applications demonstrate that diversity-embedded codes have the potential to outperform traditional single-layer codes in moderate SNR regimes.

A profiling framework for high level design space exploration for memory and system architectures

In 1971, the first microprocessor produced in mass production had 2300 transistor and was able to compute 60'000 operations per second at 740 kHz. Nowadays, even a common gaming console uses a central unit including 243 millions of transistors running at 4 GHz separated in a 9-cores architecture. This exponential evolution following the famous "Moore's Law" is possible thanks to the innovations made in every domain implied in a chip conception and allows chipset creation targeting a more and more wide range of applications. This variety of processors implies a great number of variations in the hardware choices, to match application (general purpose processor, digital signal processor, application-specific processor…), performance requirements and / or other operative constraints such as power consumptions. The applications running on these powerful solutions are growing in complexity exponentially as well, relying on more and more sophisticated software. Consequently the design team is facing a real challenge when designing and implementing an optimal architectural solution. To ease their task, the trend in computer aided design is to develop integrated frameworks for simulation and design, providing all the tools needed during the process, in a top-down approach. These tools allow system specification by means of abstract concurrent entities down to final implementation by means of successive refinements of the different entities and of the communication among then. In parallel, these hardware solutions run applications of a constantly increasing complexity, leading to the need for more and more intensive specification and validation tasks, by means of abstract software descriptions, typically referred to as verification models. These models implement all the functionalities of the application and thus, from the end of this specification phase, the abstract description of the application in the verification model becomes the most reliable reference for the corresponding application. All these reasons make the intuitive understanding of the processing complexity and tend to create redesign loops in the conception process when realizing that the initial architecture choices were sub-optimal (or even wrong), preventing the system to meet the desired performance constraints. In this case, a costly re-design iteration is mandatory, targeting a new platform choice but introducing delay and cost in the design causing the project to arrive too late on the market. Obviously, to eliminate these re-design iterations and to be able to help as soon as possible, the preliminary complexity analysis should be performed before starting the design of the target architecture. Since the first step of the design cycle implies an algorithm description through a verification model, it is desirable to perform the complexity study on this model. Indeed, though considerable efforts are carried out on developing powerful co-design tools, by means high-level abstract descriptions, fast prototyping and flexible design-reusability; no automatic tool is available to help the designer in the first analysis and comprehension phase. Moreover, the size of verification models is growing together with the complexity of the applications, and it is not surprising to have to deal with verification models of tens of thousands of source code lines; consequently, paper-and-pencil and manual-instrumentation analysis methods are neither feasible nor reliable any longer. Furthermore, static complexity evaluations, not taking into account the dynamic dependency of the complexity from the input data, are becoming less and less meaningful for the development of cost-effective solutions. Worst-case analysis is typically suitable for real-time control applications but it cannot be applied in all the cases in which quality-of-service/cost trade-offs are of concern; for instance, a multimedia or signal-processing architecture developed to support the worst-case scenario would simply result to be too expensive and under-exploited for most of the processing time. This dissertation presents a new approach to algorithmic complexity analysis, called the Software Instrumentation Tool (SIT), based on the previous observations and aiming at filling the gap in state of the art tools. The main goal of the SIT is to provide a high-level analysis framework for both a faithful design-oriented evaluation of the computational complexity of verification models and a hardware simulation of the projected architecture. The breakthrough in this version of the SIT is to provide a full set of results about complexity in a complete framework, allowing to use all these data in a methodology able to fill the gap from verification model to hardware implementation or algorithm porting. The analysis is performed at the highest possible abstraction level, i.e. at source code language level, in order to adhere to the same degree of abstraction of verification models; that is, the analysis is not biased by the underlying architecture over which the verification model is tested or by the compilation process. The analysis strictly depends on the input data, in order to take into account the real algorithmic complexity in real working conditions and relies on a completely automatic process, performed directly on the source code of verification models, without forcing the designer to make any manual modification such as source code rewriting or manual instrumentation. SIT approach to complexity analysis is based on the instrumentation by means of C++ operator overloading. SIT analyzes C source code and is capable to instrument, automatically, any legal C data-type or operation or statement, providing eventually an exhaustive complexity analysis at C language level. The tool is building on a core system (a core for the base algorithmic complexity, a second for memory analysis) and supports module extensions (a module for critical path evaluation, a module for data transfer, both can be plugged in the memory core). All the cores and modules are reporting their results in a single visual interface, allowing a quick and efficient complexity overview as well as an in-depth result exploration. As SIT allows extracting meaningful complexity measures directly from the verification models in the preliminary analysis and comprehension phase, the designer benefits from a tool-assisted approach allowing to step to the latest design phases through intermediate tools. The results provided by the first version of the SIT are computational data (what types of operation are performed? On which type of data? ...) and memory usage analysis (how many memory accesses? In which function?). This build of the SIT includes a customizable memory usage analysis, made possible by the simulation of (customizable) virtual memory architectures; this allows to focus the analysis on other aspects of the algorithmic complexity which could not otherwise be estimated by means of static analysis methods, or software profilers, or instruction-level profilers. Another novelty in the SIT is the data-transfer module, allowing both a quick and efficient overview of the main data flows inside the virtual architecture (thanks to a graphical representation of the mains transfers) and a precise in depth analysis of bandwidth and data transfers between functions (thanks to the detailed view included in Sitview). The latest result is the critical path evaluation analysis, allowing to detect the major functions of the execution tree and to extract information about parallelism at different level, from function to algorithm level. All these information are provided through the SIT graphical interface SitView, and a methodology is described to step from the high-level verification model in C to an actor language partioning based on the tool analysis. This partition can be used with dedicated actor languages to create a FPGA code or to create an optimized hardware solution, most probably better than an instinctively created hardware.

EPFL2007

Trustworthy Biometric Verification under Spoofing Attacks

Ivana Chingovska

The need for automation of the identity recognition process for a vast number of applications resulted in great advancement of biometric systems in the recent years. Yet, many studies indicate that these systems suffer from vulnerabilities to spoofing (presentation) attacks: a weakness that may compromise their usage in many cases. Face verification systems account for one of the most attractive spoofing targets, due to the easy access to face images of users, as well as the simplicity of the spoofing attack manufacturing process. Many counter-measures to spoofing have been proposed in the literature. They are based on different cues that are used to distinguish between real accesses and spoofing attacks. The task of detecting spoofing attacks is most often considered as a binary classification problem, with real accesses being the positive class and spoofing attacks being the negative class. The main objective of this thesis is to put the problem of anti-spoofing in a wider context, with an accent on its cooperation with a biometric verification system. In such a context, it is important to adopt an integrated perspective on biometric verification and anti-spoofing. In this thesis we identify and address three points where integration of the two systems is of interest. The first integration point is situated at input-level. At this point, we are concerned with providing a unified information that both verification and anti-spoofing systems use. The unified information includes the samples used to enroll clients in the system, as well as the identity claims of the client at query time. We design two anti-spoofing schemes, one with a generative and one with a discriminative approach, which we refer to as client-specific, as opposed to the traditional client-independent ones. The proposed methods are applied on several case studies for the face mode. Overall, the experimental results prove the integration to be beneficial for creating trustworthy face verification systems. At input-level, the results show the advantage of the client-specific approaches over the client-independent ones. At output-level, they present a comparison of the fusion methods. The case studies are furthermore used to demonstrate the EPS framework and its potential in evaluation of biometric verification systems under spoofing attacks. The source code for the full set of methods is available as free software, as a satellite package to the free signal processing and machine learning toolbox Bob. It can be used to reproduce the results of the face mode case studies presented in this thesis, as well as to perform additional analysis and improve the proposed methods. Furthermore, it can be used to design case studies applying the proposed methods to other biometric modes. At the second integration point, situated at output-level, we address the issue of combining the output of biometric verification and anti-spoofing systems in order to achieve an optimal combined decision about an input sample. We adopt a multiple expert fusion approach and we investigate several fusion methods, comparing the verification performance and robustness to spoofing of the fused systems. The third integration point is associated with the evaluation process. The integrated perspective implies three types of inputs for the biometric system: real accesses, zero-effort impostors and spoofing attacks. We propose an evaluation methodology for biometric verification systems under spoofing attacks, called Expected Performance and Spoofability (EPS) framework, which accounts for all the three types of input and the error rates associated with them. Within this framework, we propose the EPS Curve (EPSC), which enables unbiased comparison of systems.

EPFL2016

A profiling framework for high level design space exploration for memory and system architectures

EPFL2007

Trustworthy Biometric Verification under Spoofing Attacks

Ivana Chingovska

EPFL2016